Table des matières

• Parser
• Propagation du EXPLAIN
• Conclusion

Bonjour à toutes et tous 😃

Par l’introduction des index secondaires, nous avons ouvert tout un champ des possibles sur de la recherche de données plus efficiente. Mais nous n’avons vraiment parcouru que la moitié du chemin: nous savons indexer, mais pas rechercher dans cet index.

Afin de permettre de comprendre quand le query engine décide ou non de décider de l’utilisation des index secondaires. Nous allons introduire un modificateur d’exécution que nous allons appeler EXPLAIN. Ce sera notre mode de debug pour bâtir des systèmes plus intelligents et complexes.

On a encore bien du pain sur la planche, mais au bout de 16 articles et je ne sais combien de millier de lignes de codes expliquées, vous commencez à prendre l’habitude. 😅

Parser

Tout commence par bâtir un parser pour détecter notre modificateur d’exécution.

Nous décidons que si le premier token est EXPLAIN, alors la commande doit-être debugguée.

EXPLAIN SELECT ...

Nous devons ainsi reconnaître le token EXPLAIN.

enum Token {
    /// EXPLAIN token
    Explain,
}

La structure reconnue est un peu étrange

struct Explain(usize);

Le usize représentera le nombre de bytes consommée pour parser le “EXPLAIN” s’il existe.

impl<'a> Visitable<'a, u8> for Explain {
    fn accept(scanner: &mut Scanner<'a, u8>) -> crate::parser::Result<Self> {
        let cursor = scanner.cursor();
        scanner.visit::<OptionalWhitespaces>()?;
        recognize(Token::Explain, scanner)?;
        scanner.visit::<OptionalWhitespaces>()?;
        let delta = scanner.cursor() - cursor;
        Ok(Self(delta))
    }
}

On est désormais en capacité de détecter notre nouveau modificateur.

#[test]
fn test_explain() {
    let data = b"EXPLAIN SELECT * FROM table";
    let mut tokenizer = Tokenizer::new(data);
    let result = tokenizer.visit();
    // 8 bytes incluant l'espace blanc après EXPLAIN
    assert_eq!(result, Ok(Explain(8)));
}

#[test]
fn test_explain_fail() {
    let data = b"SELECT * FROM table";
    let mut tokenizer = Tokenizer::new(data);
    let result = tokenizer.visit::<Explain>();
    // non reconnu
    assert!(result.is_err());
}

On réalise également un utilitaire qui reconnaît directement notre modificateur.

pub fn detect_explain(scanner: &str) -> Option<usize> {
    let mut scanner = Scanner::new(scanner.as_bytes());
    scanner.visit::<Explain>().ok().map(|Explain(size)| size)
}

Propagation du EXPLAIN

Une fois le modificateur EXPLAIN détectée ou non, il faut le propager dans l’exécution.

Etant donné que le modificateur induit un comportement différent, nous allons avoir deux types de retours:

• des résultat de commandes
• le résultat du EXPLAIN.

enum ExecuteResult {
    // la commande ne renvoie pas de réponse
    Nil,
    // la commande renvoie une liste de tuples
    Tuples(Vec<Vec<Value>>),
    // le résultat de EXPLAIN
    Explain(Vec<String>),
}

EXPLAIN va retourner une liste de détails. D’où le Vec<String>

Pour permettre à toutes les commandes de bénéficier du EXPLAIN, la détection est réalisée avant le parse de la commande elle-même.

impl Database {
    pub fn run(&mut self, command: &str) -> Result<ExecuteResult, ExecutionError> {
        // si la table master n'existe pas, la créer
        if !self.tables.contains_key(MASTER_TABLE_NAME) {
            let schema = "(type TEXT(10), name TEXT(50), tbl_name TEXT(50), sql TEXT(300), PRIMARY KEY (type, name, tbl_name));";
            // récupère le schéma
            let schema = schema_from_str(schema).map_err(ExecutionError::Parse)?;
            // création de la table master
            let master_table = Table::new(schema, MASTER_TABLE_NAME.to_string());
            // insertion de la table master à la base de données
            self.tables
                .insert(MASTER_TABLE_NAME.to_string(), master_table);
        }

        // active ou non le mode de "debug"
        let mut explain = false;
        // décale le curseur de début de parse
        let mut cursor = 0;

        // détection du potentiel modificateur EXPLAIN
        if let Some(explain_size) = detect_explain(command) {
            // si le modificateur existe, décaler le curseur d'autant que reconnu
            cursor = explain_size;
            // activer le flag de explain
            explain = true;
        }

        parse(&command[cursor..])
            .map_err(ExecutionError::Command)?
            .execute(self, explain)
    }
}

On modifie le trait Execute en rajoutant un flag booléen qui permet de passer l’exécution en “dry run” de debug ou non.

trait Execute {
    fn execute(
        self,
        database: &mut Database,
        explain: bool,
    ) -> Result<ExecuteResult, ExecutionError>;
}

Le flag est propagé, jusqu’à atteindre la base de données et sa méthode select.

impl Database {
     pub fn select(
        &mut self,
        table_name: String,
        where_clause: Option<WhereClause>,
        _explain: bool,
    ) -> Result<ExecuteResult, SelectError> {
        match self.tables.get(&table_name) {
            Some(table) => table.select(where_clause),
            None => Err(SelectError::TableNotExist(table_name))?,
        }
    }
}

Pour le moment, nous n’en ferons rien, mais ce n’est qu’une question de temps. 😄

Conclusion

L’article est court, mais va permettre de construire la suite plus simplement.

Dans la prochaine partie, nous allons attaquer le concept fondamental de la base de données qu’est le logical plan.

Merci de votre lecture ❤️

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