Partie 17: Logical Plan
Les articles de la série
- Partie 1 : Construire le REPL
- Partie 2 : Sérialisation des données
- Partie 3 : Database
- Partie 4 : Tables
- Partie 5 : Parser les commandes, création de la boîte à outils
- Partie 6 : Parser les commandes SQL
- Partie 7 : Tuples de données
- Partie 8 : Contraindre les données via un schéma
- Partie 9 : Découper le stockage des tables en pages
- Partie 10 : Clefs primaires
- Partie 11 : Expressions Logiques SQL
- Partie 12 : Scans et filtrage
- Partie 13 : UTF-8 et caractères échappés
- Partie 14 : Attributs nullifiables
- Partie 15 : Index secondaires
- Partie 16 : Directive EXPLAIN
Bonjour à toutes et tous 😃
Lors de la partie précédente, on définit une directive EXPLAIN et propagé un flag dans le reste de l'application.
Mais une question vous brûle les lèvres :
Pourquoi ???
Rendre le QueryEngine "intelligent" et verbeux
Et bien, nous allons complexifier de plus en plus la brique QueryEngine au fil des articles qui vont arriver, mais pour éviter de se retrouver devant une "boîte noire" totalement incompréhensible, nous avons besoin de savoir les choix que le query engine réalise.
Quels sont-ils ?
Réponse courte : comment récupérer efficacement de la donnée dans la base de données.
Réponse plus élaborée.
Nous avons deux choix pour récupérer de la donnée :
- scanner la base de données en parcourant les pages
- utiliser un index qui donne un accès direct à la donnée.
Des index nous en avons de deux types:
- Par clef primaire : il existe toujours et pour toutes les entrées de notre base, il n'en n'existe qu'un par table
- Par index secondaires : peuvent exister ou pas et peuvent être plus d'un par table
Les index secondaires sont eux même décomposé en deux catégories:
- index unique : chaque clef d'index pointe sur un record en base
- index non-unique : chaque clef d'index pointe vers une liste de record en base
Notre EXPLAIN
va avoir deux effets :
- Empêcher l'exécution des scans et appels aux index
- Afficher quel a été la méthode d'accès à la donnée
Prenons une table telle que celle-ci
(
id INTEGER PRIMARY KEY,
nom TEXT(50),
prénom Text(50),
genre TEXT(2),
ville Text(100)
);
INTEGER PRIMARY KEY, nom TEXT(50),prénom Text(50), genre TEXT(2), ville Text(100) );
(id
Muni des index suivants :
(nom, prénom);
(ville);
On fournit le set de données suivant :
INSERT INTO Client (id, nom, prénom, genre, ville) VALUES (1, 'Smith', 'John', 'M', 'Paris');
INSERT INTO Client (id, nom, prénom, genre, ville) VALUES (2, 'Martin', 'Marie', 'F', 'New York');
INSERT INTO Client (id, nom, prénom, genre, ville) VALUES (3, 'Haddad', 'Karim (كريم)', 'M', 'Tokyo');
INSERT INTO Client (id, nom, prénom, genre, ville) VALUES (4, 'Dubois', 'Sophie', 'F', 'Beyrouth');
INSERT INTO Client (id, nom, prénom, genre, ville) VALUES (5, 'Tanaka', 'Hiroshi (ひろし)', 'M', 'Beyrouth');
INSERT INTO Client (id, nom, prénom, genre, ville) VALUES (6, 'Yamamoto', 'Sakura (さくら)', 'F', 'Paris');
INSERT INTO Client (id, nom, prénom, genre, ville) VALUES (7, 'Smith', 'Emily', 'F', 'Osaka');
INSERT INTO Client (id, nom, prénom, genre, ville) VALUES (8, 'Martin', 'Jean', 'M', 'Lyon');
INSERT INTO Client (id, nom, prénom, genre, ville) VALUES (9, 'Haddad', 'Layla (ليلى)', 'F', 'New York');
INSERT INTO Client (id, nom, prénom, genre, ville) VALUES (10, 'Dubois', 'Paul', 'M', 'Tokyo');
Si nous demandons toutes les entrées, aucune intelligence ne va être développée, nous réalisons un Full Scan et c'est tout.
SELECT * FROM Client;
Cet état va être détecté, car il n'y a pas de clause_where à la suite de la sélection de table, le Query Engine viendra opérer l'opération la plus coûteuse : lire chaque entrée de la table "Client", désérialiser les données.
Par contre, si on demande toutes les femmes du registre, cette fois-ci, il y a une expression qui sert de clause_where, donc potentiellement de l'intelligence à avoir sur la récupération des entrées correspondantes.
Chaque table possède une collection d'index sur divers tuples de champs, le sport intellectuel du Query Engine va être de détecter si oui ou non l'expression de la requête peut coller avec un index.
Si la requête est :
SELECT * FROM Client WHERE genre = 'F';
Le query engine va demander à la table "Client"
C'est quoi tes index ?
Et la table va lui répondre:
primary => (id,)
idx_identité => (nom, prénom)
idx_ville => (ville,)
Le Query Engine va alors déconstruire l'expression genre = 'F'
en (genre,)
.
Il va ensuite boucler sur les index à la recherche d'une correspondance.
Ici aucune correspondance ne peut être trouvé, on fallback sur du FullScan que l'on filtrera par la suite.
Par contre si la requête est:
SELECT * FROM Client WHERE ville = 'Paris';
De la même manière, le QueryEngine déconstruit l'expression ville = 'Paris'
en (ville,)
.
Cette fois-ci, il existe une correspondance d'index : idx_ville => (ville,)
.
Le QueryEngine va alors utiliser l'index idx_ville
pour récupérer la donnée.
Index non-unique qui se présente ainsi:
('Paris',) => [0, 5],
('New York',) => [1, 8],
('Tokyo',) => [2, 9],
('Beyrouth',) => [3, 4],
('Osaka',) => [6]
('Lyon',) => [7]
Des tuples associé à des liste de row_id.
Lorsque l'on demande "les personnes qui habitent Paris", ce que l'on fait, c'est demander la liste des row_id des entrées qui correspondent à cette ville.
Une fois que l'on a récupéré cette liste, on par row_id, rechercher les tuples de données correspondantes.
Cette fois-ci le mode d'accès a été réalisé au travers de l'index secondaire idx_ville
. On obtient alors la liste de row_id suivante [0, 5]
.
Passer par les index n'est pas toujours le plus efficace, si votre table est petite, il est parfois préférable de full scan que d'abord de récupérer les row_id puis les tuples.
Tout cela dépend des statistiques de la table, mais nous, nous n'avons pas bâti ces statistiques, et donc n'avons pas de moyens de deviner la bonne marche à suivre.
Si l'expression est plus conséquente comme dans:
SELECT * FROM Client WHERE nom = 'Dubois' AND prénom = 'Sophie';
Alors la déconstruction doit prendre garde à la construction logique de l'expression.
Il faut analyser l'entièreté de l'expression et ses relation logiques. Si l'index est composite comme par exemple (nom, prénom)
alors ça doit se matérialiser au niveau de l'expression par une intersection représenté par l'opérateur logique "AND".
On recherche donc une expression qui possède à la nom = '...'
ET prénom = '...'
.
Les champs d'index peuvent très bien être séparés dans l'expression par une autre expression qui n'a pas de rapport avec l'index actuel.
SELECT * FROM Client WHERE nom = 'Dubois' AND id > 10 AND prénom = 'Sophie';
Ici le
id
n'a pas de rôle à jouer dans la définition de la compatibilité d'index.
Trouver l'index composite s'il existe va donc nécessiter deux étapes:
- Décomposer l'expression
- Rechercher un groupe logique qui correspond à la définition de l'index
Et cela, il faut le réaliser pour tous les index.
Implémentation
Maintenant que l'on a tout bien défini et expliqué, nous allons pouvoir nous attaquer à la partie intéressante de l'implémentation de tout cela.
Plan
La première chose que nous allons déclarer est appelée le Plan, c'est toutes les étapes que le QueryEngine pense réaliser si on lui demande de rechercher dans la base de données en utilisant telle ou telle Expression.
Cette structure est un wrapper autours d'un Vec<PlanStep>
.
Le PlanStep
est lui-même une énumération.
Comme nous l'avons vu précédemment, il existe une grande variété de façons de lire de la donnée dans la base de données, ces manières sont matérialisées par l'énumération.
Ces variantes ont elle-même des structures comme valeur, car nous viendrons y accrocher des comportements dans de prochains articles.
/// Represents a scan operation that retrieves rows by their primary key values.
///
/// # Fields
/// - `primary_key`: The primary key columns used for the scan.
/// - `values`: The set of primary key values used to fetch the matching rows.
/// Represents a scan operation using a secondary index.
///
/// # Fields
/// - `index`: The columns that are part of the index.
/// - `name`: The name of the index being used.
/// - `values`: The values used to search the index.
/// - `uniqueness`: Indicates if the index enforces uniqueness (`Unique` or `NonUnique`).
Détermination de la méthode de scan
Pour cela, nous allons devoir faire le même chemin mental que lors de la première partie de cet article.
La question que l'on se pose est : est-ce que l'expression associée à la sélection correspond à la définition d'un index ou pas?
Le boulot de la méthode expression_from_index_definition_to_tuple
est de réaliser la première étape qui consiste à transformer par rapport à une expression, une potentielle définition d'index.
Si cette définition d'index est compatible alors il est possible de construire sur cette expression une clef d'index.
/// From index column names and an [Expression]
/// creates a tuple only if the expression is
/// compatible to the index definition
Cette méthode est naïve et comporte des bugs connus, mais est une base suffisante pour débuter.
Pour l'aider dans sa tâche, elle peut compter sur
Qui va récursivement décomposer notre Expression afin de déterminer si une expression logique existe et si oui la décomposer en map de colonne_name <=> colonne.
Comme une table peut avoir autant d'index secondaire que l'on veut et que ceux-ci peuvent avoir la définition qu'ils désirent. Il faut que l'IndexRegistry associé à la table soit en mesure de déterminer si l'expression actuelle est compatible avec un de ses index ou non.
Pour cela, celui-ci va boucler sur ses index à la recherche du premier qui possède les critères adéquats
Comme il existe deux types d'index, on se créé une fonction qui va rechercher dans les deux groupes d'index.
On s'assure de taper les index uniques en premier, car ce sont ceux qui renvoient le moins de résultats, 1 seul pour être plus précis.
Une fois cela fait on peut alors se construire une méthode qui va être en musure de trouver la méthode de lecture de la DB la plus efficace, compte tenu de l'expression.
/// Determines the most efficient scan method for a query based on the provided table
/// and expression. It evaluates whether the query can utilize primary keys or indexes
/// for optimized access to the table.
///
/// # Arguments
///
/// * `table` - A reference to the `Table` for which the scan method needs to be determined.
/// * `expression` - The query `Expression` that defines conditions for accessing table data.
///
/// # Returns
///
/// A result containing the `ScanKind` variant that represents the scan method:
///
/// - `ScanKind::ByPk` if the query can make use of the table's primary key.
/// - An indexed scan method if the query matches one of the table's defined indexes.
/// - `ScanKind::FullScan` if no specific scan method is applicable.
///
/// Returns a `QueryError` if any issue arises during the determination of the scan kind,
/// such as invalid expressions or index lookup failures.
Construction du Plan
Nous allons définir un QueryPlanner
son travail est de venir ajouter les étapes au plan qui permettent de rechercher de la données dans une table.
/// The `QueryPlanner` struct is responsible for generating query execution plans
/// based on the database, table name, and an optional filter expression.
///
/// # Fields
/// - `database`: A reference to the `Database` that contains the tables being queried.
/// - `table_name`: The name of the table to execute the query against.
/// - `expression`: An optional filter expression to use for query optimization
/// or filtering the results.
Sa méthode plan
à pour travail de faire ces opérations
Modification du ExecuteResult
On modifie le ExecuteResult pour qu'il soit en mesure d'afficher le Plan que l'on avait mis en attente sous la forme d'un Vec<String>
dans l'article précédent.
Comme Plan
implémente Display
, il est possible lui faire afficher les étapes au travers de la méthode run principale.
Intégration du QueryPlanner
Nous allons enfin pouvoir utiliser le flag venant de la directive EXPLAIN.
Je ne vais pas les recopier ici, mais ci-joint, voici les divers tests qui s'assure du bon fonctionnement de l'ensemble.
On peut enfin jouer avec !
Reprenons notre exemple du début.
Au travers de la table:
(
id INTEGER PRIMARY KEY,
nom TEXT(50),
prénom Text(50),
genre TEXT(2),
ville Text(100)
);
Muni des index suivants :
(nom, prénom);
(ville);
On fournit le set de données suivant :
INSERT INTO Client (id, nom, prénom, genre, ville) VALUES (1, 'Smith', 'John', 'M', 'Paris');
INSERT INTO Client (id, nom, prénom, genre, ville) VALUES (2, 'Martin', 'Marie', 'F', 'New York');
INSERT INTO Client (id, nom, prénom, genre, ville) VALUES (3, 'Haddad', 'Karim (كريم)', 'M', 'Tokyo');
INSERT INTO Client (id, nom, prénom, genre, ville) VALUES (4, 'Dubois', 'Sophie', 'F', 'Beyrouth');
INSERT INTO Client (id, nom, prénom, genre, ville) VALUES (5, 'Tanaka', 'Hiroshi (ひろし)', 'M', 'Beyrouth');
INSERT INTO Client (id, nom, prénom, genre, ville) VALUES (6, 'Yamamoto', 'Sakura (さくら)', 'F', 'Paris');
INSERT INTO Client (id, nom, prénom, genre, ville) VALUES (7, 'Smith', 'Emily', 'F', 'Osaka');
INSERT INTO Client (id, nom, prénom, genre, ville) VALUES (8, 'Martin', 'Jean', 'M', 'Lyon');
INSERT INTO Client (id, nom, prénom, genre, ville) VALUES (9, 'Haddad', 'Layla (ليلى)', 'F', 'New York');
INSERT INTO Client (id, nom, prénom, genre, ville) VALUES (10, 'Dubois', 'Paul', 'M', 'Tokyo');
Il est alors possible de lui demander ce qu'il compte faire.
EXPLAIN SELECT * FROM Client WHERE ville = 'Tokyo';
Il va alors vous dire qu'il connait index secondaire idx_ville
qui est apte à donner la bonne réponse sans tout scanner.
Scan secondary index idx_ville : ville = 'Tokyo' for table Client
Filter: ville = 'Tokyo'
Mais rajoute tout de même l'étape de filtration, car il ne sait pas si c'est exactement la donnée attendue, en tout cas les clients sont assurés d'habiter Tokyo.
On pourrait par exemple avoir:
SELECT * FROM Client WHERE ville = 'Paris' AND gender = 'F';
Sans filtrage, on aurait alors 2 entrées provenant directement de l'index
[Integer(1), Text("Smith"), Text("John"), Text("M"), Text("Paris")]
[Integer(6), Text("Yamamoto"), Text("Sakura (さくら)"), Text("F"), Text("Paris")]
Or nous ne voulons que les femmes, c'est pour cela que le filter vient rajouter la contrainte supplémentaire.
db > EXPLAIN SELECT * FROM Client WHERE ville = 'Paris' AND gender = 'F';
Scan secondary index idx_ville : ville = 'Paris' for table Client
Filter: gender = 'F' AND ville = 'Paris'
De sorte à ce que le résultat soit celui que l'on attend bien.
Pour les clefs primaires, c'est le même fonctionnement.
db > EXPLAIN SELECT * FROM Client WHERE id = 7 and ville = 'Paris';
PK direct access : id = 7 for table Client
Filter: ville = 'Paris' AND id = 7
Et si la données n'est indexée nulle part, alors on se rabat sur le coûteux fullscan.
db > EXPLAIN SELECT * FROM Client WHERE genre = 'F';
Full scan for table Client
Filter: genre = 'F'
Si aucune expression n'est défini, alors on n'a même pas de filtrage.
db > EXPLAIN SELECT * FROM Client;
Full scan for table Client
Nous venons de définir un gros morceau de ce qui fait l'ingéniosité d'une base de données, son LogicalPlan.
Conclusion
Cette fois-ci nous sommes en mesure de savoir ce que le QueryEngine pense faire de notre requête.
Il n'est pas parfait et possède nombreuses failles algorithmique, mais c'est une bonne base de réflexion pour itérer par-dessus.
Dans la prochaine partie nous allons utiliser ce LogicalPlan pour en faire un plan d'éxécution qui va réellement aller réaliser les opérations de recherches dans les index et de scan de tables.
Merci de votre lecture ❤️
Vous pouvez trouver le code la partie ici et le diff là.
Ce travail est sous licence CC BY-NC-SA 4.0.