Durante las tres primeras sesiones de desarrollo de FlinDB, cada consulta realizaba un escaneo completo de tabla. User.where(email == "[email protected]") iteraba a través de cada entidad User, verificando el campo email uno por uno. Para cien usuarios, esto era instantáneo. Para diez mil usuarios, era notable. Para un millón de usuarios, sería inutilizable.
La anotación @index ya existía en la definición del esquema de FlinDB. Los desarrolladores podían escribir email: text @index y sentir que estaban haciendo lo correcto. Pero la anotación era decorativa. El índice se declaraba pero nunca se construía. El motor de consultas lo ignoraba por completo.
La Sesión 163 corrigió esto. En una sola sesión, implementamos la población de índices, el mantenimiento de índices a través de todas las operaciones de mutación, la optimización de consultas que usa automáticamente los índices cuando están disponibles, y la verificación de restricciones unique respaldada por índices. Nueve pruebas. Cada consulta en un campo indexado pasó de O(n) a O(1).
El problema: índices decorativos
Antes de la Sesión 163, la anotación @index modificaba el esquema pero no tenía efecto en la ejecución de consultas:
flinentity User {
email: text @index // Declared but never used
name: text
}
// This query always scanned every User entity
users = User.where(email == "[email protected]")El esquema registraba que email debería estar indexado. El motor de consultas no verificaba si un campo estaba indexado. Cada operación where_eq, where_lt y where_gt realizaba un escaneo lineal a través de todas las entidades de ese tipo.
Esta era una brecha conocida. Las Sesiones 160-162 se enfocaron en la corrección -- hacer que CRUD, restricciones y agregaciones funcionaran correctamente. La Sesión 163 fue sobre hacerlas funcionar rápido.
Diseño del almacenamiento de índices
La estructura de datos del índice es un HashMap anidado almacenado dentro de cada colección de entidades:
rust// EntityCollection fields
indexes: HashMap<String, HashMap<String, Vec<u64>>>La clave exterior es el nombre del campo (p. ej., "email"). La clave interior es el valor codificado (p. ej., "$$TEXT$$:[email protected]"). El valor es un vector de IDs de entidades que tienen ese valor para ese campo.
La clave del índice usa un prefijo de tipo para evitar colisiones entre diferentes tipos de valores:
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),
}
}¿Por qué el prefijo de tipo? Porque la cadena "42" y el entero 42 son valores diferentes que deberían mapear a entradas de índice diferentes. Sin el prefijo, Value::Text("42") y Value::Int(42) colisionarían en el índice, causando resultados de consulta incorrectos.
Población del índice al guardar
Cuando se guarda una entidad, sus campos indexados se agregan a los índices apropiados:
rustfn add_to_indexes(
&mut self,
schema: &EntitySchema,
entity_id: u64,
fields: &HashMap<String, Value>,
) {
for field_name in &schema.indexed_fields {
if let Some(value) = fields.get(field_name) {
let key = value_to_index_key(value);
self.indexes
.entry(field_name.clone())
.or_default()
.entry(key)
.or_default()
.push(entity_id);
}
}
}Para actualizaciones, el mantenimiento del índice es un proceso de dos pasos: eliminar el valor antiguo del índice, luego agregar el nuevo valor:
rust// In save() for existing entities:
// 1. Remove old values from indexes
self.remove_from_indexes(schema, entity_id, &old_fields);
// 2. Add new values to indexes
self.add_to_indexes(schema, entity_id, &new_fields);Esto asegura que el índice siempre refleje el estado actual de los datos. Una entidad que cambia su email de "[email protected]" a "[email protected]" se elimina de la entrada del índice para "[email protected]" y se agrega a la entrada para "[email protected]".
Mantenimiento del índice en eliminación y restauración
La eliminación suave, la destrucción permanente y la restauración afectan los índices:
La eliminación suave elimina la entidad de los índices. Dado que todas las consultas excluyen automáticamente las entidades eliminadas de forma suave, el índice no debería contenerlas:
rust// In delete():
self.remove_from_indexes(schema, entity_id, &entity.fields);La destrucción permanente también elimina de los índices, pero antes de que la entidad se elimine del almacenamiento:
rust// In destroy():
self.remove_from_indexes(schema, entity_id, &entity.fields);
// Then remove entity from dataLa restauración (des-eliminar una entidad eliminada de forma suave) agrega la entidad de vuelta a los índices:
rust// In restore():
self.add_to_indexes(schema, entity_id, &entity.fields);Esta gestión del ciclo de vida es crítica. Sin ella, los índices se volverían obsoletos -- conteniendo referencias a entidades eliminadas o faltando referencias a entidades restauradas. Cada operación de mutación debe mantener la consistencia del índice, o el índice es peor que inútil (devolvería resultados incorrectos, lo cual es peor que ser lento).
Optimización de consultas
El motor de ejecución de consultas fue modificado para verificar la disponibilidad de índices antes de ejecutar una consulta:
rustfn execute_query(&self, query: &Query) -> DatabaseResult<Vec<EntityInstance>> {
// Check if any equality condition is on an indexed field
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
let results: Vec<_> = entity_ids.iter()
.filter_map(|id| self.find_by_id_internal(entity_type, *id).ok())
.filter(|entity| entity.deleted_at.is_none())
.filter(|entity| query.remaining_conditions_match(entity))
.collect();
return Ok(results);
}
// Fallback: full table scan
self.full_scan(query)
}El optimizador busca condiciones de igualdad (where_eq) en campos indexados. Si encuentra una, usa el índice para la búsqueda inicial y luego aplica cualquier condición restante como filtros sobre el conjunto de resultados.
Por ejemplo, considera esta consulta:
flinUser.where(email == "[email protected]" && active == true)Si email está indexado pero active no:
- Búsqueda en índice de
emaildevuelve IDs de entidades[42]-- O(1) - Cargar entidad 42 del almacén de datos -- O(1)
- Verificar
active == trueen la entidad 42 -- O(1)
Total: O(1) en lugar de O(n).
Si ningún campo está indexado, la consulta recurre a un escaneo completo. Si ambos campos están indexados, el optimizador elige la primera condición indexada que encuentra. Un optimizador más sofisticado podría estimar la selectividad y elegir el índice más selectivo, pero para el caso de uso de FlinDB (bases de datos embebidas con volúmenes de datos moderados), el enfoque simple funciona bien.
Verificación de restricciones unique respaldada por índices
La verificación de restricciones unique también se optimizó para usar índices. Antes de la Sesión 163, verificar la unicidad requería escanear todas las entidades para encontrar duplicados. Después de la Sesión 163, los campos unique que también están indexados usan el índice para detección de conflictos O(1):
rustfn check_unique_constraints(&self, ...) -> DatabaseResult<()> {
for constraint in &schema.constraints {
match constraint {
Constraint::Unique(field) => {
if let Some(value) = fields.get(field) {
// Try index lookup first
if schema.indexed_fields.contains(field) {
let ids = self.lookup_by_index(entity_type, field, value)?;
for existing_id in ids {
if Some(existing_id) != id {
return Err(DatabaseError::UniqueViolation { /* ... */ });
}
}
} else {
// Full scan fallback for non-indexed unique fields
self.check_unique_by_scan(entity_type, id, field, value)?;
}
}
}
_ => {}
}
}
Ok(())
}En la práctica, los campos unique siempre deberían estar indexados (y FlinDB podría auto-indexarlos en una versión futura). Pero la implementación maneja ambos casos -- los campos unique indexados obtienen verificaciones O(1), y los campos unique no indexados recurren a escaneos O(n).
Impacto en el rendimiento
La mejora de rendimiento es dramática para consultas indexadas:
| Operación | Antes (Complejidad) | Después (Complejidad) |
|---|---|---|
where_eq en campo indexado | O(n) | O(1) |
| Verificación unique en campo indexado | O(n) | O(1) |
where_gt en cualquier campo | O(n) | O(n) |
where_eq no indexado | O(n) | O(n) |
Las operaciones O(n) permanecen sin cambios porque las consultas de rango (>, <, >=, <=) requieren una estructura de índice diferente (B-tree o array ordenado) que no se implementó en esta sesión. Para la carga de trabajo objetivo de FlinDB -- aplicaciones con cientos a miles de entidades por tipo -- el índice hash cubriendo consultas de igualdad es la optimización de mayor impacto.
Indexación automática para referencias
Una de las contribuciones de la Sesión 164 (cubierta en el artículo de relaciones) fue la indexación automática de campos de referencia de entidades. Cuando un esquema contiene una referencia como author: User, ZeroCore agrega automáticamente author a la lista de campos indexados:
rust// During schema registration
for field in &schema.fields {
if field.field_type == FieldType::EntityRef(_) {
schema.indexed_fields.push(field.name.clone());
}
}Esto significa que las consultas de relaciones -- Post.where(author == user) -- se benefician automáticamente de la aceleración por índice sin que el desarrollador agregue una anotación @index explícita. Dado que las consultas de relaciones están entre los patrones de consulta más comunes, esta indexación automática proporciona una mejora de rendimiento significativa sin configuración.
Las nueve pruebas
La Sesión 163 agregó nueve pruebas cubriendo cada aspecto del comportamiento de índices:
test_index_populated_on_save-- verifica la creación del índice para nuevas entidadestest_index_updated_on_entity_update-- verifica la eliminación del valor antiguo y la adición del nuevotest_index_removed_on_delete-- verifica que la eliminación suave remueve del índicetest_index_removed_on_destroy-- verifica que la eliminación permanente remueve del índicetest_index_restored_on_restore-- verifica que la restauración agrega de vuelta al índicetest_where_eq_uses_index-- verifica que la consulta usa el índice para igualdadtest_unique_constraint_uses_index-- verifica que la verificación unique usa el índicetest_index_multiple_entities_same_value-- verifica que los índices no unique funcionan correctamentetest_index_with_multiple_conditions-- verifica el índice más condiciones de filtro adicionales
La prueba 8 es particularmente importante. Los índices no unique pueden tener múltiples IDs de entidades para el mismo valor. Por ejemplo, si diez usuarios están en el rol "admin", la entrada del índice para role: "admin" debería contener los diez IDs de entidades. La prueba verifica que la búsqueda devuelve todas las entidades coincidentes, no solo la primera.
La prueba 9 verifica la ruta combinada: búsqueda en índice para una condición, luego filtro para condiciones adicionales. Este es el patrón del mundo real más común -- rara vez consultas sobre un solo campo.
Después de la Sesión 163: 2.120 pruebas pasando (1.514 de biblioteca + 606 de integración).
Lo que los índices no pueden hacer (aún)
La Sesión 163 implementó índices hash optimizados para búsquedas de igualdad. Varias funcionalidades avanzadas de índices se difirieron:
Índices de rango -- índices B-tree u ordenados que acelerarían las consultas where_gt, where_lt y de rango. Estos son importantes para consultas basadas en tiempo (created_at > yesterday) pero requieren una estructura de datos más compleja.
Índices compuestos -- índices sobre múltiples campos juntos, acelerando consultas como where(category == "electronics" && brand == "Apple"). La implementación actual puede usar un índice en cualquiera de los campos pero no en ambos simultáneamente.
Índices parciales -- índices que solo incluyen entidades que coinciden con una condición, útiles para grandes conjuntos de datos donde la mayoría de las entidades no coinciden con el patrón de consulta común.
Estadísticas de índice -- rastrear con qué frecuencia se usa cada índice, qué tan selectivo es y si el optimizador de consultas está tomando buenas decisiones.
Estas funcionalidades acercarían la indexación de FlinDB a las capacidades de PostgreSQL. Pero para el caso de uso de base de datos embebida -- aplicaciones con volúmenes de datos moderados ejecutándose en una sola máquina -- el índice hash cubre los escenarios de mayor impacto. La regla 80/20 aplica: el 80% del rendimiento de consultas proviene del 20% de las funcionalidades de índice, y ese 20% son las búsquedas de igualdad en campos indexados.
Esta es la Parte 6 de la serie "Cómo construimos FlinDB", documentando cómo construimos un motor de base de datos embebido completo para el lenguaje de programación FLIN.
Navegación de la serie: - [058] CRUD Without SQL - [059] Constraints and Validation in FlinDB - [060] Aggregations and Analytics - [061] Index Utilization: Making Queries Fast (estás aquí) - [062] Relationships and Eager/Lazy Loading