Resolvendo problema de performance no PostgreSQL com CTE

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.