Table des matières

• Null Table
• Ajout des Value::Null
• Modification du check_values
• Implémentation de la null table
• Modification de Schema
• Testons !
• Conclusion

Bonjour à toutes et tous 😃

Lorsque nous avons introduit les clef primaires, j’ai défini deux contraintes appliquable sur les colonnes.

• PRIMARY KEY
• NOT NULL

PRIMARY KEY on s’en est déjà occupé, NOT NULL par contre, on l’a laissé sur le bas côté.

Il est temps d’y remédier.

Le but va être de pouvoir insérer de la données sans définir toutes les colonnes systématiquement.

CREATE TABLE Users (id INTEGER NOT NULL PRIMARY KEY, name TEXT(50) NOT NULL, age INTEGER);
INSERT INTO Users (id, name, age) VALUES (1, 'Max', 20);
INSERT INTO Users (id, name) VALUES (2, 'Amy');

Let’s go !

Null Table

La pierre angulaire de notre système va être un concept que l’on nomme en informatique une null table.

Qu’est-ce que NULL, d’ailleurs ?

NULL matérialise le concept d’absence de données, pas un 0, pas un FALSE. Son absence.

Du coup stocker du vide, ça commence à être tendax, tout est des bytes, des 0 et des 1. On n’a pas de troisième état qui permet de définir le néant.

On va diviser pour mieux régner.

On va définir une table qui dire si oui ou non la données est présente ou pas.

Prenons un exemple avec un tableau d’entiers possédant une valeur NULL.

[1, NULL, 3]

Si on veut sérialiser ça, nous allons devoir faire un choix de représentation du NULL, je vais arbitrairement dire que c’est 0x0.

Ce qui nous donne.

0x1 0x0 0x2

Mais rien ne distingue pour le moment 0x0 d’un vrai 0 ou d’un NULL.

L’idée est de créer une table de vérité de nos données:

• 1 elle existe
• 0 non

Ce qui donne la table suivante:

[1, 0, 1]

Que l’on sérialise en

0x1 0x0 0x1    0x1 0x0 0x2
^              ^
null table     data

On peut alors utiliser le 0x0 de la null table pour déterminer si c’est du 0 ou du NULL.

Par contre, on double notre stockage. C’est pas tip-top.

Heureusement, nous n’avons pas exploré toutes les possibilités.

Lorsque l’on écrit 0x5

Ce qu’il faut lire c’est

0b101

Et donc un tableau de 1 et de 0.

On peut compactifier notre null table avec un simple nombre.

0b101          0x1 0x0 0x2
^              ^
null table     data

Question

Ok, mais comment à partir de 0x5 je suis sensé savoir que le deuxième élément des données est NULL ?

Et bien grâce à deux opérations binaires extrèmement optimisées par le CPU:

• le masque
• le décalage binaire

Le décalage binaire permet comme son nom l’indique de décaler un bit, il est symbolisé par << quand il décale vers la gauche.

0b001 << 1 = 0b010

Ici on décale à gauche notre bit.

Note

Dans les faits c’est une multiplication par 2^n

1 << 1 = 1 * 2   = 0b01 << 1   = 0b10  = 2
1 << 2 = 1 * 2^2 = 0b01 << 2   = 0b100 = 4

Mais contrairement à la puissance qui coûte très cher en CPU, décaler des bits est évident pour le CPU car directement câblé physiquement.

Le masque est également une opération câblée dans le CPU qui permet de vérifier que deux bit sont égaux.

On utilise pour ça une opération de ET représenté par &

   0b101
&  0b110
-----------
   0b100

On peut alors fusionner les deux opérations.

null_table & (1 << bit)

Si on reprend notre exemple, cela donne:

   0b101 // null_table
&  0b010 // 0b001 << 1
-----------
   0b000 = 0x0 

Par contre si on veut la première valeur

   0b101 // null_table
&  0b001 // 0b001 << 0
-----------
   0b001 = 0x1 

Ou la troisième

   0b101 // null_table
&  0b100 // 0b001 << 2
-----------
   0b100 = 0x4 

Et donc notre algo est:

null_table & (1 << bit) == 0

Question

Compris, mais un byte ne comporte que 8 bits, on fait comment si notre tuple a plus de 8 attributs?

Réponse courte, on utilise 2 nombres au lieu d’un! 😎

Réponse plus élaborée.

Pour ce set de data :

[NULL, 2, 3, NULL, 5, 6, 7, 8, 9, NULL]

On a 3 positions qui sont NULL:

• 0
• 3
• 9

Pour les position 0 et 3 pas de souci, c’est notre null-table classique : 0b01101111. Par contre la suite on la met où ?

Ben à la suite !

Le deuxième groupe de 8 attributs donne la null-table suivante: 0b01

On fusionne les deux.

Notre null-table complète est donc:

0b0101101111

Mais comme ça ne rentre pas dans notre sérialisation en byte, on scinde en deux.

0b01101111    0b01
^             ^
partition 0   partition 1

On va appeler chacun des groupe une partition.

Et donc si on sérialise

[NULL, 2, 3, NULL, 5, 6, 7, 8, 9, NULL]

Cela devient

0x6f 0x01      0x0 0x2 0x3 0x0 0x5 0x6 0x7 0x8 0x9 0x0
^              ^
null table     data

On fera difficilement plus compact. 😅

Question

Et avec ce tableau de 2 nombres, je fais comment pour savoir si l’attribut est null ou pas ?

Et bien, on sait que la partition fera forcément 1 octet, donc 8 bits.

Si on recherche le bit 12, il ne peut pas se retrouver dans la partition 0 qui ne va que jusqu’à l’index 7.

Donc pour trouver la partition, il suffit de diviser cet index par la taille de la partition ici 8.

partition = index / 8

Et pour trouver le bit qui doit être masqué on récupère le reste de la division par le modulo de cette division

bit = index % 8

Finalement il vient

partition = index / 8
bit = index % 8
null_table[partition] & (1 << bit) == 0 

Et là on a tout ! 😇

Ajout des Value::Null

Maintenant que nous avons bien théorisé tout cela, nous allons pouvoir nous attaquer à l’implémentation de la fonctionnalité.

Pour cela, nous allons rajouter une nouvelle variante à notre énumération Value.

#[derive(Debug, PartialEq, Ord, Eq, PartialOrd, Clone)]
pub enum Value {
    Integer(i64),
    Text(String),
    Null,
}

impl Serializable for Value {
    fn serialize(&self, cursor: &mut Cursor<&mut [u8]>) -> Result<usize, SerializationError> {
        let size = match self {
            Value::Integer(data) => data.serialize(cursor)?,
            Value::Text(data) => data.serialize(cursor)?,
            Value::Null => 0,
        };

        Ok(size)
    }
}

On en profite pour implémenter le Serializable pour la nouvelle variante.

Modification du check_values

Maintenant que nous avons défini notre Value::Null, nous allons améliorer notre méthode check_values qui a pour but de vérifier la conformité de la donnée.

On se rajoute pour l’occasion une nouvelle erreur.

#[derive(Debug, PartialEq)]
pub enum CheckColumnDefinitionError {
       NonNullableColumn {
        column_name: String,
    },
}

Celle-ci permet d’interdire une valeur d’être NULL si le schéma ne le permet pas.

impl Schema {
   pub fn check_values(&self, values: &HashMap<String, Value>) -> Result<(), CheckColumnDefinitionError> {
      // snip...
      for (key, value) in values.iter() {
         // snip ...

         // récupération de la contrainte Not Null si elle existe. 
         let non_nullable: bool = &self
               .fields
               .get(key)
               .ok_or(CheckColumnDefinitionError::UnknownColumn(key.to_string()))?
               .constraints
               .contains(&Constraint::NotNull);
         match (value, column_type.get_column_type()) {
            // si la valeur est NULL
            (Value::Null, _) => {
               // mais que le schéma interdit le NULL
               if *non_nullable {
                  return Err(CheckColumnDefinitionError::NonNullableColumn {
                     column_name: key.to_string(),
                  });
               }
            }
         }
      }
   }
}

Implémentation de la null table

Nous devons maintenant déterminer la null table associer au tuple de donnée.

/// Taille de la partition de la null table d'un octet
pub const PARTITION_SIZE: usize = 8;

fn values_to_null_table(values: &[&Value]) -> Vec<u8> {
   // pour chaque attribut
    let indexes = values
        .iter()
        .enumerate()
        .fold(vec![], |mut acc, (index, value)| {
            // récupérer la partition
            let partition = index / PARTITION_SIZE;
            // si la partition n'existe pas
            if acc.len() <= partition {
               // la créer
               acc.push(0);
            }
            // si la valeur n'est pas null
            // définir le bit à 1
            // par défaut le bit vaut 0
            if &Value::Null != *value {
               // bit = index % PARTITION_SIZE 
               acc[partition] |= 1 << (index % PARTITION_SIZE);
            }
            acc
        });

    indexes
}

Ce qui donne ce fonctionnement.

#[test]
fn test_values_to_null_table_with_12_values() {
   // Expected result with 12 values: 0b 00000110 11001101
   let values = vec![
      // chunk 0
      &Value::Integer(1), // 1
      &Value::Null,       // 0
      &Value::Integer(2), // 1
      &Value::Integer(3), // 1
      &Value::Null,       // 0
      &Value::Null,       // 0
      &Value::Integer(4), // 1
      &Value::Integer(5), // 1   => 0b11001101
      // chunk 1
      &Value::Null,       // 0
      &Value::Integer(6), // 1
      &Value::Integer(7), // 1
      &Value::Null,       // 0   => 0b00000110
   ];
   let result = values_to_null_table(&values);
   assert_eq!(result, vec![0b11001101, 0b00000110]);
}

La deuxième chose que l’on a besoin de définir est l’opération de détection de NULL value.

fn is_null(null_table: &[u8], index: usize) -> bool {
   let partition = index / PARTITION_SIZE;
   let bit = index % PARTITION_SIZE;

   null_table[partition] & (1 << bit) == 0
}

Et qui peut être utilisé de cette manière:

#[test]
fn test_is_null() {
    let values = vec![
        // chunk 0
        &Value::Integer(1), // 0
        &Value::Null,       // 1
        &Value::Integer(2), // 2
        &Value::Integer(3), // 3
        &Value::Null,       // 4
        &Value::Null,       // 5
        &Value::Integer(4), // 6
        &Value::Integer(5), // 7
        // chunk 1
        &Value::Null,       // 8
        &Value::Integer(6), // 9
        &Value::Integer(7), // 10
        &Value::Null,       // 11
    ];
    let def = (0..12)
        .map(|i| {
            (
                format!("field_{i}"),
                ColumnDefinition::new(ColumnType::Integer, vec![]),
            )
        })
        .collect::<Vec<_>>();
    let null_table = values_to_null_table(&values);
    assert!(!is_null(null_table.as_slice(), 0));
    assert!(is_null(null_table.as_slice(), 5));
    assert!(is_null(null_table.as_slice(), 8));
    assert!(!is_null(null_table.as_slice(), 10));
}

Et nous allons définir une dernière méthode qui à partir du schéma vient définir la taille de la null table de chaque tuple de la page.

Pour cela, on recherche le multiple de 8 supérieur ou égal au nombre d’attributs du tuple.

fn get_nullable_table_size(schema: &Schema) -> usize {
    let num_columns = schema.columns.len();
    // on vérifie l'alignement
    let alignement = num_columns % PARTITION_SIZE;
    // si c'est aligné c'est parfait
    if alignement == 0 {
        num_columns
    } else {
        // sinon on rajoute ce qu'il manque pour atteindre le multiple de 8
        num_columns + (PARTITION_SIZE - alignement)
    }
}

Cela donne:

#[test]
fn test_nullable_table_size() {
    let def = (0..5)
        .map(|i| {
            (
                format!("field_{i}"),
                ColumnDefinition::new(ColumnType::Integer, vec![]),
            )
        })
        .collect::<Vec<_>>();
    let schema = Schema::new(def, vec![]);
    let size = get_nullable_table_size(&schema);
    assert_eq!(size, 8);

    let def = (0..12)
        .map(|i| {
            (
                format!("field_{i}"),
                ColumnDefinition::new(ColumnType::Integer, vec![]),
            )
        })
        .collect::<Vec<_>>();
    let schema = Schema::new(def, vec![]);
    let size = get_nullable_table_size(&schema);
    assert_eq!(size, 16);

    let def = (0..18)
        .map(|i| {
            (
                format!("field_{i}"),
                ColumnDefinition::new(ColumnType::Integer, vec![]),
            )
        })
        .collect::<Vec<_>>();
    let schema = Schema::new(def, vec![]);
    let size = get_nullable_table_size(&schema);
    assert_eq!(size, 24);
}

Je me permets également de rajouter la possibilité de sérialiser du u8.

impl Serializable for u8 {
    fn serialize(
        &self,
        cursor: &mut std::io::Cursor<&mut [u8]>,
    ) -> Result<usize, SerializationError> {
        cursor
            .write(self.to_le_bytes().as_ref())
            .map_err(|e| SerializationError::Buffer(BufferError::BufferFull(e.to_string())))?;
        Ok(size_of::<u8>())
    }
}

impl Deserializable for u8 {
    type Output = u8;

    fn deserialize(cursor: &mut std::io::Cursor<&[u8]>) -> Result<Self, DeserializationError> {
        let mut data = [0_u8; size_of::<u8>()];
        cursor
            .read_exact(&mut data)
            .map_err(|e| DeserializationError::Buffer(BufferError::ReadTooMuch(e.to_string())))?;
        Ok(u8::from_le_bytes(data))
    }
}

Modification de Schema

La première chose à faire est de corriger la taille du tuple dans la page, en effet, il faut maintenant rajouter la null_table en plus.

impl Size for Schema {
    fn size(&self) -> usize {
        self.fields
            .values()
            .map(|column| column.get_column_type().size())
            .sum::<usize>()
            + get_nullable_table_size(self)
    }
}

Ensuite, il faut redéfinir la méthode de sérialisation des données en prenant en compte que certains champs ne seront pas présent.

Il faut alors définir et encoder la null_table.

Puis pour chaque attribut, si la valeur est null, ne rien sérialiser du tout, sinon sérialiser la donnée.

impl Schema {
    pub fn serialize(
        &self,
        cursor: &mut Cursor<&mut [u8]>,
        mut values: HashMap<String, Value>,
    ) -> Result<(), SerializationError> {
        // création de la hashmap nulléfié
        for key in self.fields.keys() {
            if !values.contains_key(key) {
                values.insert(key.clone(), Value::Null);
            }
        }

        // vérification de la validité des données
        self.check_values(&values)
            .map_err(SerializationError::ColumnDefinition)?;

        // réorganisation des attributs dans l'ordre du tuple défini par le schéma
        let attributes = self.columns.iter().fold(vec![], |mut acc, schema_field| {
            acc.push(values.get(schema_field).unwrap());
            acc
        });
        // création de la null table du tuple
        let nullable_table = values_to_null_table(&attributes);
        for partition in nullable_table.iter() {
            partition.serialize(cursor)?;
        }

        // sérialisation ordonnées
        for schema_field in self.columns.iter() {
            // récupération de la valeur
            let value = values
                .get(schema_field)
                .ok_or(SerializationError::MissingColumn(schema_field.to_string()))?;
            // récupération du ColumnType
            let definition = self
                .fields
                .get(schema_field)
                .ok_or(SerializationError::MissingColumn(schema_field.to_string()))?
                .get_column_type();
            // si la valeur n'est pas null
            if value != &Value::Null {
                // sérialisation de la valeur
                definition.serialize(cursor, value)?
            } else {
                // sinon on avance le curseur
                cursor.set_position(cursor.position() + definition.size() as u64);
            }
        }
        Ok(())
    }
}

Et l’opération inverse de désérialisation, qui consiste à récupérer la null table, puis pour chaque attribut si la null table indique un NULL, passer la désérialisation et renvoyer un Value::Null.

impl Schema {
    pub fn deserialize(
        &self,
        cursor: &mut Cursor<&[u8]>,
    ) -> Result<Vec<Value>, DeserializationError> {
        // récupération de la null table du tuple
        let mut nullable_table = vec![];
        for _ in 0..get_nullable_table_size(self) / PARTITION_SIZE {
            nullable_table.push(u8::deserialize(cursor)?);
        }
        let mut values = Vec::with_capacity(self.columns.len());
        // Le schéma connaît l'ordonnancement des champs
        for (index, schema_field) in self.columns.iter().enumerate() {
            // récupération du ColumnType associé
            let definition = self
                .fields
                .get(schema_field)
                .ok_or(DeserializationError::MissingColumn(
                    schema_field.to_string(),
                ))?
                .get_column_type();
            // si la valeur n'est pas null
            let value = if !is_null(&nullable_table, index) {
                // désérialisation dans la bonne variante de Value
                definition.deserialize(cursor)?
            } else {
                // sinon on avance simplement le curseur à l'attribut suivant
                cursor.set_position(cursor.position() + definition.size() as u64);
                Value::Null
            };
            // accumulation dans le tuple
            values.push(value);
        }
        Ok(values)
    }
}

Et on peut tester notre merveille !

Testons !

On définit deux champs NOT NULL

• id
• name

Et on laisse nullifiable l’âge.

CREATE TABLE Users (id INTEGER NOT NULL PRIMARY KEY, nom TEXT(50) NOT NULL, âge INTEGER);

On peut alors insérer partiellement de la donnée.

INSERT INTO Users (id, nom, âge) VALUES (1, 'Max', 20);
INSERT INTO Users (id, nom) VALUES (2, 'Amy');

Par contre, si on va trop loin dans le “partiel” et que l’on oublie de remplir le nom

INSERT INTO Users (id) VALUES (3);
Insertion(Serialization(ColumnDefinition(NonNullableColumn { column_name: "nom" })))

On peut alors sélectionner nos données

SELECT * FROM Users;
[Integer(1), Text("Max"), Integer(20)]
[Integer(2), Text("Amy"), Null]

Nous avons bien “Amy” qui est sans âge ^^

Conclusion

Pas du tout non ? On commence à entrevoir du sql, la route est encore longue, mais l’on progresse. 😎

Dans la prochaine partie, nous verrons comment gérer les index secondaires.

Merci de votre lecture ❤️

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