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

From: Teodor Sigaev <[email-masked]>
Date: Sat, 26 Dec 2015 21:04:58 +0300

I'd like to present OR-clause support for indexes. Although OR-clauses could be 
supported by bitmapOR index scan it isn't very effective and such scan lost any 
order existing in index. We (with Alexander Korotkov) presented results on 
Vienna's conference this year. In short, it provides performance improvement:

EXPLAIN ANALYZE
SELECT count(*) FROM tst WHERE id = 5 OR id = 500 OR id = 5000;
me=0.080..0.267 rows=173 loops=1)
          Recheck Cond: ((id = 5) OR (id = 500) OR (id = 5000))
          Heap Blocks: exact=172
          ->  Bitmap Index Scan on idx_gin  (cost=0.00..57.50 rows=15000 
width=0) (actual time=0.059..0.059 rows=147 loops=1)
                Index Cond: ((id = 5) OR (id = 500) OR (id = 5000))
  Planning time: 0.077 ms
  Execution time: 0.308 ms   <-------
                                                             QUERY PLAN 

-----------------------------------------------------------------------------------------------------------------------------------
  Aggregate  (cost=51180.53..51180.54 rows=1 width=0) (actual 
time=796.766..796.766 rows=1 loops=1)
    ->  Index Only Scan using idx_btree on tst  (cost=0.42..51180.40 rows=55 
width=0) (actual time=0.444..796.736 rows=173 loops=1)
          Filter: ((id = 5) OR (id = 500) OR (id = 5000))
          Rows Removed by Filter: 999829
          Heap Fetches: 1000002
  Planning time: 0.087 ms
  Execution time: 796.798 ms  <------
                                                 QUERY PLAN 

-------------------------------------------------------------------------------------------------------------
  Aggregate  (cost=21925.63..21925.64 rows=1 width=0) (actual 
time=160.412..160.412 rows=1 loops=1)
    ->  Seq Scan on tst  (cost=0.00..21925.03 rows=237 width=0) (actual 
time=0.535..160.362 rows=175 loops=1)
          Filter: ((id = 5) OR (id = 500) OR (id = 5000))
          Rows Removed by Filter: 999827
  Planning time: 0.459 ms
  Execution time: 160.451 ms

It also could work together with KNN feature of GiST and in this case 
performance improvement could be up to several orders of magnitude, in 
artificial example it was 37000 times faster.

Not all  indexes can support oR-clause, patch adds support to GIN, GiST and BRIN 
indexes. pg_am table is extended for adding amcanorclause column which indicates 
possibility of executing of OR-clause by index.

  indexqual and indexqualorig doesn't contain implicitly-ANDed list of index 
qual expressions, now that lists could contain OR RestrictionInfo. Actually, the 
patch just tries to convert BitmapOr node to IndexScan or IndexOnlyScan. Thats 
significantly simplifies logic to find possible clause's list for index.
Index always gets a array of ScanKey but for indexes which support OR-clauses
array  of ScanKey is actually exection tree in reversed polish notation form. 
Transformation is done in ExecInitIndexScan().

The problems on the way which I see for now:
1 Calculating cost. Right now it's just a simple transformation of costs 
computed for BitmapOr path. I'd like to hope that's possible and so index's 
estimation function could be non-touched. So, they could believe that all 
clauses are implicitly-ANDed
2 I'd like to add such support to btree but it seems that it should be a 
separated patch. Btree search algorithm doesn't use any kind of stack of pages 
and algorithm to walk over btree doesn't clear for me for now.
3 I could miss some places which still assumes  implicitly-ANDed list of clauses 
although regression tests passes fine.

Hope, hackers will not have an strong objections to do that. But obviously patch
requires further work and I'd like to see comments, suggestions and 
recommendations. Thank you.

-- 
Teodor Sigaev                                   E-mail: [email-masked]
                                                    WWW: http://www.sigaev.ru/

-- 
Sent via pgsql-hackers mailing list ([email-masked])
To make changes to your subscription:
http://www.postgresql.org/mailpref/pgsql-hackers

---

From: Feng Tian <[email-masked]>
Date: Sat, 26 Dec 2015 10:40:02 -0800

Hi, Teodor,

This is great.   I got a question, is it possible make btree index to
support OR as well?  Is btree supports more invasive, in the sense that we
need to do enhance ScanKey to supports an array of values?

Thanks,
Feng

On Sat, Dec 26, 2015 at 10:04 AM, Teodor Sigaev <[email-masked]> wrote:

> I'd like to present OR-clause support for indexes. Although OR-clauses
> could be supported by bitmapOR index scan it isn't very effective and such
> scan lost any order existing in index. We (with Alexander Korotkov)
> presented results on Vienna's conference this year. In short, it provides
> performance improvement:
>
> EXPLAIN ANALYZE
>    ->  Index Only Scan using idx_btree on tst  (cost=0.42..51180.40
> rows=55 width=0) (actual time=0.444..796.736 rows=173 loops=1)
> Not all  indexes can support oR-clause, patch adds support to GIN, GiST
> and BRIN indexes. pg_am table is extended for adding amcanorclause column
> which indicates possibility of executing of OR-clause by index.
>
>  indexqual and indexqualorig doesn't contain implicitly-ANDed list of
> index qual expressions, now that lists could contain OR RestrictionInfo.
> Actually, the patch just tries to convert BitmapOr node to IndexScan or
> IndexOnlyScan. Thats significantly simplifies logic to find possible
> clause's list for index.
> array  of ScanKey is actually exection tree in reversed polish notation
> form. Transformation is done in ExecInitIndexScan().
>
> separated patch. Btree search algorithm doesn't use any kind of stack of
> pages and algorithm to walk over btree doesn't clear for me for now.
> 3 I could miss some places which still assumes  implicitly-ANDed list of
> clauses although regression tests passes fine.
>

---

From: Teodor Sigaev <[email-masked]>
Date: Sat, 26 Dec 2015 22:25:19 +0300

> This is great.   I got a question, is it possible make btree index to support OR
> as well?  Is btree supports more invasive, in the sense that we need to do
> enhance ScanKey to supports an array of values?
Btree now works by follow: find the max/min tuple which satisfies condtions and 
then executes forward/backward scan over leaf pages. For complicated clauses 
it's not obvious how to find min/max tuple. Scanning whole index isn't an option 
from preformance point of view.

---

From: David Rowley <[email-masked]>
Date: Mon, 11 Jan 2016 16:16:23 +1300

>  Execution time: 0.308 ms   <-------

Hi,

I'd like to see comments too! but more so in the code. :) I've had a look
over this, and it seems like a great area in which we could improve on, and
your reported performance improvements are certainly very interesting too.
However I'm finding the code rather hard to follow, which might be a
combination of my lack of familiarity with the index code, but more likely
it's the lack of comments to explain what's going on. Let's just take 1
function as an example:

Here there's not a single comment, so I'm just going to try to work out
what's going on based on the code.

+static void
+compileScanKeys(IndexScanDesc scan)
+{
+ GISTScanOpaque so = (GISTScanOpaque) scan->opaque;
+ int *stack,
+ stackPos = -1,
+ i;
+
+ if (scan->numberOfKeys <= 1 || so->useExec == false)
+ return;
+
+ Assert(scan->numberOfKeys >=3);

Why can numberOfKeys never be 2? I looked at what calls this and I can't
really work it out. I'm really also not sure what useExec means as there's
no comment in that struct member, and what if numberOfKeys == 1 and useExec
== false, won't this Assert() fail? If that's not a possible situation then
why not?

+
+ if (so->leftArgs != NULL)
+ return;
+
+ so->leftArgs = MemoryContextAlloc(so->giststate->scanCxt,
+  sizeof(*so->leftArgs) * scan->numberOfKeys);
+ so->rightArgs = MemoryContextAlloc(so->giststate->scanCxt,
+   sizeof(*so->rightArgs) * scan->numberOfKeys);
+
+ stack = palloc(sizeof(*stack) * scan->numberOfKeys);
+
+ for(i=0; i<scan->numberOfKeys; i++)
+ {
+ ScanKey     key = scan->keyData + i;

Is there a reason not to use keyData[i]; ?

+
+ if (stackPos >= 0 && (key->sk_flags & (SK_OR | SK_AND)))
+ {
+ Assert(stackPos >= 1 && stackPos < scan->numberOfKeys);

stackPos >= 1? This seems unnecessary and confusing as the if test surely
makes that impossible.
+
+ so->leftArgs[i] = stack[stackPos - 1];

Something is broken here as stackPos can be 0 (going by the if() not the
Assert()), therefore that's stack[-1].

+ so->rightArgs[i] = stack[stackPos];
+ stackPos--;
+ }
+ else
+ {
+ stackPos++;
+ }
+

stackPos is initialised to -1, so this appears to always skip the first
element of the keyData array. If that's really the intention, then wouldn't
it be better to just make the initial condition of the for() look i = 1 ?

+ stack[stackPos] = i;
+ }
+
+ Assert(stackPos == 0);
+ pfree(stack);
+}

I'd like to review more, but it feels like a job that's more difficult than
it needs to be due to lack of comments.

Would it be possible to update the patch to try and explain things a little
better?

Many thanks

David

-- 
 David Rowley                   http://www.2ndQuadrant.com/
 PostgreSQL Development, 24x7 Support, Training & Services

---

From: Alvaro Herrera <[email-masked]>
Date: Thu, 28 Jan 2016 12:16:04 +0100

I think this is very exciting stuff, but since you didn't submit an
updated patch after David's review, I'm closing it for now as
returned-with-feedback.  Please submit a new version once you have it.

-- 
Álvaro Herrera                http://www.2ndQuadrant.com/
PostgreSQL Development, 24x7 Support, Remote DBA, Training & Services

---

From: Teodor Sigaev <[email-masked]>
Date: Mon, 29 Feb 2016 21:04:38 +0300

Thank you for review!

> I'd like to see comments too! but more so in the code. :) I've had a look over
> this, and it seems like a great area in which we could improve on, and your
> reported performance improvements are certainly very interesting too. However
> I'm finding the code rather hard to follow, which might be a combination of my
> lack of familiarity with the index code, but more likely it's the lack of
I've added comments, fixed a found bugs.

> comments to explain what's going on. Let's just take 1 function as an example:
>
> Here there's not a single comment, so I'm just going to try to work out what's
> going on based on the code.
>
> +static void
> +GISTScanOpaqueso = (GISTScanOpaque) scan->opaque;
> +int*stack,
> +stackPos = -1,
> +i;
> +
> +if (scan->numberOfKeys <= 1 || so->useExec == false)
> +return;
> +
> +Assert(scan->numberOfKeys >=3);
>
> Why can numberOfKeys never be 2? I looked at what calls this and I can't really
Because here they are actually an expression, expression could contain 1 or tree 
or more nodes but could not two (operation AND/OR plus two arguments)

> work it out. I'm really also not sure what useExec means as there's no comment
fixed. If useExec == false then SkanKeys are implicitly ANDed and stored in just 
array.

> in that struct member, and what if numberOfKeys == 1 and useExec == false, won't
> this Assert() fail? If that's not a possible situation then why not?
fixed

> +ScanKey     key = scan->keyData + i;
That's the same ScanKey	key = &scan->keyData[i];
I prefer first form as more clear but I could be wrong - but there are other 
places in code where pointer arithmetic is used.

> +if (stackPos >= 0 && (key->sk_flags & (SK_OR | SK_AND)))
> +{
> +Assert(stackPos >= 1 && stackPos < scan->numberOfKeys);
> stackPos >= 1? This seems unnecessary and confusing as the if test surely makes
> that impossible.

> +
> +so->leftArgs[i] = stack[stackPos - 1];
fixed

> stackPos is initialised to -1, so this appears to always skip the first element
> of the keyData array. If that's really the intention, then wouldn't it be better
> to just make the initial condition of the for() look i = 1 ?
done

> I'd like to review more, but it feels like a job that's more difficult than it
> needs to be due to lack of comments.
>
> Would it be possible to update the patch to try and explain things a little better?
Hope, I made cleaner..

---

From: Tomas Vondra <[email-masked]>
Date: Thu, 10 Mar 2016 14:04:37 +0100

Hi Teodor,

I've looked into v2 of the patch you sent a few days ago. Firstly, I
definitely agree that being able to use OR conditions with an index is
definitely a cool idea.

I do however agree with David that the patch would definitely benefit
from comments documenting various bits that are less obvious to mere
mortals like me, with limited knowledge of the index internals.

I also wonder whether the patch should add explanation of OR-clauses
handling into the READMEs in src/backend/access/*

The patch would probably benefit from transforming it into a patch
series - one patch for the infrastructure shared by all the indexes,
then one patch per index type. That should make it easier to review, and
I seriously doubt we'd want to commit this in one huge chunk anyway.

Now, some review comments from eyeballing the patch. Some of those are
nitpicking, but well ...

1) fields in BrinOpaque are not following the naming convention (all the
existing fields start with bo_)

2) there's plenty of places violating the usual code style (e.g. for
single-command if branches) - not a big deal for WIP patch, but needs to
get fixed eventually

3) I wonder whether we really need both SK_OR and SK_AND, considering
they are mutually exclusive. Why not to assume SK_AND by default, and
only use SK_OR? If we really need them, perhaps an assert making sure
they are not set at the same time would be appropriate.

4) scanGetItem is a prime example of the "badly needs comments" issue,
particularly because the previous version of the function actually had
quite a lot of them while the new function has none.

5) scanGetItem() may end up using uninitialized 'cmp' - it only gets
initialized when (!leftFinished && !rightFinished), but then gets used
when either part of the condition evaluates to true. Probably should be

    if (!leftFinished || !rightFinished)
        cmp = ...

6) the code in nodeIndexscan.c should not include call to abort()

    {
        abort();
        elog(ERROR, "unsupported indexqual type: %d",
            (int) nodeTag(clause));
    }

7) I find it rather ugly that the paths are built by converting BitmapOr
paths. Firstly, it means indexes without amgetbitmap can't benefit from
this change. Maybe that's reasonable limitation, though?

But more importantly, this design already has a bunch of unintended
consequences. For example, the current code completely ignores
enable_indexscan setting, because it merely copies the costs from the
bitmap path.

    SET enable_indexscan = off;
    EXPLAIN SELECT * FROM t WHERE (c && ARRAY[1] OR c && ARRAY[2]);

                             QUERY PLAN
-------------------------------------------------------------------
 Index Scan using t_c_idx on t  (cost=0.00..4.29 rows=0 width=33)
   Index Cond: ((c && '{1}'::integer[]) OR (c && '{2}'::integer[]))
(2 rows)

That's pretty dubious, I guess. So this code probably needs to be made
aware of enable_indexscan - right now it entirely ignores startup_cost
in convert_bitmap_path_to_index_clause(). But of course if there are
multiple IndexPaths, the  enable_indexscan=off will be included multiple
times.

9) This already breaks estimation for some reason. Consider this
example, using a table with int[] column, with gist index built using
intarray:

EXPLAIN SELECT * FROM t WHERE (c && ARRAY[1,2,3,4,5,6,7]);

                           QUERY PLAN
--------------------------------------------------------------------
 Index Scan using t_c_idx on t  (cost=0.28..52.48 rows=12 width=33)
   Index Cond: (c && '{1,2,3,4,5,6,7}'::integer[])
(2 rows)

EXPLAIN SELECT * FROM t WHERE (c && ARRAY[8,9,10,11,12,13,14]);

                           QUERY PLAN
--------------------------------------------------------------------
 Index Scan using t_c_idx on t  (cost=0.28..44.45 rows=10 width=33)
   Index Cond: (c && '{8,9,10,11,12,13,14}'::integer[])
(2 rows)

EXPLAIN SELECT * FROM t WHERE (c && ARRAY[1,2,3,4,5,6,7])
                           OR (c && ARRAY[8,9,10,11,12,13,14]);

                           QUERY PLAN
--------------------------------------------------------------------
 Index Scan using t_c_idx on t  (cost=0.00..4.37 rows=0 width=33)
   Index Cond: ((c && '{1,2,3,4,5,6,7}'::integer[])
             OR (c && '{8,9,10,11,12,13,14}'::integer[]))
(2 rows)

So the OR-clause is estimated to match 0 rows, less than each of the
clauses independently. Needless to say that without the patch this works
just fine.

10) Also, this already breaks some regression tests, apparently because
it changes how 'width' is computed.

So I think this way of building the index path from a BitmapOr path is
pretty much a dead-end.

regards

-- 
Tomas Vondra                  http://www.2ndQuadrant.com
PostgreSQL Development, 24x7 Support, Remote DBA, Training & Services

---

From: Teodor Sigaev <[email-masked]>
Date: Thu, 17 Mar 2016 20:19:55 +0300

> handling into the READMEs in src/backend/access/*

Oops, will add shortly.
> I seriously doubt we'd want to commit this in one huge chunk anyway.
Ok, will do it.

fixed

> single-command if branches) - not a big deal for WIP patch, but needs to
hope, fixed

> they are not set at the same time would be appropriate.
In short: possible ambiguity and increasing stack machine complexity.
Let we have follow expression in reversed polish notation (letters represent a 
condtion, | - OR, & - AND logical operation, ANDs are omitted):
a b c |

Is it ((a & b)| c) or (a & (b | c)) ?

Also, using both SK_ makes code more readable.

> quite a lot of them while the new function has none.
Will add soon

fixed

>          elog(ERROR, "unsupported indexqual type: %d",
fixed, just forgot to remove

> this change. Maybe that's reasonable limitation, though?
I based on following thoughts:
1 code which tries to find OR-index path will be very similar to existing
   generate_or_bitmap code. Obviously, it should not be duplicated.
2 all existsing indexes have amgetbitmap method, only a few don't. amgetbitmap
   interface is simpler. Anyway, I can add an option for generate_or_bitmap
   to use any index, but, in current state it will just repeat all work.

> enable_indexscan setting, because it merely copies the costs from the
I'd like to add separate enable_indexorscan

> 9) This already breaks estimation for some reason. Consider this
...
fixed

> it changes how 'width' is computed.
fixed too

> So I think this way of building the index path from a BitmapOr path is
I don't think so because separate code path to support OR-clause in index will 
significanlty duplicate BitmapOr generator.

Will send next version as soon as possible. Thank you for your attention!

---

From: Teodor Sigaev <[email-masked]>
Date: Fri, 18 Mar 2016 19:38:05 +0300

> handling into the READMEs in src/backend/access/*
Not yet, but will

> I seriously doubt we'd want to commit this in one huge chunk anyway.
I splitted to two:
1 0001-idx_or_core - only planner and executor changes
2 0002-idx_or_indexes - BRIN/GIN/GiST changes with tests

I don't think that splitting of second patch adds readability but increase 
management diffculties, but if your insist I will split.

> quite a lot of them while the new function has none.
added

---

From: Andreas Karlsson <[email-masked]>
Date: Sat, 19 Mar 2016 00:46:26 +0100

I gave this patch a quick spin and noticed a strange query plan.

CREATE TABLE test (a int, b int, c int);
CREATE INDEX ON test USING gin (a, b, c);
INSERT INTO test SELECT i % 7, i % 9, i % 11 FROM generate_series(1, 
1000000) i;
EXPLAIN ANALYZE SELECT * FROM test WHERE (a = 3 OR b = 5) AND c = 2;

                                                             QUERY PLAN 

----------------------------------------------------------------------------------------------------------------------------------
  Bitmap Heap Scan on test  (cost=829.45..4892.10 rows=21819 width=12) 
(actual time=66.494..76.234 rows=21645 loops=1)
    Recheck Cond: ((((a = 3) AND (c = 2)) OR ((b = 5) AND (c = 2))) AND 
(c = 2))
    Heap Blocks: exact=5406
    ->  Bitmap Index Scan on test_a_b_c_idx  (cost=0.00..824.00 
rows=2100 width=0) (actual time=65.272..65.272 rows=21645 loops=1)
          Index Cond: ((((a = 3) AND (c = 2)) OR ((b = 5) AND (c = 2))) 
AND (c = 2))
  Planning time: 0.200 ms
  Execution time: 77.206 ms
(7 rows)

Shouldn't the index condition just be "((a = 3) AND (c = 2)) OR ((b = 5) 
AND (c = 2))"?

Also when applying and reading the patch I noticed some minor 
issues/nitpick.

- I get whitespace warnings from git apply when I apply the patches.
- You have any insconstent style for casts: I think "(Node*)clause" 
should be "(Node *) clause".
- Same with pointers. "List* quals" should be "List *quals"
- I am personally not a fan of seeing the "isorderby == false && 
index->rd_amroutine->amcanorclause" clause twice. Feels like a risk for 
diverging code paths. But it could be that there is no clean alternative.

Andreas

---

From: Tomas Vondra <[email-masked]>
Date: Sun, 20 Mar 2016 01:44:37 +0100

Hi Teodor,

Sadly the v4 does not work for me - I do get assertion failures. For 
example with the example Andreas Karlsson posted in this thread:

CREATE EXTENSION btree_gin;

It seems working, but only until I run ANALYZE on the table. Once I do 
that, I start getting crashes at this line

     *qualcols = list_concat(*qualcols,
                             list_copy(idx_path->indexqualcols));

in convert_bitmap_path_to_index_clause. Apparently one of the lists is 
T_List while the other one is T_IntList, so list_concat() errors out.

My guess is that the T_BitmapOrPath branch should do

     oredqualcols = list_concat(oredqualcols, li_qualcols);
     ...
     *qualcols = list_concat(qualcols, oredqualcols);

instead of

     oredqualcols = lappend(oredqualcols, li_qualcols);
     ...
     *qualcols = lappend(*qualcols, oredqualcols);

but once I fixed that I got some other assert failures further down, 
that I haven't tried to fix.

So the patch seems to be broken, and I suspect this might be related to 
the broken index condition reported by Andreas (although I don't see 
that - I either see correct condition or assertion failures).

On 03/17/2016 06:19 PM, Teodor Sigaev wrote:
...
>   to use any index, but, in current state it will just repeat all work.

I agree that the code should not be duplicated, but is this really a 
good solution. Perhaps a refactoring that'd allow sharing most of the 
code would be more appropriate.

> I'd like to add separate enable_indexorscan

That may be useful, but why shouldn't enable_indexscan=off also disable 
indexorscan? I would find it rather surprising if after setting 
enable_indexscan=off I'd still get index scans for OR-clauses.

>> multiple IndexPaths, the  enable_indexscan=off will be included multiple

... and it does not address this at all.

I really doubt a costing derived from the bitmap index scan nodes will 
make much sense - you essentially need to revert unknown parts of the 
costing to only include building the bitmap once, etc.

regards

---

From: David Steele <[email-masked]>
Date: Fri, 25 Mar 2016 11:13:26 -0400

Hi Teador,

On 3/19/16 8:44 PM, Tomas Vondra wrote:

> Sadly the v4 does not work for me - I do get assertion failures.

Time is growing short and there seem to be some serious concerns with 
this patch.  Can you provide a new patch soon?  If not, I think it might 
be be time to mark this "returned with feedback".

Thanks,
-- 
-David
[email-masked]

---

From: David Steele <[email-masked]>
Date: Tue, 29 Mar 2016 10:01:21 -0400

> be be time to mark this "returned with feedback".

I have marked this patch "returned with feedback".  Please feel free to 
resubmit for 9.7!

Thanks,
-- 
-David
[email-masked]

---

From: Andrey Lepikhov <[email-masked]>
Date: Wed, 28 Dec 2022 09:19:27 +0500

On 12/26/15 23:04, Teodor Sigaev wrote:
> could be supported by bitmapOR index scan it isn't very effective and 
> such scan lost any order existing in index. We (with Alexander Korotkov) 
> presented results on Vienna's conference this year. In short, it 
> provides performance improvement:
> 
> EXPLAIN ANALYZE
> computed for BitmapOr path. I'd like to hope that's possible and so 
> index's estimation function could be non-touched. So, they could believe 
> that all clauses are implicitly-ANDed
I support such a cunning approach. But this specific case, you 
demonstrated above, could be optimized independently at an earlier 
stage. If to convert:

(F(A) = ConstStableExpr_1) OR (F(A) = ConstStableExpr_2)
to
F(A) IN (ConstStableExpr_1, ConstStableExpr_2)

it can be seen significant execution speedup. For example, using the 
demo.sql to estimate maximum positive effect we see about 40% of 
execution and 100% of planning speedup.

To avoid unnecessary overhead, induced by the optimization, such 
transformation may be made at the stage of planning (we have cardinality 
estimations and have pruned partitions) but before creation of a 
relation scan paths. So, we can avoid planning overhead and non-optimal 
BitmapOr in the case of many OR's possibly aggravated by many indexes on 
the relation.
For example, such operation can be executed in create_index_paths() 
before passing rel->indexlist.

-- 
Regards
Andrey Lepikhov
Postgres Professional

---

From: vignesh C <[email-masked]>
Date: Sat, 27 Jan 2024 08:28:53 +0530

On Tue, 5 Dec 2023 at 16:25, Andrei Lepikhov <[email-masked]> wrote:
>
> Here is fresh version with the pg_dump.pl regex fixed. Now it must pass
> buildfarm.
>
> Under development:
> 1. Explanation of the general idea in comments (Robert's note)
> 2. Issue with hiding some optimizations (Alexander's note and example
> with overlapping clauses on two partial indexes)

CFBot shows that the patch does not apply anymore as in [1]:
=== Applying patches on top of PostgreSQL commit ID
64444ce071f6b04d3fc836f436fa08108a6d11e2 ===
=== applying patch ./v14-1-0001-Transform-OR-clause-to-ANY-expressions.patch
....
patching file src/test/regress/expected/sysviews.out
Hunk #1 succeeded at 124 (offset 1 line).
Hunk #2 FAILED at 134.
1 out of 2 hunks FAILED -- saving rejects to file
src/test/regress/expected/sysviews.out.rej

Please post an updated version for the same.

[1] - http://cfbot.cputube.org/patch_46_4450.log

Regards,
Vignesh

---

From: jian he <[email-masked]>
Date: Tue, 30 Jan 2024 22:15:20 +0800

> Here is fresh version with the pg_dump.pl regex fixed. Now it must pass

+JumbleState *
+JumbleExpr(Expr *expr, uint64 *queryId)
+{
+ JumbleState *jstate = NULL;
+
+ Assert(queryId != NULL);
+
+ jstate = (JumbleState *) palloc(sizeof(JumbleState));
+
+ /* Set up workspace for query jumbling */
+ jstate->jumble = (unsigned char *) palloc(JUMBLE_SIZE);
+ jstate->jumble_len = 0;
+ jstate->clocations_buf_size = 32;
+ jstate->clocations = (LocationLen *)
+ palloc(jstate->clocations_buf_size * sizeof(LocationLen));
+ jstate->clocations_count = 0;
+ jstate->highest_extern_param_id = 0;
+
+ /* Compute query ID */
+ _jumbleNode(jstate, (Node *) expr);
+ *queryId = DatumGetUInt64(hash_any_extended(jstate->jumble,
+ jstate->jumble_len,
+ 0));
+
+ if (*queryId == UINT64CONST(0))
+ *queryId = UINT64CONST(1);
+
+ return jstate;
+}

+/*
+ * Hash function that's compatible with guc_name_compare
+ */
+static uint32
+orclause_hash(const void *data, Size keysize)
+{
+ OrClauseGroupKey   *key = (OrClauseGroupKey *) data;
+ uint64 hash;
+
+ (void) JumbleExpr(key->expr, &hash);
+ hash += ((uint64) key->opno + (uint64) key->exprtype) % UINT64_MAX;
+ return hash;
+}

correct me if i am wrong:
in orclause_hash, you just want to return a uint32, then why does the
JumbleExpr function return struct JumbleState.
here JumbleExpr, we just simply hash part of a Query struct,
so JumbleExpr's queryId would be confused with JumbleQuery function's queryId.

not sure the purpose of the following:
+ if (*queryId == UINT64CONST(0))
+ *queryId = UINT64CONST(1);

even if  *queryId is 0
`hash += ((uint64) key->opno + (uint64) key->exprtype) % UINT64_MAX;`
will make the hash return non-zero?

+ MemSet(&info, 0, sizeof(info));
i am not sure this is necessary.

Some comments on OrClauseGroupEntry would be great.

seems there is no doc.

create or replace function retint(int) returns int as
$func$
begin return $1 + round(10 * random()); end
$func$ LANGUAGE plpgsql;

set enable_or_transformation to on;
EXPLAIN (COSTS OFF)
SELECT count(*) FROM tenk1
WHERE thousand = 42 AND (tenthous * retint(1) = NULL OR tenthous *
retint(1) = 3) OR thousand = 41;

returns:
                                                    QUERY PLAN
-------------------------------------------------------------------------------------------------------------------
 Aggregate
   ->  Seq Scan on tenk1
         Filter: (((thousand = 42) AND ((tenthous * retint(1)) = ANY
('{NULL,3}'::integer[]))) OR (thousand = 41))
(3 rows)

Based on the query plan, retint executed once, but here it should be
executed twice?
maybe we need to use contain_volatile_functions to check through the
other part of the operator expression.

+ if (IsA(leftop, Const))
+ {
+ opno = get_commutator(opno);
+
+ if (!OidIsValid(opno))
+ {
+ /* Commuter doesn't exist, we can't reverse the order */
+ or_list = lappend(or_list, orqual);
+ continue;
+ }
+
+ nconst_expr = get_rightop(orqual);
+ const_expr = get_leftop(orqual);
+ }
+ else if (IsA(rightop, Const))
+ {
+ const_expr = get_rightop(orqual);
+ nconst_expr = get_leftop(orqual);
+ }
+ else
+ {
+ or_list = lappend(or_list, orqual);
+ continue;
+ }
do we need to skip this transformation for the const type is anyarray?

---

From: jian he <[email-masked]>
Date: Wed, 31 Jan 2024 10:55:56 +0800

+/*

looks strange. `hash` is uint64, but here you return uint32.

based on my understanding of
https://www.postgresql.org/docs/current/xoper-optimization.html#XOPER-COMMUTATOR
I think you need move commutator check right after the `if
(get_op_rettype(opno) != BOOLOID)` branch

+ opno = ((OpExpr *) orqual)->opno;
+ if (get_op_rettype(opno) != BOOLOID)
+ {
+ /* Only operator returning boolean suits OR -> ANY transformation */
+ or_list = lappend(or_list, orqual);
+ continue;
+ }

select  po.oprname,po.oprkind,po.oprcanhash,po.oprleft::regtype,po.oprright,po.oprresult,
po1.oprname
from    pg_operator po join pg_operator po1
on      po.oprcom = po1.oid
where   po.oprresult = 16;

I am wondering, are all these types as long as the return type is bool
suitable for this transformation?

---

From: jian he <[email-masked]>
Date: Wed, 31 Jan 2024 18:15:00 +0800

> (get_op_rettype(opno) != BOOLOID)` branch
I was wrong about this part. sorry for the noise.

I have made some changes (attachment).
* if the operator expression left or right side type category is
{array | domain | composite}, then don't do the transformation.
(i am not 10% sure with composite)

* if the left side of the operator expression node contains volatile
functions, then don't do the transformation.

* some other minor  cosmetic changes.

---

From: Alena Rybakina <[email-masked]>
Date: Wed, 31 Jan 2024 14:10:44 +0300

Hi, thank you for your review and interest in this subject.

On 31.01.2024 13:15, jian he wrote:
> On Wed, Jan 31, 2024 at 10:55 AM jian he<[email-masked]>  wrote:

To be honest, I'm not sure about this check, because we check the type 
of variable there:

if (!IsA(orqual, OpExpr))
         {
             or_list = lappend(or_list, orqual);
             continue;
         }
And below:
if (IsA(leftop, Const))
         {
             opno = get_commutator(opno);

             if (!OidIsValid(opno))
             {
                 /* Commuter doesn't exist, we can't reverse the order */
                 or_list = lappend(or_list, orqual);
                 continue;
             }

             nconst_expr = get_rightop(orqual);
             const_expr = get_leftop(orqual);
         }
         else if (IsA(rightop, Const))
         {
             const_expr = get_rightop(orqual);
             nconst_expr = get_leftop(orqual);
         }
         else
         {
             or_list = lappend(or_list, orqual);
             continue;
         }

Isn't that enough?

Besides, some of examples (with ARRAY) works fine:

postgres=# CREATE TABLE sal_emp (
     pay_by_quarter  integer[],
     pay_by_quater1 integer[]
);
CREATE TABLE
postgres=# INSERT INTO sal_emp
     VALUES (
     '{10000, 10000, 10000, 10000}',
     '{1,2,3,4}');
INSERT 0 1
postgres=# select * from sal_emp where pay_by_quarter[1] = 10000 or 
pay_by_quarter[1]=2;
       pay_by_quarter       | pay_by_quater1
---------------------------+----------------
  {10000,10000,10000,10000} | {1,2,3,4}
(1 row)

postgres=# explain select * from sal_emp where pay_by_quarter[1] = 10000 
or pay_by_quarter[1]=2;
                           QUERY PLAN
--------------------------------------------------------------
  Seq Scan on sal_emp  (cost=0.00..21.00 rows=9 width=64)
    Filter: (pay_by_quarter[1] = ANY ('{10000,2}'::integer[]))
(2 rows)

> functions, then don't do the transformation.

I'm also not sure about the volatility check function, because we 
perform such a conversion at the parsing stage, and at this stage we 
don't have a RelOptInfo variable and especially a RestictInfo such as 
PathTarget.

Speaking of NextValueExpr, I couldn't find any examples where the 
current patch wouldn't work. I wrote one of them below:

postgres=# create table foo (f1 int, f2 int generated always as identity);
CREATE TABLE
postgres=# insert into foo values(1);
INSERT 0 1

postgres=# explain verbose update foo set f1 = 2 where f1=1 or f1=2 ;
                             QUERY PLAN
-------------------------------------------------------------------
  Update on public.foo  (cost=0.00..38.25 rows=0 width=0)
    ->  Seq Scan on public.foo  (cost=0.00..38.25 rows=23 width=10)
          Output: 2, ctid
          Filter: (foo.f1 = ANY ('{1,2}'::integer[]))
(4 rows)

Maybe I missed something. Do you have any examples?

> * some other minor  cosmetic changes.
Thank you, I agree with them.

-- 
Regards,
Alena Rybakina
Postgres Professional:http://www.postgrespro.com
The Russian Postgres Company

---

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