Arquitetura dos Dados

Uma das primeiras coisas que aprendemos em SQL é o JOIN. A ideia parece bastante simples: combinar informações de duas tabelas relacionadas. Depois de alguns exemplos, a operação se torna tão natural que quase esquecemos o trabalho que existe por trás dela.

Foi exatamente isso que aconteceu comigo.

Durante muito tempo enxerguei o JOIN apenas como uma instrução da linguagem SQL. Bastava escrever algumas linhas e o banco de dados encontrava os registros correspondentes. Parecia quase uma operação gratuita.

Mas bastou estudar um pouco mais sobre a arquitetura dos bancos de dados para perceber que um JOIN pode facilmente se transformar em uma das consultas mais caras de um sistema.

O problema parece simples

Imagine duas tabelas bastante comuns.

clientes
id | nome
------------
1  | Arthur
2  | Maria
3  | João

pedidos
id | cliente_id | valor
-------------------------
1  |     2      | 350
2  |     1      | 120
3  |     1      | 500

Agora queremos descobrir quais pedidos pertencem a cada cliente.

SELECT
    c.nome,
    p.valor
FROM clientes c
JOIN pedidos p
    ON c.id = p.cliente_id;

O resultado parece trivial, mas a pergunta interessante não é qual será o resultado. É outra: Como o banco encontra essas correspondências?

Imagine fazendo isso manualmente

Suponha que existam apenas dez clientes. É fácil, você olha cada pedido e encontra o cliente correspondente. Agora imagine um milhão de clientes e cinquenta milhões de pedidos.

Se você tivesse que fazer essa tarefa manualmente, provavelmente começaria assim: pegaria o primeiro pedido, depois procuraria o cliente correspondente, depois faria exatamente a mesma busca para o segundo pedido, depois para o terceiro, depois para o quarto. Muito rapidamente perceberia que está repetindo a mesma operação milhões de vezes. Foi exatamente esse problema que os bancos de dados precisaram resolver.

A solução mais ingênua existe

O algoritmo mais simples possível faz exatamente isso.

Para cada cliente…

…procure todos os pedidos.

Cliente 1
↓
Pedido 1?
Pedido 2?
Pedido 3?
...
Pedido 50.000.000?

Depois repita tudo novamente para o Cliente 2, e depois para o Cliente 3.

O número de comparações cresce assustadoramente. Se existem N clientes e M pedidos, esse algoritmo pode precisar realizar aproximadamente N x M comparações.

Imagine:

1.000.000 clientes
×
50.000.000 pedidos

Estamos falando de 50 trilhões de comparações.

Claramente isso não escala. Esse algoritmo existe e recebe um nome pouco criativo, mas bastante descritivo: Nested Loop Join.

Então por que ele ainda existe?

Essa foi uma das perguntas que mais me surpreendeu. Se ele é tão caro, por que bancos modernos continuam utilizando Nested Loops? Porque custo depende do contexto.

Vamos pra outro exemplo:

clientes
10 registros

pedidos
50 milhões

Existe um índice em:

pedidos(cliente_id)

Agora a história muda completamente, para cada cliente, basta utilizar o índice para localizar seus pedidos. Em vez de percorrer cinquenta milhões de registros, o banco faz uma busca extremamente eficiente na B+ Tree. Curiosamente, um algoritmo considerado “ruim” pode ser a melhor escolha. Tudo depende dos dados.

Foi aqui que comecei a entender o Query Optimizer

Durante muito tempo imaginei que o banco simplesmente executasse o SQL exatamente da forma como escrevemos. Hoje sei que isso raramente acontece. Antes de executar a consulta, o banco constrói vários planos possíveis: Nested Loop, Hash Join, Merge Join. Depois estima o custo de cada um deles e só então decide qual será executado.

Foi justamente estudando o famoso artigo de Patricia Selinger (cito nesse texto aqui) que comecei a perceber que bancos de dados não procuram consultas corretas. Eles procuram consultas baratas.

Hash Join

Vamos supor outro cenário. As duas tabelas possuem milhões de registros, existe memória suficiente, talvez seja melhor construir uma Hash Table.

Clientes
↓
Hash Table
↓
Pedidos procuram diretamente

Agora encontrar um cliente deixa de exigir milhares de comparações, cada pedido consulta diretamente a tabela hash. O número de operações cai drasticamente, por isso Hash Join costuma ser extremamente eficiente para grandes volumes de dados.

Merge Join

Existe ainda outra possibilidade. Imagine que ambas as tabelas já estejam ordenadas pelo campo utilizado no JOIN. Nesse caso, não faz sentido construir uma Hash Table, também não faz sentido realizar milhões de buscas independentes. Basta caminhar pelas duas tabelas simultaneamente.

Clientes →
Pedidos →

Como duas pessoas folheando listas telefônicas em ordem alfabética, esse algoritmo recebe o nome de Merge Join.

Então qual deles é o melhor?

Foi justamente essa pergunta que me fez mudar a forma de estudar bancos de dados. A resposta é: depende.

Não existe um algoritmo universalmente melhor. Nested Loop pode ser excelente, Hash Join pode ser excelente, Merge Join pode ser excelente. Tudo depende de fatores como:

• quantidade de registros;
• índices disponíveis;
• distribuição dos dados;
• memória disponível;
• estatísticas da tabela.

É exatamente por isso que existe um Query Optimizer, ele tenta responder uma pergunta extremamente difícil, Qual algoritmo custará menos para esta consulta?

Você pode ver isso acontecendo

No PostgreSQL, por exemplo, basta executar:

EXPLAIN ANALYZE
SELECT
    c.nome,
    p.valor
FROM clientes c
JOIN pedidos p
ON c.id = p.cliente_id;

O resultado costuma mostrar algo parecido com isto.

Hash Join

ou

Nested Loop

ou

Merge Join

Naquele momento, o banco está revelando qual estratégia escolheu. E, mais interessante ainda, quanto custou essa decisão.

O que mudou na minha forma de pensar

Antes de estudar esse assunto, eu acreditava que escrever SQL significava dizer ao banco como executar uma consulta. Hoje percebo que fazemos algo bem diferente, nós apenas descrevemos o que queremos obter, o restante fica por conta do banco de dados.

Quando escrevemos um JOIN, não escolhemos algoritmos, não escolhemos estruturas de dados, não decidimos como as tabelas serão percorridas. Declaramos apenas o resultado esperado, cabe ao Query Optimizer encontrar o caminho mais barato para chegar até ele. Foi justamente por isso que passei a enxergar um JOIN de outra maneira, ele deixou de ser apenas uma cláusula do SQL e passou a ser uma pergunta extremamente complexa que fazemos ao banco de dados:

“Qual é a forma mais eficiente de combinar essas duas tabelas?”

E talvez seja essa a principal razão pela qual um simples JOIN pode consumir milissegundos… ou vários minutos.