public inbox for [email protected]
help / color / mirror / Atom feedPOC, WIP: OR-clause support for indexes
29+ messages / 14 participants
[nested] [flat]
* POC, WIP: OR-clause support for indexes
@ 2015-12-26 18:04 Teodor Sigaev <[email protected]>
2015-12-26 18:40 ` Re: POC, WIP: OR-clause support for indexes Feng Tian <[email protected]>
2016-01-11 03:16 ` Re: POC, WIP: OR-clause support for indexes David Rowley <[email protected]>
2022-12-28 04:19 ` Re: POC, WIP: OR-clause support for indexes Andrey Lepikhov <[email protected]>
2024-01-27 02:58 ` Re: POC, WIP: OR-clause support for indexes vignesh C <[email protected]>
2024-01-30 14:15 ` Re: POC, WIP: OR-clause support for indexes jian he <[email protected]>
2025-03-24 10:10 ` Re: POC, WIP: OR-clause support for indexes Andrei Lepikhov <[email protected]>
0 siblings, 6 replies; 29+ messages in thread
From: Teodor Sigaev @ 2015-12-26 18:04 UTC (permalink / raw)
To: pgsql-hackers
I'd like to present OR-clause support for indexes. Although OR-clauses could be
supported by bitmapOR index scan it isn't very effective and such scan lost any
order existing in index. We (with Alexander Korotkov) presented results on
Vienna's conference this year. In short, it provides performance improvement:
EXPLAIN ANALYZE
SELECT count(*) FROM tst WHERE id = 5 OR id = 500 OR id = 5000;
me=0.080..0.267 rows=173 loops=1)
Recheck Cond: ((id = 5) OR (id = 500) OR (id = 5000))
Heap Blocks: exact=172
-> Bitmap Index Scan on idx_gin (cost=0.00..57.50 rows=15000
width=0) (actual time=0.059..0.059 rows=147 loops=1)
Index Cond: ((id = 5) OR (id = 500) OR (id = 5000))
Planning time: 0.077 ms
Execution time: 0.308 ms <-------
QUERY PLAN
-----------------------------------------------------------------------------------------------------------------------------------
Aggregate (cost=51180.53..51180.54 rows=1 width=0) (actual
time=796.766..796.766 rows=1 loops=1)
-> Index Only Scan using idx_btree on tst (cost=0.42..51180.40 rows=55
width=0) (actual time=0.444..796.736 rows=173 loops=1)
Filter: ((id = 5) OR (id = 500) OR (id = 5000))
Rows Removed by Filter: 999829
Heap Fetches: 1000002
Planning time: 0.087 ms
Execution time: 796.798 ms <------
QUERY PLAN
-------------------------------------------------------------------------------------------------------------
Aggregate (cost=21925.63..21925.64 rows=1 width=0) (actual
time=160.412..160.412 rows=1 loops=1)
-> Seq Scan on tst (cost=0.00..21925.03 rows=237 width=0) (actual
time=0.535..160.362 rows=175 loops=1)
Filter: ((id = 5) OR (id = 500) OR (id = 5000))
Rows Removed by Filter: 999827
Planning time: 0.459 ms
Execution time: 160.451 ms
It also could work together with KNN feature of GiST and in this case
performance improvement could be up to several orders of magnitude, in
artificial example it was 37000 times faster.
Not all indexes can support oR-clause, patch adds support to GIN, GiST and BRIN
indexes. pg_am table is extended for adding amcanorclause column which indicates
possibility of executing of OR-clause by index.
indexqual and indexqualorig doesn't contain implicitly-ANDed list of index
qual expressions, now that lists could contain OR RestrictionInfo. Actually, the
patch just tries to convert BitmapOr node to IndexScan or IndexOnlyScan. Thats
significantly simplifies logic to find possible clause's list for index.
Index always gets a array of ScanKey but for indexes which support OR-clauses
array of ScanKey is actually exection tree in reversed polish notation form.
Transformation is done in ExecInitIndexScan().
The problems on the way which I see for now:
1 Calculating cost. Right now it's just a simple transformation of costs
computed for BitmapOr path. I'd like to hope that's possible and so index's
estimation function could be non-touched. So, they could believe that all
clauses are implicitly-ANDed
2 I'd like to add such support to btree but it seems that it should be a
separated patch. Btree search algorithm doesn't use any kind of stack of pages
and algorithm to walk over btree doesn't clear for me for now.
3 I could miss some places which still assumes implicitly-ANDed list of clauses
although regression tests passes fine.
Hope, hackers will not have an strong objections to do that. But obviously patch
requires further work and I'd like to see comments, suggestions and
recommendations. Thank you.
--
Teodor Sigaev E-mail: [email protected]
WWW: http://www.sigaev.ru/
--
Sent via pgsql-hackers mailing list ([email protected])
To make changes to your subscription:
http://www.postgresql.org/mailpref/pgsql-hackers
Attachments:
[application/x-gzip] index_or-1.patch.gz (19.3K, ../../[email protected]/2-index_or-1.patch.gz)
download
^ permalink raw reply [nested|flat] 29+ messages in thread
* Re: POC, WIP: OR-clause support for indexes
2015-12-26 18:04 POC, WIP: OR-clause support for indexes Teodor Sigaev <[email protected]>
@ 2015-12-26 18:40 ` Feng Tian <[email protected]>
2015-12-26 19:25 ` Re: POC, WIP: OR-clause support for indexes Teodor Sigaev <[email protected]>
5 siblings, 1 reply; 29+ messages in thread
From: Feng Tian @ 2015-12-26 18:40 UTC (permalink / raw)
To: Teodor Sigaev <[email protected]>; +Cc: pgsql-hackers
Hi, Teodor,
This is great. I got a question, is it possible make btree index to
support OR as well? Is btree supports more invasive, in the sense that we
need to do enhance ScanKey to supports an array of values?
Thanks,
Feng
On Sat, Dec 26, 2015 at 10:04 AM, Teodor Sigaev <[email protected]> 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: [email protected]
> WWW:
> http://www.sigaev.ru/
>
>
> --
> Sent via pgsql-hackers mailing list ([email protected])
> To make changes to your subscription:
> http://www.postgresql.org/mailpref/pgsql-hackers
>
>
^ permalink raw reply [nested|flat] 29+ messages in thread
* Re: POC, WIP: OR-clause support for indexes
2015-12-26 18:04 POC, WIP: OR-clause support for indexes Teodor Sigaev <[email protected]>
2015-12-26 18:40 ` Re: POC, WIP: OR-clause support for indexes Feng Tian <[email protected]>
@ 2015-12-26 19:25 ` Teodor Sigaev <[email protected]>
0 siblings, 0 replies; 29+ messages in thread
From: Teodor Sigaev @ 2015-12-26 19:25 UTC (permalink / raw)
To: Feng Tian <[email protected]>; +Cc: 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: [email protected]
WWW: http://www.sigaev.ru/
--
Sent via pgsql-hackers mailing list ([email protected])
To make changes to your subscription:
http://www.postgresql.org/mailpref/pgsql-hackers
^ permalink raw reply [nested|flat] 29+ messages in thread
* Re: POC, WIP: OR-clause support for indexes
2015-12-26 18:04 POC, WIP: OR-clause support for indexes Teodor Sigaev <[email protected]>
@ 2016-01-11 03:16 ` David Rowley <[email protected]>
2016-01-28 11:16 ` Re: POC, WIP: OR-clause support for indexes Alvaro Herrera <[email protected]>
2016-02-29 18:04 ` Re: POC, WIP: OR-clause support for indexes Teodor Sigaev <[email protected]>
5 siblings, 2 replies; 29+ messages in thread
From: David Rowley @ 2016-01-11 03:16 UTC (permalink / raw)
To: Teodor Sigaev <[email protected]>; +Cc: pgsql-hackers
On 27 December 2015 at 07:04, Teodor Sigaev <[email protected]> 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
^ permalink raw reply [nested|flat] 29+ messages in thread
* Re: POC, WIP: OR-clause support for indexes
2015-12-26 18:04 POC, WIP: OR-clause support for indexes Teodor Sigaev <[email protected]>
2016-01-11 03:16 ` Re: POC, WIP: OR-clause support for indexes David Rowley <[email protected]>
@ 2016-01-28 11:16 ` Alvaro Herrera <[email protected]>
1 sibling, 0 replies; 29+ messages in thread
From: Alvaro Herrera @ 2016-01-28 11:16 UTC (permalink / raw)
To: David Rowley <[email protected]>; +Cc: Teodor Sigaev <[email protected]>; pgsql-hackers
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
--
Sent via pgsql-hackers mailing list ([email protected])
To make changes to your subscription:
http://www.postgresql.org/mailpref/pgsql-hackers
^ permalink raw reply [nested|flat] 29+ messages in thread
* Re: POC, WIP: OR-clause support for indexes
2015-12-26 18:04 POC, WIP: OR-clause support for indexes Teodor Sigaev <[email protected]>
2016-01-11 03:16 ` Re: POC, WIP: OR-clause support for indexes David Rowley <[email protected]>
@ 2016-02-29 18:04 ` Teodor Sigaev <[email protected]>
2016-03-10 13:04 ` Re: POC, WIP: OR-clause support for indexes Tomas Vondra <[email protected]>
1 sibling, 1 reply; 29+ messages in thread
From: Teodor Sigaev @ 2016-02-29 18:04 UTC (permalink / raw)
To: David Rowley <[email protected]>; +Cc: pgsql-hackers
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: [email protected]
WWW: http://www.sigaev.ru/
--
Sent via pgsql-hackers mailing list ([email protected])
To make changes to your subscription:
http://www.postgresql.org/mailpref/pgsql-hackers
Attachments:
[application/x-gzip] index_or-2.patch.gz (21.5K, ../../[email protected]/2-index_or-2.patch.gz)
download
^ permalink raw reply [nested|flat] 29+ messages in thread
* Re: POC, WIP: OR-clause support for indexes
2015-12-26 18:04 POC, WIP: OR-clause support for indexes Teodor Sigaev <[email protected]>
2016-01-11 03:16 ` Re: POC, WIP: OR-clause support for indexes David Rowley <[email protected]>
2016-02-29 18:04 ` Re: POC, WIP: OR-clause support for indexes Teodor Sigaev <[email protected]>
@ 2016-03-10 13:04 ` Tomas Vondra <[email protected]>
2016-03-17 17:19 ` Re: POC, WIP: OR-clause support for indexes Teodor Sigaev <[email protected]>
2016-03-18 16:38 ` Re: POC, WIP: OR-clause support for indexes Teodor Sigaev <[email protected]>
0 siblings, 2 replies; 29+ messages in thread
From: Tomas Vondra @ 2016-03-10 13:04 UTC (permalink / raw)
To: Teodor Sigaev <[email protected]>; +Cc: David Rowley <[email protected]>; pgsql-hackers
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
--
Sent via pgsql-hackers mailing list ([email protected])
To make changes to your subscription:
http://www.postgresql.org/mailpref/pgsql-hackers
^ permalink raw reply [nested|flat] 29+ messages in thread
* Re: POC, WIP: OR-clause support for indexes
2015-12-26 18:04 POC, WIP: OR-clause support for indexes Teodor Sigaev <[email protected]>
2016-01-11 03:16 ` Re: POC, WIP: OR-clause support for indexes David Rowley <[email protected]>
2016-02-29 18:04 ` Re: POC, WIP: OR-clause support for indexes Teodor Sigaev <[email protected]>
2016-03-10 13:04 ` Re: POC, WIP: OR-clause support for indexes Tomas Vondra <[email protected]>
@ 2016-03-17 17:19 ` Teodor Sigaev <[email protected]>
2016-03-20 00:44 ` Re: POC, WIP: OR-clause support for indexes Tomas Vondra <[email protected]>
1 sibling, 1 reply; 29+ messages in thread
From: Teodor Sigaev @ 2016-03-17 17:19 UTC (permalink / raw)
To: Tomas Vondra <[email protected]>; +Cc: David Rowley <[email protected]>; pgsql-hackers
> 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: [email protected]
WWW: http://www.sigaev.ru/
--
Sent via pgsql-hackers mailing list ([email protected])
To make changes to your subscription:
http://www.postgresql.org/mailpref/pgsql-hackers
Attachments:
[application/x-gzip] index_or-3.patch.gz (20.2K, ../../[email protected]/2-index_or-3.patch.gz)
download
^ permalink raw reply [nested|flat] 29+ messages in thread
* Re: POC, WIP: OR-clause support for indexes
2015-12-26 18:04 POC, WIP: OR-clause support for indexes Teodor Sigaev <[email protected]>
2016-01-11 03:16 ` Re: POC, WIP: OR-clause support for indexes David Rowley <[email protected]>
2016-02-29 18:04 ` Re: POC, WIP: OR-clause support for indexes Teodor Sigaev <[email protected]>
2016-03-10 13:04 ` Re: POC, WIP: OR-clause support for indexes Tomas Vondra <[email protected]>
2016-03-17 17:19 ` Re: POC, WIP: OR-clause support for indexes Teodor Sigaev <[email protected]>
@ 2016-03-20 00:44 ` Tomas Vondra <[email protected]>
2016-03-25 15:13 ` Re: POC, WIP: OR-clause support for indexes David Steele <[email protected]>
0 siblings, 1 reply; 29+ messages in thread
From: Tomas Vondra @ 2016-03-20 00:44 UTC (permalink / raw)
To: Teodor Sigaev <[email protected]>; +Cc: David Rowley <[email protected]>; pgsql-hackers
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
--
Sent via pgsql-hackers mailing list ([email protected])
To make changes to your subscription:
http://www.postgresql.org/mailpref/pgsql-hackers
^ permalink raw reply [nested|flat] 29+ messages in thread
* Re: POC, WIP: OR-clause support for indexes
2015-12-26 18:04 POC, WIP: OR-clause support for indexes Teodor Sigaev <[email protected]>
2016-01-11 03:16 ` Re: POC, WIP: OR-clause support for indexes David Rowley <[email protected]>
2016-02-29 18:04 ` Re: POC, WIP: OR-clause support for indexes Teodor Sigaev <[email protected]>
2016-03-10 13:04 ` Re: POC, WIP: OR-clause support for indexes Tomas Vondra <[email protected]>
2016-03-17 17:19 ` Re: POC, WIP: OR-clause support for indexes Teodor Sigaev <[email protected]>
2016-03-20 00:44 ` Re: POC, WIP: OR-clause support for indexes Tomas Vondra <[email protected]>
@ 2016-03-25 15:13 ` David Steele <[email protected]>
2016-03-29 14:01 ` Re: POC, WIP: OR-clause support for indexes David Steele <[email protected]>
0 siblings, 1 reply; 29+ messages in thread
From: David Steele @ 2016-03-25 15:13 UTC (permalink / raw)
To: Teodor Sigaev <[email protected]>; +Cc: Tomas Vondra <[email protected]>; David Rowley <[email protected]>; pgsql-hackers; Andres Freund <[email protected]>
Hi Teador,
On 3/19/16 8:44 PM, Tomas Vondra wrote:
> Sadly the v4 does not work for me - I do get assertion failures.
Time is growing short and there seem to be some serious concerns with
this patch. Can you provide a new patch soon? If not, I think it might
be be time to mark this "returned with feedback".
Thanks,
--
-David
[email protected]
--
Sent via pgsql-hackers mailing list ([email protected])
To make changes to your subscription:
http://www.postgresql.org/mailpref/pgsql-hackers
^ permalink raw reply [nested|flat] 29+ messages in thread
* Re: POC, WIP: OR-clause support for indexes
2015-12-26 18:04 POC, WIP: OR-clause support for indexes Teodor Sigaev <[email protected]>
2016-01-11 03:16 ` Re: POC, WIP: OR-clause support for indexes David Rowley <[email protected]>
2016-02-29 18:04 ` Re: POC, WIP: OR-clause support for indexes Teodor Sigaev <[email protected]>
2016-03-10 13:04 ` Re: POC, WIP: OR-clause support for indexes Tomas Vondra <[email protected]>
2016-03-17 17:19 ` Re: POC, WIP: OR-clause support for indexes Teodor Sigaev <[email protected]>
2016-03-20 00:44 ` Re: POC, WIP: OR-clause support for indexes Tomas Vondra <[email protected]>
2016-03-25 15:13 ` Re: POC, WIP: OR-clause support for indexes David Steele <[email protected]>
@ 2016-03-29 14:01 ` David Steele <[email protected]>
0 siblings, 0 replies; 29+ messages in thread
From: David Steele @ 2016-03-29 14:01 UTC (permalink / raw)
To: Teodor Sigaev <[email protected]>; +Cc: Tomas Vondra <[email protected]>; David Rowley <[email protected]>; pgsql-hackers; Andres Freund <[email protected]>
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
[email protected]
--
Sent via pgsql-hackers mailing list ([email protected])
To make changes to your subscription:
http://www.postgresql.org/mailpref/pgsql-hackers
^ permalink raw reply [nested|flat] 29+ messages in thread
* Re: POC, WIP: OR-clause support for indexes
2015-12-26 18:04 POC, WIP: OR-clause support for indexes Teodor Sigaev <[email protected]>
2016-01-11 03:16 ` Re: POC, WIP: OR-clause support for indexes David Rowley <[email protected]>
2016-02-29 18:04 ` Re: POC, WIP: OR-clause support for indexes Teodor Sigaev <[email protected]>
2016-03-10 13:04 ` Re: POC, WIP: OR-clause support for indexes Tomas Vondra <[email protected]>
@ 2016-03-18 16:38 ` Teodor Sigaev <[email protected]>
2016-03-18 23:46 ` Re: POC, WIP: OR-clause support for indexes Andreas Karlsson <[email protected]>
1 sibling, 1 reply; 29+ messages in thread
From: Teodor Sigaev @ 2016-03-18 16:38 UTC (permalink / raw)
To: Tomas Vondra <[email protected]>; +Cc: David Rowley <[email protected]>; pgsql-hackers
> 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: [email protected]
WWW: http://www.sigaev.ru/
--
Sent via pgsql-hackers mailing list ([email protected])
To make changes to your subscription:
http://www.postgresql.org/mailpref/pgsql-hackers
Attachments:
[application/x-gzip] 0001-idx_or_core-v4.patch.gz (8.3K, ../../[email protected]/2-0001-idx_or_core-v4.patch.gz)
download
[application/x-gzip] 0002-idx_or_indexes-v4.patch.gz (13.1K, ../../[email protected]/3-0002-idx_or_indexes-v4.patch.gz)
download
^ permalink raw reply [nested|flat] 29+ messages in thread
* Re: POC, WIP: OR-clause support for indexes
2015-12-26 18:04 POC, WIP: OR-clause support for indexes Teodor Sigaev <[email protected]>
2016-01-11 03:16 ` Re: POC, WIP: OR-clause support for indexes David Rowley <[email protected]>
2016-02-29 18:04 ` Re: POC, WIP: OR-clause support for indexes Teodor Sigaev <[email protected]>
2016-03-10 13:04 ` Re: POC, WIP: OR-clause support for indexes Tomas Vondra <[email protected]>
2016-03-18 16:38 ` Re: POC, WIP: OR-clause support for indexes Teodor Sigaev <[email protected]>
@ 2016-03-18 23:46 ` Andreas Karlsson <[email protected]>
0 siblings, 0 replies; 29+ messages in thread
From: Andreas Karlsson @ 2016-03-18 23:46 UTC (permalink / raw)
To: Teodor Sigaev <[email protected]>; Tomas Vondra <[email protected]>; +Cc: David Rowley <[email protected]>; pgsql-hackers
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
--
Sent via pgsql-hackers mailing list ([email protected])
To make changes to your subscription:
http://www.postgresql.org/mailpref/pgsql-hackers
^ permalink raw reply [nested|flat] 29+ messages in thread
* Re: POC, WIP: OR-clause support for indexes
2015-12-26 18:04 POC, WIP: OR-clause support for indexes Teodor Sigaev <[email protected]>
@ 2022-12-28 04:19 ` Andrey Lepikhov <[email protected]>
5 siblings, 0 replies; 29+ messages in thread
From: Andrey Lepikhov @ 2022-12-28 04:19 UTC (permalink / raw)
To: Teodor Sigaev <[email protected]>; pgsql-hackers; +Cc: a.rybakina <[email protected]>
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
Attachments:
[application/sql] demo.sql (567B, ../../[email protected]/2-demo.sql)
download
^ permalink raw reply [nested|flat] 29+ messages in thread
* Re: POC, WIP: OR-clause support for indexes
2015-12-26 18:04 POC, WIP: OR-clause support for indexes Teodor Sigaev <[email protected]>
@ 2024-01-27 02:58 ` vignesh C <[email protected]>
5 siblings, 0 replies; 29+ messages in thread
From: vignesh C @ 2024-01-27 02:58 UTC (permalink / raw)
To: Andrei Lepikhov <[email protected]>; +Cc: Alena Rybakina <[email protected]>; Robert Haas <[email protected]>; pgsql-hackers; Alexander Korotkov <[email protected]>; Peter Geoghegan <[email protected]>; Finnerty, Jim <[email protected]>; Marcos Pegoraro <[email protected]>; [email protected]; Ranier Vilela <[email protected]>; Tomas Vondra <[email protected]>; Peter Eisentraut <[email protected]>
On Tue, 5 Dec 2023 at 16:25, Andrei Lepikhov <[email protected]> wrote:
>
> Here is fresh version with the pg_dump.pl regex fixed. Now it must pass
> buildfarm.
>
> Under development:
> 1. Explanation of the general idea in comments (Robert's note)
> 2. Issue with hiding some optimizations (Alexander's note and example
> with overlapping clauses on two partial indexes)
CFBot shows that the patch does not apply anymore as in [1]:
=== Applying patches on top of PostgreSQL commit ID
64444ce071f6b04d3fc836f436fa08108a6d11e2 ===
=== applying patch ./v14-1-0001-Transform-OR-clause-to-ANY-expressions.patch
....
patching file src/test/regress/expected/sysviews.out
Hunk #1 succeeded at 124 (offset 1 line).
Hunk #2 FAILED at 134.
1 out of 2 hunks FAILED -- saving rejects to file
src/test/regress/expected/sysviews.out.rej
Please post an updated version for the same.
[1] - http://cfbot.cputube.org/patch_46_4450.log
Regards,
Vignesh
^ permalink raw reply [nested|flat] 29+ messages in thread
* Re: POC, WIP: OR-clause support for indexes
2015-12-26 18:04 POC, WIP: OR-clause support for indexes Teodor Sigaev <[email protected]>
@ 2024-01-30 14:15 ` jian he <[email protected]>
2024-01-31 02:55 ` Re: POC, WIP: OR-clause support for indexes jian he <[email protected]>
5 siblings, 1 reply; 29+ messages in thread
From: jian he @ 2024-01-30 14:15 UTC (permalink / raw)
To: Andrei Lepikhov <[email protected]>; +Cc: Alena Rybakina <[email protected]>; Robert Haas <[email protected]>; pgsql-hackers; Alexander Korotkov <[email protected]>; Peter Geoghegan <[email protected]>; Finnerty, Jim <[email protected]>; Marcos Pegoraro <[email protected]>; [email protected]; Ranier Vilela <[email protected]>; Tomas Vondra <[email protected]>; Peter Eisentraut <[email protected]>
On Tue, Dec 5, 2023 at 6:55 PM Andrei Lepikhov
<[email protected]> wrote:
>
> Here is fresh version with the pg_dump.pl regex fixed. Now it must pass
> buildfarm.
+JumbleState *
+JumbleExpr(Expr *expr, uint64 *queryId)
+{
+ JumbleState *jstate = NULL;
+
+ Assert(queryId != NULL);
+
+ jstate = (JumbleState *) palloc(sizeof(JumbleState));
+
+ /* Set up workspace for query jumbling */
+ jstate->jumble = (unsigned char *) palloc(JUMBLE_SIZE);
+ jstate->jumble_len = 0;
+ jstate->clocations_buf_size = 32;
+ jstate->clocations = (LocationLen *)
+ palloc(jstate->clocations_buf_size * sizeof(LocationLen));
+ jstate->clocations_count = 0;
+ jstate->highest_extern_param_id = 0;
+
+ /* Compute query ID */
+ _jumbleNode(jstate, (Node *) expr);
+ *queryId = DatumGetUInt64(hash_any_extended(jstate->jumble,
+ jstate->jumble_len,
+ 0));
+
+ if (*queryId == UINT64CONST(0))
+ *queryId = UINT64CONST(1);
+
+ return jstate;
+}
+/*
+ * Hash function that's compatible with guc_name_compare
+ */
+static uint32
+orclause_hash(const void *data, Size keysize)
+{
+ OrClauseGroupKey *key = (OrClauseGroupKey *) data;
+ uint64 hash;
+
+ (void) JumbleExpr(key->expr, &hash);
+ hash += ((uint64) key->opno + (uint64) key->exprtype) % UINT64_MAX;
+ return hash;
+}
correct me if i am wrong:
in orclause_hash, you just want to return a uint32, then why does the
JumbleExpr function return struct JumbleState.
here JumbleExpr, we just simply hash part of a Query struct,
so JumbleExpr's queryId would be confused with JumbleQuery function's queryId.
not sure the purpose of the following:
+ if (*queryId == UINT64CONST(0))
+ *queryId = UINT64CONST(1);
even if *queryId is 0
`hash += ((uint64) key->opno + (uint64) key->exprtype) % UINT64_MAX;`
will make the hash return non-zero?
+ MemSet(&info, 0, sizeof(info));
i am not sure this is necessary.
Some comments on OrClauseGroupEntry would be great.
seems there is no doc.
create or replace function retint(int) returns int as
$func$
begin return $1 + round(10 * random()); end
$func$ LANGUAGE plpgsql;
set enable_or_transformation to on;
EXPLAIN (COSTS OFF)
SELECT count(*) FROM tenk1
WHERE thousand = 42 AND (tenthous * retint(1) = NULL OR tenthous *
retint(1) = 3) OR thousand = 41;
returns:
QUERY PLAN
-------------------------------------------------------------------------------------------------------------------
Aggregate
-> Seq Scan on tenk1
Filter: (((thousand = 42) AND ((tenthous * retint(1)) = ANY
('{NULL,3}'::integer[]))) OR (thousand = 41))
(3 rows)
Based on the query plan, retint executed once, but here it should be
executed twice?
maybe we need to use contain_volatile_functions to check through the
other part of the operator expression.
+ if (IsA(leftop, Const))
+ {
+ opno = get_commutator(opno);
+
+ if (!OidIsValid(opno))
+ {
+ /* Commuter doesn't exist, we can't reverse the order */
+ or_list = lappend(or_list, orqual);
+ continue;
+ }
+
+ nconst_expr = get_rightop(orqual);
+ const_expr = get_leftop(orqual);
+ }
+ else if (IsA(rightop, Const))
+ {
+ const_expr = get_rightop(orqual);
+ nconst_expr = get_leftop(orqual);
+ }
+ else
+ {
+ or_list = lappend(or_list, orqual);
+ continue;
+ }
do we need to skip this transformation for the const type is anyarray?
^ permalink raw reply [nested|flat] 29+ messages in thread
* Re: POC, WIP: OR-clause support for indexes
2015-12-26 18:04 POC, WIP: OR-clause support for indexes Teodor Sigaev <[email protected]>
2024-01-30 14:15 ` Re: POC, WIP: OR-clause support for indexes jian he <[email protected]>
@ 2024-01-31 02:55 ` jian he <[email protected]>
2024-01-31 10:15 ` Re: POC, WIP: OR-clause support for indexes jian he <[email protected]>
0 siblings, 1 reply; 29+ messages in thread
From: jian he @ 2024-01-31 02:55 UTC (permalink / raw)
To: Andrei Lepikhov <[email protected]>; +Cc: Alena Rybakina <[email protected]>; Robert Haas <[email protected]>; pgsql-hackers; Alexander Korotkov <[email protected]>; Peter Geoghegan <[email protected]>; Finnerty, Jim <[email protected]>; Marcos Pegoraro <[email protected]>; [email protected]; Ranier Vilela <[email protected]>; Tomas Vondra <[email protected]>; Peter Eisentraut <[email protected]>
+/*
+ * Hash function that's compatible with guc_name_compare
+ */
+static uint32
+orclause_hash(const void *data, Size keysize)
+{
+ OrClauseGroupKey *key = (OrClauseGroupKey *) data;
+ uint64 hash;
+
+ (void) JumbleExpr(key->expr, &hash);
+ hash += ((uint64) key->opno + (uint64) key->exprtype) % UINT64_MAX;
+ return hash;
+}
looks strange. `hash` is uint64, but here you return uint32.
based on my understanding of
https://www.postgresql.org/docs/current/xoper-optimization.html#XOPER-COMMUTATOR
I think you need move commutator check right after the `if
(get_op_rettype(opno) != BOOLOID)` branch
+ opno = ((OpExpr *) orqual)->opno;
+ if (get_op_rettype(opno) != BOOLOID)
+ {
+ /* Only operator returning boolean suits OR -> ANY transformation */
+ or_list = lappend(or_list, orqual);
+ continue;
+ }
select po.oprname,po.oprkind,po.oprcanhash,po.oprleft::regtype,po.oprright,po.oprresult,
po1.oprname
from pg_operator po join pg_operator po1
on po.oprcom = po1.oid
where po.oprresult = 16;
I am wondering, are all these types as long as the return type is bool
suitable for this transformation?
^ permalink raw reply [nested|flat] 29+ messages in thread
* Re: POC, WIP: OR-clause support for indexes
2015-12-26 18:04 POC, WIP: OR-clause support for indexes Teodor Sigaev <[email protected]>
2024-01-30 14:15 ` Re: POC, WIP: OR-clause support for indexes jian he <[email protected]>
2024-01-31 02:55 ` Re: POC, WIP: OR-clause support for indexes jian he <[email protected]>
@ 2024-01-31 10:15 ` jian he <[email protected]>
2024-01-31 11:10 ` Re: POC, WIP: OR-clause support for indexes Alena Rybakina <[email protected]>
0 siblings, 1 reply; 29+ messages in thread
From: jian he @ 2024-01-31 10:15 UTC (permalink / raw)
To: Andrei Lepikhov <[email protected]>; +Cc: Alena Rybakina <[email protected]>; Robert Haas <[email protected]>; pgsql-hackers; Alexander Korotkov <[email protected]>; Peter Geoghegan <[email protected]>; Finnerty, Jim <[email protected]>; Marcos Pegoraro <[email protected]>; [email protected]; Ranier Vilela <[email protected]>; Tomas Vondra <[email protected]>; Peter Eisentraut <[email protected]>
On Wed, Jan 31, 2024 at 10:55 AM jian he <[email protected]> wrote:
>
> based on my understanding of
> https://www.postgresql.org/docs/current/xoper-optimization.html#XOPER-COMMUTATOR
> I think you need move commutator check right after the `if
> (get_op_rettype(opno) != BOOLOID)` branch
>
I was wrong about this part. sorry for the noise.
I have made some changes (attachment).
* if the operator expression left or right side type category is
{array | domain | composite}, then don't do the transformation.
(i am not 10% sure with composite)
* if the left side of the operator expression node contains volatile
functions, then don't do the transformation.
* some other minor cosmetic changes.
Attachments:
[application/octet-stream] v14_comments.no-cfbot (2.5K, ../../CACJufxFrZS07oBHMk1_c8P3A84VZ3ysXiZV8NeU6gAnvu+HsVA@mail.gmail.com/2-v14_comments.no-cfbot)
download
^ permalink raw reply [nested|flat] 29+ messages in thread
* Re: POC, WIP: OR-clause support for indexes
2015-12-26 18:04 POC, WIP: OR-clause support for indexes Teodor Sigaev <[email protected]>
2024-01-30 14:15 ` Re: POC, WIP: OR-clause support for indexes jian he <[email protected]>
2024-01-31 02:55 ` Re: POC, WIP: OR-clause support for indexes jian he <[email protected]>
2024-01-31 10:15 ` Re: POC, WIP: OR-clause support for indexes jian he <[email protected]>
@ 2024-01-31 11:10 ` Alena Rybakina <[email protected]>
0 siblings, 0 replies; 29+ messages in thread
From: Alena Rybakina @ 2024-01-31 11:10 UTC (permalink / raw)
To: jian he <[email protected]>; +Cc: Andrei Lepikhov <[email protected]>; Robert Haas <[email protected]>; pgsql-hackers; Alexander Korotkov <[email protected]>; Peter Geoghegan <[email protected]>; Finnerty, Jim <[email protected]>; Marcos Pegoraro <[email protected]>; [email protected]; Ranier Vilela <[email protected]>; Tomas Vondra <[email protected]>; Peter Eisentraut <[email protected]>
Hi, thank you for your review and interest in this subject.
On 31.01.2024 13:15, jian he wrote:
> On Wed, Jan 31, 2024 at 10:55 AM jian he<[email protected]> wrote:
>> based on my understanding of
>> https://www.postgresql.org/docs/current/xoper-optimization.html#XOPER-COMMUTATOR
>> I think you need move commutator check right after the `if
>> (get_op_rettype(opno) != BOOLOID)` branch
>>
> I was wrong about this part. sorry for the noise.
>
>
> I have made some changes (attachment).
> * if the operator expression left or right side type category is
> {array | domain | composite}, then don't do the transformation.
> (i am not 10% sure with composite)
To be honest, I'm not sure about this check, because we check the type
of variable there:
if (!IsA(orqual, OpExpr))
{
or_list = lappend(or_list, orqual);
continue;
}
And below:
if (IsA(leftop, Const))
{
opno = get_commutator(opno);
if (!OidIsValid(opno))
{
/* Commuter doesn't exist, we can't reverse the order */
or_list = lappend(or_list, orqual);
continue;
}
nconst_expr = get_rightop(orqual);
const_expr = get_leftop(orqual);
}
else if (IsA(rightop, Const))
{
const_expr = get_rightop(orqual);
nconst_expr = get_leftop(orqual);
}
else
{
or_list = lappend(or_list, orqual);
continue;
}
Isn't that enough?
Besides, some of examples (with ARRAY) works fine:
postgres=# CREATE TABLE sal_emp (
pay_by_quarter integer[],
pay_by_quater1 integer[]
);
CREATE TABLE
postgres=# INSERT INTO sal_emp
VALUES (
'{10000, 10000, 10000, 10000}',
'{1,2,3,4}');
INSERT 0 1
postgres=# select * from sal_emp where pay_by_quarter[1] = 10000 or
pay_by_quarter[1]=2;
pay_by_quarter | pay_by_quater1
---------------------------+----------------
{10000,10000,10000,10000} | {1,2,3,4}
(1 row)
postgres=# explain select * from sal_emp where pay_by_quarter[1] = 10000
or pay_by_quarter[1]=2;
QUERY PLAN
--------------------------------------------------------------
Seq Scan on sal_emp (cost=0.00..21.00 rows=9 width=64)
Filter: (pay_by_quarter[1] = ANY ('{10000,2}'::integer[]))
(2 rows)
> * if the left side of the operator expression node contains volatile
> functions, then don't do the transformation.
I'm also not sure about the volatility check function, because we
perform such a conversion at the parsing stage, and at this stage we
don't have a RelOptInfo variable and especially a RestictInfo such as
PathTarget.
Speaking of NextValueExpr, I couldn't find any examples where the
current patch wouldn't work. I wrote one of them below:
postgres=# create table foo (f1 int, f2 int generated always as identity);
CREATE TABLE
postgres=# insert into foo values(1);
INSERT 0 1
postgres=# explain verbose update foo set f1 = 2 where f1=1 or f1=2 ;
QUERY PLAN
-------------------------------------------------------------------
Update on public.foo (cost=0.00..38.25 rows=0 width=0)
-> Seq Scan on public.foo (cost=0.00..38.25 rows=23 width=10)
Output: 2, ctid
Filter: (foo.f1 = ANY ('{1,2}'::integer[]))
(4 rows)
Maybe I missed something. Do you have any examples?
> * some other minor cosmetic changes.
Thank you, I agree with them.
--
Regards,
Alena Rybakina
Postgres Professional:http://www.postgrespro.com
The Russian Postgres Company
^ permalink raw reply [nested|flat] 29+ messages in thread
* Re: POC, WIP: OR-clause support for indexes
2015-12-26 18:04 POC, WIP: OR-clause support for indexes Teodor Sigaev <[email protected]>
@ 2025-03-24 10:10 ` Andrei Lepikhov <[email protected]>
2025-03-24 10:46 ` Re: POC, WIP: OR-clause support for indexes Pavel Borisov <[email protected]>
5 siblings, 1 reply; 29+ messages in thread
From: Andrei Lepikhov @ 2025-03-24 10:10 UTC (permalink / raw)
To: Alexander Korotkov <[email protected]>; +Cc: Alexander Lakhin <[email protected]>; [email protected]; Pavel Borisov <[email protected]>; a.rybakina <[email protected]>
Hi,
Playing with the feature, I found a slightly irritating permutation -
even if this code doesn't group any clauses, it may permute positions of
the quals. See:
DROP TABLE IF EXISTS main_tbl;
CREATE TABLE main_tbl(id bigint, hundred int, thousand int);
CREATE INDEX mt_hundred_ix ON main_tbl(hundred);
CREATE INDEX mt_thousand_ix ON main_tbl(thousand);
VACUUM (ANALYZE) main_tbl;
SET enable_seqscan = off;
EXPLAIN (COSTS OFF)
SELECT m.id, m.hundred, m.thousand
FROM main_tbl m WHERE (m.hundred < 2 OR m.thousand < 3);
Bitmap Heap Scan on public.main_tbl m
Output: id, hundred, thousand
Recheck Cond: ((m.thousand < 3) OR (m.hundred < 2))
-> BitmapOr
-> Bitmap Index Scan on mt_thousand_ix
Index Cond: (m.thousand < 3)
-> Bitmap Index Scan on mt_hundred_ix
Index Cond: (m.hundred < 2)
Conditions on the columns "thousand" and "hundred" changed their places
according to the initial positions defined in the user's SQL.
It isn't okay. I see that users often use the trick of "OR order" to
avoid unnecessary calculations - most frequently, Subplan evaluations.
So, it makes sense to fix.
In the attachment, I have included a quick fix for this issue. Although
many tests returned to their initial (pre-18) state, I added some tests
specifically related to this issue to make it clearer.
--
regards, Andrei Lepikhov
Attachments:
[text/x-patch] clause-permutation-fix.diff (9.1K, ../../[email protected]/2-clause-permutation-fix.diff)
download | inline diff:
diff --git a/src/backend/optimizer/path/indxpath.c b/src/backend/optimizer/path/indxpath.c
index a43ca16d68..7d8ef0c90f 100644
--- a/src/backend/optimizer/path/indxpath.c
+++ b/src/backend/optimizer/path/indxpath.c
@@ -1254,6 +1254,7 @@ group_similar_or_args(PlannerInfo *root, RelOptInfo *rel, RestrictInfo *rinfo)
ListCell *lc;
ListCell *lc2;
List *orargs;
+ bool grouping_happened = false;
List *result = NIL;
Index relid = rel->relid;
@@ -1465,13 +1466,18 @@ group_similar_or_args(PlannerInfo *root, RelOptInfo *rel, RestrictInfo *rinfo)
rinfo->incompatible_relids,
rinfo->outer_relids);
result = lappend(result, subrinfo);
+ grouping_happened = true;
}
group_start = i;
}
}
pfree(matches);
- return result;
+
+ if (grouping_happened)
+ return result;
+ else
+ return orargs;
}
/*
diff --git a/src/test/regress/expected/create_index.out b/src/test/regress/expected/create_index.out
index bd5f002cf2..c6f84bda64 100644
--- a/src/test/regress/expected/create_index.out
+++ b/src/test/regress/expected/create_index.out
@@ -3248,6 +3248,37 @@ SELECT b.relname,
(2 rows)
DROP TABLE concur_temp_tab_1, concur_temp_tab_2, reindex_temp_before;
+-- No OR-clause groupings should happen - no clause permutations in
+-- the filtering conditions we should see in the EXPLAIN.
+EXPLAIN (COSTS OFF)
+SELECT * FROM tenk1 WHERE unique1 < 1 OR hundred < 2;
+ QUERY PLAN
+--------------------------------------------------
+ Bitmap Heap Scan on tenk1
+ Recheck Cond: ((unique1 < 1) OR (hundred < 2))
+ -> BitmapOr
+ -> Bitmap Index Scan on tenk1_unique1
+ Index Cond: (unique1 < 1)
+ -> Bitmap Index Scan on tenk1_hundred
+ Index Cond: (hundred < 2)
+(7 rows)
+
+-- OR clauses on the 'unique' column is grouped. So, clause permutation happened
+-- We see it in the 'Recheck Cond' and order of BitmapOr subpaths: index scan on
+-- the 'hundred' column occupies the first position.
+EXPLAIN (COSTS OFF)
+SELECT * FROM tenk1 WHERE unique1 < 1 OR unique1 < 3 OR hundred < 2;
+ QUERY PLAN
+---------------------------------------------------------------------
+ Bitmap Heap Scan on tenk1
+ Recheck Cond: ((hundred < 2) OR ((unique1 < 1) OR (unique1 < 3)))
+ -> BitmapOr
+ -> Bitmap Index Scan on tenk1_hundred
+ Index Cond: (hundred < 2)
+ -> Bitmap Index Scan on tenk1_unique1
+ Index Cond: (unique1 < ANY ('{1,3}'::integer[]))
+(7 rows)
+
-- Check bitmap scan can consider similar OR arguments separately without
-- grouping them into SAOP.
CREATE TABLE bitmap_split_or (a int NOT NULL, b int NOT NULL, c int NOT NULL);
diff --git a/src/test/regress/expected/join.out b/src/test/regress/expected/join.out
index a57bb18c24..a950153d76 100644
--- a/src/test/regress/expected/join.out
+++ b/src/test/regress/expected/join.out
@@ -4333,20 +4333,20 @@ select * from tenk1 a join tenk1 b on
Nested Loop
Join Filter: (((a.unique1 = 1) AND (b.unique1 = 2)) OR ((a.unique2 = 3) AND (b.hundred = 4)))
-> Bitmap Heap Scan on tenk1 b
- Recheck Cond: ((hundred = 4) OR (unique1 = 2))
+ Recheck Cond: ((unique1 = 2) OR (hundred = 4))
-> BitmapOr
- -> Bitmap Index Scan on tenk1_hundred
- Index Cond: (hundred = 4)
-> Bitmap Index Scan on tenk1_unique1
Index Cond: (unique1 = 2)
+ -> Bitmap Index Scan on tenk1_hundred
+ Index Cond: (hundred = 4)
-> Materialize
-> Bitmap Heap Scan on tenk1 a
- Recheck Cond: ((unique2 = 3) OR (unique1 = 1))
+ Recheck Cond: ((unique1 = 1) OR (unique2 = 3))
-> BitmapOr
- -> Bitmap Index Scan on tenk1_unique2
- Index Cond: (unique2 = 3)
-> Bitmap Index Scan on tenk1_unique1
Index Cond: (unique1 = 1)
+ -> Bitmap Index Scan on tenk1_unique2
+ Index Cond: (unique2 = 3)
(17 rows)
explain (costs off)
@@ -4360,12 +4360,12 @@ select * from tenk1 a join tenk1 b on
Filter: ((unique1 = 2) OR (ten = 4))
-> Materialize
-> Bitmap Heap Scan on tenk1 a
- Recheck Cond: ((unique2 = 3) OR (unique1 = 1))
+ Recheck Cond: ((unique1 = 1) OR (unique2 = 3))
-> BitmapOr
- -> Bitmap Index Scan on tenk1_unique2
- Index Cond: (unique2 = 3)
-> Bitmap Index Scan on tenk1_unique1
Index Cond: (unique1 = 1)
+ -> Bitmap Index Scan on tenk1_unique2
+ Index Cond: (unique2 = 3)
(12 rows)
explain (costs off)
@@ -4377,12 +4377,12 @@ select * from tenk1 a join tenk1 b on
Nested Loop
Join Filter: (((a.unique1 = 1) AND (b.unique1 = 2)) OR (((a.unique2 = 3) OR (a.unique2 = 7)) AND (b.hundred = 4)))
-> Bitmap Heap Scan on tenk1 b
- Recheck Cond: ((hundred = 4) OR (unique1 = 2))
+ Recheck Cond: ((unique1 = 2) OR (hundred = 4))
-> BitmapOr
- -> Bitmap Index Scan on tenk1_hundred
- Index Cond: (hundred = 4)
-> Bitmap Index Scan on tenk1_unique1
Index Cond: (unique1 = 2)
+ -> Bitmap Index Scan on tenk1_hundred
+ Index Cond: (hundred = 4)
-> Materialize
-> Bitmap Heap Scan on tenk1 a
Recheck Cond: (((unique2 = 3) OR (unique2 = 7)) OR (unique1 = 1))
@@ -4403,12 +4403,12 @@ select * from tenk1 a join tenk1 b on
Nested Loop
Join Filter: (((a.unique1 = 1) AND (b.unique1 = 2)) OR (((a.unique2 = 3) OR (a.unique2 = 7)) AND (b.hundred = 4)))
-> Bitmap Heap Scan on tenk1 b
- Recheck Cond: ((hundred = 4) OR (unique1 = 2))
+ Recheck Cond: ((unique1 = 2) OR (hundred = 4))
-> BitmapOr
- -> Bitmap Index Scan on tenk1_hundred
- Index Cond: (hundred = 4)
-> Bitmap Index Scan on tenk1_unique1
Index Cond: (unique1 = 2)
+ -> Bitmap Index Scan on tenk1_hundred
+ Index Cond: (hundred = 4)
-> Materialize
-> Bitmap Heap Scan on tenk1 a
Recheck Cond: (((unique2 = 3) OR (unique2 = 7)) OR (unique1 = 1))
diff --git a/src/test/regress/expected/partition_join.out b/src/test/regress/expected/partition_join.out
index 938cedd79a..6101c8c7cf 100644
--- a/src/test/regress/expected/partition_join.out
+++ b/src/test/regress/expected/partition_join.out
@@ -2568,24 +2568,24 @@ where not exists (select 1 from prtx2
-> Seq Scan on prtx1_1
Filter: ((a < 20) AND (c = 91))
-> Bitmap Heap Scan on prtx2_1
- Recheck Cond: ((c = 99) OR (b = (prtx1_1.b + 1)))
+ Recheck Cond: ((b = (prtx1_1.b + 1)) OR (c = 99))
Filter: (a = prtx1_1.a)
-> BitmapOr
- -> Bitmap Index Scan on prtx2_1_c_idx
- Index Cond: (c = 99)
-> Bitmap Index Scan on prtx2_1_b_idx
Index Cond: (b = (prtx1_1.b + 1))
+ -> Bitmap Index Scan on prtx2_1_c_idx
+ Index Cond: (c = 99)
-> Nested Loop Anti Join
-> Seq Scan on prtx1_2
Filter: ((a < 20) AND (c = 91))
-> Bitmap Heap Scan on prtx2_2
- Recheck Cond: ((c = 99) OR (b = (prtx1_2.b + 1)))
+ Recheck Cond: ((b = (prtx1_2.b + 1)) OR (c = 99))
Filter: (a = prtx1_2.a)
-> BitmapOr
- -> Bitmap Index Scan on prtx2_2_c_idx
- Index Cond: (c = 99)
-> Bitmap Index Scan on prtx2_2_b_idx
Index Cond: (b = (prtx1_2.b + 1))
+ -> Bitmap Index Scan on prtx2_2_c_idx
+ Index Cond: (c = 99)
(23 rows)
select * from prtx1
diff --git a/src/test/regress/sql/create_index.sql b/src/test/regress/sql/create_index.sql
index be570da08a..51e030294e 100644
--- a/src/test/regress/sql/create_index.sql
+++ b/src/test/regress/sql/create_index.sql
@@ -1355,6 +1355,17 @@ SELECT b.relname,
ORDER BY 1;
DROP TABLE concur_temp_tab_1, concur_temp_tab_2, reindex_temp_before;
+-- No OR-clause groupings should happen - no clause permutations in
+-- the filtering conditions we should see in the EXPLAIN.
+EXPLAIN (COSTS OFF)
+SELECT * FROM tenk1 WHERE unique1 < 1 OR hundred < 2;
+
+-- OR clauses on the 'unique' column is grouped. So, clause permutation happened
+-- We see it in the 'Recheck Cond' and order of BitmapOr subpaths: index scan on
+-- the 'hundred' column occupies the first position.
+EXPLAIN (COSTS OFF)
+SELECT * FROM tenk1 WHERE unique1 < 1 OR unique1 < 3 OR hundred < 2;
+
-- Check bitmap scan can consider similar OR arguments separately without
-- grouping them into SAOP.
CREATE TABLE bitmap_split_or (a int NOT NULL, b int NOT NULL, c int NOT NULL);
^ permalink raw reply [nested|flat] 29+ messages in thread
* Re: POC, WIP: OR-clause support for indexes
2015-12-26 18:04 POC, WIP: OR-clause support for indexes Teodor Sigaev <[email protected]>
2025-03-24 10:10 ` Re: POC, WIP: OR-clause support for indexes Andrei Lepikhov <[email protected]>
@ 2025-03-24 10:46 ` Pavel Borisov <[email protected]>
2025-03-24 12:46 ` Re: POC, WIP: OR-clause support for indexes Alena Rybakina <[email protected]>
0 siblings, 1 reply; 29+ messages in thread
From: Pavel Borisov @ 2025-03-24 10:46 UTC (permalink / raw)
To: Andrei Lepikhov <[email protected]>; +Cc: Alexander Korotkov <[email protected]>; Alexander Lakhin <[email protected]>; [email protected]; a.rybakina <[email protected]>
Hi, Andrei!
On Mon, 24 Mar 2025 at 14:10, Andrei Lepikhov <[email protected]> wrote:
>
> Hi,
>
> Playing with the feature, I found a slightly irritating permutation -
> even if this code doesn't group any clauses, it may permute positions of
> the quals. See:
>
> DROP TABLE IF EXISTS main_tbl;
> CREATE TABLE main_tbl(id bigint, hundred int, thousand int);
> CREATE INDEX mt_hundred_ix ON main_tbl(hundred);
> CREATE INDEX mt_thousand_ix ON main_tbl(thousand);
> VACUUM (ANALYZE) main_tbl;
>
> SET enable_seqscan = off;
> EXPLAIN (COSTS OFF)
> SELECT m.id, m.hundred, m.thousand
> FROM main_tbl m WHERE (m.hundred < 2 OR m.thousand < 3);
>
> Bitmap Heap Scan on public.main_tbl m
> Output: id, hundred, thousand
> Recheck Cond: ((m.thousand < 3) OR (m.hundred < 2))
> -> BitmapOr
> -> Bitmap Index Scan on mt_thousand_ix
> Index Cond: (m.thousand < 3)
> -> Bitmap Index Scan on mt_hundred_ix
> Index Cond: (m.hundred < 2)
>
> Conditions on the columns "thousand" and "hundred" changed their places
> according to the initial positions defined in the user's SQL.
> It isn't okay. I see that users often use the trick of "OR order" to
> avoid unnecessary calculations - most frequently, Subplan evaluations.
> So, it makes sense to fix.
> In the attachment, I have included a quick fix for this issue. Although
> many tests returned to their initial (pre-18) state, I added some tests
> specifically related to this issue to make it clearer.
I looked at your patch and have no objections to it.
However it's clearly stated in PostgreSQL manual that nothing about
the OR order is warranted [1]. So changing OR order was (and is) ok
and any users query tricks about OR order may work and may not work.
[1] https://www.postgresql.org/docs/17/sql-expressions.html#SYNTAX-EXPRESS-EVAL
Regards,
Pavel Borisov
Supabase
^ permalink raw reply [nested|flat] 29+ messages in thread
* Re: POC, WIP: OR-clause support for indexes
2015-12-26 18:04 POC, WIP: OR-clause support for indexes Teodor Sigaev <[email protected]>
2025-03-24 10:10 ` Re: POC, WIP: OR-clause support for indexes Andrei Lepikhov <[email protected]>
2025-03-24 10:46 ` Re: POC, WIP: OR-clause support for indexes Pavel Borisov <[email protected]>
@ 2025-03-24 12:46 ` Alena Rybakina <[email protected]>
2025-03-27 23:18 ` Re: POC, WIP: OR-clause support for indexes Alexander Korotkov <[email protected]>
0 siblings, 1 reply; 29+ messages in thread
From: Alena Rybakina @ 2025-03-24 12:46 UTC (permalink / raw)
To: Pavel Borisov <[email protected]>; Andrei Lepikhov <[email protected]>; +Cc: Alexander Korotkov <[email protected]>; Alexander Lakhin <[email protected]>; [email protected]
On 24.03.2025 13:46, Pavel Borisov wrote:
> Hi, Andrei!
>
> On Mon, 24 Mar 2025 at 14:10, Andrei Lepikhov<[email protected]> wrote:
>> Hi,
>>
>> Playing with the feature, I found a slightly irritating permutation -
>> even if this code doesn't group any clauses, it may permute positions of
>> the quals. See:
>>
>> DROP TABLE IF EXISTS main_tbl;
>> CREATE TABLE main_tbl(id bigint, hundred int, thousand int);
>> CREATE INDEX mt_hundred_ix ON main_tbl(hundred);
>> CREATE INDEX mt_thousand_ix ON main_tbl(thousand);
>> VACUUM (ANALYZE) main_tbl;
>>
>> SET enable_seqscan = off;
>> EXPLAIN (COSTS OFF)
>> SELECT m.id, m.hundred, m.thousand
>> FROM main_tbl m WHERE (m.hundred < 2 OR m.thousand < 3);
>>
>> Bitmap Heap Scan on public.main_tbl m
>> Output: id, hundred, thousand
>> Recheck Cond: ((m.thousand < 3) OR (m.hundred < 2))
>> -> BitmapOr
>> -> Bitmap Index Scan on mt_thousand_ix
>> Index Cond: (m.thousand < 3)
>> -> Bitmap Index Scan on mt_hundred_ix
>> Index Cond: (m.hundred < 2)
>>
>> Conditions on the columns "thousand" and "hundred" changed their places
>> according to the initial positions defined in the user's SQL.
>> It isn't okay. I see that users often use the trick of "OR order" to
>> avoid unnecessary calculations - most frequently, Subplan evaluations.
>> So, it makes sense to fix.
>> In the attachment, I have included a quick fix for this issue. Although
>> many tests returned to their initial (pre-18) state, I added some tests
>> specifically related to this issue to make it clearer.
> I looked at your patch and have no objections to it.
>
> However it's clearly stated in PostgreSQL manual that nothing about
> the OR order is warranted [1]. So changing OR order was (and is) ok
> and any users query tricks about OR order may work and may not work.
>
> [1]https://www.postgresql.org/docs/17/sql-expressions.html#SYNTAX-EXPRESS-EVAL
>
I agree with Andrey's changes and think we should fix this, because
otherwise it might be inconvenient.
For example, without this changes we will have to have different test
output files for the same query for different versions of Postres in
extensions if the whole change is only related to the order of column
output for a transformation that was not applied.
--
Regards,
Alena Rybakina
Postgres Professional
^ permalink raw reply [nested|flat] 29+ messages in thread
* Re: POC, WIP: OR-clause support for indexes
2015-12-26 18:04 POC, WIP: OR-clause support for indexes Teodor Sigaev <[email protected]>
2025-03-24 10:10 ` Re: POC, WIP: OR-clause support for indexes Andrei Lepikhov <[email protected]>
2025-03-24 10:46 ` Re: POC, WIP: OR-clause support for indexes Pavel Borisov <[email protected]>
2025-03-24 12:46 ` Re: POC, WIP: OR-clause support for indexes Alena Rybakina <[email protected]>
@ 2025-03-27 23:18 ` Alexander Korotkov <[email protected]>
2025-03-28 10:47 ` Re: POC, WIP: OR-clause support for indexes Pavel Borisov <[email protected]>
2025-03-28 11:32 ` Re: POC, WIP: OR-clause support for indexes Andrei Lepikhov <[email protected]>
2025-03-28 12:23 ` Re: POC, WIP: OR-clause support for indexes Alena Rybakina <[email protected]>
0 siblings, 3 replies; 29+ messages in thread
From: Alexander Korotkov @ 2025-03-27 23:18 UTC (permalink / raw)
To: Alena Rybakina <[email protected]>; +Cc: Pavel Borisov <[email protected]>; Andrei Lepikhov <[email protected]>; Alexander Lakhin <[email protected]>; [email protected]
Hi!
On Mon, Mar 24, 2025 at 2:46 PM Alena Rybakina
<[email protected]> wrote:
> I agree with Andrey's changes and think we should fix this, because otherwise it might be inconvenient.
> For example, without this changes we will have to have different test output files for the same query for different versions of Postres in extensions if the whole change is only related to the order of column output for a transformation that was not applied.
I agree with problem spotted by Andrei: it should be preferred to
preserve original order of clauses as much as possible. The approach
implemented in Andrei's patch seems fragile for me. Original order is
preserved if we didn't find any group. But once we find a single
group original order might be destroyed completely.
The attached patch changes the reordering algorithm of
group_similar_or_args() in the following way. We reorder each group
of similar clauses so that the first item of the group stays in place,
but all the other items are moved after it. So, if there are no
similar clauses, the order of clauses stays the same. When there are
some groups, only required reordering happens while the rest of the
clauses remain in their places.
------
Regards,
Alexander Korotkov
Supabase
Attachments:
[application/octet-stream] v1-0001-Make-group_similar_or_args-reorder-clause-list-as.patch (16.4K, ../../CAPpHfdu71LCrXfwaRot1u_xfx7r92VFvZNRLvQJS79B3XFmBhg@mail.gmail.com/2-v1-0001-Make-group_similar_or_args-reorder-clause-list-as.patch)
download | inline diff:
From 1829564b42450cac8d030d9942ef0a5f26ff86fe Mon Sep 17 00:00:00 2001
From: Alexander Korotkov <[email protected]>
Date: Fri, 28 Mar 2025 00:15:29 +0200
Subject: [PATCH v1] Make group_similar_or_args() reorder clause list as little
as possible
Currently, group_similar_or_args() permutes original positions of clauses
independently on whether it manages to find any groups of similar clauses.
While we are not providing any strict warranties on saving the original order
of OR-clauses, it is preferred that the original order be modified as little
as possible.
This commit changes the reordering algorithm of group_similar_or_args() in
the following way. We reorder each group of similar clauses so that the
first item of the group stays in place, but all the other items are moved
after it. So, if there are no similar clauses, the order of clauses stays
the same. When there are some groups, only required reordering happens while
the rest of the clauses remain in their places.
Reported-by: Andrei Lepikhov <[email protected]>
Discussion: https://postgr.es/m/3ac7c436-81e1-4191-9caf-b0dd70b51511%40gmail.com
---
src/backend/optimizer/path/indxpath.c | 60 +++++++++++++++++++-
src/test/regress/expected/create_index.out | 18 +++---
src/test/regress/expected/join.out | 52 ++++++++---------
src/test/regress/expected/partition_join.out | 12 ++--
4 files changed, 100 insertions(+), 42 deletions(-)
diff --git a/src/backend/optimizer/path/indxpath.c b/src/backend/optimizer/path/indxpath.c
index a43ca16d683..2a18bf7c7c3 100644
--- a/src/backend/optimizer/path/indxpath.c
+++ b/src/backend/optimizer/path/indxpath.c
@@ -1189,6 +1189,8 @@ typedef struct
Oid inputcollid; /* OID of the OpClause input collation */
int argindex; /* index of the clause in the list of
* arguments */
+ int groupindex; /* value of argindex for the fist clause in
+ * the group of similar clauses */
} OrArgIndexMatch;
/*
@@ -1229,6 +1231,29 @@ or_arg_index_match_cmp(const void *a, const void *b)
return 0;
}
+/*
+ * Another comparison function for OrArgIndexMatch. It sorts groups together
+ * using groupindex. The group items are then sorted by argindex.
+ */
+static int
+or_arg_index_match_cmp_group(const void *a, const void *b)
+{
+ const OrArgIndexMatch *match_a = (const OrArgIndexMatch *) a;
+ const OrArgIndexMatch *match_b = (const OrArgIndexMatch *) b;
+
+ if (match_a->groupindex < match_b->groupindex)
+ return -1;
+ else if (match_a->groupindex > match_b->groupindex)
+ return 1;
+
+ if (match_a->argindex < match_b->argindex)
+ return -1;
+ else if (match_a->argindex > match_b->argindex)
+ return 1;
+
+ return 0;
+}
+
/*
* group_similar_or_args
* Transform incoming OR-restrictinfo into a list of sub-restrictinfos,
@@ -1282,6 +1307,7 @@ group_similar_or_args(PlannerInfo *root, RelOptInfo *rel, RestrictInfo *rinfo)
i++;
matches[i].argindex = i;
+ matches[i].groupindex = i;
matches[i].indexnum = -1;
matches[i].colnum = -1;
matches[i].opno = InvalidOid;
@@ -1400,9 +1426,41 @@ group_similar_or_args(PlannerInfo *root, RelOptInfo *rel, RestrictInfo *rinfo)
return orargs;
}
- /* Sort clauses to make similar clauses go together */
+ /*
+ * Sort clauses to make similar clauses go together. But at the same
+ * time, we would like to change the order of clauses as little as
+ * possible. To have this property, we reorder each group of similar
+ * clauses so that the first item of the group stays in place, but all the
+ * other items are moved after it. So, if there are no similar clauses,
+ * the order of clauses stays the same. When there are some groups, only
+ * required reordering happens while the rest of the clauses remain in
+ * their places. That is achieved by assigning a 'groupindex' to each
+ * clause: the number of the first item in the group in the original
+ * clause list.
+ */
qsort(matches, n, sizeof(OrArgIndexMatch), or_arg_index_match_cmp);
+ /* Assign groupindex to the sorted clauses */
+ for (i = 1; i < n; i++)
+ {
+ /*
+ * When two clauses are similar and should belong to the same group,
+ * copy the 'groupindex' from the previous clause. Given we are
+ * considering clauses in direct order, all the clauses would have a
+ * 'groupindex' equal to the 'groupindex' of the first clause in the
+ * group.
+ */
+ if ((matches[i].indexnum == matches[i - 1].indexnum ||
+ matches[i].colnum == matches[i - 1].colnum ||
+ matches[i].opno == matches[i - 1].opno ||
+ matches[i].inputcollid == matches[i - 1].inputcollid) &&
+ matches[i].indexnum != -1)
+ matches[i].groupindex = matches[i - 1].groupindex;
+ }
+
+ /* Resort clauses first by groupindex then by argindex */
+ qsort(matches, n, sizeof(OrArgIndexMatch), or_arg_index_match_cmp_group);
+
/*
* Group similar clauses into single sub-restrictinfo. Side effect: the
* resulting list of restrictions will be sorted by indexnum and colnum.
diff --git a/src/test/regress/expected/create_index.out b/src/test/regress/expected/create_index.out
index bd5f002cf20..3bd18bbbac9 100644
--- a/src/test/regress/expected/create_index.out
+++ b/src/test/regress/expected/create_index.out
@@ -1899,13 +1899,13 @@ SELECT * FROM tenk1
QUERY PLAN
-------------------------------------------------------------------------------------------------------------------------------------------
Bitmap Heap Scan on tenk1
- Recheck Cond: (((thousand = 42) AND (tenthous IS NULL)) OR ((thousand = 42) AND ((tenthous = 1) OR (tenthous = 3) OR (tenthous = 42))))
+ Recheck Cond: (((thousand = 42) AND ((tenthous = 1) OR (tenthous = 3) OR (tenthous = 42))) OR ((thousand = 42) AND (tenthous IS NULL)))
Filter: ((tenthous = 1) OR (tenthous = 3) OR (tenthous = 42) OR (tenthous IS NULL))
-> BitmapOr
- -> Bitmap Index Scan on tenk1_thous_tenthous
- Index Cond: ((thousand = 42) AND (tenthous IS NULL))
-> Bitmap Index Scan on tenk1_thous_tenthous
Index Cond: ((thousand = 42) AND (tenthous = ANY ('{1,3,42}'::integer[])))
+ -> Bitmap Index Scan on tenk1_thous_tenthous
+ Index Cond: ((thousand = 42) AND (tenthous IS NULL))
(8 rows)
EXPLAIN (COSTS OFF)
@@ -1938,13 +1938,13 @@ SELECT * FROM tenk1
QUERY PLAN
-----------------------------------------------------------------------------------------------------------------------------------------------------
Bitmap Heap Scan on tenk1
- Recheck Cond: (((thousand = 42) AND ((tenthous = '3'::bigint) OR (tenthous = '42'::bigint))) OR ((thousand = 42) AND (tenthous = '1'::smallint)))
+ Recheck Cond: (((thousand = 42) AND (tenthous = '1'::smallint)) OR ((thousand = 42) AND ((tenthous = '3'::bigint) OR (tenthous = '42'::bigint))))
Filter: ((tenthous = '1'::smallint) OR (tenthous = '3'::bigint) OR (tenthous = '42'::bigint))
-> BitmapOr
- -> Bitmap Index Scan on tenk1_thous_tenthous
- Index Cond: ((thousand = 42) AND (tenthous = ANY ('{3,42}'::bigint[])))
-> Bitmap Index Scan on tenk1_thous_tenthous
Index Cond: ((thousand = 42) AND (tenthous = '1'::smallint))
+ -> Bitmap Index Scan on tenk1_thous_tenthous
+ Index Cond: ((thousand = 42) AND (tenthous = ANY ('{3,42}'::bigint[])))
(8 rows)
EXPLAIN (COSTS OFF)
@@ -2129,16 +2129,16 @@ SELECT count(*) FROM tenk1
---------------------------------------------------------------------------------------------------------------------------
Aggregate
-> Bitmap Heap Scan on tenk1
- Recheck Cond: ((hundred = 42) AND (((thousand = 99) AND (tenthous = 2)) OR ((thousand = 42) OR (thousand = 41))))
+ Recheck Cond: ((hundred = 42) AND (((thousand = 42) OR (thousand = 41)) OR ((thousand = 99) AND (tenthous = 2))))
Filter: ((thousand = 42) OR (thousand = 41) OR ((thousand = 99) AND (tenthous = 2)))
-> BitmapAnd
-> Bitmap Index Scan on tenk1_hundred
Index Cond: (hundred = 42)
-> BitmapOr
- -> Bitmap Index Scan on tenk1_thous_tenthous
- Index Cond: ((thousand = 99) AND (tenthous = 2))
-> Bitmap Index Scan on tenk1_thous_tenthous
Index Cond: (thousand = ANY ('{42,41}'::integer[]))
+ -> Bitmap Index Scan on tenk1_thous_tenthous
+ Index Cond: ((thousand = 99) AND (tenthous = 2))
(12 rows)
SELECT count(*) FROM tenk1
diff --git a/src/test/regress/expected/join.out b/src/test/regress/expected/join.out
index a57bb18c24f..14da5708451 100644
--- a/src/test/regress/expected/join.out
+++ b/src/test/regress/expected/join.out
@@ -4333,20 +4333,20 @@ select * from tenk1 a join tenk1 b on
Nested Loop
Join Filter: (((a.unique1 = 1) AND (b.unique1 = 2)) OR ((a.unique2 = 3) AND (b.hundred = 4)))
-> Bitmap Heap Scan on tenk1 b
- Recheck Cond: ((hundred = 4) OR (unique1 = 2))
+ Recheck Cond: ((unique1 = 2) OR (hundred = 4))
-> BitmapOr
- -> Bitmap Index Scan on tenk1_hundred
- Index Cond: (hundred = 4)
-> Bitmap Index Scan on tenk1_unique1
Index Cond: (unique1 = 2)
+ -> Bitmap Index Scan on tenk1_hundred
+ Index Cond: (hundred = 4)
-> Materialize
-> Bitmap Heap Scan on tenk1 a
- Recheck Cond: ((unique2 = 3) OR (unique1 = 1))
+ Recheck Cond: ((unique1 = 1) OR (unique2 = 3))
-> BitmapOr
- -> Bitmap Index Scan on tenk1_unique2
- Index Cond: (unique2 = 3)
-> Bitmap Index Scan on tenk1_unique1
Index Cond: (unique1 = 1)
+ -> Bitmap Index Scan on tenk1_unique2
+ Index Cond: (unique2 = 3)
(17 rows)
explain (costs off)
@@ -4360,12 +4360,12 @@ select * from tenk1 a join tenk1 b on
Filter: ((unique1 = 2) OR (ten = 4))
-> Materialize
-> Bitmap Heap Scan on tenk1 a
- Recheck Cond: ((unique2 = 3) OR (unique1 = 1))
+ Recheck Cond: ((unique1 = 1) OR (unique2 = 3))
-> BitmapOr
- -> Bitmap Index Scan on tenk1_unique2
- Index Cond: (unique2 = 3)
-> Bitmap Index Scan on tenk1_unique1
Index Cond: (unique1 = 1)
+ -> Bitmap Index Scan on tenk1_unique2
+ Index Cond: (unique2 = 3)
(12 rows)
explain (costs off)
@@ -4377,21 +4377,21 @@ select * from tenk1 a join tenk1 b on
Nested Loop
Join Filter: (((a.unique1 = 1) AND (b.unique1 = 2)) OR (((a.unique2 = 3) OR (a.unique2 = 7)) AND (b.hundred = 4)))
-> Bitmap Heap Scan on tenk1 b
- Recheck Cond: ((hundred = 4) OR (unique1 = 2))
+ Recheck Cond: ((unique1 = 2) OR (hundred = 4))
-> BitmapOr
- -> Bitmap Index Scan on tenk1_hundred
- Index Cond: (hundred = 4)
-> Bitmap Index Scan on tenk1_unique1
Index Cond: (unique1 = 2)
+ -> Bitmap Index Scan on tenk1_hundred
+ Index Cond: (hundred = 4)
-> Materialize
-> Bitmap Heap Scan on tenk1 a
- Recheck Cond: (((unique2 = 3) OR (unique2 = 7)) OR (unique1 = 1))
+ Recheck Cond: ((unique1 = 1) OR ((unique2 = 3) OR (unique2 = 7)))
Filter: ((unique1 = 1) OR (unique2 = 3) OR (unique2 = 7))
-> BitmapOr
- -> Bitmap Index Scan on tenk1_unique2
- Index Cond: (unique2 = ANY ('{3,7}'::integer[]))
-> Bitmap Index Scan on tenk1_unique1
Index Cond: (unique1 = 1)
+ -> Bitmap Index Scan on tenk1_unique2
+ Index Cond: (unique2 = ANY ('{3,7}'::integer[]))
(18 rows)
explain (costs off)
@@ -4403,21 +4403,21 @@ select * from tenk1 a join tenk1 b on
Nested Loop
Join Filter: (((a.unique1 = 1) AND (b.unique1 = 2)) OR (((a.unique2 = 3) OR (a.unique2 = 7)) AND (b.hundred = 4)))
-> Bitmap Heap Scan on tenk1 b
- Recheck Cond: ((hundred = 4) OR (unique1 = 2))
+ Recheck Cond: ((unique1 = 2) OR (hundred = 4))
-> BitmapOr
- -> Bitmap Index Scan on tenk1_hundred
- Index Cond: (hundred = 4)
-> Bitmap Index Scan on tenk1_unique1
Index Cond: (unique1 = 2)
+ -> Bitmap Index Scan on tenk1_hundred
+ Index Cond: (hundred = 4)
-> Materialize
-> Bitmap Heap Scan on tenk1 a
- Recheck Cond: (((unique2 = 3) OR (unique2 = 7)) OR (unique1 = 1))
+ Recheck Cond: ((unique1 = 1) OR ((unique2 = 3) OR (unique2 = 7)))
Filter: ((unique1 = 1) OR (unique2 = 3) OR (unique2 = 7))
-> BitmapOr
- -> Bitmap Index Scan on tenk1_unique2
- Index Cond: (unique2 = ANY ('{3,7}'::integer[]))
-> Bitmap Index Scan on tenk1_unique1
Index Cond: (unique1 = 1)
+ -> Bitmap Index Scan on tenk1_unique2
+ Index Cond: (unique2 = ANY ('{3,7}'::integer[]))
(18 rows)
explain (costs off)
@@ -4431,15 +4431,15 @@ select * from tenk1 a join tenk1 b on
-> Seq Scan on tenk1 b
-> Materialize
-> Bitmap Heap Scan on tenk1 a
- Recheck Cond: (((unique2 = 3) OR (unique2 = 7)) OR ((unique1 = 3) OR (unique1 = 1)) OR (unique1 < 20))
+ Recheck Cond: ((unique1 < 20) OR ((unique1 = 3) OR (unique1 = 1)) OR ((unique2 = 3) OR (unique2 = 7)))
Filter: ((unique1 < 20) OR (unique1 = 3) OR (unique1 = 1) OR (unique2 = 3) OR (unique2 = 7))
-> BitmapOr
- -> Bitmap Index Scan on tenk1_unique2
- Index Cond: (unique2 = ANY ('{3,7}'::integer[]))
- -> Bitmap Index Scan on tenk1_unique1
- Index Cond: (unique1 = ANY ('{3,1}'::integer[]))
-> Bitmap Index Scan on tenk1_unique1
Index Cond: (unique1 < 20)
+ -> Bitmap Index Scan on tenk1_unique1
+ Index Cond: (unique1 = ANY ('{3,1}'::integer[]))
+ -> Bitmap Index Scan on tenk1_unique2
+ Index Cond: (unique2 = ANY ('{3,7}'::integer[]))
(14 rows)
--
diff --git a/src/test/regress/expected/partition_join.out b/src/test/regress/expected/partition_join.out
index 938cedd79ad..6101c8c7cf1 100644
--- a/src/test/regress/expected/partition_join.out
+++ b/src/test/regress/expected/partition_join.out
@@ -2568,24 +2568,24 @@ where not exists (select 1 from prtx2
-> Seq Scan on prtx1_1
Filter: ((a < 20) AND (c = 91))
-> Bitmap Heap Scan on prtx2_1
- Recheck Cond: ((c = 99) OR (b = (prtx1_1.b + 1)))
+ Recheck Cond: ((b = (prtx1_1.b + 1)) OR (c = 99))
Filter: (a = prtx1_1.a)
-> BitmapOr
- -> Bitmap Index Scan on prtx2_1_c_idx
- Index Cond: (c = 99)
-> Bitmap Index Scan on prtx2_1_b_idx
Index Cond: (b = (prtx1_1.b + 1))
+ -> Bitmap Index Scan on prtx2_1_c_idx
+ Index Cond: (c = 99)
-> Nested Loop Anti Join
-> Seq Scan on prtx1_2
Filter: ((a < 20) AND (c = 91))
-> Bitmap Heap Scan on prtx2_2
- Recheck Cond: ((c = 99) OR (b = (prtx1_2.b + 1)))
+ Recheck Cond: ((b = (prtx1_2.b + 1)) OR (c = 99))
Filter: (a = prtx1_2.a)
-> BitmapOr
- -> Bitmap Index Scan on prtx2_2_c_idx
- Index Cond: (c = 99)
-> Bitmap Index Scan on prtx2_2_b_idx
Index Cond: (b = (prtx1_2.b + 1))
+ -> Bitmap Index Scan on prtx2_2_c_idx
+ Index Cond: (c = 99)
(23 rows)
select * from prtx1
--
2.39.5 (Apple Git-154)
^ permalink raw reply [nested|flat] 29+ messages in thread
* Re: POC, WIP: OR-clause support for indexes
2015-12-26 18:04 POC, WIP: OR-clause support for indexes Teodor Sigaev <[email protected]>
2025-03-24 10:10 ` Re: POC, WIP: OR-clause support for indexes Andrei Lepikhov <[email protected]>
2025-03-24 10:46 ` Re: POC, WIP: OR-clause support for indexes Pavel Borisov <[email protected]>
2025-03-24 12:46 ` Re: POC, WIP: OR-clause support for indexes Alena Rybakina <[email protected]>
2025-03-27 23:18 ` Re: POC, WIP: OR-clause support for indexes Alexander Korotkov <[email protected]>
@ 2025-03-28 10:47 ` Pavel Borisov <[email protected]>
2 siblings, 0 replies; 29+ messages in thread
From: Pavel Borisov @ 2025-03-28 10:47 UTC (permalink / raw)
To: Alexander Korotkov <[email protected]>; +Cc: Alena Rybakina <[email protected]>; Andrei Lepikhov <[email protected]>; Alexander Lakhin <[email protected]>; [email protected]
Hi, Alexander!
d4378c0005e61b1bb7
On Fri, 28 Mar 2025 at 03:18, Alexander Korotkov <[email protected]> wrote:
>
> Hi!
>
> On Mon, Mar 24, 2025 at 2:46 PM Alena Rybakina
> <[email protected]> wrote:
> > I agree with Andrey's changes and think we should fix this, because otherwise it might be inconvenient.
> > For example, without this changes we will have to have different test output files for the same query for different versions of Postres in extensions if the whole change is only related to the order of column output for a transformation that was not applied.
>
> I agree with problem spotted by Andrei: it should be preferred to
> preserve original order of clauses as much as possible. The approach
> implemented in Andrei's patch seems fragile for me. Original order is
> preserved if we didn't find any group. But once we find a single
> group original order might be destroyed completely.
>
> The attached patch changes the reordering algorithm of
> group_similar_or_args() in the following way. We reorder each group
> of similar clauses so that the first item of the group stays in place,
> but all the other items are moved after it. So, if there are no
> similar clauses, the order of clauses stays the same. When there are
> some groups, only required reordering happens while the rest of the
> clauses remain in their places.
With your patch, I've re-checked that there are no changes in the
order of evaluation in plans compared to d4378c0005e61b1bb7
It might be good to also include Andrei's test from his last patch. i.e:
+-- No OR-clause groupings should happen - no clause permutations in
+-- the filtering conditions we should see in the EXPLAIN.
+EXPLAIN (COSTS OFF)
+SELECT * FROM tenk1 WHERE unique1 < 1 OR hundred < 2;
+
+-- OR clauses on the 'unique' column is grouped. So, clause
permutation happened
+-- We see it in the 'Recheck Cond' and order of BitmapOr subpaths:
index scan on
+-- the 'hundred' column occupies the first position.
+EXPLAIN (COSTS OFF)
+SELECT * FROM tenk1 WHERE unique1 < 1 OR unique1 < 3 OR hundred < 2;
I propose small changes for comments:
s/To have this property,/To do so,/g
s/in place, but all the/in place, and all the/g
s/some groups, only/some groups,/g
s/Resort/Re-sort/п
The patch overall looks good to me.
Regards,
Pavel Borisov
Supabase
^ permalink raw reply [nested|flat] 29+ messages in thread
* Re: POC, WIP: OR-clause support for indexes
2015-12-26 18:04 POC, WIP: OR-clause support for indexes Teodor Sigaev <[email protected]>
2025-03-24 10:10 ` Re: POC, WIP: OR-clause support for indexes Andrei Lepikhov <[email protected]>
2025-03-24 10:46 ` Re: POC, WIP: OR-clause support for indexes Pavel Borisov <[email protected]>
2025-03-24 12:46 ` Re: POC, WIP: OR-clause support for indexes Alena Rybakina <[email protected]>
2025-03-27 23:18 ` Re: POC, WIP: OR-clause support for indexes Alexander Korotkov <[email protected]>
@ 2025-03-28 11:32 ` Andrei Lepikhov <[email protected]>
2025-03-28 11:59 ` Re: POC, WIP: OR-clause support for indexes Alexander Korotkov <[email protected]>
2 siblings, 1 reply; 29+ messages in thread
From: Andrei Lepikhov @ 2025-03-28 11:32 UTC (permalink / raw)
To: Alexander Korotkov <[email protected]>; Alena Rybakina <[email protected]>; +Cc: Pavel Borisov <[email protected]>; Alexander Lakhin <[email protected]>; [email protected]
On 3/28/25 00:18, Alexander Korotkov wrote:
> The attached patch changes the reordering algorithm of
> group_similar_or_args() in the following way. We reorder each group
> of similar clauses so that the first item of the group stays in place,
> but all the other items are moved after it. So, if there are no
> similar clauses, the order of clauses stays the same. When there are
> some groups, only required reordering happens while the rest of the
> clauses remain in their places.
The patch looks good to me from a technical perspective. But it seems
like an overkill, isn't it?
You introduce additional CPU-consuming operations in the planning OR
operations.
My point is: 1) as Pavel has mentioned, Postgres doesn't guarantee the
evaluation/output order of the clauses at all. 2) we need that to keep
regression tests stable (don't forget extensions' and forks' developers
too). But it should be done once if we have no fluidity in OR clauses
order in general.
The trade-off with tricky query writers and regression tests may be
preserving the order until OR->ANY has happened. If it has happened,
just ensure the order is determined somehow. Except that, any other
spending on CPU cycles seems too expensive.
--
regards, Andrei Lepikhov
^ permalink raw reply [nested|flat] 29+ messages in thread
* Re: POC, WIP: OR-clause support for indexes
2015-12-26 18:04 POC, WIP: OR-clause support for indexes Teodor Sigaev <[email protected]>
2025-03-24 10:10 ` Re: POC, WIP: OR-clause support for indexes Andrei Lepikhov <[email protected]>
2025-03-24 10:46 ` Re: POC, WIP: OR-clause support for indexes Pavel Borisov <[email protected]>
2025-03-24 12:46 ` Re: POC, WIP: OR-clause support for indexes Alena Rybakina <[email protected]>
2025-03-27 23:18 ` Re: POC, WIP: OR-clause support for indexes Alexander Korotkov <[email protected]>
2025-03-28 11:32 ` Re: POC, WIP: OR-clause support for indexes Andrei Lepikhov <[email protected]>
@ 2025-03-28 11:59 ` Alexander Korotkov <[email protected]>
2025-03-28 12:15 ` Re: POC, WIP: OR-clause support for indexes Andrei Lepikhov <[email protected]>
0 siblings, 1 reply; 29+ messages in thread
From: Alexander Korotkov @ 2025-03-28 11:59 UTC (permalink / raw)
To: Andrei Lepikhov <[email protected]>; +Cc: Alena Rybakina <[email protected]>; Pavel Borisov <[email protected]>; Alexander Lakhin <[email protected]>; [email protected]
On Fri, Mar 28, 2025 at 1:32 PM Andrei Lepikhov <[email protected]> wrote:
> On 3/28/25 00:18, Alexander Korotkov wrote:
> > The attached patch changes the reordering algorithm of
> > group_similar_or_args() in the following way. We reorder each group
> > of similar clauses so that the first item of the group stays in place,
> > but all the other items are moved after it. So, if there are no
> > similar clauses, the order of clauses stays the same. When there are
> > some groups, only required reordering happens while the rest of the
> > clauses remain in their places.
> The patch looks good to me from a technical perspective. But it seems
> like an overkill, isn't it?
> You introduce additional CPU-consuming operations in the planning OR
> operations.
I don't think this is going to be CPU-consuming. I don't think this
is going to be measurable. This patch introduces one additional pass
over array of OrArgIndexMatch'es, and qsort of them. I think I've
seen places where we spend quadratic time over the number of
OR-clauses. Even calls of match_index_to_operand() for every clause
and every index look way more expensive.
> My point is: 1) as Pavel has mentioned, Postgres doesn't guarantee the
> evaluation/output order of the clauses at all. 2) we need that to keep
> regression tests stable (don't forget extensions' and forks' developers
> too). But it should be done once if we have no fluidity in OR clauses
> order in general.
> The trade-off with tricky query writers and regression tests may be
> preserving the order until OR->ANY has happened. If it has happened,
> just ensure the order is determined somehow. Except that, any other
> spending on CPU cycles seems too expensive.
I think my patch gives better determinism too. For instance, output
order doesn't depend on order of indexes in rel->indexlist.
------
Regards,
Alexander Korotkov
Supabase
^ permalink raw reply [nested|flat] 29+ messages in thread
* Re: POC, WIP: OR-clause support for indexes
2015-12-26 18:04 POC, WIP: OR-clause support for indexes Teodor Sigaev <[email protected]>
2025-03-24 10:10 ` Re: POC, WIP: OR-clause support for indexes Andrei Lepikhov <[email protected]>
2025-03-24 10:46 ` Re: POC, WIP: OR-clause support for indexes Pavel Borisov <[email protected]>
2025-03-24 12:46 ` Re: POC, WIP: OR-clause support for indexes Alena Rybakina <[email protected]>
2025-03-27 23:18 ` Re: POC, WIP: OR-clause support for indexes Alexander Korotkov <[email protected]>
2025-03-28 11:32 ` Re: POC, WIP: OR-clause support for indexes Andrei Lepikhov <[email protected]>
2025-03-28 11:59 ` Re: POC, WIP: OR-clause support for indexes Alexander Korotkov <[email protected]>
@ 2025-03-28 12:15 ` Andrei Lepikhov <[email protected]>
0 siblings, 0 replies; 29+ messages in thread
From: Andrei Lepikhov @ 2025-03-28 12:15 UTC (permalink / raw)
To: Alexander Korotkov <[email protected]>; +Cc: Alena Rybakina <[email protected]>; Pavel Borisov <[email protected]>; Alexander Lakhin <[email protected]>; [email protected]
On 3/28/25 12:59, Alexander Korotkov wrote:
> On Fri, Mar 28, 2025 at 1:32 PM Andrei Lepikhov <[email protected]> wrote:
> I don't think this is going to be CPU-consuming. I don't think this
> is going to be measurable. This patch introduces one additional pass
> over array of OrArgIndexMatch'es, and qsort of them. I think I've
> seen places where we spend quadratic time over the number of
> OR-clauses. Even calls of match_index_to_operand() for every clause
> and every index look way more expensive.
Ok, I have no more objections.
> I think my patch gives better determinism too. For instance, output
> order doesn't depend on order of indexes in rel->indexlist.
Nice!
--
regards, Andrei Lepikhov
^ permalink raw reply [nested|flat] 29+ messages in thread
* Re: POC, WIP: OR-clause support for indexes
2015-12-26 18:04 POC, WIP: OR-clause support for indexes Teodor Sigaev <[email protected]>
2025-03-24 10:10 ` Re: POC, WIP: OR-clause support for indexes Andrei Lepikhov <[email protected]>
2025-03-24 10:46 ` Re: POC, WIP: OR-clause support for indexes Pavel Borisov <[email protected]>
2025-03-24 12:46 ` Re: POC, WIP: OR-clause support for indexes Alena Rybakina <[email protected]>
2025-03-27 23:18 ` Re: POC, WIP: OR-clause support for indexes Alexander Korotkov <[email protected]>
@ 2025-03-28 12:23 ` Alena Rybakina <[email protected]>
2025-03-28 12:31 ` Re: POC, WIP: OR-clause support for indexes Alena Rybakina <[email protected]>
2 siblings, 1 reply; 29+ messages in thread
From: Alena Rybakina @ 2025-03-28 12:23 UTC (permalink / raw)
To: Alexander Korotkov <[email protected]>; +Cc: Pavel Borisov <[email protected]>; Andrei Lepikhov <[email protected]>; Alexander Lakhin <[email protected]>; [email protected]
On 28.03.2025 02:18, Alexander Korotkov wrote:
> Hi!
>
> On Mon, Mar 24, 2025 at 2:46 PM Alena Rybakina
> <[email protected]> wrote:
>> I agree with Andrey's changes and think we should fix this, because otherwise it might be inconvenient.
>> For example, without this changes we will have to have different test output files for the same query for different versions of Postres in extensions if the whole change is only related to the order of column output for a transformation that was not applied.
> I agree with problem spotted by Andrei: it should be preferred to
> preserve original order of clauses as much as possible. The approach
> implemented in Andrei's patch seems fragile for me. Original order is
> preserved if we didn't find any group. But once we find a single
> group original order might be destroyed completely.
>
> The attached patch changes the reordering algorithm of
> group_similar_or_args() in the following way. We reorder each group
> of similar clauses so that the first item of the group stays in place,
> but all the other items are moved after it. So, if there are no
> similar clauses, the order of clauses stays the same. When there are
> some groups, only required reordering happens while the rest of the
> clauses remain in their places.
>
I agree with your code in general, but to be honest, double qsort
confused me a little.
I understood why it is needed - we need to sort the elements so that
they stand next to each other if they can be assigned to the same group,
and then sort the groups themselves according to the set identifier.
I may be missing something, but in the worst case we can get the
complexity of qsort O(n^2), right? And I saw the letter where you
mentioned this, but it is possible to use mergesort algorithm instead of
qsort, which in the worst case gives n * O(n) complexity?
--
Regards,
Alena Rybakina
Postgres Professional
^ permalink raw reply [nested|flat] 29+ messages in thread
* Re: POC, WIP: OR-clause support for indexes
2015-12-26 18:04 POC, WIP: OR-clause support for indexes Teodor Sigaev <[email protected]>
2025-03-24 10:10 ` Re: POC, WIP: OR-clause support for indexes Andrei Lepikhov <[email protected]>
2025-03-24 10:46 ` Re: POC, WIP: OR-clause support for indexes Pavel Borisov <[email protected]>
2025-03-24 12:46 ` Re: POC, WIP: OR-clause support for indexes Alena Rybakina <[email protected]>
2025-03-27 23:18 ` Re: POC, WIP: OR-clause support for indexes Alexander Korotkov <[email protected]>
2025-03-28 12:23 ` Re: POC, WIP: OR-clause support for indexes Alena Rybakina <[email protected]>
@ 2025-03-28 12:31 ` Alena Rybakina <[email protected]>
0 siblings, 0 replies; 29+ messages in thread
From: Alena Rybakina @ 2025-03-28 12:31 UTC (permalink / raw)
To: Alexander Korotkov <[email protected]>; +Cc: Pavel Borisov <[email protected]>; Andrei Lepikhov <[email protected]>; Alexander Lakhin <[email protected]>; [email protected]
On 28.03.2025 15:23, Alena Rybakina wrote:
>
> I agree with your code in general, but to be honest, double qsort
> confused me a little.
>
> I understood why it is needed - we need to sort the elements so that
> they stand next to each other if they can be assigned to the same
> group, and then sort the groups themselves according to the set
> identifier.
>
> I may be missing something, but in the worst case we can get the
> complexity of qsort O(n^2), right? And I saw the letter where you
> mentioned this, but it is possible to use mergesort algorithm instead
> of qsort, which in the worst case gives n * O(n) complexity?
>
No, sorry, I was wrong here and it is impossible to rewrite it this way.
I apologize, I agree with your code.
--
Regards,
Alena Rybakina
Postgres Professional
^ permalink raw reply [nested|flat] 29+ messages in thread
end of thread, other threads:[~2025-03-28 12:31 UTC | newest]
Thread overview: 29+ messages (download: mbox mbox.gz follow: Atom feed)
-- links below jump to the message on this page --
2015-12-26 18:04 POC, WIP: OR-clause support for indexes Teodor Sigaev <[email protected]>
2015-12-26 18:40 ` Feng Tian <[email protected]>
2015-12-26 19:25 ` Teodor Sigaev <[email protected]>
2016-01-11 03:16 ` David Rowley <[email protected]>
2016-01-28 11:16 ` Alvaro Herrera <[email protected]>
2016-02-29 18:04 ` Teodor Sigaev <[email protected]>
2016-03-10 13:04 ` Tomas Vondra <[email protected]>
2016-03-17 17:19 ` Teodor Sigaev <[email protected]>
2016-03-20 00:44 ` Tomas Vondra <[email protected]>
2016-03-25 15:13 ` David Steele <[email protected]>
2016-03-29 14:01 ` David Steele <[email protected]>
2016-03-18 16:38 ` Teodor Sigaev <[email protected]>
2016-03-18 23:46 ` Andreas Karlsson <[email protected]>
2022-12-28 04:19 ` Andrey Lepikhov <[email protected]>
2024-01-27 02:58 ` vignesh C <[email protected]>
2024-01-30 14:15 ` jian he <[email protected]>
2024-01-31 02:55 ` jian he <[email protected]>
2024-01-31 10:15 ` jian he <[email protected]>
2024-01-31 11:10 ` Alena Rybakina <[email protected]>
2025-03-24 10:10 ` Andrei Lepikhov <[email protected]>
2025-03-24 10:46 ` Pavel Borisov <[email protected]>
2025-03-24 12:46 ` Alena Rybakina <[email protected]>
2025-03-27 23:18 ` Alexander Korotkov <[email protected]>
2025-03-28 10:47 ` Pavel Borisov <[email protected]>
2025-03-28 11:32 ` Andrei Lepikhov <[email protected]>
2025-03-28 11:59 ` Alexander Korotkov <[email protected]>
2025-03-28 12:15 ` Andrei Lepikhov <[email protected]>
2025-03-28 12:23 ` Alena Rybakina <[email protected]>
2025-03-28 12:31 ` Alena Rybakina <[email protected]>
This inbox is served by agora; see mirroring instructions
for how to clone and mirror all data and code used for this inbox