Otimização de query: findChildrenTree() e similares

[filipedeschamps]

Contexto

Hoje, se eu não me engano, a query mais pesada do sistema inteiro é esta aqui:

tabnews.com.br/models/content.js

Line 772 in 0bbb0f6

async function findChildrenTree(options) {

Ela monta a árvore de respostas de um conteúdo e, para isso, de forma recursiva ela vai calculando a relação entre os conteúdos usando o parent_id e isto é bastante pesado dependendo da quantidade de interações que uma publicação receber.

Além disto, este tipo de recursão é utilizada em outras situações, como por exemplo contar a quantidade de comentários:

tabnews.com.br/models/content.js

Lines 124 to 151 in 0bbb0f6

	(
	WITH RECURSIVE children AS (
	SELECT
	id,
	parent_id
	FROM
	contents as all_contents
	WHERE
	all_contents.id = contents.id AND
	all_contents.status = 'published'
	UNION ALL
	SELECT
	all_contents.id,
	all_contents.parent_id
	FROM
	contents as all_contents
	INNER JOIN
	children ON all_contents.parent_id = children.id
	WHERE
	all_contents.status = 'published'
	)
	SELECT
	count(children.id)::integer
	FROM
	children
	WHERE
	children.id NOT IN (contents.id)
	) as children_deep_count

Há outros lugares dentro deste model que calculamos a quantidade de filhos para colocar em children_deep_count.

Execução

Com isto, sugiro adicionar um novo campo root_id na tabela contents que contém e congela o id do primeiro conteúdo (o conteúdo root), onde este id é replicado para todos os conteúdos children, para depois colocar um índice e adicionar na recursão a procura por este campo, onde eu especulo que irá acelerar muito o retorno da consulta.

E destaco o fato de "congelar" o id no root_id, pois hoje a nossa árvore de conteúdos é fluída, onde ao alterar o parent_id de uma publicação existente você pode mover um nó de conteúdo de uma discussão para outra. Altas feature massa que nunca foi usada e acabou sendo uma otimização prematura (e que pode ser solucionada de outra formas melhores).

Então devemos remover a possibilidade de alguém conseguir fazer um PATCH com essa propriedade, e isto irá quebrar todos os testes que envolvem "parent_id", como este:

tabnews.com.br/tests/integration/api/v1/contents/[username]/[slug]/patch.test.js

Line 2612 in 0bbb0f6

test('Content with "parent_id" declared solely', async () => {

E para fazer isso, eu iniciaria pelo controller que recebe o PATCH. O body que é enviado na request passa por essa validação:

tabnews.com.br/pages/api/v1/contents/[username]/[slug]/index.public.js

Lines 68 to 75 in 0bbb0f6

	const cleanBodyValues = validator(request.body, {
	parent_id: 'optional',
	slug: 'optional',
	title: 'optional',
	body: 'optional',
	status: 'optional',
	source_url: 'optional',
	});

Onde neste caso, basta remover por completo a linha parent_id: 'optional' que irá fazer o validator remover esta propriedade antes de passar para frente. Então a primeira coisa que eu faria é remover esta linha, rodas os testes e ver o que acontece (e como avançar dali para frente). Por último, eu escreveria um novo teste para provar que enviar um parent_id não faz nada com o conteúdo.

E por hora, o root_id não precisa ser retornado na interface pública da API eu especulo, e seria apenas um recurso interno para otimização.

Esta alteração envolve anunciar uma Breaking Change na API antes de ser aplicada, mas que não será um problema, pois novamente, eu especulo que ninguém esteja utilizando esta feature.

[FabricioFFC]

Fiz um teste com o root_id e realmente o ganho é muito bom. Além disso, com ele conseguimos tirar a complexidade do RECURSIVE e problemas de performance caso a recursão da árvore de contents seja grande.

Comparação dos resultados dos tempos do explain:

	Planning time	Execution time
Query atual	0.360 ms	1.537 ms
Query usando o root_id	0.154 ms	0.170 ms

E vale adicionar, que rodei o explain com diferentes tamanhos da árvore, e conforme ela vai crescendo, a query atual vai degradando, enquanto a query usando o root_id não degrada, justamente por não ter o uso da recursão.

[filipedeschamps]

Cara que sensacionaaaal!!!!! Isso vai ser uma das maiores contribuições de performance da Milestone e vai dar para habilitar novamente o autorefresh dos conteúdos das listas 🎉🎉🎉

[aprendendofelipe]

Turma, andei estudando como otimizar essas consultas, e eliminar as recursivas, e chegue na conclusão de que a solução materialized_path vai nos atender bem melhor.

Basicamente vamos ter uma coluna do tipo uuid[] com todos os id superiores ao conteúdo, do root_id até o parent_id, ao invés de ter apenas o root_id. E a cada novo filho que for adicionado só será preciso concatenar com o array do seu pai. Não muito diferente do que iríamos fazer com root_id, que era só usar o mesmo dado do pai.

Só que com isso podemos buscar qualquer árvore, pois é só filtrar como WHERE 'conten_id' = ANY(materialized_path), o que deve ser muito eficiente com um índice gin.

O que acham?

[filipedeschamps]

Continuando o que foi escrito no #1413 (comment)

A complexidade das duas implementações é a mesma, mas as vantagens são muito maiores para materialized_path, pois poderemos buscar qualquer trecho da árvore de comentários sem precisar de recursiva.

Geniaaaaal!!!! Faz total sentido!

Minha única preocupação é o quanto isto vai otimizar no tempo de toda a request (considerando a entrada dos índices). Comecei a me perguntar isso depois dos testes lá no repositório do curso, onde montar a árvore de filhos era a parte mais rápida.

Então o que acha de também implementarmos um log de trace, marcando o tempo, e que seja possível criar um gráfico no Axiom de cada trecho do código? Eu não sei se o Axiom consegue plotar isso, mas se conseguir, seria muito interessante revelar de forma concreta qual a parte que está precisando de mais otimização 🤝

[aprendendofelipe]

Então o que acha de também implementarmos um log de trace, marcando o tempo, e que seja possível criar um gráfico no Axiom de cada trecho do código? Eu não sei se o Axiom consegue plotar isso, mas se conseguir, seria muito interessante revelar de forma concreta qual a parte que está precisando de mais otimização 🤝

Eu acho uma boa, e tinha pensado justamente nisso pra gente entender o PR 18 do curso.dev 🤝

[FabricioFFC]

Me parece uma boa solução tbm, e atende a necessidade de filtrar não necessariamente pelo root_id.

Ainda mais que acredito que o path não muda após a criação do content, pois seria custoso remontar esse path com frequência.

[aprendendofelipe]

Ainda mais que acredito que o path não muda após a criação do content, pois seria custoso remontar esse path com frequência.

Exato! Desde esse commit d0b8d00 não é mais possível alterar o parent_id de um conteúdo, então o path também nunca vai mudar. Mas mesmo se precisar alterar todos os filhos de um comentário, caso um dia volte a ser possível mudar o parent_id, ainda vai valer a pena usar o path, pois as leituras são em quantidade muito maior do que as gravações.

Aproveitando... O path resolve a busca de todos os filhos sem precisar da recursiva, mas ainda precisamos lidar com duas coisas:

1. Caso exista um comentário excluído que possua filhos ainda publicados, esses filhos serão retornados usando a consulta pelo path. Dá pra gente excluir eles na sequência, mas eu acho que poderíamos manter esses filhos no retorno e montar a árvore mostrando onde houver respostas para comentários já excluídos. Assim esses comentários não ficam totalmente órfãos.

2. Para poder paginar os comentários precisamos ter uma forma padrão de ordenação deles. No Transforma /contents em um ponto capaz de fornecer todos os tipos de dados sobre os conteúdos públicos #1413 estou usando um outro array para isso (por enquanto é montado na recursiva). É parecido com o array do path, mas colocando todos published_at acima do item, desde o root. Assim dá pra classificar por data ao mesmo tempo que mantém a estrutura da árvore. Obs.: Desde o commit d66a049 o published_at também ficou um campo fixo após a primeira publicação.

[filipedeschamps]

1. Caso exista um comentário excluído que possua filhos ainda publicados, esses filhos serão retornados usando a consulta pelo path. Dá pra gente excluir eles na sequência, mas eu acho que poderíamos manter esses filhos no retorno e montar a árvore mostrando onde houver respostas para comentários já excluídos. Assim esses comentários não ficam totalmente órfãos.

Exato! O princípio disso acontece quando um comentário pai foi deletado, e você acessa o filho (aparece como "não disponível"):

https://www.tabnews.com.br/filipedeschamps/d23e15c0-419c-4a71-9124-89780a8a8936

Acessando esse conteúdo ali de cima pela API, mas acessando o /parent dele:

https://www.tabnews.com.br/api/v1/contents/filipedeschamps/d23e15c0-419c-4a71-9124-89780a8a8936/parent

Isto é feito no filtro de saída:

tabnews.com.br/models/authorization.js

Lines 233 to 239 in c67630d

	if (output.status !== 'published' && user.id !== output.owner_id) {
	clonedOutput.title = '[Não disponível]';
	clonedOutput.body = '[Não disponível]';
	clonedOutput.slug = 'nao-disponivel';
	clonedOutput.source_url = null;
	clonedOutput.children_deep_count = 0;
	}

Eu topo total então fazer retornar todos os conteúdos, mas filtrar eles na saída 🤝

[aprendendofelipe]

Testei o desempenho com as diversas possibilidades de busca de todos os filhos de um conteúdo e o resumo dos resultados são:

1. Usar root_id com ou sem índice apresentou praticamente os mesmos tempos de execução da recursiva atual.
2. Já usando materialized_path melhorou de formas diferentes.
3. Filtrando por WHERE 'uuid' = ANY(path) o índice não faz diferença (nunca é utilizado), mas o tempo de execução já cai para metade.
4. Filtrando por WHERE path @> ARRAY['uuid']::uuid[] sem criar o índice diminui o tempo de execução um pouco mais do que usando ANY.
5. Agora usando @> junto do índice gin no uuid[] a redução do tempo de execução foi de cerca de 100x 🚀

Obs. Pela pequena quantidade de linhas no banco durante meus testes (74), rodei tudo usando ENABLE_SEQSCAN = OFF.

Então vou criar o PR usando path::uuid[] já com o índice gin 👍

[aprendendofelipe]

[Edit 2] As primeiras otimizações começaram nos PRs #1400 e #1403...

Com a implementação do caminho materializado e a utilização da coluna path em todos os locais onde utilizávamos recursivas, os PRs #1419, #1421 e #1426 concluem o que era proposto nessa issue 🚀

[Edit] O PR #1431 corrige o bug causado por conteúdo órfão assumindo lugar do conteúdo root