Visualização de índices no SQLite

 (mrsuh.com)
3 pontos por GN⁺ 2024-11-16 | 1 comentários | Compartilhar no WhatsApp
  • Para verificar como os índices do SQLite ficam de fato organizados em disco e na memória, a estrutura de B-Tree foi analisada, e os dados do índice foram despejados e visualizados
  • O índice é composto por unidades de Page e Cell; a Page contém o link para o filho da direita e os dados das Cells, enquanto a Cell contém os dados do índice, o rowId e o link para o filho da esquerda
  • Como apenas o tamanho da Page, número de entradas, profundidade da B-tree e número de Pages usadas fornecidos por sqlite3_analyzer não eram suficientes, foram adicionadas funções de depuração ao código-fonte do SQLite
  • O experimento compara quantidade de registros, ASC/DESC, índices baseados em expressão, UNIQUE com NULL incluído, Partial Index, múltiplas colunas e combinações de texto, REAL e inteiro+texto
  • Com 1.000.000 de registros, criar o índice antes da inserção resultou em 3.342 Pages, enquanto criá-lo depois resultou em 2.930 Pages; após VACUUM ou REINDEX, o total também caiu para 2.930 Pages

Por que olhar diretamente para os índices do SQLite

  • O experimento busca ir além da estrutura básica dos índices para verificar a estrutura de dados, os algoritmos e a forma de armazenamento em disco
  • O objetivo é observar como um SGBD armazena índices em disco e na memória, e como acessa esses dados durante o processo de busca
  • O SQLite foi escolhido como alvo do experimento pelos seguintes motivos
    • É um SGBD amplamente usado em navegadores, apps móveis e sistemas operacionais
    • É fácil de depurar apenas com a aplicação cliente, sem necessidade de servidor separado
    • Tem uma base de código menor que MySQL ou PostgreSQL, mas usa estruturas de dados semelhantes para índices
    • É open source

B-Tree formada por Page e Cell

  • Segundo a documentação do SQLite, os índices são armazenados em uma estrutura B-Tree
  • No SQLite, a unidade equivalente a um Node é a Page
    • A Page armazena os dados das Cells
    • A Page possui um link para a Page filha da direita
  • A Cell inclui os dados do índice, o rowId e o link para a Page filha da esquerda
  • Cada linha de uma tabela SQLite possui, por padrão, um rowId único, que funciona como uma chave primária implícita quando não há chave primária explícita
  • Cada Page tem tamanho fixo, com faixa de 512~65.536 bytes
  • Os cabeçalhos de Page e Cell usam 4 bytes para armazenar links de filhos
    • Para descobrir o número da Page filha, é necessário ler o cabeçalho separadamente com a função get4byte(...)
  • Exemplos de estruturas internas do SQLite
    • MemPage: inclui o número da Page pgno, a quantidade de Cells nCell, a área de índice de Cells aCellIdx, o ponteiro aData para a imagem da Page em disco, entre outros
    • CellInfo: inclui pPayload, que aponta para o início do payload, entre outros

Limites do sqlite3_analyzer e funções de depuração

  • Com o sqlite3_analyzer, é possível ver informações gerais do índice
    • A saída de exemplo inclui tamanho de Page 4096, número de entradas 1000, profundidade da B-tree 2 e número de Pages usadas 4
  • Mas essa ferramenta oferece apenas uma visão geral, insuficiente para inspecionar diretamente as Cells internas e o payload do índice
  • Após algumas semanas de experimento, foram escritas funções para análise do índice
    • Código: sqlite.patch
    • sqlite3DebugGetMemoryPayload(Mem *mem)
    • sqlite3DebugGetCellPayloadAndRowId(BtCursor *pCur, MemPage * pPage, int cellIndex)
    • sqlite3DebugBtreeIndexDump(BtCursor *pCur, int pageNumber)
  • Essas funções leem o conteúdo do índice selecionado e o imprimem em STDOUT
    • O fluxo é SQL query -> selected index -> stdout
    • A saída inclui número da Page, número da Page filha da direita, número da Cell, número da Page filha da esquerda, payload e rowId
  • É possível executar o ambiente de experimento com 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

Mudanças na forma de visualização

  • No início, foi usado o d3-org-tree para visualizar a estrutura do índice
  • Conforme a árvore ficava mais profunda e o número de Pages por nível aumentava, ficou difícil ajustar o espaçamento entre as Pages, e a imagem se tornava grande demais e difícil de ler
  • Houve tentativas de ajuste com JavaScript e CSS, mas como não funcionaram bem, em certo momento houve migração para uma representação textual da estrutura
  • A saída em texto mostra número total de Pages, número total de Cells, quantidade de Pages e Cells por nível, informações das Pages e informações das Cells com payload
  • Depois, isso evoluiu para saída em imagem usando a extensão ImageMagick do PHP, com controle mais refinado de design e espaçamento
  • A imagem final inclui as seguintes informações
    • Exibição de informações gerais do índice no canto superior esquerdo
    • Exibição do número total de Pages e Cells em cada nível
    • Exibição, em cada Page, do número da Page, do link para o filho da direita e das informações da primeira e da última Cell
    • Exibição de apenas algumas Pages por nível, incluindo a primeira e a última
    • A Page raiz fica localizada no primeiro nível
  • O comando para gerar a imagem a partir do dump é o seguinte
    • php bin/console app:render-index --dumpIndexPath=dump.txt --outputImagePath=image.webp

Como a quantidade de registros muda a forma do índice

  • Foi criado um índice column1 ASC em uma tabela column1 INT NOT NULL, variando a quantidade de registros para observar a estrutura
  • O índice com 1 registro é composto por 1 nível, 1 Page e 1 Cell
  • O índice com 1.000 registros também foi gerado da mesma forma e visualizado
  • O índice com 1.000.000 de registros tem a seguinte estrutura
    • 3 níveis
    • 2.930 Pages
    • 1.000.000 Cells
  • Como os dados foram adicionados em ordem, quando rowId = 1, então column1 = 1

Direção de ordenação e índices por expressão

  • Para os mesmos dados, foram criados idx_asc e idx_desc para comparar índices ASC/DESC
  • O índice ASC é igual ao anterior, já que a ordenação padrão é ASC
    • O item com rowId=1.000.000, column1=1.000.000, payload=1.000.000 está na última Cell da Page mais à direita
    • O item com rowId=1, column1=1, payload=1 está na primeira Cell da Page mais à esquerda
  • O índice DESC fica disposto de forma inversa
    • O item com rowId=1, column1=1, payload=1 está na última Cell da Page mais à direita
    • O item com rowId=1.000.000, column1=1.000.000, payload=1.000.000 está na primeira Cell da Page mais à esquerda
  • Um índice baseado em expressão armazena a string produzida pela expressão
    • O exemplo extrai $.timestamp de um texto JSON e depois converte com strftime('%Y-%m-%d %H:%M:%S', ..., 'unixepoch') para criar um índice ASC
    • Também é possível usar expressões mais complexas, e o índice armazena apenas o resultado delas

NULL, Partial Index e múltiplas colunas

  • O SQLite oferece suporte a índices UNIQUE com valores NULL incluídos
    • O exemplo insere 1, vários NULL e 1000000, depois executa CREATE UNIQUE INDEX idx ON table_test (column1 ASC)
    • O índice visualizado parece armazenar apenas valores não nulos
  • Um Partial Index com a condição WHERE column1 IS NOT NULL filtra os valores NULL
    • Esse índice contém apenas uma Page
    • Isso leva a buscas mais rápidas do que no exemplo UNIQUE anterior
  • Um índice de múltiplas colunas armazena os dados de todos os campos em sequência dentro da Cell
    • O exemplo usa o índice (column1 ASC, column2 ASC)
    • Na visualização, os campos são separados por dois-pontos :

Momento de criação do índice e efeito da reconstrução

  • Foi feita a comparação entre criar o índice antes de inserir os dados e criá-lo depois que todos os dados já haviam sido inseridos
  • Quando novos dados são adicionados, a árvore precisa se rebalancear sozinha
  • Criar o índice de uma vez sobre dados já existentes pode ser muito mais eficiente
  • Os dois índices parecem semelhantes, mas o segundo, com menos Pages, pode ser mais rápido
  • O resultado da comparação com base em 1.000.000 Cells é o seguinte
Categoria Total de Pages Total de Cells
Criado antes da inserção 3342 1000000
Criado depois da inserção 2930 1000000
  • Uma otimização semelhante pode ser feita com VACUUM ou REINDEX
    • VACUUM recria índice e tabela junto com os dados
    • REINDEX idx recria apenas o índice
  • Nos exemplos, ambos os comandos reduziram o número de Pages de 3342 para 2930

Armazenamento do índice por tipo de dado

  • Dados de texto curtos são armazenados diretamente na Cell do índice, mas textos longos precisam ser armazenados separadamente
    • O exemplo insere de text-1 até text-1000000 e cria um índice column1 ASC
    • É possível verificar que as strings reais ficam armazenadas diretamente no índice
  • Dados REAL também foram armazenados no índice e visualizados
    • O exemplo usa os valores 1.14, 2.14, ..., 1000000.14
  • Também foi verificado um índice composto com inteiro e texto
    • O exemplo cria o índice (column1 ASC, column2 ASC) em uma tabela (column1 INT, column2 TEXT)
    • O inteiro e a string são armazenados juntos na mesma Cell, conforme definido na criação do índice

Como reproduzir e próximos passos

  • O experimento mostra como os índices do SQLite são estruturados, como os dados dos registros são armazenados na memória e como a B-Tree organiza e acessa os dados
  • A visualização é usada para analisar e comparar diferentes índices
  • Todos os exemplos podem ser reproduzidos com os seguintes comandos
    • docker run -it --rm -v "$PWD":/app/data --platform linux/x86_64 mrsuh/sqlite-index bash
    • sh bin/test-index.sh
  • O código e os exemplos estão em mrsuh/sqlite-index
  • Os próximos trabalhos são a visualização da busca baseada em índice e a exploração de algumas consultas SQL

Leituras relacionadas

1 comentários

 
GN⁺ 2024-11-16
Comentários do Hacker News

  • Cada linha de uma tabela SQLite tem, por padrão, um rowid único e já disseram que, se não houver chave primária explícita, ele funciona como chave primária, mas na prática o rowid é usado mesmo quando há chave primária
    Seria legal visualizar o índice da chave primária de uma tabela WITHOUT ROWID. Esse tipo de índice é especialmente interessante
    Mesmo que os dois índices pareçam parecidos, o fato de o segundo ter menos páginas não significa imediatamente que ele seja mais rápido. O importante é a altura da árvore e, depois disso, se após encontrar o valor no índice ainda é preciso ler o restante dos dados em uma tabela separada (rowid) ou se os dados já estão ali, como em WITHOUT ROWID. Isso faz bastante diferença especialmente em consultas de intervalo como where 50 <= col <= 100

    • Considerando apenas um acesso isolado, a altura da árvore faz sentido, mas se o índice for acessado com frequência, o tamanho total também pode ser muito importante para a taxa de acerto de cache
    • Há uma exceção para essa história de usar rowid mesmo com chave primária. Se você criar INTEGER PRIMARY KEY, o SQLite usa isso no lugar [1]
      [1]: https://sqlite.org/rowidtable.html

  • O SQLite é bem peculiar em quase tudo que faz, e acho que isso é ainda mais verdade no processamento de consultas
    O SQLite tende a preferir simplicidade em vez de desempenho, então muitas vezes implementa as coisas de um jeito diferente dos outros bancos de dados com que já trabalhei. O SQLite compete menos com outros bancos de dados e mais com arquivos JSON/XML para armazenamento persistente. Então olhar a implementação do SQLite não necessariamente ensina muito sobre como bancos de dados de fato fazem a mesma coisa

    • Ele compete com ambos. É verdade que o SQLite é usado como armazenamento persistente local, mas em situações em que não é necessário um processo de servidor separado, ele também compete com outros sistemas gerenciadores de bancos de dados relacionais
      Isso só quer dizer que os requisitos costumam ser bem diferentes, não que seu uso se limite a substituir arquivos JSON/XML
    • O SQLite é um motor de banco de dados de verdade. Provavelmente a ideia é mais que ele não compete com servidores de banco de dados
    • Não é tão diferente da forma como outros servidores de sistemas gerenciadores de bancos de dados tratam armazenamento e índices. Os princípios são quase os mesmos, especialmente quando o SQLite está operando em modo WAL

  • O site é tão agradável de ler que realmente dá vontade de ler

    • No iPhone, achei o tamanho da fonte do texto principal grande demais. O texto importante dentro dos diagramas é bem menor, então para ler o corpo do texto preciso afastar o celular do rosto e, para ler os diagramas, aproximá-lo de novo, o que fica estranho
    • É muito bom poder ver o conteúdo sem anúncios apertados por todos os lados. O texto também está muito bom

  • “indexes” também pode ser a forma verbal na terceira pessoa do singular de “to index” e também o plural de “index”. Já “indices” é o plural tradicional, usado especialmente em contextos de matemática e ciência
    No inglês geral, “indexes” é comum, mas na área técnica às vezes há preferência por indices por precisão linguística. Nesse contexto, usar “indices” pode melhorar a clareza ao distinguir o ato de indexar do plural de índice

    • Os dois estão corretos(https://www.nasdaq.com/articles/indexes-or-indices-whats-the...). A documentação do SQLite e do PostgreSQL, por exemplo, usa indexes
    • Tentar fazer o plural de “time series” não é fácil
      Na Finlândia, já vi usarem “time series” no plural e “time serie” no singular
    • Não sei com base em que autoridade isso está sendo afirmado
      Todos os principais sistemas gerenciadores de bancos de dados relacionais usam o termo indexes
    • Depende do público-alvo. Se for para a academia, use indices; se for para o público geral, “indices” pode soar pedante

  • Seria interessante ver também como o PostgreSQL faz a mesma coisa. Dá para aprender bastante comparando

  • Para ver vários layouts com menos trabalho, também poderia gerar TGF para o yEd