(Bit per bit) Superset e sottoinsiemi in MySQL

Question

Sono le seguenti query efficace in 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 è stato creato un indice per il campo?

In caso contrario, c'è un modo per farlo funzionare più velocemente?

Answer 1

Aggiornamento:

Vedere questa voce nel mio blog per i dettagli delle prestazioni:

• operazioni bit per bit e gli indici

---

SELECT * FROM table WHERE field & number = number

SELECT * FROM table WHERE field | number = number

Questo indice può essere efficace in due modi:

1. Per evitare le scansioni di tabella primi anni (dal momento che il valore da confrontare è contenuto nell'indice stesso)
   • Per limitare l'intervallo di valori esaminati.

Né condizioni nelle query sopra è sargable , è l'indice non verrà utilizzato per la scansione gamma (con le condizioni come sono ora).

Tuttavia, il punto 1 detiene ancora, e l'indice può essere utile.

Se la tabella contiene, per esempio, 100 byte per riga in media, e le registrazioni 1,000,000, quindi la scansione tabella sarà necessario eseguire la scansione 100 Mb dei dati.

Se ha un indice (con una chiave 4 byte, 6 byte puntatore di riga e un overhead interno), la query dovrà scansione solo 10 Mb dei dati più dati aggiuntivi dalla tabella se il filtro ha successo.

• La scansione di tabella è più efficiente se la sua condizione non è selettiva (si soffre di probablility per abbinare la condizione).
• L'indice di scansione è più efficiente se la sua condizione è selettiva (si dispone di bassa probablility per abbinare la condizione).

Entrambe queste query richiederanno la scansione dell'intero indice.

Ma riscrivendo la query AND si può beneficiare dalla vanno sull'indice troppo.

Questa condizione:

field & number = number

può abbinare solo i campi se i più alti bit di set number vengono impostati nel field troppo.

E si dovrebbe solo fornire questa condizione in più per la query:

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

Questa utilizzerà il range per filtrazione grossolana e la condizione per il filtro fine.

I più bit per number sono disinserito alla fine, tanto meglio.

Answer 2

Dubito che l'ottimizzatore dovrebbe capire che uno ...

Forse è possibile chiamare contare su queste query e confermare la mia ipotesi pessimistica. (Ricordando naturalmente che gran parte delle decisioni piano di query si riferiscono al caso specifico di un determinato database, cioè quantità variabili di dati e / minerale soltanto dati con un profilo differente statistica può produrre piani distinti).

Supponendo che la tabella ha una notevole quantità di righe, e che i criteri "bitwised" rimane abbastanza selettiva) una possibile ottimizzazione si ottiene quando evitando un'operazione bit per bit su ogni singola riga, riscrivendo la query con un costrutto IN (o con un JOIN)

Qualcosa del genere (concettuale, vale a dire non testato)

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

I vantaggi di un approccio come questo bisogno di essere valutati con diversi casi d'uso (ognuno dei quali con un numero considerevole di righe nella tabella, poiché in caso contrario la diretta "DOVE campo | number = number" approccio è abbastanza efficace), ma ho il sospetto che questo potrebbe essere significativamente più veloce. Ulteriori guadagni possono essere raggiunti se i "tblFieldValues" non ha bisogno di essere ricreato ogni volta. Creazione efficiente di questa tabella, ovviamente implica un indice sul campo nella tabella originale.

Answer 3

Ho provato io stesso, e le operazioni bit per bit non sono sufficienti per evitare che MySQL da utilizzando un indice sulla colonna "campo". E 'probabile, però, che una scansione completa dell'indice è in corso.