Início / dba / Perguntas / 334249
Accepted
cjheppell
Asked: 2023-12-21 19:06:58 +0800 CST

Unindo tabelas usando o caminho ltree correspondente mais longo

  • 772

Dada uma tabela assim:

caminho (ltree)
abc
ab
a
de
f

Como eu escreveria uma consulta para retornar o caminho ltree correspondente mais longo, dada uma entrada?

Por exemplo:

(input) => expected output

(a.b.c) => a.b.c
(d.e.f) => d.e
(f.g.h) => f
(a.b)   => a.b

Eu gostaria de poder usar isso para unir uma tabela contendo caminhos ltree em seu "caminho correspondente mais longo" em outra tabela de uma forma que tenha bom desempenho. Então, dada uma tabela contendo linhas de todos os itens inputsdo exemplo acima, como eu a juntaria à tabela para obter linhas com a "correspondência mais longa"?

postgresql

1 respostas

  1. Best Answer

    Criar dados de teste...

    -- main table
CREATE UNLOGGED TABLE tree( path ltree NOT NULL );
INSERT INTO tree SELECT (a)::text::ltree FROM generate_series(1,32) a;
INSERT INTO tree SELECT (a||'.'||b)::ltree FROM generate_series(1,32) a, generate_series(1,32) b;
INSERT INTO tree SELECT (a||'.'||b||'.'||c)::ltree FROM generate_series(1,32) a, generate_series(1,32) b, generate_series(1,32) c;
INSERT INTO tree SELECT (a||'.'||b||'.'||c||'.'||d)::ltree FROM generate_series(1,32) a, generate_series(1,32) b, generate_series(1,32) c, generate_series(1,32) d;
CREATE INDEX path_gist_idx ON tree USING GIST (path);
VACUUM ANALYZE subs;

-- table for join
CREATE UNLOGGED TABLE other( path ltree NOT NULL );
INSERT INTO other SELECT path||'foo' FROM tree WHERE random()<0.001;

    Para aproximadamente 1.000 linhas na tabela "outros", procura o caminho correspondente mais longo na tabela "árvore" que contém 1 milhão de linhas.

    Primeira tentativa: função de janela. 140ms sem LIMITE. Seria necessária alguma desduplicação na saída.

    SELECT o.path, first_value(t.path) over (partition by o.path ORDER BY nlevel(t.path) DESC) FROM other o JOIN tree t ON (t.path @> o.path) LIMIT 10;
      path      | first_value
----------------+-------------
 1.1.18.17.foo  | 1.1.18.17
 1.1.18.17.foo  | 1.1.18.17
 1.1.18.17.foo  | 1.1.18.17
 1.1.18.17.foo  | 1.1.18.17
 1.1.28.28.foo  | 1.1.28.28
 1.1.28.28.foo  | 1.1.28.28
 1.1.28.28.foo  | 1.1.28.28
 1.1.28.28.foo  | 1.1.28.28
 1.13.15.26.foo | 1.13.15.26
 1.13.15.26.foo | 1.13.15.26

    Segunda tentativa: comparação ltree pode ser usada, como '1.2.3'::ltree>'1.2'::ltree, então usar max() simplesmente retornaria o mais longo. Infelizmente max() não está implementado para ltree, mas você pode adicioná-lo . Mas sempre podemos usar LATERAL, que tem a vantagem de retornar a linha inteira caso você precise.

    SELECT o.path, foo.path FROM other o 
LEFT JOIN LATERAL (
    SELECT path FROM tree t 
    WHERE t.path @> o.path
    ORDER BY t.path DESC LIMIT 1
) foo ON true;

    Este é mais rápido em 80 ms porque a classificação é movida dentro do loop aninhado e é um heapsort top-1. Portanto, 80 µs por linha para encontrar o caminho mais longo.

     Nested Loop Left Join  (cost=10255.64..10850500.55 rows=1058 width=80) (actual time=33.828..79.518 rows=1058 loops=1)
   ->  Seq Scan on other o  (cost=0.00..20.58 rows=1058 width=44) (actual time=0.017..0.094 rows=1058 loops=1)
   ->  Limit  (cost=10255.64..10255.64 rows=1 width=36) (actual time=0.043..0.043 rows=1 loops=1058)
         ->  Sort  (cost=10255.64..10282.70 rows=10824 width=36) (actual time=0.043..0.043 rows=1 loops=1058)
               Sort Key: t.path DESC
               Sort Method: top-N heapsort  Memory: 25kB
               ->  Bitmap Heap Scan on tree t  (cost=616.30..10201.52 rows=10824 width=36) (actual time=0.040..0.041 rows=4 loops=1058)
                     Recheck Cond: (path @> o.path)
                     Heap Blocks: exact=4197
                     ->  Bitmap Index Scan on path_gist_idx  (cost=0.00..613.59 rows=10824 width=0) (actual time=0.039..0.039 rows=4 loops=1058)
                           Index Cond: (path @> o.path)
 Planning Time: 0.232 ms
 JIT:
   Functions: 7
   Options: Inlining true, Optimization true, Expressions true, Deforming true
   Timing: Generation 2.195 ms, Inlining 9.237 ms, Optimization 17.678 ms, Emission 6.752 ms, Total 35.862 ms
 Execution Time: 81.884 ms

    Terceiro: função de retorno de conjunto.

    CREATE OR REPLACE FUNCTION unnest_ltree( path ltree )
RETURNS SETOF ltree
RETURNS NULL ON NULL INPUT
COST 10 ROWS 5
LANGUAGE plpgsql AS $$
BEGIN
WHILE path != '' LOOP
    RETURN NEXT path;
    path := subpath( path, 0, -1 );
END LOOP;
END;
$$;
select unnest_ltree( '1.2.3.4'::ltree );
 unnest_ltree
--------------
 1.2.3.4
 1.2.3
 1.2
 1

SELECT o.path, foo.path FROM other o 
LEFT JOIN LATERAL (
    SELECT path FROM unnest_ltree(o.path) u JOIN tree t ON (t.path=u)
    LIMIT 1
) foo ON true;

    Resultado: 29ms, muito mais rápido.

    No entanto, depende do fato de que o postgres usará as linhas de unnest_ltree() na ordem em que a função as retorna, o que não é garantido.

    Quarta tentativa: junção manual

    CREATE OR REPLACE FUNCTION get_closest( _path ltree )
RETURNS tree
RETURNS NULL ON NULL INPUT
LANGUAGE plpgsql AS $$
DECLARE
    myrow tree;
BEGIN
WHILE _path != '' LOOP
    SELECT INTO myrow * FROM tree WHERE path=_path;
    IF FOUND THEN RETURN myrow; END IF;
    _path := subpath( _path, 0, -1 );
END LOOP;
END;
$$;

SELECT get_closest(path) FROM other;

    Resultado: 35ms com índice Gist no caminho, 16ms com índice btree no caminho.

    No entanto, agora que adicionei um índice btree na coluna path, a primeira consulta contra-ataca. Como o pai mais longo (t.path) de um caminho (o.path) deve satisfazer t.path <= o.path, e devido à ordem de classificação dos caminhos, adicionar essa condição significa que o btree encontra a linha de destino imediatamente, enquanto a essência simplesmente retorna todos os ancestrais que precisam ser classificados. Portanto esta é a opção mais rápida, mas precisa de um índice extra.

    SELECT o.path, foo.path FROM other o 
LEFT JOIN LATERAL (
    SELECT path FROM tree t 
    WHERE t.path @> o.path AND t.path<=o.path
    ORDER BY t.path DESC LIMIT 1
) foo ON true;

 Nested Loop Left Join  (cost=0.43..5629.18 rows=1058 width=80) (actual time=0.870..11.314 rows=1058 loops=1)
   ->  Seq Scan on other o  (cost=0.00..20.58 rows=1058 width=44) (actual time=0.017..0.097 rows=1058 loops=1)
   ->  Limit  (cost=0.43..5.29 rows=1 width=36) (actual time=0.010..0.010 rows=1 loops=1058)
         ->  Index Only Scan Backward using tree_path_idx on tree t  (cost=0.43..17548.43 rows=3608 width=36) (actual time=0.010..0.010 rows=1 loops=1058)
               Index Cond: (path <= o.path)
               Filter: (path @> o.path)
               Rows Removed by Filter: 2
               Heap Fetches: 0
 Planning Time: 0.310 ms
 Execution Time: 11.400 ms

    Mas... o que aconteceria se a tabela "outros" fosse muito maior? Vamos tentar com 500 mil linhas.

    CREATE UNLOGGED TABLE other2( path ltree NOT NULL );
INSERT INTO other2 SELECT path||'foo' FROM tree WHERE random()<0.5;

    Nesse caso, todos os métodos acima são afetados, demorando cerca de 3,5s, porque estão todos restritos a um tipo de plano de loop aninhado. Para um grande número de linhas em ambas as tabelas, uma junção de mesclagem seria uma opção muito melhor... Infelizmente o postgres não suporta ASOF JOIN que faria isso automaticamente, mas sempre podemos classificar!

    WITH b AS (SELECT path tp, NULL op FROM tree UNION ALL SELECT NULL, path FROM other2)
SELECT * FROM b ORDER BY COALESCE(tp,op);

     tp      |       op
-------------+-----------------
 1           | Null
 1.1         | Null
 1.1.1       | Null
 1.1.1.1     | Null         -- the row we want
 Null        | 1.1.1.1.foo  -- is just above this one
 1.1.1.10    | Null
 Null        | 1.1.1.10.foo
 1.1.1.11    | Null
 1.1.1.12    | Null
 Null        | 1.1.1.12.foo
 1.1.1.13    | Null
 Null        | 1.1.1.13.foo

    Como isso fornece as linhas relacionadas próximas (uma sempre acima da outra), uma função de janela pode resolver isso.

    WITH b AS (SELECT path tp, NULL op FROM tree UNION ALL SELECT NULL, path FROM other2),
c AS (SELECT LAG(tp,1) OVER w tp, op FROM b WINDOW w AS (ORDER BY COALESCE(tp,op)))
SELECT * FROM c WHERE tp @> op;

    Isso não usa nenhum índice e deve funcionar em tabelas grandes, mas no meu caso de teste leva quase o mesmo tempo que os anteriores.

    • 1

relate perguntas