Dans les bases de données SQL (j'utilise Python + Sqlite), comment s'assurer que, si nous avons 1 million de lignes, la requête

SELECT * FROM mytable WHERE myfunction(description) < 500 AND column2 < 1000
                           [-----------------------------]   [--------------]
                               high-CPU cost condition         easy-to-test 
                              requiring 100 µs per test         condition

Est optimisé pour que la 1ère condition (coûteuse CPU) ne soit testée que si la seconde condition facile à tester est déjà vraie? (puisque c'est un AND logique, est-ce un AND paresseux?)

Exemple:

  • si la 1ère condition est toujours testée, il faudrait 1 million x 100 µs = 100 secondes!

  • si la 2e condition est testée en premier, alors seulement 5000 éléments seraient pré-filtrés (dans mon cas d'utilisation), puis, appliquer la 1ère condition serait très rapide.

Remarque:

  • column2 n'est pas nécessaire un ID, cela pourrait être autre chose

  • dans mon cas d'utilisation, myfunction implique le calcul de la distance de Levenshtein

3
Basj 16 avril 2018 à 18:54

3 réponses

Inspiré par la réponse de @ GordThompson, voici une référence entre:

(1)  SELECT * FROM mytable WHERE col2 < 1000 AND myfunction(col1) < 500

Contre.

(2)  SELECT * FROM mytable WHERE myfunction(col1) < 500 AND col2 < 1000

Test (1) (condition facile à tester en premier): 1,02 seconde

import sqlite3, time, random

def myfunc(x):
    time.sleep(0.001) # wait 1 millisecond for each call of this function
    return x

# Create database
db = sqlite3.connect(':memory:')
db.create_function("myfunction", 1, myfunc)
c = db.cursor()
c.execute('CREATE TABLE mytable (col1 INTEGER, col2 INTEGER)');
for i in range(10*1000):
    a = random.randint(0,1000)
    c.execute('INSERT INTO mytable VALUES (?, ?)', (a, i));

# Do the evil query
t0 = time.time()
c.execute('SELECT * FROM mytable WHERE col2 < 1000 AND myfunction(col1) < 500')
for e in c.fetchall():
    print e
print "Elapsed time: %.2f" % (time.time() - t0)

Résultat: 1,02 seconde, cela signifie que myfunc a été appelé au maximum 1000 fois, c'est-à-dire pas pour toutes les 10 000 lignes .


Test (2) (condition lente à calculer en premier): 10,05 secondes

Idem avec:

c.execute('SELECT * FROM mytable WHERE myfunction(col1) < 500 AND col2 < 1000')

Au lieu.

Résultat: 10,05 secondes, cela signifie que myfunc a été appelé ~ 10 000 fois, c'est-à-dire pour toutes les 10 000 lignes , même celles pour lesquelles la condition col2 < 1000 n'est pas vraie.


Conclusion globale: Sqlite fait une évaluation paresseuse pour AND, c'est-à-dire que la condition facile doit être écrite en premier comme ceci:

... WHERE <easy_condition> AND <expensive_condition>
0
Basj 17 avril 2018 à 19:18

Vous pouvez forcer l'ordre d'exécution en utilisant une expression case. En général, les optimiseurs SQL peuvent réorganiser les opérations, la seule exception étant case.

SELECT *
FROM mytable
WHERE (CASE WHEN column2 >= 1000  OR column2 IS NULL THEN 0
            WHEN myfunction(description) < 500 THEN 1
       END) = 1;

En règle générale, les expressions case sont déconseillées dans les clauses WHERE. . . l'une des principales raisons est qu'elles entravent l'optimisation. Dans ce cas, c'est une bonne chose.

3
Basj 17 avril 2018 à 09:37

SQLite réorganisera avec plaisir les expressions connectées ET chaque fois qu'il en aura envie. Ainsi, lors de la réécriture de la requête pour vérifier que column2 semble fonctionner pour la première fois, il n'y a aucune garantie.

L'optimiseur de requêtes suppose que la vitesse est principalement déterminée par les E / S disque, il estime donc que le coût des deux conditions est le même. Les estimations de coûts sont influencées par les index et par les ANALYZE statistiques (qui ne fonctionnent que pour les données indexées). Donc, la façon la plus simple d'accélérer cette requête (et probablement la plupart des autres requêtes que vous utiliserez) est de créer un index sur column2:

CREATE INDEX my_little_index ON mytable(column2);

Si vous ne souhaitez pas utiliser un index pour une raison quelconque, vous devez utiliser une construction que l'optimiseur de requête ne peut pas optimiser loin. Une expression CASE comme indiqué dans la réponse de Gordon fonctionnerait très bien. Dans le cas général, déplacez la première condition dans une sous-requête et empêchez l'aplatissement de la sous-requête en interrompant l'une des règles énumérées; l'ajout d'une clause LIMIT factice aux deux requêtes est généralement plus simple:

SELECT *
FROM (SELECT *
      FROM mytable
      WHERE column2 < 1000
      LIMIT -1)
WHERE myfunction(description) < 500
LIMIT -1;
2
CL. 17 avril 2018 à 08:47