(RDB) 13 façons de comprendre les jointures

 (justinjaffray.com)
4 points par GN⁺ 2023-07-04 | 1 commentaires | Partager sur WhatsApp
  • Dans les bases de données relationnelles, un inner join dépasse la simple syntaxe SQL : une même structure peut s’interpréter différemment comme recherche, boucle imbriquée, modèle logique, vérification de types ou point de vue algébrique
  • Dans des tables normalisées, la jointure devient l’outil le plus pratique pour suivre les références et recombiner des informations stockées sans duplication
  • Du point de vue de l’implémentation, on peut la voir comme un parcours des paires de lignes qui ne conserve que les combinaisons satisfaisant une condition, ou comme la sélection, dans les domaines de colonnes, des seules combinaisons de valeurs présentes dans les deux relations
  • Dans les modèles de programmation, on peut expliquer la jointure avec flatMap, le SQL LATERAL, la résolution du problème N+1 des ORM, la vérification de types fondée sur les traits en Rust, ou le andThen de la monade Set
  • Mathématiquement, les chemins dans un graphe, le modèle minimal, la plus grande relation admissible, la borne supérieure minimale d’un ordre partiel et le produit d’anneau d’expressions relationnelles révèlent tous les mêmes propriétés de la jointure

Dans des données normalisées, une jointure devient une recherche

  • Très concrètement, on peut voir une jointure comme le fait de rechercher une valeur, ou d’ajouter à des données existantes des informations redondantes
  • L’exemple part d’une table qui stocke user, country et country_code ensemble
    • Pour une même valeur de country, country_code est répété, ce qui crée de la duplication
    • Si les données changent souvent, il faut mettre à jour toutes les occurrences en même temps, ce qui accroît les erreurs et l’inefficacité
  • Sous forme normalisée, la relation entre country et country_code est séparée dans une table dédiée, et la table des utilisateurs ne référence que country_id
  • En faisant un INNER JOIN entre users et countries sur country_id, on peut retrouver la forme initiale user, country, country_code
  • La suite suppose que les jointures se font implicitement sur les colonnes de même nom, sans s’attacher strictement aux détails de la syntaxe SQL

Point de vue de l’implémentation : joindre en parcourant lignes et colonnes

  • Étant donnés deux ensembles R, S et un prédicat p, une jointure parcourt tous les r ∈ R et s ∈ S, puis n’émet que les cas où p(r, s) est vrai
    • Si le produit cartésien de deux collections correspond à toutes les connexions de lignes possibles, la jointure en est le sous-ensemble qui satisfait la condition
  • Du point de vue des colonnes, on considère le domaine de chaque colonne comme l’ensemble de ses valeurs possibles, puis on parcourt les combinaisons de valeurs de colonnes
    • Si l’on a R(a, b) et S(b, c), on parcourt les domaines de a, b et c
    • On n’émet [a, b, c] que lorsque (a, b) est dans R et (b, c) est dans S

La jointure comme réalités alternatives compatibles

  • L’exemple de John et Sally explique la jointure comme une opération qui ne conserve que les réalités compatibles, dans une situation où chacun ne dispose que d’une partie des informations
  • John connaît les combinaisons possibles entre son animal de compagnie et un animal errant, et Sally connaît aussi les combinaisons possibles entre son animal de compagnie et un animal errant
    • Le cas où John a un chien et l’animal errant est un chien ne peut pas être vrai en même temps que le cas où Sally a un chat et l’animal errant est une souris
    • C’est parce que les deux personnes doivent observer le même animal errant
  • En joignant les deux tables sur stray, on ne conserve, parmi les combinaisons animal de John·animal errant·animal de Sally, que celles qui ne se contredisent pas

Les jointures dans les modèles de programmation

  • flatMap est une fonction qui crée un nouveau tableau pour chaque élément du tableau d’origine, puis concatène les résultats ; elle peut servir à implémenter une jointure
    • SELECT * FROM r INNER JOIN s ON p s’exprime par r.flatMap(x => s.filter(y => p(x, y)))
    • La syntaxe LATERAL de certaines variantes de SQL transforme la jointure en une forme de flatMap
  • Si la partie droite de LATERAL ne référence pas de colonne de gauche, elle est équivalente à un produit cartésien
    • La décorrélation de requêtes repose sur la suppression des références aux colonnes de droite au moyen de réécritures successives
  • Le problème N+1, fréquent avec les ORM, peut aussi s’expliquer par les jointures
    • Si l’on exécute une requête supplémentaire pour chaque ligne du résultat, les bases de données qui utilisent des connexions, comme Postgres, imposent un coût fixe élevé pour chaque requête individuelle
    • Demander à la base de données « d’effectuer toutes ces recherches » produit une jointure comme users INNER JOIN countries
    • Avec une base de données in-process comme Sqlite, ce problème est moins marqué

Chemins de graphe et modèle logique

  • Comme une relation « met en relation » deux ensembles, on peut la représenter comme un graphe
    • La table users relie l’ensemble des noms d’utilisateurs à l’ensemble des country_id
    • La relation qui relie country_id aux codes pays à deux lettres peut aussi être représentée comme un graphe séparé
  • Si l’ensemble de sommets de droite du premier graphe est le même que l’ensemble de sommets de gauche du second, on peut les fusionner
  • Énumérer tous les chemins qui partent de l’ensemble de gauche, passent par un sommet central et arrivent à l’ensemble de droite donne la jointure des deux relations
  • En logique formelle, on voit les relations comme des prédicats, et l’ensemble des faits qui rend vrai un ensemble d’énoncés comme un modèle
    • Si users(A, B) et countries(B, C, D) sont vrais, on pose l’implication selon laquelle Q(A, B, C, D) est vrai
    • Plusieurs modèles peuvent satisfaire cette condition
    • Pour obtenir le résultat standard, on choisit, parmi les modèles qui satisfont la condition, le plus petit modèle
    • Ce plus petit modèle est identique au résultat de la jointure entre users et country

La jointure vue comme vérification de types

  • Les systèmes de types de style ML ressemblent fortement à Prolog et Datalog, si bien qu’on peut les exprimer d’une façon proche des jointures
  • Dans l’exemple en Rust, les relations sont définies comme des traits
    • Users et CountryCode jouent le rôle de relations
    • Smudge, Sissel, Petee, Canada, UnitedStates, CA, US sont définis comme des types concrets
  • Les implémentations de traits comme (Smudge, Canada): Users et (Canada, CA): CountryCode correspondent aux lignes de la relation
  • Pour que (A, B, C) appartienne à la jointure, il faut que (A, B): Users et (B, C): CountryCode
  • test::<(Smudge, _, CA)>() réussit la vérification de types, tandis que test::<(Smudge, _, US)>() échoue parce que (Canada, US): CountryCode n’est pas implémenté

La jointure comme opération de la monade Set

  • L’exemple JavaScript avec Some et None commence par une façon de fusionner des records optionnels
    • Si deux records ont le même country, ils sont fusionnés et Some est renvoyé
    • S’ils ne sont pas compatibles, ou s’il n’y a pas de valeur, None est renvoyé
  • andThen extrait le contenu d’une valeur optionnelle et applique la fonction de fusion
  • En conservant la même fonction combine mais en remplaçant le conteneur par Rel, on peut traiter des ensembles de relations
    • Rel.map applique une fonction à toutes les lignes
    • Rel.andThen concatène avec flatMap les relations produites par chaque ligne
  • En exécutant le même combine sur la relation users et la relation countries, on obtient comme résultat de jointure Smudge, Sissel et Petee avec leurs codes pays ajoutés

Plus grande relation admissible et join d’un ordre partiel

  • Une troisième relation T qui possède toutes les colonnes de deux relations R et S est dite admissible si elle n’invente pas de nouvelles informations
    • Lorsqu’on restreint une ligne de T aux colonnes de R, cette ligne doit exister dans R
    • De la même manière, lorsqu’on la restreint aux colonnes de S, cette ligne doit aussi exister dans S
  • Par exemple, Smudge, Canada, US n’est pas admissible
    • Si l’on ne garde que country et country_code, on obtient Canada, US, qui n’est pas une ligne de S
  • La relation vide est elle aussi admissible, mais la plus grande relation admissible contient Smudge-Canada-CA, Sissel-Canada-CA et Petee-United States-US
  • Cette plus grande relation admissible est la jointure des deux relations
  • Du point de vue d’un ordre partiel, on définit R ≤ Q comme suit
    • Q contient toutes les colonnes de R
    • Lorsque chaque ligne de Q est restreinte aux colonnes de R, elle devient une ligne de R
  • Dans cet ordre partiel, la borne supérieure minimale R ∨ S des deux relations R, S existe, et c’est le join au même sens que la jointure relationnelle

La jointure comme produit d’anneau

  • On peut aussi représenter les relations algébriquement
    • Une ligne est représentée comme un produit de paires colonne-valeur
    • Une relation est représentée comme une somme de plusieurs lignes
  • Par exemple, le terme obtenu en multipliant user = Smudge et country_id = 1 devient une ligne
  • Des règles sont ajoutées pour simplifier les expressions
    • Idempotence : [x = y][x = y] = [x = y]
    • Contradiction : [x = y][x = z] = 0 if y ≠ z
  • En multipliant la relation utilisateurs R et la relation de lookup des pays S, puis en développant avec les lois de distributivité et de commutativité, les termes contradictoires disparaissent et seuls les termes compatibles restent
  • L’expression restante est Smudge-1-Canada-CA, Sissel-1-Canada-CA, Petee-2-United States-US, ce qui correspond exactement à la jointure des deux relations
  • Cette approche peut aussi être vue comme une tensor contraction

À lire aussi

1 commentaires

 
GN⁺ 2023-07-04
Avis sur Hacker News

  • J’ai commencé à trouver les jointures beaucoup plus faciles à comprendre en les pensant en dimensions spatiales
    Si on met chaque dimension dans une table séparée, comme Dim_X, Dim_Y, Dim_Z, et qu’on les relie avec le même EntityId, on peut voir ça comme la construction de la position en 3D d’une entité
    Pour créer 3 dimensions, il faut au moins 2 jointures internes, et on peut étendre le même principe à des dimensions non spatiales comme le temps
    Si on ne limite pas un instant précis, on obtient alors un rapport contenant toutes les positions qu’une entité a occupées au fil du temps
    Les autres types de jointures deviennent aussi plus faciles à comprendre avec cette variante une fois qu’on a bien intégré le concept, au point de pouvoir “faire pivoter” le schéma mentalement

    • Ça me fait penser à HyperDex. Il utilise un hachage des valeurs dans un hyperespace multidimensionnel basé sur les attributs pour l’indexation
      https://dbdb.io/db/hyperdex
    • Ça semble plus proche d’une hypernormalisation des données. En général, en BCNF, on ferait plutôt une table comme EntityPosition(EntityId, X, Y, Z)
      Cela dit, l’idée d’assembler des fragments de plusieurs dimensions et de gérer des agrégations fait penser au data warehouse
    • Je me suis toujours demandé pourquoi on utilisait une syntaxe comme JOIN ou INNER JOIN. Lister les tables dans FROM et écrire les conditions de jointure dans la clause WHERE comme des équations me paraît bien plus clair
      Quand plusieurs JOIN sont mélangés dans une clause FROM complexe, c’est difficile à lire, et lire des conditions d’égalité dans WHERE semble plus intuitif
    • Je me demande s’il faut comprendre que toutes les jointures sont en fait des variantes de la jointure cartésienne

  • Le point de vue numéro 0, c’est que la jointure est un opérateur de l’algèbre relationnelle
    https://en.m.wikipedia.org/wiki/Relational_algebra
    La jointure naturelle R ⋈ S est l’ensemble des combinaisons de tuples dont les noms d’attributs communs sont identiques, et c’est une opération relationnelle correspondant au AND logique
    ⋈ peut être vu comme un produit cartésien filtré par un prédicat pour éliminer les lignes qui ne doivent pas apparaître dans le résultat, et une grande partie de SQL se comprend bien sous cet angle

    • Dans l’interprétation fonctionnelle de la théorie relationnelle, la jointure est une composition de fonctions, et je suis surpris que ce point de vue soit absent
    • L’explication en termes de “boucles imbriquées sur les lignes” contient déjà ce point de vue de produit cartésien + prédicat

  • Depuis quelques jours, je cherche des ressources sur l’implémentation de l’exécution/de la planification de requêtes, mais je trouve peu de contenu côté implémentation sur les prédicats, les index existants ou les jointures
    Les résultats Google sont pollués par du contenu expliquant simplement comment utiliser ces fonctionnalités
    Jusqu’ici, je n’ai trouvé que les ressources du CMU Database Group, et elles sont excellentes

    • Il existe un livre gratuit de 700 pages sur le sujet : “Building Query Compilers”
      https://pi3.informatik.uni-mannheim.de/~moer/querycompiler.p...
      Le cours de TUM “Database Systems on Modern CPU Architectures” peut aussi être utile, et les supports de 2020 incluent l’ensemble des vidéos du cours
      https://db.in.tum.de/teaching/ss20/moderndbs/?lang=en
    • Je ne sais pas si ça correspondra au niveau de profondeur recherché, mais les documents de SQLite sur la vue d’ensemble de l’optimisation et le query planner valent le détour
      https://www.sqlite.org/optoverview.html
      https://www.sqlite.org/queryplanner.html
    • Dans ce genre de cas, on recommande souvent de lire la documentation de Postgres et son code source. Le code est d’ailleurs assez lisible
      https://www.postgresql.org/docs/current/planner-optimizer.ht...
    • C’est un sujet assez spécialisé, donc il est difficile de trouver un bon manuel, et tout dépend de la profondeur voulue et de la partie qui vous intéresse
      L’exécution des requêtes et leur planification sont en pratique presque deux sujets distincts
      Côté articles sur l’optimisation des jointures, je pense que l’article fondateur de Selinger reste le meilleur
      https://courses.cs.duke.edu/compsci516/cps216/spring03/paper...
      Il ne prend pas en charge les jointures externes et des techniques plus efficaces ont été proposées depuis, mais pour quelqu’un qui regarde des optimiseurs de la famille System R, il reste très familier
      Le fichier src/backend/optimizer/README de Postgres contient aussi beaucoup d’éléments qu’on voit rarement ailleurs
      Les cours d’Andy Pavlo à la CMU sont pratiquement les seules ressources en ligne qui expliquent ce sujet, et le PDF “Building Query Compilers”, bien qu’incomplet, rassemble les articles clés de Moerkotte et d’autres, ce qui en fait une lecture utile pour une implémentation moderne
      Trouver les index applicables n’est généralement pas difficile : il suffit de voir s’il existe un sargable predicate, mais l’estimation de sélectivité est difficile, et l’estimation de sélectivité à travers des jointures est presque le problème le plus difficile pour un optimiseur
      Par exemple, si on a A=x AND B=y AND C=z et uniquement des informations de sélectivité/cardinalité pour les index (A,B) et (B,C), estimer la sélectivité de l’ensemble des trois conditions n’a rien de trivial
      Il existe même des articles qui demandent un solveur de “programmation conique du second ordre” pour traiter ce problème
    • En préfixant la recherche query planning par relational algebra, j’ai l’impression, même à vue d’œil, d’obtenir davantage de résultats orientés implémentation

  • La 14e méthode est la jointure multiple, aussi appelée « worst-case optimal join », même si le nom n’est pas terrible
    Au lieu de joindre les tables deux par deux en produisant sans cesse des résultats intermédiaires, cela consiste à joindre ensemble 3 tables ou plus sans résultat intermédiaire
    Un billet de blog connexe et une courte vidéo sont disponibles sur https://relational.ai/blog/dovetail-join, et l’article original est ici : https://dl.acm.org/doi/pdf/10.1145/3180143
    Je travaille chez RelationalAI, et nous faisons partie, avec quelques autres jeunes entreprises du secteur des bases de données, de ceux qui amènent sur le marché ce nouvel algorithme de jointure étudié dans le monde académique depuis une dizaine d’années

    • Le billet de Justin qui présente les WCOJ est aussi plutôt bon
      https://justinjaffray.com/a-gentle-ish-introduction-to-worst...
    • Si on nie l’entrée, c’est-à-dire qu’on la transforme en complément d’ensemble, le AND de la jointure devient un NOR, et Tetris exploite ce point
      La borne du pire cas ne devient pas plus serrée que pour les WCOJ sans état / en streaming, mais les données réelles ont souvent des certificats de boîte bien plus petits
      Je n’ai pas vu si la jointure Dovetail prend en charge les requêtes récursives, c’est-à-dire du datalog arbitraire où seule la relation de sortie est spécifiée et où le moteur gère lui-même les relations intermédiaires
      Je serais curieux de savoir si ce type de requête est pris en charge

  • Il faudrait plus d’articles de ce genre, qui montrent surtout les subtilités du modèle relationnel aux développeurs au niveau applicatif
    L’explication et l’exploration sous l’angle de la programmation fonctionnelle sont elles aussi concises et convaincantes

  • On dirait qu’ils ont encore raté une occasion d’enseigner le problème N+1
    Faire une jointure sur un index non clusterisé reste du N+1, simplement du N+1 sur disque plutôt que du N+1 entre le réseau et le disque

    • On dirait un peu : « il aurait fallu traiter le problème X qui m’intéresse, et tant pis si l’article devenait plus long »

  • Une jointure interne est un produit cartésien assorti d’une condition

    • Il y a une grande différence de performance entre produire un produit cartésien puis filtrer avec une condition, et générer directement la condition
      Une jointure interne avec une condition d’égalité génère directement la condition, tandis qu’une condition de jointure non fondée sur l’égalité nécessite une véritable évaluation

  • Bonne explication. Dire que « la bonne méthode consiste à normaliser les tables » est vrai pour les bases de données transactionnelles, mais dans les entrepôts de données, un certain degré de dénormalisation est largement accepté

  • Cet exemple de normalisation m’a rappelé l’époque où je concevais des tables en pensant que les clés primaires numériques étaient plus rapides que les chaînes
    On se retrouvait alors avec des id dénués de sens, et il fallait faire des jointures pour obtenir la vraie valeur unique recherchée
    Un jour, j’ai compris qu’utiliser la même clé unique dans deux tables pouvait réduire le nombre de jointures, et c’était simple mais efficace

    • Malgré tout, j’aime bien avoir un champ id unique par table. C’est utile pour les logs et cela évite d’avoir à se soucier de la « vraie » clé composée de plusieurs champs
      En revanche, je mets un index unique sur les valeurs de chaîne et, plus important encore, j’y attache les contraintes d’intégrité
      Une table remplie de chaînes porteuses de sens est bien plus lisible qu’une table remplie d’id numériques ou d’UUID