▣ gabysql

Estado: ✅ Aceptada Fecha: 2026-05-18 Contexto que la motiva: bloque “range scan por índice secundario” de Fase 2 → habilitar WHERE col_idx BETWEEN a AND b sin desarmar el resto del motor.

🧭 Contexto

ADR-0005 fijó el formato del índice secundario: B+Tree con clave i64 = FNV-1a-64(value_bytes), buckets que listan (value_bytes, pk) para tolerar colisiones de hash. Esto cierra el caso de equality (WHERE col = X) en O(log N + bucket_size), que es lo que el bloque pedía en su momento.

Pero hash → range no se compone. Dos valores cercanos (5 y 6) tienen hashes arbitrariamente distintos. Cualquier intento de WHERE col BETWEEN 5 AND 100 sobre el índice actual requiere visitar todos los buckets — o sea, full scan disfrazado. El ítem “range scan por índice secundario” del roadmap quedó marcado como no viable con la estructura de ADR-0005.

La salida natural es: para columnas donde el orden i64 ES el orden semántico, usar el valor directamente como clave del B+Tree en lugar del hash. Con Tree::cursor_range(idx_root, from, to) ya implementado (ADR-0008), eso da range scan en O(log N + k) donde k = filas en el rango.

Las columnas que satisfacen “orden i64 = orden semántico” son las INT. Las demás (TEXT, FLOAT, BOOL, DATE, DATETIME) requieren un encoder order-preserving distinto, idealmente un B+Tree byte-keyed — fuera de scope para este bloque.

Restricciones del proyecto:

💡 Decisión

Tres cambios en concierto, todos bajo VERSION 7:

1. IndexKind en IndexMeta

pub enum IndexKind {
    Hash,        // ADR-0005 — equality only
    OrderedInt,  // ADR-0017 — value-as-key, range-capable
}

pub struct IndexMeta {
    pub name: String,
    pub column: String,
    pub root_page: u32,
    pub unique: bool,
    pub kind: IndexKind,  // ← nuevo
}

Layout on-disk: un byte extra por índice tras unique:u8. V6 files se rechazan con el mensaje estándar “version=6 (expected 7). Re-create the database with the current binary.”

IndexKind::for_column(column_type) decide automáticamente:

2. Nuevos buckets ordenados en src/index.rs

Layout de un bucket OrderedInt:

[count:u16] + count × [pk:i64]

No hace falta guardar el valor en cada entry porque la clave del B+Tree es el valor. PKs almacenados en orden creciente para que WHERE pk = … short-circuits sigan siendo determinísticos.

Helpers:

3. Branching por kind en sql.rs

Toda función que tocaba un índice (index_upsert_pk, index_remove_pk, check_unique_conflict, lookup_pks_via_index, integrity check, FK cascade child lookup) ahora recibe kind: IndexKind o lee idx.kind y elige el camino correcto.

Nuevo path: lookup_pks_via_index_range(pager, idx, from, to) — usa Tree::cursor_range(idx.root_page, from, to) para iterar las claves en orden, decodifica cada bucket ordenado, devuelve los PKs.

Plan dispatch para WHERE col BETWEEN a AND b:

NULL handling

NULL no se almacena en índices OrderedInt:

Trade-off: si alguien quisiera WHERE col IS NULL acelerado por índice, no es posible con este layout. Aceptable — IS NULL no era parte del plan tampoco.

🤔 Alternativas evaluadas

  1. B+Tree byte-keyed para TODOS los índices: el camino limpio que cubre TEXT/FLOAT/DATE además de INT. Pero requiere reescribir bptree.rs para clave Vec<u8> o introducir un B+Tree paralelo. Estimación: 800+ LOC, riesgo de regresión en hot path. Diferido a un futuro bloque cuando se necesite range sobre TEXT.

  2. Encoding order-preserving para FLOAT/DATE en i64: posible (flip-sign trick para FLOAT, DATE ya es i64 internamente). Habría dado range scan adicional sin nueva estructura. Diferido: no resuelve TEXT y agrega complejidad de encoding por tipo. Cuando aparezca demanda concreta, se evalúa.

  3. Mantener todo en hash y agregar un segundo índice ordenado separado cuando el usuario pide range: dos índices físicos por columna, dos veces el costo de mantenimiento. No.

  4. Índices compuestos en el mismo bump: el ítem original del roadmap los agrupaba con range scan. Pero compuestos requieren claves multi-columna que con el approach value-as-i64 sería forzado (concatenar dos i64 → un solo i64 pierde información). Compuestos requieren prácticamente el mismo trabajo que un B+Tree byte-keyed. Separados explícitamente del bloque actual.

  5. Mantener el hash para INT también, agregar un range scan vía full-bucket sweep: O(N) sobre el número de claves del índice, igual que un full scan. No aporta nada sobre la tabla.

✅ Consecuencias

Positivas:

Negativas / a vigilar:

🔗 Referencias