I have the following table in my PostgreSQL database (v13.8, running on Debian 11 (Bullseye)) which contains ~15,000,000 rows:
=> \d ncbitaxon
Table "public.ncbitaxon"
Column | Type | Collation | Nullable | Default
------------ --------- ----------- ---------- ---------
assertion | integer | | |
retraction | integer | | | 0
graph | text | | |
subject | text | | |
predicate | text | | |
object | text | | |
datatype | text | | |
annotation | text | | |
The table does not have a primary key and is such that each subject field can be associated with multiple object and predicate fields. I would like to retrieve every subject that is associated with the predicate 'rdf:type' and the object 'owl:Class', but that is not associated with the predicate 'rdfs:subClassOf'.
The table has no indexes, and when I run the following query I get an answer back consistently in under 2s (which I consider acceptable):
select n1.subject
from ncbitaxon n1
where n1.predicate = 'rdf:type'
and n1.object = 'owl:Class'
and not exists (
select 1
from ncbitaxon n2
where n2.subject = n1.subject
and n2.predicate = 'rdfs:subClassOf'
)
However when I add (non-unique) btree indexes on each of the subject, object, predicate, and datatype columns the performance slows down considerably, so that my result comes back consistently in about 9s or so (which is too slow).
I realise that indexes are not a silver bullet and can (evidently) sometimes even slow down select queries.
But what puzzles me is that when I run the same query on the same table, but this time in SQLite (v3.34.1, running on the same laptop), I have the opposite effect. I.e., with those indexes I get a result in about 5s, and without the indexes I eventually have to press Ctrl-C because I get fed up of waiting for the result to come back.
I wondered if this might be due to some sort of caching effect, so I tried clearing PostgreSQL's cache by running:
echo 1 > /proc/sys/vm/drop_caches
echo 2 > /proc/sys/vm/drop_caches
echo 3 > /proc/sys/vm/drop_caches
systemctl restart postgresql
And indeed there is a bit of a cache effect, because the first time I run the query in PostgreSQL after doing this it takes about 3s (instead of 2s). But this is still faster than running the query in either SQLite (~5s) or PostgreSQL (~9s) if I have those indexes in place.
I'm confused. Anyone know what's going on here?
The create index statements are:
create index idx_77907_idx_ncbitaxon_predicate on ncbitaxon (predicate);
create index idx_77907_idx_ncbitaxon_subject on ncbitaxon (subject);
create index idx_77907_idx_ncbitaxon_object on ncbitaxon (object);
create index idx_77907_idx_ncbitaxon_datatype on ncbitaxon (datatype);
Here is the output of explain (analyze, buffers, format text) for the with-indexes case:
QUERY PLAN
-----------------------------------------------------------------------------------------------------------------------------------------------------------------
Gather (cost=1000.56..549629.43 rows=1 width=17) (actual time=5354.149..7223.752 rows=2 loops=1)
Workers Planned: 2
Workers Launched: 2
Buffers: shared hit=12556526 read=226206
-> Nested Loop Anti Join (cost=0.56..548629.33 rows=1 width=17) (actual time=5942.986..7184.393 rows=1 loops=3)
Buffers: shared hit=12556526 read=226206
-> Parallel Seq Scan on ncbitaxon n1 (cost=0.00..295443.22 rows=168032 width=17) (actual time=137.371..630.607 rows=812952 loops=3)
Filter: ((predicate = 'rdf:type'::text) AND (object = 'owl:Class'::text))
Rows Removed by Filter: 4250687
Buffers: shared hit=6214 read=194286
-> Index Scan using idx_77907_idx_ncbitaxon_subject on ncbitaxon n2 (cost=0.56..3.46 rows=5 width=17) (actual time=0.008..0.008 rows=1 loops=2438855)
Index Cond: (subject = n1.subject)
Filter: (predicate = 'rdfs:subClassOf'::text)
Rows Removed by Filter: 4
Buffers: shared hit=12550312 read=31920
Planning:
Buffers: shared hit=14 read=6
Planning Time: 1.054 ms
JIT:
Functions: 27
Options: Inlining true, Optimization true, Expressions true, Deforming true
Timing: Generation 6.551 ms, Inlining 111.762 ms, Optimization 182.297 ms, Emission 117.506 ms, Total 418.115 ms
Execution Time: 7228.950 ms
(23 rows)
and here it is for the no-indexes case:
------------------------------------------------------------------------------------------------------------------------------------------------------
Gather (cost=299030.49..603580.05 rows=1 width=17) (actual time=1461.791..1500.212 rows=2 loops=1)
Workers Planned: 2
Workers Launched: 2
Buffers: shared hit=25757 read=375369, temp read=22444 written=22996
-> Parallel Hash Anti Join (cost=298030.49..602579.95 rows=1 width=17) (actual time=1425.751..1432.604 rows=1 loops=3)
Hash Cond: (n1.subject = n2.subject)
Buffers: shared hit=25757 read=375369, temp read=22444 written=22996
-> Parallel Seq Scan on ncbitaxon n1 (cost=0.00..295443.22 rows=168032 width=17) (actual time=0.021..447.123 rows=812952 loops=3)
Filter: ((predicate = 'rdf:type'::text) AND (object = 'owl:Class'::text))
Rows Removed by Filter: 4250687
Buffers: shared hit=12868 read=187632
-> Parallel Hash (cost=279619.35..279619.35 rows=1002811 width=17) (actual time=694.169..694.170 rows=812951 loops=3)
Buckets: 65536 Batches: 64 Memory Usage: 2624kB
Buffers: shared hit=12772 read=187728, temp written=11456
-> Parallel Seq Scan on ncbitaxon n2 (cost=0.00..279619.35 rows=1002811 width=17) (actual time=139.958..552.807 rows=812951 loops=3)
Filter: (predicate = 'rdfs:subClassOf'::text)
Rows Removed by Filter: 4250687
Buffers: shared hit=12772 read=187728
Planning:
Buffers: shared hit=5 dirtied=1
Planning Time: 0.582 ms
JIT:
Functions: 39
Options: Inlining true, Optimization true, Expressions true, Deforming true
Timing: Generation 6.349 ms, Inlining 93.709 ms, Optimization 198.947 ms, Emission 126.610 ms, Total 425.615 ms
Execution Time: 1504.890 ms
(26 rows)
The output of explain in SQLite (with indexes) is:
addr opcode p1 p2 p3 p4 p5 comment
---- ------------- ---- ---- ---- ------------- -- -------------
0 Init 0 27 0 0 Start at 27
1 OpenRead 0 34019 0 6 0 root=34019 iDb=0; ncbitaxon
2 OpenRead 2 519613 0 k(2,,) 2 root=519613 iDb=0; idx_ncbitaxon_object
3 String8 0 1 0 owl:Class 0 r[1]='owl:Class'
4 SeekGE 2 26 1 1 0 key=r[1]
5 IdxGT 2 26 1 1 0 key=r[1]
6 DeferredSeek 2 0 0 0 Move 0 to 2.rowid if needed
7 Column 0 4 2 0 r[2]=ncbitaxon.predicate
8 Ne 3 25 2 BINARY-8 82 if r[2]!=r[3] goto 25
9 Integer 0 4 0 0 r[4]=0; Init EXISTS result
10 Integer 1 5 0 0 r[5]=1; LIMIT counter
11 OpenRead 1 34019 0 5 0 root=34019 iDb=0; ncbitaxon
12 OpenRead 3 332263 0 k(2,,) 2 root=332263 iDb=0; idx_ncbitaxon_subject
13 Column 0 3 6 0 r[6]=ncbitaxon.subject
14 SeekGE 3 22 6 1 0 key=r[6]
15 IdxGT 3 22 6 1 0 key=r[6]
16 DeferredSeek 3 0 1 0 Move 1 to 3.rowid if needed
17 Column 1 4 7 0 r[7]=ncbitaxon.predicate
18 Ne 8 21 7 BINARY-8 82 if r[7]!=r[8] goto 21
19 Integer 1 4 0 0 r[4]=1
20 DecrJumpZero 5 22 0 0 if (--r[5])==0 goto 22
21 Next 3 15 1 0
22 If 4 25 1 0
23 Column 0 3 10 0 r[10]=ncbitaxon.subject
24 ResultRow 10 1 0 0 output=r[10]
25 Next 2 5 1 0
26 Halt 0 0 0 0
27 Transaction 0 0 77 0 1 usesStmtJournal=0
28 String8 0 3 0 rdf:type 0 r[3]='rdf:type'
29 String8 0 8 0 rdfs:subClassOf 0 r[8]='rdfs:subClassOf'
30 Goto 0 1 0 0
Finally, here is the output of explain query plan in SQLite:
QUERY PLAN
|--SEARCH TABLE ncbitaxon AS n1 USING INDEX idx_ncbitaxon_object (object=?)
`--CORRELATED SCALAR SUBQUERY 1
`--SEARCH TABLE ncbitaxon AS n2 USING INDEX idx_ncbitaxon_subject (subject=?)
CodePudding user response：
I cannot give a complete answer, but here are some ideas:
In the slow plan, PostgreSQL underestimates the number of rows found in
ncbitaxon n1by a factor of almost 5. Try to improve that estimate, either by runningANALYZEto collect fresh statistics, or, if that is not sufficient, by creating extended statistics for the correlation of these columns.If that estimate is more accurate, the slow plan will be estimated with a higher cost and will not be chosen.
In the slow plan, the repeated index scan on
ncbitaxon n2is much more expensive than PostgreSQL estimates. This is partly due to the mis-estimate above, but perhapsrandom_page_costis set lower than appropriate for your hardware, so that PostgreSQL underestimates the cost of an index scan.