Resolvendo problema de performance no PostgreSQL com CTE

Spoiler: a query ficou 23x mais rpida com CTE's apenas transformando o problema quadrtico em linear. Sem ndices.

Um dos cenrios mais comuns de problemas de performance em software o famoso nested loop.

Com o banco de dados no diferente. Por vezes podemos acabar por escrever queries que apresentam complexidade quadrtica, onde nossa primeira soluo bvia para melhorar a performance seria atravs da criao 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 contm basicamente 3 tabelas contendo:

• 200 users
• 20 bancos
• 4000 contas bancrias
• 4000 transferncias feitas entre diferentes contas

Nota: no final do artigo compartilho o link para o Gist com o cdigo completo.

Desafio

A ideia que a query retorne a lista com todas as contas de diferentes bancos com seus respectivos saldos calculados:

Query com mltiplos JOIN's e SUM aggregate

A princpio, podemos escrever uma query que, a partir da tabela de users, faa 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 balanceFROM    usersJOIN accounts ON accounts.user_id = users.idJOIN banks ON banks.id = accounts.bank_idqLEFT JOIN transfers ON    transfers.source_account_id = accounts.id    OR transfers.target_account_id = accounts.idGROUP BY users.name, banks.nameORDER 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 mdia.

ndices?

Uma possvel soluo 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 especfico sem criao de ndices?

Nota: em apps de produo, muito comum a utilizao de ndices. Mas no podemos abusar de ndices por causa do impacto na escrita, pelo que estes tm de ser analisados e utilizados com parcimnia.

Reduzindo a complexidade do nested loop

Como j podemos saber, a melhor forma de resolver um algoritmo de complexidade quadrtica (nested loops) reduzindo-o para linear, logartmica 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 no de forma aninhada (nested).

Como podemos ento fazer? Criar uma query com SELECTs e Sub-SELECTs? Talvez, mas a query ficaria enorme e bastante difcil 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 compreenso da mesma.

E de quebra, isto pode ajudar a melhorar a performance, se conseguirmos escrever bem a query de forma linear (e no 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 balanceFROM resultsGROUP BY username, bankORDER BY username ASC, balance ASC

Com o WITH do PostgreSQL, estamos criando 4 tabelas temporrias que estaro ativas apenas durante a execuo da transao da query:

• accounts_idx, guarda a info dos users e bancos em uma hash
• accounts_from, percorre a tabela "transfers" buscando por sadas em contas
• accounts_to, percorre a tabela "transfers" buscando por entradas em contas
• results, que faz a UNION das CTE's

Esta a tcnica por trs da escrita de um cdigo linear. O JOIN com OR na tabela transfers foi completamente removido!

E sobre o UNION, o truque que, ao garantirmos que as CTE's tm a mesma quantidade de colunas, podemos projetar como um append, exatamente como na unio de conjuntos.

Analisando a query com CTE's

Agora podemos novamente analisar com EXPLAIN no PgAdmin4:

Podemos reparar que j no h mais o node de Nested Loop, pelo que feito um CTE scan primeiro, que garante que os dados sero materializados de forma linear e posteriormente agregados e filtrados na query.

Com isto, a query reduziu de 7000ms para 300ms! Sem necessidade de ndices!

Concluso

Apesar de haver drawbacks com o uso de CTE's, pois podem ser materializadas sem necessidade e ocupar espao demasiado, o uso consciente com query planner (EXPLAIN) pode ser um bom aliado para terminarmos com um cdigo modular e performtico sem abusar de ndices!

Segue link para o gist.