Horton

Thread

  1. BUG #19059: PostgreSQL fails to evaluate the cheaper expression first, leading to 45X performance degradation

    PG Bug reporting form <noreply@postgresql.org> — 2025-09-20T16:08:11Z

    The following bug has been logged on the website:

Bug reference:      19059
Logged by:          Jinhui Lai
Email address:      jinhui.lai@qq.com
PostgreSQL version: 17.6
Operating system:   ubuntu 22.04
Description:        

Dear PG developers,

Thanks for reading my report. You can reproduce it as follows, please.

PG has applied short-circuit evaluation for the following queries, which
contain an OR expression in their WHERE clause. When "t0.c0 > 0" is true, PG
will skip to evaluate "EXISTS (SELECT 1 FROM t1 WHERE t1.c1 = t0.c0)",
since true and any boolean expression is true.

However, the optimizer fails to reorder the expressions in the WHERE clause
for the second query. You can observe this from the second row in the plan:
"Filter: (EXISTS(SubPlan 1) OR (c0 > 0))"
A more optimal strategy would be for PG to use its cost model to reorder
expressions, prioritizing the evaluation of less expensive operations first.


CREATE TABLE t0(c0 INT8);
INSERT INTO t1 VALUES(1);
CREATE TABLE t1(c1 INT8);
INSERT INTO t1 SELECT * FROM generate_series(1, 1000000);

SELECT t0.c0 FROM t0 WHERE  t0.c0 > 0 OR EXISTS (SELECT 1 FROM t1 WHERE
t1.c1 = t0.c0);
Time: 139.416 ms

SELECT t0.c0 FROM t0 WHERE EXISTS (SELECT 1 FROM t1 WHERE t1.c1 = t0.c0) OR
t0.c0 > 0;
Time: 6221.886 ms (00:06.222)

explain SELECT t0.c0 FROM t0 WHERE EXISTS (SELECT 1 FROM t1 WHERE t1.c1 =
t0.c0) OR t0.c0 > 0;
                                  QUERY PLAN
-------------------------------------------------------------------------------
 Seq Scan on t0  (cost=0.00..893306001.25 rows=1700 width=4)
   Filter: (EXISTS(SubPlan 1) OR (c0 > 0))
   SubPlan 1
     ->  Seq Scan on t1  (cost=0.00..350316.06 rows=1 width=0)
           Filter: (c1 = t0.c0)
 JIT:
   Functions: 7
   Options: Inlining true, Optimization true, Expressions true, Deforming
true

Thanks you once again. I look forward to your reply.
Best regard,
Jinhui

  2. Re: BUG #19059: PostgreSQL fails to evaluate the cheaper expression first, leading to 45X performance degradation

    Tom Lane <tgl@sss.pgh.pa.us> — 2025-09-20T21:19:22Z

    PG Bug reporting form <noreply@postgresql.org> writes:
> However, the optimizer fails to reorder the expressions in the WHERE clause
> for the second query. You can observe this from the second row in the plan:
> "Filter: (EXISTS(SubPlan 1) OR (c0 > 0))"
> A more optimal strategy would be for PG to use its cost model to reorder
> expressions, prioritizing the evaluation of less expensive operations first.

We do do that at the top AND level (cf. order_qual_clauses())
but we have not bothered for OR clauses.

The whole exercise is pretty questionable really, considering how weak
our cost model for expressions is.  We could easily end up pessimizing
a clause that the user had put into carefully-selected order.
While we've not gotten a huge amount of push-back about the top-level
re-ordering, there's been some complaints.  So I'm not eager to
propagate the idea further down.

			regards, tom lane

  3. Re: BUG #19059: PostgreSQL fails to evaluate the cheaper expression first, leading to 45X performance degradation

    Christophe Pettus <xof@thebuild.com> — 2025-09-20T22:54:54Z

    
> On Sep 20, 2025, at 14:19, Tom Lane <tgl@sss.pgh.pa.us> wrote:
> While we've not gotten a huge amount of push-back about the top-level
> re-ordering, there's been some complaints.  So I'm not eager to
> propagate the idea further down.

And tangentially, doesn't the SQL standard make it implementation-defined if OR short-circuits or not?

  4. Re: BUG #19059: PostgreSQL fails to evaluate the cheaper expression first, leading to 45X performance degradation

    Tom Lane <tgl@sss.pgh.pa.us> — 2025-09-20T23:19:03Z

    Christophe Pettus <xof@thebuild.com> writes:
> And tangentially, doesn't the SQL standard make it implementation-defined if OR short-circuits or not?

It looks like it says it's implementation-dependent, meaning
that not only is it not defined by the standard, but we're not
required to document it either:

    Subclause 6.3.3.3, “Rule evaluation order”:

	a) It is implementation-dependent whether expressions are
	actually evaluated from left to right when the precedence is
	not otherwise determined by the Formats or by parentheses.

	b) If evaluation of the inessential parts of an expression or
	search condition would cause an exception condition to be
	raised, then it is implementation-dependent whether or not
	that condition is raised.

	c) The declared type of a site that contains an intermediate
	result is implementation-dependent.

This is a good thing, because while we do mention boolean expression
re-ordering and short-circuiting, there's an awful lot of such details
that we've left undocumented.

			regards, tom lane

  5. Re: BUG #19059: PostgreSQL fails to evaluate the cheaper expression first, leading to 45X performance degradation

    Vik Fearing <vik@postgresfriends.org> — 2025-09-21T09:09:02Z

    On 21/09/2025 00:54, Christophe Pettus wrote:
>> On Sep 20, 2025, at 14:19, Tom Lane<tgl@sss.pgh.pa.us> wrote:
>> While we've not gotten a huge amount of push-back about the top-level
>> re-ordering, there's been some complaints.  So I'm not eager to
>> propagate the idea further down.
> And tangentially, doesn't the SQL standard make it implementation-defined if OR short-circuits or not?
>

Not that I can see.  The only implementation-defined mention in <boolean 
value expression> is:


"If the SQL-implementation supports Feature T101, “Enhanced nullability 
determination”, and if BVE conforms to an implementation-defined (IE011) 
rule that enables the SQL-implementation to correctly infer that, when 
BVE is True, then X cannot be null, then BVE is a known-not-null 
condition for X. "

-- 

Vik Fearing

  6. Re: BUG #19059: PostgreSQL fails to evaluate the cheaper expression first, leading to 45X performance degradation

    Jinhui Lai <jinhui.lai@qq.com> — 2025-09-21T16:05:34Z

    &gt; We&nbsp;do&nbsp;do&nbsp;that&nbsp;at&nbsp;the&nbsp;top&nbsp;AND&nbsp;level&nbsp;(cf.&nbsp;order_qual_clauses()), but&nbsp;we&nbsp;have&nbsp;not&nbsp;bothered&nbsp;for&nbsp;OR&nbsp;clauses.

Hi, Tom. Thanks for your reply.
I have another case that influences both AND/OR clauses. You can reproduce it as follows:


-- Create tables t0 and t1.&nbsp;
CREATE TABLE t0(c0 INT8); -- small table
INSERT INTO t0 SELECT * FROM generate_series(1, 1000);
CREATE TABLE t1(c1 INT8); &nbsp;-- large table
INSERT INTO t1 SELECT * FROM generate_series(1, 10000000);


-- These two short-circuit evaluation examples happen before scanning any tables, as their plans only contain one row.&nbsp;
SELECT (SELECT MIN(c1) FROM t1)&gt;0 OR TRUE; &nbsp;-- Time: 0.311 ms
SELECT (SELECT MIN(c1) FROM t1)&gt;0 AND FALSE; &nbsp;-- Time: 0.318 ms
explain SELECT (SELECT MIN(c1) FROM t1)&gt;0 OR TRUE;
&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; QUERY PLAN &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;
------------------------------------------
&nbsp;Result &nbsp;(cost=0.00..0.01 rows=1 width=1)


-- These two short-circuit evaluation examples may happen after scanning table t0, as their execution times are similar to that of the query "SELECT (SELECT MIN(c0) FROM t0)&gt;0".&nbsp;
SELECT (SELECT MIN(c0) FROM t0)&gt;0 OR (SELECT MIN(c1) FROM t1)&gt;0; &nbsp;-- Time: 0.416 ms
SELECT (SELECT MIN(c0) FROM t0)<0 AND (SELECT MIN(c1) FROM t1)&gt;0; -- Time: 0.640 ms


SELECT (SELECT MIN(c0) FROM t0)&gt;0; &nbsp;-- Time: 0.665 ms


-- As demonstrated by the following two queries, the optimizer fails to reorder expressions in the SELECT clause for AND/OR operations. This can be observed in their execution plans. Since t0 is smaller than t1, evaluating t0 first (based on the cost model) would be more efficient.&nbsp;
-- Particularly, given that PostgreSQL applies short-circuit evaluation during execution, the logical reordering of these expressions becomes a crucial optimization opportunity.


SELECT (SELECT MIN(c1) FROM t1)&gt;0 OR (SELECT MIN(c0) FROM t0)&gt;0;
Time: 148.815 ms
explain SELECT (SELECT MIN(c1) FROM t1)&gt;0 OR (SELECT MIN(c0) FROM t0)&gt;0;
&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; QUERY PLAN &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;&nbsp;
-----------------------------------------------------------------------------------------------
&nbsp;Result &nbsp;(cost=97348.95..97348.96 rows=1 width=1)
&nbsp; &nbsp;InitPlan 1
&nbsp; &nbsp; &nbsp;-&gt; &nbsp;Finalize Aggregate &nbsp;(cost=97331.43..97331.44 rows=1 width=8)
&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;-&gt; &nbsp;Gather &nbsp;(cost=97331.21..97331.42 rows=2 width=8)
&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;Workers Planned: 2
&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;-&gt; &nbsp;Partial Aggregate &nbsp;(cost=96331.21..96331.22 rows=1 width=8)
&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;-&gt; &nbsp;Parallel Seq Scan on t1 &nbsp;(cost=0.00..85914.57 rows=4166657 width=8)
&nbsp; &nbsp;InitPlan 2
&nbsp; &nbsp; &nbsp;-&gt; &nbsp;Aggregate &nbsp;(cost=17.50..17.51 rows=1 width=8)
&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;-&gt; &nbsp;Seq Scan on t0 &nbsp;(cost=0.00..15.00 rows=1000 width=8)




SELECT (SELECT MIN(c1) FROM t1)&gt;0 AND (SELECT MIN(c0) FROM t0)<0;
Time: 153.308 ms


explain SELECT (SELECT MIN(c1) FROM t1)&gt;0 AND (SELECT MIN(c0) FROM t0)<0;
&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; QUERY PLAN &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;&nbsp;
-----------------------------------------------------------------------------------------------
&nbsp;Result &nbsp;(cost=97348.95..97348.96 rows=1 width=1)
&nbsp; &nbsp;InitPlan 1
&nbsp; &nbsp; &nbsp;-&gt; &nbsp;Finalize Aggregate &nbsp;(cost=97331.43..97331.44 rows=1 width=8)
&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;-&gt; &nbsp;Gather &nbsp;(cost=97331.21..97331.42 rows=2 width=8)
&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;Workers Planned: 2
&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;-&gt; &nbsp;Partial Aggregate &nbsp;(cost=96331.21..96331.22 rows=1 width=8)
&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;-&gt; &nbsp;Parallel Seq Scan on t1 &nbsp;(cost=0.00..85914.57 rows=4166657 width=8)
&nbsp; &nbsp;InitPlan 2
&nbsp; &nbsp; &nbsp;-&gt; &nbsp;Aggregate &nbsp;(cost=17.50..17.51 rows=1 width=8)
&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;-&gt; &nbsp;Seq Scan on t0 &nbsp;(cost=0.00..15.00 rows=1000 width=8)


Thanks you once again. I look forward to your reply.
Best regard,
Jinhui