(Битовые) Суперсеты и Поднаборы в 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

Update:

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

• Bitwise operations and indexes

---

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 (или с 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); 

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

Answer 3

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