(Bit a bit) Supersets e subconjuntos em MySQL

Question

As seguintes consultas eficazes no 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

... se um índice para o campo foi criado?

Se não, há uma maneira de torná-lo correr mais rápido?

Answer 1

Update:

Veja esta entrada no meu blog para mais detalhes de desempenho:

• operações e índices bit a bit

---

SELECT * FROM table WHERE field & number = number

SELECT * FROM table WHERE field | number = number

Este índice pode ser eficaz de duas maneiras:

1. Para evitar varreduras de tabela início (desde que o valor para comparar está contida no próprio índice)
   • Para limitar a gama de valores examinado.

Nem condição nas consultas acima é sargable , este é o índice não será utilizado na digitalização gama (com as condições como são agora).

No entanto, o ponto 1 ainda se mantém, eo índice pode ser útil.

Se a tabela contém, digamos, 100 por linha bytes em média, e os registros 1,000,000, então a verificação de tabela precisará 100 Mb varredura de dados.

Se você tiver um índice (com uma chave 4-byte, 6-byte ponteiro linha e alguma sobrecarga interna), a consulta terá de digitalizar apenas 10 Mb de dados além de dados adicionais a partir da tabela se o filtro bem-sucedido.

• A varredura da tabela é mais eficiente se a sua condição não é selectiva (você tem alta probablility para coincidir com a condição).
• A verificação de índice é mais eficiente se a sua condição é seletiva (você tem baixa probablility para coincidir com a condição).

Ambas as consultas exigirá verificação de todo o índice.

Mas por reescrever a consulta AND você pode se beneficiar do variando sobre o índice também.

Esta condição:

field & number = number

só pode coincidir com os campos se os bits mais altos do conjunto number são definidos no field também.

E você deve apenas fornecer essa condição extra para a consulta:

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

Isto irá usar o intervalo para filtragem grosseira e a condição para filtragem fina.

Os mais bits para number são desactivado no final, melhor.

Answer 2

Eu duvido que o otimizador iria entender isso ...

Talvez você possa chamar EXPLICAR nestas consultas e confirmar meu palpite pessimista. (Lembrando é claro que muito da consulta decisões do plano são baseados na instância específica de um determinado banco de dados, ou seja, quantidades variáveis ??de dados e / minério meramente dados com um perfil estatístico diferente pode produzir planos distintos).

Assumindo que a tabela tem uma quantidade significativa de linhas, e que os critérios "bitwised" permanecem suficientemente selectivo) de uma eventual optimização seja alcançado quando evitando uma operação de bit a bit em cada fileira, reescrevendo a consulta com uma construção IN (ou com um JOIN)

Algo assim (conceitual, ou seja, não testado)

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

Os benefícios de uma abordagem como essa necessidade de ser avaliada com diferentes casos de uso (todos com um número considerável de linhas na tabela, pois caso contrário o direto "ONDE campo | número = número" abordagem é bastante eficiente), mas eu suspeito que isso poderia ser significativamente mais rápido. Ganhos adicionais pode ser alcançado se os "tblFieldValues" não precisa ser recriado a cada vez. Criação eficiente desta tabela é claro implica um índice em campo na tabela original.

Answer 3

Eu tentei isso mesmo, e as operações bit a bit não são suficientes para evitar Mysql de usar um índice na coluna "campo". É provável, porém, que uma varredura completa do índice está ocorrendo.