SQLite 10 vezes mais rápido com filtro de Bloom

• O SQLite é um armazenamento orientado a linhas, gravado em disco em uma estrutura de árvore B, e executa consultas usando uma máquina virtual chamada VDBE. Ele é independente de plataforma e pode rodar em thread única em praticamente qualquer ambiente
• Embora seja um banco de dados de uso geral, se destaca em cargas OLTP. Em 2015, pesquisadores da Universidade de Buffalo descobriram que a maioria das consultas era composta por buscas simples de chave-valor e consultas OLAP complexas
• Pesquisadores da Universidade de Wisconsin-Madison trabalharam para tornar as consultas analíticas mais rápidas. Compararam o desempenho usando DuckDB e o Star Schema Benchmark (SSB)

Causa

• Para identificar por que o SQLite era lento, usaram a opção VDBE_PROFILE para medir os ciclos de CPU consumidos por cada instrução da VDBE.
• Dois opcodes, SeekRowID e Column, foram identificados como os principais responsáveis.

Junção de bancos de dados

• Entre as formas de implementar junções em bancos de dados estão nested loop join, hash join e sort-merge join.
• O SQLite usa o mais simples, o "nested loop join". Isso se assemelha a uma busca em árvore B e tem custo elevado.

A importância da otimização de junções

• Nas operações de junção, a ordem das tabelas é importante. Mudar a ordem pode reduzir bastante o número de operações. Isso é um problema NP-difícil.
• Existem dois algoritmos de junção melhores que o nested loop join, mas o hash join consome muita memória, e o SQLite costuma rodar em ambientes com restrição de memória.
• Os pesquisadores usaram filtros de Bloom para melhorar a eficiência de espaço e se ajustar às linhas de cache da CPU. Foram adicionados dois opcodes, Filter e FilterAdd.

Resultado

• Após a otimização, na análise de ciclos de CPU, as grandes barras azuis praticamente desapareceram.
• O SQLite ficou de 7 a 10 vezes mais rápido. Esse resultado de pesquisa foi aplicado ao SQLite v3.38.0.
• Os filtros de Bloom se encaixam bem na implementação simples do SQLite com sobrecarga mínima de memória e funcionam dentro do mecanismo de consultas existente

[porteleaf]

Acabei de verificar a versão, e esse sistema está usando a 3.42.0. No momento, a mais recente é a 3.47.2.

[halfenif]

Acho que vou ter que verificar qual versão do SQLite estou usando agora.

Na verdade, mais do que isso, estou gerando arquivos do Excel usando openpyxl, mas está levando muito tempo, então preciso procurar se existe alguma outra biblioteca.

[savvykang]

Não seria melhor fazer um profiling?