Message-ID: <a29936a0-e446-d4d1-6bd1-42d7212c26a0@gmail.com>
Date: Fri, 16 Jun 2023 14:56:07 +0200
MIME-Version: 1.0
User-Agent: Mozilla/5.0 (X11; Linux x86_64; rv:102.0) Gecko/20100101
 Thunderbird/102.11.0
Subject: Re: BUG #17964: Missed query planner optimization
Content-Language: de-AT
To: David Rowley <dgrowleyml@gmail.com>
References: <17964-cdeb9e3f89c18393@postgresql.org>
 <CAApHDvpj1rjTsOn34K0W9WpVptQHJkMQHt+db0FVWOxVK0OewQ@mail.gmail.com>
 <94608857-707f-55ce-99a0-ac500aeb06f8@gmail.com>
 <CAApHDvq_5v=G=9aS3QQwRUH-h1nf09Ycnzh=GQeDJtsYsQvd_g@mail.gmail.com>
 <8ca5637b-32c4-cb17-2de6-10f9248c5857@gmail.com>
 <b7440c1d-db4a-fb43-bd85-3a4f02277204@gmail.com>
 <CAApHDvqiZSEoJ1fGSkBLTY9cTQJAmjUgUH8PziFP0uRMr-ARLw@mail.gmail.com>
Cc: pgsql-bugs@lists.postgresql.org
From: Mathias Kunter <mathiaskunter@gmail.com>
In-Reply-To: 
 <CAApHDvqiZSEoJ1fGSkBLTY9cTQJAmjUgUH8PziFP0uRMr-ARLw@mail.gmail.com>
Content-Type: text/plain; charset=UTF-8; format=flowed
Content-Transfer-Encoding: 7bit
Archived-At: 
 <https://www.postgresql.org/message-id/a29936a0-e446-d4d1-6bd1-42d7212c26a0%40gmail.com>
Precedence: bulk

> We'd need a way to determine which is cheaper based on estimated costs

Yes, that decision must of course be based on estimated costs, and also 
the cost estimation must be reasonably accurate. In all examples which 
I've seen so far, the cost estimations were adequate.

> that might be, in my opinion, fairly tricky to do based on the order of
> how things currently are done in the query planner.

I don't know the details about the current planner implementation, but 
the planner obviously can already correctly estimate costs for both the 
IN and ANY(ARRAY()) variants.

> I was just trying to show that it's quite a tricky problem to
> fix properly.

Yes, the tricky part obviously is to decide whether or not an IN clause 
should be converted to a semi-join, because that decision depends on the 
other IN clauses of the query as well. So, it's unfortunately not 
possible to decide independently for each IN clause.

As you've already pointed out, doing an exhaustive search of all 
possible combinations is obviously problematic, since we'd have to check 
2^N possible query plans (with N being the number of IN clauses of the 
query). So, this is certainly NOT the way to go, unless maybe N<4 or so.

> Having the planner consider the costs of converting the IN to a semi-
> join and converting or not based on cost seems like a worthy goal.

It obviously is. As shown, the performance improvement can be gigantic 
for certain queries.

> If you think it's quite an easy project, then we'll welcome
> contributions to improve this.

I'm not familiar with the current implementation, but my understanding 
is that this should be quite easy to implement for someone who is 
currently working on planner-related issues.

After all, a reasonable heuristic solution can be as simple as this:


1) Create the query plan for the original query, using the current 
planner implementation. (That's the status quo.)

2) Create a modified version of the original input query where all of 
the IN clauses are replaced with ANY(ARRAY()). Create the query plan for 
that modified query version, using the current planner implementation.

3) Compare the two previously created query plans and execute the one 
with the lower estimated total cost. If you don't trust the planner's 
cost estimations for some reason, then only execute the modified version 
if its estimated cost is SIGNIFICANTLY lower.


A simple solution like this would already be good enough to avoid many 
of the horrifying worst case scenarios, where a query takes minutes when 
it should actually only take milliseconds.

It would of course be possible (and desirable) to come up with a more 
sophisticated heuristic than the one given above. For example, create a 
third version of the original query where only those IN clauses are 
replaced with ANY(ARRAY()) where the estimated number of rows returned 
by the subselect is below a certain threshold, and estimate costs for 
that modified query as well.

> The pgsql-hackers as a good emailing list to bring up the topic

Thank you for the hint. I'll continue the discussion over there.

Mathias