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