(Побитовое) Надмножества и подмножества в 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. Чтобы избежать раннего сканирования таблицы (поскольку сравниваемое значение содержится в самом индексе)
   • Ограничить диапазон исследуемых значений.

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

Однако точка 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 (или с помощью JOIN). )

Что-то в этом роде (концептуальное, т.е.не испытано)

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); 

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

Answer 3

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