Visualización de índices de SQLite

 (mrsuh.com)
3 puntos por GN⁺ 2024-11-16 | 1 comentarios | Compartir por WhatsApp
  • Para comprobar cómo se distribuyen realmente los índices de SQLite en disco y memoria, se analiza la estructura B-Tree y se vuelcan los datos del índice para visualizarlos
  • Los índices están compuestos por Pages y Cells; una Page contiene el enlace al hijo derecho y los datos de las Cells, y una Cell contiene los datos del índice, el rowId y el enlace al hijo izquierdo
  • Como el tamaño de las Pages, la cantidad de entradas, la profundidad del B-tree y el número de Pages usadas que ofrece sqlite3_analyzer no eran suficientes, se añadieron funciones de depuración al código fuente de SQLite
  • El experimento compara cantidad de registros, ASC/DESC, índices basados en expresiones, UNIQUE con NULL, Partial Index, múltiples columnas y combinaciones de texto, REAL y entero+texto
  • Con 1,000,000 de registros, si el índice se crea antes de insertar, termina con 3,342 Pages; si se crea después de insertar, queda con 2,930 Pages, y tras VACUUM o REINDEX también se reduce a 2,930 Pages

Por qué mirar directamente dentro de los índices de SQLite

  • Es un experimento para ir más allá de la estructura básica de un índice y comprobar la estructura de datos real, los algoritmos y la forma en que se almacena en disco
  • El objetivo es observar cómo un DBMS guarda los índices en disco y memoria, y cómo accede a ellos durante el proceso de búsqueda
  • Se eligió SQLite como objeto de experimentación por las siguientes razones
    • Es un DBMS ampliamente usado en navegadores, apps móviles y sistemas operativos
    • Es fácil de depurar solo con la aplicación cliente, sin un servidor aparte
    • Tiene una base de código más pequeña que MySQL o PostgreSQL, pero usa estructuras de datos similares para los índices
    • Es open source

Un B-Tree formado por Pages y Cells

  • Según la documentación de SQLite, los índices se almacenan con una estructura B-Tree
  • En SQLite, la unidad equivalente a un Node es una Page
    • Una Page almacena los datos de las Cells
    • Una Page tiene un enlace hacia la Page hija derecha
  • Una Cell incluye los datos del índice, el rowId y el enlace a la Page hija izquierda
  • Cada fila de una tabla de SQLite tiene por defecto un rowId único, que funciona como clave primaria cuando no hay una clave primaria explícita
  • Cada Page tiene un tamaño fijo, con un rango de 512~65,536 bytes
  • Los encabezados de Page y Cell usan 4 bytes para guardar enlaces a hijos
    • Para conocer el número de la Page hija, hay que leer el encabezado por separado con la función get4byte(...)
  • Algunos ejemplos de estructuras internas de SQLite son los siguientes
    • MemPage: incluye el número de Page pgno, la cantidad de Cells nCell, el área de índices de Cells aCellIdx, el puntero aData a la imagen de la Page en disco, entre otros
    • CellInfo: incluye pPayload, que apunta a la posición inicial del payload

Límites de sqlite3_analyzer y funciones de depuración

  • Con sqlite3_analyzer se puede ver información general del índice
    • La salida de ejemplo incluye tamaño de Page 4096, cantidad de entradas 1000, profundidad del B-tree 2 y número de Pages usadas 4
  • Sin embargo, esta herramienta se queda en información de visión general y no permite inspeccionar directamente las Cells internas ni el payload del índice
  • Después de varias semanas de pruebas, se escribieron funciones para analizar índices
    • Código: sqlite.patch
    • sqlite3DebugGetMemoryPayload(Mem *mem)
    • sqlite3DebugGetCellPayloadAndRowId(BtCursor *pCur, MemPage * pPage, int cellIndex)
    • sqlite3DebugBtreeIndexDump(BtCursor *pCur, int pageNumber)
  • Estas funciones leen el contenido del índice seleccionado y lo imprimen en STDOUT
    • El flujo es SQL query -> selected index -> stdout
    • La salida incluye número de Page, número de la Page hija derecha, número de Cell, número de la Page hija izquierda, payload y rowId
  • El entorno de pruebas puede ejecutarse con Docker
    • docker run -it --rm -v "$PWD":/app/data --platform linux/x86_64 mrsuh/sqlite-index bash
    • sh bin/dump-index.sh database.sqlite "SELECT * FROM table INDEXED BY index WHERE column=1" dump.txt

Cómo fue cambiando la visualización

  • Al principio se usó d3-org-tree para visualizar la estructura del índice
  • A medida que el árbol se hacía más profundo y aumentaba la cantidad de Pages por nivel, resultó difícil ajustar el espaciado entre Pages, por lo que la imagen se volvía demasiado grande y difícil de leer
  • Se intentó ajustarlo con JavaScript y CSS, pero no encajó bien, así que por un tiempo se cambió a una representación basada en texto
  • La salida en texto muestra el número total de Pages, el número total de Cells, la cantidad de Pages y Cells por nivel, información de cada Page e información de cada Cell con su payload
  • Más adelante evolucionó a una salida en imagen usando la extensión ImageMagick para PHP, lo que permitió controlar con más detalle el diseño y los espacios
  • La imagen final incluye la siguiente información
    • En la parte superior izquierda se muestra la información general del índice
    • En cada nivel se muestra el número total de Pages y Cells
    • En cada Page se muestran el número de Page, el enlace al hijo derecho y la información de la primera y la última Cell
    • En cada nivel solo se muestran algunas Pages, incluyendo la primera y la última
    • La Page raíz se ubica en el primer nivel
  • El comando para generar una imagen a partir del volcado es el siguiente
    • php bin/console app:render-index --dumpIndexPath=dump.txt --outputImagePath=image.webp

La forma del índice cambia según la cantidad de registros

  • Se creó un índice column1 ASC en una tabla column1 INT NOT NULL y se cambió la cantidad de registros para observar la estructura
  • El índice con 1 registro está compuesto por 1 nivel, 1 Page y 1 Cell
  • El índice con 1,000 registros también se generó y visualizó de la misma forma
  • El índice con 1,000,000 registros tiene la siguiente estructura
    • 3 niveles
    • 2,930 Pages
    • 1,000,000 Cells
  • Como los datos se agregaron en orden, cuando rowId = 1, entonces column1 = 1

Dirección de ordenamiento e índices por expresión

  • Sobre los mismos datos se crearon idx_asc y idx_desc para comparar índices ASC/DESC
  • El índice ASC es igual al anterior porque el orden predeterminado es ASC
    • El elemento con rowId=1,000,000, column1=1,000,000, payload=1,000,000 está en la última Cell de la Page más a la derecha
    • El elemento con rowId=1, column1=1, payload=1 está en la primera Cell de la Page más a la izquierda
  • El índice DESC está distribuido al revés
    • El elemento con rowId=1, column1=1, payload=1 está en la última Cell de la Page más a la derecha
    • El elemento con rowId=1,000,000, column1=1,000,000, payload=1,000,000 está en la primera Cell de la Page más a la izquierda
  • Un índice basado en expresiones almacena la cadena generada por la expresión
    • El ejemplo extrae $.timestamp de un texto JSON y luego lo convierte con strftime('%Y-%m-%d %H:%M:%S', ..., 'unixepoch') para crear un índice ASC
    • También se pueden usar expresiones más complejas, y en el índice solo se almacena su resultado

NULL, Partial Index y múltiples columnas

  • SQLite soporta índices UNIQUE que incluyen valores NULL
    • En el ejemplo se insertan 1, varios NULL y 1000000, y luego se ejecuta CREATE UNIQUE INDEX idx ON table_test (column1 ASC)
    • El índice visualizado parece almacenar solo los valores que no son NULL
  • Un Partial Index con la condición WHERE column1 IS NOT NULL filtra los valores NULL
    • Este índice contiene solo una Page
    • Eso lleva a una búsqueda más rápida que en el ejemplo UNIQUE anterior
  • Un índice de múltiples columnas guarda los datos de todos los campos en orden dentro de una Cell
    • El ejemplo usa un índice (column1 ASC, column2 ASC)
    • En la visualización, los campos aparecen separados por dos puntos :

Momento de creación del índice y efecto de la reconstrucción

  • Se comparó el caso de crear el índice antes de insertar los datos con el de crearlo después de insertar todos los datos
  • Cuando se agregan nuevos datos, el árbol tiene que rebalancearse por sí solo
  • Crear el índice de una sola vez sobre los datos ya existentes puede ser mucho más eficiente
  • Ambos índices se ven parecidos, pero el segundo, con menos Pages, podría ser más rápido
  • La comparación con 1,000,000 Cells da el siguiente resultado
Categoría Total Pages Total Cells
Creado antes de insertar 3342 1000000
Creado después de insertar 2930 1000000
  • Una optimización similar puede hacerse con VACUUM o REINDEX
    • VACUUM vuelve a crear índices y tablas junto con los datos
    • REINDEX idx vuelve a crear solo el índice
  • En el ejemplo, ambos comandos reducen la cantidad de Pages de 3342 a 2930

Cómo se almacenan los índices según el tipo de dato

  • Los datos de texto con cadenas cortas se almacenan directamente en la Cell del índice, pero los textos largos deben almacenarse por separado
    • En el ejemplo se insertan valores desde text-1 hasta text-1000000 y se crea un índice column1 ASC
    • Se puede comprobar que la cadena real se guarda directamente en el índice
  • Los datos REAL también se almacenan en el índice y se visualizan
    • El ejemplo usa los valores 1.14, 2.14, ..., 1000000.14
  • También se revisa un índice compuesto que mezcla entero y texto
    • El ejemplo crea un índice (column1 ASC, column2 ASC) sobre una tabla (column1 INT, column2 TEXT)
    • El entero y la cadena se almacenan juntos en la misma Cell, tal como se definió al crear el índice

Cómo reproducirlo y qué sigue

  • El experimento muestra cómo se estructuran los índices de SQLite, cómo se almacenan los datos de los registros en memoria y cómo el B-Tree organiza y accede a los datos
  • La visualización se usa para analizar y comparar distintos índices
  • Todos los ejemplos pueden reproducirse con el siguiente comando
    • docker run -it --rm -v "$PWD":/app/data --platform linux/x86_64 mrsuh/sqlite-index bash
    • sh bin/test-index.sh
  • El código y los ejemplos están en mrsuh/sqlite-index
  • El siguiente trabajo será la visualización de búsquedas basadas en índices y la exploración de algunas consultas SQL

Lecturas relacionadas

1 comentarios

 
GN⁺ 2024-11-16
Comentarios en Hacker News

  • Cada fila de una tabla de SQLite tiene por defecto un rowId único, y se dijo que si no hay una clave primaria explícita, funciona como si fuera la clave primaria, pero en realidad usa rowid incluso cuando sí hay clave primaria
    Estaría bueno visualizar el índice de clave primaria de una tabla WITHOUT ROWID. Ese tipo de índice es especialmente interesante
    Aunque dos índices se vean parecidos, que el segundo tenga menos páginas no significa automáticamente que sea más rápido. Lo importante es la altura del árbol y, después, si tras encontrar el valor en el índice hay que leer el resto de los datos desde una tabla aparte (rowid), o si los datos están ahí mismo como en WITHOUT ROWID. La diferencia se nota mucho, sobre todo en consultas por rango como where 50 <= col <= 100

    • Si hablamos solo de un acceso individual, la altura del árbol es lo correcto, pero si se accede al índice con frecuencia, el tamaño total también puede ser muy importante para la tasa de aciertos de caché
    • Hay una excepción a eso de que usa rowid incluso con clave primaria. Si creas un INTEGER PRIMARY KEY, SQLite usa eso en su lugar [1]
      [1]: https://sqlite.org/rowidtable.html

  • SQLite es bastante inusual en casi todo lo que hace, y creo que todavía más en el procesamiento de consultas
    SQLite tiende a preferir la simplicidad sobre el rendimiento, así que muchas veces está implementado de formas distintas a otras bases de datos con las que he trabajado. SQLite no compite tanto con otras bases de datos como con archivos JSON/XML de almacenamiento persistente. Por eso, ver cómo está implementado SQLite no necesariamente te enseña mucho sobre cómo hacen lo mismo las bases de datos "reales"

    • Compite con ambas cosas. Está claro que SQLite se usa como almacenamiento persistente local, pero también compite con otros sistemas de gestión de bases de datos relacionales en situaciones donde no hace falta un proceso de servidor separado
      Eso sí, los requisitos suelen ser muy distintos, pero su uso no se limita solo a reemplazar archivos JSON/XML
    • SQLite sí es un motor de base de datos real. Probablemente lo que se quiere decir es que no compite con servidores de bases de datos
    • No está tan alejado de cómo otros servidores de sistemas de gestión de bases de datos manejan el almacenamiento y los índices. Los principios son casi los mismos, especialmente cuando SQLite funciona en modo WAL

  • El sitio web se lee tan bien que dan ganas de leerlo de verdad

    • Viéndolo en un iPhone, el tamaño de letra del texto principal es demasiado grande. El texto importante dentro de los diagramas es mucho más pequeño, así que para leer el cuerpo del texto hay que alejar el teléfono de la cara y para leer los diagramas volver a acercarlo, lo cual se siente raro
    • Da mucho gusto poder ver el contenido sin anuncios por todos lados. El artículo también está muy bueno

  • “indexes” también puede ser la forma de presente en tercera persona singular del verbo “to index”, además de ser el plural del sustantivo “index”. En cambio, “indices” es el plural tradicional, y se usa mucho sobre todo en contextos de matemáticas y ciencia
    En inglés general, “indexes” es más común, pero en áreas técnicas a veces se prefiere indices por precisión lingüística. En este contexto, usar “indices” puede dar más claridad al distinguir entre la acción de indexar y el plural de índice

    • Las dos formas están bien(https://www.nasdaq.com/articles/indexes-or-indices-whats-the...). La documentación de SQLite y PostgreSQL, por ejemplo, usa indexes
    • No es nada fácil intentar hacer plural “time series”
      En Finlandia he visto que usan “time series” como plural y “time serie” como singular
    • No sé con qué autoridad se afirma eso
      Todos los principales sistemas de gestión de bases de datos relacionales usan el término indexes
    • Depende del público objetivo. Si escribes para el ámbito académico, usa indices; si escribes para lectores generales, “indices” puede sonar pretencioso

  • También estaría bueno ver cómo hace lo mismo PostgreSQL. Seguro habría mucho que aprender de la comparación

  • Para ver distintas disposiciones con menos trabajo, también podría hacer que genere TGF para yEd