Table des matières

• Index itérables
  • Théorie
  • Trait Indexable
  • ValueIndex
  • Primary Index
• IndexIterator
• Index Registry
• Full scan
• Execution du plan logique
  • Trait ExecutePlan
  • Plan
• Plan Executor
• Adaptation de la méthode select de la base de données
• Adaptation de la déclaration de table
• On a fini !
• Conclusion

Bonjour à toutes et tous 😃

Lors de la partie précédente, nous avons défini une directive EXPLAIN et avons propagé un flag dans le reste de l’application.

Celui-ci nous permet de demander à la base de données ce qu’elle compte faire comme opérations pour récupérer des entrées selon des critères.

On a vu que si l’on possédait des index sur les données, il était possible de limiter les opérations de lectures complètes de la table, que l’on appelle plus communément un “full scan”.

Aujourd’hui, nous allons modifier la base de code pour réaliser concrètement les opérations de scan d’index et de tables.

Et pour cela, nous allons devoir revoir pas mal de choses sur les index et leur définition.

Mais également tout le processus de lecture de base de données qui, pour le moment, est basé sur un système d’allocation mémoire et de copie de données, système qui fonctionne sur de petits volumes de données, mais sur des tables avec des milliers de lignes, ce n’est juste pas jouable.

Nous allons donc passer tout ce beau monde dans une logique d’itérateur.

Nous avions également abordé dans la conclusion de la partie 12 la notion de “Volcano Model”, nous allons le mettre en place également. Cela signifie que des itérateurs consomment d’autres itérateurs jusqu’à produire un résultat streamable.

On verra les détails dans la partie de l’article qui lui est consacrée.

Bref, on a du pain sur la planche !

Index itérables

Théorie

Comme je vous l’ai dit dans l’introduction, les index actuels ne nous permettent pas de scanner les données, de plus la manière même dont ils sont définis ne les rend pas portables dans les itérateurs.

Or, nous voulons streamer le contenu de nos index.

Prenons les données suivantes:

Muni des index suivants :

CREATE UNIQUE INDEX idx_identité ON Client(nom, prénom);
CREATE INDEX idx_ville ON Client(ville);

Pour l’identité, pas de surprise, il y a un ID qui correspond à un couple unique (nom, prénom).

Donc pour chaque entrée dans l’index, nous avons un tableau “ids” d’un seul élément qui représente la “row_id” de l’entrée correspondant à la valeur de l’index.

En bases, les index vont ressembler à ceci.

L’index “idx_ville” est plus intéressant, car il peut y avoir plus d’une personne qui habite la même ville.

Et c’est bien ce qui est stocké en mémoire, non pas un “row_id”, mais une collection de “row_id”.

Chaque entrée représente une entrée qui possède la ville indexée comme valeur.

Prenons par exemple “Paris”. Nous avons [1, 6] comme valeur.

Et si on regarde nos données, nous avons effectivement deux entrées, la 1 et la 6, qui ont comme valeur ville=“Paris”.

Maintenant, imaginez que cette table est le registre mondial d’une grande entreprise.

Ce ne sont pas des dizaines d’entrées, mais des millions qu’il faudra gérer.

Et parmi ces millions de personnes, la probabilité que des dizaines de milliers de personnes habitent au même endroit est plus que probable.

C’est pour cela qu’il nous faut un itérateur. Pour rappel, un itérateur est un mécanisme qui permet de charger des données uniquement lorsque c’est nécessaire.

Si on reprend notre exemple, il y a 15556 personnes habitant à Paris.

Cela donnerai une structure du type:

Paris => 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, ..., 15554, 15555, 15556

Il n’est pas exclu de tout charger en mémoire, mais ce n’est pas très efficace.

À la place, nous allons plutôt parcourir le tableau de données de l’index au moyen d’un curseur, capable de “se rappeler de la position où il est”.

0, 1, 2, 3, 4, 5, 6, 7, 8, 9, ..., 15554, 15555, 15556
↑

Lorsque l’on vient lire l’index, le curseur se déplace d’un cran.

 0,  1,  2,  3,  4,  5,  6,  7,  8,  9, ..., 15554, 15555, 15556
     ↑

Et ainsi de suite jusqu’à atteindre la fin de l’index.

 0,  1,  2,  3,  4,  5,  6,  7,  8,  9, ..., 15554, 15555, 15556
                                                                 ↑

De cette manière, on peut consommer au fur et à mesure de la donnée, sans avoir à charger l’intégralité de l’index en mémoire.

C’était la théorie, maintenant place à la pratique ! 😇

Trait Indexable

La première chose que nous allons faire est de déclarer un trait qui nous permettra de travailler plus confortablement avec nos index.

Étant donné que nous allons utiliser très régulièrement l’itérateur, nous allons créer un alias de type pour le trait.

pub type IndexIteratorData<'a> = Box<dyn Iterator<Item = &'a usize> + 'a>;

Maintenant nous allons pouvoir définir le trait.

trait Indexable: DerefMut<Target = BTreeMap<Vec<Value>, Vec<usize>>> {
    /// Push a new value to the index
    fn push(&mut self, row_id: usize, value: Vec<Value>);
    /// Check value is compatible to the index
    fn check(&self, columns: &[String], row: &HashMap<String, Value>) -> Result<(), IndexError>;
    /// Get the iterator for the given value
    fn get_value(&self, value: &[Value]) -> Option<IndexIteratorData>;
    /// Get the index name
    fn get_index_name(&self) -> &str;
    /// Get the table name
    fn get_table_name(&self) -> &str;
    /// Get the index definition
    fn get_definition(&self) -> &Vec<String>;
}

Ce trait contient 5 méthodes:

• push qui permet de rajouter un row_id à une entrée de l’index
• check qui valide que la donnée à indexée est conforme à la définition de l’index notamment l’unicité de la valeur indexée
• get_value qui renvoie le fameux itérateur que l’on va définir.
• get_index_name, get_table_name et get_definition, les getters des champs associés

Pour rappel, les Value sont les valeur de nos tuples.

enum Value {
    Integer(i64),
    Text(String),
    Null,
}

Voici un exemple de l’utilisation du trait.

// indexation
index.push(12, vec![Value::String("Paris".into())]);
index.push(68, vec![Value::String("Tokyo".into())]);
index.push(22, vec![Value::String("Paris".into())]);
index.push(35, vec![Value::String("Buenas Aires".into())]);
index.push(9, vec![Value::String("Paris".into())]);

let index_iterator = index.get_value(&[Value::Text("Paris".into)]);
// On vérifie que l'index existe bien pour la valeur demandée
let index_iterator = index_iterator.except("Index entry not found");
// Il peut alors être consommé
for row_id in index_iterator {
    // iter 12, 22, 9
}

ValueIndex

Nous allons en définir une implémentation qui a pour rôle de venir indexer des tuples de valeurs.

Nous allons l’appeler ValueIndex.

pub struct ValueIndex {
    /// The underlying BTreeMap that stores the index data
    inner: BTreeMap<Vec<Value>, Vec<usize>>,
    /// The name of the table that the index belongs to
    table_name: String,
    /// The name of the index
    index_name: String,
    /// The uniqueness of the index
    uniqueness: Uniqueness,
    /// The definition of the index
    definition: Vec<String>,
}

Et voici son implémentation du trait Indexable.

impl Indexable for ValueIndex {
    /// Insert a new value into the index.
    ///
    /// If the index has `Uniqueness::Unique`, it will check if the value is already present
    /// in the index. If it is, it will return an error. If not, it will add the value to the
    /// index and store the row id that the value is associated with.
    ///
    /// If the index has `Uniqueness::NonUnique`, it will simply add the value to the index
    /// and store the row id that the value is associated with.
    ///
    /// # Parameters
    /// - `row_id`: The row id that the value is associated with
    /// - `value`: The value to insert into the index
    fn push(&mut self, row_id: usize, value: Vec<Value>) {
        match self.uniqueness {
            Uniqueness::Unique => {
                println!(
                    "Insert {:?} into unique index {}  => row_id {row_id}",
                    value, self.index_name
                );
                self.insert(value, vec![row_id]);
            }
            Uniqueness::NonUnique => {
                println!(
                    "Insert {:?} into non unique index {} => row_id {row_id}",
                    value, self.index_name
                );
                self.entry(value).or_default().push(row_id);
            }
        }
    }

    /// Check if the given row can be inserted into the index, given the columns of the index.
    ///
    /// If the index has `Uniqueness::Unique`, it will check if the value is already present in the index.
    /// If it is, it will return an `IndexError::DuplicateIndexValue` error. If not, it will return `Ok(())`.
    ///
    /// If the index has `Uniqueness::NonUnique`, it will simply return `Ok(())`.
    ///
    /// # Parameters
    /// - `row`: The row to check
    ///
    /// # Errors
    /// - `IndexError::DuplicateIndexValue`: If the index has `Uniqueness::Unique` and the value is already present in the index.
    fn check(&self, row: &HashMap<String, Value>) -> Result<(), IndexError> {
        match self.uniqueness {
            Uniqueness::Unique => {
                let key = as_index_tuple(self.get_definition(), row);

                if self.contains_key(&key) {
                    return Err(IndexError::DuplicateIndexValue {
                        index_name: self.index_name.to_string(),
                        table_name: self.table_name.to_string(),
                        values: key,
                    });
                }
            }
            Uniqueness::NonUnique => {}
        }
        Ok(())
    }

    /// Returns an iterator over the row ids associated with the given value.
    ///
    /// # Parameters
    /// - `value`: The value to search for in the index.
    ///
    /// # Returns
    /// - `Option<IndexIteratorData>`: An iterator over the row ids associated with the given value,
    /// or `None` if the value is not found in the index.
    fn get_value(&self, value: &[Value]) -> Option<IndexIteratorData> {
        self.get(value)
            .map(|v| Box::new(v.iter()) as IndexIteratorData)
    }

    fn get_index_name(&self) -> &str {
        &self.index_name
    }

    fn get_table_name(&self) -> &str {
        &self.table_name
    }

    fn get_definition(&self) -> &Vec<String> {
        &self.definition
    }
}

La méthode get_value renvoie un itérateur sur les row_ids associées à l’entrée de l’index si celle-ci existe.

Il faut remarquer qu’il n’y a aucune allocation mémoire lors de la création de l’itérateur. Cela signifie que l’on peut lire les données sans avoir besoin de copier les données de l’index.

On utilise également une fonctionnalité de Rust pour convertir notre Box d’itérateur en IndexIteratorData.

Primary Index

Nous avions précédemment défini les index primaires séparément car nous devions nous l’avouer, la modélisation de nos index n’était pas vraiment optimale. 😅

Désormais, nous possédons le trait Indexable qui définit les comportements des index.

Nous pouvons donc définir une seconde implémentation de Indexable pour nos index primaires.

pub const PRIMARY_INDEX_NAME: &str = "PRIMARY";

struct PrimaryIndex {
    table_name: String,
    definition: Vec<String>,
    inner: BTreeMap<Vec<Value>, Vec<usize>>,
}

impl Indexable for PrimaryIndex {
    fn push(&mut self, row_id: usize, value: Vec<Value>) {
        self.entry(value).or_default().push(row_id);
    }

    fn check(&self, _row: &HashMap<String, Value>) -> Result<(), IndexError> {
        Ok(())
    }

    fn get_index_name(&self) -> &str {
        PRIMARY_INDEX_NAME
    }

    fn get_table_name(&self) -> &str {
        &self.table_name
    }

    fn get_definition(&self) -> &Vec<String> {
        &self.definition
    }
}

Les index primaires sont unique à une table de donnée, son nom est également unique et se nomme “PRIMARY”.

IndexIterator

Nous avons un itérateur de row IDs, mais ce n’est pas ce qui nous intéresse vraiment.

Nous voulons les lignes associées à ces row IDs.

Nous avons donc besoin d’un itérateur sur les lignes.

Pour cela, nous allons définir une structure IndexIterator.

pub struct IndexIterator<'a> {
    /// The query engine
    query_engine: QueryEngine<'a>,
    /// The iterator over the row ids
    row_ids: IndexIteratorData<'a>,
}

Cette structure a deux champs:

• query_engine: Le moteur de requête.
• row_ids: Un itérateur sur les row IDs.

Pour créer cet itérateur nous allons utiliser la fonction get_row de QueryEngine qui renvoie un itérateur sur les rows.

impl Iterator for IndexIterator<'_> {
    type Item = Result<Vec<Value>, SelectError>;

    fn next(&mut self) -> Option<Self::Item> {
        match self.row_ids.next() {
            // Retourne `None` si l'itérateur est fini
            None => None,
            // Appel du moteur de requête pour obtenir la row associée au row_id
            // lecture de la table et des pages contenant les rows
            Some(row_id) => Some(self.query_engine.get_row(*row_id)),
        }
    }
}

C’est à ce moment-là que nous allons réellement lire l’index et obtenir les row IDs.

Dans notre implémentation actuelle, nos index sont des BTreeMap en mémoire, donc le gain de performance est minime. Par contre, les futurs index seront des fichiers sur disque.

Lire les données de manière “lazy” signifie que les données seront lues lorsque l’on va les utiliser, ce qui n’est pas négligeable pour des accès disque. 😊

Reprenons nos données précédentes:

Sur cette table, il y a 3 index:

• PRIMARY id index primaire.
• idx_ville ville index non-unique.
• idx_identité (nom, prénom) index unique.

On commence par obtenir depuis l’index idx_ville l’itérateur sur les row IDs qui correspondent à la ville “Paris”:

let index_rows = index.get_value(&[Value::Text("Paris".into)]);.except("Index entry not found");

De cet itérateur nous obtenons ensuite un itérateur sur les rows:

let index_iterator = IndexIterator {
    query_engine: query_engine,
    row_ids: index_rows,
};

Celui-ci peut alors être consommé de cette manière:

for row in index_iterator {
    // [Value::Text("Smith")), Value::Text("John")Value::Text("M".into()), Value::Text("Paris")]
    // [Value::Text("Yamamoto")), Value::Text("Sakura (さくら)")Value::Text("F".into()), Value::Text("Paris")]
}

On induit alors une deuxième couche de laziness: l’index itérateur n’appelle l’itérateur interne que lorsque les données sont utilisées, et l’itérateur interne n’appelle l’index que lorsque l’index itérateur l’appelle.

De ce fait, notre index peut avoir des milliers de lignes, et nous ne lirons les pages de la table que lorsque cela est réellement nécessaire.

On progresse ! 😊

Index Registry

Maintenant que nous avons des index non seulement itérables mais également scannables, nous avons besoin de les stocker afin de pouvoir les retrouver lorsque cela sera necessaire.

Tout d’abord modélisons notre collection d’index.

/// A map of column definitions to index implementations.
type Index = BTreeMap<String, Box<dyn Indexable>>;

Chaque index possède un nom unique qui nous permettra de le retrouver facilement lorsque cela sera nécessaire.

On pourrait s’arrêter là, mais nous allons légèrement complexifier le modèle pour optimiser les recherches.

Dans une base de données, rechercher par index primaire est toujours plus avantageux que de rechercher dans des index.

Nous voulons donc que les requêtes se fassent sur les index primaires autant que possible.

Si la requête ne permet pas de trouver des rows par index primaire, nous allons chercher par index non-unique ou unique.

Mais dans ces deux index il y a également une notion de performance qui entre en ligne de compte.

En effet, par définition, un index unique associe une seule row à une entrée dans l’index. Au contraire, un index non-unique peut associer plusieurs rows à une seule entrée.

Cela signifie que scanner un index unique est la certitude de n’avoir au plus qu’une seule row, tandis que scanner un index non-unique peut avoir plusieurs rows, parfois des milliers.

La modélisation de notre stockage d’index va matérialiser cette distinction de type d’index, via une map entre le type d’index et son contenu.

Nous allons utiliser une BtreeMap pour cela. Car elle possède la particularité de fournir un itérateur ordonné.

Cela signifie que si nous définissons un ordre de priorité sur nos types d’index, alors nous aurons la certitude que le type d’index scanner sera dans l’ordre d’importance que nous voulons.

PRIMARY > UNIQUE > NON_UNIQUE

Pour cela nous pouvons utiliser une propriété des énumération qui permet de donner explicitement une valeur à une variante.

Ensuite en dérivant Ord et PartialOrd sur notre enum, nous aurons une ordonnancement naturelle.

#[derive(PartialEq, PartialOrd, Eq, Ord)]
pub enum IndexType {
    Primary = 0,
    ValueUnique = 1,
    ValueNonUnique = 2,
}

On définit ensuite notre struct IndexRegistry qui utilise une BTreeMap associant un IndexType et un Index.

#[derive(Default)]
pub struct IndexRegistry {
    indexes: BTreeMap<IndexType, Index>,
    names: BTreeSet<String>,
}

On stocke également le nom des index pour ne pas avoir de duplication de nom d’index sur la table.

On peut alors implementer IndexRegistry:

On commence par l’ajout d’index.

impl IndexRegistry {
    /// Add a value index to the registry
    pub fn add_value_index(&mut self, index: ValueIndex) -> Result<(), IndexError> {
        let name = index.get_index_name();
        let table_name = index.get_table_name();

        if self.names.contains(name) {
            return Err(IndexError::DuplicateIndex {
                index_name: name.to_string(),
                table_name: table_name.to_string(),
            });
        }

        self.names.insert(name.to_string());
        match index.get_uniqueness() {
            Uniqueness::Unique => {
                self.indexes
                    .entry(IndexType::ValueUnique)
                    .or_default()
                    .insert(name.to_string(), index.boxed());
            }
            Uniqueness::NonUnique => {
                self.indexes
                    .entry(IndexType::ValueNonUnique)
                    .or_default()
                    .insert(name.to_string(), index.boxed());
            }
        }

        Ok(())
    }

        /// Add a primary index to the registry
    pub fn add_primary_index(&mut self, index: PrimaryIndex) {
        // Check if the primary index is already added
        // If it is, do nothing
        if self.names.contains(PRIMARY_INDEX_NAME) {
            return;
        }

        self.names.insert(PRIMARY_INDEX_NAME.to_string());
        self.indexes
            .entry(IndexType::Primary)
            .or_default()
            .insert(PRIMARY_INDEX_NAME.to_string(), index.boxed());
    }
}

On vérifie que l’index n’a pas de doublon avant de l’ajouter.

On ajoute ensuite le nom de l’index au registre. Nous sommes obligé de découpler les cas d’index unique et non-unique.

L’API entry de BtreeMap permet de créer une entrée si elle n’existe pas alors or_default permet de la créer et de renvoyer une référence mutable vers l’entrée.

let map = BTreeMap::new::<usize, String>();
let value = map.entry(1).or_default();

Dans le cas où celle-ci n’existe pas, value est une référence mutable vers une String vide qui sera créé dans la map à la clef 1.

Sinon value est une réference mutable vers la valeur de la clef1.

Ensuite, nous implémentons les méthodes permettant d’insérer des valeurs dans les index, ainsi que celle permettant de trouver un index par sa définition.

On implémente également la méthode permettant de vérifier si un index peut être ajouté.

impl IndexRegistry {

    /// Check if the given value can be inserted into the index
    pub fn check(&mut self, value: &HashMap<String, Value>) -> Result<(), IndexError> {
        for index in self
            .indexes
            .iter()
            .flat_map(|(_, indexes)| indexes.values())
        {
            index.check(value)?;
        }

        Ok(())
    }

    /// Insert a value into all indexes matching the value
    pub fn insert_into_index(
        &mut self,
        value: &HashMap<String, Value>,
        row_id: usize,
    ) -> Result<(), IndexError> {
        for index in self
            .indexes
            .iter_mut()
            .flat_map(|(_, indexes)| indexes.values_mut())
        {
            let key = as_index_tuple(index.get_definition(), value);
            index.push(row_id, key);
        }

        Ok(())
    }

    /// Get an index by its definition
    pub fn get_index(&self, name: &str) -> Option<&dyn Indexable> {
        self.indexes
            .values()
            .find_map(|indexes| indexes.get(name))
            .map(|v| v.as_ref())
    }
}

Ici on va utiliser la fonctionnalité de flat_map de Iterator pour itérer sur tous les types d’index et les indexes eux-mêmes.

Mais également le find_map de la option de Option qui permet de prendre la première valeur de l’option qui satisfait une condition.

Ces deux APIs permettent de traiter de manière indifférentielle les index uniques et non-uniques.

Ce n’est pas réellement nécessaire, mais je voulais m’amuser un peu avec les APIs de Rust. ^^

On implémente la méthode permettant de trouver un index par expression.

impl IndexRegistry {
    /// From an [Expression] get the potential index matching it
    /// Priority is given to unique index
    pub fn get_index_by_expression(
        &self,
        expression: &Expression,
        table_name: &str,
    ) -> Result<Option<ScanKind>, QueryError> {
        let mut scan_kind = None;

        // Indexes are stored by type, because unique index has higher priority
        // unique index will be checked first
        for (index_columns, index) in self.indexes.iter().flat_map(|(_, indexes)| indexes) {
            if let Some(index_values) =
                expression_from_index_definition_to_tuple(index_columns, expression)?
            {
                scan_kind = Some(ScanKind::ByIndex(ScanByIndex::new(
                    index_columns.clone(),
                    index.get_index_name().to_string(),
                    index_values,
                    table_name,
                )));
                break;
            }
        }
        Ok(scan_kind)
    }
}

Pour chaque table de la base de données. La structure des index est la suivante:

{
    Primary: {
        1 => [1],
        2 => [2],
        8 => [8],
        9 => [9],
        10 => [10],
    }
    Unique: {
        "idx_identité": {
            ("Smith", "John") => [1],
            ("Martin", "Marie") => [2],
            ("Martin", "Jean") => [8],
            ("Haddad", "Layla") => [9],
            ("Dubois", "Paul") => [10],
        },
    },
    NonUnique: {
        "idx_ville": {
            "Beyrouth" => [4, 5],
            "Lyon" => [2, 4],
            "New York" => [2, 9],
            "Osaka" => [7],
        },
        "idx_nom": {
            "Smith" => [1],
            "Martin" => [2, 8],
            "Haddad" => [9],
            "Dubois" => [10],
        }
    }
}

Comme les index sont stockés par type et que les index uniques sont prioritaires, alors les index uniques seront parcourus en premier.

for index in self.indexes.keys() {
    // IndexType::ValueUnique
    // IndexType::ValueNonUnique
    // IndexType::ValueNonUnique
}

Donc si un index unique correspondant à l’expression est trouvé, alors on sort de la boucle et on retourne l’index sans passer par les indexes non uniques.

Bon, ça commence à prendre forme. 😄

Full scan

Nous allons adapter le scanner que nous avions fait en partie 12.

pub struct Scanner<'a> {
    query_engine: QueryEngine<'a>,
    current_row: usize,
}

impl<'a> Scanner<'a> {
    pub fn new(query_engine: QueryEngine<'a>) -> Self {
        Self {
            query_engine,
            current_row: 0,
        }
    }
}

impl Iterator for Scanner<'_> {
    type Item = Result<Vec<Value>, SelectError>;

    fn next(&mut self) -> Option<Self::Item> {
        // on va jusqu'au dernier tuple de la table
        if self.current_row >= self.query_engine.get_table().row_number {
            return None;
        }

        let row = self.query_engine.get_row(self.current_row);

        match row {
            Ok(row) => {
                self.current_row += 1;
                Some(Ok(row))
            }
            Err(err) => Some(Err(err)),
        }
    }
}

Pas grand-chose à ajouter, à part que le scanner utilise désormais le QueryEngine pour réaliser la récupération des données.

Cela permet d’homogénéiser les deux API entre le scan d’index et le scan de table.

Le premier via l’IndexIterator et le deuxième via le Scanner.

Les deux API sont des itérateurs de Vec<Value>.

Execution du plan logique

Maintenant que tous nos composants de récupération de données sont sous la forme d’itérateurs, nous pouvons passer à l’exécution du plan logique.

Pour rappel, un plan est un ensemble d’étapes de traitement de la donnée, qui va de la récupération de celles-ci dans la base de données jusqu’à leur affichage final.

Trait ExecutePlan

Nous allons maintenant rajouter une trait ExecutePlan qui va permettre de traiter un plan de maniere dynamique.

Nous allons définir deux type alias pour faciliter la lecture.

/// The input of the step of the plan to execute
type PlanExecInput<'a> = Box<dyn Iterator<Item = Result<Vec<Value>, SelectError>> + 'a>;
/// The output of the step of the plan executed
pub type PlanExecOutput<'a> =
    Result<Box<dyn Iterator<Item = Result<Vec<Value>, SelectError>> + 'a>, SelectError>;

Le boxing est nécessaire car les itérateurs ne sont pas des structures mais des traits.

PlanExecInput est un itérateur de Vec<Value> il sera utilisé comme entree de la prochaine étape du plan.

PlanExecOutput est un itérateur de Vec<Value> il sera utilisé comme sortie de la prochaine étape du plan.

trait ExecutePlan {
    fn execute<'a>(
        self,
        database: &'a Database,
        inputs: Vec<PlanExecInput<'a>>,
    ) -> PlanExecOutput<'a>;
}

Chaque étape du plan prendra deux arguments:

• database: la base de données
• inputs: la sortie de l’etape precedente

inputs peut être un seul itérateur ou plusieurs itérateurs ou même aucun.

Plan

Voici sa modélisation en Rust.

struct Plan {
    steps: Vec<PlanStep>,
}

enum PlanStep {
    /// Represents a scan operation in a query plan.
    Scan(ScanKind),

    /// Represents a filter operation in a query plan.
    Filter(FilterRow),
}
```	

#### Etapes de scans

Les opérations de scans elles se décomposent en plusieurs types:
- `ScanKind::ByIndex`
- `ScanKind::FullScan`

```rust
enum ScanKind {
    /// A scan that reads all rows in the table (Full Table Scan).
    FullScan(FullScan),
    /// A scan that retrieves rows using an index
    ByIndex(ScanByIndex),
}

Un full scan est la manière la plus simple mais aussi généralement la plus lente et peu efficace de récupérer des données.

struct FullScan {
    // nom de la table à parcourir
    table_name: String,
}

Le full scan va lire toutes les lignes de la table et les retourner. Cette simplicité se retrouve dans modélisation: seul le nom de la table est requis.

Pour cela on utilise le Scanner qui va nous retourner un itérateur sur les lignes de la table.

impl ExecutePlan for FullScan {
    fn execute<'a>(
        self,
        database: &'a Database,
        _inputs: Vec<PlanExecInput<'a>>,
    ) -> PlanExecOutput<'a> {
        let table_name = &self.table_name;
        // Get the table
        let table = database
            .get_table(table_name)
            .ok_or(SelectError::TableNotExist(table_name.to_string()))?;
        // Create the query engine
        let query_engine = QueryEngine::new(table);
        // Create the scanner
        let scanner = Scanner::new(query_engine);
        Ok(Box::new(scanner))
    }
}

Un scan par index est légèrement plus complexe.

struct ScanByIndex {
    // composants de l'index
    definition: Vec<String>,
    // nom de l'index
    name: String,
    // valeur de l'entrée de l'index
    values: Vec<Value>,
    // nom de la table associé à l'index
    table_name: String,
}

On implémente ExecutePlan pour ScanByIndex:

impl ExecutePlan for ScanByIndex {
    fn execute<'a>(
        self,
        database: &'a Database,
        _inputs: Vec<PlanExecInput<'a>>,
    ) -> PlanExecOutput<'a> {
        let table_name = &self.table_name;
        
        // Get the table
        let table = database
            .get_table(table_name)
            .ok_or(SelectError::TableNotExist(table_name.to_string()))?;

        // Get the index by its name
        let index = table.indexes.get_index(&self.name);

        // Get the row ids iterator from the index
        let result = match index {
            Some(index) => match index.get_value(&self.values) {
                Some(rows) => rows,
                None => return Ok(dummy()),
            },
            None => return Ok(dummy()),
        };
        
        // Create the index iterator over rows
        let index_iterator = IndexIterator::new(table_name.to_string(), database, result)?;

        Ok(Box::new(index_iterator))
    }
}

Etape de filtres

Un filtre est une opération qui permet de conserver uniquement certaines lignes d’une table.

Le filtre prend en argument une expression et un nom de table.

struct FilterRow {
    pub expression: Expression,
    pub table_name: String,
}

Nous allons réutiliser la fonction filter_row de la partie 12.

impl ExecutePlan for FilterRow {
    fn execute<'a>(
        self,
        database: &'a Database,
        mut inputs: Vec<PlanExecInput<'a>>,
    ) -> PlanExecOutput<'a> {
        // Check the number of inputs
        if inputs.len() != 1 {
            return Err(SelectError::InvalidFilter(
                "Invalid number of inputs".to_string(),
            ));
        }
        // Get the first iterator of the input
        let input = inputs.remove(0);
        let expression = self.expression;
        // Get the table
        let table_name = &self.table_name;
        let table = database
            .get_table(table_name)
            .ok_or(SelectError::TableNotExist(table_name.to_string()))?;

        // Filter the iterator
        let result = input.filter_map(move |row| match row {
            Ok(row) => match filter_row(&row, &expression, &table.schema) {
                // tuple matches
                Ok(true) => Some(Ok(row)),
                // tuple doesn't match
                Ok(false) => None,
                // Propagate the error
                Err(err) => Some(Err(SelectError::Query(err))),
            },
            Err(err) => Some(Err(err)),
        });
        Ok(Box::new(result))
    }
}

On vérifie que l’étape possède une seule entrée.

Ensuite, on applique notre filtrage sur cet itérateur.

L’itérateur résultant sera le filtrage du résultat de l’étape précédente.

  

flowchart 
    Scan--->|Iterator Rows|Filter
    Filter --->|Iterator Rows filtred|Output

Plan Executor

Maintenant que chaque étape est exécutable, il est temps de mettre en musique tout cela.

Pour cela, nous allons définir un plan executor qui va permettre d’ordonner les étapes et de les exécuter successivement.

struct PlanExecutor<'a> {
    database: &'a Database,
    plan: Plan,
}

Celui-ci prend la base de données et le plan en argument.

Nous allons définir une fonction dummy qui nous permettra de renvoyer un iterator vide.

fn dummy() -> Box<dyn Iterator<Item = Result<Vec<Value>, SelectError>>> {
    Box::new(vec![].into_iter())
}

Nous pouvons maintenant exécuter notre plan.

impl<'a> PlanExecutor<'a> {
    /// Execute the plan and return the results.
    pub fn exec(self) -> PlanExecOutput<'a> {
        let mut out = dummy();
        for step in self.plan.steps.into_iter() {
            match step {
                PlanStep::Scan(scan_step) => match scan_step {
                    ScanKind::FullScan(scan) => {
                        out = scan.execute(self.database, vec![])?;
                    }
                    ScanKind::ByIndex(scan) => {
                        out = scan.execute(self.database, vec![])?;
                    }
                },
                PlanStep::Filter(filter) => {
                    out = filter.execute(self.database, vec![out])?;
                }
            }
        }

        Ok(out)
    }
}

Le fonctionnement est le suivant :

1. On initialise un itérateur vide.
2. On itère sur chaque étape du plan.
3. Pour chaque étape, on exécutera :
   1. Si l’étape est une scan, on l’exécutera et on mettra à jour l’itérateur (out).
   2. Si l’étape est un filtre, on l’exécutera avec l’itérateur (out) comme entrée et on mettra à jour l’itérateur (out).

Et on renverra l’itérateur contenant les résultats de la dernière étape.

A noter que même à l’issue de la dernière étape, aucune lecture n’a encore eu lieu.

Nous avons simplement défini des itérateurs imbriqués les uns des autres.

Mais tant que l’itérateur n’est pas consommé, aucun accès à la base de données ne sera fait.

Adaptation de la méthode select de la base de données

Nous devons également adapter la méthode select de la base de données pour la faire utiliser notre plan executor.

impl Database {
    pub fn select(
        &mut self,
        table_name: String,
        where_clause: Option<WhereClause>,
        explain: bool,
    ) -> Result<ExecuteResult, SelectError> {
        let expression = where_clause
            .as_ref()
            .map(|where_clause| &where_clause.expression);
        // Create the planner
        let query_planner = QueryPlanner::new(self, &table_name, expression);
        let mut plan = Plan::new();
        // Plan the query
        query_planner.plan(&mut plan).map_err(SelectError::Query)?;
        // Display the plan and return if in explain mode
        if explain {
            return Ok(ExecuteResult::Explain(plan));
        }
        // Declare the plan executor
        let plan_executor = PlanExecutor::new(self, plan);
        // Execute the plan
        let rows = plan_executor.exec()?;
        // Return the final iterator
        Ok(ExecuteResult::Tuples(rows))
    }
}

Le fonctionnement est le suivant :

1. On crée un plan executor avec la base de données et le plan.
2. On exécute le plan et on renvoie l’itérateur contenant les résultats.

Adaptation de la déclaration de table

Nous avons transformé nos index primaires en index “classique”, il faut donc faire une petite adaptation.

Précédemment nous avons défini la structure de la table comme suit.

pub struct Table {
    table_name: String,
    schema: Schema,
    row_number: usize,
    primary_indexes: Index<usize>, // 👈 index primaires précédents
    pager: Pager,
    indexes: IndexRegistry,
}

Les index primaires étaient séparés des autres index.

Nous allons les stocker de manière naturelle dans l’IndexRegistry.

struct Table {
    /// Name of the table
    table_name: String,
    /// Schema of the table
    schema: Schema,
    /// Max ever row number
    row_number: usize,
    /// Page manager
    pager: Pager,
    /// Index registry
    indexes: IndexRegistry,
}

On adapte le constructeur en conséquence.

impl Table {
    pub fn new(schema: Schema, table_name: String) -> Self {
        // instanciation de l'index registry
        let mut indexes = IndexRegistry::default();
        // création de l'index primaire
        let primary_index = PrimaryIndex::new(table_name.clone(), schema.primary_key.clone());
        // ajout de l'index primaire
        indexes.add_primary_index(primary_index);

        Table {
            pager: Pager::new(schema.size()),
            schema,
            row_number: 0,
            indexes,
            table_name,
        }
    }
}

Et on modifie le processus d’insertion.

impl Table {
    pub fn insert(&mut self, row: HashMap<String, Value>) -> Result<(), InsertionError> {
        // récupération de la slice de données stockée par la page du tuple
        let page = self.pager.write(self.row_number);

        let mut writer = Cursor::new(page);
        // appel à la sérialisation au travers du schéma
        // la vérification est également faite à ce moment

        let row = self
            .schema
            .prepare_values(row)
            .map_err(InsertionError::Serialization)?;

        // on vérifie que les données à indexer sont cohérentes
        self.indexes
            .check(&row)
            .map_err(InsertionError::IndexError)?;

        // insertion des données
        self.schema
            .serialize(&mut writer, &row)
            .map_err(InsertionError::Serialization)?;

        // insersion des indexes
        self.indexes
            .insert_into_index(&row, self.row_number)
            .map_err(InsertionError::IndexError)?;

        // incrémentation de l'ID interne
        self.row_number += 1;

        Ok(())
    }
}

La différence étant qu’il n’y a plus d’indexation primaire explicite, l’indexation par clé primaire est directement gérée par l’IndexRegistry. 🤩

On a fini !

Tout est en place, il est maintenant temps de tester.

Toute ressemblance avec la partie précedente est purement fortuite.

Voici notre déclaration de 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');

Le plan logique va être le suivant:

db > EXPLAIN SELECT * FROM Client WHERE ville = 'Tokyo';
Scan index idx_ville : ville = 'Tokyo' for table Client
Filter: ville = 'Tokyo'

Et lorsque l’on exécute sans le EXPLAIN, on obitient.

db > SELECT * FROM Client WHERE ville = 'Tokyo';         
Ok([Integer(3), Text("Haddad"), Text("Karim (كريم)"), Text("M"), Text("Tokyo")])
Ok([Integer(10), Text("Dubois"), Text("Paul"), Text("M"), Text("Tokyo")])

Ce qui est le résultat attendu !

Nous sommes donc capable d’utiliser les index secondaoires non-uniques pour récupérer nos entrés.

Voyons par accès par clef primaires.

db > EXPLAIN SELECT * FROM Client  WHERE id = 7 and ville = 'Paris';
Scan index PRIMARY : id = 7 for table Client
Filter: ville = 'Paris' AND id = 7

Sans EXPLAIN, on obtient.

db > EXPLAIN SELECT * FROM Client  WHERE id = 7 and ville = 'Paris';

Rien ! Et c’est normal.

Personne n’habite à Paris et n’a l’id 7.

Par contre si on enlève le fitre de ville, on obtient.

db > EXPLAIN SELECT * FROM Client  WHERE id = 7;
Scan index PRIMARY : id = 7 for table Client
Filter: id = 7
db > SELECT * FROM Client  WHERE id = 7;
Ok([Integer(7), Text("Smith"), Text("Emily"), Text("F"), Text("Osaka")])

Et là nous sommes contents! 😇

Si la données n’est indexé nulle part, on va lire chaque entrée de la table.

db > EXPLAIN SELECT * FROM Client WHERE genre = 'F';
Full scan Client
Filter: genre = 'F'

db > SELECT * FROM Client WHERE genre = 'F';         
Ok([Integer(2), Text("Martin"), Text("Marie"), Text("F"), Text("New York")])
Ok([Integer(4), Text("Dubois"), Text("Sophie"), Text("F"), Text("Beyrouth")])
Ok([Integer(6), Text("Yamamoto"), Text("Sakura (さくら)"), Text("F"), Text("Paris")])
Ok([Integer(7), Text("Smith"), Text("Emily"), Text("F"), Text("Osaka")])
Ok([Integer(9), Text("Haddad"), Text("Layla (ليلى)"), Text("F"), Text("New York")])

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

db > SELECT * FROM Client;                   
Ok([Integer(1), Text("Smith"), Text("John"), Text("M"), Text("Paris")])
Ok([Integer(2), Text("Martin"), Text("Marie"), Text("F"), Text("New York")])
Ok([Integer(3), Text("Haddad"), Text("Karim (كريم)"), Text("M"), Text("Tokyo")])
Ok([Integer(4), Text("Dubois"), Text("Sophie"), Text("F"), Text("Beyrouth")])
Ok([Integer(5), Text("Tanaka"), Text("Hiroshi (ひろし)"), Text("M"), Text("Beyrouth")])
Ok([Integer(6), Text("Yamamoto"), Text("Sakura (さくら)"), Text("F"), Text("Paris")])
Ok([Integer(7), Text("Smith"), Text("Emily"), Text("F"), Text("Osaka")])
Ok([Integer(8), Text("Martin"), Text("Jean"), Text("M"), Text("Lyon")])
Ok([Integer(9), Text("Haddad"), Text("Layla (ليلى)"), Text("F"), Text("New York")])
Ok([Integer(10), Text("Dubois"), Text("Paul"), Text("M"), Text("Tokyo")])

Et voilà, nous avons un système de recherche de données optimisé par index !! 🎉

Conclusion

Et bien, c’était un gros morceau ! On a passé un temps non négligeable sur les index, alors que le titre de l’article était “Exécution du plan logique”, mais c’était essentiel.

Une base de données sans index performant est totalement inutilisable.

Or notre plan se base totalement sur les index pour éviter les full-scans.

Le deuxième axe qui nous a occupé une belle partie est la transformation de notre système de récupération de données par recopie et allocation vers un modèle “lazy” via l’utilisation d’itérateurs.

Cette optimisation permet à notre base de données de ne plus être dépendante de la taille de la table qui est lue !

Le système d’itérateurs imbriqués permet de donner la responsabilité à une étape du plan de lire ou non de la donnée. Ce système va être essentiel lorsque l’on abordera la jointure de tables.

Dans la prochaine partie, nous verrons comment supprimer de la donnée.

Merci de votre lecture ❤️

Vous pouvez trouver le code la partie ici et le diff là.