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

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: teodor(at)sigaev(dot)ru
WWW: http://www.sigaev.ru/

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 <teodor(at)sigaev(dot)ru> 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
> 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: teodor(at)sigaev(dot)ru
> WWW:
> http://www.sigaev.ru/
>
>
> --
> Sent via pgsql-hackers mailing list (pgsql-hackers(at)postgresql(dot)org)
> To make changes to your subscription:
> http://www.postgresql.org/mailpref/pgsql-hackers
>
>

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

--
Teodor Sigaev E-mail: teodor(at)sigaev(dot)ru
WWW: http://www.sigaev.ru/

On 27 December 2015 at 07:04, Teodor Sigaev <teodor(at)sigaev(dot)ru> 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
> 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.

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

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

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
> +compileScanKeys(IndexScanDesc scan)
> +{
> +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;
> Is there a reason not to use 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];
> Something is broken here as stackPos can be 0 (going by the if() not the
> Assert()), therefore that's stack[-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..

--
Teodor Sigaev E-mail: teodor(at)sigaev(dot)ru
WWW: http://www.sigaev.ru/

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

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

Oops, will add shortly.
>
> 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.
Ok, will do it.

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

>
> 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
hope, fixed

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

> 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.
Will add soon

>
> 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 = ...
fixed

>
> 6) the code in nodeIndexscan.c should not include call to abort()
>
> {
> abort();
> elog(ERROR, "unsupported indexqual type: %d",
> (int) nodeTag(clause));
> }
fixed, just forgot to remove

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

>
> 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.
I'd like to add separate enable_indexorscan

> 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
...
> 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.
fixed

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

> So I think this way of building the index path from a BitmapOr path is
> pretty much a dead-end.
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!

--
Teodor Sigaev E-mail: teodor(at)sigaev(dot)ru
WWW: http://www.sigaev.ru/

> I also wonder whether the patch should add explanation of OR-clauses
> handling into the READMEs in src/backend/access/*
Not yet, but will

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

> 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.
added

--
Teodor Sigaev E-mail: teodor(at)sigaev(dot)ru
WWW: http://www.sigaev.ru/

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

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

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

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.

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

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

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

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

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
david(at)pgmasters(dot)net

On 3/25/16 11:13 AM, David Steele wrote:

> 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".

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

Thanks,
--
-David
david(at)pgmasters(dot)net

On 12/26/15 23:04, Teodor Sigaev 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
> SELECT count(*) FROM tst WHERE id = 5 OR id = 500 OR id = 5000;
> ...
> 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.
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

I agree with your idea and try to implement it and will soon attach a
patch with a solution.

I also have a really practical example confirming that such optimization
can be useful.

A query was written that consisted of 50000 conditions due to the fact
that the ORM framework couldn't work with a query having an ANY
operator. In summary, we got a better plan that contained 50000 Bitmap
Index Scan nodes with 50000 different conditions. Since approximately
27336 Bite of memory were required to initialize one BitmapOr Index Scan
node, therefore, about 1.27 GB of memory was spent at the initialization
step of the plan execution and query execution time was about 55756,053
ms (00:55,756).

|psql -U postgres -c "CREATE DATABASE test_db" pgbench -U postgres -d
test_db -i -s 10 ||SELECT FORMAT('prepare x %s AS SELECT * FROM pgbench_accounts a WHERE
%s', '(' || string_agg('int', ',') || ')', string_agg(FORMAT('aid =
$%s', g.id), ' or ') ) AS cmd FROM generate_series(1, 50000) AS g(id)
\gexec ||SELECT FORMAT('execute x %s;', '(' || string_agg(g.id::text, ',') ||
')') AS cmd FROM generate_series(1, 50000) AS g(id) \gexec |||||

||

I got the plan of this query:

|QUERY PLAN

---------------------------------------------------------------------------------------------------------------------------------------------------
 Bitmap Heap Scan on pgbench_accounts a  (cost=44.35..83.96 rows=10
width=97)
   Recheck Cond: ((aid = 1) OR (aid = 2) OR (aid = 3) OR (aid = 4) OR
(aid = 5) OR (aid = 6) OR (aid = 7) OR (aid = 8) OR (aid = 9) OR (aid = 10))
   ->  BitmapOr  (cost=44.35..44.35 rows=10 width=0)
         ->  Bitmap Index Scan on pgbench_accounts_pkey
(cost=0.00..4.43 rows=1 width=0)
               Index Cond: (aid = 1)
         ->  Bitmap Index Scan on pgbench_accounts_pkey
(cost=0.00..4.43 rows=1 width=0)
               Index Cond: (aid = 2)
         ->  Bitmap Index Scan on pgbench_accounts_pkey
(cost=0.00..4.43 rows=1 width=0)
               Index Cond: (aid = 3)
         ->  Bitmap Index Scan on pgbench_accounts_pkey
(cost=0.00..4.43 rows=1 width=0)
               Index Cond: (aid = 4)
         ->  Bitmap Index Scan on pgbench_accounts_pkey
(cost=0.00..4.43 rows=1 width=0)
               Index Cond: (aid = 5)
         ->  Bitmap Index Scan on pgbench_accounts_pkey
(cost=0.00..4.43 rows=1 width=0)
               Index Cond: (aid = 6)
         ->  Bitmap Index Scan on pgbench_accounts_pkey
(cost=0.00..4.43 rows=1 width=0)
               Index Cond: (aid = 7)
         ->  Bitmap Index Scan on pgbench_accounts_pkey
(cost=0.00..4.43 rows=1 width=0)
               Index Cond: (aid = 8)
         ->  Bitmap Index Scan on pgbench_accounts_pkey
(cost=0.00..4.43 rows=1 width=0)
               Index Cond: (aid = 9)
         ->  Bitmap Index Scan on pgbench_accounts_pkey
(cost=0.00..4.43 rows=1 width=0)
               Index Cond: (aid = 10)|

If I rewrite this query using ANY operator,

SELECT FORMAT('prepare x %s AS SELECT * FROM pgbench_accounts a WHERE aid = ANY(SELECT
g.id FROM generate_series(1, 50000) AS g(id))',
'(' || string_agg('int',',') ||')'
) AS cmd FROM generate_series(1, 50000) AS g(id)
\gexec

I will get a plan where the array comparison operator is used through
ANY operator at the index scan stage. It's execution time is
significantly lower as  339,764 ms.

QUERY PLAN
---------------------------------------------------------------------------------------------------
Index Scan using pgbench_accounts_pkey on pgbench_accounts a (cost=0.42..48.43 rows=10 width=97)
Index Cond: (aid = ANY ('{1,2,3,4,5,6,7,8,9,10}'::integer[]))
(2 rows)

IN operator is also converted to ANY operator, and if I rewrite this
query as:

SELECT FORMAT('prepare x %s AS SELECT * FROM pgbench_accounts a WHERE aid IN(%s)',
'(' || string_agg('int',',') ||')',
string_agg(FORMAT('%s', g.id),', ')
) AS cmd
FROM generate_series(1, 50000) AS g(id)
\gexec

I will get the same plan as the previous one using ANY operator and his
execution time will be about the same.

QUERY PLAN
---------------------------------------------------------------------------------------------------
Index Scan using pgbench_accounts_pkey on pgbench_accounts a (cost=0.42..48.43 rows=10 width=97)
Index Cond: (aid = ANY ('{1,2,3,4,5,6,7,8,9,10}'::integer[]))
(2 rows)

On 28.12.2022 07:19, Andrey Lepikhov wrote:
> On 12/26/15 23:04, Teodor Sigaev 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
>> SELECT count(*) FROM tst WHERE id = 5 OR id = 500 OR id = 5000;
>> ...
>> 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.
> 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.
>
--
Alena Rybakina
Postgres Professional

>
> I agree with your idea and try to implement it and will soon attach a
> patch with a solution.
>
Additionally, if those OR constants repeat you'll see ...
If all constants are the same value, fine
explain select * from x where ((ID = 1) OR (ID = 1) OR (ID = 1));
Index Only Scan using x_id on x (cost=0.42..4.44 rows=1 width=4)
Index Cond: (id = 1)

if all values are almost the same, ops
explain select * from x where ((ID = 1) OR (ID = 1) OR (ID = 1) OR (ID =
2));
Bitmap Heap Scan on x (cost=17.73..33.45 rows=4 width=4)
Recheck Cond: ((id = 1) OR (id = 1) OR (id = 1) OR (id = 2))
-> BitmapOr (cost=17.73..17.73 rows=4 width=0)
-> Bitmap Index Scan on x_id (cost=0.00..4.43 rows=1 width=0)
Index Cond: (id = 1)
-> Bitmap Index Scan on x_id (cost=0.00..4.43 rows=1 width=0)
Index Cond: (id = 1)
-> Bitmap Index Scan on x_id (cost=0.00..4.43 rows=1 width=0)
Index Cond: (id = 1)
-> Bitmap Index Scan on x_id (cost=0.00..4.43 rows=1 width=0)
Index Cond: (id = 2)

thanks
Marcos

Hi, all! Sorry I haven't written for a long time.

I finished writing the code patch for transformation "Or" expressions to
"Any" expressions. I didn't see any problems in regression tests, even
when I changed the constant at which the minimum or expression is
replaced by any at 0. I ran my patch on sqlancer and so far the code has
never fallen.

On 14.01.2023 18:45, Marcos Pegoraro wrote:
>
> I agree with your idea and try to implement it and will soon
> attach a patch with a solution.
>
> Additionally, if those OR constants repeat you'll see ...
> If all constants are the same value, fine
> explain select * from x where ((ID = 1) OR (ID = 1) OR (ID = 1));
> Index Only Scan using x_id on x  (cost=0.42..4.44 rows=1 width=4)
>   Index Cond: (id = 1)
>
> if all values are almost the same, ops
> explain select * from x where ((ID = 1) OR (ID = 1) OR (ID = 1) OR (ID
> = 2));
> Bitmap Heap Scan on x  (cost=17.73..33.45 rows=4 width=4)
>   Recheck Cond: ((id = 1) OR (id = 1) OR (id = 1) OR (id = 2))
>   ->  BitmapOr  (cost=17.73..17.73 rows=4 width=0)
>         ->  Bitmap Index Scan on x_id  (cost=0.00..4.43 rows=1 width=0)
>               Index Cond: (id = 1)
>         ->  Bitmap Index Scan on x_id  (cost=0.00..4.43 rows=1 width=0)
>               Index Cond: (id = 1)
>         ->  Bitmap Index Scan on x_id  (cost=0.00..4.43 rows=1 width=0)
>               Index Cond: (id = 1)
>         ->  Bitmap Index Scan on x_id  (cost=0.00..4.43 rows=1 width=0)
>               Index Cond: (id = 2)
>
> thanks
> Marcos
>
--

Regards,

Alena Rybakina

Sorry,  I wrote the last sentence in a confusing way, I meant that I
formed transformations for any number of "or" expressions
(const_transform_or_limit=1). in regression tests, I noticed only diff
changes of transformations of "or" expressions to "any". I attach a file
with diff.

On 26.06.2023 04:47, Alena Rybakina wrote:
>
> Hi, all! Sorry I haven't written for a long time.
>
> I finished writing the code patch for transformation "Or" expressions
> to "Any" expressions. I didn't see any problems in regression tests,
> even when I changed the constant at which the minimum or expression is
> replaced by any at 0. I ran my patch on sqlancer and so far the code
> has never fallen.
>
> On 14.01.2023 18:45, Marcos Pegoraro wrote:
>>
>> I agree with your idea and try to implement it and will soon
>> attach a patch with a solution.
>>
>> Additionally, if those OR constants repeat you'll see ...
>> If all constants are the same value, fine
>> explain select * from x where ((ID = 1) OR (ID = 1) OR (ID = 1));
>> Index Only Scan using x_id on x  (cost=0.42..4.44 rows=1 width=4)
>>   Index Cond: (id = 1)
>>
>> if all values are almost the same, ops
>> explain select * from x where ((ID = 1) OR (ID = 1) OR (ID = 1) OR
>> (ID = 2));
>> Bitmap Heap Scan on x  (cost=17.73..33.45 rows=4 width=4)
>>   Recheck Cond: ((id = 1) OR (id = 1) OR (id = 1) OR (id = 2))
>>   ->  BitmapOr  (cost=17.73..17.73 rows=4 width=0)
>>         ->  Bitmap Index Scan on x_id  (cost=0.00..4.43 rows=1 width=0)
>>               Index Cond: (id = 1)
>>         ->  Bitmap Index Scan on x_id  (cost=0.00..4.43 rows=1 width=0)
>>               Index Cond: (id = 1)
>>         ->  Bitmap Index Scan on x_id  (cost=0.00..4.43 rows=1 width=0)
>>               Index Cond: (id = 1)
>>         ->  Bitmap Index Scan on x_id  (cost=0.00..4.43 rows=1 width=0)
>>               Index Cond: (id = 2)
>>
>> thanks
>> Marcos
>>
> --
>
> Regards,
>
> Alena Rybakina
>

On Sun, Jun 25, 2023 at 6:48 PM Alena Rybakina <lena(dot)ribackina(at)yandex(dot)ru> wrote:
> I finished writing the code patch for transformation "Or" expressions to "Any" expressions.

This seems interesting to me. I'm currently working on improving
nbtree's "native execution of ScalarArrayOpExpr quals" (see commit
9e8da0f7 for background information). That is relevant to what you're
trying to do here.

Right now nbtree's handling of ScalarArrayOpExpr is rather
inefficient. The executor does pass the index scan an array of
constants, so the whole structure already allows the nbtree code to
execute the ScalarArrayOpExpr in whatever way would be most efficient.
There is only one problem: it doesn't really try to do so. It more or
less just breaks down the large ScalarArrayOpExpr into "mini" queries
-- one per constant. Internally, query execution isn't significantly
different to executing many of these "mini" queries independently. We
just sort and deduplicate the arrays. We don't intelligently decide
which pages dynamically. This is related to skip scan.

Attached is an example query that shows the problem. Right now the
query needs to access a buffer containing an index page a total of 24
times. It's actually accessing the same 2 pages 12 times. My draft
patch only requires 2 buffer accesses -- because it "coalesces the
array constants together" dynamically at run time. That is a little
extreme, but it's certainly possible.

BTW, this project is related to skip scan. It's part of the same
family of techniques -- MDAM techniques. (I suppose that that's
already true for ScalarArrayOpExpr execution by nbtree, but without
dynamic behavior it's not nearly as valuable as it could be.)

If executing ScalarArrayOpExprs was less inefficient in these cases
then the planner could be a lot more aggressive about using them.
Seems like these executor improvements might go well together with
what you're doing in the planner. Note that I have to "set
random_page_cost=0.1" to get the planner to use all of the quals from
the query as index quals. It thinks (correctly) that the query plan is
very inefficient. That happens to match reality right now, but the
underlying reality could change significantly. Something to think
about.

--
Peter Geoghegan

On 26.06.2023 06:18, Peter Geoghegan wrote:
> On Sun, Jun 25, 2023 at 6:48 PM Alena Rybakina<lena(dot)ribackina(at)yandex(dot)ru> wrote:
>> I finished writing the code patch for transformation "Or" expressions to "Any" expressions.
> This seems interesting to me. I'm currently working on improving
> nbtree's "native execution of ScalarArrayOpExpr quals" (see commit
> 9e8da0f7 for background information). That is relevant to what you're
> trying to do here.
>
> Right now nbtree's handling of ScalarArrayOpExpr is rather
> inefficient. The executor does pass the index scan an array of
> constants, so the whole structure already allows the nbtree code to
> execute the ScalarArrayOpExpr in whatever way would be most efficient.
> There is only one problem: it doesn't really try to do so. It more or
> less just breaks down the large ScalarArrayOpExpr into "mini" queries
> -- one per constant. Internally, query execution isn't significantly
> different to executing many of these "mini" queries independently. We
> just sort and deduplicate the arrays. We don't intelligently decide
> which pages dynamically. This is related to skip scan.
>
> Attached is an example query that shows the problem. Right now the
> query needs to access a buffer containing an index page a total of 24
> times. It's actually accessing the same 2 pages 12 times. My draft
> patch only requires 2 buffer accesses -- because it "coalesces the
> array constants together" dynamically at run time. That is a little
> extreme, but it's certainly possible.
>
> BTW, this project is related to skip scan. It's part of the same
> family of techniques -- MDAM techniques. (I suppose that that's
> already true for ScalarArrayOpExpr execution by nbtree, but without
> dynamic behavior it's not nearly as valuable as it could be.)
>
> If executing ScalarArrayOpExprs was less inefficient in these cases
> then the planner could be a lot more aggressive about using them.
> Seems like these executor improvements might go well together with
> what you're doing in the planner. Note that I have to "set
> random_page_cost=0.1" to get the planner to use all of the quals from
> the query as index quals. It thinks (correctly) that the query plan is
> very inefficient. That happens to match reality right now, but the
> underlying reality could change significantly. Something to think
> about.
>
> --
> Peter Geoghegan
Thank you for your feedback, your work is also very interesting and
important, and I will be happy to review it. I learned something new
from your letter, thank you very much for that!

I analyzed the buffer consumption when I ran control regression tests
using my patch. diff shows me that there is no difference between the
number of buffer block scans without and using my patch, as far as I
have seen. (regression.diffs)

In addition, I analyzed the scheduling and duration of the execution
time of the source code and with my applied patch. I generated 20
billion data from pgbench and plotted the scheduling and execution time
depending on the number of "or" expressions.
By runtime, I noticed a clear acceleration for queries when using the
index, but I can't say the same when the index is disabled.
At first I turned it off in this way:
1)enable_seqscan='off'
2)enable_indexonlyscan='off'
enable_indexscan='off'

Unfortunately, it is not yet clear which constant needs to be set when
the transformation needs to be done, I will still study in detail. (the
graph for all this is presented in graph1.svg)
\\

--
Regards,
Alena Rybakina

On 27.06.2023 16:19, Alena Rybakina wrote:
> Thank you for your feedback, your work is also very interesting and
> important, and I will be happy to review it. I learned something new
> from your letter, thank you very much for that!
>
> I analyzed the buffer consumption when I ran control regression tests
> using my patch. diff shows me that there is no difference between the
> number of buffer block scans without and using my patch, as far as I
> have seen. (regression.diffs)
>
>
> In addition, I analyzed the scheduling and duration of the execution
> time of the source code and with my applied patch. I generated 20
> billion data from pgbench and plotted the scheduling and execution
> time depending on the number of "or" expressions.
> By runtime, I noticed a clear acceleration for queries when using the
> index, but I can't say the same when the index is disabled.
> At first I turned it off in this way:
> 1)enable_seqscan='off'
> 2)enable_indexonlyscan='off'
> enable_indexscan='off'
>
> Unfortunately, it is not yet clear which constant needs to be set when
> the transformation needs to be done, I will still study in detail.
> (the graph for all this is presented in graph1.svg)
> \\
> --
> Regards,
> Alena Rybakina
Sorry, just now I noticed that there were incorrect names in the
headings of the pictures, I corrected it. I also attach its html copy,
because it may be more convenient for viewing it.

--
Regards,
Alena Rybakina

On Tue, Jun 27, 2023 at 6:19 AM Alena Rybakina <lena(dot)ribackina(at)yandex(dot)ru> wrote:
> I learned something new from your letter, thank you very much for that!

Cool. The MDAM paper is also worth a read:

https://vldb.org/conf/1995/P710.PDF

Some of the techniques it describes are already in Postgres. With
varying degrees of maturity.

The paper actually mentions OR optimization at one point, under
"Duplicate Elimination". The general idea is that ScalarArrayOpExpr
execution can "eliminate duplicates before the data is read". The
important underlying principle is that it can be really useful to give
the B-Tree code the context it requires to be clever about stuff like
that. We can do this by (say) using one ScalarArrayOpExpr, rather than
using two or more index scans that the B-Tree code will treat as
independent things. So a lot of the value in your patch comes from the
way that it can enable other optimizations (the immediate benefits are
also nice).

In the past, OR optimizations have been prototyped that were later
withdrawn/rejected because the duplicate elimination aspect was...too
scary [1]. It's very easy to see that ScalarArrayOpExpr index scans
don't really have the same problem. "Giving the B-Tree code the
required context" helps here too.

> I analyzed the buffer consumption when I ran control regression tests using my patch. diff shows me that there is no difference between the number of buffer block scans without and using my patch, as far as I have seen. (regression.diffs)

To be clear, I wasn't expecting that there'd be any regressions from
your patch. Intuitively, it seems like this optimization should make
the query plan do almost the same thing at execution time -- just
slightly more efficiently on average, and much more efficiently in
some individual cases.

It would probably be very hard for the optimizer to model/predict how
much work it can save by using a ScalarArrayOpExpr instead of an
"equivalent" set of bitmap index scans, OR'd together. But it doesn't
necessarily matter -- the only truly critical detail is understanding
the worst case for the transformation optimization. It cannot be too
bad (maybe it's ~zero added runtime overhead relative to not doing the
transformation, even?). At the same time, nbtree can be clever about
ScalarArrayOpExpr execution at runtime (once that's implemented),
without ever needing to make any kind of up-front commitment to
navigating through the index in any particular way. It's all dynamic,
and can be driven by the actual observed characteristics of the index
structure.

In other words, we don't really need to gamble (in the planner, or at
execution time). We're just keeping our options open in more cases.
(My thinking on these topics was influenced by Goetz Graefe -- "choice
is confusion" [2]).

[1] https://www.postgresql.org/message-id/flat/1397.1486598083%40sss.pgh.pa.us#310f974a8dc84478d6d3c70f336807bb
[2] https://sigmodrecord.org/publications/sigmodRecord/2009/pdfs/05_Profiles_Graefe.pdf
--
Peter Geoghegan

Hi! I'm sorry I didn't answer you right away, I was too busy with work.

On 27.06.2023 22:50, Peter Geoghegan wrote:
> On Tue, Jun 27, 2023 at 6:19 AM Alena Rybakina<lena(dot)ribackina(at)yandex(dot)ru> wrote:
>> I learned something new from your letter, thank you very much for that!
> Cool. The MDAM paper is also worth a read:
>
> https://vldb.org/conf/1995/P710.PDF
>
> Some of the techniques it describes are already in Postgres. With
> varying degrees of maturity.
>
> The paper actually mentions OR optimization at one point, under
> "Duplicate Elimination". The general idea is that ScalarArrayOpExpr
> execution can "eliminate duplicates before the data is read". The
> important underlying principle is that it can be really useful to give
> the B-Tree code the context it requires to be clever about stuff like
> that. We can do this by (say) using one ScalarArrayOpExpr, rather than
> using two or more index scans that the B-Tree code will treat as
> independent things. So a lot of the value in your patch comes from the
> way that it can enable other optimizations (the immediate benefits are
> also nice).
>
> In the past, OR optimizations have been prototyped that were later
> withdrawn/rejected because the duplicate elimination aspect was...too
> scary [1]. It's very easy to see that ScalarArrayOpExpr index scans
> don't really have the same problem. "Giving the B-Tree code the
> required context" helps here too.
>
Thank you for the explanation and the material provided) unfortunately,
I am still only studying the article and at the moment I cannot write
more. To be honest, I didn't think about the fact that my optimization
can help eliminate duplicates before reading the data before.

I am still only in the process of familiarizing myself with the thread
[1] (reference from your letter), but I have already seen that there are
problems related, for example, to when "or" expressions refer to the
parent element.

I think, I would face the similar problems if I complicate the current
code, for example, so that not only or expressions standing on the same
level are written in any, but also on different ones without violating
the logic of the priority of executing operators.

For example, this query works now:

postgres=# EXPLAIN (analyze, COSTS OFF)
SELECT oid,relname FROM pg_class
WHERE
  (oid = 13779 OR oid = 2) OR (oid = 4 OR oid = 5) OR
  relname = 'pg_extension'
;

                                                    QUERY PLAN
------------------------------------------------------------------------------------------------------------------
 Seq Scan on pg_class (actual time=0.086..0.140 rows=1 loops=1)
   Filter: ((oid = ANY ('{4,5}'::oid[])) OR (oid = ANY
('{13779,2}'::oid[])) OR (relname = 'pg_extension'::name))
   Rows Removed by Filter: 412
 Planning Time: 2.135 ms
 Execution Time: 0.160 ms
(5 rows)

But I would like it works such as:

                                      QUERY PLAN
--------------------------------------------------------------------------------------
 Seq Scan on pg_class (actual time=0.279..0.496 rows=1 loops=1)
   Filter: ((oid = ANY ('{13779,2,4,5}'::oid[])) OR (relname =
'pg_extension'::name))
   Rows Removed by Filter: 412
 Planning Time: 0.266 ms
 Execution Time: 0.536 ms
(5 rows)

>> I analyzed the buffer consumption when I ran control regression tests using my patch. diff shows me that there is no difference between the number of buffer block scans without and using my patch, as far as I have seen. (regression.diffs)
> To be clear, I wasn't expecting that there'd be any regressions from
> your patch. Intuitively, it seems like this optimization should make
> the query plan do almost the same thing at execution time -- just
> slightly more efficiently on average, and much more efficiently in
> some individual cases.
>
> It would probably be very hard for the optimizer to model/predict how
> much work it can save by using a ScalarArrayOpExpr instead of an
> "equivalent" set of bitmap index scans, OR'd together. But it doesn't
> necessarily matter -- the only truly critical detail is understanding
> the worst case for the transformation optimization.
Yes, I agree with you and I have yet to analyze this.
> It cannot be too
> bad (maybe it's ~zero added runtime overhead relative to not doing the
> transformation, even?).
I haven't seen a major performance degradation so far, but to be honest,
I have not conducted a detailed analysis on other types of queries other
than x=1 or x=2 or x=1 or y=2, etc. As soon as something is known, I
will provide the data, it is very interesting to me.
> At the same time, nbtree can be clever about
> ScalarArrayOpExpr execution at runtime (once that's implemented),
> without ever needing to make any kind of up-front commitment to
> navigating through the index in any particular way. It's all dynamic,
> and can be driven by the actual observed characteristics of the index
> structure.
>
> In other words, we don't really need to gamble (in the planner, or at
> execution time). We're just keeping our options open in more cases.
> (My thinking on these topics was influenced by Goetz Graefe -- "choice
> is confusion" [2]).

Unfortunately, when I tried to make a transformation at the stage of
index formation, I encountered too incorrect an assessment of the
selectivity of relation, which affected the incorrect calculation of the
cost and cardinality. I couldn't solve this problem.

My diff (transform_or_v0.diff). I got this result:

CREATE TABLE tenk1 (unique1int, unique2int, tenint, hundredint);
insert into tenk1 SELECT x,x,x,x FROM generate_series(1,50000) as x;
CREATE INDEX a_idx1 ON tenk1(unique1);
CREATE INDEX a_idx2 ON tenk1(unique2);
CREATE INDEX a_hundred ON tenk1(hundred);

postgres=# explain analyze
select * from tenk1 a join tenk1 b on
a.unique2 = 3 or a.unique2 = 7 or a.unique1 = 1;
QUERY PLAN
----------------------------------------------------------------------------------------------------------------------
Nested Loop (cost=0.00..15627479.50 rows=1250050000 width=32) (actual time=0.040..75.531 rows=150000 loops=1)
-> Seq Scan on tenk1 b (cost=0.00..771.00 rows=50000 width=16) (actual time=0.022..5.467 rows=50000 loops=1)
-> Materialize (cost=0.00..1146.01 rows=25001 width=16) (actual time=0.000..0.001 rows=3 loops=50000)
-> Seq Scan on tenk1 a (cost=0.00..1021.00 rows=25001 width=16) (actual time=0.011..22.789 rows=3 loops=1)
Filter: ((unique2 = ANY (ARRAY[3, 7])) OR (unique1 = 1))
Rows Removed by Filter: 49997
Planning Time: 0.427 ms
Execution Time: 80.027 ms
(8 rows)

The current patch's result:

postgres=# set enable_bitmapscan ='off';
SET
postgres=# explain analyze
select * from tenk1 a join tenk1 b on
a.unique2 = 3 or a.unique2 = 7 or a.unique1 = 1;
QUERY PLAN
----------------------------------------------------------------------------------------------------------------------
Nested Loop (cost=0.00..22247.02 rows=1350000 width=32) (actual time=0.094..373.627 rows=1350000 loops=1)
-> Seq Scan on tenk1 b (cost=0.00..2311.00 rows=150000 width=16) (actual time=0.051..14.667 rows=150000 loops=1)
-> Materialize (cost=0.00..3061.05 rows=9 width=16) (actual time=0.000..0.001 rows=9 loops=150000)
-> Seq Scan on tenk1 a (cost=0.00..3061.00 rows=9 width=16) (actual time=0.026..42.389 rows=9 loops=1)
Filter: ((unique2 = ANY ('{3,7}'::integer[])) OR (unique1 = 1))
Rows Removed by Filter: 149991
Planning Time: 0.414 ms
Execution Time: 409.154 ms
(8 rows)

> [1]https://www.postgresql.org/message-id/flat/1397.1486598083%40sss.pgh.pa.us#310f974a8dc84478d6d3c70f336807bb
> [2]https://sigmodrecord.org/publications/sigmodRecord/2009/pdfs/05_Profiles_Graefe.pdf
Thank you again for the explanations and the material provided. I will
carefully study everything as soon as possible and will write if there
are any thoughts or if there are ideas about my patch.

--

Regards,
Alena Rybakina
Postgres Professional

I apologize for breaks the original thread. In my defense, I can say
that I'm new to all this and I'm just learning. I will try to make as
few mistakes as possible.

I try to fix it by forwarding this message to you, besides it might be
interesting to you too. This message to you, because it might be
interesting to you too.

I'm sorry if I didn't state my goals clearly at first, but it seemed to
me that initially the problem I encountered was very similar to what is
described in this thread, only I suggested a slightly different way to
solve it.

I have described the problem more or less clearly here [1] and the worst
case, as it seems to me, too, but if this is not the case, let me know.

1.
https://www.mail-archive.com/pgsql-hackers(at)lists(dot)postgresql(dot)org/msg146230.html

> On 29.06.2023 12:32, Alena Rybakina wrote:
>>
>> Hi! I'm sorry I didn't answer you right away, I was too busy with work.
>>
>> On 27.06.2023 22:50, Peter Geoghegan wrote:
>>> On Tue, Jun 27, 2023 at 6:19 AM Alena Rybakina<lena(dot)ribackina(at)yandex(dot)ru> wrote:
>>>> I learned something new from your letter, thank you very much for that!
>>> Cool. The MDAM paper is also worth a read:
>>>
>>> https://vldb.org/conf/1995/P710.PDF
>>>
>>> Some of the techniques it describes are already in Postgres. With
>>> varying degrees of maturity.
>>>
>>> The paper actually mentions OR optimization at one point, under
>>> "Duplicate Elimination". The general idea is that ScalarArrayOpExpr
>>> execution can "eliminate duplicates before the data is read". The
>>> important underlying principle is that it can be really useful to give
>>> the B-Tree code the context it requires to be clever about stuff like
>>> that. We can do this by (say) using one ScalarArrayOpExpr, rather than
>>> using two or more index scans that the B-Tree code will treat as
>>> independent things. So a lot of the value in your patch comes from the
>>> way that it can enable other optimizations (the immediate benefits are
>>> also nice).
>>>
>>> In the past, OR optimizations have been prototyped that were later
>>> withdrawn/rejected because the duplicate elimination aspect was...too
>>> scary [1]. It's very easy to see that ScalarArrayOpExpr index scans
>>> don't really have the same problem. "Giving the B-Tree code the
>>> required context" helps here too.
>>>
>> Thank you for the explanation and the material provided)
>> unfortunately, I am still only studying the article and at the moment
>> I cannot write more. To be honest, I didn't think about the fact that
>> my optimization can help eliminate duplicates before reading the data
>> before.
>>
>> I am still only in the process of familiarizing myself with the
>> thread [1] (reference from your letter), but I have already seen that
>> there are problems related, for example, to when "or" expressions
>> refer to the parent element.
>>
>> I think, I would face the similar problems if I complicate the
>> current code, for example, so that not only or expressions standing
>> on the same level are written in any, but also on different ones
>> without violating the logic of the priority of executing operators.
>>
>> For example, this query works now:
>>
>> postgres=# EXPLAIN (analyze, COSTS OFF)
>> SELECT oid,relname FROM pg_class
>> WHERE
>>   (oid = 13779 OR oid = 2) OR (oid = 4 OR oid = 5) OR
>>   relname = 'pg_extension'
>> ;
>>
>>                                                     QUERY PLAN
>> ------------------------------------------------------------------------------------------------------------------
>>  Seq Scan on pg_class (actual time=0.086..0.140 rows=1 loops=1)
>>    Filter: ((oid = ANY ('{4,5}'::oid[])) OR (oid = ANY
>> ('{13779,2}'::oid[])) OR (relname = 'pg_extension'::name))
>>    Rows Removed by Filter: 412
>>  Planning Time: 2.135 ms
>>  Execution Time: 0.160 ms
>> (5 rows)
>>
>> But I would like it works such as:
>>
>>                                       QUERY PLAN
>> --------------------------------------------------------------------------------------
>>  Seq Scan on pg_class (actual time=0.279..0.496 rows=1 loops=1)
>>    Filter: ((oid = ANY ('{13779,2,4,5}'::oid[])) OR (relname =
>> 'pg_extension'::name))
>>    Rows Removed by Filter: 412
>>  Planning Time: 0.266 ms
>>  Execution Time: 0.536 ms
>> (5 rows)
>>
>>>> I analyzed the buffer consumption when I ran control regression tests using my patch. diff shows me that there is no difference between the number of buffer block scans without and using my patch, as far as I have seen. (regression.diffs)
>>> To be clear, I wasn't expecting that there'd be any regressions from
>>> your patch. Intuitively, it seems like this optimization should make
>>> the query plan do almost the same thing at execution time -- just
>>> slightly more efficiently on average, and much more efficiently in
>>> some individual cases.
>>>
>>> It would probably be very hard for the optimizer to model/predict how
>>> much work it can save by using a ScalarArrayOpExpr instead of an
>>> "equivalent" set of bitmap index scans, OR'd together. But it doesn't
>>> necessarily matter -- the only truly critical detail is understanding
>>> the worst case for the transformation optimization.
>> Yes, I agree with you and I have yet to analyze this.
>>> It cannot be too
>>> bad (maybe it's ~zero added runtime overhead relative to not doing the
>>> transformation, even?).
>> I haven't seen a major performance degradation so far, but to be
>> honest, I have not conducted a detailed analysis on other types of
>> queries other than x=1 or x=2 or x=1 or y=2, etc. As soon as
>> something is known, I will provide the data, it is very interesting
>> to me.
>>> At the same time, nbtree can be clever about
>>> ScalarArrayOpExpr execution at runtime (once that's implemented),
>>> without ever needing to make any kind of up-front commitment to
>>> navigating through the index in any particular way. It's all dynamic,
>>> and can be driven by the actual observed characteristics of the index
>>> structure.
>>>
>>> In other words, we don't really need to gamble (in the planner, or at
>>> execution time). We're just keeping our options open in more cases.
>>> (My thinking on these topics was influenced by Goetz Graefe -- "choice
>>> is confusion" [2]).
>>
>> Unfortunately, when I tried to make a transformation at the stage of
>> index formation, I encountered too incorrect an assessment of the
>> selectivity of relation, which affected the incorrect calculation of
>> the cost and cardinality. I couldn't solve this problem.
>>
>> My diff (transform_or_v0.diff). I got this result:
>>
>> CREATE TABLE tenk1 (unique1int, unique2int, tenint, hundredint);
>> insert into tenk1 SELECT x,x,x,x FROM generate_series(1,50000) as x;
>> CREATE INDEX a_idx1 ON tenk1(unique1);
>> CREATE INDEX a_idx2 ON tenk1(unique2);
>> CREATE INDEX a_hundred ON tenk1(hundred);
>>
>> postgres=# explain analyze
>> select * from tenk1 a join tenk1 b on
>> a.unique2 = 3 or a.unique2 = 7 or a.unique1 = 1;
>> QUERY PLAN
>> ----------------------------------------------------------------------------------------------------------------------
>> Nested Loop (cost=0.00..15627479.50 rows=1250050000 width=32) (actual time=0.040..75.531 rows=150000 loops=1)
>> -> Seq Scan on tenk1 b (cost=0.00..771.00 rows=50000 width=16) (actual time=0.022..5.467 rows=50000 loops=1)
>> -> Materialize (cost=0.00..1146.01 rows=25001 width=16) (actual time=0.000..0.001 rows=3 loops=50000)
>> -> Seq Scan on tenk1 a (cost=0.00..1021.00 rows=25001 width=16) (actual time=0.011..22.789 rows=3 loops=1)
>> Filter: ((unique2 = ANY (ARRAY[3, 7])) OR (unique1 = 1))
>> Rows Removed by Filter: 49997
>> Planning Time: 0.427 ms
>> Execution Time: 80.027 ms
>> (8 rows)
>>
>> The current patch's result:
>>
>> postgres=# set enable_bitmapscan ='off';
>> SET
>> postgres=# explain analyze
>> select * from tenk1 a join tenk1 b on
>> a.unique2 = 3 or a.unique2 = 7 or a.unique1 = 1;
>> QUERY PLAN
>> ----------------------------------------------------------------------------------------------------------------------
>> Nested Loop (cost=0.00..22247.02 rows=1350000 width=32) (actual time=0.094..373.627 rows=1350000 loops=1)
>> -> Seq Scan on tenk1 b (cost=0.00..2311.00 rows=150000 width=16) (actual time=0.051..14.667 rows=150000 loops=1)
>> -> Materialize (cost=0.00..3061.05 rows=9 width=16) (actual time=0.000..0.001 rows=9 loops=150000)
>> -> Seq Scan on tenk1 a (cost=0.00..3061.00 rows=9 width=16) (actual time=0.026..42.389 rows=9 loops=1)
>> Filter: ((unique2 = ANY ('{3,7}'::integer[])) OR (unique1 = 1))
>> Rows Removed by Filter: 149991
>> Planning Time: 0.414 ms
>> Execution Time: 409.154 ms
>> (8 rows)
>>
>>> [1]https://www.postgresql.org/message-id/flat/1397.1486598083%40sss.pgh.pa.us#310f974a8dc84478d6d3c70f336807bb
>>> [2]https://sigmodrecord.org/publications/sigmodRecord/2009/pdfs/05_Profiles_Graefe.pdf
>> Thank you again for the explanations and the material provided. I
>> will carefully study everything as soon as possible and will write if
>> there are any thoughts or if there are ideas about my patch.

--
Regards,
Alena Rybakina
Postgres Professional

Em qui., 29 de jun. de 2023 às 06:56, Alena Rybakina <
lena(dot)ribackina(at)yandex(dot)ru> escreveu:

> I apologize for breaks the original thread. In my defense, I can say that
> I'm new to all this and I'm just learning. I will try to make as few
> mistakes as possible.
>
By no means, your work is excellent and deserves all compliments.

regards,
Ranier Vilela

On 29.06.2023 14:23, Ranier Vilela wrote:
> Em qui., 29 de jun. de 2023 às 06:56, Alena Rybakina
> <lena(dot)ribackina(at)yandex(dot)ru> escreveu:
>
> I apologize for breaks the original thread. In my defense, I can
> say that I'm new to all this and I'm just learning. I will try to
> make as few mistakes as possible.
>
> By no means, your work is excellent and deserves all compliments.

Thank you, I will try to work in the same spirit, especially since there
is still quite a lot of work left).

Thank you for your feedback.

--
Regards,
Alena Rybakina
Postgres Professional

HI, all!

> On 27.06.2023 16:19, Alena Rybakina wrote:
>> Thank you for your feedback, your work is also very interesting and
>> important, and I will be happy to review it. I learned something new
>> from your letter, thank you very much for that!
>>
>> I analyzed the buffer consumption when I ran control regression tests
>> using my patch. diff shows me that there is no difference between the
>> number of buffer block scans without and using my patch, as far as I
>> have seen. (regression.diffs)
>>
>>
>> In addition, I analyzed the scheduling and duration of the execution
>> time of the source code and with my applied patch. I generated 20
>> billion data from pgbench and plotted the scheduling and execution
>> time depending on the number of "or" expressions.
>> By runtime, I noticed a clear acceleration for queries when using the
>> index, but I can't say the same when the index is disabled.
>> At first I turned it off in this way:
>> 1)enable_seqscan='off'
>> 2)enable_indexonlyscan='off'
>> enable_indexscan='off'
>>
>> Unfortunately, it is not yet clear which constant needs to be set
>> when the transformation needs to be done, I will still study in
>> detail. (the graph for all this is presented in graph1.svg

I finished comparing the performance of queries with converted or
expressions and the original ones and found that about 500 "OR"
expressions have significantly noticeable degradation of execution time,
both using the index and without it (you can look at
time_comsuption_with_indexes.png and time_comsuption_without_indexes.html )

The test was performed on the same benchmark database generated by 2
billion values.

I corrected this constant in the patch.

--
Regards,
Alena Rybakina
Postgres Professional

Sorry, I threw off the wrong charts, I'm sending the right ones.

On 05.07.2023 22:39, Alena Rybakina wrote:
> HI, all!
>
>> On 27.06.2023 16:19, Alena Rybakina wrote:
>>> Thank you for your feedback, your work is also very interesting and
>>> important, and I will be happy to review it. I learned something new
>>> from your letter, thank you very much for that!
>>>
>>> I analyzed the buffer consumption when I ran control regression
>>> tests using my patch. diff shows me that there is no difference
>>> between the number of buffer block scans without and using my patch,
>>> as far as I have seen. (regression.diffs)
>>>
>>>
>>> In addition, I analyzed the scheduling and duration of the execution
>>> time of the source code and with my applied patch. I generated 20
>>> billion data from pgbench and plotted the scheduling and execution
>>> time depending on the number of "or" expressions.
>>> By runtime, I noticed a clear acceleration for queries when using
>>> the index, but I can't say the same when the index is disabled.
>>> At first I turned it off in this way:
>>> 1)enable_seqscan='off'
>>> 2)enable_indexonlyscan='off'
>>> enable_indexscan='off'
>>>
>>> Unfortunately, it is not yet clear which constant needs to be set
>>> when the transformation needs to be done, I will still study in
>>> detail. (the graph for all this is presented in graph1.svg
>
> I finished comparing the performance of queries with converted or
> expressions and the original ones and found that about 500 "OR"
> expressions have significantly noticeable degradation of execution
> time, both using the index and without it (you can look at
> time_comsuption_with_indexes.png and
> time_comsuption_without_indexes.html )
>
> The test was performed on the same benchmark database generated by 2
> billion values.
>
> I corrected this constant in the patch.
>
--
Regards,
Alena Rybakina
Postgres Professional

On 6/7/2023 03:06, Alena Rybakina wrote:
>> I corrected this constant in the patch.
The patch don't apply cleanly: it contains some trailing spaces.

Also, quick glance into the code shows some weak points;
1. transformBoolExprOr should have input type BoolExpr.
2. You can avoid the switch operator at the beginning of the function,
because you only need one option.
3. Stale comments: RestrictIinfos definitely not exists at this point.
4. I don't know, you really need to copy the expr or not, but it is
better to do as late, as possible.
5. You assume, that leftop is non-constant and rightop - constant. Why?
6.I doubt about equivalence operator. Someone can invent a custom '='
operator with another semantics, than usual. May be better to check
mergejoinability?
7. I don't know how to confidently identify constant expressions at this
level. So, I guess, You can only merge here expressions like
"F(X)=Const", not an 'F(X)=ConstExpression'.

See delta.diff with mentioned changes in attachment.

--
regards,
Andrey Lepikhov
Postgres Professional

On 6/7/2023 03:06, Alena Rybakina wrote:
>> The test was performed on the same benchmark database generated by 2
>> billion values.
>>
>> I corrected this constant in the patch.
In attempt to resolve some issues had mentioned in my previous letter I
used op_mergejoinable to detect mergejoinability of a clause.
Constant side of the expression is detected by call of
eval_const_expressions() and check each side on the Const type of node.

See 'diff to diff' in attachment.

--
regards,
Andrey Lepikhov
Postgres Professional

Hi! Thank you for your detailed review, your changes have greatly helped
to improve this patch.

On 06.07.2023 13:20, Andrey Lepikhov wrote:
> On 6/7/2023 03:06, Alena Rybakina wrote:
>>> I corrected this constant in the patch.
> The patch don't apply cleanly: it contains some trailing spaces.
I fixed it.
>
> Also, quick glance into the code shows some weak points;
> 1. transformBoolExprOr should have input type BoolExpr.
Agreed.
> 2. You can avoid the switch operator at the beginning of the function,
> because you only need one option.
Agreed.
> 3. Stale comments: RestrictIinfos definitely not exists at this point.
Yes, unfortunately, I missed this from the previous version when I tried
to perform such a transformation at the index creation stage.
> 4. I don't know, you really need to copy the expr or not, but it is
> better to do as late, as possible.
Yes, I agree with you, copying "expr" is not necessary in this patch
> 5. You assume, that leftop is non-constant and rightop - constant. Why?
Agreed, It was too presumptuous on my part and I agree with your changes.
> 6.I doubt about equivalence operator. Someone can invent a custom '='
> operator with another semantics, than usual. May be better to check
> mergejoinability?
Yes, I agree with you, and I haven't thought about it before. But I
haven't found any functions to arrange this in PostgreSQL, but using
mergejoinability turns out to be more beautiful here.
> 7. I don't know how to confidently identify constant expressions at
> this level. So, I guess, You can only merge here expressions like
> "F(X)=Const", not an 'F(X)=ConstExpression'.
I see, you can find solution for this case, thank you for this, and I
think it's reliable enough.

On 07.07.2023 05:43, Andrey Lepikhov wrote:
> On 6/7/2023 03:06, Alena Rybakina wrote:
>>> The test was performed on the same benchmark database generated by 2
>>> billion values.
>>>
>>> I corrected this constant in the patch.
> In attempt to resolve some issues had mentioned in my previous letter
> I used op_mergejoinable to detect mergejoinability of a clause.
> Constant side of the expression is detected by call of
> eval_const_expressions() and check each side on the Const type of node.
>
> See 'diff to diff' in attachment.

I notices you remove condition for checking equal operation.

strcmp(strVal(linitial((arg)->name)), "=") == 0

Firstly, it is noticed me not correct, but a simple example convinced me
otherwise:

postgres=# explain analyze select x from a where x=1 or x>5 or x<3 or x=2;
                                               QUERY PLAN
--------------------------------------------------------------------------------------------------------
 Seq Scan on a  (cost=0.00..2291.00 rows=97899 width=4) (actual
time=0.038..104.168 rows=99000 loops=1)
   Filter: ((x > '5'::numeric) OR (x < '3'::numeric) OR (x = ANY
('{1,2}'::numeric[])))
   Rows Removed by Filter: 1000
 Planning Time: 9.938 ms
 Execution Time: 113.457 ms
(5 rows)

It surprises me that such check I can write such similar way:

eval_const_expressions(NULL, orqual).

Yes, I see we can remove this code:

bare_orarg = transformExprRecurse(pstate, (Node *)arg);
bare_orarg = coerce_to_boolean(pstate, bare_orarg, "OR");

because we will provide similar manipulation in this:

foreach(l, gentry->consts)
{
      Node       *rexpr = (Node *) lfirst(l);

      rexpr = coerce_to_common_type(pstate, rexpr,
                                                scalar_type,
                                                "IN");
     aexprs = lappend(aexprs, rexpr);
}

--
Regards,
Alena Rybakina
Postgres Professional

On 7/7/2023 15:20, Alena Rybakina wrote:
>
> because we will provide similar manipulation in this:
>
> foreach(l, gentry->consts)
> {
>       Node       *rexpr = (Node *) lfirst(l);
>
>       rexpr = coerce_to_common_type(pstate, rexpr,
>                                                 scalar_type,
>                                                 "IN");
>      aexprs = lappend(aexprs, rexpr);
> }
I'm not sure that it should be replaced.
In attachment - a bit more corrections to the patch.
The most important change - or_list contains already transformed
expression subtree. So, I think we don't need to free it at all.

--
regards,
Andrey Lepikhov
Postgres Professional

I agreed with the changes. Thank you for your work.

I updated patch and added you to the authors.

I specified Ranier Vilela as a reviewer.

On 10.07.2023 06:12, Andrey Lepikhov wrote:
> On 7/7/2023 15:20, Alena Rybakina wrote:
>>
>> because we will provide similar manipulation in this:
>>
>> foreach(l, gentry->consts)
>> {
>>        Node       *rexpr = (Node *) lfirst(l);
>>
>>        rexpr = coerce_to_common_type(pstate, rexpr,
>>                                                  scalar_type,
>>                                                  "IN");
>>       aexprs = lappend(aexprs, rexpr);
>> }
> I'm not sure that it should be replaced.
> In attachment - a bit more corrections to the patch.
> The most important change - or_list contains already transformed
> expression subtree. So, I think we don't need to free it at all.
>
--
Regards,
Alena Rybakina
Postgres Professional

Hi Alena,

Em seg., 10 de jul. de 2023 às 05:38, Alena Rybakina <
lena(dot)ribackina(at)yandex(dot)ru> escreveu:

> I agreed with the changes. Thank you for your work.
>
> I updated patch and added you to the authors.
>
> I specified Ranier Vilela as a reviewer.
>
Is a good habit when post a new version of the patch, name it v1, v2,
v3,etc.
Makes it easy to follow development and references on the thread.

Regarding the last patch.
1. I think that variable const_is_left is not necessary.
You can stick with:
+ if (IsA(get_leftop(orqual), Const))
+ nconst_expr =get_rightop(orqual);
+ const_expr = get_leftop(orqual) ;
+ else if (IsA(get_rightop(orqual), Const))
+ nconst_expr =get_leftop(orqual);
+ const_expr = get_rightop(orqual) ;
+ else
+ {
+ or_list = lappend(or_list, orqual);
+ continue;
+ }

2. Test scalar_type != RECORDOID is more cheaper,
mainly if OidIsValid were a function, we knows that is a macro.
+ if (scalar_type != RECORDOID && OidIsValid(scalar_type))

3. Sorry about wrong tip about array_type, but if really necessary,
better use it.
+ newa->element_typeid = scalar_type;
+ newa->array_typeid = array_type;

4. Is a good habit, call free last, to avoid somebody accidentally using it.
+ or_list = lappend(or_list, gentry->expr);
+ list_free(gentry->consts);
+ continue;

5. list_make1(makeString((char *) "=")
Is an invariant?
We can store in a variable and keep out the loop?

Keep up the good work.

best regards,
Ranier Vilela

Em seg., 10 de jul. de 2023 às 09:03, Ranier Vilela <ranier(dot)vf(at)gmail(dot)com>
escreveu:

> Hi Alena,
>
> Em seg., 10 de jul. de 2023 às 05:38, Alena Rybakina <
> lena(dot)ribackina(at)yandex(dot)ru> escreveu:
>
>> I agreed with the changes. Thank you for your work.
>>
>> I updated patch and added you to the authors.
>>
>> I specified Ranier Vilela as a reviewer.
>>
> Is a good habit when post a new version of the patch, name it v1, v2,
> v3,etc.
> Makes it easy to follow development and references on the thread.
>
> Regarding the last patch.
> 1. I think that variable const_is_left is not necessary.
> You can stick with:
> + if (IsA(get_leftop(orqual), Const))
> + nconst_expr =get_rightop(orqual);
> + const_expr = get_leftop(orqual) ;
> + else if (IsA(get_rightop(orqual), Const))
> + nconst_expr =get_leftop(orqual);
> + const_expr = get_rightop(orqual) ;
> + else
> + {
> + or_list = lappend(or_list, orqual);
> + continue;
> + }
>
> 2. Test scalar_type != RECORDOID is more cheaper,
> mainly if OidIsValid were a function, we knows that is a macro.
> + if (scalar_type != RECORDOID && OidIsValid(scalar_type))
>
> 3. Sorry about wrong tip about array_type, but if really necessary,
> better use it.
> + newa->element_typeid = scalar_type;
> + newa->array_typeid = array_type;
>
> 4. Is a good habit, call free last, to avoid somebody accidentally using
> it.
> + or_list = lappend(or_list, gentry->expr);
> + list_free(gentry->consts);
> + continue;
>
> 5. list_make1(makeString((char *) "=")
> Is an invariant?
>
Please nevermind 5. Is not invariant.

regards,
Ranier Vilela

On 10/7/2023 15:38, Alena Rybakina wrote:
> I agreed with the changes. Thank you for your work.
>
> I updated patch and added you to the authors.
>
> I specified Ranier Vilela as a reviewer.
This patch looks much better than earlier. But it definitely needs some
covering with tests. As a first simple approximation, here you can see
the result of regression tests, where the transformation limit is set to
0. See in the attachment some test changes induced by these diffs.

Also, I see some impact of the transformation to other queries:
create_view.out:
(NOT x > z) ----> (x <= z)
inherit.out:
(((a)::text = 'ab'::text) OR ((a)::text = ANY ('{NULL,cd}'::text[])))
to
(((a)::text = ANY ('{NULL,cd}'::text[])) OR ((a)::text = 'ab'::text))

Transformations, mentioned above, are correct, of course. But it can be
a sign of possible unstable behavior.

--
regards,
Andrey Lepikhov
Postgres Professional

Hi!

On 10.07.2023 15:15, Ranier Vilela wrote:
> Em seg., 10 de jul. de 2023 às 09:03, Ranier Vilela
> <ranier(dot)vf(at)gmail(dot)com> escreveu:
>
> Hi Alena,
>
> Em seg., 10 de jul. de 2023 às 05:38, Alena Rybakina
> <lena(dot)ribackina(at)yandex(dot)ru> escreveu:
>
> I agreed with the changes. Thank you for your work.
>
> I updated patch and added you to the authors.
>
> I specified Ranier Vilela as a reviewer.
>
> Is a good habit when post a new version of the patch, name it v1,
> v2, v3,etc.
> Makes it easy to follow development and references on the thread.
>
Sorry, I fixed it.
>
> Regarding the last patch.
> 1. I think that variable const_is_left is not necessary.
> You can stick with:
> + if (IsA(get_leftop(orqual), Const))
> + nconst_expr =get_rightop(orqual);
> + const_expr = get_leftop(orqual) ;
> + else if (IsA(get_rightop(orqual), Const))
> + nconst_expr =get_leftop(orqual);
> + const_expr = get_rightop(orqual) ;
> + else
> + {
> + or_list = lappend(or_list, orqual);
> + continue;
> + }
>
Agreed.
>
>
> 2. Test scalar_type != RECORDOID is more cheaper,
> mainly if OidIsValid were a function, we knows that is a macro.
> + if (scalar_type != RECORDOID && OidIsValid(scalar_type))
>
Is it safe? Maybe we should first make sure that it can be checked on
RECORDOID at all?
>
> 3. Sorry about wrong tip about array_type, but if really necessary,
> better use it.
> + newa->element_typeid = scalar_type;
> + newa->array_typeid = array_type;
>
Agreed.
>
>
> 4. Is a good habit, call free last, to avoid somebody accidentally
> using it.
> + or_list = lappend(or_list, gentry->expr);
> + list_free(gentry->consts);
> + continue;
>
No, this is not necessary, because we add the original expression in
these places to the resulting list and later
we will not use the list of constants for this group at all, otherwise
it would be an error.

--
Regards,
Alena Rybakina
Postgres Professional

Em ter., 11 de jul. de 2023 às 09:29, Alena Rybakina <
lena(dot)ribackina(at)yandex(dot)ru> escreveu:

> Hi!
> On 10.07.2023 15:15, Ranier Vilela wrote:
>
> Em seg., 10 de jul. de 2023 às 09:03, Ranier Vilela <ranier(dot)vf(at)gmail(dot)com>
> escreveu:
>
>> Hi Alena,
>>
>> Em seg., 10 de jul. de 2023 às 05:38, Alena Rybakina <
>> lena(dot)ribackina(at)yandex(dot)ru> escreveu:
>>
>>> I agreed with the changes. Thank you for your work.
>>>
>>> I updated patch and added you to the authors.
>>>
>>> I specified Ranier Vilela as a reviewer.
>>>
>> Is a good habit when post a new version of the patch, name it v1, v2,
>> v3,etc.
>> Makes it easy to follow development and references on the thread.
>>
>> Sorry, I fixed it.
>
> Regarding the last patch.
>> 1. I think that variable const_is_left is not necessary.
>> You can stick with:
>> + if (IsA(get_leftop(orqual), Const))
>> + nconst_expr =get_rightop(orqual);
>> + const_expr = get_leftop(orqual) ;
>> + else if (IsA(get_rightop(orqual), Const))
>> + nconst_expr =get_leftop(orqual);
>> + const_expr = get_rightop(orqual) ;
>> + else
>> + {
>> + or_list = lappend(or_list, orqual);
>> + continue;
>> + }
>>
> Agreed.
>
You missed in removing the declaration
- bool const_is_left = true;
.

>
>> 2. Test scalar_type != RECORDOID is more cheaper,
>> mainly if OidIsValid were a function, we knows that is a macro.
>> + if (scalar_type != RECORDOID && OidIsValid(scalar_type))
>>
>> Is it safe? Maybe we should first make sure that it can be checked on
> RECORDOID at all?
>
Yes it's safe, because && connector.
But you can leave as is in v5.

best regards,
Ranier Vilela

On 11.07.2023 16:29, Ranier Vilela wrote:
> Em ter., 11 de jul. de 2023 às 09:29, Alena Rybakina
> <lena(dot)ribackina(at)yandex(dot)ru> escreveu:
>
> Hi!
>
> On 10.07.2023 15:15, Ranier Vilela wrote:
>> Em seg., 10 de jul. de 2023 às 09:03, Ranier Vilela
>> <ranier(dot)vf(at)gmail(dot)com> escreveu:
>>
>> Hi Alena,
>>
>> Em seg., 10 de jul. de 2023 às 05:38, Alena Rybakina
>> <lena(dot)ribackina(at)yandex(dot)ru> escreveu:
>>
>> I agreed with the changes. Thank you for your work.
>>
>> I updated patch and added you to the authors.
>>
>> I specified Ranier Vilela as a reviewer.
>>
>> Is a good habit when post a new version of the patch, name it
>> v1, v2, v3,etc.
>> Makes it easy to follow development and references on the thread.
>>
> Sorry, I fixed it.
>>
>> Regarding the last patch.
>> 1. I think that variable const_is_left is not necessary.
>> You can stick with:
>> + if (IsA(get_leftop(orqual), Const))
>> + nconst_expr =get_rightop(orqual);
>> + const_expr = get_leftop(orqual) ;
>> + else if (IsA(get_rightop(orqual), Const))
>> + nconst_expr =get_leftop(orqual);
>> + const_expr = get_rightop(orqual) ;
>> + else
>> + {
>> + or_list = lappend(or_list, orqual);
>> + continue;
>> + }
>>
> Agreed.
>
> You missed in removing the declaration
> - bool const_is_left = true;
Yes, thank you. I fixed it.
> .
>
>>
>> 2. Test scalar_type != RECORDOID is more cheaper,
>> mainly if OidIsValid were a function, we knows that is a macro.
>> + if (scalar_type != RECORDOID && OidIsValid(scalar_type))
>>
> Is it safe? Maybe we should first make sure that it can be checked
> on RECORDOID at all?
>
> Yes it's safe, because && connector.
> But you can leave as is in v5.
>
Added it.

--
Regards,
Alena Rybakina
Postgres Professional

Hi!

On 11.07.2023 11:47, Andrey Lepikhov wrote:
> This patch looks much better than earlier. But it definitely needs
> some covering with tests. As a first simple approximation, here you
> can see the result of regression tests, where the transformation limit
> is set to 0. See in the attachment some test changes induced by these
> diffs.
>
Yes, I think so too. I also added some tests. I have attached an
additional diff-5.diff where you can see the changes.
> Also, I see some impact of the transformation to other queries:
> create_view.out:
> (NOT x > z) ----> (x <= z)
> inherit.out:
> (((a)::text = 'ab'::text) OR ((a)::text = ANY ('{NULL,cd}'::text[])))
> to -
> (((a)::text = ANY ('{NULL,cd}'::text[])) OR ((a)::text = 'ab'::text))
>
> Transformations, mentioned above, are correct, of course. But it can
> be a sign of possible unstable behavior.
>
I think it can be made more stable if we always add the existing
transformed expressions first, and then the original ones, or vice versa. T

o do this, we will need two more lists, I think, and then we can combine
them, where the elements of the second will be written to the end of the
first.

But I suppose that this may not be the only unstable behavior - I
suppose we need sorting result elements on the left side, what do you think?

--
Regards,
Alena Rybakina
Postgres Professional

Hi, all!

I sent a patch to commitfest and noticed that the authors and the
reviewer were incorrectly marked.

Sorry about that. I fixed it and sent the current version of the patch.

--
Regards,
Alena Rybakina
Postgres Professional

On Thu, Jun 29, 2023 at 2:32 AM Alena Rybakina <lena(dot)ribackina(at)yandex(dot)ru> wrote:
> Hi! I'm sorry I didn't answer you right away, I was too busy with work.

Same for me, this time. I was busy working on my patch, which I
finally posted yesterday.

> To be honest, I didn't think about the fact that my optimization can help eliminate duplicates before reading the data before.

I'm not surprised that you didn't specifically think of that, because
it's very subtle.

> I am still only in the process of familiarizing myself with the thread [1] (reference from your letter), but I have already seen that there are problems related, for example, to when "or" expressions refer to the parent element.

I didn't intend to imply that you might have the same problem here. I
just meant that OR optimizations can have problems with duplicate
elimination, in general. I suspect that your patch doesn't have that
problem, because you are performing a transformation of one kind of OR
into another kind of OR.

> I think, I would face the similar problems if I complicate the current code, for example, so that not only or expressions standing on the same level are written in any, but also on different ones without violating the logic of the priority of executing operators.

I can't say that I am particularly experienced in this general area --
I have never tried to formally reason about how two different
statements are equivalent. It just hasn't been something that I've
needed to have a totally rigorous understanding of up until now. But
my recent patch changes that. Now I need to study this area to make
sure that I have a truly rigorous understanding.

Jeff Davis suggested that I read "Logic and Databases", by C.J. Date.
So now I have some homework to do.

> Unfortunately, when I tried to make a transformation at the stage of index formation, I encountered too incorrect an assessment of the selectivity of relation, which affected the incorrect calculation of the cost and cardinality.

It's not surprising that a weird shift in the plan chosen by the
optimizer is seen with some random test case, as a result of this
added transformation. Even changes that are 100% strictly better (e.g.
changes in a selectivity estimation function that is somehow
guaranteed to be more accurate in all cases) might do that. Here is a
recent example of that with another patch, involving a bitmap OR:

https://postgr.es/m/CAH2-WznCDK9n2tZ6j_-iLN563_ePuC3NzP6VSVTL6jHzs6nRuQ@mail.gmail.com

This example was *not* a regression, if you go by conventional
measures. It was merely a less robust plan than the bitmap OR plan,
because it didn't pass down both columns as index quals.

BTW, there are various restrictions on the sort order of SAOPs that
you might want to try to familiarize yourself with. I describe them
(perhaps not very clearly) here:

https://postgr.es/m/CAH2-Wz=ksvN_sjcnD1+Bt-WtifRA5ok48aDYnq3pkKhxgMQpcw@mail.gmail.com

Currently, the optimizer doesn't recognize multi-column indexes with
SAOPs on every column as having a valid sort order, except on the
first column. It seems possible that that has consequences for your
patch. (I'm really only guessing, though; don't trust anything that I
say about the optimizer too much.)

--
Peter Geoghegan

Hi!

On 26.07.2023 02:47, Peter Geoghegan wrote:
> On Thu, Jun 29, 2023 at 2:32 AM Alena Rybakina <lena(dot)ribackina(at)yandex(dot)ru> wrote:
>> Hi! I'm sorry I didn't answer you right away, I was too busy with work.
> Same for me, this time. I was busy working on my patch, which I
> finally posted yesterday.
I'm glad to hear it, I've seen your thread ("Optimizing nbtree
ScalarArrayOp execution, allowing multi-column ordered scans, skip
scan"), but, unfortunately, I didn't have enough time to read it. I'll
review it soon!
>> To be honest, I didn't think about the fact that my optimization can help eliminate duplicates before reading the data before.
> I'm not surprised that you didn't specifically think of that, because
> it's very subtle.
>
>> I am still only in the process of familiarizing myself with the thread [1] (reference from your letter), but I have already seen that there are problems related, for example, to when "or" expressions refer to the parent element.
> I didn't intend to imply that you might have the same problem here. I
> just meant that OR optimizations can have problems with duplicate
> elimination, in general. I suspect that your patch doesn't have that
> problem, because you are performing a transformation of one kind of OR
> into another kind of OR.

Yes, you are right, but I studied this topic and two other sources to
accumulate my knowledge. It was an exciting experience for me)

I was especially inspired after studying the interview with Goetz Graf
[2], his life experience is the most inspiring, and from this article I
was able to get a broad understanding of the field of databases:
current problems, future development, how it works... Thank you for the
recommendation.

I discovered for myself that the idea described in the article [1] is
similar to the idea of representing grouped data in OLAP cubes, and
also, if I saw correctly, an algorithm like depth-first search is used
there, but for indexes.

I think it really helps to speed up the search with similar deep
filtering compared to cluster indexes, but do we have cases where we
don't use this algorithm because it takes longer than an usual index?
I thought about the situation with wide indexes (with a lot of multiple
columns) and having a lot of filtering predicates for them.
But I'm not sure about this, so it seems to me that this is a problem of
improper use of indexes rather.
>> I think, I would face the similar problems if I complicate the current code, for example, so that not only or expressions standing on the same level are written in any, but also on different ones without violating the logic of the priority of executing operators.
> I can't say that I am particularly experienced in this general area --
> I have never tried to formally reason about how two different
> statements are equivalent. It just hasn't been something that I've
> needed to have a totally rigorous understanding of up until now. But
> my recent patch changes that. Now I need to study this area to make
> sure that I have a truly rigorous understanding.
>
> Jeff Davis suggested that I read "Logic and Databases", by C.J. Date.
> So now I have some homework to do.
I'll read this book too. Maybe I can finish work with the knowledge I
got from there. Thank you for sharing!
>> Unfortunately, when I tried to make a transformation at the stage of index formation, I encountered too incorrect an assessment of the selectivity of relation, which affected the incorrect calculation of the cost and cardinality.
> It's not surprising that a weird shift in the plan chosen by the
> optimizer is seen with some random test case, as a result of this
> added transformation. Even changes that are 100% strictly better (e.g.
> changes in a selectivity estimation function that is somehow
> guaranteed to be more accurate in all cases) might do that. Here is a
> recent example of that with another patch, involving a bitmap OR:
>
> https://postgr.es/m/CAH2-WznCDK9n2tZ6j_-iLN563_ePuC3NzP6VSVTL6jHzs6nRuQ@mail.gmail.com
At first, this surprised me very much. It took time to find a suitable
place to implement the transformation.

I have looked through this thread many times, I will study it in more
detail .
> This example was *not* a regression, if you go by conventional
> measures. It was merely a less robust plan than the bitmap OR plan,
> because it didn't pass down both columns as index quals.
>
> BTW, there are various restrictions on the sort order of SAOPs that
> you might want to try to familiarize yourself with. I describe them
> (perhaps not very clearly) here:
>
> https://postgr.es/m/CAH2-Wz=ksvN_sjcnD1+Bt-WtifRA5ok48aDYnq3pkKhxgMQpcw@mail.gmail.com
Thank you! Yes, I'll study it too)
> Currently, the optimizer doesn't recognize multi-column indexes with
> SAOPs on every column as having a valid sort order, except on the
> first column. It seems possible that that has consequences for your
> patch. (I'm really only guessing, though; don't trust anything that I
> say about the optimizer too much.)
>
Honestly, I couldn't understand your concerns very well, could you
describe it in more detail?

1. https://vldb.org/conf/1995/P710.PDF

2.
https://sigmodrecord.org/publications/sigmodRecord/2009/pdfs/05_Profiles_Graefe.pdf

--
Regards,
Alena Rybakina
Postgres Professional

On Wed, Jul 26, 2023 at 6:30 PM Alena Rybakina <lena(dot)ribackina(at)yandex(dot)ru> wrote:
> > I didn't intend to imply that you might have the same problem here. I
> > just meant that OR optimizations can have problems with duplicate
> > elimination, in general. I suspect that your patch doesn't have that
> > problem, because you are performing a transformation of one kind of OR
> > into another kind of OR.
>
> Yes, you are right, but I studied this topic and two other sources to
> accumulate my knowledge. It was an exciting experience for me)

Cool! Yeah, a lot of the value with these sorts of things comes from
the way that they can interact with each other. This is hard to
describe exactly, but still important.

> I was especially inspired after studying the interview with Goetz Graf
> [2], his life experience is the most inspiring, and from this article I
> was able to get a broad understanding of the field of databases:
> current problems, future development, how it works... Thank you for the
> recommendation.

I also think that his perspective is very interesting.

> I think it really helps to speed up the search with similar deep
> filtering compared to cluster indexes, but do we have cases where we
> don't use this algorithm because it takes longer than an usual index?
> I thought about the situation with wide indexes (with a lot of multiple
> columns) and having a lot of filtering predicates for them.

I think that it should be possible for the optimizer to only use
multi-column SAOP index paths when there is at least likely to be some
small advantage -- that's definitely my goal. Importantly, we may not
really need to accurately model the costs where the new approach turns
out to be much faster. The only essential thing is that we avoid cases
where the new approach is much slower than the old approach. Which is
possible (in at least some cases) by making the runtime behavior
adaptive.

The best decision that the planner can make may be no decision at all.
Better to wait until runtime where at all possible, since that gives
us the latest and most accurate picture of things.

> But I'm not sure about this, so it seems to me that this is a problem of
> improper use of indexes rather.

It's hard to say how true that is.

Certainly, workloads similar to the TPC-DS benchmark kinda need
something like MDAM. It's just not practical to have enough indexes to
support every possible query -- the benchmark is deliberately designed
to have unpredictable, hard-to-optimize access paths. It seems to
require having fewer, more general indexes that can support
multi-dimensional access reasonably efficiently.

Of course, with OLTP it's much more likely that the workload will have
predictable access patterns. That makes having exactly the right
indexes much more practical. So maybe you're right there. But, I still
see a lot of value in a design that is as forgiving as possible. Users
really like that kind of thing in my experience.

> > Currently, the optimizer doesn't recognize multi-column indexes with
> > SAOPs on every column as having a valid sort order, except on the
> > first column. It seems possible that that has consequences for your
> > patch. (I'm really only guessing, though; don't trust anything that I
> > say about the optimizer too much.)
> >
> Honestly, I couldn't understand your concerns very well, could you
> describe it in more detail?

Well, I'm not sure if there is any possible scenario where the
transformation from your patch makes it possible to go from an access
path that has a valid sort order (usually because there is an
underlying index scan) into an access path that doesn't. In fact, the
opposite situation seems more likely (which is good news) --
especially if you assume that my own patch is also present.

Going from a bitmap OR (which cannot return sorted output) to a
multi-column SAOP index scan (which now can) may have significant
value in some specific circumstances. Most obviously, it's really
useful when it enables us to feed tuples into a GroupAggregate without
a separate sort step, and without a hash aggregate (that's why I see
value in combining your patch with my own patch). You just need to be
careful about allowing the opposite situation to take place.

More generally, there is a need to think about strange second order
effects. We want to be open to useful second order effects that make
query execution much faster in some specific context, while avoiding
harmful second order effects. Intuitively, I think that it should be
possible to do this with the transformations performed by your patch.

In other words, "helpful serendipity" is an important advantage, while
"harmful anti-serendipity" is what we really want to avoid. Ideally by
making the harmful cases impossible "by construction".

--
Peter Geoghegan

Hi!

>> I think it really helps to speed up the search with similar deep
>> filtering compared to cluster indexes, but do we have cases where we
>> don't use this algorithm because it takes longer than an usual index?
>> I thought about the situation with wide indexes (with a lot of multiple
>> columns) and having a lot of filtering predicates for them.
> I think that it should be possible for the optimizer to only use
> multi-column SAOP index paths when there is at least likely to be some
> small advantage -- that's definitely my goal. Importantly, we may not
> really need to accurately model the costs where the new approach turns
> out to be much faster. The only essential thing is that we avoid cases
> where the new approach is much slower than the old approach. Which is
> possible (in at least some cases) by making the runtime behavior
> adaptive.
>
> The best decision that the planner can make may be no decision at all.
> Better to wait until runtime where at all possible, since that gives
> us the latest and most accurate picture of things.
>
>> But I'm not sure about this, so it seems to me that this is a problem of
>> improper use of indexes rather.
> It's hard to say how true that is.
>
> Certainly, workloads similar to the TPC-DS benchmark kinda need
> something like MDAM. It's just not practical to have enough indexes to
> support every possible query -- the benchmark is deliberately designed
> to have unpredictable, hard-to-optimize access paths. It seems to
> require having fewer, more general indexes that can support
> multi-dimensional access reasonably efficiently.
>
> Of course, with OLTP it's much more likely that the workload will have
> predictable access patterns. That makes having exactly the right
> indexes much more practical. So maybe you're right there. But, I still
> see a lot of value in a design that is as forgiving as possible. Users
> really like that kind of thing in my experience.
I tend to agree with you, but a runtime estimate cannot give us an
accurate picture when using indexes correctly or
any other optimizations due to the unstable state of the environment in
which the query is executed.
I believe that a more complex analysis is needed here.
>>> Currently, the optimizer doesn't recognize multi-column indexes with
>>> SAOPs on every column as having a valid sort order, except on the
>>> first column. It seems possible that that has consequences for your
>>> patch. (I'm really only guessing, though; don't trust anything that I
>>> say about the optimizer too much.)
>>>
>> Honestly, I couldn't understand your concerns very well, could you
>> describe it in more detail?
> Well, I'm not sure if there is any possible scenario where the
> transformation from your patch makes it possible to go from an access
> path that has a valid sort order (usually because there is an
> underlying index scan) into an access path that doesn't. In fact, the
> opposite situation seems more likely (which is good news) --
> especially if you assume that my own patch is also present.
>
> Going from a bitmap OR (which cannot return sorted output) to a
> multi-column SAOP index scan (which now can) may have significant
> value in some specific circumstances. Most obviously, it's really
> useful when it enables us to feed tuples into a GroupAggregate without
> a separate sort step, and without a hash aggregate (that's why I see
> value in combining your patch with my own patch). You just need to be
> careful about allowing the opposite situation to take place.
>
> More generally, there is a need to think about strange second order
> effects. We want to be open to useful second order effects that make
> query execution much faster in some specific context, while avoiding
> harmful second order effects. Intuitively, I think that it should be
> possible to do this with the transformations performed by your patch.
>
> In other words, "helpful serendipity" is an important advantage, while
> "harmful anti-serendipity" is what we really want to avoid. Ideally by
> making the harmful cases impossible "by construction".
>
I noticed only one thing there: when we have unsorted array values in
SOAP, the query takes longer than
when it has a sorted array. I'll double-check it just in case and write
about the results later.

I am also testing some experience with multi-column indexes using SAOPs.

--
Regards,
Alena Rybakina
Postgres Professional

On Mon, Jul 31, 2023 at 9:38 AM Alena Rybakina <lena(dot)ribackina(at)yandex(dot)ru> wrote:
> I noticed only one thing there: when we have unsorted array values in
> SOAP, the query takes longer than
> when it has a sorted array. I'll double-check it just in case and write
> about the results later.

I would expect the B-Tree preprocessing by _bt_preprocess_array_keys()
to be very slightly faster when the query is written with presorted,
duplicate-free constants. Sorting is faster when you don't really have
to sort. However, I would not expect the effect to be significant
enough to matter, except perhaps in very extreme cases.
Although...some of the cases you care about are very extreme cases.

> I am also testing some experience with multi-column indexes using SAOPs.

Have you thought about a similar transformation for when the row
constructor syntax happens to have been used?

Consider a query like the following, against a table with a composite
index on (a, b):

select * from multi_test where ( a, b ) in (( 1, 1 ), ( 2, 1 ));

This query will get a BitmapOr based plan that's similar to the plans
that OR-based queries affected by your transformation patch get today,
on HEAD. However, this equivalent spelling has the potential to be
significantly faster:

select * from multi_test where a = any('{1,2}') and b = 1;

(Of course, this is more likely to be true with my nbtree SAOP patch in place.)

Note that we currently won't use RowCompareExpr in many simple cases
where the row constructor syntax has been used. For example, a query
like this:

select * from multi_test where ( a, b ) = (( 2, 1 ));

This case already involves a transformation that is roughly comparable
to the one you're working on now. We'll remove the RowCompareExpr
during parsing. It'll be as if my example row constructor equality
query was written this way instead:

select * from multi_test where a = 2 and b = 1;

This can be surprisingly important, when combined with other things,
in more realistic examples.

The nbtree code has special knowledge of RowCompareExpr that makes the
rules for comparing index tuples different to those from other kinds
of index scans. However, due to the RowCompareExpr transformation
process I just described, we don't need to rely on that specialized
nbtree code when the row constructor syntax is used with a simple
equality clause -- which is what makes the normalization process have
real value. If the nbtree code cannot see RowCompareExpr index quals
then it cannot have this problem in the first place. In general it is
useful to "normalize to conjunctive normal form" when it might allow
scan key preprocessing in the nbtree code to come up with a much
faster approach to executing the scan.

It's easier to understand what I mean by showing a simple example. The
nbtree preprocessing code is smart enough to recognize that the
following query doesn't really need to do any work, due to having
quals that it recognizes as contradictory (it can set so->qual_okay to
false for unsatisfiable quals):

select * from multi_test where ( a, b ) = (( 2, 1 )) and a = -1;

However, it is not smart enough to perform the same trick if we change
one small detail with the query:

select * from multi_test where ( a, b ) >= (( 2, 1 )) and a = -1;

Ideally, the optimizer would canonicalize/normalize everything in a
way that made all of the nbtree preprocessing optimizations work just
as well, without introducing any new special cases. Obviously, there
is no reason why we can't perform the same trick with the second
variant. (Note also that the nbtree preprocessing code can be smart
about redundant quals, not just contradictory quals, so it matters
more than it may appear from this simple, unrealistic example of
mine.)

While these similar RowCompareExpr transformations are at least
somewhat important, that's not really why I bring them up now. I am
pointing them out now because I think that it might help you to
develop a more complete mental model of these transformations.
Ideally, your initial approach will generalize to other situations
later on. So it's worth considering the relationship between this
existing RowCompareExpr transformation, and the one that you're
working on currently. Plus other, future transformations.

This example might also give you some appreciation of why my SAOP
patch is confused about when we need to do normalization/safety
checks. Some things seem necessary when generating index paths in the
optimizer. Other things seem necessary during preprocessing, in the
nbtree code, at the start of the index scan. Unfortunately, it's not
obvious to me where the right place is to deal with each aspect of
setting up multi-column SAOP index quals. My mental model is very
incomplete.

--
Peter Geoghegan

Peter, I'm very glad to hear that you're researching this!

Will this include skip-scan optimizations for OR or IN predicates, or when the number of distinct values in a leading non-constant index column(s) is sufficiently small? e.g. suppose there is an ORDER BY b, and WHERE clause predicates (a = 1 AND b = 5) OR (c > 12 AND b BETWEEN 100 AND 200). Then a single index scan on an index with leading column b could visit b = 5, and then the range b from 100:200, and deliver the rows in the order requested. Or if the predicate is (a = 1 AND b = 5) OR (c LIKE 'XYZ' AND b < 12), then you can scan just b < 12. Or if the index is defined on (a, b) and you know that b = 100, and that there are only 4 distinct values of column a, then you could skip each distinct value of a where b = 100, and so on.

If you have an ORDER BY clause and a lower and upper bound on the first column of the ORDER BY list, you have a potential to reduce search effort versus a full index scan, even when that upper and lower bound needs to be derived from a complex predicate.

Of course, if you have an IN list you can either skip to the distinct values listed or scan the entire index, depending on estimated cost.

/Jim F

On 8/1/23, 3:43 PM, "Peter Geoghegan" <pg(at)bowt(dot)ie <mailto:pg(at)bowt(dot)ie>> wrote:

CAUTION: This email originated from outside of the organization. Do not click links or open attachments unless you can confirm the sender and know the content is safe.

On Mon, Jul 31, 2023 at 9:38 AM Alena Rybakina <lena(dot)ribackina(at)yandex(dot)ru <mailto:lena(dot)ribackina(at)yandex(dot)ru>> wrote:
> I noticed only one thing there: when we have unsorted array values in
> SOAP, the query takes longer than
> when it has a sorted array. I'll double-check it just in case and write
> about the results later.

I would expect the B-Tree preprocessing by _bt_preprocess_array_keys()
to be very slightly faster when the query is written with presorted,
duplicate-free constants. Sorting is faster when you don't really have
to sort. However, I would not expect the effect to be significant
enough to matter, except perhaps in very extreme cases.
Although...some of the cases you care about are very extreme cases.

> I am also testing some experience with multi-column indexes using SAOPs.

Have you thought about a similar transformation for when the row
constructor syntax happens to have been used?

Consider a query like the following, against a table with a composite
index on (a, b):

select * from multi_test where ( a, b ) in (( 1, 1 ), ( 2, 1 ));

This query will get a BitmapOr based plan that's similar to the plans
that OR-based queries affected by your transformation patch get today,
on HEAD. However, this equivalent spelling has the potential to be
significantly faster:

select * from multi_test where a = any('{1,2}') and b = 1;

(Of course, this is more likely to be true with my nbtree SAOP patch in place.)

Note that we currently won't use RowCompareExpr in many simple cases
where the row constructor syntax has been used. For example, a query
like this:

select * from multi_test where ( a, b ) = (( 2, 1 ));

This case already involves a transformation that is roughly comparable
to the one you're working on now. We'll remove the RowCompareExpr
during parsing. It'll be as if my example row constructor equality
query was written this way instead:

select * from multi_test where a = 2 and b = 1;

This can be surprisingly important, when combined with other things,
in more realistic examples.

The nbtree code has special knowledge of RowCompareExpr that makes the
rules for comparing index tuples different to those from other kinds
of index scans. However, due to the RowCompareExpr transformation
process I just described, we don't need to rely on that specialized
nbtree code when the row constructor syntax is used with a simple
equality clause -- which is what makes the normalization process have
real value. If the nbtree code cannot see RowCompareExpr index quals
then it cannot have this problem in the first place. In general it is
useful to "normalize to conjunctive normal form" when it might allow
scan key preprocessing in the nbtree code to come up with a much
faster approach to executing the scan.

It's easier to understand what I mean by showing a simple example. The
nbtree preprocessing code is smart enough to recognize that the
following query doesn't really need to do any work, due to having
quals that it recognizes as contradictory (it can set so->qual_okay to
false for unsatisfiable quals):

select * from multi_test where ( a, b ) = (( 2, 1 )) and a = -1;

However, it is not smart enough to perform the same trick if we change
one small detail with the query:

select * from multi_test where ( a, b ) >= (( 2, 1 )) and a = -1;

Ideally, the optimizer would canonicalize/normalize everything in a
way that made all of the nbtree preprocessing optimizations work just
as well, without introducing any new special cases. Obviously, there
is no reason why we can't perform the same trick with the second
variant. (Note also that the nbtree preprocessing code can be smart
about redundant quals, not just contradictory quals, so it matters
more than it may appear from this simple, unrealistic example of
mine.)

While these similar RowCompareExpr transformations are at least
somewhat important, that's not really why I bring them up now. I am
pointing them out now because I think that it might help you to
develop a more complete mental model of these transformations.
Ideally, your initial approach will generalize to other situations
later on. So it's worth considering the relationship between this
existing RowCompareExpr transformation, and the one that you're
working on currently. Plus other, future transformations.

This example might also give you some appreciation of why my SAOP
patch is confused about when we need to do normalization/safety
checks. Some things seem necessary when generating index paths in the
optimizer. Other things seem necessary during preprocessing, in the
nbtree code, at the start of the index scan. Unfortunately, it's not
obvious to me where the right place is to deal with each aspect of
setting up multi-column SAOP index quals. My mental model is very
incomplete.

--
Peter Geoghegan

Jim,

On Tue, Aug 1, 2023 at 1:11 PM Finnerty, Jim <jfinnert(at)amazon(dot)com> wrote:
> Peter, I'm very glad to hear that you're researching this!

Glad to hear it!

> Will this include skip-scan optimizations for OR or IN predicates, or when the number of distinct values in a leading non-constant index column(s) is sufficiently small?

Yes -- though perhaps not in the first iteration.

As I go into on the thread associated with my own patch [1], my
initial goal is to support efficient execution of multiple IN() lists
for multiple columns from the same index, all while preserving index
sort order on output, and avoiding a separate duplicate elimination
step. Some of the most compelling cases for these MDAM techniques
involve GroupAggregates, ORDER BY ... LIMIT, and DISTINCT -- I
understand the importance of making the index scan appear to be a
conventional index scan to the optimizer.

> If you have an ORDER BY clause and a lower and upper bound on the first column of the ORDER BY list, you have a potential to reduce search effort versus a full index scan, even when that upper and lower bound needs to be derived from a complex predicate.

It sounds like your example is an attempt to ascertain whether or not
my design considers the need to convert complicated predicates into
disjuncts that can be executed as if by one single index scan, via CNF
-> DNF transformations/preprocessing. That is certainly the plan, at
least medium term -- I fully expect to be able to combine all of these
techniques together, in ways that continue to work even with very
complicated predicates. Like the really hairy example from the MDAM
paper, or like your example.

There are already some nbtree scan key preprocessing steps a little
like the ones considered by the MDAM paper. These steps eliminate
redundant and contradictory quals -- but they weren't specifically
written with the very general MDAM DNF design requirements in mind.
Plus there are already at least some transformations like the one that
Alena is working on in the patch discussed on this thread -- these
were also not written with MDAM stuff in mind.

A major goal of mine for this project in the short term is to come up
with a very general design. I must reconcile all this stuff, somehow
or other, so that these very complicated cases will work just as well
as simpler and more obvious cases. I really hate special cases.

> Of course, if you have an IN list you can either skip to the distinct values listed or scan the entire index, depending on estimated cost.

Actually, I think that it should be possible to decide on how to skip
dynamically, without needing an up-front decision around skipping from
the optimizer. In other words, the scans can skip using an adaptive
strategy. This is feasible provided I can make the overhead of a
dynamic/adaptive approach negligible. When it turns out that a full
index scan is appropriate, we'll just end up doing it that way at
runtime.

Nothing stops a given scan from needing to do skip a great deal in the
first half of an index, while scanning everything in the second half
of the index. Obviously, a static choice won't do well there, since it
works at the level of the whole scan/index, which seems like the wrong
framing to me. (Of course we'll still need to model skipping stuff in
the planner -- just not so that we can decide between two index paths
that are essentially identical, that should just be one index path.)

[1] https://postgr.es/m/CAH2-Wz=ksvN_sjcnD1+Bt-WtifRA5ok48aDYnq3pkKhxgMQpcw@mail.gmail.com
--
Peter Geoghegan

I fixed an error that caused the current optimization not to work with
prepared queries. I added a test to catch similar cases in the future.
I have attached a patch.

On 01.08.2023 22:42, Peter Geoghegan wrote:
> On Mon, Jul 31, 2023 at 9:38 AM Alena Rybakina <lena(dot)ribackina(at)yandex(dot)ru> wrote:
>> I noticed only one thing there: when we have unsorted array values in
>> SOAP, the query takes longer than
>> when it has a sorted array. I'll double-check it just in case and write
>> about the results later.
> I would expect the B-Tree preprocessing by _bt_preprocess_array_keys()
> to be very slightly faster when the query is written with presorted,
> duplicate-free constants. Sorting is faster when you don't really have
> to sort. However, I would not expect the effect to be significant
> enough to matter, except perhaps in very extreme cases.
> Although...some of the cases you care about are very extreme cases.
I tested an optimization to compare execution time and scheduling with
sorting, shuffling, and reverse sorting constants in the simple case and
I didn't notice any significant changes (compare_sorted.png).
(I used a database with 100 million values generated by pgbench).
>> I am also testing some experience with multi-column indexes using SAOPs.
> Have you thought about a similar transformation for when the row
> constructor syntax happens to have been used?
>
> Consider a query like the following, against a table with a composite
> index on (a, b):
>
> select * from multi_test where ( a, b ) in (( 1, 1 ), ( 2, 1 ));
>
> This query will get a BitmapOr based plan that's similar to the plans
> that OR-based queries affected by your transformation patch get today,
> on HEAD. However, this equivalent spelling has the potential to be
> significantly faster:
>
> select * from multi_test where a = any('{1,2}') and b = 1;
>
> (Of course, this is more likely to be true with my nbtree SAOP patch in place.)
No, I haven't thought about it yet. I studied the example and it would
really be nice to add optimization here. I didn't notice any problems
with its implementation. I also have an obvious example with the "or"
operator, for example
, select * from multi_test, where (a, b ) = ( 1, 1 ) or (a, b ) = ( 2, 1
) ...;

Although I think such a case will be used less often.

Thank you for the example, I think I understand better why our patches
help each other, but I will review your patch again.

I tried another example to see the lack of optimization in the pgbench
database, but I also created an additional index:

create index ind1 on pgbench_accounts(aid,bid);

test_db=# explain analyze select * from pgbench_accounts where (aid,
bid) in ((2,1), (2,2), (2,3), (3,3));
                                                             QUERY PLAN
------------------------------------------------------------------------------------------------------------------------------------
 Bitmap Heap Scan on pgbench_accounts  (cost=17.73..33.66 rows=1
width=97) (actual time=0.125..0.133 rows=1 loops=1)
   Recheck Cond: ((aid = 2) OR (aid = 2) OR (aid = 2) OR (aid = 3))
   Filter: (((aid = 2) AND (bid = 1)) OR ((aid = 2) AND (bid = 2)) OR
((aid = 2) AND (bid = 3)) OR ((aid = 3) AND (bid = 3)))
   Rows Removed by Filter: 1
   Heap Blocks: exact=1
   ->  BitmapOr  (cost=17.73..17.73 rows=4 width=0) (actual
time=0.100..0.102 rows=0 loops=1)
         ->  Bitmap Index Scan on pgbench_accounts_pkey
(cost=0.00..4.43 rows=1 width=0) (actual time=0.036..0.037 rows=1 loops=1)
               Index Cond: (aid = 2)
         ->  Bitmap Index Scan on pgbench_accounts_pkey
(cost=0.00..4.43 rows=1 width=0) (actual time=0.021..0.022 rows=1 loops=1)
               Index Cond: (aid = 2)
         ->  Bitmap Index Scan on pgbench_accounts_pkey
(cost=0.00..4.43 rows=1 width=0) (actual time=0.021..0.021 rows=1 loops=1)
               Index Cond: (aid = 2)
         ->  Bitmap Index Scan on pgbench_accounts_pkey
(cost=0.00..4.43 rows=1 width=0) (actual time=0.019..0.020 rows=1 loops=1)
               Index Cond: (aid = 3)
 Planning Time: 0.625 ms
 Execution Time: 0.227 ms
(16 rows)

I think such optimization would be useful here: aid =2 and bid in (1,2)
or (aid,bid)=((3,3))

> Note that we currently won't use RowCompareExpr in many simple cases
> where the row constructor syntax has been used. For example, a query
> like this:
>
> select * from multi_test where ( a, b ) = (( 2, 1 ));
>
> This case already involves a transformation that is roughly comparable
> to the one you're working on now. We'll remove the RowCompareExpr
> during parsing. It'll be as if my example row constructor equality
> query was written this way instead:
>
> select * from multi_test where a = 2 and b = 1;
>
> This can be surprisingly important, when combined with other things,
> in more realistic examples.
>
> The nbtree code has special knowledge of RowCompareExpr that makes the
> rules for comparing index tuples different to those from other kinds
> of index scans. However, due to the RowCompareExpr transformation
> process I just described, we don't need to rely on that specialized
> nbtree code when the row constructor syntax is used with a simple
> equality clause -- which is what makes the normalization process have
> real value. If the nbtree code cannot see RowCompareExpr index quals
> then it cannot have this problem in the first place. In general it is
> useful to "normalize to conjunctive normal form" when it might allow
> scan key preprocessing in the nbtree code to come up with a much
> faster approach to executing the scan.
>
> It's easier to understand what I mean by showing a simple example. The
> nbtree preprocessing code is smart enough to recognize that the
> following query doesn't really need to do any work, due to having
> quals that it recognizes as contradictory (it can set so->qual_okay to
> false for unsatisfiable quals):
>
> select * from multi_test where ( a, b ) = (( 2, 1 )) and a = -1;
>
> However, it is not smart enough to perform the same trick if we change
> one small detail with the query:
>
> select * from multi_test where ( a, b ) >= (( 2, 1 )) and a = -1;

Yes, I have run the examples and I see it.

((ROW(aid, bid) >= ROW(2, 1)) AND (aid = '-1'::integer))

As I see it, we can implement such a transformation:

'( a, b ) >= (( 2, 1 )) and a = -1'     ->    'aid >= 2 and bid >= 1 and
aid =-1'

It seems to me the most difficult thing is to notice problematic cases
where the transformations are incorrect, but I think it can be implemented.

> Ideally, the optimizer would canonicalize/normalize everything in a
> way that made all of the nbtree preprocessing optimizations work just
> as well, without introducing any new special cases. Obviously, there
> is no reason why we can't perform the same trick with the second
> variant. (Note also that the nbtree preprocessing code can be smart
> about redundant quals, not just contradictory quals, so it matters
> more than it may appear from this simple, unrealistic example of
> mine.)
I agree with your position, but I still don't understand how to consider
transformations to generalized cases without relying on special cases.

As I understand it, you assume that it is possible to apply
transformations at the index creation stage, but there I came across the
selectivity overestimation problem.

I still haven't found a solution for this problem.

> While these similar RowCompareExpr transformations are at least
> somewhat important, that's not really why I bring them up now. I am
> pointing them out now because I think that it might help you to
> develop a more complete mental model of these transformations.
> Ideally, your initial approach will generalize to other situations
> later on. So it's worth considering the relationship between this
> existing RowCompareExpr transformation, and the one that you're
> working on currently. Plus other, future transformations.
I will consider my case more broadly, but for this I will need some
research work.
> This example might also give you some appreciation of why my SAOP
> patch is confused about when we need to do normalization/safety
> checks. Some things seem necessary when generating index paths in the
> optimizer. Other things seem necessary during preprocessing, in the
> nbtree code, at the start of the index scan. Unfortunately, it's not
> obvious to me where the right place is to deal with each aspect of
> setting up multi-column SAOP index quals. My mental model is very
> incomplete.
To be honest, I think that in your examples I understand better what you
mean by normalization to the conjunctive norm, because I only had a
theoretical idea from the logic course.

Hence, yes, normalization/security checks - now I understand why they
are necessary.

--
Regards,
Alena Rybakina
Postgres Professional

On Wed, Aug 2, 2023 at 8:58 AM Alena Rybakina <lena(dot)ribackina(at)yandex(dot)ru> wrote:
> No, I haven't thought about it yet. I studied the example and it would
> really be nice to add optimization here. I didn't notice any problems
> with its implementation. I also have an obvious example with the "or"
> operator, for example
> , select * from multi_test, where (a, b ) = ( 1, 1 ) or (a, b ) = ( 2, 1
> ) ...;
>
> Although I think such a case will be used less often.

Right. As I said, I don't particularly care about the row constructor
syntax -- it's not essential.

In my experience patches like this one that ultimately don't succeed
usually *don't* have specific problems that cannot be fixed. The real
problem tends to be ambiguity about the general high level design. So
more than anything else, ambiguity is the thing that you need to
minimize to be successful here. This is the #1 practical problem, by
far. This may be the only thing about your patch that I feel 100% sure
of.

In my experience it can actually be easier to expand the scope of a
project, and to come up with a more general solution:

https://en.wikipedia.org/wiki/Inventor%27s_paradox

I'm not trying to make your work more difficult by expanding its
scope. I'm actually trying to make your work *easier* by expanding its
scope. I don't claim to know what the specific scope of your patch
should be at all. Just that it might be possible to get a much clearer
picture of what the ideal scope really is by *trying* to generalize it
further -- that understanding is what we lack right now. Even if this
exercise fails in some way, it won't really have been a failure. The
reasons why it fails will still be interesting and practically
relevant.

> It seems to me the most difficult thing is to notice problematic cases
> where the transformations are incorrect, but I think it can be implemented.

Right. To be clear, I am sure that it won't be practical to come up
with a 100% theoretically pure approach. If for no other reason than
this: normalizing to CNF in all cases will run into problems with very
complex predicates. It might even be computationally intractable
(could just be very slow). So there is a clear need to keep
theoretical purity in balance with practical considerations. There is
a need for some kind of negotiation between those two things. Probably
some set of heuristics will ultimately be required to keep costs and
benefits in balance.

> I agree with your position, but I still don't understand how to consider
> transformations to generalized cases without relying on special cases.

Me neither. I wish I could say something a bit less vague here.

I don't expect you to determine what set of heuristics will ultimately
be required to determine when and how to perform CNF conversions, in
the general case. But having at least some vague idea seems like it
might increase confidence in your design.

> As I understand it, you assume that it is possible to apply
> transformations at the index creation stage, but there I came across the
> selectivity overestimation problem.
>
> I still haven't found a solution for this problem.

Do you think that this problem is just an accidental side-effect? It
isn't necessarily the responsibility of your patch to fix such things.
If it's even possible for selectivity estimates to change, then it's
already certain that sometimes they'll be worse than before -- if only
because of chance interactions. The optimizer is often right for the
wrong reasons, and wrong for the right reasons -- we cannot really
expect any patch to completely avoid problems like that.

> To be honest, I think that in your examples I understand better what you
> mean by normalization to the conjunctive norm, because I only had a
> theoretical idea from the logic course.
>
> Hence, yes, normalization/security checks - now I understand why they
> are necessary.

As I explained to Jim, I am trying to put things in this area on a
more rigorous footing. For example, I have said that the way that the
nbtree code executes SAOP quals is equivalent to DNF. That is
basically true, but it's also my own slightly optimistic
interpretation of history and of the design. That's a good start, but
it's not enough on its own.

My interpretation might still be wrong in some subtle way, that I have
yet to discover. That's really what I'm concerned about with your
patch, too. I'm currently trying to solve a problem that I don't yet
fully understand, so for me "getting a properly working flow of
information" seems like a good practical exercise. I'm trying to
generalize the design of my own patch as far as I can, to see what
breaks, and why it breaks. My intuition is that this will help me with
my own patch by forcing me to gain a truly rigorous understanding of
the problem.

My suggestion about generalizing your approach to cover RowCompareExpr
cases is what I would do, if I were you, and this was my patch. That's
almost exactly what I'm doing with my own patch already, in fact.

--
Peter Geoghegan

On 02.08.2023 21:58, Peter Geoghegan wrote:
> On Wed, Aug 2, 2023 at 8:58 AM Alena Rybakina <lena(dot)ribackina(at)yandex(dot)ru> wrote:
>> No, I haven't thought about it yet. I studied the example and it would
>> really be nice to add optimization here. I didn't notice any problems
>> with its implementation. I also have an obvious example with the "or"
>> operator, for example
>> , select * from multi_test, where (a, b ) = ( 1, 1 ) or (a, b ) = ( 2, 1
>> ) ...;
>>
>> Although I think such a case will be used less often.
> Right. As I said, I don't particularly care about the row constructor
> syntax -- it's not essential.
>
> In my experience patches like this one that ultimately don't succeed
> usually *don't* have specific problems that cannot be fixed. The real
> problem tends to be ambiguity about the general high level design. So
> more than anything else, ambiguity is the thing that you need to
> minimize to be successful here. This is the #1 practical problem, by
> far. This may be the only thing about your patch that I feel 100% sure
> of.
>
> In my experience it can actually be easier to expand the scope of a
> project, and to come up with a more general solution:
>
> https://en.wikipedia.org/wiki/Inventor%27s_paradox
>
> I'm not trying to make your work more difficult by expanding its
> scope. I'm actually trying to make your work *easier* by expanding its
> scope. I don't claim to know what the specific scope of your patch
> should be at all. Just that it might be possible to get a much clearer
> picture of what the ideal scope really is by *trying* to generalize it
> further -- that understanding is what we lack right now. Even if this
> exercise fails in some way, it won't really have been a failure. The
> reasons why it fails will still be interesting and practically
> relevant.
>
> As I explained to Jim, I am trying to put things in this area on a
> more rigorous footing. For example, I have said that the way that the
> nbtree code executes SAOP quals is equivalent to DNF. That is
> basically true, but it's also my own slightly optimistic
> interpretation of history and of the design. That's a good start, but
> it's not enough on its own.
>
> My interpretation might still be wrong in some subtle way, that I have
> yet to discover. That's really what I'm concerned about with your
> patch, too. I'm currently trying to solve a problem that I don't yet
> fully understand, so for me "getting a properly working flow of
> information" seems like a good practical exercise. I'm trying to
> generalize the design of my own patch as far as I can, to see what
> breaks, and why it breaks. My intuition is that this will help me with
> my own patch by forcing me to gain a truly rigorous understanding of
> the problem.
>
> My suggestion about generalizing your approach to cover RowCompareExpr
> cases is what I would do, if I were you, and this was my patch. That's
> almost exactly what I'm doing with my own patch already, in fact.
It's all right. I understand your position)

I also agree to try to find other optimization cases and generalize them.

I read the wiki article, and as I understand it, in such a situation we
see a difficult problem with finding expressions that need to be
converted into a logically correct expression and simplify execution for
the executor. For example, this is a ROW type. It can have a simpler
expression with AND and OR operations, besides we can exclude
duplicates. But some of these transformations may be incorrect or they
will have a more complex representation. We can try to find the
problematic expressions and try to combine them into groups and finally
find a solutions for each groups or, conversely, discover that the
existing transformation is uncorrected. If I understand correctly, we
should first start searching for "ROW" expressions (define a group for
them) and think about a solution for the group.
>> It seems to me the most difficult thing is to notice problematic cases
>> where the transformations are incorrect, but I think it can be implemented.
> Right. To be clear, I am sure that it won't be practical to come up
> with a 100% theoretically pure approach. If for no other reason than
> this: normalizing to CNF in all cases will run into problems with very
> complex predicates. It might even be computationally intractable
> (could just be very slow). So there is a clear need to keep
> theoretical purity in balance with practical considerations. There is
> a need for some kind of negotiation between those two things. Probably
> some set of heuristics will ultimately be required to keep costs and
> benefits in balance.
>
> I don't expect you to determine what set of heuristics will ultimately
> be required to determine when and how to perform CNF conversions, in
> the general case. But having at least some vague idea seems like it
> might increase confidence in your design.
I agree, but I think this will be the second step after solutions are
found.
> Do you think that this problem is just an accidental side-effect? It
> isn't necessarily the responsibility of your patch to fix such things.
> If it's even possible for selectivity estimates to change, then it's
> already certain that sometimes they'll be worse than before -- if only
> because of chance interactions. The optimizer is often right for the
> wrong reasons, and wrong for the right reasons -- we cannot really
> expect any patch to completely avoid problems like that.
To be honest, I tried to fix it many times by calling the function to
calculate selectivity, and each time the result of the estimate did not
change. I didn't have any problems in this part after moving the
transformation to the parsing stage. I even tried to perform this
transformation at the planning stage (to the preprocess_qual_conditions
function), but I ran into the same problem there as well.

To tell the truth, I think I'm ready to investigate this problem again
(maybe I'll be able to see it differently or really find that I missed
something in previous times).

--
Regards,
Alena Rybakina
Postgres Professional

On Thu, Aug 3, 2023 at 12:47 PM Alena Rybakina <lena(dot)ribackina(at)yandex(dot)ru> wrote:
> It's all right. I understand your position)

Okay, good to know. :-)

> I also agree to try to find other optimization cases and generalize them.

Good idea. Since the real goal is to "get a working flow of
information", the practical value of trying to get it working with
other clauses seems to be of secondary importance.

> To be honest, I tried to fix it many times by calling the function to
> calculate selectivity, and each time the result of the estimate did not
> change. I didn't have any problems in this part after moving the
> transformation to the parsing stage. I even tried to perform this
> transformation at the planning stage (to the preprocess_qual_conditions
> function), but I ran into the same problem there as well.
>
> To tell the truth, I think I'm ready to investigate this problem again
> (maybe I'll be able to see it differently or really find that I missed
> something in previous times).

The optimizer will itself do a limited form of "normalizing to CNF".
Are you familiar with extract_restriction_or_clauses(), from
orclauses.c? Comments above the function have an example of how this
can work:

* Although a join clause must reference multiple relations overall,
* an OR of ANDs clause might contain sub-clauses that reference just one
* relation and can be used to build a restriction clause for that rel.
* For example consider
* WHERE ((a.x = 42 AND b.y = 43) OR (a.x = 44 AND b.z = 45));
* We can transform this into
* WHERE ((a.x = 42 AND b.y = 43) OR (a.x = 44 AND b.z = 45))
* AND (a.x = 42 OR a.x = 44)
* AND (b.y = 43 OR b.z = 45);
* which allows the latter clauses to be applied during the scans of a and b,
* perhaps as index qualifications, and in any case reducing the number of
* rows arriving at the join. In essence this is a partial transformation to
* CNF (AND of ORs format). It is not complete, however, because we do not
* unravel the original OR --- doing so would usually bloat the qualification
* expression to little gain.

Of course this immediately makes me wonder: shouldn't your patch be
able to perform an additional transformation here? You know, by
transforming "a.x = 42 OR a.x = 44" into "a IN (42, 44)"? Although I
haven't checked for myself, I assume that this doesn't happen right
now, since your patch currently performs all of its transformations
during parsing.

I also noticed that the same comment block goes on to say something
about "clauselist_selectivity's inability to recognize redundant
conditions". Perhaps that is relevant to the problems you were having
with selectivity estimation, back when the code was in
preprocess_qual_conditions() instead? I have no reason to believe that
there should be any redundancy left behind by your transformation, so
this is just one possibility to consider.

Separately, the commit message of commit 25a9e54d2d says something
about how the planner builds RestrictInfos, which seems
possibly-relevant. That commit enhanced extended statistics for OR
clauses, so the relevant paragraph describes a limitation of extended
statistics with OR clauses specifically. I'm just guessing, but it
still seems like it might be relevant to the problem you ran into with
selectivity estimation. Another possibility to consider.

BTW, I sometimes use RR to help improve my understanding of the planner:

https://wiki.postgresql.org/wiki/Getting_a_stack_trace_of_a_running_PostgreSQL_backend_on_Linux/BSD#Recording_Postgres_using_rr_Record_and_Replay_Framework

The planner has particularly complicated control flow, which has
unique challenges -- just knowing where to begin can be difficult
(unlike most other areas). I find that setting watchpoints to see when
and where the planner modifies state using RR is far more useful than
it would be with regular GDB. Once I record a query, I find that I can
"map out" what happens in the planner relatively easily.

--
Peter Geoghegan

On Sat, Aug 5, 2023 at 7:01 PM Peter Geoghegan <pg(at)bowt(dot)ie> wrote:
> Of course this immediately makes me wonder: shouldn't your patch be
> able to perform an additional transformation here? You know, by
> transforming "a.x = 42 OR a.x = 44" into "a IN (42, 44)"? Although I
> haven't checked for myself, I assume that this doesn't happen right
> now, since your patch currently performs all of its transformations
> during parsing.

Many interesting cases won't get SAOP transformation from the patch,
simply because of the or_transform_limit GUC's default of 500. I don't
think that that design makes too much sense. It made more sense back
when the focus was on expression evaluation overhead. But that's only
one of the benefits that we now expect from the patch, right? So it
seems like something that should be revisited soon.

I'm not suggesting that there is no need for some kind of limit. But
it seems like a set of heuristics might be a better approach. Although
I would like to get a better sense of the costs of the transformation
to be able to say too much more.

--
Peter Geoghegan

Hi! Thank you for your research, I'm sure it will help me to fix the
problem of calculating selectivity faster)
I'm sorry I didn't answer right away, to be honest, I had a full diary
of urgent matters at work. For this reason, I didn't have enough time to
work on this patch properly.

> The optimizer will itself do a limited form of "normalizing to CNF".
> Are you familiar with extract_restriction_or_clauses(), from
> orclauses.c? Comments above the function have an example of how this
> can work:
>
> * Although a join clause must reference multiple relations overall,
> * an OR of ANDs clause might contain sub-clauses that reference just one
> * relation and can be used to build a restriction clause for that rel.
> * For example consider
> * WHERE ((a.x = 42 AND b.y = 43) OR (a.x = 44 AND b.z = 45));
> * We can transform this into
> * WHERE ((a.x = 42 AND b.y = 43) OR (a.x = 44 AND b.z = 45))
> * AND (a.x = 42 OR a.x = 44)
> * AND (b.y = 43 OR b.z = 45);
> * which allows the latter clauses to be applied during the scans of a and b,
> * perhaps as index qualifications, and in any case reducing the number of
> * rows arriving at the join. In essence this is a partial transformation to
> * CNF (AND of ORs format). It is not complete, however, because we do not
> * unravel the original OR --- doing so would usually bloat the qualification
> * expression to little gain.
This is an interesting feature. I didn't notice this function before, I
studied many times consider_new_or_cause, which were called there. As
far as I know, there is a selectivity calculation going on there, but as
far as I remember, I called it earlier after my conversion, and
unfortunately it didn't solve my problem with calculating selectivity.
I'll reconsider it again, maybe I can find something I missed.
> Of course this immediately makes me wonder: shouldn't your patch be
> able to perform an additional transformation here? You know, by
> transforming "a.x = 42 OR a.x = 44" into "a IN (42, 44)"? Although I
> haven't checked for myself, I assume that this doesn't happen right
> now, since your patch currently performs all of its transformations
> during parsing.
>
> I also noticed that the same comment block goes on to say something
> about "clauselist_selectivity's inability to recognize redundant
> conditions". Perhaps that is relevant to the problems you were having
> with selectivity estimation, back when the code was in
> preprocess_qual_conditions() instead? I have no reason to believe that
> there should be any redundancy left behind by your transformation, so
> this is just one possibility to consider.
> Separately, the commit message of commit 25a9e54d2d says something
> about how the planner builds RestrictInfos, which seems
> possibly-relevant. That commit enhanced extended statistics for OR
> clauses, so the relevant paragraph describes a limitation of extended
> statistics with OR clauses specifically. I'm just guessing, but it
> still seems like it might be relevant to the problem you ran into with
> selectivity estimation. Another possibility to consider.

I understood what is said about AND clauses in this comment. It seems to
me that AND clauses saved like (BoolExpr *) expr->args->(RestrictInfo *)
clauseA->(RestrictInfo *)clauseB lists and OR clauses saved like
(BoolExpr *) expr -> orclause->(RestrictInfo *)clause A->(RestrictInfo
*)clause B.

As I understand it, selectivity is calculated for each expression. But
I'll exploring it deeper, because I think this place may contain the
answer to the question, what's wrong with selectivity calculation in my
patch.

> BTW, I sometimes use RR to help improve my understanding of the planner:
>
> https://wiki.postgresql.org/wiki/Getting_a_stack_trace_of_a_running_PostgreSQL_backend_on_Linux/BSD#Recording_Postgres_using_rr_Record_and_Replay_Framework
> The planner has particularly complicated control flow, which has
> unique challenges -- just knowing where to begin can be difficult
> (unlike most other areas). I find that setting watchpoints to see when
> and where the planner modifies state using RR is far more useful than
> it would be with regular GDB. Once I record a query, I find that I can
> "map out" what happens in the planner relatively easily.
Thank you for sharing this source! I didn't know about this before, and
it will definitely make my life easier to understand the optimizer.

I understand what you mean, and I researched the optimizer in a similar
way through gdb and looked at the comments and code in postgresql. This
is a complicated way and I didn't always understand correctly what this
variable was doing in this place, and this created some difficulties for me.

So, thank you for the link!

> Many interesting cases won't get SAOP transformation from the patch,
> simply because of the or_transform_limit GUC's default of 500. I don't
> think that that design makes too much sense. It made more sense back
> when the focus was on expression evaluation overhead. But that's only
> one of the benefits that we now expect from the patch, right? So it
> seems like something that should be revisited soon.
>
> I'm not suggesting that there is no need for some kind of limit. But
> it seems like a set of heuristics might be a better approach. Although
> I would like to get a better sense of the costs of the transformation
> to be able to say too much more.

Yes, this may be revised in the future after some transformations.
Initially, I was solving the problem described here [0]. So, after
testing [1], I come to the conclusion that 500 is the ideal value for
or_transform_limit.

[0]
https://www.postgresql.org/message-id/919bfbcb-f812-758d-d687-71f89f0d9a68%40postgrespro.ru

[1]
https://www.postgresql.org/message-id/6b97b517-f36a-f0c6-3b3a-0cf8cfba220c%40yandex.ru

--
Regards,
Alena Rybakina
Postgres Professional

Hi, all!
>> The optimizer will itself do a limited form of "normalizing to CNF".
>> Are you familiar with extract_restriction_or_clauses(), from
>> orclauses.c? Comments above the function have an example of how this
>> can work:
>>
>>   * Although a join clause must reference multiple relations overall,
>>   * an OR of ANDs clause might contain sub-clauses that reference
>> just one
>>   * relation and can be used to build a restriction clause for that rel.
>>   * For example consider
>>   *      WHERE ((a.x = 42 AND b.y = 43) OR (a.x = 44 AND b.z = 45));
>>   * We can transform this into
>>   *      WHERE ((a.x = 42 AND b.y = 43) OR (a.x = 44 AND b.z = 45))
>>   *          AND (a.x = 42 OR a.x = 44)
>>   *          AND (b.y = 43 OR b.z = 45);
>>   * which allows the latter clauses to be applied during the scans of
>> a and b,
>>   * perhaps as index qualifications, and in any case reducing the
>> number of
>>   * rows arriving at the join.  In essence this is a partial
>> transformation to
>>   * CNF (AND of ORs format).  It is not complete, however, because we
>> do not
>>   * unravel the original OR --- doing so would usually bloat the
>> qualification
>>   * expression to little gain.
> This is an interesting feature. I didn't notice this function before,
> I studied many times consider_new_or_cause, which were called there.
> As far as I know, there is a selectivity calculation going on there,
> but as far as I remember, I called it earlier after my conversion, and
> unfortunately it didn't solve my problem with calculating selectivity.
> I'll reconsider it again, maybe I can find something I missed.
>> Of course this immediately makes me wonder: shouldn't your patch be
>> able to perform an additional transformation here? You know, by
>> transforming "a.x = 42 OR a.x = 44" into "a IN (42, 44)"? Although I
>> haven't checked for myself, I assume that this doesn't happen right
>> now, since your patch currently performs all of its transformations
>> during parsing.
>>
>> I also noticed that the same comment block goes on to say something
>> about "clauselist_selectivity's inability to recognize redundant
>> conditions". Perhaps that is relevant to the problems you were having
>> with selectivity estimation, back when the code was in
>> preprocess_qual_conditions() instead? I have no reason to believe that
>> there should be any redundancy left behind by your transformation, so
>> this is just one possibility to consider.
>> Separately, the commit message of commit 25a9e54d2d says something
>> about how the planner builds RestrictInfos, which seems
>> possibly-relevant. That commit enhanced extended statistics for OR
>> clauses, so the relevant paragraph describes a limitation of extended
>> statistics with OR clauses specifically. I'm just guessing, but it
>> still seems like it might be relevant to the problem you ran into with
>> selectivity estimation. Another possibility to consider.
>
> I understood what is said about AND clauses in this comment. It seems
> to me that AND clauses saved like (BoolExpr *)
> expr->args->(RestrictInfo *) clauseA->(RestrictInfo *)clauseB lists
> and OR clauses saved like (BoolExpr *) expr -> orclause->(RestrictInfo
> *)clause A->(RestrictInfo *)clause B.
>
> As I understand it, selectivity is calculated for each expression. But
> I'll exploring it deeper, because I think this place may contain the
> answer to the question, what's wrong with selectivity calculation in
> my patch.

I could move transformation in there (extract_restriction_or_clauses)
and didn't have any problem with selectivity calculation, besides it
also works on the redundant or duplicates stage. So, it looks like:

CREATE TABLE tenk1 (unique1 int, unique2 int, ten int, hundred int);
insert into tenk1 SELECT x,x,x,x FROM generate_series(1,50000) as x;
CREATE INDEX a_idx1 ON tenk1(unique1); CREATE INDEX a_idx2 ON
tenk1(unique2); CREATE INDEX a_hundred ON tenk1(hundred);

explain analyze select * from tenk1 a join tenk1 b on ((a.unique2 = 3 or
a.unique2 = 7));

PLAN
------------------------------------------------------------------------------------------------------------------------------
Nested Loop (cost=0.29..2033.62 rows=100000 width=32) (actual
time=0.090..60.258 rows=100000 loops=1) -> Seq Scan on tenk1 b
(cost=0.00..771.00 rows=50000 width=16) (actual time=0.016..9.747
rows=50000 loops=1) -> Materialize (cost=0.29..12.62 rows=2 width=16)
(actual time=0.000..0.000 rows=2 loops=50000) -> Index Scan using a_idx2
on tenk1 a (cost=0.29..12.62 rows=2 width=16) (actual time=0.063..0.068
rows=2 loops=1) Index Cond: (unique2 = ANY (ARRAY[3, 7])) Planning Time:
8.257 ms Execution Time: 64.453 ms (7 rows)

Overall, this was due to incorrectly defined types of elements in the
array, and if we had applied the transformation with the definition of
the tup operator, we could have avoided such problems (I used
make_scalar_array_op and have not yet found an alternative to this).

When I moved the transformation on the index creation stage, it couldn't
work properly and as a result I faced the same problem of selectivity
calculation. I supposed that the selectivity values are also used there,
and not recalculated all over again. perhaps we can solve this by
forcibly recalculating the selectivity values, but I foresee other
problems there.

explain analyze select * from tenk1 a join tenk1 b on ((a.unique2 = 3 or
a.unique2 = 7));

QUERY PLAN
-----------------------------------------------------------------------------------------------------------------------------------
Nested Loop (cost=12.58..312942.91 rows=24950000 width=32) (actual
time=0.040..47.582 rows=100000 loops=1) -> Seq Scan on tenk1 b
(cost=0.00..771.00 rows=50000 width=16) (actual time=0.009..7.039
rows=50000 loops=1) -> Materialize (cost=12.58..298.16 rows=499
width=16) (actual time=0.000..0.000 rows=2 loops=50000) -> Bitmap Heap
Scan on tenk1 a (cost=12.58..295.66 rows=499 width=16) (actual
time=0.025..0.028 rows=2 loops=1) Recheck Cond: ((unique2 = 3) OR
(unique2 = 7)) Heap Blocks: exact=1 -> BitmapOr (cost=12.58..12.58
rows=500 width=0) (actual time=0.023..0.024 rows=0 loops=1) -> Bitmap
Index Scan on a_idx2 (cost=0.00..6.17 rows=250 width=0) (actual
time=0.019..0.019 rows=1 loops=1) Index Cond: (unique2 = 3) -> Bitmap
Index Scan on a_idx2 (cost=0.00..6.17 rows=250 width=0) (actual
time=0.003..0.003 rows=1 loops=1) Index Cond: (unique2 = 7) Planning
Time: 0.401 ms Execution Time: 51.350 ms (13 rows)

I have attached a diff file so far, but it is very raw and did not pass
all regression tests (I attached regression.diff) and even had bad
conversion cases (some of the cases did not work at all, in other cases
there were no non-converted nodes). But now I see an interesting
transformation, which was the most interesting for me.

EXPLAIN (COSTS OFF) SELECT * FROM tenk1 WHERE thousand = 42 AND
(tenthous = 1 OR tenthous = 3 OR tenthous = 42); - QUERY PLAN
------------------------------------------------------------------------------------------------------------------------------------------
- Bitmap Heap Scan on tenk1 - Recheck Cond: (((thousand = 42) AND
(tenthous = 1)) OR ((thousand = 42) AND (tenthous = 3)) OR ((thousand =
42) AND (tenthous = 42))) - -> BitmapOr - -> Bitmap Index Scan on
tenk1_thous_tenthous - Index Cond: ((thousand = 42) AND (tenthous = 1))
- -> Bitmap Index Scan on tenk1_thous_tenthous - Index Cond: ((thousand
= 42) AND (tenthous = 3)) - -> Bitmap Index Scan on tenk1_thous_tenthous
- Index Cond: ((thousand = 42) AND (tenthous = 42)) -(9 rows) + QUERY
PLAN
+------------------------------------------------------------------------
+ Index Scan using tenk1_thous_tenthous on tenk1 + Index Cond:
((thousand = 42) AND (tenthous = ANY (ARRAY[1, 3, 42]))) +(2 rows)

Sorry, I didn't write correctly enough, about the second second place in
the code where the conversion works well enough is the removal of
duplicate OR expressions.

I attached patch to learn it in more detail.

On 17.08.2023 13:08, a.rybakina wrote:
> Hi, all!
>>> The optimizer will itself do a limited form of "normalizing to CNF".
>>> Are you familiar with extract_restriction_or_clauses(), from
>>> orclauses.c? Comments above the function have an example of how this
>>> can work:
>>>
>>>   * Although a join clause must reference multiple relations overall,
>>>   * an OR of ANDs clause might contain sub-clauses that reference
>>> just one
>>>   * relation and can be used to build a restriction clause for that
>>> rel.
>>>   * For example consider
>>>   *      WHERE ((a.x = 42 AND b.y = 43) OR (a.x = 44 AND b.z = 45));
>>>   * We can transform this into
>>>   *      WHERE ((a.x = 42 AND b.y = 43) OR (a.x = 44 AND b.z = 45))
>>>   *          AND (a.x = 42 OR a.x = 44)
>>>   *          AND (b.y = 43 OR b.z = 45);
>>>   * which allows the latter clauses to be applied during the scans
>>> of a and b,
>>>   * perhaps as index qualifications, and in any case reducing the
>>> number of
>>>   * rows arriving at the join.  In essence this is a partial
>>> transformation to
>>>   * CNF (AND of ORs format).  It is not complete, however, because
>>> we do not
>>>   * unravel the original OR --- doing so would usually bloat the
>>> qualification
>>>   * expression to little gain.
>> This is an interesting feature. I didn't notice this function before,
>> I studied many times consider_new_or_cause, which were called there.
>> As far as I know, there is a selectivity calculation going on there,
>> but as far as I remember, I called it earlier after my conversion,
>> and unfortunately it didn't solve my problem with calculating
>> selectivity. I'll reconsider it again, maybe I can find something I
>> missed.
>>> Of course this immediately makes me wonder: shouldn't your patch be
>>> able to perform an additional transformation here? You know, by
>>> transforming "a.x = 42 OR a.x = 44" into "a IN (42, 44)"? Although I
>>> haven't checked for myself, I assume that this doesn't happen right
>>> now, since your patch currently performs all of its transformations
>>> during parsing.
>>>
>>> I also noticed that the same comment block goes on to say something
>>> about "clauselist_selectivity's inability to recognize redundant
>>> conditions". Perhaps that is relevant to the problems you were having
>>> with selectivity estimation, back when the code was in
>>> preprocess_qual_conditions() instead? I have no reason to believe that
>>> there should be any redundancy left behind by your transformation, so
>>> this is just one possibility to consider.
>>> Separately, the commit message of commit 25a9e54d2d says something
>>> about how the planner builds RestrictInfos, which seems
>>> possibly-relevant. That commit enhanced extended statistics for OR
>>> clauses, so the relevant paragraph describes a limitation of extended
>>> statistics with OR clauses specifically. I'm just guessing, but it
>>> still seems like it might be relevant to the problem you ran into with
>>> selectivity estimation. Another possibility to consider.
>>
>> I understood what is said about AND clauses in this comment. It seems
>> to me that AND clauses saved like (BoolExpr *)
>> expr->args->(RestrictInfo *) clauseA->(RestrictInfo *)clauseB lists
>> and OR clauses saved like (BoolExpr *) expr ->
>> orclause->(RestrictInfo *)clause A->(RestrictInfo *)clause B.
>>
>> As I understand it, selectivity is calculated for each expression.
>> But I'll exploring it deeper, because I think this place may contain
>> the answer to the question, what's wrong with selectivity calculation
>> in my patch.
>
> I could move transformation in there (extract_restriction_or_clauses)
> and didn't have any problem with selectivity calculation, besides it
> also works on the redundant or duplicates stage. So, it looks like:
>
> CREATE TABLE tenk1 (unique1 int, unique2 int, ten int, hundred int);
> insert into tenk1 SELECT x,x,x,x FROM generate_series(1,50000) as x;
> CREATE INDEX a_idx1 ON tenk1(unique1); CREATE INDEX a_idx2 ON
> tenk1(unique2); CREATE INDEX a_hundred ON tenk1(hundred);
>
> explain analyze select * from tenk1 a join tenk1 b on ((a.unique2 = 3
> or a.unique2 = 7));
>
> PLAN
> ------------------------------------------------------------------------------------------------------------------------------
> Nested Loop (cost=0.29..2033.62 rows=100000 width=32) (actual
> time=0.090..60.258 rows=100000 loops=1) -> Seq Scan on tenk1 b
> (cost=0.00..771.00 rows=50000 width=16) (actual time=0.016..9.747
> rows=50000 loops=1) -> Materialize (cost=0.29..12.62 rows=2 width=16)
> (actual time=0.000..0.000 rows=2 loops=50000) -> Index Scan using
> a_idx2 on tenk1 a (cost=0.29..12.62 rows=2 width=16) (actual
> time=0.063..0.068 rows=2 loops=1) Index Cond: (unique2 = ANY (ARRAY[3,
> 7])) Planning Time: 8.257 ms Execution Time: 64.453 ms (7 rows)
>
> Overall, this was due to incorrectly defined types of elements in the
> array, and if we had applied the transformation with the definition of
> the tup operator, we could have avoided such problems (I used
> make_scalar_array_op and have not yet found an alternative to this).
>
> When I moved the transformation on the index creation stage, it
> couldn't work properly and as a result I faced the same problem of
> selectivity calculation. I supposed that the selectivity values are
> also used there, and not recalculated all over again. perhaps we can
> solve this by forcibly recalculating the selectivity values, but I
> foresee other problems there.
>
> explain analyze select * from tenk1 a join tenk1 b on ((a.unique2 = 3
> or a.unique2 = 7));
>
> QUERY PLAN
> -----------------------------------------------------------------------------------------------------------------------------------
> Nested Loop (cost=12.58..312942.91 rows=24950000 width=32) (actual
> time=0.040..47.582 rows=100000 loops=1) -> Seq Scan on tenk1 b
> (cost=0.00..771.00 rows=50000 width=16) (actual time=0.009..7.039
> rows=50000 loops=1) -> Materialize (cost=12.58..298.16 rows=499
> width=16) (actual time=0.000..0.000 rows=2 loops=50000) -> Bitmap Heap
> Scan on tenk1 a (cost=12.58..295.66 rows=499 width=16) (actual
> time=0.025..0.028 rows=2 loops=1) Recheck Cond: ((unique2 = 3) OR
> (unique2 = 7)) Heap Blocks: exact=1 -> BitmapOr (cost=12.58..12.58
> rows=500 width=0) (actual time=0.023..0.024 rows=0 loops=1) -> Bitmap
> Index Scan on a_idx2 (cost=0.00..6.17 rows=250 width=0) (actual
> time=0.019..0.019 rows=1 loops=1) Index Cond: (unique2 = 3) -> Bitmap
> Index Scan on a_idx2 (cost=0.00..6.17 rows=250 width=0) (actual
> time=0.003..0.003 rows=1 loops=1) Index Cond: (unique2 = 7) Planning
> Time: 0.401 ms Execution Time: 51.350 ms (13 rows)
>
> I have attached a diff file so far, but it is very raw and did not
> pass all regression tests (I attached regression.diff) and even had
> bad conversion cases (some of the cases did not work at all, in other
> cases there were no non-converted nodes). But now I see an interesting
> transformation, which was the most interesting for me.
>
> EXPLAIN (COSTS OFF) SELECT * FROM tenk1 WHERE thousand = 42 AND
> (tenthous = 1 OR tenthous = 3 OR tenthous = 42); - QUERY PLAN
> ------------------------------------------------------------------------------------------------------------------------------------------
> - Bitmap Heap Scan on tenk1 - Recheck Cond: (((thousand = 42) AND
> (tenthous = 1)) OR ((thousand = 42) AND (tenthous = 3)) OR ((thousand
> = 42) AND (tenthous = 42))) - -> BitmapOr - -> Bitmap Index Scan on
> tenk1_thous_tenthous - Index Cond: ((thousand = 42) AND (tenthous =
> 1)) - -> Bitmap Index Scan on tenk1_thous_tenthous - Index Cond:
> ((thousand = 42) AND (tenthous = 3)) - -> Bitmap Index Scan on
> tenk1_thous_tenthous - Index Cond: ((thousand = 42) AND (tenthous =
> 42)) -(9 rows) + QUERY PLAN
> +------------------------------------------------------------------------
> + Index Scan using tenk1_thous_tenthous on tenk1 + Index Cond:
> ((thousand = 42) AND (tenthous = ANY (ARRAY[1, 3, 42]))) +(2 rows)
>

On Thu, Aug 17, 2023 at 3:08 AM a.rybakina <a(dot)rybakina(at)postgrespro(dot)ru> wrote:
> This is an interesting feature. I didn't notice this function before, I studied many times consider_new_or_cause, which were called there. As far as I know, there is a selectivity calculation going on there, but as far as I remember, I called it earlier after my conversion, and unfortunately it didn't solve my problem with calculating selectivity. I'll reconsider it again, maybe I can find something I missed.

Back in 2003, commit 9888192f removed (or at least simplified) what
were then called "CNF/DNF CONVERSION ROUTINES". Prior to that point
the optimizer README had something about leaving clause lists
un-normalized leading to selectivity estimation problems. Bear in mind
that this is a couple of years before ScalarArrayOpExpr was first
invented. Apparently even back then "The OR-of-ANDs format is useful
for indexscan implementation". It's possible that that old work will
offer some hints on what to do now.

In a way it's not surprising that work in this area would have some
impact on selectivies. The surprising part is the extent of the
problem, I suppose.

I see that a lot of the things in this area are just used by BitmapOr
clauses, such as build_paths_for_OR() -- but you're not necessarily
able to use any of that stuff. Also, choose_bitmap_and() has some
stuff about how it compensates to avoid "too-small selectivity that
makes a redundant AND step look like it reduces the total cost". It
also mentions some problems with match_join_clauses_to_index() +
extract_restriction_or_clauses(). Again, this might be a good place to
look for more clues.

--
Peter Geoghegan

On Sun, Aug 20, 2023 at 3:11 PM Peter Geoghegan <pg(at)bowt(dot)ie> wrote:
> Back in 2003, commit 9888192f removed (or at least simplified) what
> were then called "CNF/DNF CONVERSION ROUTINES". Prior to that point
> the optimizer README had something about leaving clause lists
> un-normalized leading to selectivity estimation problems. Bear in mind
> that this is a couple of years before ScalarArrayOpExpr was first
> invented. Apparently even back then "The OR-of-ANDs format is useful
> for indexscan implementation". It's possible that that old work will
> offer some hints on what to do now.

There was actually support for OR lists in index AMs prior to
ScalarArrayOpExpr. Even though ScalarArrayOpExpr don't really seem all
that related to bitmap scans these days (since at least nbtree knows
how to execute them "natively"), that wasn't always the case.
ScalarArrayOpExpr were invented the same year that bitmap index scans
were first added (2005), and seem more or less related to that work.
See commits bc843d39, 5b051852, 1e9a6ba5, and 290166f9 (all from
2005). Particularly the last one, which has a commit message that
heavily suggests that my interpretation is correct.

I think that we currently over-rely on BitmapOr for OR clauses. It's
useful that they're so general, of course, but ISTM that we shouldn't
even try to use a BitmapOr in simple cases. Things like the "WHERE
thousand = 42 AND (tenthous = 1 OR tenthous = 3 OR tenthous = 42)"
tenk1 query that you brought up probably shouldn't even have a
BitmapOr path (which I guess they don't with you patch). Note that I
recently discussed the same query at length with Tomas Vondra on the
ongoing thread for his index filter patch (you probably knew that
already).

--
Peter Geoghegan

On Thu, Aug 17, 2023 at 3:08 AM a.rybakina <a(dot)rybakina(at)postgrespro(dot)ru> wrote:
> But now I see an interesting transformation, which was the most interesting for me.
>
> EXPLAIN (COSTS OFF) SELECT * FROM tenk1 WHERE thousand = 42 AND (tenthous = 1 OR tenthous = 3 OR tenthous = 42);

It would be even more interesting if it could be an index-only scan as
a result of the transformation. For example, we could use an
index-only scan with this query (once your patch was in place):

"SELECT thousand, tenthous FROM tenk1 WHERE thousand = 42 AND
(tenthous = 1 OR tenthous = 3 OR tenthous = 42)"

Index-only scans were the original motivation for adding native
ScalarArrayExprOp support to nbtree (in 2011 commit 9e8da0f7), in
fact.

As I suggested earlier, I suspect that there is too much planner logic
that targets BitmapOrs specifically -- maybe even selectivity
estimation/restrictinfo stuff.

PS I wonder if the correctness issues that you saw could be related to
eval_const_expressions(), since "the planner assumes that this
[eval_const_expressions] will always flatten nested AND and OR clauses
into N-argument form". See its subroutines simplify_or_arguments() and
simplify_and_arguments().

--
Peter Geoghegan

Thank you for your interest in this problem and help, and I'm sorry that
I didn't respond to this email for a long time. To be honest, I wanted
to investigate the problems in more detail and already answer more
clearly, but unfortunately I have not found anything more significant yet.

On 21.08.2023 01:26, Peter Geoghegan wrote:
> There was actually support for OR lists in index AMs prior to
> ScalarArrayOpExpr. Even though ScalarArrayOpExpr don't really seem all
> that related to bitmap scans these days (since at least nbtree knows
> how to execute them "natively"), that wasn't always the case.
> ScalarArrayOpExpr were invented the same year that bitmap index scans
> were first added (2005), and seem more or less related to that work.
> See commits bc843d39, 5b051852, 1e9a6ba5, and 290166f9 (all from
> 2005). Particularly the last one, which has a commit message that
> heavily suggests that my interpretation is correct.
>
> Back in 2003, commit 9888192f removed (or at least simplified) what
> were then called "CNF/DNF CONVERSION ROUTINES". Prior to that point
> the optimizer README had something about leaving clause lists
> un-normalized leading to selectivity estimation problems. Bear in mind
> that this is a couple of years before ScalarArrayOpExpr was first
> invented. Apparently even back then "The OR-of-ANDs format is useful
> for indexscan implementation". It's possible that that old work will
> offer some hints on what to do now.
> In a way it's not surprising that work in this area would have some
> impact on selectivies. The surprising part is the extent of the
> problem, I suppose.
>
> I see that a lot of the things in this area are just used by BitmapOr
> clauses, such as build_paths_for_OR() -- but you're not necessarily
> able to use any of that stuff. Also, choose_bitmap_and() has some
> stuff about how it compensates to avoid "too-small selectivity that
> makes a redundant AND step look like it reduces the total cost". It
> also mentions some problems with match_join_clauses_to_index() +
> extract_restriction_or_clauses(). Again, this might be a good place to
> look for more clues.
I agree with your assumption about looking at the source of the error
related to selectivity in these places. But honestly, no matter how many
times I looked, until enough sensible thoughts appeared, which could
cause a problem. I keep looking, maybe I'll find something.
> EXPLAIN (COSTS OFF) SELECT * FROM tenk1 WHERE thousand = 42 AND
> (tenthous = 1 OR tenthous = 3 OR tenthous = 42); - QUERY PLAN
> ------------------------------------------------------------------------------------------------------------------------------------------
> - Bitmap Heap Scan on tenk1 - Recheck Cond: (((thousand = 42) AND
> (tenthous = 1)) OR ((thousand = 42) AND (tenthous = 3)) OR ((thousand
> = 42) AND (tenthous = 42))) - -> BitmapOr - -> Bitmap Index Scan on
> tenk1_thous_tenthous - Index Cond: ((thousand = 42) AND (tenthous =
> 1)) - -> Bitmap Index Scan on tenk1_thous_tenthous - Index Cond:
> ((thousand = 42) AND (tenthous = 3)) - -> Bitmap Index Scan on
> tenk1_thous_tenthous - Index Cond: ((thousand = 42) AND (tenthous =
> 42)) -(9 rows) + QUERY PLAN
> +------------------------------------------------------------------------
> + Index Scan using tenk1_thous_tenthous on tenk1 + Index Cond:
> ((thousand = 42) AND (tenthous = ANY (ARRAY[1, 3, 42]))) +(2 rows)
>
> I think that we currently over-rely on BitmapOr for OR clauses. It's
> useful that they're so general, of course, but ISTM that we shouldn't
> even try to use a BitmapOr in simple cases. Things like the "WHERE
> thousand = 42 AND (tenthous = 1 OR tenthous = 3 OR tenthous = 42)"
> tenk1 query that you brought up probably shouldn't even have a
> BitmapOr path (which I guess they don't with you patch). Note that I
> recently discussed the same query at length with Tomas Vondra on the
> ongoing thread for his index filter patch (you probably knew that
> already).
I think so too, but it's still quite difficult to find a stable enough
optimization to implement this, in my opinion. But I will finish the
current optimization with OR->ANY, given that something interesting has
appeared.

On 29.08.23 05:37, a.rybakina wrote:
> Thank you for your interest in this problem and help, and I'm sorry that
> I didn't respond to this email for a long time. To be honest, I wanted
> to investigate the problems in more detail and already answer more
> clearly, but unfortunately I have not found anything more significant yet.

What is the status of this patch? It is registered in the commitfest.
It looks like a stalled research project? The last posted patch doesn't
contain any description or tests, so it doesn't look very ready.

Hi!

When I sent the patch version to commitfest, I thought that the work on
this topic was completed. Patch version and test results in [0].

But in the process of discussing this patch, we found out that there is
another place where you can make a transformation, specifically, during
the calculation of selectivity. I implemented the raw version [1], but
unfortunately it didn't work in regression tests.

I'm sorry that I didn't write about the status earlier, I was very
overwhelmed with tasks at work due to releases and preparations for the
conference. I returned to the work of this patch, today or tomorrow I'll
drop the version.

[0]

https://www.postgresql.org/message-id/4bac271d-1700-db24-74ac-8414f2baf9fd%40postgrespro.ru

https://www.postgresql.org/message-id/11403645-b342-c400-859e-47d0f41ec22a%40postgrespro.ru

[1]
https://www.postgresql.org/message-id/b301dce1-09fd-72b1-834a-527ca428db5e%40yandex.ru

On 20.09.2023 12:37, Peter Eisentraut wrote:
> On 29.08.23 05:37, a.rybakina wrote:
>> Thank you for your interest in this problem and help, and I'm sorry
>> that I didn't respond to this email for a long time. To be honest, I
>> wanted to investigate the problems in more detail and already answer
>> more clearly, but unfortunately I have not found anything more
>> significant yet.
>
> What is the status of this patch?  It is registered in the commitfest.
> It looks like a stalled research project?  The last posted patch
> doesn't contain any description or tests, so it doesn't look very ready.
>

I'm sorry I didn't write for a long time, but I really had a very
difficult month, now I'm fully back to work.

*I was able to implement the patches to the end and moved the
transformation of "OR" expressions to ANY.* I haven't seen a big
difference between them yet, one has a conversion before calculating
selectivity (v7-v1-Replace-OR-clause-to-ANY.patch), the other after
(v7-v2-Replace-OR-clause-to-ANY.patch). Regression tests are passing, I
don't see any problems with selectivity, nothing has fallen into the
coredump, but I found some incorrect transformations. What is the reason
for these inaccuracies, I have not found, but, to be honest, they look
unusual). Gave the error below.
In the patch, I don't like that I had to drag three libraries from
parsing until I found a way around it.The advantage of this approach
compared to the other (v7-v0-Replace-OR-clause-to-ANY.patch) is that at
this stage all possible or transformations are performed, compared to
the patch, where the transformation was done at the parsing stage. That
is, here, for example, there are such optimizations in the transformation:

I took the common element out of the bracket and the rest is converted
to ANY, while, as noted by Peter Geoghegan, we did not have several
bitmapscans, but only one scan through the array.

postgres=# explain analyze SELECT p1.oid, p1.proname
FROM pg_proc as p1
WHERE prolang = 13 AND prolang=1 OR prolang = 13 AND prolang = 2 OR
prolang = 13 AND prolang = 3;
                                              QUERY PLAN
-------------------------------------------------------------------------------------------------------
 Seq Scan on pg_proc p1  (cost=0.00..151.66 rows=1 width=68) (actual
time=1.167..1.168 rows=0 loops=1)
   Filter: ((prolang = '13'::oid) AND (prolang = ANY (ARRAY['1'::oid,
'2'::oid, '3'::oid])))
   Rows Removed by Filter: 3302
 Planning Time: 0.146 ms
 Execution Time: 1.191 ms
(5 rows)

*While I was testing, I found some transformations that don't work,
although in my opinion, they should:**
**
**1. First case:*
explain analyze SELECT p1.oid, p1.proname
FROM pg_proc as p1
WHERE prolang = 13 AND prolang=1 OR prolang = 2 AND prolang = 2 OR
prolang = 13 AND prolang = 13;
QUERY PLAN
----------------------------------------------------------------------------------------------------------------------------------------------------------------------
 Seq Scan on pg_proc p1  (cost=0.00..180.55 rows=2 width=68) (actual
time=2.959..3.335 rows=89 loops=1)
   Filter: (((prolang = '13'::oid) AND (prolang = '1'::oid)) OR
((prolang = '2'::oid) AND (prolang = '2'::oid)) OR ((prolang =
'13'::oid) AND (prolang = '13'::oid)))
   Rows Removed by Filter: 3213
 Planning Time: 1.278 ms
 Execution Time: 3.486 ms
(5 rows)

Should have left only prolang = '13'::oid:

                                              QUERY PLAN
-------------------------------------------------------------------------------------------------------
 Seq Scan on pg_proc p1  (cost=0.00..139.28 rows=1 width=68) (actual
time=2.034..2.034 rows=0 loops=1)
   Filter: ((prolang = '13'::oid ))
   Rows Removed by Filter: 3302
 Planning Time: 0.181 ms
 Execution Time: 2.079 ms
(5 rows)

*2. Also does not work:*
postgres=# explain analyze SELECT p1.oid, p1.proname
FROM pg_proc as p1
WHERE prolang = 13 OR prolang = 2 AND prolang = 2 OR prolang = 13;
                                                  QUERY PLAN
---------------------------------------------------------------------------------------------------------------
 Seq Scan on pg_proc p1  (cost=0.00..164.04 rows=176 width=68) (actual
time=2.422..2.686 rows=89 loops=1)
   Filter: ((prolang = '13'::oid) OR ((prolang = '2'::oid) AND (prolang
= '2'::oid)) OR (prolang = '13'::oid))
   Rows Removed by Filter: 3213
 Planning Time: 1.370 ms
 Execution Time: 2.799 ms
(5 rows)

Should have left:
Filter: ((prolang = '13'::oid) OR (prolang = '2'::oid))

*3. Or another:*

explain analyze SELECT p1.oid, p1.proname
FROM pg_proc as p1
WHERE prolang = 13 OR prolang=13 OR prolang = 2 AND prolang = 2;
                                                  QUERY PLAN
---------------------------------------------------------------------------------------------------------------
 Seq Scan on pg_proc p1  (cost=0.00..164.04 rows=176 width=68) (actual
time=2.350..2.566 rows=89 loops=1)
   Filter: ((prolang = '13'::oid) OR (prolang = '13'::oid) OR ((prolang
= '2'::oid) AND (prolang = '2'::oid)))
   Rows Removed by Filter: 3213
 Planning Time: 0.215 ms
 Execution Time: 2.624 ms
(5 rows)

Should have left:
Filter: ((prolang = '13'::oid) OR (prolang = '2'::oid))

*Falls into coredump at me:*
explain analyze SELECT p1.oid, p1.proname
FROM pg_proc as p1
WHERE prolang = 13 OR prolang = 2 AND prolang = 2 OR prolang = 13;

explain analyze SELECT p1.oid, p1.proname
FROM pg_proc as p1
WHERE prolang = 13 OR prolang=13 OR prolang = 2 AND prolang = 2;
                                                  QUERY PLAN
---------------------------------------------------------------------------------------------------------------
 Seq Scan on pg_proc p1  (cost=0.00..164.04 rows=176 width=68) (actual
time=2.350..2.566 rows=89 loops=1)
   Filter: ((prolang = '13'::oid) OR (prolang = '13'::oid) OR ((prolang
= '2'::oid) AND (prolang = '2'::oid)))
   Rows Removed by Filter: 3213
 Planning Time: 0.215 ms
 Execution Time: 2.624 ms

(5 rows)

I remind that initially the task was to find an opportunity to optimize
the case of processing a large number of "or" expressions to optimize
memory consumption. The FlameGraph for executing 50,000 "or"
expressionshas grown 1.4Gb and remains in this state until exiting the
psql session (flamegraph1.png) and it sagged a lot in execution time. If
this case is converted to ANY, the query is executed much faster and
memory is optimized (flamegraph2.png). It may be necessary to use this
approach if there is no support for the framework to process ANY, IN
expressions.

Peter Geoghegan also noticed some development of this patch in terms of
preparing some transformations to optimize the query at the stage of its
execution [0].

[0]
https://www.postgresql.org/message-id/CAH2-Wz%3D9N_4%2BEyhtyFqYQRx4OgVbP%2B1aoYU2JQPVogCir61ZEQ%40mail.gmail.com

I'm sorry I didn't write for a long time, but I really had a very
difficult month, now I'm fully back to work.

*I was able to implement the patches to the end and moved the
transformation of "OR" expressions to ANY.* I haven't seen a big
difference between them yet, one has a transformation before calculating
selectivity (v7.1-Replace-OR-clause-to-ANY.patch), the other after
(v7.2-Replace-OR-clause-to-ANY.patch). Regression tests are passing, I
don't see any problems with selectivity, nothing has fallen into the
coredump, but I found some incorrect transformations. What is the reason
for these inaccuracies, I have not found, but, to be honest, they look
unusual). Gave the error below.

In the patch, I don't like that I had to drag three libraries from
parsing until I found a way around it.The advantage of this approach
compared to the other (v7.0-Replace-OR-clause-to-ANY.patch) is that at
this stage all possible or transformations are performed, compared to
the patch, where the transformation was done at the parsing stage. That
is, here, for example, there are such optimizations in the transformation:

I took the common element out of the bracket and the rest is converted
to ANY, while, as noted by Peter Geoghegan, we did not have several
bitmapscans, but only one scan through the array.

postgres=# explain analyze SELECT p1.oid, p1.proname
FROM pg_proc as p1
WHERE prolang = 13 AND prolang=1 OR prolang = 13 AND prolang = 2 OR
prolang = 13 AND prolang = 3;
                                              QUERY PLAN
-------------------------------------------------------------------------------------------------------
 Seq Scan on pg_proc p1  (cost=0.00..151.66 rows=1 width=68) (actual
time=1.167..1.168 rows=0 loops=1)
   Filter: ((prolang = '13'::oid) AND (prolang = ANY (ARRAY['1'::oid,
'2'::oid, '3'::oid])))
   Rows Removed by Filter: 3302
 Planning Time: 0.146 ms
 Execution Time: 1.191 ms
(5 rows)

*While I was testing, I found some transformations that don't work,
although in my opinion, they should:**
**
**1. First case:*
explain analyze SELECT p1.oid, p1.proname
FROM pg_proc as p1
WHERE prolang = 13 AND prolang=1 OR prolang = 2 AND prolang = 2 OR
prolang = 13 AND prolang = 13;
QUERY PLAN
----------------------------------------------------------------------------------------------------------------------------------------------------------------------
 Seq Scan on pg_proc p1  (cost=0.00..180.55 rows=2 width=68) (actual
time=2.959..3.335 rows=89 loops=1)
   Filter: (((prolang = '13'::oid) AND (prolang = '1'::oid)) OR
((prolang = '2'::oid) AND (prolang = '2'::oid)) OR ((prolang =
'13'::oid) AND (prolang = '13'::oid)))
   Rows Removed by Filter: 3213
 Planning Time: 1.278 ms
 Execution Time: 3.486 ms
(5 rows)

Should have left only prolang = '13'::oid:

                                              QUERY PLAN
-------------------------------------------------------------------------------------------------------
 Seq Scan on pg_proc p1  (cost=0.00..139.28 rows=1 width=68) (actual
time=2.034..2.034 rows=0 loops=1)
   Filter: ((prolang = '13'::oid ))
   Rows Removed by Filter: 3302
 Planning Time: 0.181 ms
 Execution Time: 2.079 ms
(5 rows)

*2. Also does not work:*
postgres=# explain analyze SELECT p1.oid, p1.proname
FROM pg_proc as p1
WHERE prolang = 13 OR prolang = 2 AND prolang = 2 OR prolang = 13;
                                                  QUERY PLAN
---------------------------------------------------------------------------------------------------------------
 Seq Scan on pg_proc p1  (cost=0.00..164.04 rows=176 width=68) (actual
time=2.422..2.686 rows=89 loops=1)
   Filter: ((prolang = '13'::oid) OR ((prolang = '2'::oid) AND (prolang
= '2'::oid)) OR (prolang = '13'::oid))
   Rows Removed by Filter: 3213
 Planning Time: 1.370 ms
 Execution Time: 2.799 ms
(5 rows)

Should have left:
Filter: ((prolang = '13'::oid) OR (prolang = '2'::oid))

*3. Or another:*

explain analyze SELECT p1.oid, p1.proname
FROM pg_proc as p1
WHERE prolang = 13 OR prolang=13 OR prolang = 2 AND prolang = 2;
                                                  QUERY PLAN
---------------------------------------------------------------------------------------------------------------
 Seq Scan on pg_proc p1  (cost=0.00..164.04 rows=176 width=68) (actual
time=2.350..2.566 rows=89 loops=1)
   Filter: ((prolang = '13'::oid) OR (prolang = '13'::oid) OR ((prolang
= '2'::oid) AND (prolang = '2'::oid)))
   Rows Removed by Filter: 3213
 Planning Time: 0.215 ms
 Execution Time: 2.624 ms
(5 rows)

Should have left:
Filter: ((prolang = '13'::oid) OR (prolang = '2'::oid))

*Falls into coredump at me:*
explain analyze SELECT p1.oid, p1.proname
FROM pg_proc as p1
WHERE prolang = 13 OR prolang = 2 AND prolang = 2 OR prolang = 13;

explain analyze SELECT p1.oid, p1.proname
FROM pg_proc as p1
WHERE prolang = 13 OR prolang=13 OR prolang = 2 AND prolang = 2;
                                                  QUERY PLAN
---------------------------------------------------------------------------------------------------------------
 Seq Scan on pg_proc p1  (cost=0.00..164.04 rows=176 width=68) (actual
time=2.350..2.566 rows=89 loops=1)
   Filter: ((prolang = '13'::oid) OR (prolang = '13'::oid) OR ((prolang
= '2'::oid) AND (prolang = '2'::oid)))
   Rows Removed by Filter: 3213
 Planning Time: 0.215 ms
 Execution Time: 2.624 ms

(5 rows)

I remind that initially the task was to find an opportunity to optimize
the case of processing a large number of "or" expressions to optimize
memory consumption. The FlameGraph for executing 50,000 "or"
expressionshas grown 1.4Gb and remains in this state until exiting the
psql session (flamegraph1.png) and it sagged a lot in execution time. If
this case is converted to ANY, the query is executed much faster and
memory is optimized (flamegraph2.png). It may be necessary to use this
approach if there is no support for the framework to process ANY, IN
expressions.

Peter Geoghegan also noticed some development of this patch in terms of
preparing some transformations to optimize the query at the stage of its
execution [0].

[0]
https://www.postgresql.org/message-id/CAH2-Wz%3D9N_4%2BEyhtyFqYQRx4OgVbP%2B1aoYU2JQPVogCir61ZEQ%40mail.gmail.com

I'm sorry I didn't write for a long time, but I really had a very
difficult month, now I'm fully back to work.

*I was able to implement the patches to the end and moved the
transformation of "OR" expressions to ANY.* I haven't seen a big
difference between them yet, one has a transformation before calculating
selectivity (v7.1-Replace-OR-clause-to-ANY.patch), the other after
(v7.2-Replace-OR-clause-to-ANY.patch). Regression tests are passing, I
don't see any problems with selectivity, nothing has fallen into the
coredump, but I found some incorrect transformations. What is the reason
for these inaccuracies, I have not found, but, to be honest, they look
unusual). Gave the error below.

In the patch, I don't like that I had to drag three libraries from
parsing until I found a way around it.The advantage of this approach
compared to the other ([1]) is that at this stage all possible or
transformations are performed, compared to the patch, where the
transformation was done at the parsing stage. That is, here, for
example, there are such optimizations in the transformation:

I took the common element out of the bracket and the rest is converted
to ANY, while, as noted by Peter Geoghegan, we did not have several
bitmapscans, but only one scan through the array.

postgres=# explain analyze SELECT p1.oid, p1.proname
FROM pg_proc as p1
WHERE prolang = 13 AND prolang=1 OR prolang = 13 AND prolang = 2 OR
prolang = 13 AND prolang = 3;
                                              QUERY PLAN
-------------------------------------------------------------------------------------------------------
 Seq Scan on pg_proc p1  (cost=0.00..151.66 rows=1 width=68) (actual
time=1.167..1.168 rows=0 loops=1)
   Filter: ((prolang = '13'::oid) AND (prolang = ANY (ARRAY['1'::oid,
'2'::oid, '3'::oid])))
   Rows Removed by Filter: 3302
 Planning Time: 0.146 ms
 Execution Time: 1.191 ms
(5 rows)

*While I was testing, I found some transformations that don't work,
although in my opinion, they should:**
**
**1. First case:*
explain analyze SELECT p1.oid, p1.proname
FROM pg_proc as p1
WHERE prolang = 13 AND prolang=1 OR prolang = 2 AND prolang = 2 OR
prolang = 13 AND prolang = 13;
QUERY PLAN
----------------------------------------------------------------------------------------------------------------------------------------------------------------------
 Seq Scan on pg_proc p1  (cost=0.00..180.55 rows=2 width=68) (actual
time=2.959..3.335 rows=89 loops=1)
   Filter: (((prolang = '13'::oid) AND (prolang = '1'::oid)) OR
((prolang = '2'::oid) AND (prolang = '2'::oid)) OR ((prolang =
'13'::oid) AND (prolang = '13'::oid)))
   Rows Removed by Filter: 3213
 Planning Time: 1.278 ms
 Execution Time: 3.486 ms
(5 rows)

Should have left only prolang = '13'::oid:

                                              QUERY PLAN
-------------------------------------------------------------------------------------------------------
 Seq Scan on pg_proc p1  (cost=0.00..139.28 rows=1 width=68) (actual
time=2.034..2.034 rows=0 loops=1)
   Filter: ((prolang = '13'::oid ))
   Rows Removed by Filter: 3302
 Planning Time: 0.181 ms
 Execution Time: 2.079 ms
(5 rows)

*2. Also does not work:*
postgres=# explain analyze SELECT p1.oid, p1.proname
FROM pg_proc as p1
WHERE prolang = 13 OR prolang = 2 AND prolang = 2 OR prolang = 13;
                                                  QUERY PLAN
---------------------------------------------------------------------------------------------------------------
 Seq Scan on pg_proc p1  (cost=0.00..164.04 rows=176 width=68) (actual
time=2.422..2.686 rows=89 loops=1)
   Filter: ((prolang = '13'::oid) OR ((prolang = '2'::oid) AND (prolang
= '2'::oid)) OR (prolang = '13'::oid))
   Rows Removed by Filter: 3213
 Planning Time: 1.370 ms
 Execution Time: 2.799 ms
(5 rows)

Should have left:
Filter: ((prolang = '13'::oid) OR (prolang = '2'::oid))

*3. Or another:*

explain analyze SELECT p1.oid, p1.proname
FROM pg_proc as p1
WHERE prolang = 13 OR prolang=13 OR prolang = 2 AND prolang = 2;
                                                  QUERY PLAN
---------------------------------------------------------------------------------------------------------------
 Seq Scan on pg_proc p1  (cost=0.00..164.04 rows=176 width=68) (actual
time=2.350..2.566 rows=89 loops=1)
   Filter: ((prolang = '13'::oid) OR (prolang = '13'::oid) OR ((prolang
= '2'::oid) AND (prolang = '2'::oid)))
   Rows Removed by Filter: 3213
 Planning Time: 0.215 ms
 Execution Time: 2.624 ms
(5 rows)

Should have left:
Filter: ((prolang = '13'::oid) OR (prolang = '2'::oid))

*Falls into coredump at me:*
explain analyze SELECT p1.oid, p1.proname
FROM pg_proc as p1
WHERE prolang = 13 OR prolang = 2 AND prolang = 2 OR prolang = 13;

explain analyze SELECT p1.oid, p1.proname
FROM pg_proc as p1
WHERE prolang = 13 OR prolang=13 OR prolang = 2 AND prolang = 2;
                                                  QUERY PLAN
---------------------------------------------------------------------------------------------------------------
 Seq Scan on pg_proc p1  (cost=0.00..164.04 rows=176 width=68) (actual
time=2.350..2.566 rows=89 loops=1)
   Filter: ((prolang = '13'::oid) OR (prolang = '13'::oid) OR ((prolang
= '2'::oid) AND (prolang = '2'::oid)))
   Rows Removed by Filter: 3213
 Planning Time: 0.215 ms
 Execution Time: 2.624 ms

(5 rows)

I remind that initially the task was to find an opportunity to optimize
the case of processing a large number of "or" expressions to optimize
memory consumption. The FlameGraph for executing 50,000 "or"
expressionshas grown 1.4Gb and remains in this state until exiting the
psql session (flamegraph1.png) and it sagged a lot in execution time. If
this case is converted to ANY, the query is executed much faster and
memory is optimized (flamegraph2.png). It may be necessary to use this
approach if there is no support for the framework to process ANY, IN
expressions.

Peter Geoghegan also noticed some development of this patch in terms of
preparing some transformations to optimize the query at the stage of its
execution [0].

[0]
https://www.postgresql.org/message-id/CAH2-Wz%3D9N_4%2BEyhtyFqYQRx4OgVbP%2B1aoYU2JQPVogCir61ZEQ%40mail.gmail.com

[1]
https://www.postgresql.org/message-id/attachment/149105/v7-Replace-OR-clause-to-ANY-expressions.patch

Sorry for the duplicates, I received a letter that my letter did not
reach the addressee, I thought the design was incorrect.

On 26.09.2023 12:21, a.rybakina wrote:
>
> I'm sorry I didn't write for a long time, but I really had a very
> difficult month, now I'm fully back to work.
>
> *I was able to implement the patches to the end and moved the
> transformation of "OR" expressions to ANY.* I haven't seen a big
> difference between them yet, one has a transformation before
> calculating selectivity (v7.1-Replace-OR-clause-to-ANY.patch), the
> other after (v7.2-Replace-OR-clause-to-ANY.patch). Regression tests
> are passing, I don't see any problems with selectivity, nothing has
> fallen into the coredump, but I found some incorrect transformations.
> What is the reason for these inaccuracies, I have not found, but, to
> be honest, they look unusual). Gave the error below.
>
> In the patch, I don't like that I had to drag three libraries from
> parsing until I found a way around it.The advantage of this approach
> compared to the other ([1]) is that at this stage all possible or
> transformations are performed, compared to the patch, where the
> transformation was done at the parsing stage. That is, here, for
> example, there are such optimizations in the transformation:
>
>
> I took the common element out of the bracket and the rest is converted
> to ANY, while, as noted by Peter Geoghegan, we did not have several
> bitmapscans, but only one scan through the array.
>
> postgres=# explain analyze SELECT p1.oid, p1.proname
> FROM pg_proc as p1
> WHERE prolang = 13 AND prolang=1 OR prolang = 13 AND prolang = 2 OR
> prolang = 13 AND prolang = 3;
>                                               QUERY PLAN
> -------------------------------------------------------------------------------------------------------
>  Seq Scan on pg_proc p1  (cost=0.00..151.66 rows=1 width=68) (actual
> time=1.167..1.168 rows=0 loops=1)
>    Filter: ((prolang = '13'::oid) AND (prolang = ANY (ARRAY['1'::oid,
> '2'::oid, '3'::oid])))
>    Rows Removed by Filter: 3302
>  Planning Time: 0.146 ms
>  Execution Time: 1.191 ms
> (5 rows)
>
> *While I was testing, I found some transformations that don't work,
> although in my opinion, they should:**
> **
> **1. First case:*
> explain analyze SELECT p1.oid, p1.proname
> FROM pg_proc as p1
> WHERE prolang = 13 AND prolang=1 OR prolang = 2 AND prolang = 2 OR
> prolang = 13 AND prolang = 13;
> QUERY PLAN
> ----------------------------------------------------------------------------------------------------------------------------------------------------------------------
>  Seq Scan on pg_proc p1  (cost=0.00..180.55 rows=2 width=68) (actual
> time=2.959..3.335 rows=89 loops=1)
>    Filter: (((prolang = '13'::oid) AND (prolang = '1'::oid)) OR
> ((prolang = '2'::oid) AND (prolang = '2'::oid)) OR ((prolang =
> '13'::oid) AND (prolang = '13'::oid)))
>    Rows Removed by Filter: 3213
>  Planning Time: 1.278 ms
>  Execution Time: 3.486 ms
> (5 rows)
>
> Should have left only prolang = '13'::oid:
>
>                                               QUERY PLAN
> -------------------------------------------------------------------------------------------------------
>  Seq Scan on pg_proc p1  (cost=0.00..139.28 rows=1 width=68) (actual
> time=2.034..2.034 rows=0 loops=1)
>    Filter: ((prolang = '13'::oid ))
>    Rows Removed by Filter: 3302
>  Planning Time: 0.181 ms
>  Execution Time: 2.079 ms
> (5 rows)
>
> *2. Also does not work:*
> postgres=# explain analyze SELECT p1.oid, p1.proname
> FROM pg_proc as p1
> WHERE prolang = 13 OR prolang = 2 AND prolang = 2 OR prolang = 13;
>                                                   QUERY PLAN
> ---------------------------------------------------------------------------------------------------------------
>  Seq Scan on pg_proc p1  (cost=0.00..164.04 rows=176 width=68) (actual
> time=2.422..2.686 rows=89 loops=1)
>    Filter: ((prolang = '13'::oid) OR ((prolang = '2'::oid) AND
> (prolang = '2'::oid)) OR (prolang = '13'::oid))
>    Rows Removed by Filter: 3213
>  Planning Time: 1.370 ms
>  Execution Time: 2.799 ms
> (5 rows)
>
> Should have left:
> Filter: ((prolang = '13'::oid) OR (prolang = '2'::oid))
>
> *3. Or another:*
>
> explain analyze SELECT p1.oid, p1.proname
> FROM pg_proc as p1
> WHERE prolang = 13 OR prolang=13 OR prolang = 2 AND prolang = 2;
>                                                   QUERY PLAN
> ---------------------------------------------------------------------------------------------------------------
>  Seq Scan on pg_proc p1  (cost=0.00..164.04 rows=176 width=68) (actual
> time=2.350..2.566 rows=89 loops=1)
>    Filter: ((prolang = '13'::oid) OR (prolang = '13'::oid) OR
> ((prolang = '2'::oid) AND (prolang = '2'::oid)))
>    Rows Removed by Filter: 3213
>  Planning Time: 0.215 ms
>  Execution Time: 2.624 ms
> (5 rows)
>
> Should have left:
> Filter: ((prolang = '13'::oid) OR (prolang = '2'::oid))
>
>
> *Falls into coredump at me:*
> explain analyze SELECT p1.oid, p1.proname
> FROM pg_proc as p1
> WHERE prolang = 13 OR prolang = 2 AND prolang = 2 OR prolang = 13;
>
> explain analyze SELECT p1.oid, p1.proname
> FROM pg_proc as p1
> WHERE prolang = 13 OR prolang=13 OR prolang = 2 AND prolang = 2;
>                                                   QUERY PLAN
> ---------------------------------------------------------------------------------------------------------------
>  Seq Scan on pg_proc p1  (cost=0.00..164.04 rows=176 width=68) (actual
> time=2.350..2.566 rows=89 loops=1)
>    Filter: ((prolang = '13'::oid) OR (prolang = '13'::oid) OR
> ((prolang = '2'::oid) AND (prolang = '2'::oid)))
>    Rows Removed by Filter: 3213
>  Planning Time: 0.215 ms
>  Execution Time: 2.624 ms
>
> (5 rows)
>
>
> I remind that initially the task was to find an opportunity to
> optimize the case of processing a large number of "or" expressions to
> optimize memory consumption. The FlameGraph for executing 50,000 "or"
> expressionshas grown 1.4Gb and remains in this state until exiting the
> psql session (flamegraph1.png) and it sagged a lot in execution time.
> If this case is converted to ANY, the query is executed much faster
> and memory is optimized (flamegraph2.png). It may be necessary to use
> this approach if there is no support for the framework to process ANY,
> IN expressions.
>
>
> Peter Geoghegan also noticed some development of this patch in terms
> of preparing some transformations to optimize the query at the stage
> of its execution [0].
>
> [0]
> https://www.postgresql.org/message-id/CAH2-Wz%3D9N_4%2BEyhtyFqYQRx4OgVbP%2B1aoYU2JQPVogCir61ZEQ%40mail.gmail.com
>
> [1]
> https://www.postgresql.org/message-id/attachment/149105/v7-Replace-OR-clause-to-ANY-expressions.patch
>

> I'm sorry I didn't write for a long time, but I really had a very
> difficult month, now I'm fully back to work.
>
> *I was able to implement the patches to the end and moved the
> transformation of "OR" expressions to ANY.* I haven't seen a big
> difference between them yet, one has a transformation before
> calculating selectivity (v7.1-Replace-OR-clause-to-ANY.patch), the
> other after (v7.2-Replace-OR-clause-to-ANY.patch). Regression tests
> are passing, I don't see any problems with selectivity, nothing has
> fallen into the coredump, but I found some incorrect transformations.
> What is the reason for these inaccuracies, I have not found, but, to
> be honest, they look unusual). Gave the error below.
>
> In the patch, I don't like that I had to drag three libraries from
> parsing until I found a way around it.The advantage of this approach
> compared to the other ([1]) is that at this stage all possible or
> transformations are performed, compared to the patch, where the
> transformation was done at the parsing stage. That is, here, for
> example, there are such optimizations in the transformation:
>
>
> I took the common element out of the bracket and the rest is converted
> to ANY, while, as noted by Peter Geoghegan, we did not have several
> bitmapscans, but only one scan through the array.
>
> postgres=# explain analyze SELECT p1.oid, p1.proname
> FROM pg_proc as p1
> WHERE prolang = 13 AND prolang=1 OR prolang = 13 AND prolang = 2 OR
> prolang = 13 AND prolang = 3;
>                                               QUERY PLAN
> -------------------------------------------------------------------------------------------------------
>  Seq Scan on pg_proc p1  (cost=0.00..151.66 rows=1 width=68) (actual
> time=1.167..1.168 rows=0 loops=1)
>    Filter: ((prolang = '13'::oid) AND (prolang = ANY (ARRAY['1'::oid,
> '2'::oid, '3'::oid])))
>    Rows Removed by Filter: 3302
>  Planning Time: 0.146 ms
>  Execution Time: 1.191 ms
> (5 rows)
> *Falls into coredump at me:*
> explain analyze SELECT p1.oid, p1.proname
> FROM pg_proc as p1
> WHERE prolang = 13 OR prolang = 2 AND prolang = 2 OR prolang = 13;
>
I continue to try to move transformations of "OR" expressions at the
optimization stage, unfortunately I have not been able to figure out
coredump yet, but I saw an important thing that it is already necessary
to process RestrictInfo expressions here. I corrected it.

To be honest, despite some significant advantages in the fact that we
are already processing pre-converted "or" expressions (logical
transformations have been performed and duplicates have been removed), I
have big doubts about this approach. We already have quite a lot of
objects at this stage that can refer to the RestrictInfo variable in
ReplOptInfo, and updating these links can be costly for us. By the way,
right now I suspect that the current coredump appeared precisely because
there is a link somewhere that refers to an un-updated RestrictInfo, but
so far I can't find this place. coredump occurs at the request execution
stage, looks like this:

Core was generated by `postgres: alena regression [local]
SELECT                                     '.
--Type <RET> for more, q to quit, c to continue without paging--
Program terminated with signal SIGSEGV, Segmentation fault.
#0  0x00005565f3ec4947 in ExecInitExprRec (node=0x5565f530b290,
state=0x5565f53383d8, resv=0x5565f53383e0, resnull=0x5565f53383dd) at
execExpr.c:1331
1331                                            Expr       *arg = (Expr
*) lfirst(lc);
(gdb) bt
#0  0x00005565f3ec4947 in ExecInitExprRec (node=0x5565f530b290,
state=0x5565f53383d8, resv=0x5565f53383e0, resnull=0x5565f53383dd) at
execExpr.c:1331
#1  0x00005565f3ec2708 in ExecInitQual (qual=0x5565f531d950,
parent=0x5565f5337948) at execExpr.c:258
#2  0x00005565f3f2f080 in ExecInitSeqScan (node=0x5565f5309700,
estate=0x5565f5337700, eflags=32) at nodeSeqscan.c:172
#3  0x00005565f3ee70c9 in ExecInitNode (node=0x5565f5309700,
estate=0x5565f5337700, eflags=32) at execProcnode.c:210
#4  0x00005565f3edbe3a in InitPlan (queryDesc=0x5565f53372f0, eflags=32)
at execMain.c:968
#5  0x00005565f3edabe3 in standard_ExecutorStart
(queryDesc=0x5565f53372f0, eflags=32) at execMain.c:266
#6  0x00005565f3eda927 in ExecutorStart (queryDesc=0x5565f53372f0,
eflags=0) at execMain.c:145
#7  0x00005565f419921e in PortalStart (portal=0x5565f52ace90,
params=0x0, eflags=0, snapshot=0x0) at pquery.c:517
#8  0x00005565f4192635 in exec_simple_query (
    query_string=0x5565f5233af0 "SELECT p1.oid, p1.proname\nFROM
pg_proc as p1\nWHERE prolang = 13 AND (probin IS NULL OR probin = '' OR
probin = '-');") at postgres.c:1233
#9  0x00005565f41976ef in PostgresMain (dbname=0x5565f526ad10
"regression", username=0x5565f526acf8 "alena") at postgres.c:4652
#10 0x00005565f40b8417 in BackendRun (port=0x5565f525f830) at
postmaster.c:4439
#11 0x00005565f40b7ca3 in BackendStartup (port=0x5565f525f830) at
postmaster.c:4167
#12 0x00005565f40b40f1 in ServerLoop () at postmaster.c:1781
#13 0x00005565f40b399b in PostmasterMain (argc=8, argv=0x5565f522c110)
at postmaster.c:1465
#14 0x00005565f3f6560e in main (argc=8, argv=0x5565f522c110) at main.c:198

I have saved my experimental version of the "or" transfer in the diff
file, I am attaching the main patch in the ".patch" format so that the
tests are checked against this version. Let me remind you that the main
patch contains the code for converting "OR" expressions to "ANY" at the
parsing stage.

On 29.09.2023 20:35, a.rybakina wrote:
>>
>> I'm sorry I didn't write for a long time, but I really had a very
>> difficult month, now I'm fully back to work.
>>
>> *I was able to implement the patches to the end and moved the
>> transformation of "OR" expressions to ANY.* I haven't seen a big
>> difference between them yet, one has a transformation before
>> calculating selectivity (v7.1-Replace-OR-clause-to-ANY.patch), the
>> other after (v7.2-Replace-OR-clause-to-ANY.patch). Regression tests
>> are passing, I don't see any problems with selectivity, nothing has
>> fallen into the coredump, but I found some incorrect transformations.
>> What is the reason for these inaccuracies, I have not found, but, to
>> be honest, they look unusual). Gave the error below.
>>
>> In the patch, I don't like that I had to drag three libraries from
>> parsing until I found a way around it.The advantage of this approach
>> compared to the other ([1]) is that at this stage all possible or
>> transformations are performed, compared to the patch, where the
>> transformation was done at the parsing stage. That is, here, for
>> example, there are such optimizations in the transformation:
>>
>>
>> I took the common element out of the bracket and the rest is
>> converted to ANY, while, as noted by Peter Geoghegan, we did not have
>> several bitmapscans, but only one scan through the array.
>>
>> postgres=# explain analyze SELECT p1.oid, p1.proname
>> FROM pg_proc as p1
>> WHERE prolang = 13 AND prolang=1 OR prolang = 13 AND prolang = 2 OR
>> prolang = 13 AND prolang = 3;
>>                                               QUERY PLAN
>> -------------------------------------------------------------------------------------------------------
>>  Seq Scan on pg_proc p1  (cost=0.00..151.66 rows=1 width=68) (actual
>> time=1.167..1.168 rows=0 loops=1)
>>    Filter: ((prolang = '13'::oid) AND (prolang = ANY (ARRAY['1'::oid,
>> '2'::oid, '3'::oid])))
>>    Rows Removed by Filter: 3302
>>  Planning Time: 0.146 ms
>>  Execution Time: 1.191 ms
>> (5 rows)
>> *Falls into coredump at me:*
>> explain analyze SELECT p1.oid, p1.proname
>> FROM pg_proc as p1
>> WHERE prolang = 13 OR prolang = 2 AND prolang = 2 OR prolang = 13;
>>
>
Hi, all!

I fixed the kernel dump issue and all the regression tests were
successful, but I discovered another problem when I added my own
regression tests.
Some queries that contain "or" expressions do not convert to "ANY". I
have described this in more detail using diff as expected and real results:

diff -U3
/home/alena/postgrespro__copy6/src/test/regress/expected/create_index.out
/home/alena/postgrespro__copy6/src/test/regress/results/create_index.out
---
/home/alena/postgrespro__copy6/src/test/regress/expected/create_index.out
2023-10-04 21:54:12.496282667 +0300
+++
/home/alena/postgrespro__copy6/src/test/regress/results/create_index.out
2023-10-04 21:55:41.665422459 +0300
@@ -1925,17 +1925,20 @@
 EXPLAIN (COSTS OFF)
 SELECT count(*) FROM tenk1
   WHERE thousand = 42 AND (tenthous = 1 OR tenthous = 3) OR thousand = 41;
-                                               QUERY PLAN
---------------------------------------------------------------------------------------------------------
+                                                        QUERY PLAN
+---------------------------------------------------------------------------------------------------------------------------
  Aggregate
    ->  Bitmap Heap Scan on tenk1
-         Recheck Cond: (((thousand = 42) AND (tenthous = ANY
('{1,3}'::integer[]))) OR (thousand = 41))
+         Recheck Cond: ((((thousand = 42) AND (tenthous = 1)) OR
((thousand = 42) AND (tenthous = 3))) OR (thousand = 41))
          ->  BitmapOr
-               ->  Bitmap Index Scan on tenk1_thous_tenthous
-                     Index Cond: ((thousand = 42) AND (tenthous = ANY
('{1,3}'::integer[])))
+               ->  BitmapOr
+                     ->  Bitmap Index Scan on tenk1_thous_tenthous
+                           Index Cond: ((thousand = 42) AND (tenthous = 1))
+                     ->  Bitmap Index Scan on tenk1_thous_tenthous
+                           Index Cond: ((thousand = 42) AND (tenthous = 3))
                ->  Bitmap Index Scan on tenk1_thous_tenthous
                      Index Cond: (thousand = 41)
-(8 rows)
+(11 rows)
@@ -1946,24 +1949,50 @@
 EXPLAIN (COSTS OFF)
 SELECT count(*) FROM tenk1
+  WHERE thousand = 42 OR tenthous = 1 AND thousand = 42 OR tenthous = 1;
+                                            QUERY PLAN
+---------------------------------------------------------------------------------------------------
+ Aggregate
+   ->  Bitmap Heap Scan on tenk1
+         Recheck Cond: ((thousand = 42) OR ((thousand = 42) AND
(tenthous = 1)) OR (tenthous = 1))
+         ->  BitmapOr
+               ->  Bitmap Index Scan on tenk1_thous_tenthous
+                     Index Cond: (thousand = 42)
+               ->  Bitmap Index Scan on tenk1_thous_tenthous
+                     Index Cond: ((thousand = 42) AND (tenthous = 1))
+               ->  Bitmap Index Scan on tenk1_thous_tenthous
+                     Index Cond: (tenthous = 1)
+(10 rows)
+
+SELECT count(*) FROM tenk1
+  WHERE thousand = 42 OR tenthous = 1 AND thousand = 42 OR tenthous = 1;
+ count
+-------
+    11
+(1 row)
+
+EXPLAIN (COSTS OFF)
+SELECT count(*) FROM tenk1
   WHERE hundred = 42 AND (thousand = 42 OR thousand = 99 OR tenthous <
2) OR thousand = 41;
-                                                         QUERY PLAN
------------------------------------------------------------------------------------------------------------------------------
+                                                       QUERY PLAN
+------------------------------------------------------------------------------------------------------------------------
  Aggregate
    ->  Bitmap Heap Scan on tenk1
-         Recheck Cond: (((hundred = 42) AND ((tenthous < 2) OR
(thousand = ANY ('{42,99}'::integer[])))) OR (thousand = 41))
+         Recheck Cond: (((hundred = 42) AND ((thousand = 42) OR
(thousand = 99) OR (tenthous < 2))) OR (thousand = 41))
          ->  BitmapOr
                ->  BitmapAnd
                      ->  Bitmap Index Scan on tenk1_hundred
                            Index Cond: (hundred = 42)
                      ->  BitmapOr
                            ->  Bitmap Index Scan on tenk1_thous_tenthous
-                                 Index Cond: (tenthous < 2)
+                                 Index Cond: (thousand = 42)
                            ->  Bitmap Index Scan on tenk1_thous_tenthous
-                                 Index Cond: (thousand = ANY
('{42,99}'::integer[]))
+                                 Index Cond: (thousand = 99)
+                           ->  Bitmap Index Scan on tenk1_thous_tenthous
+                                 Index Cond: (tenthous < 2)
                ->  Bitmap Index Scan on tenk1_thous_tenthous
                      Index Cond: (thousand = 41)
-(14 rows)
+(16 rows)

diff -U3
/home/alena/postgrespro__copy6/src/test/regress/expected/join.out
/home/alena/postgrespro__copy6/src/test/regress/results/join.out
--- /home/alena/postgrespro__copy6/src/test/regress/expected/join.out
2023-10-04 21:53:55.632069079 +0300
+++ /home/alena/postgrespro__copy6/src/test/regress/results/join.out
2023-10-04 21:55:46.597485979 +0300
 explain (costs off)
 select * from tenk1 a join tenk1 b on
   (a.unique1 < 20 or a.unique1 = 3 or a.unique1 = 1 and b.unique1 = 2) or
   ((a.unique2 = 3 or a.unique2 = 7) and b.hundred = 4);
- QUERY PLAN
----------------------------------------------------------------------------------------------------------------------------------------------------------------
+ QUERY PLAN
+-------------------------------------------------------------------------------------------------------------------------------------------------------------
  Nested Loop
-   Join Filter: ((a.unique1 < 20) OR ((a.unique1 = 1) AND (b.unique1 =
2)) OR ((a.unique2 = ANY ('{3,7}'::integer[])) AND (b.hundred = 4)) OR
(a.unique1 = 3))
+   Join Filter: ((a.unique1 < 20) OR (a.unique1 = 3) OR ((a.unique1 =
1) AND (b.unique1 = 2)) OR (((a.unique2 = 3) OR (a.unique2 = 7)) AND
(b.hundred = 4)))
    ->  Seq Scan on tenk1 b
    ->  Materialize
          ->  Bitmap Heap Scan on tenk1 a
-               Recheck Cond: ((unique1 < 20) OR (unique1 = 1) OR
(unique2 = ANY ('{3,7}'::integer[])) OR (unique1 = 3))
+               Recheck Cond: ((unique1 < 20) OR (unique1 = 3) OR
(unique1 = 1) OR (unique2 = 3) OR (unique2 = 7))
                ->  BitmapOr
                      ->  Bitmap Index Scan on tenk1_unique1
                            Index Cond: (unique1 < 20)
                      ->  Bitmap Index Scan on tenk1_unique1
+                           Index Cond: (unique1 = 3)
+                     ->  Bitmap Index Scan on tenk1_unique1
                            Index Cond: (unique1 = 1)
                      ->  Bitmap Index Scan on tenk1_unique2
-                           Index Cond: (unique2 = ANY ('{3,7}'::integer[]))
-                     ->  Bitmap Index Scan on tenk1_unique1
-                           Index Cond: (unique1 = 3)
-(15 rows)
+                           Index Cond: (unique2 = 3)
+                     ->  Bitmap Index Scan on tenk1_unique2
+                           Index Cond: (unique2 = 7)
+(17 rows)

 explain (costs off)
 select * from tenk1 a join tenk1 b on
   (a.unique1 < 20 or a.unique1 = 3 or a.unique1 = 1 and b.unique1 = 2) or
   ((a.unique2 = 3 or a.unique2 = 7) and b.hundred = 4);
- QUERY PLAN
----------------------------------------------------------------------------------------------------------------------------------------------------------------
+ QUERY PLAN
+-------------------------------------------------------------------------------------------------------------------------------------------------------------
  Nested Loop
-   Join Filter: ((a.unique1 < 20) OR ((a.unique1 = 1) AND (b.unique1 =
2)) OR ((a.unique2 = ANY ('{3,7}'::integer[])) AND (b.hundred = 4)) OR
(a.unique1 = 3))
+   Join Filter: ((a.unique1 < 20) OR (a.unique1 = 3) OR ((a.unique1 =
1) AND (b.unique1 = 2)) OR (((a.unique2 = 3) OR (a.unique2 = 7)) AND
(b.hundred = 4)))
    ->  Seq Scan on tenk1 b
    ->  Materialize
          ->  Bitmap Heap Scan on tenk1 a
-               Recheck Cond: ((unique1 < 20) OR (unique1 = 1) OR
(unique2 = ANY ('{3,7}'::integer[])) OR (unique1 = 3))
+               Recheck Cond: ((unique1 < 20) OR (unique1 = 3) OR
(unique1 = 1) OR (unique2 = 3) OR (unique2 = 7))
                ->  BitmapOr
                      ->  Bitmap Index Scan on tenk1_unique1
                            Index Cond: (unique1 < 20)
                      ->  Bitmap Index Scan on tenk1_unique1
+                           Index Cond: (unique1 = 3)
+                     ->  Bitmap Index Scan on tenk1_unique1
                            Index Cond: (unique1 = 1)
                      ->  Bitmap Index Scan on tenk1_unique2
-                           Index Cond: (unique2 = ANY ('{3,7}'::integer[]))
-                     ->  Bitmap Index Scan on tenk1_unique1
-                           Index Cond: (unique1 = 3)
-(15 rows)
+                           Index Cond: (unique2 = 3)
+                     ->  Bitmap Index Scan on tenk1_unique2
+                           Index Cond: (unique2 = 7)
+(17 rows)

I haven't been able to fully deal with this problem yet

I have attached my experimental patch with the code.

Hi, Alena!

Thank you for your work on the subject.

On Wed, Oct 4, 2023 at 10:21 PM a.rybakina <a(dot)rybakina(at)postgrespro(dot)ru> wrote:
> I fixed the kernel dump issue and all the regression tests were successful, but I discovered another problem when I added my own regression tests.
> Some queries that contain "or" expressions do not convert to "ANY". I have described this in more detail using diff as expected and real results:
>
> diff -U3 /home/alena/postgrespro__copy6/src/test/regress/expected/create_index.out /home/alena/postgrespro__copy6/src/test/regress/results/create_index.out
> --- /home/alena/postgrespro__copy6/src/test/regress/expected/create_index.out 2023-10-04 21:54:12.496282667 +0300
> +++ /home/alena/postgrespro__copy6/src/test/regress/results/create_index.out 2023-10-04 21:55:41.665422459 +0300
> @@ -1925,17 +1925,20 @@
> EXPLAIN (COSTS OFF)
> SELECT count(*) FROM tenk1
> WHERE thousand = 42 AND (tenthous = 1 OR tenthous = 3) OR thousand = 41;
> - QUERY PLAN
> ---------------------------------------------------------------------------------------------------------
> + QUERY PLAN
> +---------------------------------------------------------------------------------------------------------------------------
> Aggregate
> -> Bitmap Heap Scan on tenk1
> - Recheck Cond: (((thousand = 42) AND (tenthous = ANY ('{1,3}'::integer[]))) OR (thousand = 41))
> + Recheck Cond: ((((thousand = 42) AND (tenthous = 1)) OR ((thousand = 42) AND (tenthous = 3))) OR (thousand = 41))
> -> BitmapOr
> - -> Bitmap Index Scan on tenk1_thous_tenthous
> - Index Cond: ((thousand = 42) AND (tenthous = ANY ('{1,3}'::integer[])))
> + -> BitmapOr
> + -> Bitmap Index Scan on tenk1_thous_tenthous
> + Index Cond: ((thousand = 42) AND (tenthous = 1))
> + -> Bitmap Index Scan on tenk1_thous_tenthous
> + Index Cond: ((thousand = 42) AND (tenthous = 3))
> -> Bitmap Index Scan on tenk1_thous_tenthous
> Index Cond: (thousand = 41)
> -(8 rows)
> +(11 rows)

I think this query is not converted, because you only convert
top-level ORs in the transform_ors() function. But in the example
given, the target OR lays under AND, which in turn lays under another
OR. I think you need to make transform_ors() recursive to handle
cases like this.

I wonder about the default value of the parameter or_transform_limit
of 500. In [1] and [2] you show the execution time degradation from 0
to ~500 OR clauses. I made a simple SQL script with the query "SELECT
* FROM pgbench_accounts a WHERE aid = 1 OR aid = 2 OR ... OR aid =
100;". The pgbench results for a single connection in prepared mode
are the following.
master: 936 tps
patched (or_transform_limit == 0) :1414 tps
So, transformation to ANY obviously accelerates the execution.

I think it's important to identify the cases where this patch causes
the degradation. Generally, I don't see why ANY could be executed
slower than the equivalent OR clause. So, the possible degradation
cases are slower plan generation and worse plans. I managed to find
both.

As you stated before, currently the OR transformation has a quadratic
complexity depending on the number of or-clause-groups. I made a
simple test to evaluate this. containing 10000 or-clause-groups.
SELECT * FROM pgbench_accounts a WHERE aid + 1 * bid = 1 OR aid + 2 *
bid = 1 OR ... OR aid + 10000 * bid = 1;
master: 316ms
patched: 7142ms
Note, that the current or_transform_limit GUC parameter is not capable
of cutting such cases, because it cuts cases lower than the limit not
higher than the limit. In the comment, you mention that we could
invent something like hash to handle this. Hash should be nice, but
the problem is that we currently don't have a generic facility to hash
nodes (or even order them). It would be nice to add this facility,
that would be quite a piece of work. I would propose to limit this
patch for now to handle just a single Var node as a non-const side of
the clause and implement a simple hash for Vars.

Another problem is the possible generation of worse plans. I made an
example table with two partial indexes.
create table test as (select (random()*10)::int x, (random()*1000) y
from generate_series(1,1000000) i);
create index test_x_1_y on test (y) where x = 1;
create index test_x_2_y on test (y) where x = 2;
vacuum analyze test;

Without the transformation of ORs to ANY, our planner manages to use
both indexes with a Bitmap scan.
# explain select * from test where (x = 1 or x = 2) and y = 100;
QUERY PLAN
--------------------------------------------------------------------------------------------------------------
Bitmap Heap Scan on test (cost=8.60..12.62 rows=1 width=12)
Recheck Cond: (((y = '100'::double precision) AND (x = 1)) OR ((y =
'100'::double precision) AND (x = 2)))
-> BitmapOr (cost=8.60..8.60 rows=1 width=0)
-> Bitmap Index Scan on test_x_1_y (cost=0.00..4.30 rows=1 width=0)
Index Cond: (y = '100'::double precision)
-> Bitmap Index Scan on test_x_2_y (cost=0.00..4.30 rows=1 width=0)
Index Cond: (y = '100'::double precision)
(7 rows)

With transformation, the planner can't use indexes.
# explain select * from test where (x = 1 or x = 2) and y = 100;
QUERY PLAN
-----------------------------------------------------------------------------
Gather (cost=1000.00..12690.10 rows=1 width=12)
Workers Planned: 2
-> Parallel Seq Scan on test (cost=0.00..11690.00 rows=1 width=12)
Filter: ((x = ANY (ARRAY[1, 2])) AND (y = '100'::double precision))
(4 rows)

The solution I see would be to tech Bitmap scan to handle ANY clause
in the same way as the OR clause. I think the entry point for the
relevant logic is the choose_bitmap_and() function.

Regarding the GUC parameter, I don't see we need a limit. It's not
yet clear whether a small number or a large number of OR clauses are
more favorable for transformation. I propose to have just a boolean
enable_or_transformation GUC.

Links
1. https://www.postgresql.org/message-id/6b97b517-f36a-f0c6-3b3a-0cf8cfba220c%40yandex.ru
2. https://www.postgresql.org/message-id/938d82e1-98df-6553-334c-9db7c4e288ae%40yandex.ru

------
Regards,
Alexander Korotkov

Hi! Thank you for your review!

On 15.10.2023 01:34, Alexander Korotkov wrote:
> Hi, Alena!
>
> Thank you for your work on the subject.
>
> On Wed, Oct 4, 2023 at 10:21 PM a.rybakina<a(dot)rybakina(at)postgrespro(dot)ru> wrote:
>> I fixed the kernel dump issue and all the regression tests were successful, but I discovered another problem when I added my own regression tests.
>> Some queries that contain "or" expressions do not convert to "ANY". I have described this in more detail using diff as expected and real results:
>>
>> diff -U3 /home/alena/postgrespro__copy6/src/test/regress/expected/create_index.out /home/alena/postgrespro__copy6/src/test/regress/results/create_index.out
>> --- /home/alena/postgrespro__copy6/src/test/regress/expected/create_index.out 2023-10-04 21:54:12.496282667 +0300
>> +++ /home/alena/postgrespro__copy6/src/test/regress/results/create_index.out 2023-10-04 21:55:41.665422459 +0300
>> @@ -1925,17 +1925,20 @@
>> EXPLAIN (COSTS OFF)
>> SELECT count(*) FROM tenk1
>> WHERE thousand = 42 AND (tenthous = 1 OR tenthous = 3) OR thousand = 41;
>> - QUERY PLAN
>> ---------------------------------------------------------------------------------------------------------
>> + QUERY PLAN
>> +---------------------------------------------------------------------------------------------------------------------------
>> Aggregate
>> -> Bitmap Heap Scan on tenk1
>> - Recheck Cond: (((thousand = 42) AND (tenthous = ANY ('{1,3}'::integer[]))) OR (thousand = 41))
>> + Recheck Cond: ((((thousand = 42) AND (tenthous = 1)) OR ((thousand = 42) AND (tenthous = 3))) OR (thousand = 41))
>> -> BitmapOr
>> - -> Bitmap Index Scan on tenk1_thous_tenthous
>> - Index Cond: ((thousand = 42) AND (tenthous = ANY ('{1,3}'::integer[])))
>> + -> BitmapOr
>> + -> Bitmap Index Scan on tenk1_thous_tenthous
>> + Index Cond: ((thousand = 42) AND (tenthous = 1))
>> + -> Bitmap Index Scan on tenk1_thous_tenthous
>> + Index Cond: ((thousand = 42) AND (tenthous = 3))
>> -> Bitmap Index Scan on tenk1_thous_tenthous
>> Index Cond: (thousand = 41)
>> -(8 rows)
>> +(11 rows)
> I think this query is not converted, because you only convert
> top-level ORs in the transform_ors() function. But in the example
> given, the target OR lays under AND, which in turn lays under another
> OR. I think you need to make transform_ors() recursive to handle
> cases like this.
Yes, you are right, it seems that a recursive method is needed here.
> I wonder about the default value of the parameter or_transform_limit
> of 500. In [1] and [2] you show the execution time degradation from 0
> to ~500 OR clauses. I made a simple SQL script with the query "SELECT
> * FROM pgbench_accounts a WHERE aid = 1 OR aid = 2 OR ... OR aid =
> 100;". The pgbench results for a single connection in prepared mode
> are the following.
> master: 936 tps
> patched (or_transform_limit == 0) :1414 tps
> So, transformation to ANY obviously accelerates the execution.
>
> I think it's important to identify the cases where this patch causes
> the degradation. Generally, I don't see why ANY could be executed
> slower than the equivalent OR clause. So, the possible degradation
> cases are slower plan generation and worse plans. I managed to find
> both.
>
> As you stated before, currently the OR transformation has a quadratic
> complexity depending on the number of or-clause-groups. I made a
> simple test to evaluate this. containing 10000 or-clause-groups.
> SELECT * FROM pgbench_accounts a WHERE aid + 1 * bid = 1 OR aid + 2 *
> bid = 1 OR ... OR aid + 10000 * bid = 1;
> master: 316ms
> patched: 7142ms
> Note, that the current or_transform_limit GUC parameter is not capable
> of cutting such cases, because it cuts cases lower than the limit not
> higher than the limit. In the comment, you mention that we could
> invent something like hash to handle this. Hash should be nice, but
> the problem is that we currently don't have a generic facility to hash
> nodes (or even order them). It would be nice to add this facility,
> that would be quite a piece of work. I would propose to limit this
> patch for now to handle just a single Var node as a non-const side of
> the clause and implement a simple hash for Vars.
I ran the query and saw that you were right, this place in the patch
turns out to be very expensive. In addition to the hash, I saw a second
solution to this problem - parameterize constants and store them in the
list, but this will not be such a universal solution as hashing. If the
variable, not the constant, changes, parameterization will not help.

I agree with your suggestion to try adding hashing. I'll take a closer
look at this.

> Another problem is the possible generation of worse plans. I made an
> example table with two partial indexes.
> create table test as (select (random()*10)::int x, (random()*1000) y
> from generate_series(1,1000000) i);
> create index test_x_1_y on test (y) where x = 1;
> create index test_x_2_y on test (y) where x = 2;
> vacuum analyze test;
>
> Without the transformation of ORs to ANY, our planner manages to use
> both indexes with a Bitmap scan.
> # explain select * from test where (x = 1 or x = 2) and y = 100;
> QUERY PLAN
> --------------------------------------------------------------------------------------------------------------
> Bitmap Heap Scan on test (cost=8.60..12.62 rows=1 width=12)
> Recheck Cond: (((y = '100'::double precision) AND (x = 1)) OR ((y =
> '100'::double precision) AND (x = 2)))
> -> BitmapOr (cost=8.60..8.60 rows=1 width=0)
> -> Bitmap Index Scan on test_x_1_y (cost=0.00..4.30 rows=1 width=0)
> Index Cond: (y = '100'::double precision)
> -> Bitmap Index Scan on test_x_2_y (cost=0.00..4.30 rows=1 width=0)
> Index Cond: (y = '100'::double precision)
> (7 rows)
>
> With transformation, the planner can't use indexes.
> # explain select * from test where (x = 1 or x = 2) and y = 100;
> QUERY PLAN
> -----------------------------------------------------------------------------
> Gather (cost=1000.00..12690.10 rows=1 width=12)
> Workers Planned: 2
> -> Parallel Seq Scan on test (cost=0.00..11690.00 rows=1 width=12)
> Filter: ((x = ANY (ARRAY[1, 2])) AND (y = '100'::double precision))
> (4 rows)
>
> The solution I see would be to tech Bitmap scan to handle ANY clause
> in the same way as the OR clause. I think the entry point for the
> relevant logic is the choose_bitmap_and() function.
It's a good idea, I'll try.
But to be honest, I'm afraid that problems with selectivity may come up
again and in order to solve them, additional processing of RestrictInfo
may be required, which will be unnecessarily expensive. As far as I
understand, at this stage we are creating indexes for AND expressions
and there is a risk that its transformation may cause the need to change
references in all possible places where it was referenced.
> Regarding the GUC parameter, I don't see we need a limit. It's not
> yet clear whether a small number or a large number of OR clauses are
> more favorable for transformation. I propose to have just a boolean
> enable_or_transformation GUC.
>
> Links
> 1.https://www.postgresql.org/message-id/6b97b517-f36a-f0c6-3b3a-0cf8cfba220c%40yandex.ru
> 2.https://www.postgresql.org/message-id/938d82e1-98df-6553-334c-9db7c4e288ae%40yandex.ru

I tend to agree with you and I see that in some cases it really doesn't
help.