Spoiler: a query ficou 23x mais rápida com CTE's apenas transformando o problema quadrático em linear. Sem índices.
Um dos cenários mais comuns de problemas de performance em software é o famoso nested loop.
Com o banco de dados não é diferente. Por vezes podemos acabar por escrever queries que apresentam complexidade quadrática, onde nossa primeira solução óbvia para melhorar a performance seria através da criação de índices.
Neste artigo vou mostrar uma alternativa para este problema de nested loops em queries sem criar índices, apenas utilizando CTE's, ou Common Table Expressions.
Setup
O setup deste artigo contém basicamente 3 tabelas contendo:
- 200 users
- 20 bancos
- 4000 contas bancárias
- 4000 transferências feitas entre diferentes contas
Nota: no final do artigo compartilho o link para o Gist com o código completo.
Desafio
A ideia é que a query retorne a lista com todas as contas de diferentes bancos com seus respectivos saldos calculados:
Query com múltiplos JOIN's e SUM aggregate
A princípio, podemos escrever uma query que, a partir da tabela de users, faça JOIN com as tabelas banco, accounts e transfers, tal como a seguir:
SELECT
users.name AS username,
banks.name AS bank,
SUM(CASE
WHEN accounts.id = transfers.source_account_id
THEN transfers.amount * -1
WHEN accounts.id = transfers.target_account_id
THEN transfers.amount
ELSE
0.00
END)
AS balance
FROM
users
JOIN accounts ON accounts.user_id = users.id
JOIN banks ON banks.id = accounts.bank_idq
LEFT JOIN transfers ON
transfers.source_account_id = accounts.id
OR transfers.target_account_id = accounts.id
GROUP BY users.name, banks.name
ORDER BY username ASC, balance ASC
Ao executarmos a query com EXPLAIN no PgAdmin4, temos esta imagem que mostra o nested loop sendo utilizado e seu custo associado:
Com um total cost de 280k no JOIN com transfers. Ou seja, é mesmo ali que está o gargalo na nossa query, que totaliza uma demora de 7000ms (7 segundos) em média.
Índices?
Uma possível solução passa por criar índices. Neste nosso exemplo, cheguei a criar o índice na tabela de transfers (onde está acontecendo o nested loop):
DROP INDEX IF EXISTS transfers_in, transfers_out;
CREATE INDEX transfers_in ON transfers (target_account_id);
CREATE INDEX transfers_out ON transfers (source_account_id);
...o que reduziu a query de 7000ms para 400ms (melhoria gigante), mas o índice tem um custo: a cada escrita na tabela transfer, o índice é atualizado.
Ok, mas há alternativa para este caso específico sem criação de índices?
Nota: em apps de produção, é muito comum a utilização de índices. Mas não podemos abusar de índices por causa do impacto na escrita, pelo que estes têm de ser analisados e utilizados com parcimônia.
Reduzindo a complexidade do nested loop
Como já podemos saber, a melhor forma de resolver um algoritmo de complexidade quadrática (nested loops) é reduzindo-o para linear, logarítmica ou até mesmo, constante.
Neste caso, analisamos que o melhor que podemos conseguir é reduzindo para linear, ou seja, percorrendo a tabela transfers 1 ou 2 ou 3 vezes se for o caso, mas não de forma aninhada (nested).
Como podemos então fazer? Criar uma query com SELECTs e Sub-SELECTs? Talvez, mas a query ficaria enorme e bastante difícil de manter.
CTE's for the rescue
Sabemos que com CTE's, podemos organizar melhor nossas queries, quebrando uma query grande em diversas queries pequenas, facilitando a compreensão da mesma.
E de quebra, isto pode ajudar a melhorar a performance, se conseguirmos escrever bem a query de forma linear (e não nested).
WITH
accounts_idx AS(
SELECT
accounts.id AS account_id,
users.name AS username,
banks.name AS bank
FROM accounts
JOIN users ON users.id = accounts.user_id
JOIN banks ON banks.id = accounts.bank_id
),
accounts_from AS (
SELECT
idx.username,
idx.bank,
SUM(transfers.amount * -1) AS balance
FROM transfers
JOIN accounts_idx idx ON idx.account_id = transfers.source_account_id
GROUP BY idx.username, idx.bank
),
accounts_to AS (
SELECT
idx.username,
idx.bank,
SUM(transfers.amount) AS balance
FROM transfers
JOIN accounts_idx idx ON idx.account_id = transfers.target_account_id
GROUP BY idx.username, idx.bank
),
results AS (
SELECT * FROM accounts_from
UNION
SELECT * FROM accounts_to
)
SELECT
username,
bank,
SUM(balance) AS balance
FROM results
GROUP BY username, bank
ORDER BY username ASC, balance ASC
Com o WITH do PostgreSQL, estamos criando 4 tabelas temporárias que estarão ativas apenas durante a execução da transação da query:
- accounts_idx, guarda a info dos users e bancos em uma hash
- accounts_from, percorre a tabela "transfers" buscando por saídas em contas
- accounts_to, percorre a tabela "transfers" buscando por entradas em contas
- results, que faz a UNION das CTE's
Esta é a técnica por trás da escrita de um código linear. O JOIN com OR na tabela transfers foi completamente removido!
E sobre o UNION, o truque é que, ao garantirmos que as CTE's têm a mesma quantidade de colunas, podemos projetar como um append, exatamente como na união de conjuntos.
Analisando a query com CTE's
Agora podemos novamente analisar com EXPLAIN no PgAdmin4:
Podemos reparar que já não há mais o node de Nested Loop, pelo que é feito um CTE scan primeiro, que garante que os dados serão materializados de forma linear e posteriormente agregados e filtrados na query.
Com isto, a query reduziu de 7000ms para 300ms! Sem necessidade de índices!
Conclusão
Apesar de haver drawbacks com o uso de CTE's, pois podem ser materializadas sem necessidade e ocupar espaço demasiado, o uso consciente com query planner (EXPLAIN) pode ser um bom aliado para terminarmos com um código modular e performático sem abusar de índices!
Segue link para o gist.
Top comments (6)
Otimo post Leandro, eu uso bastante CTEs principalmente para gerar dados direito do banco transacional.
Uma outra alternativa, ou complemento, que talvez até melhore os 300ms, é usar views materializadas, quando os dados não precisam ser realtime, as views materializadas são uma mão na roda, precisa só tomar o cuidado de agendar corretamente a refresh dela.
Eu combino bastante CTEs com views materializadas, a grande vantagem dela é que a aplicação entendem ela como uma tabela, isso faz com que você consiga usar ela com qualquer ORM disponivel sem dor de cabeça.
valeu Duke! parece uma ótima combinação mesmo, views materializadas com CTE's!
Muito interessante, sempre tive uma pulga atrás da orelha sobre a utilização de views para melhorar o planing time das consultas, porém essa abordagem com CTEs parece ser mais interessante, não conhecia esse recurso e fico feliz em descobrir.
O PostgreSQL sempre tem um recurso que não conhecemos, é incrível isso.
Muito interessante o artigo, não conhecia essa aproximação para criação de tabelas temporárias.
Parabéns!
ótimo artigo, parabéns!!
Finalmente vejo uma explicação clara do uso da cláusula WITH. Obrigado!