Нужна помощь в оптимизации запроса MySQL без соединения

Мой запрос в настоящее время занимает примерно 3 секунды, и я уверен, что его можно оптимизировать. Я просто не могу понять, как его оптимизировать.

В моем приложении достаточно большая таблица products (примерно 500 000 записей). Каждый продукт может быть указан в одном из 50 доменов (перечисленных в таблице domains). Связи между продуктами и доменами хранятся в таблице domains_products (которая содержит примерно 1 400 000 записей). Медленный запрос находится в разделе администратора моего приложения, где мне нужно иметь возможность видеть продукты, которые НЕ указаны ни в одном домене.

Разобранный до голых костей с удаленными всеми несвязанными соединениями, рассматриваемый запрос выглядит следующим образом:

SELECT    `products`.*
FROM      `products`
LEFT JOIN `domains_products`
ON        `domains_products`.`product_id` = `products`.`id`
WHERE     `products`.`deleted` = 'N'
AND       `domains_products`.`domain_id` IS NULL
ORDER BY  `products`.`id` ASC

В таком виде запрос занимает более 3 секунд и возвращает чуть более 3000 товаров (что верно). Если я удалю любое предложение WHERE, запрос займет 0,12 секунды (но, очевидно, не вернет правильные результаты).

Обе таблицы используют механизм InnoDB. Таблица products имеет первичный ключ в столбце id и индекс в столбце deleted. В таблице domains_products есть только столбцы product_id и domain_id, первичный ключ находится в обоих этих столбцах, и у них обоих есть собственный индекс. Все соответствующие столбцы являются NOT NULL столбцами.

EXPLAIN дает мне это:

id select_type table            type possible_keys key        key_len ref         rows   Extra
1  SIMPLE      products         ref  deleted       deleted    1       const       188616 Using where
1  SIMPLE      domains_products ref  product_id    product_id 4       products.id 1      Using where; Using index; Not exists

Обратите внимание, что, хотя MySQL обнаружил правильные ключи, похоже, что на самом деле они их не используют.

Профайлер говорит следующее:

Status               Time
Starting             62 µs
Checking Permissions 7 µs
Checking Permissions 5 µs
Opening Tables       38 µs
System Lock          13 µs
Init                 37 µs
Optimizing           17 µs
Statistics           1,3 ms
Preparing            25 µs
Executing            5 µs
Sorting Result       5 µs
Sending Data         3,3 s
End                  28 µs
Query End            8 µs
Closing Tables       25 µs
Freeing Items        297 µs
Logging Slow Query   4 µs
Cleaning Up          5 µs

Обратите внимание, что он, кажется, висит на Sending Data. Я попытался заменить соединение на NOT IN:

SELECT `products`.*
FROM   `products`
WHERE  `products`.`deleted` = 'N'
AND    `product`.`id` NOT IN (
    SELECT `product_id`
    FROM   `domains_products`
)
ORDER BY `products`.`id` ASC

Этот запрос дает точно такие же результаты, но занимает 3,8 секунды.

Может ли кто-нибудь указать мне правильное направление для оптимизации этого запроса?