(Побитовые) надмножества и подмножества в MySQL

Question

В MySQL действуют следующие запросы:

SELECT * FROM table WHERE field & number = number; 
# to find values with superset of number's bits

SELECT * FROM table WHERE field | number = number; 
# to find values with subset of number's bits

... если индекс для поля был создан?

Если нет, есть ли способ заставить его работать быстрее?

Answer 1

Обновление:

Смотрите эту запись в моем блоге для деталей производительности:

• Битовые операции и индексы

---

SELECT * FROM table WHERE field & number = number

SELECT * FROM table WHERE field | number = number

Этот индекс может быть эффективен двумя способами:

1. Чтобы избежать раннего сканирования таблицы (поскольку сравниваемое значение содержится в самом индексе)
   • Для ограничения диапазона исследуемых значений.

Ни одно из условий в вышеприведенных запросах не является sargable , этот индекс не будет использоваться для сканирования диапазона (с такими условиями, как сейчас).

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

Если ваша таблица содержит, скажем, 100 байтов на строку в среднем и 1,000,000 записей, то при сканировании таблицы потребуется сканировать 100 Mb данных.

Если у вас есть индекс (с 4 -байтовым ключом, 6 -байтным указателем строки и некоторыми внутренними издержками), запрос должен будет сканировать только 10 Mb данных плюс дополнительные данные из таблицы, если фильтр успешен.

• Сканирование таблицы более эффективно, если ваше состояние не является выборочным (у вас высокая вероятность соответствия этому условию).
• Сканирование индекса более эффективно, если ваше условие является выборочным (у вас низкая вероятность соответствия этому условию).

Оба эти запроса потребуют сканирования всего индекса.

Но переписав запрос AND, вы также сможете извлечь выгоду из ранжирования по индексу.

Это условие:

field & number = number

может соответствовать полям, только если старшие биты из установленного number установлены и в field.

И вы должны просто предоставить это дополнительное условие для запроса:

SELECT  *
FROM    table
WHERE   field & number = number
        AND field >= 0xFFFFFFFF & ~((2 << FLOOR(LOG(2, 0xFFFFFFFF & ~number))) - 1)

Это будет использовать диапазон для грубой фильтрации и условие для тонкой фильтрации.

Чем больше битов для number сброшено в конце, тем лучше.

Answer 2

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

Может быть, вы можете позвонить EXPLAIN по этим запросам и подтвердить мои пессимистические предположения. (помня, конечно, что большинство решений плана запросов основаны на конкретном экземпляре данной базы данных, то есть переменные объемы данных и / или просто данные с другим статистическим профилем могут давать разные планы).

Если предположить, что таблица содержит значительное количество строк и что «побитовые» критерии остаются достаточно избирательными), возможная оптимизация достигается, если избегать побитовой операции в каждой отдельной строке, переписав запрос с помощью конструкции IN (или с СОЕДИНЕНИЕМ)

Нечто подобное (концептуальное, то есть не проверенное)

CREATE TEMPORARY TABLE tblFieldValues
  (Field INT);

INSERT INTO tblFieldValues
   SELECT DISTINCT Field
   FROM table;

-- SELECT * FROM table WHERE field | number = number; 
-- now becomes
SELECT * 
FROM table t
WHERE field IN 
    (SELECT Field 
     FROM tblFieldValues 
     WHERE field | number = number); 

Полные преимущества такого подхода необходимо оценивать с различными вариантами использования (все из которых с большим количеством строк в таблице, так как в противном случае прямой подход "WHERE field | number = number" достаточно эффективен), но я подозреваю, что это может быть значительно быстрее. Дальнейшее усиление может быть достигнуто, если «tblFieldValues» не нужно воссоздавать каждый раз. Эффективное создание этой таблицы, конечно, подразумевает индекс поля в исходной таблице.

Answer 3

Я попробовал это сам, и побитовых операций недостаточно, чтобы помешать Mysql использовать индекс для столбца "field". Впрочем, вполне вероятно, что происходит полное сканирование индекса.