Pendant les trois premières sessions de développement de FlinDB, chaque requête effectuait un scan complet de table. L'annotation @index existait déjà dans la définition de schéma, mais elle était décorative. L'index était déclaré mais jamais construit.
La session 163 a corrigé cela. En une seule session : population des index, maintenance sur toutes les opérations de mutation, optimisation des requêtes qui utilise automatiquement les index quand ils sont disponibles, et vérification de contrainte d'unicité adossée aux index. Neuf tests. Chaque requête sur un champ indexé est passée de O(n) à O(1).
Conception du stockage des index
rust// EntityCollection fields
indexes: HashMap<String, HashMap<String, Vec<u64>>>La clé externe est le nom du champ. La clé interne est la valeur encodée avec un préfixe de type pour éviter les collisions :
rustfn value_to_index_key(value: &Value) -> String {
match value {
Value::Text(s) => format!("$$TEXT$$:{}", s),
Value::Int(n) => format!("$$INT$$:{}", n),
Value::Number(n) => format!("$$NUM$$:{}", n),
Value::Bool(b) => format!("$$BOOL$$:{}", b),
_ => format!("$$OTHER$$:{:?}", value),
}
}Maintenance des index sur tout le cycle de vie
Save : ajoute aux index. Pour les mises à jour, supprime l'ancienne valeur puis ajoute la nouvelle.
Delete (douce) : supprime des index car les entités supprimées ne doivent pas apparaître.
Destroy (dure) : supprime des index avant la suppression du stockage.
Restore : rajoute l'entité aux index.
Optimisation des requêtes
rustfn execute_query(&self, query: &Query) -> DatabaseResult<Vec<EntityInstance>> {
if let Some((field, value)) = self.find_indexed_eq_condition(query) {
// O(1) index lookup
let entity_ids = self.lookup_by_index(entity_type, &field, &value)?;
// Apply remaining conditions as filters
return Ok(results);
}
// Fallback: full table scan
self.full_scan(query)
}Impact sur la performance
| Opération | Avant | Après |
|---|---|---|
where_eq sur champ indexé | O(n) | O(1) |
| Vérification de contrainte unique sur champ indexé | O(n) | O(1) |
where_gt sur tout champ | O(n) | O(n) |
Indexation automatique des références
Les champs de référence d'entité sont automatiquement indexés, ce qui signifie que les requêtes de relation bénéficient de l'accélération par index sans annotation @index explicite du développeur.
Ceci est la partie 6 de la série « How We Built FlinDB ».
Navigation de la série : - [058] CRUD Without SQL - [059] Constraints and Validation in FlinDB - [060] Aggregations and Analytics - [061] Index Utilization: Making Queries Fast (vous êtes ici) - [062] Relationships and Eager/Lazy Loading