Introduction au problème d’ordre de jointure

Une base de données typique peut exécuter une requête SQL de plusieurs manières, en fonction de l’ordre et des algorithmes des opérateurs sélectionnés. Une décision cruciale est l’ordre dans lequel l’optimiseur doit joindre les relations. La différence entre l’ordre de jointure optimal et non optimal peut être des ordres de grandeur. Par conséquent, l’optimiseur doit choisir l’ordre approprié des jointures pour garantir de bonnes performances globales. Dans cet article de blog, nous définissons le problème d’ordre des jointures et estimons la complexité de la planification des jointures.

Exemple

Considérez le schéma TPC-H. Les customer puis-je avoir orders. Chaque ordre peut avoir plusieurs positions définies dans le lineitem table. Les customer table a 150 000 enregistrements, le orders table a 1 500 000 enregistrements, et la lineitem table a 6 000 000 d’enregistrements. Intuitivement, chaque client passe environ 10 commandes, et chaque commande contient en moyenne quatre positions.

Supposons que nous voulions récupérer tous lineitem des postes pour tous orders placé par le donné customer:

SELECT 
  lineitem.*
FROM 
  customer,
  orders,
  lineitem
WHERE
  c_custkey = ? 
  AND c_custkey = o_custkey
  AND o_orderkey = l_orderkey

Supposons que nous ayons un modèle de coût où le coût d’un opérateur est proportionnel au nombre de tuples traités.

Nous considérons deux ordres de jointure différents. Nous pouvons rejoindre customer avec orders et puis avec lineitem. Cet ordre de jointure est très efficace car la plupart des clients sont filtrés tôt et nous avons une petite relation intermédiaire.

Alternativement, nous pouvons rejoindre orders avec lineitem et puis avec customer. Il produit une grande relation intermédiaire parce que nous mappons chaque lineitem à un order seulement pour rejeter la plupart des tuples produits dans la deuxième jointure.

Les deux ordres de jointure produisent des plans avec des coûts très différents. La première stratégie de jointure est très supérieure à la seconde.

Espace de recherche

Un optimiseur parfait devrait construire tous les plans équivalents possibles pour une requête donnée et choisir le meilleur plan. Voyons maintenant combien d’options l’optimiseur devrait prendre en compte.

Nous modélisons une jointure à n voies comme une séquence de n-1 des jointures bidirectionnelles qui forment un arbre binaire complet. Les nœuds feuilles sont des relations d’origine et les nœuds internes sont des relations de jointure. Pour trois relations, il existe 12 ordres de jointure valides :

Nous comptons le nombre d’ordres de jointure possibles pour N relations en deux étapes. Tout d’abord, nous comptons le nombre d’ordres différents de nœuds feuilles. Pour la première feuille, nous choisissons l’un des N rapports; pour la deuxième feuille, nous choisissons l’un des restants N-1 relations, etc. Cela nous donne N! différentes commandes.

Deuxièmement, nous devons calculer le nombre de toutes les formes possibles d’un arbre binaire complet avec N feuilles, qui est le nombre de façons d’associer N-1 applications d’un opérateur binaire. Ce nombre est connu pour être égal au nombre catalan C(N-1). Intuitivement, pour l’ordre fixe donné de N nœuds feuilles, nous devons trouver le nombre de façons de définir N-1 paires de parenthèses ouvertes et fermées. Par exemple, pour les quatre relations [a,b,c,d], nous avons cinq parenthèses différentes :

En multipliant les deux parties, on obtient l’équation finale :

Performance

Le nombre d’ordres de jointure augmente de façon exponentielle. Par exemple, pour trois tables, le nombre de tous les plans de jointure possibles est 12; pour cinq tables, c’est 1,680; pour dix tables, c’est 17,643,225,600. Les optimiseurs pratiques utilisent différentes techniques pour garantir des performances suffisantes de l’énumération de jointure.

Premièrement, les optimiseurs peuvent utiliser la mise en cache pour minimiser la consommation de mémoire. Deux techniques largement utilisées sont la programmation dynamique et la mémorisation.

Deuxièmement, les optimiseurs peuvent utiliser diverses heuristiques pour limiter l’espace de recherche au lieu d’effectuer une recherche exhaustive. Une heuristique courante consiste à élaguer les ordres de jointure qui génèrent des produits croisés. Bien qu’assez bonne dans le cas général, cette heuristique peut conduire à des plans non optimaux, par exemple pour certaines jointures en étoile. Une approche d’élagage plus agressive consiste à n’énumérer que les arbres profonds à gauche ou à droite. Cela réduit considérablement la complexité de la planification mais dégrade encore plus la qualité du plan. Des algorithmes probabilistes peuvent être utilisés (par exemple, des algorithmes génétiques ou un recuit simulé), également sans aucune garantie sur l’optimalité du plan.

Sommaire

Dans cet article, nous avons jeté un coup d’œil au problème de l’ordre des jointures et avons eu une vue d’ensemble de sa complexité. Dans d’autres articles, nous explorerons la complexité de la planification des ordres de jointure pour différentes topologies de graphes, nous plongerons dans les détails des techniques d’énumération concrètes et analyserons les stratégies existantes et potentielles de planification des jointures dans Apache Calcite. Restez à l’écoute!