Как выставить индексы для OR-запроса?

Question

[Futurism]

Добрый день.

Есть таблица вида

ID - int, auto increment
A - char(8) DEFAULT NULL,
B - char(8) DEFAULT NULL

И два индекса на поля A и B.

В такой таблице запрос вида SELECT count(*) from table WHERE A=xxx OR B=xxx выполняется неадекватно долго, хотя EXPLAIN показывает, что все (вроде бы?) хорошо:

possible_keys: A,B
          key: A,B
        Extra: Using union(A,B); Using where

Если разбить этот запрос на два - они отрабатывают моментально, но по разным причинам мне это не подходит.

Вопрос заключается в следующем:
1. почему этот запрос так сильно тормозит?
2. можно ли не меняя запроса (не разбивая его на два) добиться нормального быстродействия?

Comments

[FanatPHP]

Uneasy Hearts Weigh the Most, это будет на редкость бессмысленное занятие. запрос же не AND

[FanatPHP]

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

[FanatPHP]

as of why,

This often works very well, but sometimes the algorithm’s buffering, sorting, and merging operations use lots of CPU and memory resources. This is especially true if not all of the indexes are very selective, so the parallel scans return lots of rows to the merge operation.

https://www.oreilly.com/library/view/high-performa...

[Алексей Горбунов]

Можете применить научный подход. В дискретной математике есть теорема о полноте, по которой если убрать из операций OR, то полнота все равно сохраняется. Соответственно OR можно заменить операциями NOT и AND.

В вашем случае A=xxx OR B=xxx эквивалентно NOT (A<>xxx AND B<>xxx)

[ComodoHacker]

Futurism, а если самому переписать через union?

[ComodoHacker]

Алексей Горбунов, Все верно, осталось объяснить планировщику Мускула, как это поможет ускорить запрос.

[Алексей Горбунов]

ComodoHacker, Если есть индекс по А и В, то поможет

[FanatPHP]

ComodoHacker, ну вот Rsa ниже правильно пишет что там дубли будут

[d'Ivan]

Futurism
А какая версия Mysql используется?

[ComodoHacker]

Алексей Горбунов, Проверяли, или только предполагаете, что поможет?

[Алексей Горбунов]

ComodoHacker, Автор пусть проверяет

[FanatPHP]

Алексей Горбунов, автор уже проверил, можешь сливаться

Answer 1

[Rsa97]

OR, как и UNION DISTINCT, плохо работает при большом перекрытии данных.
Скажем, у вас в таблице миллион строк. По первому условию выбралось полмиллиона, по второму ещё полмиллиона. Если взять OR, то сколько уникальных строк должно быть в результате? Вот на выборке только уникальных строк и идут тормоза.
Быстро работает UNION ALL, но он не удаляет дубли строк.

Comments

[Rsa97]

FanatPHP, Тогда вторая и третья часть плохо индексироваться будут. Хотя в итоге может получиться и быстрее, чем OR.

EXPLAIN SELECT `a`, `b`
  FROM `test`
  WHERE `a` = 1 AND `b` = 1
UNION ALL SELECT `a`, `b`
  FROM `test`
  WHERE `a` = 1 AND `b` <> 1
UNION ALL SELECT `a`, `b`
  FROM `test`
  WHERE `a` <> 1 AND `b` = 1;

| id  | select_type  | table        | partitions | type  | possible_keys | key    | key_len | ref         | rows | filtered | Extra                    |
| --- | ------------ | ------------ | ---------- | ----- | ------------- | ------ | ------- | ----------- | ---- | -------- | ------------------------ |
| 1   | PRIMARY      | test         |            | ref   | key_ab,key_ba | key_ab | 10      | const,const | 1    | 100      | Using index              |
| 2   | UNION        | test         |            | range | key_ab,key_ba | key_ab | 10      |             | 9    | 100      | Using where; Using index |
| 3   | UNION        | test         |            | range | key_ab,key_ba | key_ba | 10      |             | 9    | 100      | Using where; Using index |

Можно ещё попробовать, например, NOT (A <> X AND B <> X).

EXPLAIN SELECT `a`, `b`
  FROM `test`
  WHERE NOT(`a` <> 1 AND `b` <> 1);

| id  | select_type | table | partitions | type  | possible_keys | key    | key_len | ref | rows | filtered | Extra                    |
| --- | ----------- | ----- | ---------- | ----- | ------------- | ------ | ------- | --- | ---- | -------- | ------------------------ |
| 1   | SIMPLE      | test  |            | index | key_ab,key_ba | key_ab | 10      |     | 100  | 55       | Using where; Using index |

[FanatPHP]

Rsa97, я жестоко затупил, этот запро неправильный. удалил коммент
а у NOT (A <> X AND B <> X) explain идентичный A=xxx OR B=xxx

[Rsa97]

FanatPHP, Действительно, идентичный. Возможно, что MySQL раскрывает NOT, переделывая из AND в OR.
А запрос с UNION ALL отрабатывает правильно.

[Rsa97]

FanatPHP, Странно. Такого быть не должно. Там же тождество

(a & b) | (a & !b) | (!a & b) = (a & (b | !b)) | (!a & b) = 
= a | (!a & b) = !(!a & !(!a & b)) = !(!a & (a | !b)) =
= !((!a & a) | (!a & !b)) = !(!a & !b) = a | b

Разве что где-то NULL затесался, тогда любые чудеса могут быть.

[FanatPHP]

действительно, там нуллов вагон

[FanatPHP]

ну то есть ок, вариант с юнионами работает
если воткнуть два составных индекса

[ComodoHacker]

Мог бы помочь bitmap индекс или колоночное хранение, но Мускул их не умеет.

Или уже умеет?

[Rsa97]

FanatPHP, В принципе, достаточно одного составного и одного простого. Но вариант плохо масштабируемый. Если в OR будет три условия, то получим уже семь SELECT'ов в UNION, если четыре, то 15 и т.д.

[FanatPHP]

Не, лучше два составных - тогда будет using index, вся фильтрация будет проходить в индексе
Но так-то да, это сферическй запрос в вакууме, и не масштабируется.

[FanatPHP]

ComodoHacker, не умеет
но вот идея переехать в кликхаус стоит рассмотрения

[Rsa97]

FanatPHP, На неравенство индекс не работает.
a = x and b = x - составной индекс (a, b).
a = x and b <> x - составной индекс (a, b), только часть a.
a <>x and b = x - достаточно индекса (b).

[FanatPHP]

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

[Rsa97]

FanatPHP, У меня EXPLAIN показывает Using where; Using index. Хотя и в таблице у меня только a и b были.
Если MySQL сможет использовать индекс частично как покрывающий, то да, два составных будут лучше.

[FanatPHP]

я вижу на эксплейне key_ba :)
тут дело не в покрытии, а в том что идет поиск прямо в индексе
грубо коворя мы находим в индексе значение x для а, и тут же, в этой же самой ячейке индекса смотрим, не равняется ли b = x. И если равняется, то убираем строку из выборки.
а при одиночном индексе для всех найденных "а=х" читается значение b из базы.

[Rsa97]

FanatPHP, А я только два составных индекса делал. Если сделать ещё и два простых, то он составные вообще не использует, слишком маленькая таблица.

тут дело не в покрытии, а в том что идет поиск прямо в индексе

Это и называется "покрывающий индекс". Если размер записи индекса гораздо меньше размера всей строки, то MySQL может использовать индекс даже для неиндексного поиска (например, LIKE '%vasya%'). Ускорение достигается за счёт более плотного расположения данных в индексе, чем в самой таблице, и, соответственно, лучшего использования кэша диска.