Table des matières

• Rendre le QueryEngine “intelligent” et verbeux
• Implémentation
  • Plan
  • Détermination de la méthode de scan
  • Construction du Plan
  • Modification du ExecuteResult
• Intégration du QueryPlanner
• On peut enfin jouer avec !
• Conclusion

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 :

Question

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

CREATE TABLE Client (
    id INTEGER PRIMARY KEY, 
    nom TEXT(50),
    prénom Text(50), 
    genre TEXT(2),
    ville Text(100)
);

CREATE TABLE Client (id INTEGER PRIMARY KEY, nom TEXT(50),prénom Text(50), genre TEXT(2), ville Text(100) );

Muni des index suivants :

CREATE UNIQUE INDEX idx_identité ON Client(nom, prénom);
CREATE INDEX idx_ville ON Client(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”

Question

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ée, 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].

Attention

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 (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 = '...'.

Attention

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.

pub struct Plan {
    steps: Vec<PlanStep>,
}

impl Plan {
    pub fn new() -> Self {
        Self { steps: vec![] }
    }

    // Ajoute une nouvelle étapes dans l'exécution du plan
    pub fn add_step(&mut self, step: PlanStep) {
        self.steps.push(step);
    }
}

Cette structure est un wrapper autours d’un Vec<PlanStep>.

Le PlanStep est lui-même une énumération.

enum PlanStep {
    /// Represents a scan operation in a query plan.
    ///
    /// # Fields
    /// - `kind`: The kind of scan to perform (e.g., full table scan, index scan).
    /// - `table_name`: The name of the table to scan.
    Scan { kind: ScanKind, table_name: String },

    /// Represents a filter operation in a query plan.
    ///
    /// # Fields
    /// - `expression`: The logical expression used to filter rows.
    Filter { expression: Expression },
}

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.

enum ScanKind {
    /// A scan that reads all rows in the table (Full Table Scan).
    FullScan(FullScan),
    /// A scan that retrieves rows by their primary key values.
    ByPk(ScanByPk),
    /// A scan that retrieves rows using a secondary index.
    ByIndex(ScanByIndex),
}

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.
#[derive(Debug, PartialEq)]
pub struct ScanByPk {
    pub(crate) primary_key: PrimaryKey,
    pub(crate) values: Vec<Value>,
}

/// 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`).
struct ScanByIndex {
    index: Vec<String>,
    name: String,
    values: Vec<Value>,
    uniqueness: Uniqueness,
}

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
pub fn expression_from_index_definition_to_tuple(
    index: &[String],
    expression: &Expression,
) -> Result<Option<Vec<Value>>, QueryError> {
    let index = index.iter().map(|s| s.as_str()).collect::<Vec<&str>>();
    // Create the map that will accumulate the association between the
    // index column name and the value in the expression
    // for expression : col1 = val1 AND col2 > val2 AND col3 = val3 AND col4 = val4
    // for index : (col1, col3)
    // gives the map:
    //      col1 => val1
    //      col3 => val3
    //      col4 => val4
    let mut columns = HashMap::new();
    deconstruct_to_index_fields(expression, &mut columns);

    let columns_names: HashSet<&&str> = HashSet::from_iter(columns.keys());
    // Build a set out of the index definition
    let index_fields = HashSet::from_iter(&index);

    // if column_names is a superset of index_fields
    // then all index definition can be found in the expression
    if columns_names.is_superset(&index_fields) {
        let mut values = vec![];
        for column_name in index {
            if let Some(ColumnExpression { value, .. }) = columns.get(column_name) {
                // accumulate values in the right order
                values.push(value.clone());
            }
        }
        // giving in our example the tuple (val1, val3)
        Ok(Some(values))
    } else {
        // if it's not a superset then the index isn't compatible with the expression
        Ok(None)
    }
}

Attention

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

fn deconstruct_to_index_fields<'a>(
    expression: &'a Expression,
    acc: &mut HashMap<&'a str, &'a ColumnExpression>,
) {
    match expression {
        // nous nous limitons aux expressions en AND
        Expression::Logical(LogicalExpression { lhs, operator, rhs }) => {
            if operator == &LogicalOperator::And {
                deconstruct_to_index_fields(lhs, acc);
                deconstruct_to_index_fields(rhs, acc);
            }
        }
        // si c'est une colonne, on peut extraire le nom
        Expression::Column(column) => {
            let ColumnExpression {
                column: column_name,
                operator,
                ..
            } = column;
            // pour être une définition d'index, la valeur doit être égale
            if operator == &BinaryOperator::Equal {
                acc.insert(column_name.0.as_str(), column);
            }
        }
    }
}

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

impl IndexRegistry {
    fn search_index<I: Indexable>(
        &self,
        expression: &Expression,
        indexes: &BTreeMap<Vec<String>, I>,
        uniqueness: Uniqueness,
    ) -> Result<Option<ScanKind>, QueryError> {
        for (index_columns, index) in indexes.iter() {
            if let Some(index_values) =
                expression_from_index_definition_to_tuple(index_columns, expression)?
            {
                return Ok(Some(ScanKind::ByIndex(ScanByIndex::new(
                    index_columns.clone(),
                    index.name().to_string(),
                    index_values,
                    uniqueness,
                ))));
            }
        }

        Ok(None)
    }
}

Comme il existe deux types d’index, on se créé une fonction qui va rechercher dans les deux groupes d’index.

impl IndexRegistry {
    pub fn get_index(&self, expression: &Expression) -> Result<Option<ScanKind>, QueryError> {
        if let Some(index) =
            self.search_index(expression, &self.unique_indexes, Uniqueness::Unique)?
        {
            return Ok(Some(index));
        }

        if let Some(index) = self.search_index(expression, &self.indexes, Uniqueness::NonUnique)? {
            return Ok(Some(index));
        }

        Ok(None)
    }
}

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.
fn get_scan_method<'a>(
    table: &'a Table,
    expression: &'a Expression,
) -> Result<ScanKind, QueryError> {
    if let Some(pk) =
        expression_from_index_definition_to_tuple(&table.schema.primary_key, expression)?
    {
        return Ok(ScanKind::ByPk(ScanByPk::new(expression.clone(), pk)));
    }

    if let Some(scan) = table.indexes.get_index(expression)? {
        return Ok(scan);
    }

    Ok(ScanKind::FullScan(FullScan))
}

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.
pub struct QueryPlanner<'a> {
    /// The database object containing all tables and their metadata.
    database: &'a Database,
    /// The name of the table on which the query operation is being planned.
    table_name: &'a str,
    /// An optional filter expression that determines which rows are included in the query.
    expression: Option<&'a Expression>,
}

Sa méthode plan à pour travail de faire ces opérations

impl QueryPlanner<'_> {
    pub fn plan(&self, plan: &mut Plan) -> Result<(), QueryError> {
        // on détermine s'il y a besoin de filtrer les résultats
        let expression = if let Some(expression) = self.expression {
            expression
        } else {
            // si ce n'est pas le cas, on réalise un fullscan
            plan.add_step(PlanStep::Scan {
                kind: ScanKind::FullScan(FullScan),
                table_name: self.table_name.to_string(),
            });
            return Ok(());
        };

        let table = self
            .database
            .get_table(self.table_name)
            .ok_or(QueryError::TableNotExist(self.table_name.to_string()))?;

        // en fonction de l'expression, on choisit la méthode de scan
        // la plus appropriée, les index ou le fullscan
        let scan_kind = get_scan_method(table, expression)?;

        // on ajoute une étape de scan
        plan.add_step(PlanStep::Scan {
            kind: scan_kind,
            table_name: self.table_name.to_string(),
        });
        // on ajoute l'étape de filtration des résultats
        plan.add_step(PlanStep::Filter {
            expression: expression.clone(),
        });

        Ok(())
    }
}

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.

enum ExecuteResult {
    Nil,
    Tuples(Vec<Vec<Value>>),
    Explain(Plan),
}

Comme Plan implémente Display, il est possible lui faire afficher les étapes au travers de la méthode run principale.

pub fn run() -> Result<(), Box<dyn Error>> {
    let mut database = database::Database::new();
    loop {
        print!("db > ");
        std::io::stdout().flush()?;
        let mut command = String::new();
        std::io::stdin().read_line(&mut command)?;
        let command = command.trim();

        match database.run(command) {
            Ok(ExecuteResult::Tuples(rows)) => {
                for row in rows {
                    println!("{:?}", row);
                }
            }
            Ok(ExecuteResult::Explain(plan)) => {
                println!("{}", plan);
            }
            Ok(ExecuteResult::Nil) => {}
            Err(err) => {
                println!("{}", err);
            }
        }
    }
}

Intégration du QueryPlanner

Nous allons enfin pouvoir utiliser le flag venant de la directive EXPLAIN.

impl Database {
    pub fn select(
        &mut self,
        table_name: String,
        where_clause: Option<WhereClause>,
        explain: bool,
    ) -> Result<ExecuteResult, SelectError> {
        // si on est en dry run
        if explain {
            let expression = where_clause
                .as_ref()
                .map(|where_clause| &where_clause.expression);
            let query_planner = QueryPlanner::new(self, &table_name, expression);
            // on créé un plan vide
            let mut plan = Plan::new();
            query_planner.plan(&mut plan).map_err(SelectError::Query)?;
            // on renvoie un explain
            Ok(ExecuteResult::Explain(plan))
        } else {
            // le code précédent
            match self.tables.get(&table_name) {
                Some(table) => table.select(where_clause),
                None => Err(SelectError::TableNotExist(table_name))?,
            }
        }
    }
}

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:

CREATE TABLE Client (
    id INTEGER PRIMARY KEY, 
    nom TEXT(50),
    prénom Text(50), 
    genre TEXT(2),
    ville Text(100)
);

Muni des index suivants :

CREATE UNIQUE INDEX idx_identité ON Client(nom, prénom);
CREATE INDEX idx_ville ON Client(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 algorithmiques, 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à.