JavaScript pode ser 2x mais rápido que C: Otimizando o SQLite
Nessa semana eu me dei um desafio interessante: quero reescrever o SQLite em JavaScript, mas com o máximo de performance possível. Claro que seria uma prova de conceito, o SQLite é uma biblioteca bem grande, e claro que a minha performance seria significativamente inferior que a do SQLite original, escrito em C, mas eu queria saber o quão perto era possível chegar. Para minha surpresa, o meu experimento foi capaz de superar o SQLite original em tempo de execução! Conto aqui como isso foi possível.
TLDR: Vamos utilizar WebAssembly gerado dinamicamente.
Antes de mais nada, o que é o SQLite?
Se você já é super familiar com o SQLite, pode pular essa sessão.
O SQLite é, de longe, o banco de dados mais popular do mundo. O seu celular provavelmente contém algumas dezenas de instalações dele neste momento, por exemplo. O diferencial é que ele é super compacto. Todos os dados ficam salvos em um único arquivo e, diferente de quase todos os outros bancos de dados, ele é uma biblioteca embutida na sua aplicação, não um servidor separado que você se conecta para consultar. Se você já fez qualquer desenvolvimento mobile, com certeza já utilizou direta ou indiretamente.
Ele é todo desenvolvido em C, com código disponível em domínio público. No entanto ele não é "open source" de fato, é desenvolvido por uma equipe muito enxuta e não aceitam contribuições externas. Ele se monetiza vendendo consultoria e vendendo o desenvolvimento de features nele para quem precisar. Além disso todos os testes unitários dele são código fechado e proprietário. É um caso bem peculiar, não conheço outros assim.
Tanto que a Turso recentemente anunciou o LibSQL, que é um fork open source do SQLite, visando mudar essa realidade. E mais recentemente ainda anunciaram o Limbo, uma tentativa de reescrever o SQLite do zero em Rust para modernizar o código e adicionar algumas funcionalidades de alto impacto, como async IO. É polêmico e interessante o que estão fazendo, mas não vou entrar nesse mérito agora.
Qual o plano?
Em média a performance de JavaScript bem escrito tende a ser 2x inferior à performance de código equivalente em uma linguagem nativa como C. Então a forma de otimizar performance precisa vir através de alguma outra técnica que me dê muito mais do que 2x, para compensar isso. Lembrando que não quero mudar a funcionalidade em si do SQLite.
Vamos revisar como o SQLite funciona. Ele é dividido em 3 camadas: o Compilador de SQL, uma Máquina Virtual e o Armazenamento.
Camada #1: Compilador de SQL
Tudo começa com uma query escrita em SQL. Para o SQLite isso é apenas uma string, então o primeiro passo é fazer um parse para extrair a estrutura e semântica dessa query. É nesse momento que as palavras chaves como SELECT e WHERE são entendidas, que as expressões são organizadas e as colunas são conectadas às suas respectivas tabelas para a análise de tipos. Por exemplo:
SELECT name, age
FROM people
WHERE age >= 18
LIMIT 10Essa query vai selecionar os nomes e idades de 10 pessoas maiores de idade. O resultado dessa análise será uma árvore semelhante a essa aqui:
Ainda dentro dessa camada precisamos planejar como essa query será executada. Toda a graça do SQL é que você descreve de onde vem o resultado que você quer, mas não descreve como a consulta deve obter esse resultado. Quase sempre existem várias estratégias possíveis e o banco de dados precisará escolher uma dessas estratégias. Neste caso o plano mais simples é o de percorrer toda a tabela de pessoas uma linha de cada vez e verificar o age dessa linha, se for >= 18, então será incluída no resultado, até que 10 linhas sejam encontradas. No pior caso esse plano pode percorrer 100% das pessoas e não encontrar ninguém que encaixe nos filtros!
Outro plano possível nesse caso seria utilizar um índice na couna age, se existir. O índice é basicamente uma cópia da tabela ordenada por essa coluna. Então se queremos os maiores de 18 podemos pular nesse índice diretamente para a primeira posição que o número 18 aparece e começar a ler a partir dalí, simplesmente entregando as primeiras 10 linhas que aparecerem. Muito mais rápido.
O planejado do banco de dados precisa avaliar os planos possíveis, estimar qual será o mais eficiênte para essa query e concretizar o plano. Podemos pedir detalhes do plano atual colocando EXPLAIN na frente do comando SQL. Neste caso, e assumindo que o índice exista, este será o plano:
Plan: SEARCH people USING INDEX people_age (age>?)
Bytecode:
0: Init(13)
// Inicia a execução e salta para linha 13.
1: Integer(10, 1)
// Carrega o valor 10 na variável $1.
2: OpenRead(0, "people")
// Abre um cursor para a tabela 'people' com ID 0.
3: OpenRead(1, "people_age")
// Abre um cursor para o índice 'people_age' com ID 1.
4: Integer(18, 2)
// Carrega o valor 18 na variável $2.
5: SeekGE(1, 12, 2)
// Move o cursor de ID 1 para o primeiro elemento >=
// o valor apontado pela variável $2. Se não encontrar,
// salta para linha 12. Ou seja: busca age >= 18.
6: DeferredSeek(1, 0)
// Altera o cursor de ID 0 para a mesma linha do ID 1.
7: Column(0, 0, 3)
// Lê a coluna 'name' do cursor de ID 0 na variável $3.
8: Column(1, 0, 4)
// Lê a coluna 'age' do cursor de ID 1 na variável $4.
9: ResultRow(3, 2)
// Cria uma linha de resultado com as variáveis $3 e $4.
10: DecrJumpZero(1, 12)
// Subtrai 1 da variável $1 e salta para linha 12 se der 0.
11: Next(1, 6)
// Avança o cursor de ID 1 para o próximo registro e salta
// para linha 6 se não estiver no fim da tabela.
12: Halt()
// Encerra a execução.
13: Transaction()
// Inicia uma transação de leitura.
14: Goto(1)
// Pula para a linha 1.Os comentários foram adicionados por mim para facilitar o entendimento. Repare como o comando DecrJumpZero cria um loop de 10 elementos. Se o índice não existisse esse plano seria bem diferente, embora desse o mesmo resultado, experimente! Detalhes sobre todos os comandos disponíveis podem ser encontrados na documentação do SQLite.
Note que o resultado final do Compilador de SQL após receber o texto é uma sequência de comandos primitivos e concretos que podem ser executados passo a passo para produzir o resultado da consulta, já utilizando detalhes deste banco, como índices e afins. O plano pode ser reaproveitado se a mesma query for executada novamente, o que salva tempo.
Camada #2: Máquina Virtual
O nome “máquina virtual” pode fazer essa camada parecer mais complicada do que ela realmente é. Ela é responsável por receber um plano concreto (aquela sequência de comandos) e seguir esses comandos passo a passo até entregar o resultado final. É um grande loop com um grande switch dentro, em outras palavras: um interpretador.
Isso vai permitir executar toda a lógica desse plano, mantendo o valor das variáveis e dos cursores a cada passo e sabendo para qual comando saltar após cada passo. A única coisa que falta é entender como esses cursores funcionam para ler as tabelas.
Camada #3: Armazenamento
Aqui finalmente chegamos na parte de dados do banco de dados. O que essa camada faz é prover algumas funções e operadores básicos para a máquina virtual poder utilizar. Em sua grande maioria esses vem na forma de cursores. Você pode abrir um cursor para uma tabela, mover esse cursor ou um passo por vez ou saltar para uma posição específica na tabela. E quando eu falo de tabela, isso inclui índices também.
No caso do SQLite todos os dados estão em um único arquivo que é organizado em blocos de mesmo tamanho chamados “páginas”. Cada página guarda um pedaço de uma tabela, na forma de uma BTree+. Não vou entrar agora no nível de detalhe de como essas árvores funcionam, mas praticamente todo banco de dados utiliza ou BTree+ ou LSM Tree para armazenar seus dados em arquivos.
Finalmente, o plano
Se quero que a minha implementação em JavaScript possa competir em performance preciso encontrar um ponto de melhora significativo em alguma dessas 3 camadas.
A primeira é bastante complexa e evoluiu ao longo de décadas. Encontro alguns casos de queries em que eu conseguiria gerar um plano melhor do que o SQLite gera, mas são sempre casos bem específicos. A lógica de calcular o plano também não consome um tempo significativo para ser relevante.
A terceira camada é basicamente centrada em implementar operadores de BTree e paginação com cache. Tem bem pouco espaço para melhorar aqui se eu impuser a restrição de que não quero mudar o layout do arquivo que o SQLite utiliza hoje. Se a gente fosse mudar a estrutura desse arquivo, teríamos bastante espaço para melhorar isso, a começar por remover os “varints” que gastam CPU para ler e não economizam muito espaço, mas podendo avançar para uma estrutura colunar potencialmente utilizando LSM. De todo modo, isso já começa a se aproximar do que o DuckDB faz, que é uma alternativa forte ao SQLite.
Já na segunda camada vejo muito espaço! Ela é um interpretador, simples e direto. E se a gente pudesse transformar esse bytecode do SQLite em código nativo usando JIT e então simplesmente executar esse código nativo? Isso seria uma ordem de magnitude de melhora em performance. Em vez de executar um comando de cada vez podemos deixar a CPU fazer isso diretamente. Essa ideia é um pouco inusitada para um banco de dados, mas o SQLite já é tão rápido que precisamos atacar em algum lugar.
Mas aguarde um momento, estamos falando de JavaScript, como vamos compilar e executar código nativo?
Gerando WebAssembly dinamicamente
WebAssembly não te permite fazer nada que você já não consiga fazer com JavaScript, ele apenas faz isso mais rápido. Na prática é uma segunda linguagem na web, binária e bem mais limitada em funcionalidades. Por outro lado ela pode ser executada muito mais rápido pelo navegador já que é muito mais parecida com código nativo.
Em geral, a maioria dos códigos não podem ser convertidos para WebAssembly pois interagem com a DOM ou com objetos JavaScript. Mas se o seu código encaixa dentro das limitações, pode ter um salto significativo de performance. Vem sendo usado bastante para renderização, jogos e para calculo numérico intenso. Também abre espaço para várias linguagens que podem ser compiladas eficientemente para WebAssembly participarem da Web em primeira classe, como Rust, C++, C#, Dart, Go, etc.
Mas assim como o código em JavaScript pode ser visto como uma string que você pode chamar com eval, o código WebAssembly é um ArrayBuffer que você pode instanciar e executar.
Nosso plano será:
Receber o SQL em texto e fazer o parse e construção da árvore sintática.
Decidir um plano de execução.
Gerar os comandos desse plano de execução na forma de um módulo WebAssembly.
E assim executar a query será o mesmo que simplesmente executar o módulo WebAssembly, nenhum interpretador necessário.
Claro, precisamos também implementar a camada de armazenamento, com toda a lógica de cursores para navegar pelos dados.
Isso talvez seja o suficiente para a minha implementação do SQLite em JavaScript ser competitiva com a implementação original. Resolvi prototipar esse experimento para descobrir.
O protótipo
Para validar o experimento decidi implementar apenas um tipo de query inicialmente, que fosse simples em escopo, mas que pudesse demorar tempo executando, para ser válido: SELECT count(*) FROM table. Claro que eu poderia dar seguimento a implementar todo o resto do SQLite, mas seria um projeto de muitos meses e não de alguns dias.
Para o parse utilize o Chevrotrain. É uma biblioteca em que você pode expressar a gramática de uma linguagem e ela realizará o parse produzindo a AST ou uma sequência de ações. O diferencial dela, além da boa performance, é que não é um gerador de código, significando que eu posso modificar as regras do parser em runtime. Poderia, por exemplo, implementar extensões do SQLite que teriam a capacidade de adicionar novas regras de sintaxe como statements novos ou expressões novas. Até onde sei, isso nunca foi feito, seria interessante. De todo modo, o nosso foco agora não está no parsing.
Na outra ponta, implementei a leitura do arquivo em páginas. Não é um trabalho difícil, porém é bastante minucioso em entender o exato significado de cada byte do arquivo. A primeira página guarda 100 bytes de header, com algumas informações gerais e na sequência cada página pode ser um nó intermediário ou um nó folha de uma BTree, que represente ou uma tabela ou um índice.
Essa lógica é dividida em uma parte JavaScript que faz a leitura crua do arquivo e gerencia um cache de páginas e uma outra parte escrita em WebAssembly na mão que lê os bytes e implementa cursores. Assim pode ser oferecida uma API de armazenamento para a query utilizar. Isso vai ficar claro logo mais.
E por fim temos o planejador, que recebe a AST de uma query e deve produzir o binário de um módulo WebAssembly equivalente. Para isso escrevi um gerador de código em TypeScript pondo boa parte das regras de validação do WebAssembly no sistema de tipos, de forma que não seja possível emitir um código inválido. Isso já bloqueia vários possíveis bugs.
Para todos os testes vou utilizar um banco de dados sobre bicicletas da HubWay, disponível nesse artigo https://www.dataquest.io/blog/sql-basics/. Este banco possui uma tabela trips com 1.5 milhões de linhas.
Com a query SELECT count(*) FROM trips o meu programa gera o seguinte código:
(func $query (export "query") (result i32)
// Declara 3 variáveis
(local $counter i32) (local $cursor i32) (local $is_valid i32)
// Cria um novo cursor, chamando uma função predefinida
(local.set $cursor
(call $runtime.cursor_alloc))
// Move o cursor para a primeira linha da tabela 2 (trips)
(local.set $is_valid
(call $runtime.cursor_init_first_row
(local.get $cursor)
(i32.const 2)))
// Começa um loop, enquanto $is_valid for true
(loop
(if
(local.get $is_valid)
(then
// Incrementa o contador
(local.set $counter
(i32.add
(local.get $counter)
(i32.const 1)))
// Avança o cursor para a próxima linha
(local.set $is_valid
(call $runtime.cursor_next
(local.get $cursor)))
(br 1))))
// Aqui $is_valid se tornou false, chegamos ao fim da tabela
// Libera a memória utilizada pelo cursor
(call $runtime.free
(local.get $cursor))
// Retorna o contador
(local.get $counter)
)Isso seria aproximadamente equivalente ao seguinte código:
function query() {
const cursor = cursor_alloc();
let is_valid = cursor_init_first_row(cursor, 2);
let counter = 0;
while (is_valid) {
counter++;
is_valid = cursor_next(cursor);
}
free(cursor);
return counter;
}Em uma query mais complexa essa função poderia receber argumentos e retornar múltiplas linhas iterativamente. Mas agora tendo o nosso compilador de SQL que recebe uma string e retorna o módulo WebAssembly acima, e tendo a nossa camada de runtime que implementa as funções de cursores baseado no arquivo no formato do SQLite, temos tudo o necessário para executar alguns testes.
Por referência vamos começar com o próprio SQLite, utilizando o módulo node:sqlite do Node.js 22.
Primeira query (cache zerado):
47.281msPróximas queries (cache aquecido):
13.535ms
Bem rápido. E aqui já fica clara a diferença entre ter ou não ter cache. Quando o cache já está aquecido toda a tabela está em memória e não é necessário mais pagar o custo de acessar o disco. Para muitos dos casos de uso do SQLite, será comum todos os dados estarem em memória.
Agora executando o meu protótipo, temos números interessantes:
Primeira query (cache zerado):
2.970sPróximas queries (ainda com cache zerado):
299.485msPróximas queries (cache aquecido):
6.581ms
Sim, foram TRÊS SEGUNDOS para executar essa query, mas isso vem da natureza do JavaScript e do WebAssembly: eles utilizam JIT. Da primeira vez que qualquer código roda ele será muito lento pois o navegador ou o Node.js está justamente consumindo tempo para otimizar esse código. Geralmente esse primeiro número nem é mostrado na maioria dos benchmarks. O SQLite ganha indiscutivelmente aqui por ser código em C já pré-compilado. Não há um preço a pagar na primeira execução.
Nas próximas execuções, ainda sem ativar o cache, temos 300ms. Quer dizer que estamos fazendo IO significativamente mais lentamente que o SQLite.
Por outro lado, quando os dados já estão em cache, o que acontece a partir da segunda execução da query, temos um tempo abaixo de 7ms. Isso mesmo, essa solução é 2x mais rápida que o SQLite. Por essa eu não esperava.
Mas ainda podemos melhorar. Esse tempo lento de acesso ao disco vem do fato de estarmos utilizando async para fazer a leitura, com Promises. Aparentemente o V8 não otimiza bem interações entre WebAssembly e Promises ainda. Se trocar-mos todo o IO para ser sync (igual a como o SQLite faz), temos esses números:
Primeira query (cache zerado):
255.643msPróximas queries (ainda com cache zerado):
51.468msPróximas queries (cache aquecido):
6.581ms
Subtamente temos números muito mais razoáveis. Repare que se a gente desconsiderar a primeira query, em que o JIT ainda tem um efeito muito forte, o restante está basicamente igual ou significativamente melhor que o SQLite. Este foi um ganho acima do esperado.
Próximos passos
A conclusão é que o interpretador de bytecode do SQLite é uma oportunidade ainda não explorada. Fica relevante quando é uma query pesada, como esse count, mas também vale para consultas mais complexas como muitos joins, agregações e relatórios. Também vale para consultas repetidas, que sejam executadas muitas vezes.
Tudo isso me lembra de um artigo que li uns 2 anos atrás: Fast Compilation and Execution of SQL Queries with WebAssembly.
O mesmo que eu implementei em JavaScript poderia também ser implementado em C ou em Rust no Limbo. Uma abordagem é receber o bytecode que já existe hoje é transformar este para WebAssembly, ou até utilizar o Cranelift para ir direto para código nativo. Precisa ser uma funcionalidade opcional, claro, mas pode ser um bom boost para prepared statements. É parecido com o que o PostgreSQL faz com o LLVM.
Quem sabe no futuro eu explore essa possibilidade também.