When does PostgreSQL collapse subqueries to join?

Hi everybody,

Denis from SO (see his latest comment) advised me to post my question
here:
http://stackoverflow.com/questions/27363263/when-does-postgresql-collapse-subqueries-to-joins-and-when-not
Please also read all the comments as they contain valuable data as well.

What we actually have now is that PostgreSQL collapses subqueries to
joins but a way differently than using "normal joins" by using "Merge
Semi Joins" or "Nested Loop Semi Joins" (btw an explanation of these
would be great here :) ). The queries given in the post are reduced to
the problem at hand and the by-PostgreSQL-optimized version performed
very well (bit slower than "normal joins"). Regarding our actual query
however, the still-different query plan leads to a big performance
issue. We actually need the complete rows of a instead of a.id. I
prepared the query plans for you (please note, that querie are executed
empty file and mem chaches):



################ Perfect Plan ###############
We assume all our queries to be equivalent and therefore want PostgreSQL
to re-plan the others to this one.

explain analyze verbose select * from a where a.id in (select a.id from
a inner join text_b b1 on (a.id=b1.a_id) inner join text_b b2 on
(a.id=b2.a_id) where b1.x='x1' and b1.y='y1' and b2.x='x2' and b2.y='y2'
order by a.date desc limit 20);

QUERY PLAN

----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
  Nested Loop  (cost=183.30..191.34 rows=1 width=135) (actual
time=812.486..918.561 rows=20 loops=1)
    Output: a.id, a.date, a.content1, a.content2, a.content3,
a.content4, a.content5, a.content6n, a.content7, a.content8, a.content9
    ->  HashAggregate  (cost=182.87..182.88 rows=1 width=4) (actual
time=804.866..804.884 rows=20 loops=1)
          Output: a_1.id
          Group Key: a_1.id
          ->  Limit  (cost=182.85..182.86 rows=1 width=8) (actual
time=804.825..804.839 rows=20 loops=1)
                Output: a_1.id, a_1.date
                ->  Sort  (cost=182.85..182.86 rows=1 width=8) (actual
time=804.823..804.829 rows=20 loops=1)
                      Output: a_1.id, a_1.date
                      Sort Key: a_1.date
                      Sort Method: top-N heapsort  Memory: 25kB
                      ->  Nested Loop  (cost=1.57..182.84 rows=1
width=8) (actual time=96.737..803.871 rows=739 loops=1)
                            Output: a_1.id, a_1.date
                            ->  Merge Join  (cost=1.14..178.74 rows=1
width=8) (actual time=64.829..83.489 rows=739 loops=1)
                                  Output: b1.a_id, b2.a_id
                                  Merge Cond: (b1.a_id = b2.a_id)
                                  ->  Index Only Scan using text_b_y_x_y
on public.text_b b1  (cost=0.57..163.29 rows=3936 width=4) (actual
time=34.811..47.328 rows=15195 loops=1)
                                        Output: b1.x, b1.y, b1.a_id
                                        Index Cond: ((b1.x = 'x1'::text)
AND (b1.y = 'y1'::text))
                                        Heap Fetches: 0
                                  ->  Index Only Scan using text_b_y_x_y
on public.text_b b2  (cost=0.57..5.49 rows=46 width=4) (actual
time=22.123..30.940 rows=1009 loops=1)
                                        Output: b2.x, b2.y, b2.a_id
                                        Index Cond: ((b2.x = 'x2'::text)
AND (b2.y = 'y2'::text))
                                        Heap Fetches: 0
                            ->  Index Only Scan using a_id_date on
public.a a_1  (cost=0.43..4.09 rows=1 width=8) (actual time=0.970..0.973
rows=1 loops=739)
                                  Output: a_1.id, a_1.date
                                  Index Cond: (a_1.id = b1.a_id)
                                  Heap Fetches: 0
    ->  Index Scan using a_id_date on public.a  (cost=0.43..8.45 rows=1
width=135) (actual time=5.677..5.679 rows=1 loops=20)
          Output: a.id, a.date, a.content1, a.content2, a.content3,
a.content4, a.content5, a.content6n, a.content7, a.content8, a.content9
          Index Cond: (a.id = a_1.id)
  Planning time: 331.190 ms
  Execution time: 918.694 ms


###################### Not so perfect Plan ##################
Because PostgreSQL does not re-plan the id-only query from SO to the
perfect query, we also see here a performance degradation.

explain analyze verbose select * from a where a.id in (select a.id from
a where a.id in (select text_b.a_id from text_b where text_b.x='x1' and
text_b.y='y1') and a.id in (select text_b.a_id from text_b where
text_b.x='x2' and text_b.y='y2') order by a.date desc limit 20);

QUERY PLAN

----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
  Nested Loop  (cost=384.48..392.51 rows=1 width=135) (actual
time=1311.680..1426.135 rows=20 loops=1)
    Output: a.id, a.date, a.content1, a.content2, a.content3,
a.content4, a.content5, a.content6n, a.content7, a.content8, a.content9
    ->  HashAggregate  (cost=384.04..384.05 rows=1 width=4) (actual
time=1298.447..1298.470 rows=20 loops=1)
          Output: a_1.id
          Group Key: a_1.id
          ->  Limit  (cost=384.03..384.03 rows=1 width=8) (actual
time=1298.411..1298.426 rows=20 loops=1)
                Output: a_1.id, a_1.date
                ->  Sort  (cost=384.03..384.03 rows=1 width=8) (actual
time=1298.409..1298.416 rows=20 loops=1)
                      Output: a_1.id, a_1.date
                      Sort Key: a_1.date
                      Sort Method: top-N heapsort  Memory: 25kB
                      ->  Merge Semi Join  (cost=1.57..384.02 rows=1
width=8) (actual time=160.186..1297.628 rows=739 loops=1)
                            Output: a_1.id, a_1.date
                            Merge Cond: (a_1.id = text_b.a_id)
                            ->  Nested Loop  (cost=1.00..210.76 rows=46
width=12) (actual time=80.587..1236.967 rows=1009 loops=1)
                                  Output: a_1.id, a_1.date, text_b_1.a_id
                                  ->  Index Only Scan using text_b_y_x_y
on public.text_b text_b_1  (cost=0.57..5.49 rows=46 width=4) (actual
time=51.190..63.400 rows=1009 loops=1)
                                        Output: text_b_1.x, text_b_1.y,
text_b_1.a_id
                                        Index Cond: ((text_b_1.x =
'x2'::text) AND (text_b_1.y = 'y2'::text))
                                        Heap Fetches: 0
                                  ->  Index Only Scan using a_id_date on
public.a a_1  (cost=0.43..4.45 rows=1 width=8) (actual time=1.158..1.160
rows=1 loops=1009)
                                        Output: a_1.id, a_1.date
                                        Index Cond: (a_1.id = text_b_1.a_id)
                                        Heap Fetches: 0
                            ->  Index Only Scan using text_b_y_x_y on
public.text_b  (cost=0.57..163.29 rows=3936 width=4) (actual
time=36.963..54.396 rows=15194 loops=1)
                                  Output: text_b.x, text_b.y, text_b.a_id
                                  Index Cond: ((text_b.x = 'x1'::text)
AND (text_b.y = 'y1'::text))
                                  Heap Fetches: 0
    ->  Index Scan using a_id_date on public.a  (cost=0.43..8.45 rows=1
width=135) (actual time=6.376..6.378 rows=1 loops=20)
          Output: a.id, a.date, a.content1, a.content2, a.content3,
a.content4, a.content5, a.content6n, a.content7, a.content8, a.content9
          Index Cond: (a.id = a_1.id)
  Planning time: 248.279 ms
  Execution time: 1426.337 ms


################### Slow Joins ##########################
Directly querying from the join performs worse.

explain analyze verbose select * from a inner join text_b b1 on
(a.id=b1.a_id) inner join text_b b2 on (a.id=b2.a_id) where b1.x='x1'
and b1.y='y1' and b2.x='x2' and b2.y='y2' order by a.date desc limit 20;

QUERY PLAN

-----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
  Limit  (cost=186.83..186.83 rows=1 width=177) (actual
time=4133.420..4133.434 rows=20 loops=1)
    Output: a.id, a.date, a.content1, a.content2, a.content3,
a.content4, a.content5, a.content6n, a.content7, a.content8, a.content9,
b1.a_id, b1.x, b1.y, b2.a_id, b2.x, b2.y, a.date
    ->  Sort  (cost=186.83..186.83 rows=1 width=177) (actual
time=4133.417..4133.423 rows=20 loops=1)
          Output: a.id, a.date, a.content1, a.content2, a.content3,
a.content4, a.content5, a.content6n, a.content7, a.content8, a.content9,
b1.a_id, b1.x, b1.y, b2.a_id, b2.x, b2.y, a.date
          Sort Key: a.date
          Sort Method: top-N heapsort  Memory: 34kB
          ->  Nested Loop  (cost=1.57..186.82 rows=1 width=177) (actual
time=109.094..4130.290 rows=739 loops=1)
                Output: a.id, a.date, a.content1, a.content2,
a.content3, a.content4, a.content5, a.content6n, a.content7, a.content8,
a.content9, b1.a_id, b1.x, b1.y, b2.a_id, b2.x, b2.y, a.date
                ->  Merge Join  (cost=1.14..178.74 rows=1 width=42)
(actual time=72.023..94.234 rows=739 loops=1)
                      Output: b1.a_id, b1.x, b1.y, b2.a_id, b2.x, b2.y
                      Merge Cond: (b1.a_id = b2.a_id)
                      ->  Index Only Scan using text_b_y_x_y on
public.text_b b1  (cost=0.57..163.29 rows=3936 width=21) (actual
time=36.084..50.308 rows=15195 loops=1)
                            Output: b1.x, b1.y, b1.a_id
                            Index Cond: ((b1.x = 'x1'::text) AND (b1.y =
'y1'::text))
                            Heap Fetches: 0
                      ->  Index Only Scan using text_b_y_x_y on
public.text_b b2  (cost=0.57..5.49 rows=46 width=21) (actual
time=20.227..37.654 rows=1009 loops=1)
                            Output: b2.x, b2.y, b2.a_id
                            Index Cond: ((b2.x = 'x2'::text) AND (b2.y =
'y2'::text))
                            Heap Fetches: 0
                ->  Index Scan using a_id_date on public.a
(cost=0.43..8.07 rows=1 width=135) (actual time=5.454..5.457 rows=1
loops=739)
                      Output: a.id, a.date, a.content1, a.content2,
a.content3, a.content4, a.content5, a.content6n, a.content7, a.content8,
a.content9
                      Index Cond: (a.id = b1.a_id)
  Planning time: 332.545 ms
  Execution time: 4133.574 ms

################### Slow Subqueries ##########################
Directly querying from the subqueries performs even worse.


explain analyze verbose select * from a where a.id in (select
text_b.a_id from text_b where text_b.x='x1' and text_b.y='y1') and a.id
in (select text_b.a_id from text_b where text_b.x='x2' and
text_b.y='y2') order by a.date desc limit 20;

QUERY PLAN

---------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
  Limit  (cost=568.02..568.03 rows=1 width=135) (actual
time=9765.174..9765.190 rows=20 loops=1)
    Output: a.id, a.date, a.content1, a.content2, a.content3,
a.content4, a.content5, a.content6n, a.content7, a.content8, a.content9
    ->  Sort  (cost=568.02..568.03 rows=1 width=135) (actual
time=9765.173..9765.180 rows=20 loops=1)
          Output: a.id, a.date, a.content1, a.content2, a.content3,
a.content4, a.content5, a.content6n, a.content7, a.content8, a.content9
          Sort Key: a.date
          Sort Method: top-N heapsort  Memory: 30kB
          ->  Merge Semi Join  (cost=1.57..568.01 rows=1 width=135)
(actual time=294.909..9762.978 rows=739 loops=1)
                Output: a.id, a.date, a.content1, a.content2,
a.content3, a.content4, a.content5, a.content6n, a.content7, a.content8,
a.content9
                Merge Cond: (a.id = text_b.a_id)
                ->  Nested Loop  (cost=1.00..394.76 rows=46 width=139)
(actual time=94.441..9668.179 rows=1009 loops=1)
                      Output: a.id, a.date, a.content1, a.content2,
a.content3, a.content4, a.content5, a.content6n, a.content7, a.content8,
a.content9, text_b_1.a_id
                      ->  Index Only Scan using text_b_y_x_y on
public.text_b text_b_1  (cost=0.57..5.49 rows=46 width=4) (actual
time=52.588..67.307 rows=1009 loops=1)
                            Output: text_b_1.x, text_b_1.y, text_b_1.a_id
                            Index Cond: ((text_b_1.x = 'x2'::text) AND
(text_b_1.y = 'y2'::text))
                            Heap Fetches: 0
                      ->  Index Scan using a_id_date on public.a
(cost=0.43..8.45 rows=1 width=135) (actual time=9.485..9.511 rows=1
loops=1009)
                            Output: a.id, a.date, a.content1,
a.content2, a.content3, a.content4, a.content5, a.content6n, a.content7,
a.content8, a.content9
                            Index Cond: (a.id = text_b_1.a_id)
                ->  Index Only Scan using text_b_y_x_y on public.text_b
(cost=0.57..163.29 rows=3936 width=4) (actual time=22.705..86.822
rows=15194 loops=1)
                      Output: text_b.x, text_b.y, text_b.a_id
                      Index Cond: ((text_b.x = 'x1'::text) AND (text_b.y
= 'y1'::text))
                      Heap Fetches: 0
  Planning time: 267.442 ms
  Execution time: 9765.339 m


What needs to be done in order to feed PostgreSQL with the last query
and achieve the performance of the first one?

Best regards,

--
Sven R. Kunze
TBZ-PARIV GmbH, Bernsdorfer Str. 210-212, 09130 Chemnitz
Tel: +49 (0)371 5347916, Fax: +49 (0)371 5347920
e-mail: srkunze@tbz-pariv.de
web: www.tbz-pariv.de

Geschäftsführer: Dr. Reiner Wohlgemuth
Sitz der Gesellschaft: Chemnitz
Registergericht: Chemnitz HRB 8543