Missed query planner optimization

Hi all,

this is about a limitation of the current query planner implementation 
which causes big performance declines for certain types of queries. 
Affected queries will typically execute about 1000 times slower than 
they could. Examples are given below.

After talking about this with David Rowley on the pgsql-bugs mailing 
list (bug #17964), it turns out that the reason for the problem 
apparently is that eligible IN clauses are always converted into 
semi-joins. This is done even in situations where such a conversion 
prevents further optimizations to be made.

Hence, it would be desirable that the planner would intelligently decide 
based on estimated costs whether or not an IN clause should be converted 
into a semi-join. The planner obviously can already correctly estimate 
which variant will be faster, as shown in the query plans below.

The tricky part is that it's unfortunately not guaranteed that we'll 
find the BEST possible solution if we decide independently for each IN 
clause, because estimated total costs will depend on the other IN 
clauses of the query as well. However, a simple heuristic solution would 
be to restrain from converting an IN clause into a semi-join if the 
estimated number of rows returned by the subselect is below a certain 
threshold. Then, the planner should make its final decision based on the 
estimated total cost of the two possible query variants (i.e. between 
applying the heuristic vs. not applying the heuristic).

Example queries follow. Full query plans are provided within the linked 
database fiddles.



Example 1: Combining an IN clause with OR.

SELECT * FROM book WHERE
   author_id IS NULL OR
   author_id IN (SELECT id FROM author WHERE name = 'some_name');

Execution time:                       159.227 ms
Execution time (optimized variant):     0.084 ms (1896 times faster)

Estimated cost:                     16933.31
Estimated cost (optimized variant):  2467.85     (6.86 times lower)

Full query plans here: https://dbfiddle.uk/SOOJBMwI



Example 2: Combining two IN clauses with OR.

SELECT * FROM book WHERE
   author_id IN (SELECT id FROM author WHERE name = 'some_name') OR
   publisher_id IN (SELECT id FROM publisher WHERE name = 'some_name');

Execution time:                       227.822 ms
Execution time (optimized variant):     0.088 ms (2589 times faster)

Estimated cost:                     20422.61
Estimated cost (optimized variant):  4113.39     (4.96 times lower)

Full query plans here: https://dbfiddle.uk/q6_4NuDX



Example 3: Combining an IN clause with UNION.

SELECT * FROM
   (SELECT * FROM table1 UNION SELECT * FROM table2) AS q
   WHERE id IN (SELECT id FROM table3);

Execution time:                        932.412 ms
Execution time (optimized variant):      0.728 ms (1281 times faster)

Estimated cost:                     207933.98
Estimated cost (optimized variant):     97.40     (2135 times lower)

Full query plans here: https://dbfiddle.uk/TXASgMZf



Example 4: Complex real-life query from our project.

The full query is linked below.

Execution time:                       72436.509 ms
Execution time (optimized variant):       0.201 ms (360381 times faster)

Estimated cost:                     3941783.92
Estimated cost (optimized variant):    1515.62     (2601 times lower)

Original query here: https://pastebin.com/raw/JsY1PzG3
Optimized query here: https://pastebin.com/raw/Xvq7zUY2



Now, I'm not familiar with the current planner implementation, but 
wanted to know whether there is anybody on this list who would be 
willing to work on this. Having the planner consider the costs of 
converting IN clauses into semi-joins obviously seems like a worthy 
goal. As shown, the performance improvements are gigantic for certain 
types of queries.

Thank you very much!

Mathias