(Bitwise) Surensembles et sous-ensembles dans MySQL

Question

Les requêtes suivantes sont-elles efficaces dans 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

...si un index pour le champ a été créé ?

Si non, existe-t-il un moyen de le faire fonctionner plus rapidement ?

Answer 1

Mise à jour:

Voir cette entrée dans mon blog pour les détails de la performance:

• les opérations et les index au niveau du bit

---

SELECT * FROM table WHERE field & number = number

SELECT * FROM table WHERE field | number = number

Cet indice peut être efficace de deux façons:

1. Pour éviter les analyses de table au début (puisque la valeur à comparer est contenue dans l'indice lui-même)
   • Pour limiter la plage de valeurs examinées.

Aucune de ces conditions dans les requêtes ci-dessus est sargable , c'est l'indice ne sera pas utilisé pour l'analyse de la plage (avec les conditions telles qu'elles sont maintenant).

Toutefois, le point 1 tient toujours, et l'indice peut être utile.

Si votre table contient, par exemple, 100 octets par ligne en moyenne, et les dossiers de 1,000,000, le balayage de la table devra analyser 100 Mb des données.

Si vous avez un index (avec une clé 4 octets, pointeur de ligne 6 octets et une surcharge interne), la requête devra analyser uniquement 10 Mb des données ainsi que des données supplémentaires de la table si le filtre réussit.

• L'analyse de la table est plus efficace si votre condition n'est pas sélective (vous avez une probablility pour correspondre à la condition).
• L'analyse d'index est plus efficace si votre condition est sélective (vous avez faible probablility pour correspondre à la condition).

Ces deux requêtes nécessitent le balayage complet de l'index.

Mais en réécrivant la requête AND vous pouvez bénéficier de l'allant de l'indice aussi.

Cette condition:

field & number = number

ne peut correspondre aux champs si les bits les plus élevés du jeu de number sont définies dans le field aussi.

Et vous devez simplement fournir cette condition supplémentaire à la requête:

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

utilisera la gamme pour le filtrage grossier et la condition de filtration fine.

Les autres bits pour number sont hors service à la fin, le mieux.

Answer 2

Je doute que l'optimiseur comprendrait celui-là...

Peut-être pouvez-vous appeler EXPLAIN sur ces requêtes et confirmer ma supposition pessimiste.(en gardant bien sûr à l'esprit qu'une grande partie des décisions relatives aux plans de requête sont basées sur l'instance spécifique d'une base de données donnée, c'est-à-diredes quantités variables de données et/ou simplement des données ayant un profil statistique différent peuvent produire des plans distincts).

En supposant que la table comporte un nombre important de lignes et que les critères "bit à bit" restent suffisamment sélectifs), une optimisation possible est obtenue en évitant une opération au niveau du bit sur chaque ligne, en réécrivant la requête avec une construction IN (ou avec un JOIN )

Quelque chose comme ça (conceptuel, c'est-à-direpas testé)

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

Tous les avantages d'une approche comme celle-ci doivent être évalués avec différents cas d'utilisation (tous avec un nombre important de lignes dans le tableau, car sinon l'approche directe "WHERE field | number = number" est suffisamment efficace), mais je soupçonne cela pourrait être beaucoup plus rapide.Des gains supplémentaires peuvent être obtenus si les "tblFieldValues" n'ont pas besoin d'être recréées à chaque fois.La création efficace de cette table implique bien entendu un index sur Field dans la table d'origine.

Answer 3

J'ai essayé moi-même, et les opérations ne sont pas assez au niveau du bit pour empêcher Mysql d'utiliser un index sur la colonne « champ ». Il est probable, cependant, qu'une analyse complète de l'indice est en cours.