Partie 7 : Tuples de données

Bonjour à toutes et tous 😃

Depuis la partie 6 nous sommes capables de parser une commande une commande permettant de créer une table avec un schéma arbitraire, puis d'y insérer et finalement d'y récupérer des records.

Aujourd'hui nous allons généraliser les entités User et Car que nous avions utilisés comme placeholder pour simuler les opérations d'enregistrements et de lecture sans devoir se soucier des problématique de schémas.

Nous allons toujours pas nous occuper des schémas, mais par contre nous allons introduire le concept fondamental qui permettra de stocker de manière optimale des enregistrement et nous donnera de manière quasi gratuite la l'atomicité des update de colonnes.

Mais le chemin est encore long. 😅

On va commencer par déjà généraliser nos données stockées.

Tuples

Rappelez vous la commande d'insertion est réduite en une InsertIntoCommand, qui possède une map de Value

struct InsertIntoCommand {
    pub table_name: String,
    pub fields: HashMap<String, Value>,
}

Cette Value se décompe elle-même en deux variantes.

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

La question est alors:

Comment peut-on stocker cette énumération en base de données?

La réponse ne va pas vous défriser, il faut sérialiser, tout comme l'on avait fait avec User et Car.

Comme c'est une énumération, il faut qu'à la désérialisation on puisse recréer la bonne variante.

Pour cela on se créé une autre énumération qui va servir de discriminant à la désérialisation.

enum Discrimant {
    Integer = 0,
    Text,
}

impl TryFrom<u8> for Discrimant {
    type Error = DeserializationError;

    fn try_from(value: u8) -> Result<Self, Self::Error> {
        match value {
            0 => Ok(Discrimant::Integer),
            1 => Ok(Discrimant::Text),
            _ => Err(DeserializationError::EnumDiscriminant(value)),
        }
    }
}

On rajoute une erreur de désérialisation supplémentaire.

enum DeserializationError {
    Buffer(BufferError),
    UnableToDeserializeString(FromUtf8Error),
    // Ici 👇
    EnumDiscriminant(u8),
}

Maintenant on peut implémenter la sérialisation.

impl Serializable for Value {
    fn serialize(&self, cursor: &mut Cursor<&mut [u8]>) -> Result<(), SerializationError> {
        // on récupère le discrimnant
        let discriminant = match self {
            Value::Integer(_) => Discrimant::Integer,
            Value::Text(_) => Discrimant::Text,
        };

        // on stocke dans 1 byte le discriminant
        cursor
            .write_all(&[discriminant as u8])
            .map_err(|e| SerializationError::Buffer(BufferError::BufferFull(e.to_string())))?;

        // la données interne est alors sérialisée
        match self {
            Value::Integer(data) => data.serialize(cursor)?,
            Value::Text(data) => data.serialize(cursor)?,
        }

        Ok(())
    }
}

Et son complémentaire de désérialisation.

impl Deserializable for Value {
    fn deserialize(cursor: &mut Cursor<&[u8]>) -> Result<Self, DeserializationError> {
        // on lit le premier byte
        let mut discrimant = [0u8];
        cursor.read_exact(&mut discrimant).map_err(|err| {
            DeserializationError::Buffer(BufferError::ReadTooMuch(err.to_string()))
        })?;
        // que tente de convertir en un Discriminant
        let discriminant = Discrimant::try_from(discrimant[0])?;
        // puis on désérialise vers le bon type avant de wrap le résultat dans la variante
        match discriminant {
            Discrimant::Integer => i64::deserialize(cursor).map(Value::Integer),
            Discrimant::Text => String::deserialize(cursor).map(Value::Text),
        }
    }
}

Nous sommes désormais capables de sérialiser nos Value.

#[test]
fn test_serialize_deserialize_integer() {
    let value = Value::Integer(1);
    let mut buffer = [0u8; 1024];
    let mut writer = Cursor::new(&mut buffer[..]);
    value.serialize(&mut writer).unwrap();
    let mut reader = Cursor::new(&buffer[..]);
    let deserialized = Value::deserialize(&mut reader).unwrap();
    assert_eq!(value, deserialized);
}

#[test]
fn test_serialize_deserialize_text() {
    let value = Value::Text("texte de test".to_string());
    let mut buffer = [0u8; 1024];
    let mut writer = Cursor::new(&mut buffer[..]);
    value.serialize(&mut writer).unwrap();
    let mut reader = Cursor::new(&buffer[..]);
    let deserialized = Value::deserialize(&mut reader).unwrap();
    assert_eq!(value, deserialized);
}

Mais notre commande d'insertion comporte plusieurs valeurs. Ce n'est donc pas une Value mais un Vec<Value>.

Alors on pourrait implémenter Serializable sur Vec<Value>, mais on va se donner le luxe d'utiliser les outils de Rust et utiliser la blanket implementation.

On a exactement le même concept que pour l'énumération, à la désérialisation, il faut qu'on soit capable de déterminer combien d'élements sont constitutifs du Vec.

impl<T: Serializable> Serializable for Vec<T> {
    fn serialize(&self, cursor: &mut Cursor<&mut [u8]>) -> Result<(), SerializationError> {
        // on stocke dans le premier byte le nombre d'élements sérialisé
        cursor
            .write_all(&[self.len() as u8])
            .map_err(|err| SerializationError::Buffer(BufferError::BufferFull(err.to_string())))?;
        // on sérialise à la chaîne chaque valeur
        for item in self {
            item.serialize(cursor)?;
        }
        Ok(())
    }
}

La désérialisation n'est pas plus complexe.

impl<T: Deserializable> Deserializable for Vec<T> {
    fn deserialize(cursor: &mut Cursor<&[u8]>) -> Result<Self, DeserializationError> {
        // on lit le premier byte qui est la taille du Vec
        let mut size = [0u8; 1];
        cursor.read_exact(&mut size).map_err(|err| {
            DeserializationError::Buffer(BufferError::ReadTooMuch(err.to_string()))
        })?;
        let size = size[0] as usize;
        
        // on alloue suffisamment de place dans un Vec pour
        // accueillir les éléments
        let mut items = Vec::with_capacity(size);

        // on désérialise à la chaîne les N éléments du Vec
        for _ in 0..size {
            items.push(T::deserialize(cursor)?);
        }
        Ok(items)
    }
}

Et cette fois-ci on est bon ! 😎

#[test]
fn test_serialize_deserialize_tuple() {
    let tuple = vec![
        Value::Integer(1),
        Value::Text("John Doe".to_string()),
        Value::Text("john.doe@example.com".to_string()),
    ];

    let mut buffer = [0u8; 1024];
    let mut writer = Cursor::new(&mut buffer[..]);
    tuple.serialize(&mut writer).unwrap();
    let mut reader = Cursor::new(&buffer[..]);
    let deserialized = <Vec<Value>>::deserialize(&mut reader).unwrap();
    assert_eq!(tuple, deserialized);
}

Si on résume notre sérialisation, on se retrouve pour un [Integer(42), Text("test")] avec ceci en mémoire.

0x02         0x00      0x00 0x00 0x00 0x00 0x00 0x00 0x00 0xd6   0x01       0x04       0x74 0x65 0x73 0x74
^            ^         ^                                         ^          ^          ^
taille       D=Int     42 sur 8 bytes encodé en litte-endian     D=Text     taille     "test" encodé en UTF-8
du Vec                                                                      String

Cette structure de données sérialisée est notre Tuple.

Le format va radiacalement changer lorsque l'on introduira le schéma dans la sérialisation. Pour le moment nos données sont auto-porteuses du schéma mais on gâche des bytes à encoder des données pas forcément utile comme les tailles de vecteur, les tailles de string et les discriminants.

Sur des millions d'enregistrements, cela peut avoir un poids considérable !!

Nos entiers également prennent vraiment trop de place, on va également revoir leur stockage.

Intrduction du nouveau parser

Maintenant que l'on a notre tuple de données.

Modification de Table

Même si pour le moment nous n'allons pas réellement l'utiliser, nous allons préparer le terrain pour les futurs travaux.

Nous allons doter la table d'un Schéma, directement issu de la commande CreateTableCommand.

struct CreateTableCommand {
    pub table_name: String,
    pub schema: Schema,
}

Et on n'oublie de modifier le constructeur en conséquence.

struct Table {
    inner: Vec<u8>,
    schema: Schema,
    offset: usize,
    row_number: usize,
}

impl Table {
    pub fn new(schema: Schema) -> Self {
        Self {
            schema,
            inner: vec![0; TABLE_SIZE],
            offset: 0,
            row_number: 0,
        }
    }
}

Modification de Database

Prédémment pour identifier les tables dans la Database on se servait de l'énumération TableName.

enum TableName {
    User,
    Car,
}

Or celle-ci n'a plus de sens désormais car l'utilisateur à la création de la table la nomme comme il l'entend.

De même la notion de Record est complètement caduque et remplacée par le tuple Vec<Value>.

enum Record {
    User(User),
    Car(Car),
}

On modifie donc Database pour mapper non pas TableName mais une String à nos Table.

struct Database {
    tables: HashMap<String, Table>,
}

Cela a pour incidence de modifier les signature des fonctions en dessous.

impl Database {
    pub fn create_table(
        &mut self,
        // le nom de la table est arbitraire
        table_name: String,
        // le schéma est rajouté
        schema: Schema,
    ) -> Result<(), CreationError> {
        if self.tables.contains_key(&table_name) {
            return Err(CreationError::TableAlreadyExist(table_name));
        }
        self.tables.insert(table_name, Table::new(schema));
        Ok(())
    }

    pub fn insert(
        &mut self,
        // le nom de la table est désormais arbitraire
        table: String,
        // ce n'est plus un Record mais une map de Value
        data: HashMap<String, Value>,
    ) -> Result<(), InsertionError> {
        match self.tables.get_mut(&table) {
            Some(table) => {
                // on collecte les valeurs, on fera les check de schéma
                // plus tard
                let values = data.into_values().collect::<Vec<Value>>();
                table.insert(values)?;
            }
            None => {
                Err(InsertionError::TableNotExist(table))?;
            }
        }

        Ok(())
    }

    pub fn select(
        &mut self,
        // le nom de la table est désormais arbitraire 
        table_name: String
    ) -> Result<
            // le retour n'est plus un Vec<Record> mais un Vec<Vec<Value>>
            Vec<Vec<Value>>, 
            SelectError
        > {
        match self.tables.get(&table_name) {
            // on désérialise vers un Vec<Value> chaque enregistrement
            Some(table) => table.select::<Vec<Value>>(),
            None => Err(SelectError::TableNotExist(table_name))?,
        }
    }
}

Utilisation du nouveau parser

Pour rappel nous avons l'énumération Command comme suit

enum Command {
    CreateTable(create_table::CreateTableCommand),
    Select(select::SelectCommand),
    InsertInto(insert_into::InsertIntoCommand),
}

Ce Command est visitable. On peut donc en faire un parser en 2 lignes.

fn parse_sql_command(data: &[u8]) -> crate::parser::Result<Command> {
    let mut scanner = Scanner::new(data);
    Command::accept(&mut scanner)
}

On introduit une nouvelle CommandError

enum CommandError {
    /// Une erreur de parse est survenue
    Parse(ParseError),
}

On peut alors remplacer notre parser approximatif par quelque chose de bien plus puissant.

pub fn parse(input: &str) -> Result<Command, CommandError> {
    let input = input.trim_start();
    let command = if input.starts_with(".") {
        meta::MetaCommand::try_from_str(input)?.map(Command::Meta)
    } else {
        parse_sql_command(input.as_bytes())
            .map(|command| Some(Command::Sql(command)))
            .map_err(CommandError::Parse)?
    }
    .unwrap_or(Command::Unknown { command: input });
    Ok(command)
}

Implémentation des commandes

Il nous reste alors d'implémenter le trait Execute pour les différente commandes.

D'abord le CREATE TABLE.

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

Puis le INSERT INTO

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

Finalement SELECT FROM

impl Execute for SelectCommand {
    fn execute(self, database: &mut Database) -> Result<(), ExecutionError> {
        let SelectCommand { table_name, .. } = self;
        let rows = database
            .select(table_name)
            .map_err(ExecutionError::Select)?;
        for row in rows {
            // on affiche juste le tuple sans formattage avancé
            println!("{:?}", row);
        }
        Ok(())
    }
}

Tout ceci permettant de faire remonter l'exécution jusq'à la commande

impl Execute for Command {
    fn execute(self, database: &mut Database) -> Result<(), ExecutionError> {
        match self {
            Command::CreateTable(command) => command.execute(database),
            Command::Select(command) => command.execute(database),
            Command::InsertInto(command) => command.execute(database),
        }
    }
}

N'ayant pas modifié l'interface publique de notre API, nous avons déjà quelque chose de fonctionnel ! 😍

Petit tests

Ce que l'on pouvait faire avant, on peut toujours le faire.

db > CREATE TABLE Users (id INTEGER, name TEXT(50), email TEXT(128));
db > INSERT INTO Users(id, name, email) VALUES (1, 'John Doe', 'john.doe@example.com');
db > INSERT INTO Users(id, name, email) VALUES (2, 'Jane Doe', 'jane.doe@example.com'); 
db > SELECT * FROM Users;
[Text("john.doe@example.com"), Integer(1), Text("John Doe")]
[Text("Jane Doe"), Integer(2), Text("jane.doe@example.com")]

On voit que le tuple n'est pas dans le bon sens car le HashMap.values().collect() ne conserve pas l'ordre d'insertion. On remédiera au problème à l'introduction du schéma.

Et on peut désormais créer des tables arbitrairement nommées et avec un nombre et des types de champs eux aussi arbitraires.

db > CREATE TABLE Birds (name TEXT(50), specie TEXT(128));
db > INSERT INTO Birds(name, specie) VALUES ('titi', 'canary');  
db > INSERT INTO Birds(name, specie) VALUES ('Iago', 'parrot'); 
db > SELECT * FROM Birds;
[Text("canary"), Text("titi")]
[Text("Iago"), Text("parrot")]
db > 

On est pas mal quand même non ? 🤩

Conclusion

Notre implémentation du tuple est approximative, mais donne une bonne idée de l'API finale.

Dans la prochaine partie on mettra en place ce schéma tant désiré !

Merci de votre lecture ❤️

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

Auteur: Akanoa

Je découvre, j'apprends, je comprends et j'explique ce que j'ai compris dans ce blog.

Ce travail est sous licence CC BY-NC-SA 4.0.