Table des matières

• Modification de la Where Clause
  • Adaptation du Parser
  • Adaptation de Table
• Méthode run de la Database
• Scanner
• Filtrage
• Scan
• On teste!
• Conclusion

Bonjour à toutes et tous 😃

Nous avons défini la grammaire d’Expression qui défini des expressions logiques permettant d’appliquer des contraintes sur des tuples.

Il est temps de mettre en place ce qu’il faut pour requêter plus intelligement notre base de données.

Pour rappel, notre table a ce schéma.

CREATE TABLE PhoneBook(name TEXT(50) PRIMARY KEY, city TEXT(50), phone_number TEXT(50), gender TEXT(1));

Que l’on peut remplir avec des entrées de ce type:

INSERT INTO PhoneBook (name, city, phone_number, gender) VALUES ('Amelie Dupont', 'Paris', '+33612345679', 'F');
INSERT INTO PhoneBook (name, city, phone_number, gender) VALUES ('Fatima Benkacem', 'Paris', '+33634567890', 'F');
INSERT INTO PhoneBook (name, city, phone_number, gender) VALUES ('Claire Nguyen', 'Paris', '+33628345678', 'F');
INSERT INTO PhoneBook (name, city, phone_number, gender) VALUES ('Jean-Pierre Durand', 'Lyon', '+33658466789', 'M');
INSERT INTO PhoneBook (name, city, phone_number, gender) VALUES ('Omar Traore', 'Marseille', '+33692345678', 'M');
INSERT INTO PhoneBook (name, city, phone_number, gender) VALUES ('Sofia Martins', 'Nice', '+33678432109', 'F');
INSERT INTO PhoneBook (name, city, phone_number, gender) VALUES ('Theo Garnier', 'Bordeaux', '+33643215678', 'M');
INSERT INTO PhoneBook (name, city, phone_number, gender) VALUES ('Aicha Diallo', 'Strasbourg', '+33654987654', 'F');
INSERT INTO PhoneBook (name, city, phone_number, gender) VALUES ('Camille Morel', 'Toulouse', '+33681234567', 'F');
INSERT INTO PhoneBook (name, city, phone_number, gender) VALUES ('Victor Lefevre', 'Lille', '+33612345678', 'M');

Et à la fin de l’article on pourra les requêter ainsi. 😃

SELECT * FROM PhoneBook WHERE city = 'Paris' AND gender = 'F';

Mais la route va être longue. C’est partie ! 😎

Modification de la Where Clause

Nous avons introduit la Where Clause lors d’un précédent article.

struct WhereClause {
    field: String,
    value: Value,
}

Notre première tâche va être de modifier ce système simpliste qui ne gère que des requêtes du type id = 12, nous voulons généraliser tout ça, et ça tombe bien nos expressions font exactement ça. La vie est bien faite quand même. 😇

pub struct WhereClause {
    expression: Expression,
}

Adaptation du Parser

Notre Visiteur de Expression rend le parse évident.

impl<'a> Visitable<'a, u8> for WhereClause {
    fn accept(scanner: &mut Scanner<'a, u8>) -> crate::parser::Result<Self> {
        scanner.visit::<OptionalWhitespaces>()?;
        recognize(Token::Where, scanner)?;
        scanner.visit::<Whitespaces>()?;
        // 👇 on remplace le parse du field et de la value par celui de l'Expression
        let expression = scanner.visit::<Expression>()?;
        Ok(Self { expression })
    }
}

Ce qui nous les résultats suivants.

#[test]
fn test_where_clause() {
    let mut scanner = Scanner::new(b"WHERE id = 42");
    let where_clause = scanner.visit::<WhereClause>().unwrap();
    assert_eq!(
        where_clause,
        WhereClause {
            expression: Expression::Column(ColumnExpression::new(
                Column("id".to_string()),
                BinaryOperator::Equal,
                Value::Integer(42)
            ))
        }
    );
}

#[test]
fn test_where_logical_clause() {
    let mut scanner = Scanner::new(b"WHERE id = 42 AND name = 'Max'");
    let where_clause = scanner.visit::<WhereClause>().unwrap();

    let lhs = Expression::Column(ColumnExpression::new(
        Column("id".to_string()),
        BinaryOperator::Equal,
        Value::Integer(42),
    ));

    let rhs = Expression::Column(ColumnExpression::new(
        Column("name".to_string()),
        BinaryOperator::Equal,
        Value::Text("Max".to_string()),
    ));

    assert_eq!(
        where_clause,
        WhereClause {
            expression: Expression::Logical(LogicalExpression {
                lhs: Box::new(lhs),
                operator: LogicalOperator::And,
                rhs: Box::new(rhs),
            })
        }
    );
}

Une bonne chose de faite ! 😃

Adaptation de Table

Notre table doit également être modifié, celle-ci étant adapté pout l’ancienne WhereClause.

Notre vieux code

impl Table {
    pub fn select(
        &self,
        where_clause: Option<WhereClause>,
    ) -> Result<Vec<Vec<Value>>, SelectError> {
        // instanciation du Query Engine pour la table
        let engine = QueryEngine::new(self);

        match where_clause {
            None => engine.full_scan(),
            // sinon si la clause where concerne la clef primaire
            Some(WhereClause { field, value })
                if self.schema.primary_key == vec![field.clone()] =>
            {
                // on récupère l'entrée désignée
                engine.get_by_pk(&vec![value], &self.primary_indexes)
            }
            /// on jette tout ce qui n'est pas une demande direct par clef primaire
            _ => Err(SelectError::NotImplemented),
        }
    }
}

Devient

impl Table {
    pub fn select(
        &self,
        where_clause: Option<WhereClause>,
    ) -> Result<Vec<Vec<Value>>, SelectError> {
        // instanciation du Query Engine pour la table
        let engine = QueryEngine::new(self);

        match where_clause {
            // s'il n'y a pas de clause where on scan tout
            None => engine.full_scan(),
            // sinon on est un peu plus malin
            Some(WhereClause { expression }) => match expression {
                // si la clause where concerne la clef primaire
                Expression::Column(ColumnExpression {
                    column,
                    operator,
                    value,
                }) if vec![column.0.to_string()] == self.schema.primary_key
                    && operator == BinaryOperator::Equal =>
                {
                    // on scan par PK
                    engine.get_by_pk(&vec![value], &self.primary_indexes)
                }
                // on introduit une nouvelle méthode 'scan' qui prend l'expression en paramètre
                expression => engine.scan(&expression),
            },
        }
    }
}

Nous verrons par la suite comment définir la méthode scan.

Méthode run de la Database

Pour faciliter nos tests, nous allons définir une méthode run qui va nous permettre de d’éviter de devoir écrire l’AST de la requête (qui va commencer à devenir complexe 😅).

On créé une énumération des résultats des requêtes.

enum ExecuteResult {
    // pas de retour
    Nil,
    // une liste de tuples
    Tuples(Vec<Vec<Value>>),
}

On modifie le trait Execute pour y inclure notre ExecuteResult.

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

Et par effet domino, on modifie les Execute de nos commandes

impl Execute for CreateTableCommand {
    fn execute(self, database: &mut Database) -> Result<ExecuteResult, ExecutionError> {
        let CreateTableCommand { schema, table_name } = self;
        database
            .create_table(table_name, schema)
            .map(|_| ExecuteResult::Nil)
            .map_err(ExecutionError::Create)
    }
}

impl Execute for InsertIntoCommand {
    fn execute(self, database: &mut Database) -> Result<ExecuteResult, ExecutionError> {
        let InsertIntoCommand { table_name, fields } = self;
        database
            .insert(table_name, fields)
            .map_err(ExecutionError::Insertion)
            .map(|_| ExecuteResult::Nil)
    }
}

impl Execute for SelectCommand {
    fn execute(self, database: &mut Database) -> Result<ExecuteResult, ExecutionError> {
        let SelectCommand {
            table_name,
            where_clause,
            ..
        } = self;
        database
            .select(table_name, where_clause)
            .map_err(ExecutionError::Select)
            .map(ExecuteResult::Tuples)
    }
}

impl Execute for Command<'_> {
    fn execute(self, database: &mut Database) -> Result<ExecuteResult, ExecutionError> {
        match self {
            Command::Meta(command) => command.execute(database),
            Command::Sql(command) => command.execute(database),
            Command::Unknown { command } => Err(ExecutionError::Command(
                CommandError::UnknownCommand(command.to_string()),
            )),
        }
    }
}

Ce qui permet de définir la méthode run.

impl Database {
    pub fn run(&mut self, command: &str) -> Result<ExecuteResult, ExecutionError> {
        parse(command)
            .map_err(ExecutionError::Command)?
            .execute(self)
    }
}

On modifie également le point d’entré de l’application pour afficher les résultats du ExecuteResult

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::Nil) => {}
            Err(err) => {
                println!("{}", err);
            }
        }
    }
}

Parfait, nous allons pouvoir faire des choses bien plus pratiquement désormais. 😎

Scanner

Notre méthode bien que fonctionnel, est un peu limitée.

Nous allons remédier à ça en transformant notre processus itératif de scan

impl QueryEngine<'_> {
    pub fn full_scan(&self, row_number: usize) -> Result<Vec<Vec<Value>>, SelectError> {
        let mut rows = Vec::with_capacity(row_number);
        for row_number in 0..row_number {
            let page = self
                .table
                .pager
                .read(row_number)
                .ok_or(SelectError::PageNotExist(row_number))?;
            let mut reader = Cursor::new(page);
            rows.push(
                // désérialisation par le schéma
                self.table
                    .schema
                    .deserialize(&mut reader)
                    .map_err(SelectError::Deserialization)?,
            )
        }
        Ok(rows)
    }
}

En itérateur:

impl QueryEngine<'_> {
    pub fn full_scan(&self) -> Result<Vec<Vec<Value>>, SelectError> {
        Scanner::new(self.table).collect()
    }
}

Même s’il possède le même nom que celui du Parser, ce Scanner n’est pas le même.

Le voici, il prend une référence de Table.

Le current_row aura pour rôle de garder en mémoire les tuples déjà lu.

pub struct Scanner<'a> {
    table: &'a Table,
    current_row: usize,
}

impl<'a> Scanner<'a> {
    pub fn new(table: &'a Table) -> Self {
        Self {
            table,
            current_row: 0,
        }
    }
}

On déplace alors notre code itératif dans l’implémentation de l’Iterator pour Scanner.

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.table.row_number {
            return None;
        }
        // on récupère le morceau de page contenant le tuple
        let page = self
            .table
            .pager
            .read(self.current_row)
            .ok_or(SelectError::PageNotExist(self.current_row));

        // early return
        let page = match page {
            Err(e) => return Some(Err(e)),
            Ok(page) => page,
        };

        // on désérialise le tuple
        let mut reader = Cursor::new(page);
        match self
            .table
            .schema
            .deserialize(&mut reader)
            .map_err(SelectError::Deserialization)
        {
            Ok(row) => {
                self.current_row += 1;
                Some(Ok(row))
            }
            Err(err) => Some(Err(err)),
        }
    }
}

On rajoute également un squelette de méthode scan.

impl QueryEngine<'_> {
    pub fn full_scan(&self) -> Result<Vec<Vec<Value>>, SelectError> {
        Scanner::new(self.table).collect()
    }

    pub fn scan(&self, expression: &Expression) {
        todo!()
    }
}

A partir de ce moment, notre full scan refonctionne correctement.

#[test]
fn test_full_scan() {
    let mut database = Database::new();

    database
        .run("CREATE TABLE Users (id INTEGER PRIMARY KEY, name TEXT(50), email TEXT(128));")
        .expect("create table failed");

    for i in 0..1000 {
        database
            .run(&format!(
                "INSERT INTO Users (id, name, email) VALUES ({i}, 'test_{i}', 'email_{i}@example.com');",
            ))
            .expect("insert user failed");
    }

    match database.run("SELECT * FROM Users;") {
        Ok(ExecuteResult::Tuples(rows)) => {
            assert_eq!(rows.len(), 1000);
            for (i, row) in rows.iter().enumerate() {
                let expected = vec![
                    Value::Integer(i as i64),
                    Value::Text(format!("test_{i}")),
                    Value::Text(format!("email_{i}@example.com")),
                ];
                let row = row.to_vec();

                assert_eq!(row, expected);
            }
        }
        _ => panic!("select failed"),
    }
}

Filtrage

L’enchâssement des Expression qui peuvent contenir des sous expressions peut sembler intimidant au premier abord, mais dans les faits, il suffit de suivre la récursion que l’on a appliqué lors du parse.

On démarre d’une Expression et on en détermine si on est dans le cas simple à une colonne.

Si on est dans le cas d’une expression logique, alors il faut décoposer les groupe en deux expression et appliquer l’opérateur logique entre les résultats.

Les grands discours ont perdu la France, plutôt que de décoomposer tout, voici le code commenté.

fn filter_row(
    row: &Vec<Value>,
    expression: &Expression,
    schema: &Schema,
) -> Result<bool, QueryError> {
    match expression {
        // l'expression est un groupe logique
        Expression::Logical(logical_expression) => {
            // on appel récursivement la méthode filter_row sur l'expression de gauche du groupe
            let lhs = filter_row(row, &logical_expression.lhs, schema)?;
            // et de droite également
            let rhs = filter_row(row, &logical_expression.rhs, schema)?;
            // puis on réconcillie les résultats
            match logical_expression.operator {
                // soit avec un OU logique
                LogicalOperator::Or => Ok(lhs || rhs),
                // soit un ET logique
                LogicalOperator::And => Ok(lhs && rhs),
            }
        }
        // l'expression ne concerne qu'une colonne, on peut en faire
        // un traitement
        Expression::Column(column_expression) => {
            // on récupère le nom de la colonne
            let column_name = &column_expression.column.0;
            // son index dans le tuple
            let col_idx = schema
                .column_indexes
                .get(column_name)
                .ok_or(QueryError::UnknownColumn(column_name.to_string()))?;
            // ce qui nous donne la valeur de l'attribut
            let value = &row[*col_idx];
            // on récupère également la définition de cette colonne dans le schéma
            let column_type = &schema
                .fields
                .get(column_name)
                .ok_or(QueryError::UnknownColumn(column_name.to_string()))?
                .column_type;

            match column_type {
                // si l'attribut est un entier, toutes les comparaisons sont possibles
                ColumnType::Integer => match column_expression.operator {
                    BinaryOperator::GreaterThanOrEqual => Ok(*value >= column_expression.value),
                    BinaryOperator::LessThanOrEqual => Ok(*value <= column_expression.value),
                    BinaryOperator::GreaterThan => Ok(*value > column_expression.value),
                    BinaryOperator::LessThan => Ok(*value < column_expression.value),
                    BinaryOperator::Equal => Ok(*value == column_expression.value),
                    BinaryOperator::Different => Ok(*value != column_expression.value),
                },
                // si l'attribut est du texte, on restreint à l'égalité ou l'inégalité
                ColumnType::Text(_) => match column_expression.operator {
                    BinaryOperator::Equal => Ok(*value == column_expression.value),
                    BinaryOperator::Different => Ok(*value != column_expression.value),
                    _ => Err(QueryError::InvalidOperator),
                },
            }
        }
    }
}

Scan

Maintenant que nous avons le moyen de filtrer un tuple par rapport à une expression, nous pouvons impléménter la méthode scan du QueryEngine.

Notre Scanner étant un itérateur, on possède gratuitement toutes les méthodes de celui-ci, dont filter_map.

filter_row renvoie un booléen en fonction d’une expression et d’un tuple.

On rassemble le tout et ça nous donne:

impl QueryEngine<'_> {
    pub fn full_scan(&self) -> Result<Vec<Vec<Value>>, SelectError> {
        Scanner::new(self.table).collect()
    }

    pub fn scan(&self, expression: &Expression) -> Result<Vec<Vec<Value>>, SelectError> {
        Scanner::new(self.table)
            .filter_map(|row| match row {
                Ok(row) => match filter_row(&row, expression, &self.table.schema) {
                    // le tuple correspond au prédicat 
                    Ok(true) => Some(Ok(row)),
                    // le tuple ne correspond pas au prédicat
                    Ok(false) => None,
                    // propagation de l'erreur de fitrage
                    Err(err) => Some(Err(SelectError::Query(err))),
                },
                Err(err) => Some(Err(err)),
            })
            .collect()
    }
}

On peut alors scanner et filter sur une même requête.

#[test]
fn test_select_with_logical_expression() {
    let mut database = Database::new();

    database
        .run("CREATE TABLE Users (id INTEGER PRIMARY KEY, name TEXT(50), gender TEXT(1));")
        .expect("create table failed");

    for i in 0..1000 {
        let gender = if i % 2 == 0 { "M" } else { "F" };

        database
            .run(&format!(
                "INSERT INTO Users (id, name, gender) VALUES ({i}, 'test_{i}', '{gender}');",
            ))
            .expect("insert user failed");
    }

    let result =
        database.run("SELECT * FROM Users WHERE gender = 'M' AND id >= 100 AND id < 200;");
    match result {
        Ok(ExecuteResult::Tuples(rows)) => {
            assert_eq!(rows.len(), 50);
            let mut iterator = rows.iter();
            for i in (100..200).step_by(2) {
                let expected = vec![
                    Value::Integer(i as i64),
                    Value::Text(format!("test_{i}")),
                    Value::Text("M".to_string()),
                ];
                let row = iterator.next().expect("missing row");
                assert_eq!(row, &expected);
            }
        }
        _ => panic!("select failed"),
    }
}

Comme vous pouvez l’observer, un même champ peut être réutilisé plusieurs fois dans l’expression pour réaliser un encadrement.

On teste!

Revenons à nos moutons de l’introduction.

On créé la table de notre magnifique botin

CREATE TABLE PhoneBook(name TEXT(50) PRIMARY KEY, city TEXT(50), phone_number TEXT(50), gender TEXT(1));

On rajoute des entrées dedans

INSERT INTO PhoneBook (name, city, phone_number, gender) VALUES ('Amelie Dupont', 'Paris', '+33612345679', 'F');
INSERT INTO PhoneBook (name, city, phone_number, gender) VALUES ('Fatima Benkacem', 'Paris', '+33634567890', 'F');
INSERT INTO PhoneBook (name, city, phone_number, gender) VALUES ('Claire Nguyen', 'Paris', '+33628345678', 'F');
INSERT INTO PhoneBook (name, city, phone_number, gender) VALUES ('Jean-Pierre Durand', 'Lyon', '+33658466789', 'M');
INSERT INTO PhoneBook (name, city, phone_number, gender) VALUES ('Omar Traore', 'Marseille', '+33692345678', 'M');
INSERT INTO PhoneBook (name, city, phone_number, gender) VALUES ('Sofia Martins', 'Nice', '+33678432109', 'F');
INSERT INTO PhoneBook (name, city, phone_number, gender) VALUES ('Theo Garnier', 'Bordeaux', '+33643215678', 'M');
INSERT INTO PhoneBook (name, city, phone_number, gender) VALUES ('Aicha Diallo', 'Strasbourg', '+33654987654', 'F');
INSERT INTO PhoneBook (name, city, phone_number, gender) VALUES ('Camille Morel', 'Toulouse', '+33681234567', 'X');
INSERT INTO PhoneBook (name, city, phone_number, gender) VALUES ('Victor Lefevre', 'Lille', '+33612345678', 'M');

Et on requête le tout !

SELECT * FROM PhoneBook WHERE city = 'Paris' AND gender = 'F';
[Text("Amelie Dupont"), Text("Paris"), Text("+33612345679"), Text("F")]
[Text("Fatima Benkacem"), Text("Paris"), Text("+33634567890"), Text("F")]
[Text("Claire Nguyen"), Text("Paris"), Text("+33628345678"), Text("F")]

Et paf un annuaire un ! 🤩

Conclusion

Le système de requêtage est rudimentaire mais fonctionnel.

Les itérateurs sur les scans vont être une pièce essentiel dans notre query engine lorsque nous attaqueront le modèle volcan.

Mais chaque chose en son temps.

Dans la prochaine partie qui sera une récréation, nous allons rajouter le support de l’UTF-8 à nos valeur.

Merci de votre lecture ❤️

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