EXISTS выполняется 0 секунд, а NOT EXISTS 2.5 секунды

Имеются две таблицы:

CREATE TABLE messages(
    id BIGINT PRIMARY KEY NOT NULL AUTO_INCREMENT,
    to_id INT,
    from_id INT NOT NULL,
    created_at DATETIME NOT NULL DEFAULT NOW(),
    text BLOB,
    photo VARCHAR(255),
    party_id INT,
    important BOOLEAN NOT NULL DEFAULT false,
    CONSTRAINT FOREIGN_TO
    FOREIGN KEY(to_id) REFERENCES users(id) ON DELETE CASCADE ON UPDATE CASCADE,
    CONSTRAINT FOREIGN_FROM
    FOREIGN KEY(from_id) REFERENCES users(id) ON DELETE CASCADE ON UPDATE CASCADE,
    CONSTRAINT FOREIGN_MESSAGES_PARTY
    FOREIGN KEY(party_id) REFERENCES parties(id) ON DELETE CASCADE ON UPDATE CASCADE
) ENGINE = InnoDB DEFAULT CHARSET = utf16;
CREATE TABLE who_saw_message(
    message_id BIGINT NOT NULL,
    who_saw_id INT NOT NULL,
    CONSTRAINT FOREIGN_WHO_SAW_MESSAGE_MESSAGE_ID
    FOREIGN KEY(message_id) REFERENCES messages(id) ON DELETE CASCADE ON UPDATE CASCADE,
    CONSTRAINT FOREIGN_WHO_SAW_MESSAGE_WHO_SAW_ID
    FOREIGN KEY(who_saw_id) REFERENCES users(id) ON DELETE CASCADE ON UPDATE CASCADE
    //для теста не будем делать primary key(message_id,who_saw_id)
) ENGINE = InnoDB DEFAULT CHARSET = utf8;

В 1-ой таблице хранятся сообщения(1000 записей), во 2-ой хранятся записи какие прочитал пользователь сообщения(1 000 000 записей, столько записей вставлено для проверки). Ввожу запрос который узнает какие сообщения в группе мной непрочитаны:

SELECT id FROM messages WHERE party_id=25 AND NOT EXISTS(SELECT message_id FROM who_saw_message WHERE message_id=id AND who_saw_id=91); - запрос выполняется 2.5 секунды и возвращает 2 записи

Однако если заменить NOT EXISTS на просто EXISTS, то запрос выполняется 0 секунд

SELECT id FROM messages WHERE party_id=25 AND EXISTS(SELECT message_id FROM who_saw_message WHERE message_id=id AND who_saw_id=91); - запрос выполняется 0.00 секунд и возвращает 40 записей

EXPLAIN запросов:

Почему 1-ый запрос выполняется так долго и как сделать его по скорости таким же как и 2-ой запрос? Таблицы непроиндексированы.

P.S Проблему решил просто заменив

SELECT id FROM messages WHERE party_id=25 AND NOT EXISTS(SELECT message_id FROM who_saw_message WHERE message_id=id AND who_saw_id=91); 

на

SELECT id FROM messages WHERE party_id=25 AND EXISTS(SELECT message_id FROM who_saw_message WHERE message_id=id AND who_saw_id=91)!=true; - запрос выполняется 0 секунд

EXPLAIN нового супер быстрого запроса:

Но все равно хотелось бы узнать почему так происходит.