Preciso calcular a profundidade de um descendente a partir de seu ancestral. Quando um registro possui object_id = parent_id = ancestor_id
, ele é considerado um nó raiz (o ancestral). Eu tenho tentado obter uma WITH RECURSIVE
consulta em execução com o PostgreSQL 9.4 .
Eu não controlo os dados ou as colunas. O esquema de dados e tabela é proveniente de uma fonte externa. A tabela está crescendo continuamente . No momento, cerca de 30 mil registros por dia. Qualquer nó da árvore pode estar ausente e será extraído de uma fonte externa em algum momento. Eles geralmente são puxados em created_at DESC
ordem, mas os dados são puxados com trabalhos em segundo plano assíncronos.
Inicialmente, tínhamos uma solução de código para esse problema, mas agora com mais de 5 milhões de linhas, leva quase 30 minutos para ser concluído.
Definição de tabela de exemplo e dados de teste:
CREATE TABLE objects (
id serial NOT NULL PRIMARY KEY,
customer_id integer NOT NULL,
object_id integer NOT NULL,
parent_id integer,
ancestor_id integer,
generation integer NOT NULL DEFAULT 0
);
INSERT INTO objects(id, customer_id , object_id, parent_id, ancestor_id, generation)
VALUES (2, 1, 2, 1, 1, -1), --no parent yet
(3, 2, 3, 3, 3, -1), --root node
(4, 2, 4, 3, 3, -1), --depth 1
(5, 2, 5, 4, 3, -1), --depth 2
(6, 2, 6, 5, 3, -1), --depth 3
(7, 1, 7, 7, 7, -1), --root node
(8, 1, 8, 7, 7, -1), --depth 1
(9, 1, 9, 8, 7, -1); --depth 2
Observe que object_id
não é exclusivo, mas a combinação (customer_id, object_id)
é única.
Executando uma consulta como esta:
WITH RECURSIVE descendants(id, customer_id, object_id, parent_id, ancestor_id, depth) AS (
SELECT id, customer_id, object_id, parent_id, ancestor_id, 0
FROM objects
WHERE object_id = parent_id
UNION
SELECT o.id, o.customer_id, o.object_id, o.parent_id, o.ancestor_id, d.depth + 1
FROM objects o
INNER JOIN descendants d ON d.parent_id = o.object_id
WHERE
d.id <> o.id
AND
d.customer_id = o.customer_id
) SELECT * FROM descendants d;
Gostaria que a generation
coluna fosse definida como a profundidade que foi calculada. Quando um novo registro é adicionado, a coluna de geração é definida como -1. Existem alguns casos em que um parent_id
pode não ter sido extraído ainda. Se oparent_id
não existir, deve deixar a coluna de geração definida como -1.
Os dados finais devem ter a seguinte aparência:
id | customer_id | object_id | parent_id | ancestor_id | generation
2 1 2 1 1 -1
3 2 3 3 3 0
4 2 4 3 3 1
5 2 5 4 3 2
6 2 6 5 3 3
7 1 7 7 7 0
8 1 8 7 7 1
9 1 9 8 7 2
O resultado da consulta deve ser atualizar a coluna de geração para a profundidade correta.
Comecei a trabalhar a partir das respostas a esta pergunta relacionada no SO .
fonte
update
a mesa com o resultado da sua CTE recursiva?ancestor_id
já está definido, então você só precisa atribuir a geração a partir do CTE.depth?Respostas:
A consulta que você tem está basicamente correta. O único erro está na segunda parte (recursiva) do CTE, onde você tem:
Deveria ser o contrário:
Você deseja unir os objetos aos pais (que já foram encontrados).
Portanto, a consulta que calcula a profundidade pode ser escrita (nada mais mudou, apenas a formatação):
Para a atualização, basta substituir o último
SELECT
, com oUPDATE
, juntando o resultado do cte, de volta à tabela:Testado no SQLfiddle
Comentários adicionais:
ancestor_id
e oparent_id
não precisam estar na lista de seleção (o ancestral é óbvio, o pai é um pouco complicado para descobrir o porquê), para que você possa mantê-los noSELECT
consulta, se quiser, mas pode removê-los com segurança doUPDATE
.(customer_id, object_id)
parece ser um candidato a umUNIQUE
restrição. Se seus dados estiverem em conformidade com isso, adicione essa restrição. As junções realizadas no CTE recursivo não faria sentido se não fosse exclusivo (um nó poderia ter dois pais caso contrário).(customer_id, parent_id)
ela seria candidata a umaFOREIGN KEY
restrição queREFERENCES
(única)(customer_id, object_id)
. Você provavelmente não deseja adicionar essa restrição FK, já que, por sua descrição, você está adicionando novas linhas e algumas linhas podem fazer referência a outras que ainda não foram adicionadas.A
AND o.generation = -1
atualização final garantirá que as linhas que foram atualizadas na 1ª execução não serão atualizadas novamente, mas o CTE ainda é uma parte cara.A seguir, é apresentada uma tentativa de resolver esses problemas: melhore o CTE para considerar o menor número possível de linhas e use em
(customer_id, obejct_id)
vez de(id)
identificar linhas (issoid
é completamente removido da consulta. Ele pode ser usado como a 1ª atualização ou uma subseqüente:Observe como o CTE possui 3 partes. Os dois primeiros são as partes estáveis. A 1ª parte encontra os nós raiz que não foram atualizados antes e ainda os têm,
generation=-1
portanto devem ser nós adicionados recentemente. A segunda parte localiza os filhos (comgeneration=-1
) dos nós pai que foram atualizados anteriormente.A terceira parte recursiva encontra todos os descendentes das duas primeiras partes, como antes.
Testado no SQLfiddle-2
fonte
O @ypercube já fornece uma explicação ampla, por isso vou direto ao assunto o que tenho que adicionar.
Suponho que isso deva se aplicar recursivamente, ou seja, o restante da árvore sempre tem
generation = -1
um nó ausente.Se algum nó da árvore estiver ausente (ainda), precisamos encontrar linhas com
generation = -1
isso ...... são nós raiz
... ou ter um pai com
generation > -1
.E atravesse a árvore de lá. Os nós filhos dessa seleção também devem ter
generation = -1
.Pegue o
generation
do pai incrementado em um ou volte para 0 para nós raiz:A parte não recursiva é única
SELECT
dessa maneira, mas logicamente equivalente às duas uniões do @ ypercubeSELECT
. Não tem certeza do que é mais rápido, você terá que testar.O ponto muito mais importante para o desempenho é:
Índice!
Se você adicionar repetidamente linhas a uma tabela grande dessa maneira, adicione um índice parcial :
Isso alcançará mais desempenho do que todas as outras melhorias discutidas até agora - para pequenas e repetidas adições a uma grande tabela.
Adicionei a condição de índice à parte recursiva do CTE (mesmo que logicamente redundante) para ajudar o planejador de consultas a entender que o índice parcial é aplicável.
Além disso, você provavelmente também deve ter a
UNIQUE
restrição de(object_id, customer_id)
que o @ypercube já mencionado. Ou, se você não puder impor exclusividade por algum motivo (por quê?), Adicione um índice simples. A ordem das colunas do índice é importante, entre:fonte
ON objects (customer_id, parent_id, object_id) WHERE generation = -1;
e talvez outroON objects (customer_id, object_id) WHERE generation > -1;
. A atualização também precisará "alternar" todas as linhas atualizadas de um índice para outro, portanto, não tenha certeza se essa é uma boa idéia para a execução inicial do UPDATE.