Postgres multi-join query optimization with conditions on multiple tables

Question

SUMMARY

Adding certain criteria in a multi-table join with many rows ends up with orders of magnitude slower queries. I've tried a lot of things to make this faster, including every type of table join, reordering the joins, reordering the WHERE clause, doing subqueries, using CASE statements in the WHERE clause, etc.

The SQL specifics are below.

QUESTIONS

Why does the addition of this simple condition cause the planner to drastically change its execution plan?
Is it possible to tell the planner how to analyze a specific condition first without drastically changing the query or doing subqueries (using WITH for example)

Note: I am attempting to write a generic SQL builder for an API, allowing callers to specify arbitrary conditions at any point in the graph. The issue is that some of these calls are blazing fast and others are not due to the way Postgres plans executions. Optimizations crafted specifically for this query will not help me satisfy the larger goal of a generic SQL builder.

DETAILS

I have a schema that stores vertices and edges (a simplistic graph database) in Postgres:

CREATE TABLE IF NOT EXISTS vertex (type text, id serial, name text, data jsonb, UNIQUE (id))
CREATE INDEX vertex_data_idx ON vertex USING gin (data jsonb_path_ops)
CREATE INDEX vertex_type_idx ON vertex (type)
CREATE INDEX vertex_name_idx ON vertex (name)
CREATE TABLE IF NOT EXISTS edge (src integer REFERENCES vertex (id), dst integer REFERENCES vertex (id))
CREATE INDEX edge_src_idx ON edge (src)
CREATE INDEX edge_dst_idx ON edge (dst)

The schema stores graphs, one of which is like this: PLANET --> CONTINENT --> COUNTRY --> REGION

There are 447554 total vertices and 3155047 total edges in my sample database, but the data that is relevant is here:

5 PLANETs (each relates to 5 CONTINENTs)
25 CONTINENTs (each relates to 2500 COUNTRYs)
62500 COUNTRYs (25% of which relate to 100 REGIONs each, the rest have no REGION relationships)
250000 REGIONs

This query looking for planets that have spanish speakers in any given region is fast:

SELECT DISTINCT 
    v1.name as name, v1.id as id 
FROM vertex v1 
  LEFT JOIN edge e1 ON (v1.id = e1.src) 
  LEFT JOIN vertex v2 ON (v2.id = e1.dst) 
  LEFT JOIN edge e2 ON (v2.id = e2.src) 
  LEFT JOIN vertex v3 ON (v3.id = e2.dst) 
  LEFT JOIN edge e3 ON (v3.id = e3.src) 
  LEFT JOIN vertex v4 ON (v4.id = e3.dst)
WHERE
  v4.type = 'REGION' AND 
  v4.data @> '{"languages":["spanish"]}'::jsonb

Planning time: 6.289 ms Execution time: 0.744 ms

When I add a condition on an indexed column in the first table in the graph (v1) that has no effect on the outcome, the query is 12,657 times slower:

SELECT DISTINCT 
    v1.name as name, v1.id as id 
FROM vertex v1 
  LEFT JOIN edge e1 ON (v1.id = e1.src) 
  LEFT JOIN vertex v2 ON (v2.id = e1.dst) 
  LEFT JOIN edge e2 ON (v2.id = e2.src) 
  LEFT JOIN vertex v3 ON (v3.id = e2.dst) 
  LEFT JOIN edge e3 ON (v3.id = e3.src) 
  LEFT JOIN vertex v4 ON (v4.id = e3.dst)
WHERE
  v1.type = 'PLANET' AND 
  v4.type = 'REGION' AND 
  v4.data @> '{"languages":["spanish"]}'::jsonb

Planning time: 7.664 ms Execution time: 89010.096 ms

This is the EXPLAIN (ANALYZE, BUFFERS) on the first, fast call:

 Unique  (cost=154592.03..155453.96 rows=114925 width=28) (actual time=0.585..0.616 rows=4 loops=1)
   Buffers: shared hit=92
   ->  Sort  (cost=154592.03..154879.34 rows=114925 width=28) (actual time=0.579..0.588 rows=4 loops=1)
         Sort Key: v1.name, v1.id
         Sort Method: quicksort  Memory: 17kB
         Buffers: shared hit=92
         ->  Nested Loop  (cost=37.96..142377.39 rows=114925 width=28) (actual time=0.155..0.549 rows=4 loops=1)
               Buffers: shared hit=92
               ->  Nested Loop  (cost=37.53..80131.76 rows=114925 width=4) (actual time=0.141..0.468 rows=4 loops=1)
                     Join Filter: (v2.id = e1.dst)
                     Buffers: shared hit=76
                     ->  Nested Loop  (cost=37.10..49179.08 rows=14270 width=8) (actual time=0.126..0.386 rows=4 loops=1)
                           Buffers: shared hit=60
                           ->  Nested Loop  (cost=36.68..41450.17 rows=14270 width=4) (actual time=0.112..0.304 rows=4 loops=1)
                                 Join Filter: (v3.id = e2.dst)
                                 Buffers: shared hit=44
                                 ->  Nested Loop  (cost=36.25..37606.57 rows=1772 width=8) (actual time=0.092..0.209 rows=4 loops=1)
                                       Buffers: shared hit=28
                                       ->  Nested Loop  (cost=35.83..36646.82 rows=1772 width=4) (actual time=0.074..0.116 rows=4 loops=1)
                                             Buffers: shared hit=12
                                             ->  Bitmap Heap Scan on vertex v4  (cost=30.99..1514.00 rows=220 width=4) (actual time=0.039..0.042 rows=1 loops=1)
                                                   Recheck Cond: (data @> '{"languages":["spanish"]}'::jsonb)
                                                   Filter: (type = 'REGION'::text)
                                                   Heap Blocks: exact=1
                                                   Buffers: shared hit=5
                                                   ->  Bitmap Index Scan on vertex_data_idx  (cost=0.00..30.94 rows=392 width=0) (actual time=0.020..0.020 rows=1 loops=1)
                                                         Index Cond: (data @> '{"languages":["spanish"]}'::jsonb)
                                                         Buffers: shared hit=4
                                             ->  Bitmap Heap Scan on edge e3  (cost=4.84..159.12 rows=57 width=8) (actual time=0.023..0.037 rows=4 loops=1)
                                                   Recheck Cond: (dst = v4.id)
                                                   Heap Blocks: exact=4
                                                   Buffers: shared hit=7
                                                   ->  Bitmap Index Scan on edge_dst_idx  (cost=0.00..4.82 rows=57 width=0) (actual time=0.013..0.013 rows=4 loops=1)
                                                         Index Cond: (dst = v4.id)
                                                         Buffers: shared hit=3
                                       ->  Index Only Scan using vertex_id_key on vertex v3  (cost=0.42..0.53 rows=1 width=4) (actual time=0.008..0.011 rows=1 loops=4)
                                             Index Cond: (id = e3.src)
                                             Heap Fetches: 4
                                             Buffers: shared hit=16
                                 ->  Index Scan using edge_dst_idx on edge e2  (cost=0.43..1.46 rows=57 width=8) (actual time=0.008..0.011 rows=1 loops=4)
                                       Index Cond: (dst = e3.src)
                                       Buffers: shared hit=16
                           ->  Index Only Scan using vertex_id_key on vertex v2  (cost=0.42..0.53 rows=1 width=4) (actual time=0.006..0.009 rows=1 loops=4)
                                 Index Cond: (id = e2.src)
                                 Heap Fetches: 4
                                 Buffers: shared hit=16
                     ->  Index Scan using edge_dst_idx on edge e1  (cost=0.43..1.46 rows=57 width=8) (actual time=0.005..0.008 rows=1 loops=4)
                           Index Cond: (dst = e2.src)
                           Buffers: shared hit=16
               ->  Index Scan using vertex_id_key on vertex v1  (cost=0.42..0.53 rows=1 width=28) (actual time=0.006..0.009 rows=1 loops=4)
                     Index Cond: (id = e1.src)
                     Buffers: shared hit=16
 Planning time: 6.940 ms
 Execution time: 0.714 ms

And on the second, slow call:

 HashAggregate  (cost=592.23..592.24 rows=1 width=28) (actual time=89009.873..89009.885 rows=4 loops=1)
   Group Key: v1.name, v1.id
   Buffers: shared hit=11644657 read=1240045
   ->  Nested Loop  (cost=2.98..592.22 rows=1 width=28) (actual time=9098.961..89009.833 rows=4 loops=1)
         Buffers: shared hit=11644657 read=1240045
         ->  Nested Loop  (cost=2.56..306.89 rows=522 width=32) (actual time=0.424..30066.007 rows=3092522 loops=1)
               Buffers: shared hit=454795 read=46267
               ->  Nested Loop  (cost=2.13..86.31 rows=65 width=36) (actual time=0.306..2120.293 rows=62500 loops=1)
                     Buffers: shared hit=239162 read=12162
                     ->  Nested Loop  (cost=1.70..51.10 rows=65 width=32) (actual time=0.261..574.490 rows=62500 loops=1)
                           Buffers: shared hit=488 read=562
actual time=0.205..1.206 rows=25 loops=1)p  (cost=1.27..23.95 rows=8 width=36) (--More--
                                 Buffers: shared hit=109 read=17
                                 ->  Nested Loop  (cost=0.85..19.62 rows=8 width=32) (actual time=0.173..0.547 rows=25 loops=1)
                                       Buffers: shared hit=12 read=14
                                       ->  Index Scan using vertex_type_idx on vertex v1  (cost=0.42..8.44 rows=1 width=28) (actual time=0.123..0.153 rows=5 loops=1)
                                             Index Cond: (type = 'PLANET'::text)
                                             Buffers: shared hit=2 read=4
                                       ->  Index Scan using edge_src_idx on edge e1  (cost=0.43..10.18 rows=100 width=8) (actual time=0.021..0.039 rows=5 loops=5)
                                             Index Cond: (src = v1.id)
                                             Buffers: shared hit=10 read=10
                                 ->  Index Only Scan using vertex_id_key on vertex v2  (cost=0.42..0.53 rows=1 width=4) (actual time=0.009..0.013 rows=1 loops=25)
                                       Index Cond: (id = e1.dst)
                                       Heap Fetches: 25
                                       Buffers: shared hit=97 read=3
43..2.39 rows=100 width=8) (actual time=0.031..8.504 rows=2500 loops=25)(cost=0.--More--
                                 Index Cond: (src = v2.id)
                                 Buffers: shared hit=379 read=545
                     ->  Index Only Scan using vertex_id_key on vertex v3  (cost=0.42..0.53 rows=1 width=4) (actual time=0.010..0.013 rows=1 loops=62500)
                           Index Cond: (id = e2.dst)
                           Heap Fetches: 62500
                           Buffers: shared hit=238674 read=11600
               ->  Index Scan using edge_src_idx on edge e3  (cost=0.43..2.39 rows=100 width=8) (actual time=0.013..0.163 rows=49 loops=62500)
                     Index Cond: (src = v3.id)
                     Buffers: shared hit=215633 read=34105
         ->  Index Scan using vertex_id_key on vertex v4  (cost=0.42..0.54 rows=1 width=4) (actual time=0.013..0.013 rows=0 loops=3092522)
               Index Cond: (id = e3.dst)
               Filter: ((data @> '{"languages":["spanish"]}'::jsonb) AND (type = 'REGION'::text))
               Rows Removed by Filter: 1
               Buffers: shared hit=11189862 read=1193778
 Planning time: 7.664 ms
 Execution time: 89010.096 ms

Remove the LEFT JOINs. They are not needed and can only confuse the optimizer. — Gordon Linoff, Aug 2 at 20:53
The outer join on v4 is useless because it's effectively turned into an inner join due to the where condition — a_horse_with_no_name, Aug 2 at 21:28

halfer · Answer 1 · 2016-08-24 05:57:18Z

[posted as an answer, because I need the formatting]

The edge table desparately needs a primary key (this implies NOT NULL for {src,dst} which is good):

CREATE TABLE IF NOT EXISTS edge
    ( src integer NOT NULL REFERENCES vertex (id)
    , dst integer NOT NULL REFERENCES vertex (id)
    , PRIMARY KEY (src,dst)
    );
CREATE UNIQUE INDEX edge_dst_src_idx ON edge (dst, src);

-- the estimates in the question seem to be off, statistics may be absent.
VACUUM ANALYZE edge; -- refresh the statistics
VACUUM ANALYZE vertex;

And I'd combine the {type,name} indexes, too (type appears to have a very low cardinality). Maybe even make it UNIQUE and NOT NULL, but I don't know your data.

CREATE INDEX vertex_type_name_idx ON vertex (type, name);

Msf vtp · Answer 2 · 2016-08-10 04:12:53Z

up vote 0 down vote

I think using a sub-query will make the postgresql to not be able to use index. So try following query to test the performance improvement by not using the index:

select * from (
SELECT DISTINCT 
    v1.name as name, v1.id as id, v1.type as v1_type
FROM vertex v1 
  LEFT JOIN edge e1 ON (v1.id = e1.src) 
  LEFT JOIN vertex v2 ON (v2.id = e1.dst) 
  LEFT JOIN edge e2 ON (v2.id = e2.src) 
  LEFT JOIN vertex v3 ON (v3.id = e2.dst) 
  LEFT JOIN edge e3 ON (v3.id = e3.src) 
  LEFT JOIN vertex v4 ON (v4.id = e3.dst)
WHERE
  v4.type = 'REGION' AND 
  v4.data @> '{"languages":["spanish"]}'::jsonb
) t1 
where v1_type = 'PLANET'

answered Aug 10 at 4:12

Msf vtp

52937

Thanks for the comment. I've tried a subquery and it does do what I expect, but unfortunately I'm trying to create a generic query builder. These kinds of specific optimizations are useful when testing, but I'm starting to feel that there is no generic way to force the planner to use a specific index before another without reorganizing queries into subqueries (which defeats the "generic query builder" directive). – Voluntari Aug 11 at 12:39

@Voluntari I am not familiar with postgresql enough but in mysql and oracle it is possible to say to not using an index. – Msf vtp Aug 11 at 12:42

1

@Msfvtp "I think using a sub-query will make the postgresql to not be able to use index" That would be a big failure of any query optimiser. It is certainly not true of Oracle, and I doubt that it is true of any mainstream RDBMS. – David Aldridge Aug 27 at 10:40

@DavidAldridge Thank you for attention. I mean in outer query cannot use index. In this example it can't use index for v1_type = 'PLANET' criteria. – Msf vtp Aug 27 at 11:04

@Msfvtp The optimizer can perform predicate pushing, in which it moves the predicate inside the inline view if it is valid to do so. View merging is also possible, where the query is "flattened" so no inline view is present at all. Check execution plans to be sure. – David Aldridge Aug 27 at 12:22

| show 2 more comments

asked	29 days ago
viewed	27 times
active	5 days ago

current community

your communities

more stack exchange communities

Postgres multi-join query optimization with conditions on multiple tables

SUMMARY

QUESTIONS

DETAILS

2 Answers 2

Your Answer

Not the answer you're looking for? Browse other questions tagged sql database postgresql join query-optimization or ask your own question.

Visit Chat

Hot Network Questions

current community

your communities

more stack exchange communities

Postgres multi-join query optimization with conditions on multiple tables

SUMMARY

QUESTIONS

DETAILS

2 Answers 2

Your Answer

Sign up or log in

Post as a guest

Not the answer you're looking for? Browse other questions tagged sql database postgresql join query-optimization or ask your own question.

Visit Chat

Related

Hot Network Questions