2

Given a table like so:

path (ltree)
a.b.c
a.b
a
d.e
f

How would I write a query to return the longest matching ltree path given an input?

For example:

(input) => expected output

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

I'd like to be able to use this to join one table containing ltree paths against their "longest matching path" in another table in a way that is performant. So given a table containing rows of all the inputs in the example above, how would I join it to the table to get rows with the "longest match"?

Improve this question

1 Answer 1

Reset to default
1

Build test data...

-- 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;

For the ~1000 rows in table "other", this searches for the longest matching path in table "tree" which contains 1M rows.

First try: window function. 140ms without LIMIT. It would need some de-duplication in the output.

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

Second try: ltree comparison can be used, as '1.2.3'::ltree>'1.2'::ltree, so using max() would simply return the longest one. Unfortunately max() is not implemented for ltree, but you could add it. But we can always use LATERAL, which has the advantage of returning the whole row in case you need it.

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;

This one is faster at 80ms because the sort is moved inside the nested loop, and it's a top-1 heapsort. So 80µs per row to find the longest path.

 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

Third one: set-returning function.

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;

Result: 29ms, much faster.

However it relies on the fact that postgres will use the rows from unnest_ltree() in the order the function returns them, which is not guaranteed.

Fourth try: manual join

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;

Result: 35ms with gist index on path, 16ms with btree index on path.

However, now that I added a btree index on path column, the first query strikes back. Because the longest parent (t.path) of a path (o.path) must satisfy t.path <= o.path, and due to sorting order of paths, adding that condition means the btree finds the target row immediately, whereas gist simply returns all the ancestors which then have to be sorted. So this is the fastest option, but it needs an extra index.

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

But... what would happen if table "other" was instead much larger? Let's try with 500k rows.

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

In this case all the methods above take a hit, taking about 3.5s, because they're all restricted to a nested loop plan type. For a large number of rows in both tables, a merge join would be a much better option... Unfortunately postgres does not support ASOF JOIN which would do that automatically, but we can always sort!

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

Since this gives the related rows in close proximity (one always above the other), a window function can sort this out.

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;

This does not use any index and should work on large tables, but in my test case it takes about the same time as the previous ones.

Improve this answer

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.