Побитовая маска против эффективности IN () в sqlite? - PullRequest
Новая
       41

Побитовая маска против эффективности IN () в sqlite?

10 голосов
/ 04 марта 2011

У меня есть два способа выбрать набор записей из базы данных: 

  SELECT ... WHERE `level` IN (1,2,4,8) LIMIT ...;

или 

  SELECT ... WHERE `level` & mask LIMIT ...;

Всего существует 4 «уровня», пронумерованных 1,2,4,8 (из-за возможности использовать ту же маску и в других местах). Обе скобки IN() или mask могут содержать любой набор из одного или нескольких из 4 уровней. Столбец индексируется. Запрос по-прежнему длится дольше, чем удобно, и мы пытаемся оптимизировать его для скорости.

Вчера один человек сказал, что решил использовать наивный IN (), чтобы получить до четырех сравнений, и вместо этого я должен использовать битовую маску. Сегодня я слышал, что битовая маска полностью подорвет преимущества индекса по столбцу и будет намного медленнее.

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

1 Ответ

18 голосов
/ 07 сентября 2013

Ваш вопрос довольно старый, но я все же собираюсь на него ответить.

Скорее всего, битовая маска будет медленнее, так как она должна обрабатывать битовое И, тогда как IN будет использовать проиндексировал значение level, чтобы найти его в аргументах, заключенных в скобки (что, я считаю, должно быть единственной O(log(n)) операцией).

Теперь, вещь, котораяВы можете пропустить, если они не делают то же самое.

Ваш первый запрос просто проверит, является ли level 1, 2, 4 или 8.

Ваш второйзапрос, или на самом деле что-то вроде: 

SELECT ... WHERE (`level` & mask) = mask LIMIT ...;

Имеет возможность поиска levels, который содержит желаемую маску и, возможно, еще немного, в вашем случае это может быть проверка всех комбинаций значений от 1 до 15.Следовательно, производительность снижается.

Что касается грубого теста, предложенного @AlanFoster, я с ним не согласен.

Гораздо лучше поставить префикс запроса:

  • EXPLAIN, оr
  • EXPLAIN QUERY PLAN

и проверьте, сколько строк соответствует SQLite.

Обновление

EXPLAIN QUERY PLAN SELECT * FROM ... WHERE level IN (2, 3);

SEARCH TABLE ... USING INDEX ..._level (level=?) (~20 rows)

EXPLAIN QUERY PLAN SELECT * FROM ... WHERE (level & 2) = 2;

SCAN TABLE ... (~500000 rows)

Как видите, для побитового оператора И требуется полное сканирование таблицы.

...