Trees: integer[] outperformed by ltree - Mailing list pgsql-performance

Hi,

I am in a need of a very robust (esp. fast in read, non-blocking in update) tree structure storage (95% trees are of depth <4, current max. is 12). We have 10k-100k trees now, millions in the future.
I made many tests, benchmarks of usual operations, and after all, materialized path ('1.5.3' path notation) seems most promising.

My last candidates for its storage are ltree and integer[]. So I am comparing the following benchmarking tables with exactly same data (5 regular trees - each node except leaves has 5 children, depth=9, total nodes=2.441.405, id numbered according to breadth-first traversal):


TABLES:
A/ integer[]
CREATE TABLE test (
    id SERIAL,
    lpath ltree,
    CONSTRAINT test_pkey PRIMARY KEY(id)
);

CREATE INDEX test_idx1 ON test USING gist (lpath gist_ltree_ops);

B/ ltree
CREATE TABLE test (
    id SERIAL,
    apath INTEGER[],
    CONSTRAINT test_pkey PRIMARY KEY(id)
);

CREATE INDEX test_idx1 ON test USING gin (apath);

Separate single-table dbases, vacuum(analyz)ed.


TESTING MACHINE:
Windows 7, postgres 9.3.0, 4GB RAM
effective_cache_size = 2GB
work_mem = 512MB
shared_buffers = 1GB


THE PROBLEM:
My intuition says integer[] should not be much worse than ltree (rather the other way) but I am not able to reach such results. I believe I am making some trivial mistake rather than assuming false hypothesis. My general question is, what more can I do to get better performance.


WHAT I DID:

1/ I checked gist index for integer[] via intarray extension. Query plans for <@ and @> operators do not use it (reported bug/feature). That's why I am using gin.

2/ Getting ancestors - same qplans, ltree slightly wins:
A:
select * from test where apath@>(select apath from test where id=1)

Bitmap Heap Scan on test  (cost=159.04..33950.48 rows=12206 width=60) (actual time=80.912..224.182 rows=488281 loops=1)
  Recheck Cond: (apath @> $0)
  Buffers: shared hit=18280
  InitPlan 1 (returns $0)
    ->  Index Scan using test_pkey on test test_1  (cost=0.43..8.45 rows=1 width=56) (actual time=0.022..0.023 rows=1 loops=1)
          Index Cond: (id = 1)
          Buffers: shared hit=4
  ->  Bitmap Index Scan on test_idx1  (cost=0.00..147.54 rows=12206 width=0) (actual time=76.896..76.896 rows=488281 loops=1)
        Index Cond: (apath @> $0)
        Buffers: shared hit=369
Total runtime: 240.408 ms

B:
select * from test where lpath<@(select lpath from test where id=1)

Bitmap Heap Scan on test  (cost=263.81..8674.72 rows=2445 width=83) (actual time=85.395..166.683 rows=488281 loops=1)
  Recheck Cond: (lpath <@ $0)
  Buffers: shared hit=22448
  InitPlan 1 (returns $0)
    ->  Index Scan using test_pkey on test test_1  (cost=0.43..8.45 rows=1 width=79) (actual time=0.024..0.025 rows=1 loops=1)
          Index Cond: (id = 1)
          Buffers: shared hit=4
  ->  Bitmap Index Scan on test_idx1  (cost=0.00..254.75 rows=2445 width=0) (actual time=83.029..83.029 rows=488281 loops=1)
        Index Cond: (lpath <@ $0)
        Buffers: shared hit=12269
Total runtime: 182.239 ms

3/ Getting chosen nodes (eo) with chosen ancestors (ea) - index[] performs very poorly, it's qplan uses additional Bitmap Heap Scan, still indices used in both cases.

A:
select *
from test eo
where id in (select generate_series(3, 3000000, 5000)) and
    exists (
        select 1
        from test ea
        where ea.id in(select generate_series(1000, 3000, 3)) and
            ea.apath <@ eo.apath
    )

Nested Loop Semi Join  (cost=140.10..1302851104.53 rows=6103 width=60) (actual time=1768.862..210525.597 rows=104 loops=1)
  Buffers: shared hit=8420909
  ->  Nested Loop  (cost=17.94..1652.31 rows=1220554 width=60) (actual time=0.382..17.255 rows=489 loops=1)
        Buffers: shared hit=2292
        ->  HashAggregate  (cost=17.51..19.51 rows=200 width=4) (actual time=0.352..1.486 rows=600 loops=1)
              ->  Result  (cost=0.00..5.01 rows=1000 width=0) (actual time=0.009..0.100 rows=600 loops=1)
        ->  Index Scan using test_pkey on test eo  (cost=0.43..8.15 rows=1 width=60) (actual time=0.017..0.021 rows=1 loops=600)
              Index Cond: (id = (generate_series(3, 3000000, 5000)))
              Buffers: shared hit=2292
  ->  Hash Semi Join  (cost=122.16..1133.92 rows=6103 width=56) (actual time=430.482..430.482 rows=0 loops=489)
        Hash Cond: (ea.id = (generate_series(1000, 3000, 3)))
        Buffers: shared hit=8418617
        ->  Bitmap Heap Scan on test ea  (cost=94.65..251.23 rows=12206 width=60) (actual time=271.034..430.278 rows=8 loops=489)
              Recheck Cond: (apath <@ eo.apath)
              Rows Removed by Index Recheck: 444335
              Buffers: shared hit=8418617
              ->  Bitmap Index Scan on test_idx1  (cost=0.00..91.60 rows=12206 width=0) (actual time=155.355..155.355 rows=488281 loops=489)
                    Index Cond: (apath <@ eo.apath)
                    Buffers: shared hit=237668
        ->  Hash  (cost=15.01..15.01 rows=1000 width=4) (actual time=0.305..0.305 rows=667 loops=1)
              Buckets: 1024  Batches: 1  Memory Usage: 24kB
              ->  Result  (cost=0.00..5.01 rows=1000 width=0) (actual time=0.003..0.116 rows=667 loops=1)
Total runtime: 210526.004 ms

B:
select *
from test eo
where id in (select generate_series(3, 3000000, 5000)) and
    exists (
        select 1
        from test ea
        where ea.id in(select generate_series(1000, 3000, 3)) and
            ea.lpath @> eo.lpath
    )
    
Nested Loop Semi Join  (cost=45.86..276756955.40 rows=1223 width=83) (actual time=2.985..226.161 rows=104 loops=1)
  Buffers: shared hit=27675
  ->  Nested Loop  (cost=17.94..1687.51 rows=1222486 width=83) (actual time=0.660..5.987 rows=489 loops=1)
        Buffers: shared hit=2297
        ->  HashAggregate  (cost=17.51..19.51 rows=200 width=4) (actual time=0.632..1.008 rows=600 loops=1)
              ->  Result  (cost=0.00..5.01 rows=1000 width=0) (actual time=0.007..0.073 rows=600 loops=1)
        ->  Index Scan using test_pkey on test eo  (cost=0.43..8.33 rows=1 width=83) (actual time=0.007..0.007 rows=1 loops=600)
              Index Cond: (id = (generate_series(3, 3000000, 5000)))
              Buffers: shared hit=2297
  ->  Hash Semi Join  (cost=27.92..242.30 rows=1223 width=79) (actual time=0.449..0.449 rows=0 loops=489)
        Hash Cond: (ea.id = (generate_series(1000, 3000, 3)))
        Buffers: shared hit=25378
        ->  Index Scan using test_idx1 on test ea  (cost=0.41..43.43 rows=2445 width=83) (actual time=0.060..0.445 rows=8 loops=489)
              Index Cond: (lpath @> eo.lpath)
              Buffers: shared hit=25378
        ->  Hash  (cost=15.01..15.01 rows=1000 width=4) (actual time=0.178..0.178 rows=667 loops=1)
              Buckets: 1024  Batches: 1  Memory Usage: 24kB
              ->  Result  (cost=0.00..5.01 rows=1000 width=0) (actual time=0.003..0.071 rows=667 loops=1)
Total runtime: 226.308 ms

3.a/ If I turn off the index for B the query is much faster:
Nested Loop Semi Join  (cost=35.88..20535547247.01 rows=6103 width=60) (actual time=17.257..1112.276 rows=104 loops=1)
  Join Filter: (ea.apath <@ eo.apath)
  Rows Removed by Join Filter: 287529
  Buffers: shared hit=1155469
  ->  Nested Loop  (cost=17.94..1652.31 rows=1220554 width=60) (actual time=0.334..5.307 rows=489 loops=1)
        Buffers: shared hit=2292
        ->  HashAggregate  (cost=17.51..19.51 rows=200 width=4) (actual time=0.297..0.598 rows=600 loops=1)
              ->  Result  (cost=0.00..5.01 rows=1000 width=0) (actual time=0.008..0.088 rows=600 loops=1)
        ->  Index Scan using test_pkey on test eo  (cost=0.43..8.15 rows=1 width=60) (actual time=0.007..0.007 rows=1 loops=600)
              Index Cond: (id = (generate_series(3, 3000000, 5000)))
              Buffers: shared hit=2292
  ->  Nested Loop  (cost=17.94..1652.31 rows=1220554 width=56) (actual time=0.004..1.946 rows=588 loops=489)
        Buffers: shared hit=1153177
        ->  HashAggregate  (cost=17.51..19.51 rows=200 width=4) (actual time=0.001..0.089 rows=588 loops=489)
              ->  Result  (cost=0.00..5.01 rows=1000 width=0) (actual time=0.005..0.103 rows=667 loops=1)
        ->  Index Scan using test_pkey on test ea  (cost=0.43..8.15 rows=1 width=60) (actual time=0.002..0.003 rows=1 loops=287633)
              Index Cond: (id = (generate_series(1000, 3000, 3)))
              Buffers: shared hit=1153177
Total runtime: 1112.411 ms

3.b/ With the index on, if I go down to effective_cache_size = 256MB, B also skips the index usage, same qplan as in 3.a is used. Still the index is used for both versions of query 2 and ltree version of query 3.


QUESTIONS:
1/ Is my hypothesis about similar performance of ltree and integer[] correct?
2/ If so, what should I do to get it?
3/ Is there a way to improve the performance of <@ and @> operators? In fact, as I am having a tree path in the column, I only need to check if path_a 'starts_with' path_b to get ancestors/descendants. Therefore something more effective than 'contains' might be used. Is there any way?
4/ Do I understand properly that index on integer[] is much more memory-consuming, and therefore there are differences in query plans / execution times?


Thanks for any help,

Jan