Обсуждение: BUG #19059: PostgreSQL fails to evaluate the cheaper expression first, leading to 45X performance degradation

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

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

> 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?

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

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. p.p1 {margin: 0.0px 0.0px 0.0px 0.0px; font: 11.0px Helvetica; color: #000000}p.p2 {margin: 0.0px 0.0px 0.0px 0.0px; font: 10.0px Helvetica; color: #000000}p.p3 {margin: 0.0px 0.0px 0.0px 0.0px; font: 8.0px Helvetica; color: #b3b3b3}span.s1 {color: #00008e}span.s2 {color: #5c55ec}span.s3 {font: 10.0px Helvetica; color: #000000}"

-- 

Vik Fearing