Subject: Re: POC, WIP: OR-clause support for indexes

From: Alena Rybakina <[email-masked]>
Date: Thu, 28 Nov 2024 22:33:23 +0300

On 28.11.2024 22:28, Ranier Vilela wrote:
> Em qui., 28 de nov. de 2024 às 16:03, Alena Rybakina 
> <[email-masked]> escreveu:
>
>     Hi! Thank you for the case.
>
>     On 28.11.2024 21:00, Alexander Lakhin wrote:
>     > Hello Alexander,
>     >
>     > 21.11.2024 09:34, Alexander Korotkov wrote:
>     >> I'm going to push this if no objections.
>     >
>     > Please look at the following query, which triggers an error after
>     > ae4569161:
>     > SET random_page_cost = 1;
>     > CREATE TABLE tbl(u UUID);
>     > CREATE INDEX idx ON tbl USING HASH (u);
>     > SELECT COUNT(*) FROM tbl WHERE u =
>     '00000000000000000000000000000000' OR
>     >   u = '11111111111111111111111111111111';
>     >
>     > ERROR:  XX000: ScalarArrayOpExpr index qual found where not allowed
>     > LOCATION:  ExecIndexBuildScanKeys, nodeIndexscan.c:1625
>     >
>     >
>     I found out what the problem is index scan method was not
>     generated. We
>     need to check this during OR clauses for SAOP transformation.
>
>     There is a patch to fix this problem.
>
> Hi.
> Thanks for the quick fix.
>
> But I wonder if it is not possible to avoid all if the index is useless?
> Maybe moving your fix to the beginning of the function?
>
> diff --git a/src/backend/optimizer/path/indxpath.c 
> b/src/backend/optimizer/path/indxpath.c
> index d827fc9f4d..5ea0b27d01 100644
> --- a/src/backend/optimizer/path/indxpath.c
> +++ b/src/backend/optimizer/path/indxpath.c
> @@ -3248,6 +3248,10 @@ match_orclause_to_indexcol(PlannerInfo *root,
>   Assert(IsA(orclause, BoolExpr));
>   Assert(orclause->boolop == OR_EXPR);
>
> + /* Ignore index if it doesn't support index scans */
> + if(!index->amsearcharray)
> + return NULL;
> +
Agree. I have updated the patch
>   /*
>   * Try to convert a list of OR-clauses to a single SAOP expression. Each
>   * OR entry must be in the form: (indexkey operator constant) or 
> (constant
>
> The test bug:
> EXPLAIN SELECT COUNT(*) FROM tbl WHERE u = 
> '00000000000000000000000000000000' OR u = 
> '11111111111111111111111111111111';
> QUERY PLAN
> ----------------------------------------------------------------------------------------------------------------------------------
>  Aggregate  (cost=12.46..12.47 rows=1 width=8)
>    ->  Bitmap Heap Scan on tbl  (cost=2.14..12.41 rows=18 width=0)
>          Recheck Cond: ((u = 
> '00000000-0000-0000-0000-000000000000'::uuid) OR (u = 
> '11111111-1111-1111-1111-111111111111'::uuid))
>          ->  BitmapOr  (cost=2.14..2.14 rows=18 width=0)
>                ->  Bitmap Index Scan on idx  (cost=0.00..1.07 rows=9 
> width=0)
>                      Index Cond: (u = 
> '00000000-0000-0000-0000-000000000000'::uuid)
>                ->  Bitmap Index Scan on idx  (cost=0.00..1.07 rows=9 
> width=0)
>                      Index Cond: (u = 
> '11111111-1111-1111-1111-111111111111'::uuid)
> (8 rows)
>
Thank you

-- 
Regards,
Alena Rybakina
Postgres Professional
diff --git a/src/backend/optimizer/path/indxpath.c b/src/backend/optimizer/path/indxpath.c
index d827fc9f4d9..5ea0b27d014 100644
--- a/src/backend/optimizer/path/indxpath.c
+++ b/src/backend/optimizer/path/indxpath.c
@@ -3248,6 +3248,10 @@ match_orclause_to_indexcol(PlannerInfo *root,
 	Assert(IsA(orclause, BoolExpr));
 	Assert(orclause->boolop == OR_EXPR);
 
+	/* Ignore index if it doesn't support index scans */
+	if(!index->amsearcharray)
+		return NULL;
+
 	/*
 	 * Try to convert a list of OR-clauses to a single SAOP expression. Each
 	 * OR entry must be in the form: (indexkey operator constant) or (constant
diff --git a/src/test/regress/expected/create_index.out b/src/test/regress/expected/create_index.out
index 1b0a5f0e9e1..ef8bbf4748c 100644
--- a/src/test/regress/expected/create_index.out
+++ b/src/test/regress/expected/create_index.out
@@ -1233,6 +1233,23 @@ SELECT count(*) FROM tenk1 WHERE stringu1 = 'TVAAAA';
     14
 (1 row)
 
+-- Transform OR-clauses to SAOP's shouldn't be chosen
+SET random_page_cost = 1;
+EXPLAIN (COSTS OFF)
+SELECT COUNT(*) FROM tenk1 WHERE stringu1 = 'TVAAAA' OR  stringu1 = 'TVAAAB';
+                                     QUERY PLAN                                     
+------------------------------------------------------------------------------------
+ Aggregate
+   ->  Bitmap Heap Scan on tenk1
+         Recheck Cond: ((stringu1 = 'TVAAAA'::name) OR (stringu1 = 'TVAAAB'::name))
+         ->  BitmapOr
+               ->  Bitmap Index Scan on hash_tuplesort_idx
+                     Index Cond: (stringu1 = 'TVAAAA'::name)
+               ->  Bitmap Index Scan on hash_tuplesort_idx
+                     Index Cond: (stringu1 = 'TVAAAB'::name)
+(8 rows)
+
+RESET random_page_cost;
 DROP INDEX hash_tuplesort_idx;
 RESET maintenance_work_mem;
 --
diff --git a/src/test/regress/sql/create_index.sql b/src/test/regress/sql/create_index.sql
index ddd0d9ad396..0e6529f3f3d 100644
--- a/src/test/regress/sql/create_index.sql
+++ b/src/test/regress/sql/create_index.sql
@@ -372,6 +372,11 @@ CREATE INDEX hash_tuplesort_idx ON tenk1 USING hash (stringu1 name_ops) WITH (fi
 EXPLAIN (COSTS OFF)
 SELECT count(*) FROM tenk1 WHERE stringu1 = 'TVAAAA';
 SELECT count(*) FROM tenk1 WHERE stringu1 = 'TVAAAA';
+-- Transform OR-clauses to SAOP's shouldn't be chosen
+SET random_page_cost = 1;
+EXPLAIN (COSTS OFF)
+SELECT COUNT(*) FROM tenk1 WHERE stringu1 = 'TVAAAA' OR  stringu1 = 'TVAAAB';
+RESET random_page_cost;
 DROP INDEX hash_tuplesort_idx;
 RESET maintenance_work_mem;

---

From: Alexander Korotkov <[email-masked]>
Date: Fri, 29 Nov 2024 02:04:05 +0200

On Thu, Nov 28, 2024 at 9:33 PM Alena Rybakina
<[email-masked]> wrote:
> Em qui., 28 de nov. de 2024 às 16:03, Alena Rybakina <[email-masked]> escreveu:
>>
>> > SELECT COUNT(*) FROM tbl WHERE u = '00000000000000000000000000000000' OR
>> I found out what the problem is index scan method was not generated. We
> EXPLAIN SELECT COUNT(*) FROM tbl WHERE u = '00000000000000000000000000000000' OR u = '11111111111111111111111111111111';
>                                                             QUERY PLAN
>          Recheck Cond: ((u = '00000000-0000-0000-0000-000000000000'::uuid) OR (u = '11111111-1111-1111-1111-111111111111'::uuid))
>                ->  Bitmap Index Scan on idx  (cost=0.00..1.07 rows=9 width=0)
>                      Index Cond: (u = '00000000-0000-0000-0000-000000000000'::uuid)
>                ->  Bitmap Index Scan on idx  (cost=0.00..1.07 rows=9 width=0)
>                      Index Cond: (u = '11111111-1111-1111-1111-111111111111'::uuid)
> (8 rows)

I slightly revised the fix and added similar check to
group_similar_or_args().  Could you, please, review that before
commit?

------
Regards,
Alexander Korotkov
Supabase

---

From: Andrei Lepikhov <[email-masked]>
Date: Fri, 29 Nov 2024 12:10:42 +0700

> group_similar_or_args().  Could you, please, review that before
LGTM,
As I see, we didn't pay attention to this option from the beginning. 
Thanks for fixing it!

-- 
regards, Andrei Lepikhov

---

From: Alena Rybakina <[email-masked]>
Date: Fri, 29 Nov 2024 08:51:30 +0300

> group_similar_or_args().  Could you, please, review that before
I agree with changes. Thank you!

-- 
Regards,
Alena Rybakina
Postgres Professional

---

From: Alexander Korotkov <[email-masked]>
Date: Fri, 29 Nov 2024 09:54:02 +0200

> I agree with changes. Thank you!

Andrei, Alena, thank you for the feedback. Pushed!

------
Regards,
Alexander Korotkov
Supabase

---

From: Alexander Korotkov <[email-masked]>
Date: Sun, 12 Jan 2025 20:39:03 +0200

> Andrei, Alena, thank you for the feedback. Pushed!

I think we should give some more attention to the patch enabling OR to
SAOP transformation for joins (first time posted in [1]).  I think we
tried to only work with Const and Param, because we were previously
working during parse stage. So, at that stage if we have the clause
like "a.x = 1 OR a.x = b.x OR b.x = 2", then we don't know if we
should transform it into "a.x = ANY(1, b.x) OR b.x = 2" or into "a.x
=1 OR b.x = ANY(a.x, 2)". But if we do the transformation during the
index matching, we would actually be able to try the both and select
the best.

The revised patch is attached.  Most notably it revises
group_similar_or_args() to have the same notion of const-ness as
others.  In that function we split potential index key and constant
early to save time on enumerating all possible index keys.  But it
appears to be possible to split by relids bitmapsets: index key should
use our relid, while const shouldn't.  Other that that, comments,
commit message and naming are revised.

Links.
1. https://www.postgresql.org/message-id/CAPpHfdu9QJ%3DGbua3CUUH2KKG_8urakJTen4JD47PGh9wWP%3DQxQ%40mail.gmail.com

------
Regards,
Alexander Korotkov
Supabase

---

From: Alena Rybakina <[email-masked]>
Date: Sun, 12 Jan 2025 23:38:35 +0300

Hi!

> 1. https://www.postgresql.org/message-id/CAPpHfdu9QJ%3DGbua3CUUH2KKG_8urakJTen4JD47PGh9wWP%3DQxQ%40mail.gmail.com
I like your idea. I looked at your patch and haven't noticed any bugs 
yet, but my review is not finished.

I think we're missing tests here - I only noticed one difference in the 
regression test related to your specific improvement.

I thought it would be possible to look at cases where q1 and q2 are not 
equal to an integer constant table,
but have a more complex structure. For example, set the conditions "q1 
as select (1=1)::integer" and "q2 as select (1=0)::integer".

-- 
Regards,
Alena Rybakina
Postgres Professional

---

From: Yura Sokolov <[email-masked]>
Date: Mon, 13 Jan 2025 03:47:56 +0300

Вс, 12 янв. 2025 г. в 21:39, Alexander Korotkov <[email-masked]>:

the best.

But why not “a.x = ANY(1, b.x) OR b.x = ANY(a.x, 2)” ? Looks strange, but correct ))

Links.

------

Regards,

Alexander Korotkov

Supabase

---

From: Alexander Korotkov <[email-masked]>
Date: Mon, 13 Jan 2025 03:06:42 +0200

> But why not “a.x = ANY(1, b.x) OR b.x = ANY(a.x, 2)” ? Looks strange, but correct ))

That could probably work for a parse stage, but as you can check that
approach has a lot of other problems.  As we do during index matching,
that doesn't matter.  I just wanted to state that nothing in the
current approach prevent us from working the same way for joins.

------
Regards,
Alexander Korotkov
Supabase

---

From: Andrei Lepikhov <[email-masked]>
Date: Mon, 13 Jan 2025 10:39:23 +0700

> commit message and naming are revised.
Hmm, I would say we should carefully review this code.
Curiously, this patch has activated the dormant problem of duplicated 
clauses in joinorclauses. Look:

EXPLAIN (COSTS OFF)
SELECT * FROM bitmap_split_or t1, bitmap_split_or t2
WHERE t1.a=t2.b OR t1.a=1;

  Nested Loop
    ->  Seq Scan on bitmap_split_or t2
    ->  Bitmap Heap Scan on bitmap_split_or t1
          Recheck Cond: (((a = t2.b) OR (a = 1)) AND
                         ((a = t2.b) OR (a = 1)))
          ->  Bitmap Index Scan on t_a_b_idx
                Index Cond: ((a = ANY (ARRAY[t2.b, 1])) AND
                             (a = ANY (ARRAY[t2.b, 1])))

It can be resolved with a single-line change (see attached). But I need 
some time to ponder over the changing behaviour when a clause may match 
an index and be in joinorclauses.

-- 
regards, Andrei Lepikhov

diff --git a/src/backend/optimizer/path/indxpath.c b/src/backend/optimizer/path/indxpath.c
index c03547a997..2a86298d9d 100644
--- a/src/backend/optimizer/path/indxpath.c
+++ b/src/backend/optimizer/path/indxpath.c
@@ -2440,7 +2440,7 @@ match_join_clauses_to_index(PlannerInfo *root,
 
 		/* Potentially usable, so see if it matches the index or is an OR */
 		if (restriction_is_or_clause(rinfo))
-			*joinorclauses = lappend(*joinorclauses, rinfo);
+			*joinorclauses = list_append_unique_ptr(*joinorclauses, rinfo);
 
 		match_clause_to_index(root, rinfo, index, clauseset);
 	}
diff --git a/src/test/regress/expected/create_index.out b/src/test/regress/expected/create_index.out
index 8011c141bf..47bdee1d41 100644
--- a/src/test/regress/expected/create_index.out
+++ b/src/test/regress/expected/create_index.out
@@ -3255,6 +3255,16 @@ CREATE INDEX t_b_c_idx ON bitmap_split_or (b, c);
 CREATE STATISTICS t_a_b_stat (mcv) ON a, b FROM bitmap_split_or;
 CREATE STATISTICS t_b_c_stat (mcv) ON b, c FROM bitmap_split_or;
 ANALYZE bitmap_split_or;
+EXPLAIN (COSTS OFF)
+SELECT * FROM bitmap_split_or t1, bitmap_split_or t2 WHERE t1.a=t2.b OR t1.a=1;
+                       QUERY PLAN                       
+--------------------------------------------------------
+ Nested Loop
+   ->  Seq Scan on bitmap_split_or t2
+   ->  Index Scan using t_a_b_idx on bitmap_split_or t1
+         Index Cond: (a = ANY (ARRAY[t2.b, 1]))
+(4 rows)
+
 EXPLAIN (COSTS OFF)
 SELECT * FROM bitmap_split_or WHERE a = 1 AND (b = 1 OR b = 2) AND c = 2;
                             QUERY PLAN                            
diff --git a/src/test/regress/sql/create_index.sql b/src/test/regress/sql/create_index.sql
index 068c66b95a..bc12d2f098 100644
--- a/src/test/regress/sql/create_index.sql
+++ b/src/test/regress/sql/create_index.sql
@@ -1367,6 +1367,8 @@ CREATE STATISTICS t_a_b_stat (mcv) ON a, b FROM bitmap_split_or;
 CREATE STATISTICS t_b_c_stat (mcv) ON b, c FROM bitmap_split_or;
 ANALYZE bitmap_split_or;
 EXPLAIN (COSTS OFF)
+SELECT * FROM bitmap_split_or t1, bitmap_split_or t2 WHERE t1.a=t2.b OR t1.a=1;
+EXPLAIN (COSTS OFF)
 SELECT * FROM bitmap_split_or WHERE a = 1 AND (b = 1 OR b = 2) AND c = 2;
 DROP TABLE bitmap_split_or;

---

From: Andrei Lepikhov <[email-masked]>
Date: Wed, 15 Jan 2025 15:24:27 +0700

> an index and be in joinorclauses.
In addition, let me raise a couple of issues:
1. As Robert has said before, it may interfere with some short-circuit 
optimisations like below:

EXPLAIN (COSTS OFF)
SELECT * FROM bitmap_split_or t1
WHERE t1.a=2 AND (t1.b=2 OR t1.b = (
   SELECT sum(c1.reltuples) FROM pg_class c1, pg_class c2
   WHERE c1.relpages=c2.relpages AND c1.relpages = t1.a));

Here, a user may avoid evaluating the subplan at all if t1.b=2 all the 
time when t1.a=2. OR->ANY may accidentally shift this behaviour.

2. The query:

EXPLAIN (ANALYZE, COSTS OFF)
SELECT * FROM bitmap_split_or t1
WHERE t1.a=2 OR t1.a = (
   SELECT sum(c1.reltuples) FROM pg_class c1, pg_class c2
   WHERE c1.relpages=c2.relpages AND c1.relpages = t1.a)::integer;

causes SEGFAULT during index keys evaluation. I haven't dived into it 
yet, but it seems quite a typical misstep and is not difficult to fix.

-- 
regards, Andrei Lepikhov

---

From: Alexander Korotkov <[email-masked]>
Date: Sat, 25 Jan 2025 07:04:57 +0200

> yet, but it seems quite a typical misstep and is not difficult to fix.

Segfault appears to be caused by a typo.  Patch used parent rinfo
instead of child rinfo.  Fixed in the attached patch.

It appears that your first query also changed a plan after fixing
this.  Could you, please, provide another example of a regression for
short-circuit optimization, which is related to this patch?

Also, I've integrated your fix from [1].

Links.
1. https://www.postgresql.org/message-id/41ba3d47-2a48-476c-88d4-6ebd889a7af2%40gmail.com

------
Regards,
Alexander Korotkov
Supabase

---

From: Andrei Lepikhov <[email-masked]>
Date: Mon, 27 Jan 2025 15:52:16 +0700

> instead of child rinfo.  Fixed in the attached patch.
Great!
> short-circuit optimization, which is related to this patch?
Yes, it may be caused by the current lazy InitPlan evaluation strategy, 
which would only happen if it was really needed.

Examples:
---------

EXPLAIN (ANALYZE, COSTS OFF, BUFFERS OFF, TIMING OFF)
SELECT * FROM bitmap_split_or t1
WHERE t1.a=2 AND (t1.b=2 OR t1.b = (
    SELECT avg(x) FROM generate_series(1,1e6) AS x)::integer);

without optimisation:

  Index Scan using t_a_b_idx on bitmap_split_or t1 (actual rows=1 loops=1)
    Index Cond: (a = 2)
    Filter: ((b = 2) OR (b = ((InitPlan 1).col1)::integer))
    InitPlan 1
      ->  Aggregate (never executed)
            ->  Function Scan on generate_series x (never executed)
  Planning Time: 0.564 ms
  Execution Time: 0.182 ms

But having it as a part of an array, we forcedly evaluate it for (not 
100% sure) more precise selectivity estimation:

  Index Scan using t_a_b_idx on bitmap_split_or t1
    (actual rows=1 loops=1)
    Index Cond: ((a = 2) AND
                 (b = ANY (ARRAY[2, ((InitPlan 1).col1)::integer])))
    InitPlan 1
      ->  Aggregate (actual rows=1 loops=1)
            ->  Function Scan on generate_series x
                (actual rows=1000000 loops=1)
  Planning Time: 0.927 ms
  Execution Time: 489.933 ms

This also means that if, before the patch, we executed a query 
successfully, after applying the patch, we sometimes may get the error:
'ERROR: more than one row returned by a subquery used as an expression' 
because of early InitPlan evaluation. See the example below:

EXPLAIN (ANALYZE, COSTS OFF)
SELECT * FROM bitmap_split_or t1
WHERE t1.a=2 AND (t1.b=2 OR t1.b = (
    SELECT random() FROM generate_series(1,1e6) AS x)::integer);

  Index Scan using t_a_b_idx on bitmap_split_or t1
    Index Cond: ((a = 2) AND (b = ANY (ARRAY[2, ((InitPlan 
1).col1)::integer])))
    InitPlan 1
      ->  Function Scan on generate_series x

I think optimisation should have never happened and this is another 
issue, isn't it?

-- 
regards, Andrei Lepikhov

---

From: Alexander Korotkov <[email-masked]>
Date: Mon, 27 Jan 2025 11:50:09 +0200

Hi, Andrei!

> I think optimisation should have never happened and this is another

Thank you for your examples.  The reason why these example works only with
the patch is that you apply the cast outside of subquery.  This is
because d4378c0005 requires OR argument to be either Cost or Param, but not
a cast over the param.  Consider this example on master.

# EXPLAIN (ANALYZE, COSTS OFF, BUFFERS OFF, TIMING OFF)
SELECT * FROM bitmap_split_or t1
WHERE t1.a=2 AND (t1.b=2 OR t1.b = (
    SELECT avg(x)::integer FROM generate_series(1,1e6) AS x));
                                   QUERY PLAN
--------------------------------------------------------------------------------
 Index Scan using t_a_b_idx on bitmap_split_or t1 (actual rows=1 loops=1)
   Index Cond: ((a = 2) AND (b = ANY (ARRAY[2, (InitPlan 1).col1])))
   InitPlan 1
     ->  Aggregate (actual rows=1 loops=1)
           ->  Function Scan on generate_series x (actual rows=1000000
loops=1)
 Planning Time: 0.731 ms
 Execution Time: 577.953 ms
(7 rows)

I expressed my point on this in [1].  We generally greedy about index quals
and there is no logic which prevent us from using a clause and index qual
because of its cost.  And there are many cases when this causes regressions
before d4378c0005.  One of examples from [1].

# explain analyze select * from t where i = 0 and j = (select slowfunc());
                                            QUERY PLAN
---------------------------------------------------------------------------------------------------
 Seq Scan on t  (cost=25000.01..25195.01 rows=1 width=8) (actual
time=0.806..0.807 rows=0 loops=1)
   Filter: ((i = 0) AND (j = (InitPlan 1).col1))
   Rows Removed by Filter: 10000
   InitPlan 1
     ->  Result  (cost=0.00..25000.01 rows=1 width=4) (never executed)
 Planning Time: 0.165 ms
 Execution Time: 0.843 ms
(7 rows)

Links.
1.
https://www.postgresql.org/message-id/CAPpHfdt8kowRDUkmOnO7_WJJQ1uk%2BO379JiZCk_9_Pt5AQ4%2B0w%40mail.gmail.com

------
Regards,
Alexander Korotkov
Supabase

---

From: Andrei Lepikhov <[email-masked]>
Date: Tue, 28 Jan 2025 11:36:47 +0700

On 1/27/25 16:50, Alexander Korotkov wrote:
> I expressed my point on this in [1].  We generally greedy about index 
> quals and there is no logic which prevent us from using a clause and 
> index qual because of its cost.  And there are many cases when this 
> causes regressions before d4378c0005.  One of examples from [1].
Ok,
Generally, I don't concern myself with the evaluation of individual 
subplans. As you mentioned, it should be a rare occurrence when this 
becomes important. My main concern is the shift in frequency of 
evaluations during execution for various reasons.
For example:

qsort(matches, n, sizeof(OrArgIndexMatch), or_arg_index_match_cmp);

To fit an index, the order of elements in the target array of the 
`ScalarArrayOpExpr` may change compared to the initial list of OR 
expressions. If there are indexes that cover the same set of columns but 
in reverse order, this could potentially alter the position of a 
Subplan. However, I believe this is a rare case; it is supported by the 
initial OR path and should be acceptable.

So, I do not have any further objections at this time.

-- 
regards, Andrei Lepikhov

---

From: Andrei Lepikhov <[email-masked]>
Date: Tue, 28 Jan 2025 15:42:38 +0700

> initial OR path and should be acceptable.
I beg your pardon - I forgot that we've restricted the feature's scope 
and can't combine OR clauses into ScalarArrayOpExpr if the args list 
contains references to different columns.
So, my note can't be applied here.

-- 
regards, Andrei Lepikhov

---

From: Pavel Borisov <[email-masked]>
Date: Thu, 30 Jan 2025 17:22:55 +0400

> So, my note can't be applied here.

I've looked at the patch v46-0001
Looks good to me.

There is a test that demonstrates the behavior change. Maybe some more
cases like are also worth adding to a test.

+SELECT * FROM bitmap_split_or t1, bitmap_split_or t2 WHERE t1.a=t2.c
OR (t1.a=t2.b OR t1.a=1);
+                       QUERY PLAN
+--------------------------------------------------------
+ Nested Loop
+   ->  Seq Scan on bitmap_split_or t2
+   ->  Index Scan using t_a_b_idx on bitmap_split_or t1
+         Index Cond: (a = ANY (ARRAY[t2.c, t2.b, 1]))
+(4 rows)
+
+EXPLAIN (COSTS OFF)
+SELECT * FROM bitmap_split_or t1, bitmap_split_or t2 WHERE t1.c=t2.b OR t1.a=1;
+                  QUERY PLAN
+----------------------------------------------
+ Nested Loop
+   Join Filter: ((t1.c = t2.b) OR (t1.a = 1))
+   ->  Seq Scan on bitmap_split_or t1
+   ->  Materialize
+         ->  Seq Scan on bitmap_split_or t2
+(5 rows)
+
+EXPLAIN (COSTS OFF)

Comment
> *    Also, add any potentially usable join OR clauses to *joinorclauses
may reflect the change in v46-0001 lappend -> list_append_unique_ptr
that differs in the processing of equal clauses in the list.

Semantics mentioned in the commit message:
> 2. Make match_join_clauses_to_index() pass OR-clauses to
>        match_clause_to_index().
could also be added as comments in the section just before
match_join_clauses_to_index()

Since d4378c0005e6 comment for match_clause_to_indexcol() I think
needs change. This could be as a separate commit, not regarding
current patch v46-0001.
> * NOTE:  returns NULL if clause is an OR or AND clause; it is the
> * responsibility of higher-level routines to co

I think the patch can be pushed with possible additions to regression
test and comments.

Regards,
Pavel Borisov
Supabase

---

From: Alena Rybakina <[email-masked]>
Date: Fri, 31 Jan 2025 17:31:44 +0300

Hi!

On 25.01.2025 08:04, Alexander Korotkov wrote:
> On Wed, Jan 15, 2025 at 10:24 AM Andrei Lepikhov<[email-masked]>  wrote:
> 1.https://www.postgresql.org/message-id/41ba3d47-2a48-476c-88d4-6ebd889a7af2%40gmail.com

I started reviewing at the patch and saw some output "ERROR" in the 
output of the test and is it okay here?

SELECT * FROM tenk1 t1
WHERE t1.thousand= 42OR t1.thousand= (SELECT t2.tenthousFROM tenk1 t2 
WHERE t2.thousand= t1.tenthous);
ERROR: more than one row returned by a subquery used as an expression

-- 
Regards,
Alena Rybakina
Postgres Professional

---

From: Alexander Korotkov <[email-masked]>
Date: Sun, 2 Feb 2025 19:57:55 +0200

> OR (t1.a=t2.b OR t1.a=1);

Added more tests to join.sql

> that differs in the processing of equal clauses in the list.

Comments in this function are revised.  I also added detailed
explanation of this change to the commit message.

> match_join_clauses_to_index()

Right, this is addressed too.

> > * responsibility of higher-level routines to co

Good catch.  This is added as a separate patch.

> I think the patch can be pushed with possible additions to regression

OK, thank you!

------
Regards,
Alexander Korotkov
Supabase

---

From: Alexander Korotkov <[email-masked]>
Date: Sun, 2 Feb 2025 19:58:27 +0200

OK, thank you!

------
Regards,
Alexander Korotkov
Supabase

---

From: Alexander Korotkov <[email-masked]>
Date: Sun, 2 Feb 2025 20:00:06 +0200

On Fri, Jan 31, 2025 at 4:31 PM Alena Rybakina
<[email-masked]> wrote:
> I started reviewing at the patch and saw some output "ERROR" in the output of the test and is it okay here?
>
> SELECT * FROM tenk1 t1
> WHERE t1.thousand = 42 OR t1.thousand = (SELECT t2.tenthous FROM tenk1 t2 WHERE t2.thousand = t1.tenthous);

The output is correct for this query.  But the query is very
unfortunate for the regression test.  I've revised query in the v47
revision [1].

Links.
1. https://www.postgresql.org/message-id/CAPpHfdsBZmNt9qUoJBqsQFiVDX1%3DyCKpuVAt1YnR7JCpP%3Dk8%2BA%40mail.gmail.com

------
Regards,
Alexander Korotkov
Supabase

---

From: Andrei Lepikhov <[email-masked]>
Date: Mon, 3 Feb 2025 13:24:04 +0700

> Added more tests to join.sql
I have made final pass through the changes. All looks good.
Only one thing looks strange for me - multiple '42's in the output of 
the test. May be reduce output by an aggregate in the target list of the 
query?

-- 
regards, Andrei Lepikhov

---

From: Alena Rybakina <[email-masked]>
Date: Mon, 3 Feb 2025 13:22:20 +0300

Thank you for updated version! I agree for your version of the code.

On 02.02.2025 21:00, Alexander Korotkov wrote:
> 1.https://www.postgresql.org/message-id/CAPpHfdsBZmNt9qUoJBqsQFiVDX1%3DyCKpuVAt1YnR7JCpP%3Dk8%2BA%40mail.gmail.com
While analyzing the modified query plan from the regression test, I 
noticed that despite using a full seqscan for table t2 in the original 
plan,
its results are cached by Materialize node, and this can significantly 
speed up the execution of the NestedLoop algorithm.

For example, after running the query several times, I got results that 
show that the query execution time was twice as bad.

Original plan:

EXPLAIN ANALYZE SELECT * FROM bitmap_split_or t1, bitmap_split_or t2 
WHERE t1.a=t2.b OR t1.a=1; QUERY PLAN 
-------------------------------------------------------------------------------------------------------------------------------- 
Nested Loop (cost=0.00..70067.00 rows=2502499 width=24) (actual 
time=0.015..1123.247 rows=2003000 loops=1) Join Filter: ((t1.a = t2.b) 
OR (t1.a = 1)) Rows Removed by Join Filter: 1997000 Buffers: shared 
hit=22 -> Seq Scan on bitmap_split_or t1 (cost=0.00..31.00 rows=2000 
width=12) (actual time=0.006..0.372 rows=2000 loops=1) Buffers: shared 
hit=11 -> Materialize (cost=0.00..41.00 rows=2000 width=12) (actual 
time=0.000..0.111 rows=2000 loops=2000) Storage: Memory Maximum Storage: 
110kB Buffers: shared hit=11 -> Seq Scan on bitmap_split_or t2 
(cost=0.00..31.00 rows=2000 width=12) (actual time=0.003..0.188 
rows=2000 loops=1) Buffers: shared hit=11 Planning Time: 0.118 ms 
Execution Time: 1204.874 ms (13 rows)

Query plan after the patch:

EXPLAIN ANALYZE SELECT * FROM bitmap_split_or t1, bitmap_split_or t2 
WHERE t1.a=t2.b OR t1.a=1; QUERY PLAN 
----------------------------------------------------------------------------------------------------------------------------------------------- 
Nested Loop (cost=0.28..56369.00 rows=2502499 width=24) (actual 
time=0.121..2126.606 rows=2003000 loops=1) Buffers: shared hit=16009 
read=2 -> Seq Scan on bitmap_split_or t2 (cost=0.00..31.00 rows=2000 
width=12) (actual time=0.017..0.652 rows=2000 loops=1) Buffers: shared 
hit=11 -> Index Scan using t_a_b_idx on bitmap_split_or t1 
(cost=0.28..18.15 rows=1002 width=12) (actual time=0.044..0.627 
rows=1002 loops=2000) Index Cond: (a = ANY (ARRAY[t2.b, 1])) Buffers: 
shared hit=15998 read=2 Planning Time: 0.282 ms Execution Time: 2344.367 
ms (9 rows)

I'm afraid that we may lose this with this optimization. Maybe this can 
be taken into account somehow, what do you think?

-- 
Regards,
Alena Rybakina
Postgres Professional

---

From: Alexander Korotkov <[email-masked]>
Date: Mon, 3 Feb 2025 13:32:10 +0200

On Mon, Feb 3, 2025 at 12:22 PM Alena Rybakina
<[email-masked]> wrote:
> While analyzing the modified query plan from the regression test, I noticed that despite using a full seqscan for table t2 in the original plan,
> its results are cached by Materialize node, and this can significantly speed up the execution of the NestedLoop algorithm.
>
> For example, after running the query several times, I got results that show that the query execution time was twice as bad.
>
> Original plan:
>
> EXPLAIN ANALYZE SELECT * FROM bitmap_split_or t1, bitmap_split_or t2 WHERE t1.a=t2.b OR t1.a=1; QUERY PLAN -------------------------------------------------------------------------------------------------------------------------------- Nested Loop (cost=0.00..70067.00 rows=2502499 width=24) (actual time=0.015..1123.247 rows=2003000 loops=1) Join Filter: ((t1.a = t2.b) OR (t1.a = 1)) Rows Removed by Join Filter: 1997000 Buffers: shared hit=22 -> Seq Scan on bitmap_split_or t1 (cost=0.00..31.00 rows=2000 width=12) (actual time=0.006..0.372 rows=2000 loops=1) Buffers: shared hit=11 -> Materialize (cost=0.00..41.00 rows=2000 width=12) (actual time=0.000..0.111 rows=2000 loops=2000) Storage: Memory Maximum Storage: 110kB Buffers: shared hit=11 -> Seq Scan on bitmap_split_or t2 (cost=0.00..31.00 rows=2000 width=12) (actual time=0.003..0.188 rows=2000 loops=1) Buffers: shared hit=11 Planning Time: 0.118 ms Execution Time: 1204.874 ms (13 rows)
>
> EXPLAIN ANALYZE SELECT * FROM bitmap_split_or t1, bitmap_split_or t2 WHERE t1.a=t2.b OR t1.a=1; QUERY PLAN ----------------------------------------------------------------------------------------------------------------------------------------------- Nested Loop (cost=0.28..56369.00 rows=2502499 width=24) (actual time=0.121..2126.606 rows=2003000 loops=1) Buffers: shared hit=16009 read=2 -> Seq Scan on bitmap_split_or t2 (cost=0.00..31.00 rows=2000 width=12) (actual time=0.017..0.652 rows=2000 loops=1) Buffers: shared hit=11 -> Index Scan using t_a_b_idx on bitmap_split_or t1 (cost=0.28..18.15 rows=1002 width=12) (actual time=0.044..0.627 rows=1002 loops=2000) Index Cond: (a = ANY (ARRAY[t2.b, 1])) Buffers: shared hit=15998 read=2 Planning Time: 0.282 ms Execution Time: 2344.367 ms (9 rows)
>
> I'm afraid that we may lose this with this optimization. Maybe this can be taken into account somehow, what do you think?

The important aspect is that the second plan have lower cost than the
first one.  So, that's the question to the cost model.  The patch just
lets optimizer consider more comprehensive plurality of paths.  You
can let optimizer select the first plan by tuning *_cost params.  For
example, setting cpu_index_tuple_cost = 0.02 makes first plan win for
me.

Other than that the test query is quite unfortunate as t1.a=1 is very
frequent. I've adjusted the query so that nested loop with index scan
wins both in cost and execution time.

I've also adjusted another test query as proposed by Andrei.

I'm going to push this patch is there is no more notes.

Links.
1. https://www.postgresql.org/message-id/fc1017ca-877b-4f86-b491-154cf123eedd%40gmail.com

------
Regards,
Alexander Korotkov
Supabase

---

From: Alena Rybakina <[email-masked]>
Date: Mon, 3 Feb 2025 14:54:47 +0300

On 03.02.2025 14:32, Alexander Korotkov wrote:
> 1.https://www.postgresql.org/message-id/fc1017ca-877b-4f86-b491-154cf123eedd%40gmail.com
>

Okay.I agree with your codeand have no more notes

-- 
Regards,
Alena Rybakina
Postgres Professional

---

From: Pavel Borisov <[email-masked]>
Date: Mon, 3 Feb 2025 16:16:03 +0400

On Mon, 3 Feb 2025 at 15:54, Alena Rybakina <[email-masked]> wrote:
> Okay.I agree with your code and have no more notes

Hi, Alexander!
I've looked at patchset v48 and it looks good to me.

Regards,
Pavel Borisov
Supabase

---

From: Andrei Lepikhov <[email-masked]>
Date: Mon, 24 Mar 2025 11:10:00 +0100

Hi,

Playing with the feature, I found a slightly irritating permutation - 
even if this code doesn't group any clauses, it may permute positions of 
the quals. See:

DROP TABLE IF EXISTS main_tbl;
CREATE TABLE main_tbl(id bigint, hundred int, thousand int);
CREATE INDEX mt_hundred_ix ON main_tbl(hundred);
CREATE INDEX mt_thousand_ix ON main_tbl(thousand);
VACUUM (ANALYZE) main_tbl;

SET enable_seqscan = off;
EXPLAIN (COSTS OFF)
SELECT m.id, m.hundred, m.thousand
FROM main_tbl m WHERE (m.hundred < 2 OR m.thousand < 3);

  Bitmap Heap Scan on public.main_tbl m
    Output: id, hundred, thousand
    Recheck Cond: ((m.thousand < 3) OR (m.hundred < 2))
    ->  BitmapOr
          ->  Bitmap Index Scan on mt_thousand_ix
                Index Cond: (m.thousand < 3)
          ->  Bitmap Index Scan on mt_hundred_ix
                Index Cond: (m.hundred < 2)

Conditions on the columns "thousand" and "hundred" changed their places 
according to the initial positions defined in the user's SQL.
It isn't okay. I see that users often use the trick of "OR order" to 
avoid unnecessary calculations - most frequently, Subplan evaluations. 
So, it makes sense to fix.
In the attachment, I have included a quick fix for this issue. Although 
many tests returned to their initial (pre-18) state, I added some tests 
specifically related to this issue to make it clearer.

-- 
regards, Andrei Lepikhov

diff --git a/src/backend/optimizer/path/indxpath.c b/src/backend/optimizer/path/indxpath.c
index a43ca16d68..7d8ef0c90f 100644
--- a/src/backend/optimizer/path/indxpath.c
+++ b/src/backend/optimizer/path/indxpath.c
@@ -1254,6 +1254,7 @@ group_similar_or_args(PlannerInfo *root, RelOptInfo *rel, RestrictInfo *rinfo)
 	ListCell   *lc;
 	ListCell   *lc2;
 	List	   *orargs;
+	bool		grouping_happened = false;
 	List	   *result = NIL;
 	Index		relid = rel->relid;
 
@@ -1465,13 +1466,18 @@ group_similar_or_args(PlannerInfo *root, RelOptInfo *rel, RestrictInfo *rinfo)
 												   rinfo->incompatible_relids,
 												   rinfo->outer_relids);
 				result = lappend(result, subrinfo);
+				grouping_happened = true;
 			}
 
 			group_start = i;
 		}
 	}
 	pfree(matches);
-	return result;
+
+	if (grouping_happened)
+		return result;
+	else
+		return orargs;
 }
 
 /*
diff --git a/src/test/regress/expected/create_index.out b/src/test/regress/expected/create_index.out
index bd5f002cf2..c6f84bda64 100644
--- a/src/test/regress/expected/create_index.out
+++ b/src/test/regress/expected/create_index.out
@@ -3248,6 +3248,37 @@ SELECT  b.relname,
 (2 rows)
 
 DROP TABLE concur_temp_tab_1, concur_temp_tab_2, reindex_temp_before;
+-- No OR-clause groupings should happen - no clause permutations in
+-- the filtering conditions we should see in the EXPLAIN.
+EXPLAIN (COSTS OFF)
+SELECT * FROM tenk1 WHERE unique1 < 1 OR hundred < 2;
+                    QUERY PLAN                    
+--------------------------------------------------
+ Bitmap Heap Scan on tenk1
+   Recheck Cond: ((unique1 < 1) OR (hundred < 2))
+   ->  BitmapOr
+         ->  Bitmap Index Scan on tenk1_unique1
+               Index Cond: (unique1 < 1)
+         ->  Bitmap Index Scan on tenk1_hundred
+               Index Cond: (hundred < 2)
+(7 rows)
+
+-- OR clauses on the 'unique' column is grouped. So, clause permutation happened
+-- We see it in the 'Recheck Cond' and order of BitmapOr subpaths: index scan on
+-- the 'hundred' column occupies the first position.
+EXPLAIN (COSTS OFF)
+SELECT * FROM tenk1 WHERE unique1 < 1 OR unique1 < 3 OR hundred < 2;
+                             QUERY PLAN                              
+---------------------------------------------------------------------
+ Bitmap Heap Scan on tenk1
+   Recheck Cond: ((hundred < 2) OR ((unique1 < 1) OR (unique1 < 3)))
+   ->  BitmapOr
+         ->  Bitmap Index Scan on tenk1_hundred
+               Index Cond: (hundred < 2)
+         ->  Bitmap Index Scan on tenk1_unique1
+               Index Cond: (unique1 < ANY ('{1,3}'::integer[]))
+(7 rows)
+
 -- Check bitmap scan can consider similar OR arguments separately without
 -- grouping them into SAOP.
 CREATE TABLE bitmap_split_or (a int NOT NULL, b int NOT NULL, c int NOT NULL);
diff --git a/src/test/regress/expected/join.out b/src/test/regress/expected/join.out
index a57bb18c24..a950153d76 100644
--- a/src/test/regress/expected/join.out
+++ b/src/test/regress/expected/join.out
@@ -4333,20 +4333,20 @@ select * from tenk1 a join tenk1 b on
  Nested Loop
    Join Filter: (((a.unique1 = 1) AND (b.unique1 = 2)) OR ((a.unique2 = 3) AND (b.hundred = 4)))
    ->  Bitmap Heap Scan on tenk1 b
-         Recheck Cond: ((hundred = 4) OR (unique1 = 2))
+         Recheck Cond: ((unique1 = 2) OR (hundred = 4))
          ->  BitmapOr
-               ->  Bitmap Index Scan on tenk1_hundred
-                     Index Cond: (hundred = 4)
                ->  Bitmap Index Scan on tenk1_unique1
                      Index Cond: (unique1 = 2)
+               ->  Bitmap Index Scan on tenk1_hundred
+                     Index Cond: (hundred = 4)
    ->  Materialize
          ->  Bitmap Heap Scan on tenk1 a
-               Recheck Cond: ((unique2 = 3) OR (unique1 = 1))
+               Recheck Cond: ((unique1 = 1) OR (unique2 = 3))
                ->  BitmapOr
-                     ->  Bitmap Index Scan on tenk1_unique2
-                           Index Cond: (unique2 = 3)
                      ->  Bitmap Index Scan on tenk1_unique1
                            Index Cond: (unique1 = 1)
+                     ->  Bitmap Index Scan on tenk1_unique2
+                           Index Cond: (unique2 = 3)
 (17 rows)
 
 explain (costs off)
@@ -4360,12 +4360,12 @@ select * from tenk1 a join tenk1 b on
          Filter: ((unique1 = 2) OR (ten = 4))
    ->  Materialize
          ->  Bitmap Heap Scan on tenk1 a
-               Recheck Cond: ((unique2 = 3) OR (unique1 = 1))
+               Recheck Cond: ((unique1 = 1) OR (unique2 = 3))
                ->  BitmapOr
-                     ->  Bitmap Index Scan on tenk1_unique2
-                           Index Cond: (unique2 = 3)
                      ->  Bitmap Index Scan on tenk1_unique1
                            Index Cond: (unique1 = 1)
+                     ->  Bitmap Index Scan on tenk1_unique2
+                           Index Cond: (unique2 = 3)
 (12 rows)
 
 explain (costs off)
@@ -4377,12 +4377,12 @@ select * from tenk1 a join tenk1 b on
  Nested Loop
    Join Filter: (((a.unique1 = 1) AND (b.unique1 = 2)) OR (((a.unique2 = 3) OR (a.unique2 = 7)) AND (b.hundred = 4)))
    ->  Bitmap Heap Scan on tenk1 b
-         Recheck Cond: ((hundred = 4) OR (unique1 = 2))
+         Recheck Cond: ((unique1 = 2) OR (hundred = 4))
          ->  BitmapOr
-               ->  Bitmap Index Scan on tenk1_hundred
-                     Index Cond: (hundred = 4)
                ->  Bitmap Index Scan on tenk1_unique1
                      Index Cond: (unique1 = 2)
+               ->  Bitmap Index Scan on tenk1_hundred
+                     Index Cond: (hundred = 4)
    ->  Materialize
          ->  Bitmap Heap Scan on tenk1 a
                Recheck Cond: (((unique2 = 3) OR (unique2 = 7)) OR (unique1 = 1))
@@ -4403,12 +4403,12 @@ select * from tenk1 a join tenk1 b on
  Nested Loop
    Join Filter: (((a.unique1 = 1) AND (b.unique1 = 2)) OR (((a.unique2 = 3) OR (a.unique2 = 7)) AND (b.hundred = 4)))
    ->  Bitmap Heap Scan on tenk1 b
-         Recheck Cond: ((hundred = 4) OR (unique1 = 2))
+         Recheck Cond: ((unique1 = 2) OR (hundred = 4))
          ->  BitmapOr
-               ->  Bitmap Index Scan on tenk1_hundred
-                     Index Cond: (hundred = 4)
                ->  Bitmap Index Scan on tenk1_unique1
                      Index Cond: (unique1 = 2)
+               ->  Bitmap Index Scan on tenk1_hundred
+                     Index Cond: (hundred = 4)
    ->  Materialize
          ->  Bitmap Heap Scan on tenk1 a
                Recheck Cond: (((unique2 = 3) OR (unique2 = 7)) OR (unique1 = 1))
diff --git a/src/test/regress/expected/partition_join.out b/src/test/regress/expected/partition_join.out
index 938cedd79a..6101c8c7cf 100644
--- a/src/test/regress/expected/partition_join.out
+++ b/src/test/regress/expected/partition_join.out
@@ -2568,24 +2568,24 @@ where not exists (select 1 from prtx2
          ->  Seq Scan on prtx1_1
                Filter: ((a < 20) AND (c = 91))
          ->  Bitmap Heap Scan on prtx2_1
-               Recheck Cond: ((c = 99) OR (b = (prtx1_1.b + 1)))
+               Recheck Cond: ((b = (prtx1_1.b + 1)) OR (c = 99))
                Filter: (a = prtx1_1.a)
                ->  BitmapOr
-                     ->  Bitmap Index Scan on prtx2_1_c_idx
-                           Index Cond: (c = 99)
                      ->  Bitmap Index Scan on prtx2_1_b_idx
                            Index Cond: (b = (prtx1_1.b + 1))
+                     ->  Bitmap Index Scan on prtx2_1_c_idx
+                           Index Cond: (c = 99)
    ->  Nested Loop Anti Join
          ->  Seq Scan on prtx1_2
                Filter: ((a < 20) AND (c = 91))
          ->  Bitmap Heap Scan on prtx2_2
-               Recheck Cond: ((c = 99) OR (b = (prtx1_2.b + 1)))
+               Recheck Cond: ((b = (prtx1_2.b + 1)) OR (c = 99))
                Filter: (a = prtx1_2.a)
                ->  BitmapOr
-                     ->  Bitmap Index Scan on prtx2_2_c_idx
-                           Index Cond: (c = 99)
                      ->  Bitmap Index Scan on prtx2_2_b_idx
                            Index Cond: (b = (prtx1_2.b + 1))
+                     ->  Bitmap Index Scan on prtx2_2_c_idx
+                           Index Cond: (c = 99)
 (23 rows)
 
 select * from prtx1
diff --git a/src/test/regress/sql/create_index.sql b/src/test/regress/sql/create_index.sql
index be570da08a..51e030294e 100644
--- a/src/test/regress/sql/create_index.sql
+++ b/src/test/regress/sql/create_index.sql
@@ -1355,6 +1355,17 @@ SELECT  b.relname,
   ORDER BY 1;
 DROP TABLE concur_temp_tab_1, concur_temp_tab_2, reindex_temp_before;
 
+-- No OR-clause groupings should happen - no clause permutations in
+-- the filtering conditions we should see in the EXPLAIN.
+EXPLAIN (COSTS OFF)
+SELECT * FROM tenk1 WHERE unique1 < 1 OR hundred < 2;
+
+-- OR clauses on the 'unique' column is grouped. So, clause permutation happened
+-- We see it in the 'Recheck Cond' and order of BitmapOr subpaths: index scan on
+-- the 'hundred' column occupies the first position.
+EXPLAIN (COSTS OFF)
+SELECT * FROM tenk1 WHERE unique1 < 1 OR unique1 < 3 OR hundred < 2;
+
 -- Check bitmap scan can consider similar OR arguments separately without
 -- grouping them into SAOP.
 CREATE TABLE bitmap_split_or (a int NOT NULL, b int NOT NULL, c int NOT NULL);

---

From: Pavel Borisov <[email-masked]>
Date: Mon, 24 Mar 2025 14:46:07 +0400

Hi, Andrei!

> specifically related to this issue to make it clearer.

I looked at your patch and have no objections to it.

However it's clearly stated in PostgreSQL manual that nothing about
the OR order is warranted [1]. So changing OR order was (and is) ok
and any users query tricks about OR order may work and may not work.

[1] https://www.postgresql.org/docs/17/sql-expressions.html#SYNTAX-EXPRESS-EVAL

Regards,
Pavel Borisov
Supabase

---

From: Alena Rybakina <[email-masked]>
Date: Mon, 24 Mar 2025 15:46:03 +0300

On 24.03.2025 13:46, Pavel Borisov wrote:
> Hi, Andrei!
>
> On Mon, 24 Mar 2025 at 14:10, Andrei Lepikhov<[email-masked]>  wrote:
>> Hi,
>>
> [1]https://www.postgresql.org/docs/17/sql-expressions.html#SYNTAX-EXPRESS-EVAL
>
I agree with Andrey's changes and think we should fix this, because 
otherwise it might be inconvenient.
For example, without this changes we will have to have different test 
output files for the same query for different versions of Postres in 
extensions if the whole change is only related to the order of column 
output for a transformation that was not applied.

-- 
Regards,
Alena Rybakina
Postgres Professional

---

From: Alexander Korotkov <[email-masked]>
Date: Fri, 28 Mar 2025 01:18:19 +0200

Hi!

On Mon, Mar 24, 2025 at 2:46 PM Alena Rybakina
<[email-masked]> wrote:
> I agree with Andrey's changes and think we should fix this, because otherwise it might be inconvenient.
> For example, without this changes we will have to have different test output files for the same query for different versions of Postres in extensions if the whole change is only related to the order of column output for a transformation that was not applied.

I agree with problem spotted by Andrei: it should be preferred to
preserve original order of clauses as much as possible.  The approach
implemented in Andrei's patch seems fragile for me.  Original order is
preserved if we didn't find any group.  But once we find a single
group original order might be destroyed completely.

The attached patch changes the reordering algorithm of
group_similar_or_args() in the following way.  We reorder each group
of similar clauses so that the first item of the group stays in place,
but all the other items are moved after it.  So, if there are no
similar clauses, the order of clauses stays the same.  When there are
some groups, only required reordering happens while the rest of the
clauses remain in their places.

------
Regards,
Alexander Korotkov
Supabase

---

From: Pavel Borisov <[email-masked]>
Date: Fri, 28 Mar 2025 14:47:56 +0400

Hi, Alexander!
d4378c0005e61b1bb7

> clauses remain in their places.

With your patch, I've re-checked that there are no changes in the
order of evaluation in plans compared to d4378c0005e61b1bb7

It might be good to also include Andrei's test from his last patch. i.e:

+-- No OR-clause groupings should happen - no clause permutations in
+-- the filtering conditions we should see in the EXPLAIN.
+EXPLAIN (COSTS OFF)
+SELECT * FROM tenk1 WHERE unique1 < 1 OR hundred < 2;
+
+-- OR clauses on the 'unique' column is grouped. So, clause
permutation happened
+-- We see it in the 'Recheck Cond' and order of BitmapOr subpaths:
index scan on
+-- the 'hundred' column occupies the first position.
+EXPLAIN (COSTS OFF)
+SELECT * FROM tenk1 WHERE unique1 < 1 OR unique1 < 3 OR hundred < 2;

I propose small changes for comments:

s/To have this property,/To do so,/g
s/in place, but all the/in place, and all the/g
s/some groups, only/some groups,/g
s/Resort/Re-sort/п

The patch overall looks good to me.

Regards,
Pavel Borisov
Supabase

---

From: Andrei Lepikhov <[email-masked]>
Date: Fri, 28 Mar 2025 12:32:51 +0100

> clauses remain in their places.
The patch looks good to me from a technical perspective. But it seems 
like an overkill, isn't it?
You introduce additional CPU-consuming operations in the planning OR 
operations.
My point is: 1) as Pavel has mentioned, Postgres doesn't guarantee the 
evaluation/output order of the clauses at all. 2) we need that to keep 
regression tests stable (don't forget extensions' and forks' developers 
too). But it should be done once if we have no fluidity in OR clauses 
order in general.
The trade-off with tricky query writers and regression tests may be 
preserving the order until OR->ANY has happened. If it has happened, 
just ensure the order is determined somehow. Except that, any other 
spending on CPU cycles seems too expensive.

-- 
regards, Andrei Lepikhov

---

From: Alexander Korotkov <[email-masked]>
Date: Fri, 28 Mar 2025 13:59:30 +0200

> You introduce additional CPU-consuming operations in the planning OR

I don't think this is going to be CPU-consuming.  I don't think this
is going to be measurable.  This patch introduces one additional pass
over array of OrArgIndexMatch'es, and qsort of them.  I think I've
seen places where we spend quadratic time over the number of
OR-clauses.  Even calls of match_index_to_operand() for every clause
and every index look way more expensive.

> spending on CPU cycles seems too expensive.

I think my patch gives better determinism too.  For instance, output
order doesn't depend on order of indexes in rel->indexlist.

------
Regards,
Alexander Korotkov
Supabase

---

From: Andrei Lepikhov <[email-masked]>
Date: Fri, 28 Mar 2025 13:15:35 +0100

> and every index look way more expensive.
Ok, I have no more objections.

> order doesn't depend on order of indexes in rel->indexlist.
Nice!

-- 
regards, Andrei Lepikhov

---

From: Alena Rybakina <[email-masked]>
Date: Fri, 28 Mar 2025 15:23:24 +0300

> clauses remain in their places.

I agree with your code in general, but to be honest, double qsort 
confused me a little.

I understood why it is needed - we need to sort the elements so that 
they stand next to each other if they can be assigned to the same group, 
and then sort the groups themselves according to the set identifier.

I may be missing something, but in the worst case we can get the 
complexity of qsort O(n^2), right? And I saw the letter where you 
mentioned this, but it is possible to use mergesort algorithm instead of 
qsort, which in the worst case gives n * O(n) complexity?

-- 
Regards,
Alena Rybakina
Postgres Professional

---

From: Alena Rybakina <[email-masked]>
Date: Fri, 28 Mar 2025 15:31:31 +0300

On 28.03.2025 15:23, Alena Rybakina wrote:
> they stand next to each other if they can be assigned to the same 
> group, and then sort the groups themselves according to the set 
> identifier.
>
> mentioned this, but it is possible to use mergesort algorithm  instead 
> of qsort, which in the worst case gives n * O(n) complexity?
>
No, sorry, I was wrong here and it is impossible to rewrite it this way. 
I apologize, I agree with your code.

-- 
Regards,
Alena Rybakina
Postgres Professional