public inbox for [email protected]
help / color / mirror / Atom feed[PATCH] Allow Sort nodes to use the fast "single datum" tuplesort.
8+ messages / 3 participants
[nested] [flat]
* [PATCH] Allow Sort nodes to use the fast "single datum" tuplesort.
@ 2021-07-05 10:45 Ronan Dunklau <[email protected]>
0 siblings, 0 replies; 8+ messages in thread
From: Ronan Dunklau @ 2021-07-05 10:45 UTC (permalink / raw)
The sorting code in nodeagg made use of this API, but not the regular
nodesort one. This is a POC seeing how it can be done.
---
src/backend/executor/nodeSort.c | 62 +++++++++++++++++++++++++--------
src/include/nodes/execnodes.h | 1 +
2 files changed, 48 insertions(+), 15 deletions(-)
diff --git a/src/backend/executor/nodeSort.c b/src/backend/executor/nodeSort.c
index b99027e0d7..03873b0d58 100644
--- a/src/backend/executor/nodeSort.c
+++ b/src/backend/executor/nodeSort.c
@@ -44,6 +44,7 @@ ExecSort(PlanState *pstate)
ScanDirection dir;
Tuplesortstate *tuplesortstate;
TupleTableSlot *slot;
+ Sort *plannode = (Sort *) node->ss.ps.plan;
CHECK_FOR_INTERRUPTS();
@@ -64,7 +65,6 @@ ExecSort(PlanState *pstate)
if (!node->sort_Done)
{
- Sort *plannode = (Sort *) node->ss.ps.plan;
PlanState *outerNode;
TupleDesc tupDesc;
@@ -85,16 +85,29 @@ ExecSort(PlanState *pstate)
outerNode = outerPlanState(node);
tupDesc = ExecGetResultType(outerNode);
+ if ((tupDesc->natts == 1) &&
+ (TupleDescAttr(tupDesc, 0) ->attbyval) &&
+ !node->bounded)
+ {
- tuplesortstate = tuplesort_begin_heap(tupDesc,
- plannode->numCols,
- plannode->sortColIdx,
- plannode->sortOperators,
- plannode->collations,
- plannode->nullsFirst,
- work_mem,
- NULL,
- node->randomAccess);
+ node->is_single_val = true;
+ tuplesortstate = tuplesort_begin_datum(TupleDescAttr(tupDesc, 0)->atttypid,
+ plannode->sortOperators[0],
+ plannode->collations[0],
+ plannode->nullsFirst[0],
+ work_mem,
+ NULL,
+ node->randomAccess);
+ } else
+ tuplesortstate = tuplesort_begin_heap(tupDesc,
+ plannode->numCols,
+ plannode->sortColIdx,
+ plannode->sortOperators,
+ plannode->collations,
+ plannode->nullsFirst,
+ work_mem,
+ NULL,
+ node->randomAccess);
if (node->bounded)
tuplesort_set_bound(tuplesortstate, node->bound);
node->tuplesortstate = (void *) tuplesortstate;
@@ -109,8 +122,15 @@ ExecSort(PlanState *pstate)
if (TupIsNull(slot))
break;
-
- tuplesort_puttupleslot(tuplesortstate, slot);
+ if(node->is_single_val)
+ {
+ slot_getsomeattrs(slot, 1);
+ tuplesort_putdatum(tuplesortstate,
+ slot->tts_values[0],
+ slot->tts_isnull[0]);
+ } else {
+ tuplesort_puttupleslot(tuplesortstate, slot);
+ }
}
/*
@@ -150,9 +170,17 @@ ExecSort(PlanState *pstate)
* next fetch from the tuplesort.
*/
slot = node->ss.ps.ps_ResultTupleSlot;
- (void) tuplesort_gettupleslot(tuplesortstate,
- ScanDirectionIsForward(dir),
- false, slot, NULL);
+ if (node->is_single_val)
+ {
+ ExecClearTuple(slot);
+ if(tuplesort_getdatum(tuplesortstate, ScanDirectionIsForward(dir),
+ &(slot->tts_values[0]), &(slot->tts_isnull[0]), NULL))
+ ExecStoreVirtualTuple(slot);
+ }
+ else
+ (void) tuplesort_gettupleslot(tuplesortstate,
+ ScanDirectionIsForward(dir),
+ false, slot, NULL);
return slot;
}
@@ -167,6 +195,7 @@ SortState *
ExecInitSort(Sort *node, EState *estate, int eflags)
{
SortState *sortstate;
+ TupleDesc out_tuple_desc;
SO1_printf("ExecInitSort: %s\n",
"initializing sort node");
@@ -191,6 +220,7 @@ ExecInitSort(Sort *node, EState *estate, int eflags)
sortstate->bounded = false;
sortstate->sort_Done = false;
sortstate->tuplesortstate = NULL;
+ sortstate->is_single_val = false;
/*
* Miscellaneous initialization
@@ -208,6 +238,8 @@ ExecInitSort(Sort *node, EState *estate, int eflags)
eflags &= ~(EXEC_FLAG_REWIND | EXEC_FLAG_BACKWARD | EXEC_FLAG_MARK);
outerPlanState(sortstate) = ExecInitNode(outerPlan(node), estate, eflags);
+ out_tuple_desc = outerPlanState(sortstate)->ps_ResultTupleDesc;
+
/*
* Initialize scan slot and type.
diff --git a/src/include/nodes/execnodes.h b/src/include/nodes/execnodes.h
index 0ec5509e7e..643f416c54 100644
--- a/src/include/nodes/execnodes.h
+++ b/src/include/nodes/execnodes.h
@@ -2151,6 +2151,7 @@ typedef struct SortState
int64 bound_Done; /* value of bound we did the sort with */
void *tuplesortstate; /* private state of tuplesort.c */
bool am_worker; /* are we a worker? */
+ bool is_single_val; /* are we using the single value optimization ? */
SharedSortInfo *shared_info; /* one entry per worker */
} SortState;
--
2.32.0
--nextPart3227936.8YSYcEGHcz--
^ permalink raw reply [nested|flat] 8+ messages in thread
* Re: POC, WIP: OR-clause support for indexes
@ 2024-07-21 22:53 Alena Rybakina <[email protected]>
2024-07-22 00:52 ` Re: POC, WIP: OR-clause support for indexes Alexander Korotkov <[email protected]>
0 siblings, 1 reply; 8+ messages in thread
From: Alena Rybakina @ 2024-07-21 22:53 UTC (permalink / raw)
To: Nikolay Shaplov <[email protected]>; Alexander Korotkov <[email protected]>; +Cc: [email protected]; Andrei Lepikhov <[email protected]>; jian he <[email protected]>; Robert Haas <[email protected]>; pgsql-hackers; Peter Geoghegan <[email protected]>; Finnerty, Jim <[email protected]>; Marcos Pegoraro <[email protected]>; [email protected]; Tomas Vondra <[email protected]>; Peter Eisentraut <[email protected]>; Ranier Vilela <[email protected]>
Hi! Thank you for your contribution to this thread!
To be honest,I saw a larger problem. Look at the query bellow:
master:
alena@postgres=# create table t (a int not null, b int not null, c int
not null);
insert into t (select 1, 1, i from generate_series(1,10000) i);
insert into t (select i, 2, 2 from generate_series(1,10000) i);
create index t_a_b_idx on t (a, b);
create statistics t_a_b_stat (mcv) on a, b from t;
create statistics t_b_c_stat (mcv) on b, c from t;
vacuum analyze t;
CREATE TABLE
INSERT 0 10000
INSERT 0 10000
CREATE INDEX
CREATE STATISTICS
CREATE STATISTICS
VACUUM
alena@postgres=# explain select * from t where a = 1 and (b = 1 or b =
2) and c = 2;
QUERY PLAN
------------------------------------------------------------------------------
Bitmap Heap Scan on t (cost=156.55..465.57 rows=5001 width=12)
Recheck Cond: (a = 1)
Filter: ((c = 2) AND ((b = 1) OR (b = 2)))
-> Bitmap Index Scan on t_a_b_idx (cost=0.00..155.29 rows=10001
width=0)
Index Cond: (a = 1)
(5 rows)
The query plan if v26[0] and v27[1] versions are equal and wrong in my
opinion -where is c=2 expression?
v27 [1]
alena@postgres=# explain select * from t where a = 1 and (b = 1 or b =
2) and c = 2;
QUERY PLAN
------------------------------------------------------------------------------
Bitmap Heap Scan on t (cost=165.85..474.87 rows=5001 width=12)
Recheck Cond: ((a = 1) AND (b = ANY ('{1,2}'::integer[])))
Filter: (c = 2)
-> Bitmap Index Scan on t_a_b_idx (cost=0.00..164.59 rows=10001
width=0)
Index Cond: ((a = 1) AND (b = ANY ('{1,2}'::integer[])))
(5 rows)
v26 [0]
alena@postgres=# explain select * from t where a = 1 and (b = 1 or b =
2) and c = 2;
QUERY PLAN
------------------------------------------------------------------------------
Bitmap Heap Scan on t (cost=165.85..449.86 rows=5001 width=12)
Recheck Cond: ((a = 1) AND (b = ANY ('{1,2}'::integer[])))
Filter: (c = 2)
-> Bitmap Index Scan on t_a_b_idx (cost=0.00..164.59 rows=10001
width=0)
Index Cond: ((a = 1) AND (b = ANY ('{1,2}'::integer[])))
(5 rows)
In addition, I noticed that the ANY expression will be formed only for
first group and ignore for others, like in the sample bellow:
v26 version [0]:
alena@postgres=# explain select * from t where (b = 1 or b = 2) and (a =
2 or a=3);
QUERY PLAN
-----------------------------------------------------------------------------------
Index Scan using t_a_b_idx on t (cost=0.29..24.75 rows=2 width=12)
Index Cond: ((a = ANY ('{2,3}'::integer[])) AND (b = ANY
('{1,2}'::integer[])))
(2 rows)
v27 version [1]:
alena@postgres=# explain select * from t where (b = 1 or b = 2 or a = 2
or a=3);
QUERY PLAN
--------------------------------------------------------
Seq Scan on t (cost=0.00..509.00 rows=14999 width=12)
Filter: ((b = 1) OR (b = 2) OR (a = 2) OR (a = 3))
(2 rows)
alena@postgres=# create index a_idx on t(a);
CREATE INDEX
alena@postgres=# create index b_idx on t(b);
CREATE INDEX
alena@postgres=# analyze;
ANALYZE
v26:
alena@postgres=# explain select * from t where (b = 1 or b = 2 or a = 2
or a=3);
QUERY PLAN
------------------------------------------------------------------------------------
Bitmap Heap Scan on t (cost=17.18..30.94 rows=4 width=12)
Recheck Cond: ((a = ANY ('{2,3}'::integer[])) OR (a = ANY
('{2,3}'::integer[])))
-> BitmapOr (cost=17.18..17.18 rows=4 width=0)
-> Bitmap Index Scan on a_idx (cost=0.00..8.59 rows=2 width=0)
Index Cond: (a = ANY ('{2,3}'::integer[]))
-> Bitmap Index Scan on a_idx (cost=0.00..8.59 rows=2 width=0)
Index Cond: (a = ANY ('{2,3}'::integer[]))
(7 rows)
v27:
alena@postgres=# explain select * from t where (b = 1 or b = 2 or a = 2
or a=3);
QUERY PLAN
--------------------------------------------------------
Seq Scan on t (cost=0.00..509.00 rows=14999 width=12)
Filter: ((b = 1) OR (b = 2) OR (a = 2) OR (a = 3))
(2 rows)
The behavior in version 26 is incorrect, but in version 27, it does not
select anything other than seqscan
Since Thursday I have been trying to add the code forming groups of
identical "OR" expressions, as in version 26. I'm currently debugging
errors.
On 21.07.2024 11:17, Nikolay Shaplov wrote:
> В письме от среда, 17 июля 2024 г. 22:36:19 MSK пользователь Alexander
> Korotkov написал:
>
> Hi All!
>
> I am continue reading the patch, now it's newer version
>
> First main question:
>
> As far a I can get, the entry point for OR->ANY convertation have been moved
> to match_clause_to_indexcol funtion, that checks if some restriction can use
> index for performance.
>
> The thing I do not understand what match_clause_to_indexcol actually received
> as arguments. Should this be set of expressions with OR in between grouped by
> one of the expression argument?
>
> If not I do not understand how this ever should work.
The point is that we do the transformation for those columns that have
an index, since this transformation is most useful in these cases. we
pass the parameters index relation and column number to find out
information about it.
>
> The rest is about code readability
>
>> + if (bms_is_member(index->rel->relid, rinfo->right_relids))
>> + return NULL;
To be honest, I'm not sure that I understand your question. Could you
explain me?
> This check it totally not obvious for person who is not deep into postgres
> code. There should go comment explaining what are we checking for, and why it
> does not suit our purposes
>
>
>> + foreach(lc, orclause->args)
>> + {
I'll add it, thank you.
> Being no great expert in postgres code, I am confused what are we iterating on
> here? Two arguments of OR statement? (a>1) OR (b>2) those in brackets? Or
> what? Comment explaining that would be a great help here.
>
>
>> +if (sub_rinfo->is_pushed_down != rinfo->is_pushed_down ||
>> + sub_rinfo->is_clone != rinfo->is_clone ||
>> + sub_rinfo->security_level != rinfo->security_level ||
>> + !bms_equal(sub_rinfo->required_relids, rinfo->required_relids) ||
>> + !bms_equal(sub_rinfo->incompatible_relids, rinfo-
> incompatible_relids) ||
>> + !bms_equal(sub_rinfo->outer_relids, rinfo->outer_relids))
>> + {
I'll add it.
> This check it totally mind-blowing... What in the name of existence is going
> on here?
>
> I would suggest to split these checks into parts (compiler optimizer should
> take care about overhead) and give each part a sane explanation.
Alexander suggested moving the transformation to another place and it is
correct in my opinion. All previous problems are now gone.
But he also cut the code - he made a transformation for one group of
"OR" expressions. I agree, some parts don't yet
provide enough explanation of what's going on. I'm correcting this now.
Speaking of the changes according to your suggestions, I made them in
version 26 [0] and just part of that code will end up in the current
version of the patch to process all groups of "OR" expressions.
I'll try to do this as best I can, but it took me a while to figure out
how to properly organize RestrictInfo in the index.
[0]
https://www.postgresql.org/message-id/3b9bb831-da52-4779-8f3e-f8b6b83ba41f%40postgrespro.ru
[1]
https://www.postgresql.org/message-id/CAPpHfdvhWE5pArZhgJeLViLx3-A3rxEREZvfkTj3E%3Dh7q-Bx9w%40mail.g...
--
Regards,
Alena Rybakina
Postgres Professional:http://www.postgrespro.com
The Russian Postgres Company
^ permalink raw reply [nested|flat] 8+ messages in thread
* Re: POC, WIP: OR-clause support for indexes
2024-07-21 22:53 Re: POC, WIP: OR-clause support for indexes Alena Rybakina <[email protected]>
@ 2024-07-22 00:52 ` Alexander Korotkov <[email protected]>
2024-07-22 00:54 ` Re: POC, WIP: OR-clause support for indexes Alexander Korotkov <[email protected]>
2024-07-25 14:04 ` Re: POC, WIP: OR-clause support for indexes Alena Rybakina <[email protected]>
0 siblings, 2 replies; 8+ messages in thread
From: Alexander Korotkov @ 2024-07-22 00:52 UTC (permalink / raw)
To: Alena Rybakina <[email protected]>; +Cc: Nikolay Shaplov <[email protected]>; [email protected]; Andrei Lepikhov <[email protected]>; jian he <[email protected]>; Robert Haas <[email protected]>; pgsql-hackers; Peter Geoghegan <[email protected]>; Finnerty, Jim <[email protected]>; Marcos Pegoraro <[email protected]>; [email protected]; Tomas Vondra <[email protected]>; Peter Eisentraut <[email protected]>; Ranier Vilela <[email protected]>
Hi, Alena!
Let me answer to some of your findings.
On Mon, Jul 22, 2024 at 12:53 AM Alena Rybakina
<[email protected]> wrote:
> To be honest,I saw a larger problem. Look at the query bellow:
>
> master:
>
> alena@postgres=# create table t (a int not null, b int not null, c int not null);
> insert into t (select 1, 1, i from generate_series(1,10000) i);
> insert into t (select i, 2, 2 from generate_series(1,10000) i);
> create index t_a_b_idx on t (a, b);
Just a side note. As I mention in [1], there is missing statement
create index t_a_b_idx on t (a, b);
to get same plan as in [2].
> create statistics t_a_b_stat (mcv) on a, b from t;
> create statistics t_b_c_stat (mcv) on b, c from t;
> vacuum analyze t;
> CREATE TABLE
> INSERT 0 10000
> INSERT 0 10000
> CREATE INDEX
> CREATE STATISTICS
> CREATE STATISTICS
> VACUUM
> alena@postgres=# explain select * from t where a = 1 and (b = 1 or b = 2) and c = 2;
> QUERY PLAN
> ------------------------------------------------------------------------------
> Bitmap Heap Scan on t (cost=156.55..465.57 rows=5001 width=12)
> Recheck Cond: (a = 1)
> Filter: ((c = 2) AND ((b = 1) OR (b = 2)))
> -> Bitmap Index Scan on t_a_b_idx (cost=0.00..155.29 rows=10001 width=0)
> Index Cond: (a = 1)
> (5 rows)
>
>
> The query plan if v26[0] and v27[1] versions are equal and wrong in my opinion -where is c=2 expression?
>
> v27 [1]
> alena@postgres=# explain select * from t where a = 1 and (b = 1 or b = 2) and c = 2;
> QUERY PLAN
> ------------------------------------------------------------------------------
> Bitmap Heap Scan on t (cost=165.85..474.87 rows=5001 width=12)
> Recheck Cond: ((a = 1) AND (b = ANY ('{1,2}'::integer[])))
> Filter: (c = 2)
> -> Bitmap Index Scan on t_a_b_idx (cost=0.00..164.59 rows=10001 width=0)
> Index Cond: ((a = 1) AND (b = ANY ('{1,2}'::integer[])))
> (5 rows)
> v26 [0]
> alena@postgres=# explain select * from t where a = 1 and (b = 1 or b = 2) and c = 2;
> QUERY PLAN
> ------------------------------------------------------------------------------
> Bitmap Heap Scan on t (cost=165.85..449.86 rows=5001 width=12)
> Recheck Cond: ((a = 1) AND (b = ANY ('{1,2}'::integer[])))
> Filter: (c = 2)
> -> Bitmap Index Scan on t_a_b_idx (cost=0.00..164.59 rows=10001 width=0)
> Index Cond: ((a = 1) AND (b = ANY ('{1,2}'::integer[])))
> (5 rows)
I think both v26 and v27 are correct here. The c = 2 condition is in
the Filter.
> In addition, I noticed that the ANY expression will be formed only for first group and ignore for others, like in the sample bellow:
>
> v26 version [0]:
>
> alena@postgres=# explain select * from t where (b = 1 or b = 2) and (a = 2 or a=3);
> QUERY PLAN
> -----------------------------------------------------------------------------------
> Index Scan using t_a_b_idx on t (cost=0.29..24.75 rows=2 width=12)
> Index Cond: ((a = ANY ('{2,3}'::integer[])) AND (b = ANY ('{1,2}'::integer[])))
> (2 rows)
>
> v27 version [1]:
>
> alena@postgres=# explain select * from t where (b = 1 or b = 2 or a = 2 or a=3);
> QUERY PLAN
> --------------------------------------------------------
> Seq Scan on t (cost=0.00..509.00 rows=14999 width=12)
> Filter: ((b = 1) OR (b = 2) OR (a = 2) OR (a = 3))
> (2 rows)
Did you notice you're running different queries on v26 and v27 here?
If you will run ton v27 the same query you run on v26, the plan also
will be the same.
> alena@postgres=# create index a_idx on t(a);
> CREATE INDEX
> alena@postgres=# create index b_idx on t(b);
> CREATE INDEX
> alena@postgres=# analyze;
> ANALYZE
>
> v26:
>
> alena@postgres=# explain select * from t where (b = 1 or b = 2 or a = 2 or a=3);
> QUERY PLAN
> ------------------------------------------------------------------------------------
> Bitmap Heap Scan on t (cost=17.18..30.94 rows=4 width=12)
> Recheck Cond: ((a = ANY ('{2,3}'::integer[])) OR (a = ANY ('{2,3}'::integer[])))
> -> BitmapOr (cost=17.18..17.18 rows=4 width=0)
> -> Bitmap Index Scan on a_idx (cost=0.00..8.59 rows=2 width=0)
> Index Cond: (a = ANY ('{2,3}'::integer[]))
> -> Bitmap Index Scan on a_idx (cost=0.00..8.59 rows=2 width=0)
> Index Cond: (a = ANY ('{2,3}'::integer[]))
> (7 rows)
>
> v27:
>
> alena@postgres=# explain select * from t where (b = 1 or b = 2 or a = 2 or a=3);
> QUERY PLAN
> --------------------------------------------------------
> Seq Scan on t (cost=0.00..509.00 rows=14999 width=12)
> Filter: ((b = 1) OR (b = 2) OR (a = 2) OR (a = 3))
> (2 rows)
>
> The behavior in version 26 is incorrect, but in version 27, it does not select anything other than seqscan
Please, check that there is still possibility to the generate BitmapOr plan.
# explain select * from t where (b = 1 or b = 2 or a = 2 or a = 3);
QUERY PLAN
------------------------------------------------------------------------------------
Bitmap Heap Scan on t (cost=326.16..835.16 rows=14999 width=12)
Recheck Cond: ((b = 1) OR (b = 2) OR (a = 2) OR (a = 3))
-> BitmapOr (cost=326.16..326.16 rows=20000 width=0)
-> Bitmap Index Scan on t_b_c_idx (cost=0.00..151.29
rows=10000 width=0)
Index Cond: (b = 1)
-> Bitmap Index Scan on t_b_c_idx (cost=0.00..151.29
rows=10000 width=0)
Index Cond: (b = 2)
-> Bitmap Index Scan on t_a_b_idx (cost=0.00..4.29 rows=1 width=0)
Index Cond: (a = 2)
-> Bitmap Index Scan on t_a_b_idx (cost=0.00..4.29 rows=1 width=0)
Index Cond: (a = 3)
It has higher cost than SeqScan plan, but I think it would be selected
on larger tables. And yes, this is not ideal, because it fails to
generate BitmapOr over two IndexScans on SAOPs. But it's not worse
than what current master does. An optimization doesn't have to do
everything it could possible do. So, I think this could be improved
in a separate patch.
Links
1. https://www.postgresql.org/message-id/CAPpHfdvhWE5pArZhgJeLViLx3-A3rxEREZvfkTj3E%3Dh7q-Bx9w%40mail.g...
2. https://www.postgresql.org/message-id/CAPpHfdtSXxhdv3mLOLjEewGeXJ%2BFtfhjqodn1WWuq5JLsKx48g%40mail.g...
------
Regards,
Alexander Korotkov
Supabase
^ permalink raw reply [nested|flat] 8+ messages in thread
* Re: POC, WIP: OR-clause support for indexes
2024-07-21 22:53 Re: POC, WIP: OR-clause support for indexes Alena Rybakina <[email protected]>
2024-07-22 00:52 ` Re: POC, WIP: OR-clause support for indexes Alexander Korotkov <[email protected]>
@ 2024-07-22 00:54 ` Alexander Korotkov <[email protected]>
1 sibling, 0 replies; 8+ messages in thread
From: Alexander Korotkov @ 2024-07-22 00:54 UTC (permalink / raw)
To: Alena Rybakina <[email protected]>; +Cc: Nikolay Shaplov <[email protected]>; [email protected]; Andrei Lepikhov <[email protected]>; jian he <[email protected]>; Robert Haas <[email protected]>; pgsql-hackers; Peter Geoghegan <[email protected]>; Marcos Pegoraro <[email protected]>; [email protected]; Tomas Vondra <[email protected]>; Peter Eisentraut <[email protected]>; Ranier Vilela <[email protected]>
On Mon, Jul 22, 2024 at 3:52 AM Alexander Korotkov <[email protected]> wrote:
> Please, check that there is still possibility to the generate BitmapOr plan.
>
> # explain select * from t where (b = 1 or b = 2 or a = 2 or a = 3);
> QUERY PLAN
> ------------------------------------------------------------------------------------
> Bitmap Heap Scan on t (cost=326.16..835.16 rows=14999 width=12)
> Recheck Cond: ((b = 1) OR (b = 2) OR (a = 2) OR (a = 3))
> -> BitmapOr (cost=326.16..326.16 rows=20000 width=0)
> -> Bitmap Index Scan on t_b_c_idx (cost=0.00..151.29
> rows=10000 width=0)
> Index Cond: (b = 1)
> -> Bitmap Index Scan on t_b_c_idx (cost=0.00..151.29
> rows=10000 width=0)
> Index Cond: (b = 2)
> -> Bitmap Index Scan on t_a_b_idx (cost=0.00..4.29 rows=1 width=0)
> Index Cond: (a = 2)
> -> Bitmap Index Scan on t_a_b_idx (cost=0.00..4.29 rows=1 width=0)
> Index Cond: (a = 3)
Forgot to mention that I have to
# set enable_seqscan = off;
to get this plan.
------
Regards,
Alexander Korotkov
Supabase
^ permalink raw reply [nested|flat] 8+ messages in thread
* Re: POC, WIP: OR-clause support for indexes
2024-07-21 22:53 Re: POC, WIP: OR-clause support for indexes Alena Rybakina <[email protected]>
2024-07-22 00:52 ` Re: POC, WIP: OR-clause support for indexes Alexander Korotkov <[email protected]>
@ 2024-07-25 14:04 ` Alena Rybakina <[email protected]>
2024-07-27 10:56 ` Re: POC, WIP: OR-clause support for indexes Alexander Korotkov <[email protected]>
1 sibling, 1 reply; 8+ messages in thread
From: Alena Rybakina @ 2024-07-25 14:04 UTC (permalink / raw)
To: Alexander Korotkov <[email protected]>; +Cc: Nikolay Shaplov <[email protected]>; [email protected]; Andrei Lepikhov <[email protected]>; jian he <[email protected]>; Robert Haas <[email protected]>; pgsql-hackers; Peter Geoghegan <[email protected]>; Finnerty, Jim <[email protected]>; Marcos Pegoraro <[email protected]>; [email protected]; Tomas Vondra <[email protected]>; Peter Eisentraut <[email protected]>; Ranier Vilela <[email protected]>
On 22.07.2024 03:52, Alexander Korotkov wrote:
> Hi, Alena!
>
> Let me answer to some of your findings.
>
> On Mon, Jul 22, 2024 at 12:53 AM Alena Rybakina
> <[email protected]> wrote:
>> To be honest,I saw a larger problem. Look at the query bellow:
>>
>> master:
>>
>> alena@postgres=# create table t (a int not null, b int not null, c int not null);
>> insert into t (select 1, 1, i from generate_series(1,10000) i);
>> insert into t (select i, 2, 2 from generate_series(1,10000) i);
>> create index t_a_b_idx on t (a, b);
> Just a side note. As I mention in [1], there is missing statement
> create index t_a_b_idx on t (a, b);
> to get same plan as in [2].
>
>> create statistics t_a_b_stat (mcv) on a, b from t;
>> create statistics t_b_c_stat (mcv) on b, c from t;
>> vacuum analyze t;
>> CREATE TABLE
>> INSERT 0 10000
>> INSERT 0 10000
>> CREATE INDEX
>> CREATE STATISTICS
>> CREATE STATISTICS
>> VACUUM
>> alena@postgres=# explain select * from t where a = 1 and (b = 1 or b = 2) and c = 2;
>> QUERY PLAN
>> ------------------------------------------------------------------------------
>> Bitmap Heap Scan on t (cost=156.55..465.57 rows=5001 width=12)
>> Recheck Cond: (a = 1)
>> Filter: ((c = 2) AND ((b = 1) OR (b = 2)))
>> -> Bitmap Index Scan on t_a_b_idx (cost=0.00..155.29 rows=10001 width=0)
>> Index Cond: (a = 1)
>> (5 rows)
>>
>>
>> The query plan if v26[0] and v27[1] versions are equal and wrong in my opinion -where is c=2 expression?
>>
>> v27 [1]
>> alena@postgres=# explain select * from t where a = 1 and (b = 1 or b = 2) and c = 2;
>> QUERY PLAN
>> ------------------------------------------------------------------------------
>> Bitmap Heap Scan on t (cost=165.85..474.87 rows=5001 width=12)
>> Recheck Cond: ((a = 1) AND (b = ANY ('{1,2}'::integer[])))
>> Filter: (c = 2)
>> -> Bitmap Index Scan on t_a_b_idx (cost=0.00..164.59 rows=10001 width=0)
>> Index Cond: ((a = 1) AND (b = ANY ('{1,2}'::integer[])))
>> (5 rows)
>> v26 [0]
>> alena@postgres=# explain select * from t where a = 1 and (b = 1 or b = 2) and c = 2;
>> QUERY PLAN
>> ------------------------------------------------------------------------------
>> Bitmap Heap Scan on t (cost=165.85..449.86 rows=5001 width=12)
>> Recheck Cond: ((a = 1) AND (b = ANY ('{1,2}'::integer[])))
>> Filter: (c = 2)
>> -> Bitmap Index Scan on t_a_b_idx (cost=0.00..164.59 rows=10001 width=0)
>> Index Cond: ((a = 1) AND (b = ANY ('{1,2}'::integer[])))
>> (5 rows)
> I think both v26 and v27 are correct here. The c = 2 condition is in
> the Filter.
Yes, I see it and agree with that.
>> In addition, I noticed that the ANY expression will be formed only for first group and ignore for others, like in the sample bellow:
>>
>> v26 version [0]:
>>
>> alena@postgres=# explain select * from t where (b = 1 or b = 2) and (a = 2 or a=3);
>> QUERY PLAN
>> -----------------------------------------------------------------------------------
>> Index Scan using t_a_b_idx on t (cost=0.29..24.75 rows=2 width=12)
>> Index Cond: ((a = ANY ('{2,3}'::integer[])) AND (b = ANY ('{1,2}'::integer[])))
>> (2 rows)
>>
>> v27 version [1]:
>>
>> alena@postgres=# explain select * from t where (b = 1 or b = 2 or a = 2 or a=3);
>> QUERY PLAN
>> --------------------------------------------------------
>> Seq Scan on t (cost=0.00..509.00 rows=14999 width=12)
>> Filter: ((b = 1) OR (b = 2) OR (a = 2) OR (a = 3))
>> (2 rows)
> Did you notice you're running different queries on v26 and v27 here?
> If you will run ton v27 the same query you run on v26, the plan also
> will be the same.
>
>> alena@postgres=# create index a_idx on t(a);
>> CREATE INDEX
>> alena@postgres=# create index b_idx on t(b);
>> CREATE INDEX
>> alena@postgres=# analyze;
>> ANALYZE
>>
>> v26:
>>
>> alena@postgres=# explain select * from t where (b = 1 or b = 2 or a = 2 or a=3);
>> QUERY PLAN
>> ------------------------------------------------------------------------------------
>> Bitmap Heap Scan on t (cost=17.18..30.94 rows=4 width=12)
>> Recheck Cond: ((a = ANY ('{2,3}'::integer[])) OR (a = ANY ('{2,3}'::integer[])))
>> -> BitmapOr (cost=17.18..17.18 rows=4 width=0)
>> -> Bitmap Index Scan on a_idx (cost=0.00..8.59 rows=2 width=0)
>> Index Cond: (a = ANY ('{2,3}'::integer[]))
>> -> Bitmap Index Scan on a_idx (cost=0.00..8.59 rows=2 width=0)
>> Index Cond: (a = ANY ('{2,3}'::integer[]))
>> (7 rows)
>>
>> v27:
>>
>> alena@postgres=# explain select * from t where (b = 1 or b = 2 or a = 2 or a=3);
>> QUERY PLAN
>> --------------------------------------------------------
>> Seq Scan on t (cost=0.00..509.00 rows=14999 width=12)
>> Filter: ((b = 1) OR (b = 2) OR (a = 2) OR (a = 3))
>> (2 rows)
>>
>> The behavior in version 26 is incorrect, but in version 27, it does not select anything other than seqscan
> Please, check that there is still possibility to the generate BitmapOr plan.
It is fine, I think. The transformation works, but due to the fact that
index columns are different for two indexes, the transformation hasn't
been applied.
>
> # explain select * from t where (b = 1 or b = 2 or a = 2 or a = 3);
> QUERY PLAN
> ------------------------------------------------------------------------------------
> Bitmap Heap Scan on t (cost=326.16..835.16 rows=14999 width=12)
> Recheck Cond: ((b = 1) OR (b = 2) OR (a = 2) OR (a = 3))
> -> BitmapOr (cost=326.16..326.16 rows=20000 width=0)
> -> Bitmap Index Scan on t_b_c_idx (cost=0.00..151.29
> rows=10000 width=0)
> Index Cond: (b = 1)
> -> Bitmap Index Scan on t_b_c_idx (cost=0.00..151.29
> rows=10000 width=0)
> Index Cond: (b = 2)
> -> Bitmap Index Scan on t_a_b_idx (cost=0.00..4.29 rows=1 width=0)
> Index Cond: (a = 2)
> -> Bitmap Index Scan on t_a_b_idx (cost=0.00..4.29 rows=1 width=0)
> Index Cond: (a = 3)
>
> It has higher cost than SeqScan plan, but I think it would be selected
> on larger tables. And yes, this is not ideal, because it fails to
> generate BitmapOr over two IndexScans on SAOPs. But it's not worse
> than what current master does. An optimization doesn't have to do
> everything it could possible do. So, I think this could be improved
> in a separate patch.
>
> Links
> 1.https://www.postgresql.org/message-id/CAPpHfdvhWE5pArZhgJeLViLx3-A3rxEREZvfkTj3E%3Dh7q-Bx9w%40mail.g...
> 2.https://www.postgresql.org/message-id/CAPpHfdtSXxhdv3mLOLjEewGeXJ%2BFtfhjqodn1WWuq5JLsKx48g%40mail.g...
Yes, I see and agree with you.
To be honest, I have found a big problem in this patch - we try to
perform the transformation every time we examime a column:
for (indexcol = 0; indexcol < index->nkeycolumns; indexcol++) { ...
}
I have fixed it and moved the transformation before going through the loop.
I try to make an array expression for "OR" expr, but at the same time I
form the result as an "AND" expression, consisting of an "Array"
expression and "OR" expressions, and then I check whether there is an
index for this column, if so, I save it and write down the
transformation. I also had to return the previous part of the patch,
where we formed "ANY" groups, since we could end up with several such
groups. I hope I made my idea clear, but if not, please tell me.
Unfortunately, I have got the different result one of the query from
regression tests and I'm not sure if it is correct:
diff -U3
/home/alena/postgrespro_or3/src/test/regress/expected/create_index.out
/home/alena/postgrespro_or3/src/test/regress/results/create_index.out
---
/home/alena/postgrespro_or3/src/test/regress/expected/create_index.out
2024-07-23 18:51:13.077311360 +0300 +++
/home/alena/postgrespro_or3/src/test/regress/results/create_index.out
2024-07-25 16:43:56.895132328 +0300 @@ -1860,13 +1860,14 @@ EXPLAIN
(COSTS OFF) SELECT * FROM tenk1 WHERE thousand = 42 AND (tenthous = 1 OR
tenthous = (SELECT 1 + 2) OR tenthous = 42); - QUERY PLAN
-----------------------------------------------------------------------------------------
+ QUERY PLAN
+---------------------------------------------------------------------------------
Index Scan using tenk1_thous_tenthous on tenk1 - Index Cond: ((thousand
= 42) AND (tenthous = ANY (ARRAY[1, (InitPlan 1).col1, 42]))) + Index
Cond: ((thousand = 42) AND (tenthous = ANY ('{1,-1,42}'::integer[]))) +
Filter: ((tenthous = 1) OR (tenthous = (InitPlan 1).col1) OR (tenthous =
42)) InitPlan 1 -> Result -(4 rows) +(5 rows) SELECT * FROM tenk1 WHERE
thousand = 42 AND (tenthous = 1 OR tenthous = (SELECT 1 + 2) OR tenthous
= 42);
I'm researching what's wrong here now.
--
Regards,
Alena Rybakina
Postgres Professional:http://www.postgrespro.com
The Russian Postgres Company
Attachments:
[text/x-patch] v28-Transform-OR-clauses-to-ANY-expression.patch (32.8K, ../../[email protected]/3-v28-Transform-OR-clauses-to-ANY-expression.patch)
download | inline diff:
From 31f58b8ad85e77534d38d099368168d9f775149f Mon Sep 17 00:00:00 2001
From: Alena Rybakina <[email protected]>
Date: Thu, 25 Jul 2024 17:03:05 +0300
Subject: [PATCH] Transform OR clauses to ANY expression
Replace (expr op C1) OR (expr op C2) ... with expr op ANY(ARRAY[C1, C2, ...])
during matching a clause to index.
Here Cn is a n-th constant or parameters expression, 'expr' is non-constant
expression, 'op' is an operator which returns boolean result and has a commuter
(for the case of reverse order of constant and non-constant parts of the
expression, like 'Cn op expr').
Discussion: https://postgr.es/m/567ED6CA.2040504%40sigaev.ru
Author: Alena Rybakina <[email protected]>
Author: Andrey Lepikhov <[email protected]>
Reviewed-by: Peter Geoghegan <[email protected]>
Reviewed-by: Ranier Vilela <[email protected]>
Reviewed-by: Alexander Korotkov <[email protected]>
Reviewed-by: Robert Haas <[email protected]>
Reviewed-by: Jian He <[email protected]>
Reviewed-by: Tom Lane <[email protected]>
Reviewed-by: Nikolay Shaplov <[email protected]>
---
src/backend/optimizer/path/indxpath.c | 396 +++++++++++++++++++++
src/include/nodes/pathnodes.h | 31 ++
src/test/regress/expected/create_index.out | 183 +++++++++-
src/test/regress/expected/join.out | 57 ++-
src/test/regress/sql/create_index.sql | 42 +++
src/test/regress/sql/join.sql | 9 +
src/tools/pgindent/typedefs.list | 1 +
7 files changed, 697 insertions(+), 22 deletions(-)
diff --git a/src/backend/optimizer/path/indxpath.c b/src/backend/optimizer/path/indxpath.c
index c0fcc7d78df..35bdf00dcb1 100644
--- a/src/backend/optimizer/path/indxpath.c
+++ b/src/backend/optimizer/path/indxpath.c
@@ -32,7 +32,9 @@
#include "optimizer/paths.h"
#include "optimizer/prep.h"
#include "optimizer/restrictinfo.h"
+#include "utils/array.h"
#include "utils/lsyscache.h"
+#include "utils/syscache.h"
#include "utils/selfuncs.h"
@@ -191,6 +193,10 @@ static Expr *match_clause_to_ordering_op(IndexOptInfo *index,
static bool ec_member_matches_indexcol(PlannerInfo *root, RelOptInfo *rel,
EquivalenceClass *ec, EquivalenceMember *em,
void *arg);
+static bool
+try_prepare_single_or(RestrictInfo *rinfo, List **appropriate_group);
+static List *
+transform_or_to_any(PlannerInfo *root, RestrictInfo * rinfo);
/*
@@ -2087,6 +2093,7 @@ match_clause_to_index(PlannerInfo *root,
IndexClauseSet *clauseset)
{
int indexcol;
+ List *candidates = NIL;
/*
* Never match pseudoconstants to indexes. (Normally a match could not
@@ -2104,6 +2111,9 @@ match_clause_to_index(PlannerInfo *root,
if (!restriction_is_securely_promotable(rinfo, index->rel))
return;
+ if (IsA(rinfo->clause, BoolExpr) && is_orclause(rinfo->clause))
+ candidates = transform_or_to_any(root, rinfo);
+
/* OK, check each index key column for a match */
for (indexcol = 0; indexcol < index->nkeycolumns; indexcol++)
{
@@ -2119,6 +2129,71 @@ match_clause_to_index(PlannerInfo *root,
return;
}
+ if (candidates != NIL)
+ {
+ ListCell *lc1;
+ Expr *item = NULL;
+ Node *nconst_expr = NULL;
+ Expr *expr = NULL;
+ List *result = NIL;
+ bool flag = false;
+
+ foreach(lc1, candidates)
+ {
+ item = lfirst(lc1);
+
+ if(item && IsA(item, BoolExpr))
+ {
+ if(is_andclause((Node*) item) && IsA(linitial(((BoolExpr *) item)->args), ScalarArrayOpExpr))
+ {
+
+ expr = linitial(((BoolExpr *) item)->args);
+
+ nconst_expr = get_leftop(expr);
+
+ if (match_index_to_operand(nconst_expr, indexcol, index))
+ {
+ result = lappend(result, (void *) expr);
+ flag = true;
+ continue;
+ }
+ else
+ {
+ expr = lsecond(((BoolExpr *) item)->args);
+ }
+ }
+ }
+
+ if(expr == NULL)
+ result = lappend(result, (void *)item);
+ else
+ result = lappend(result, expr);
+ }
+
+ if (flag)
+ {
+ rinfo = make_restrictinfo(root,
+ list_length(result) > 1 ?
+ makeBoolExpr(OR_EXPR, result,
+ ((BoolExpr *) rinfo->clause)->location) :
+ linitial(result),
+ rinfo->is_pushed_down,
+ rinfo->has_clone,
+ rinfo->is_clone,
+ rinfo->pseudoconstant,
+ rinfo->security_level,
+ rinfo->required_relids,
+ rinfo->incompatible_relids,
+ rinfo->outer_relids);
+ iclause = makeNode(IndexClause);
+ iclause->rinfo = rinfo;
+ iclause->indexquals = list_make1(iclause->rinfo);
+ iclause->lossy = false;
+ iclause->indexcol = indexcol;
+ iclause->indexcols = NIL;
+ }
+ }
+
/* OK, try to match the clause to the index column */
iclause = match_clause_to_indexcol(root,
rinfo,
@@ -2771,6 +2846,327 @@ match_rowcompare_to_indexcol(PlannerInfo *root,
return NULL;
}
+static bool
+try_prepare_single_or(RestrictInfo *rinfo, List **appropriate_group)
+{
+ OpExpr *orqual;
+ Node *const_expr;
+ Node *nconst_expr;
+ Oid opno;
+ Oid consttype;
+ Node *leftop,
+ *rightop;
+ ListCell *lc2;
+ bool found = false;
+ OrClauseGroup *or_clause_group;
+
+ if (!IsA(rinfo, RestrictInfo) || !IsA(rinfo->clause, OpExpr))
+ {
+ return false;
+ }
+
+ orqual = (OpExpr *) rinfo->clause;
+ opno = orqual->opno;
+ if (get_op_rettype(opno) != BOOLOID)
+ {
+ /* Only operator returning boolean suits OR -> ANY transformation */
+ return false;
+ }
+
+ /*
+ * Detect the constant side of the clause. Recall non-constant
+ * expression can be made not only with Vars, but also with Params,
+ * which is not bonded with any relation. Thus, we detect the const
+ * side - if another side is constant too, the orqual couldn't be an
+ * OpExpr. Get pointers to constant and expression sides of the qual.
+ */
+ leftop = get_leftop(orqual);
+ if (IsA(leftop, RelabelType))
+ leftop = (Node *) ((RelabelType *) leftop)->arg;
+
+ rightop = get_rightop(orqual);
+ if (IsA(rightop, RelabelType))
+ rightop = (Node *) ((RelabelType *) rightop)->arg;
+
+ if (IsA(leftop, Const) || IsA(leftop, Param))
+ {
+ opno = get_commutator(opno);
+
+ if (!OidIsValid(opno))
+ {/* commutator doesn't exist, we can't reverse the order */
+ return false;
+ }
+
+ nconst_expr = get_rightop(orqual);
+ const_expr = get_leftop(orqual);
+ }
+ else if (IsA(rightop, Const) || IsA(rightop, Param))
+ {
+ const_expr = get_rightop(orqual);
+ nconst_expr = get_leftop(orqual);
+ }
+ else
+ {
+ return false;
+ }
+
+ /*
+ * Forbid transformation for composite types, records, and volatile
+ * expressions.
+ */
+ consttype = exprType(const_expr);
+ if (type_is_rowtype(exprType(const_expr)) ||
+ type_is_rowtype(consttype) ||
+ contain_volatile_functions((Node *) nconst_expr))
+ {
+ return false;
+ }
+
+ or_clause_group = makeNode(OrClauseGroup);
+
+ foreach(lc2, *appropriate_group)
+ {
+
+ if (!IsA(lfirst(lc2), OrClauseGroup))
+ Assert(0);
+
+ or_clause_group = (OrClauseGroup *) lfirst(lc2);
+
+ if (or_clause_group->opno == opno &&
+ or_clause_group->consttype == consttype &&
+ or_clause_group->inputcollid == exprCollation(const_expr) &&
+ equal(or_clause_group->expr, nconst_expr))
+ {
+ found = true;
+ break;
+ }
+ }
+
+ if (!found)
+ {
+ or_clause_group->expr = (Expr *) nconst_expr;
+ or_clause_group->exprs = list_make1((void *) orqual);
+ or_clause_group->opno = opno;
+ or_clause_group->inputcollid = exprCollation(const_expr);
+ or_clause_group->consttype = consttype;
+ or_clause_group->consts = list_make1(const_expr);
+ or_clause_group->have_param = IsA(const_expr, Param);
+ Assert(list_length(or_clause_group->exprs) == list_length(or_clause_group->consts));
+ *appropriate_group = lappend(*appropriate_group, or_clause_group);
+ Assert(list_length(or_clause_group->exprs) == list_length(or_clause_group->consts));
+ }
+ else
+ {
+ or_clause_group->consts = lappend(or_clause_group->consts, const_expr);
+ or_clause_group->exprs = lappend(or_clause_group->exprs, (void *) orqual);
+ Assert(list_length(or_clause_group->exprs) == list_length(or_clause_group->consts));
+
+ Assert(list_length(or_clause_group->exprs) == list_length(or_clause_group->consts));
+ }
+
+ return true;
+}
+
+/*
+ * transform_or_to_any -
+ * Discover the args of an OR expression and try to group similar OR
+ * expressions to SAOP expressions.
+ *
+ * This transformation groups two-sided equality expression. One side of
+ * such an expression must be a plain constant or constant expression. The
+ * other side must be a variable expression without volatile functions.
+ * To group quals, opno, inputcollid of variable expression, and type of
+ * constant expression must be equal too.
+ *
+ * The grouping technique is based on the equivalence of variable sides of
+ * the expression: using exprId and equal() routine, it groups constant sides
+ * of similar clauses into an array. After the grouping procedure, each
+ * couple ('variable expression' and 'constant array') forms a new SAOP
+ * operation, which is added to the args list of the returning expression.
+ */
+static List *
+transform_or_to_any(PlannerInfo *root, RestrictInfo * rinfo)
+{
+ List *appropriate_entries = NIL;
+ List *or_entries = NIL;
+ int len_ors = ((BoolExpr *) rinfo->clause)->args ? list_length(((BoolExpr *) rinfo->clause)->args) : 0;
+ OrClauseGroup *restrict_info_entry = NULL;
+ ListCell *lc;
+ bool found;
+ List *result = NIL;
+
+ if(len_ors < 2)
+ return NIL;
+
+ foreach(lc, ((BoolExpr *) rinfo->orclause)->args)
+ {
+ RestrictInfo *sub_rinfo;
+ Expr *or_qual = (Expr *) lfirst(lc);
+
+ if(!IsA(lfirst(lc), RestrictInfo))
+ or_entries = lappend(or_entries, (void *) or_qual);
+ else
+ {
+ sub_rinfo = (RestrictInfo *) lfirst(lc);
+
+ /*
+ * Add the restrict_info_entry to the list. It is needed exclusively to manage
+ * the problem with the order of transformed clauses in explain.
+ * Hash value can depend on the platform and version. Hence,
+ * sequental scan of the hash table would prone to change the
+ * order of clauses in lists and, as a result, break regression
+ * tests accidentially.
+ */
+ found = try_prepare_single_or(sub_rinfo, &appropriate_entries);
+
+ if (!found)
+ {
+ or_entries = lappend(or_entries, (void *) sub_rinfo->clause);
+ }
+ }
+ }
+
+ if (list_length(or_entries) == len_ors || (appropriate_entries == NIL && list_length(appropriate_entries) < 1))
+ return NIL;
+
+ found = false;
+
+ /* Let's convert each group of clauses to an ANY expression. */
+
+ /*
+ * Go through the list of groups and convert each, where number of consts
+ * more than 1. trivial groups move to OR-list again
+ */
+
+ foreach(lc, appropriate_entries)
+ {
+ Oid scalar_type;
+ Oid array_type;
+ Node *newa = NULL;
+ HeapTuple opertup;
+ Form_pg_operator operform;
+ ScalarArrayOpExpr *saopexpr = NULL;
+ Expr *candidate = NULL;
+ Expr *main_ors = NULL;
+
+ if (!IsA(lfirst(lc), OrClauseGroup))
+ {
+ Assert(0);
+ }
+
+ restrict_info_entry = (OrClauseGroup *) lfirst(lc);
+
+ Assert(list_length(restrict_info_entry->exprs) == list_length(restrict_info_entry->consts));
+
+ if (list_length(restrict_info_entry->consts) == 1)
+ {
+ /*
+ * Only one element returns origin expression into the BoolExpr
+ * args list unchanged.
+ */
+ or_entries = list_concat(or_entries, (void *) restrict_info_entry->exprs);
+ continue;
+ }
+
+ scalar_type = restrict_info_entry->consttype;
+ array_type = OidIsValid(scalar_type) ? get_array_type(scalar_type) :
+ InvalidOid;
+
+ if (!OidIsValid(array_type))
+ {
+ or_entries = list_concat(or_entries, (void *) restrict_info_entry->exprs);
+ continue;
+ }
+
+ if (restrict_info_entry->have_param)
+ {
+ /*
+ * We need to construct an ArrayExpr given we have Param's not just
+ * Const's.
+ */
+ ArrayExpr *arexpr = makeNode(ArrayExpr);
+
+ /* array_collid will be set by parse_collate.c */
+ arexpr->element_typeid = scalar_type;
+ arexpr->array_typeid = array_type;
+ arexpr->multidims = false;
+ arexpr->elements = restrict_info_entry->consts;
+ arexpr->location = -1;
+
+ newa = (Node *) arexpr;
+ }
+ else
+ {
+ /* We have only Costs's. Can generate constant array. */
+
+ int16 typlen;
+ bool typbyval;
+ char typalign;
+ Datum *elems;
+ int i = 0;
+ ArrayType *ar;
+ ListCell *lc1;
+
+ get_typlenbyvalalign(scalar_type, &typlen, &typbyval, &typalign);
+
+ elems = (Datum *) palloc(sizeof(Datum) * list_length(restrict_info_entry->consts));
+ foreach(lc1, restrict_info_entry->consts)
+ {
+ Node *elem = (Node *) lfirst(lc1);
+
+ elems[i++] = ((Const *) elem)->constvalue;
+ }
+
+ ar = construct_array(elems, i, scalar_type, typlen, typbyval, typalign);
+ newa = (Node *) makeConst(array_type, -1, restrict_info_entry->inputcollid, -1, PointerGetDatum(ar), false, false);
+
+ pfree(elems);
+ }
+
+ opertup = SearchSysCache1(OPEROID,
+ ObjectIdGetDatum(restrict_info_entry->opno));
+ if (!HeapTupleIsValid(opertup))
+ elog(ERROR, "cache lookup failed for operator %u", restrict_info_entry->opno);
+
+ operform = (Form_pg_operator) GETSTRUCT(opertup);
+
+ /* and build the expression node */
+ saopexpr = makeNode(ScalarArrayOpExpr);
+ saopexpr->opno = restrict_info_entry->opno;
+ saopexpr->opfuncid = operform->oprcode;
+ saopexpr->hashfuncid = InvalidOid;
+ saopexpr->negfuncid = InvalidOid;
+ saopexpr->useOr = true;
+ saopexpr->inputcollid = restrict_info_entry->inputcollid;
+ /* inputcollid will be set by parse_collate.c */
+ saopexpr->args = list_make2(restrict_info_entry->expr, newa);
+ saopexpr->location = -1;
+
+ Assert(list_length(restrict_info_entry->exprs) > 1);
+
+ main_ors = makeBoolExpr(OR_EXPR, restrict_info_entry->exprs, -1);
+
+ candidate = makeBoolExpr(AND_EXPR, list_make2(saopexpr, main_ors), -1);
+ //list_free(restrict_info_entry->consts);
+ result = lappend(result, (void *) candidate);
+ ReleaseSysCache(opertup);
+ }
+ list_free(appropriate_entries);
+
+ /* One more trick: assemble correct clause */
+ if (result == NIL)
+ return NIL;
+ else
+ {
+ if (or_entries != NIL)
+ result = lappend(result, list_length(or_entries) > 1 ?
+ makeBoolExpr(OR_EXPR, or_entries,
+ ((BoolExpr *) rinfo->clause)->location) :
+ linitial(or_entries));
+ return result;
+ }
+}
+
/*
* expand_indexqual_rowcompare --- expand a single indexqual condition
* that is a RowCompareExpr
diff --git a/src/include/nodes/pathnodes.h b/src/include/nodes/pathnodes.h
index 14ccfc1ac1c..23da57b6d55 100644
--- a/src/include/nodes/pathnodes.h
+++ b/src/include/nodes/pathnodes.h
@@ -2708,6 +2708,37 @@ typedef struct RestrictInfo
Oid right_hasheqoperator pg_node_attr(equal_ignore);
} RestrictInfo;
+/*
+ * The group of similar operator expressions in transform_or_to_any().
+ */
+typedef struct OrClauseGroup
+{
+ pg_node_attr(nodetag_only)
+
+ NodeTag type;
+
+ /* The expression of the variable side of operator */
+Expr *expr;
+ /* The operator of the operator expression */
+ Oid opno;
+ /* The collation of the operator expression */
+ Oid inputcollid;
+ /* The type of constant side of operator */
+ Oid consttype;
+
+ /* The list of constant sides of operators */
+ List *consts;
+
+ /*
+ * List of source expressions. We need this for convenience in case we
+ * will give up on transformation.
+ */
+ List *exprs;
+
+ Node *const_expr;
+ bool have_param;
+} OrClauseGroup;
+
/*
* This macro embodies the correct way to test whether a RestrictInfo is
* "pushed down" to a given outer join, that is, should be treated as a filter
diff --git a/src/test/regress/expected/create_index.out b/src/test/regress/expected/create_index.out
index cf6eac57349..c2b25936c8c 100644
--- a/src/test/regress/expected/create_index.out
+++ b/src/test/regress/expected/create_index.out
@@ -1844,18 +1844,11 @@ DROP TABLE onek_with_null;
EXPLAIN (COSTS OFF)
SELECT * FROM tenk1
WHERE thousand = 42 AND (tenthous = 1 OR tenthous = 3 OR tenthous = 42);
- QUERY PLAN
------------------------------------------------------------------------------------------------------------------------------------------
- Bitmap Heap Scan on tenk1
- Recheck Cond: (((thousand = 42) AND (tenthous = 1)) OR ((thousand = 42) AND (tenthous = 3)) OR ((thousand = 42) AND (tenthous = 42)))
- -> BitmapOr
- -> Bitmap Index Scan on tenk1_thous_tenthous
- Index Cond: ((thousand = 42) AND (tenthous = 1))
- -> Bitmap Index Scan on tenk1_thous_tenthous
- Index Cond: ((thousand = 42) AND (tenthous = 3))
- -> Bitmap Index Scan on tenk1_thous_tenthous
- Index Cond: ((thousand = 42) AND (tenthous = 42))
-(9 rows)
+ QUERY PLAN
+------------------------------------------------------------------------------
+ Index Scan using tenk1_thous_tenthous on tenk1
+ Index Cond: ((thousand = 42) AND (tenthous = ANY ('{1,3,42}'::integer[])))
+(2 rows)
SELECT * FROM tenk1
WHERE thousand = 42 AND (tenthous = 1 OR tenthous = 3 OR tenthous = 42);
@@ -1864,14 +1857,166 @@ SELECT * FROM tenk1
42 | 5530 | 0 | 2 | 2 | 2 | 42 | 42 | 42 | 42 | 42 | 84 | 85 | QBAAAA | SEIAAA | OOOOxx
(1 row)
+EXPLAIN (COSTS OFF)
+SELECT * FROM tenk1
+ WHERE thousand = 42 AND (tenthous = 1 OR tenthous = (SELECT 1 + 2) OR tenthous = 42);
+ QUERY PLAN
+----------------------------------------------------------------------------------------
+ Index Scan using tenk1_thous_tenthous on tenk1
+ Index Cond: ((thousand = 42) AND (tenthous = ANY (ARRAY[1, (InitPlan 1).col1, 42])))
+ InitPlan 1
+ -> Result
+(4 rows)
+
+SELECT * FROM tenk1
+ WHERE thousand = 42 AND (tenthous = 1 OR tenthous = (SELECT 1 + 2) OR tenthous = 42);
+ unique1 | unique2 | two | four | ten | twenty | hundred | thousand | twothousand | fivethous | tenthous | odd | even | stringu1 | stringu2 | string4
+---------+---------+-----+------+-----+--------+---------+----------+-------------+-----------+----------+-----+------+----------+----------+---------
+ 42 | 5530 | 0 | 2 | 2 | 2 | 42 | 42 | 42 | 42 | 42 | 84 | 85 | QBAAAA | SEIAAA | OOOOxx
+(1 row)
+
EXPLAIN (COSTS OFF)
SELECT count(*) FROM tenk1
WHERE hundred = 42 AND (thousand = 42 OR thousand = 99);
- QUERY PLAN
----------------------------------------------------------------------------------
+ QUERY PLAN
+------------------------------------------------------------------------------------
Aggregate
-> Bitmap Heap Scan on tenk1
- Recheck Cond: ((hundred = 42) AND ((thousand = 42) OR (thousand = 99)))
+ Recheck Cond: ((hundred = 42) AND (thousand = ANY ('{42,99}'::integer[])))
+ -> BitmapAnd
+ -> Bitmap Index Scan on tenk1_hundred
+ Index Cond: (hundred = 42)
+ -> Bitmap Index Scan on tenk1_thous_tenthous
+ Index Cond: (thousand = ANY ('{42,99}'::integer[]))
+(8 rows)
+
+SELECT count(*) FROM tenk1
+ WHERE hundred = 42 AND (thousand = 42 OR thousand = 99);
+ count
+-------
+ 10
+(1 row)
+
+EXPLAIN (COSTS OFF)
+SELECT * FROM tenk1
+ WHERE thousand = 42 AND (tenthous = 1 OR tenthous = 3 OR tenthous = 42);
+ QUERY PLAN
+------------------------------------------------------------------------------
+ Index Scan using tenk1_thous_tenthous on tenk1
+ Index Cond: ((thousand = 42) AND (tenthous = ANY ('{1,3,42}'::integer[])))
+(2 rows)
+
+SELECT * FROM tenk1
+ WHERE thousand = 42 AND (tenthous = 1 OR tenthous = 3 OR tenthous = 42);
+ unique1 | unique2 | two | four | ten | twenty | hundred | thousand | twothousand | fivethous | tenthous | odd | even | stringu1 | stringu2 | string4
+---------+---------+-----+------+-----+--------+---------+----------+-------------+-----------+----------+-----+------+----------+----------+---------
+ 42 | 5530 | 0 | 2 | 2 | 2 | 42 | 42 | 42 | 42 | 42 | 84 | 85 | QBAAAA | SEIAAA | OOOOxx
+(1 row)
+
+EXPLAIN (COSTS OFF)
+SELECT count(*) FROM tenk1
+ WHERE hundred = 42 AND (thousand = 42 OR thousand = 99);
+ QUERY PLAN
+------------------------------------------------------------------------------------
+ Aggregate
+ -> Bitmap Heap Scan on tenk1
+ Recheck Cond: ((hundred = 42) AND (thousand = ANY ('{42,99}'::integer[])))
+ -> BitmapAnd
+ -> Bitmap Index Scan on tenk1_hundred
+ Index Cond: (hundred = 42)
+ -> Bitmap Index Scan on tenk1_thous_tenthous
+ Index Cond: (thousand = ANY ('{42,99}'::integer[]))
+(8 rows)
+
+SELECT count(*) FROM tenk1
+ WHERE hundred = 42 AND (thousand = 42 OR thousand = 99);
+ count
+-------
+ 10
+(1 row)
+
+EXPLAIN (COSTS OFF)
+SELECT count(*) FROM tenk1
+ WHERE hundred = 42 AND (thousand < 42 OR thousand < 99 OR 43 > thousand OR 42 > thousand);
+ QUERY PLAN
+------------------------------------------------------------------------------------------
+ Aggregate
+ -> Bitmap Heap Scan on tenk1
+ Recheck Cond: ((hundred = 42) AND (thousand < ANY ('{42,99,43,42}'::integer[])))
+ -> BitmapAnd
+ -> Bitmap Index Scan on tenk1_hundred
+ Index Cond: (hundred = 42)
+ -> Bitmap Index Scan on tenk1_thous_tenthous
+ Index Cond: (thousand < ANY ('{42,99,43,42}'::integer[]))
+(8 rows)
+
+SELECT count(*) FROM tenk1
+ WHERE hundred = 42 AND (thousand < 42 OR thousand < 99 OR 43 > thousand OR 42 > thousand);
+ count
+-------
+ 10
+(1 row)
+
+EXPLAIN (COSTS OFF)
+SELECT count(*) FROM tenk1
+ WHERE thousand = 42 AND (tenthous = 1 OR tenthous = 3) OR thousand = 41;
+ QUERY PLAN
+--------------------------------------------------------------------------------------------------------
+ Aggregate
+ -> Bitmap Heap Scan on tenk1
+ Recheck Cond: (((thousand = 42) AND (tenthous = ANY ('{1,3}'::integer[]))) OR (thousand = 41))
+ -> BitmapOr
+ -> Bitmap Index Scan on tenk1_thous_tenthous
+ Index Cond: ((thousand = 42) AND (tenthous = ANY ('{1,3}'::integer[])))
+ -> Bitmap Index Scan on tenk1_thous_tenthous
+ Index Cond: (thousand = 41)
+(8 rows)
+
+SELECT count(*) FROM tenk1
+ WHERE thousand = 42 AND (tenthous = 1 OR tenthous = 3) OR thousand = 41;
+ count
+-------
+ 10
+(1 row)
+
+EXPLAIN (COSTS OFF)
+SELECT count(*) FROM tenk1
+ WHERE hundred = 42 AND (thousand = 42 OR thousand = 99 OR tenthous < 2) OR thousand = 41;
+ QUERY PLAN
+------------------------------------------------------------------------------------------------------------------------
+ Aggregate
+ -> Bitmap Heap Scan on tenk1
+ Recheck Cond: (((hundred = 42) AND ((thousand = 42) OR (thousand = 99) OR (tenthous < 2))) OR (thousand = 41))
+ -> BitmapOr
+ -> BitmapAnd
+ -> Bitmap Index Scan on tenk1_hundred
+ Index Cond: (hundred = 42)
+ -> BitmapOr
+ -> Bitmap Index Scan on tenk1_thous_tenthous
+ Index Cond: (thousand = 42)
+ -> Bitmap Index Scan on tenk1_thous_tenthous
+ Index Cond: (thousand = 99)
+ -> Bitmap Index Scan on tenk1_thous_tenthous
+ Index Cond: (tenthous < 2)
+ -> Bitmap Index Scan on tenk1_thous_tenthous
+ Index Cond: (thousand = 41)
+(16 rows)
+
+SELECT count(*) FROM tenk1
+ WHERE hundred = 42 AND (thousand = 42 OR thousand = 99 OR tenthous < 2) OR thousand = 41;
+ count
+-------
+ 20
+(1 row)
+
+EXPLAIN (COSTS OFF)
+SELECT count(*) FROM tenk1
+ WHERE hundred = 42 AND (thousand = 42 OR thousand = 41 OR thousand = 99 AND tenthous = 2);
+ QUERY PLAN
+-------------------------------------------------------------------------------------------------------------------------
+ Aggregate
+ -> Bitmap Heap Scan on tenk1
+ Recheck Cond: ((hundred = 42) AND ((thousand = 42) OR (thousand = 41) OR ((thousand = 99) AND (tenthous = 2))))
-> BitmapAnd
-> Bitmap Index Scan on tenk1_hundred
Index Cond: (hundred = 42)
@@ -1879,11 +2024,13 @@ SELECT count(*) FROM tenk1
-> Bitmap Index Scan on tenk1_thous_tenthous
Index Cond: (thousand = 42)
-> Bitmap Index Scan on tenk1_thous_tenthous
- Index Cond: (thousand = 99)
-(11 rows)
+ Index Cond: (thousand = 41)
+ -> Bitmap Index Scan on tenk1_thous_tenthous
+ Index Cond: ((thousand = 99) AND (tenthous = 2))
+(13 rows)
SELECT count(*) FROM tenk1
- WHERE hundred = 42 AND (thousand = 42 OR thousand = 99);
+ WHERE hundred = 42 AND (thousand = 42 OR thousand = 41 OR thousand = 99 AND tenthous = 2);
count
-------
10
diff --git a/src/test/regress/expected/join.out b/src/test/regress/expected/join.out
index 53f70d72ed6..abe98ff3c53 100644
--- a/src/test/regress/expected/join.out
+++ b/src/test/regress/expected/join.out
@@ -4278,15 +4278,64 @@ select * from tenk1 a join tenk1 b on
Index Cond: (hundred = 4)
-> Materialize
-> Bitmap Heap Scan on tenk1 a
- Recheck Cond: ((unique1 = 1) OR (unique2 = 3) OR (unique2 = 7))
+ Recheck Cond: ((unique1 = 1) OR (unique2 = ANY ('{3,7}'::integer[])))
+ Filter: ((unique1 = 1) OR (unique2 = 3) OR (unique2 = 7))
-> BitmapOr
-> Bitmap Index Scan on tenk1_unique1
Index Cond: (unique1 = 1)
-> Bitmap Index Scan on tenk1_unique2
- Index Cond: (unique2 = 3)
+ Index Cond: (unique2 = ANY ('{3,7}'::integer[]))
+(18 rows)
+
+explain (costs off)
+select * from tenk1 a join tenk1 b on
+ (a.unique1 = 1 and b.unique1 = 2) or
+ ((a.unique2 = 3 or a.unique2 = 7) and b.hundred = 4);
+ QUERY PLAN
+----------------------------------------------------------------------------------------------------------------------
+ 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: ((unique1 = 2) OR (hundred = 4))
+ -> BitmapOr
+ -> 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: ((unique1 = 1) OR (unique2 = ANY ('{3,7}'::integer[])))
+ Filter: ((unique1 = 1) OR (unique2 = 3) OR (unique2 = 7))
+ -> BitmapOr
+ -> Bitmap Index Scan on tenk1_unique1
+ Index Cond: (unique1 = 1)
-> Bitmap Index Scan on tenk1_unique2
- Index Cond: (unique2 = 7)
-(19 rows)
+ Index Cond: (unique2 = ANY ('{3,7}'::integer[]))
+(18 rows)
+
+explain (costs off)
+select * from tenk1 a join tenk1 b on
+ (a.unique1 < 20 or a.unique1 = 3 or a.unique1 = 1 and b.unique1 = 2) or
+ ((a.unique2 = 3 or a.unique2 = 7) and b.hundred = 4);
+ QUERY PLAN
+-------------------------------------------------------------------------------------------------------------------------------------------------------------
+ Nested Loop
+ Join Filter: ((a.unique1 < 20) OR (a.unique1 = 3) OR ((a.unique1 = 1) AND (b.unique1 = 2)) OR (((a.unique2 = 3) OR (a.unique2 = 7)) AND (b.hundred = 4)))
+ -> Seq Scan on tenk1 b
+ -> Materialize
+ -> Bitmap Heap Scan on tenk1 a
+ Recheck Cond: ((unique1 < 20) OR (unique1 = 3) OR (unique1 = 1) OR (unique2 = ANY ('{3,7}'::integer[])))
+ Filter: ((unique1 < 20) OR (unique1 = 3) OR (unique1 = 1) OR (unique2 = 3) OR (unique2 = 7))
+ -> BitmapOr
+ -> Bitmap Index Scan on tenk1_unique1
+ Index Cond: (unique1 < 20)
+ -> Bitmap Index Scan on tenk1_unique1
+ Index Cond: (unique1 = 3)
+ -> Bitmap Index Scan on tenk1_unique1
+ Index Cond: (unique1 = 1)
+ -> Bitmap Index Scan on tenk1_unique2
+ Index Cond: (unique2 = ANY ('{3,7}'::integer[]))
+(16 rows)
--
-- test placement of movable quals in a parameterized join tree
diff --git a/src/test/regress/sql/create_index.sql b/src/test/regress/sql/create_index.sql
index e296891cab8..f74ad415fbf 100644
--- a/src/test/regress/sql/create_index.sql
+++ b/src/test/regress/sql/create_index.sql
@@ -726,6 +726,24 @@ DROP TABLE onek_with_null;
-- Check bitmap index path planning
--
+EXPLAIN (COSTS OFF)
+SELECT * FROM tenk1
+ WHERE thousand = 42 AND (tenthous = 1 OR tenthous = 3 OR tenthous = 42);
+SELECT * FROM tenk1
+ WHERE thousand = 42 AND (tenthous = 1 OR tenthous = 3 OR tenthous = 42);
+
+EXPLAIN (COSTS OFF)
+SELECT * FROM tenk1
+ WHERE thousand = 42 AND (tenthous = 1 OR tenthous = (SELECT 1 + 2) OR tenthous = 42);
+SELECT * FROM tenk1
+ WHERE thousand = 42 AND (tenthous = 1 OR tenthous = (SELECT 1 + 2) OR tenthous = 42);
+
+EXPLAIN (COSTS OFF)
+SELECT count(*) FROM tenk1
+ WHERE hundred = 42 AND (thousand = 42 OR thousand = 99);
+SELECT count(*) FROM tenk1
+ WHERE hundred = 42 AND (thousand = 42 OR thousand = 99);
+
EXPLAIN (COSTS OFF)
SELECT * FROM tenk1
WHERE thousand = 42 AND (tenthous = 1 OR tenthous = 3 OR tenthous = 42);
@@ -738,6 +756,30 @@ SELECT count(*) FROM tenk1
SELECT count(*) FROM tenk1
WHERE hundred = 42 AND (thousand = 42 OR thousand = 99);
+EXPLAIN (COSTS OFF)
+SELECT count(*) FROM tenk1
+ WHERE hundred = 42 AND (thousand < 42 OR thousand < 99 OR 43 > thousand OR 42 > thousand);
+SELECT count(*) FROM tenk1
+ WHERE hundred = 42 AND (thousand < 42 OR thousand < 99 OR 43 > thousand OR 42 > thousand);
+
+EXPLAIN (COSTS OFF)
+SELECT count(*) FROM tenk1
+ WHERE thousand = 42 AND (tenthous = 1 OR tenthous = 3) OR thousand = 41;
+SELECT count(*) FROM tenk1
+ WHERE thousand = 42 AND (tenthous = 1 OR tenthous = 3) OR thousand = 41;
+
+EXPLAIN (COSTS OFF)
+SELECT count(*) FROM tenk1
+ WHERE hundred = 42 AND (thousand = 42 OR thousand = 99 OR tenthous < 2) OR thousand = 41;
+SELECT count(*) FROM tenk1
+ WHERE hundred = 42 AND (thousand = 42 OR thousand = 99 OR tenthous < 2) OR thousand = 41;
+
+EXPLAIN (COSTS OFF)
+SELECT count(*) FROM tenk1
+ WHERE hundred = 42 AND (thousand = 42 OR thousand = 41 OR thousand = 99 AND tenthous = 2);
+SELECT count(*) FROM tenk1
+ WHERE hundred = 42 AND (thousand = 42 OR thousand = 41 OR thousand = 99 AND tenthous = 2);
+
--
-- Check behavior with duplicate index column contents
--
diff --git a/src/test/regress/sql/join.sql b/src/test/regress/sql/join.sql
index d81ff63be53..4473b8f04d5 100644
--- a/src/test/regress/sql/join.sql
+++ b/src/test/regress/sql/join.sql
@@ -1433,6 +1433,15 @@ select * from tenk1 a join tenk1 b on
(a.unique1 = 1 and b.unique1 = 2) or
((a.unique2 = 3 or a.unique2 = 7) and b.hundred = 4);
+explain (costs off)
+select * from tenk1 a join tenk1 b on
+ (a.unique1 = 1 and b.unique1 = 2) or
+ ((a.unique2 = 3 or a.unique2 = 7) and b.hundred = 4);
+explain (costs off)
+select * from tenk1 a join tenk1 b on
+ (a.unique1 < 20 or a.unique1 = 3 or a.unique1 = 1 and b.unique1 = 2) or
+ ((a.unique2 = 3 or a.unique2 = 7) and b.hundred = 4);
+
--
-- test placement of movable quals in a parameterized join tree
--
diff --git a/src/tools/pgindent/typedefs.list b/src/tools/pgindent/typedefs.list
index b4d7f9217ce..992c80f9350 100644
--- a/src/tools/pgindent/typedefs.list
+++ b/src/tools/pgindent/typedefs.list
@@ -1717,6 +1717,7 @@ NumericVar
OM_uint32
OP
OSAPerGroupState
+OrClauseGroup
OSAPerQueryState
OSInfo
OSSLCipher
--
2.34.1
^ permalink raw reply [nested|flat] 8+ messages in thread
* Re: POC, WIP: OR-clause support for indexes
2024-07-21 22:53 Re: POC, WIP: OR-clause support for indexes Alena Rybakina <[email protected]>
2024-07-22 00:52 ` Re: POC, WIP: OR-clause support for indexes Alexander Korotkov <[email protected]>
2024-07-25 14:04 ` Re: POC, WIP: OR-clause support for indexes Alena Rybakina <[email protected]>
@ 2024-07-27 10:56 ` Alexander Korotkov <[email protected]>
2024-07-28 09:59 ` Re: POC, WIP: OR-clause support for indexes Alena Rybakina <[email protected]>
0 siblings, 1 reply; 8+ messages in thread
From: Alexander Korotkov @ 2024-07-27 10:56 UTC (permalink / raw)
To: Alena Rybakina <[email protected]>; +Cc: Nikolay Shaplov <[email protected]>; [email protected]; Andrei Lepikhov <[email protected]>; jian he <[email protected]>; Robert Haas <[email protected]>; pgsql-hackers; Peter Geoghegan <[email protected]>; Finnerty, Jim <[email protected]>; Marcos Pegoraro <[email protected]>; [email protected]; Tomas Vondra <[email protected]>; Peter Eisentraut <[email protected]>; Ranier Vilela <[email protected]>
On Thu, Jul 25, 2024 at 5:04 PM Alena Rybakina
<[email protected]> wrote:
> To be honest, I have found a big problem in this patch - we try to perform the transformation every time we examime a column:
>
> for (indexcol = 0; indexcol < index->nkeycolumns; indexcol++) { ...
>
> }
>
> I have fixed it and moved the transformation before going through the loop.
What makes you think there is a problem? Do you have a test case
illustrating a slow planning time?
When v27 performs transformation for a particular column, it just
stops facing the first unmatched OR entry. So,
match_orclause_to_indexcol() examines just the first OR entry for all
the columns excepts at most one. So, the check
match_orclause_to_indexcol() does is not much slower than other
match_*_to_indexcol() do.
I actually think this could help performance in many cases, not hurt
it. At least we get rid of O(n^2) complexity over the number of OR
entries, which could be very many.
------
Regards,
Alexander Korotkov
Supabase
^ permalink raw reply [nested|flat] 8+ messages in thread
* Re: POC, WIP: OR-clause support for indexes
2024-07-21 22:53 Re: POC, WIP: OR-clause support for indexes Alena Rybakina <[email protected]>
2024-07-22 00:52 ` Re: POC, WIP: OR-clause support for indexes Alexander Korotkov <[email protected]>
2024-07-25 14:04 ` Re: POC, WIP: OR-clause support for indexes Alena Rybakina <[email protected]>
2024-07-27 10:56 ` Re: POC, WIP: OR-clause support for indexes Alexander Korotkov <[email protected]>
@ 2024-07-28 09:59 ` Alena Rybakina <[email protected]>
2024-07-29 02:36 ` Re: POC, WIP: OR-clause support for indexes Alexander Korotkov <[email protected]>
0 siblings, 1 reply; 8+ messages in thread
From: Alena Rybakina @ 2024-07-28 09:59 UTC (permalink / raw)
To: Alexander Korotkov <[email protected]>; +Cc: Nikolay Shaplov <[email protected]>; [email protected]; Andrei Lepikhov <[email protected]>; jian he <[email protected]>; Robert Haas <[email protected]>; pgsql-hackers; Peter Geoghegan <[email protected]>; Finnerty, Jim <[email protected]>; Marcos Pegoraro <[email protected]>; [email protected]; Tomas Vondra <[email protected]>; Peter Eisentraut <[email protected]>; Ranier Vilela <[email protected]>
On 27.07.2024 13:56, Alexander Korotkov wrote:
> On Thu, Jul 25, 2024 at 5:04 PM Alena Rybakina
> <[email protected]> wrote:
>> To be honest, I have found a big problem in this patch - we try to perform the transformation every time we examime a column:
>>
>> for (indexcol = 0; indexcol < index->nkeycolumns; indexcol++) { ...
>>
>> }
>>
>> I have fixed it and moved the transformation before going through the loop.
> What makes you think there is a problem?
To be honest, I was bothered by the fact that we need to go through
expressions several times that obviously will not fit under other
conditions.
Just yesterday I thought that it would be worthwhile to create a list of
candidates - expressions that did not fit because the column did not
match the index (!match_index_to_operand(nconst_expr, indexcol, index)).
Another problem that is related to the first one that the boolexpr could
contain expressions referring to different operands, for example, both x
and y. that is, we may have the problem that the optimal "ANY"
expression may not be used, because the expression with x may come
earlier and the loop may end earlier.
alena@postgres=# create table b (x int, y int);
CREATE TABLE
alena@postgres=# insert into b select id, id from
generate_series(1,1000) as id;
INSERT 0 1000
alena@postgres=# create index x_idx on b(x);
CREATE INDEX
alena@postgres=# analyze;
ANALYZE
alena@postgres=# explain select * from b where y =3 or x =4 or x=5 or
x=6 or x = 7 or x=8 or x=9;
QUERY PLAN
---------------------------------------------------------------------------------------
Seq Scan on b (cost=0.00..32.50 rows=7 width=8)
Filter: ((y = 3) OR (x = 4) OR (x = 5) OR (x = 6) OR (x = 7) OR (x =
8) OR (x = 9))
(2 rows)
alena@postgres=# explain select * from b where x =4 or x=5 or x=6 or x =
7 or x=8 or x=9 or y=1;
QUERY PLAN
---------------------------------------------------------------------------------------
Seq Scan on b (cost=0.00..32.50 rows=7 width=8)
Filter: ((x = 4) OR (x = 5) OR (x = 6) OR (x = 7) OR (x = 8) OR (x =
9) OR (y = 1))
(2 rows)
alena@postgres=# explain select * from b where x =4 or x=5 or x=6 or x =
7 or x=8 or x=9;
QUERY PLAN
----------------------------------------------------------------
Index Scan using x_idx on b (cost=0.28..12.75 rows=6 width=8)
Index Cond: (x = ANY ('{4,5,6,7,8,9}'::integer[]))
(2 rows)
Furthermore expressions can be stored in a different order.
For example, first comes "AND" expr, and then group of "OR" expr, which
we can convert to "ANY" expr, but we won't do this due to the fact that
we will exit the loop early, according to this condition:
if (!IsA(sub_rinfo->clause, OpExpr))
return NULL;
or it may occur due to other conditions.
alena@postgres=# create index x_y_idx on b(x,y);
CREATE INDEX
alena@postgres=# analyze;
ANALYZE
alena@postgres=# explain select * from b where (x = 2 and y =3) or x =4
or x=5 or x=6 or x = 7 or x=8 or x=9;
QUERY PLAN
-----------------------------------------------------------------------------------------------------
Seq Scan on b (cost=0.00..35.00 rows=6 width=8)
Filter: (((x = 2) AND (y = 3)) OR (x = 4) OR (x = 5) OR (x = 6) OR
(x = 7) OR (x = 8) OR (x = 9))
(2 rows)
Because of these reasons, I tried to save this and that transformation
together for each column and try to analyze for each expr separately
which method would be optimal.
> Do you have a test case
> illustrating a slow planning time?
No, I didn't have time to measure it and sorry for that. I'll do it.
> When v27 performs transformation for a particular column, it just
> stops facing the first unmatched OR entry. So,
> match_orclause_to_indexcol() examines just the first OR entry for all
> the columns excepts at most one. So, the check
> match_orclause_to_indexcol() does is not much slower than other
> match_*_to_indexcol() do.
>
> I actually think this could help performance in many cases, not hurt
> it. At least we get rid of O(n^2) complexity over the number of OR
> entries, which could be very many.
I agree with you that there is an overhead and your patch fixes this
problem, but optimizer needs to have a good ordering of expressions for
application.
I think we can try to move the transformation to another place where
there is already a loop pass, and also save two options "OR" expr and
"ANY" expr in one place (through BoolExpr) (like find_duplicate_ors
function) and teach the optimizer to determine which option is better,
for example, like now in match_orclause_to_indexcol() function.
What do you thing about it?
--
Regards,
Alena Rybakina
Postgres Professional:http://www.postgrespro.com
The Russian Postgres Company
^ permalink raw reply [nested|flat] 8+ messages in thread
* Re: POC, WIP: OR-clause support for indexes
2024-07-21 22:53 Re: POC, WIP: OR-clause support for indexes Alena Rybakina <[email protected]>
2024-07-22 00:52 ` Re: POC, WIP: OR-clause support for indexes Alexander Korotkov <[email protected]>
2024-07-25 14:04 ` Re: POC, WIP: OR-clause support for indexes Alena Rybakina <[email protected]>
2024-07-27 10:56 ` Re: POC, WIP: OR-clause support for indexes Alexander Korotkov <[email protected]>
2024-07-28 09:59 ` Re: POC, WIP: OR-clause support for indexes Alena Rybakina <[email protected]>
@ 2024-07-29 02:36 ` Alexander Korotkov <[email protected]>
0 siblings, 0 replies; 8+ messages in thread
From: Alexander Korotkov @ 2024-07-29 02:36 UTC (permalink / raw)
To: Alena Rybakina <[email protected]>; +Cc: Nikolay Shaplov <[email protected]>; [email protected]; Andrei Lepikhov <[email protected]>; jian he <[email protected]>; Robert Haas <[email protected]>; pgsql-hackers; Peter Geoghegan <[email protected]>; Finnerty, Jim <[email protected]>; Marcos Pegoraro <[email protected]>; [email protected]; Tomas Vondra <[email protected]>; Peter Eisentraut <[email protected]>; Ranier Vilela <[email protected]>
On Sun, Jul 28, 2024 at 12:59 PM Alena Rybakina
<[email protected]> wrote:
> On 27.07.2024 13:56, Alexander Korotkov wrote:
> > On Thu, Jul 25, 2024 at 5:04 PM Alena Rybakina
> > <[email protected]> wrote:
> >> To be honest, I have found a big problem in this patch - we try to perform the transformation every time we examime a column:
> >>
> >> for (indexcol = 0; indexcol < index->nkeycolumns; indexcol++) { ...
> >>
> >> }
> >>
> >> I have fixed it and moved the transformation before going through the loop.
> > What makes you think there is a problem?
>
> To be honest, I was bothered by the fact that we need to go through
> expressions several times that obviously will not fit under other
> conditions.
> Just yesterday I thought that it would be worthwhile to create a list of
> candidates - expressions that did not fit because the column did not
> match the index (!match_index_to_operand(nconst_expr, indexcol, index)).
I admit that this area probably could use some optimization,
especially for case of many clauses and many indexes. But in the
scope of this patch, I think this is enough to not make things worse
in this area.
> Another problem that is related to the first one that the boolexpr could
> contain expressions referring to different operands, for example, both x
> and y. that is, we may have the problem that the optimal "ANY"
> expression may not be used, because the expression with x may come
> earlier and the loop may end earlier.
>
> alena@postgres=# create table b (x int, y int);
> CREATE TABLE
> alena@postgres=# insert into b select id, id from
> generate_series(1,1000) as id;
> INSERT 0 1000
> alena@postgres=# create index x_idx on b(x);
> CREATE INDEX
> alena@postgres=# analyze;
> ANALYZE
> alena@postgres=# explain select * from b where y =3 or x =4 or x=5 or
> x=6 or x = 7 or x=8 or x=9;
> QUERY PLAN
> ---------------------------------------------------------------------------------------
> Seq Scan on b (cost=0.00..32.50 rows=7 width=8)
> Filter: ((y = 3) OR (x = 4) OR (x = 5) OR (x = 6) OR (x = 7) OR (x =
> 8) OR (x = 9))
> (2 rows)
> alena@postgres=# explain select * from b where x =4 or x=5 or x=6 or x =
> 7 or x=8 or x=9 or y=1;
> QUERY PLAN
> ---------------------------------------------------------------------------------------
> Seq Scan on b (cost=0.00..32.50 rows=7 width=8)
> Filter: ((x = 4) OR (x = 5) OR (x = 6) OR (x = 7) OR (x = 8) OR (x =
> 9) OR (y = 1))
> (2 rows)
> alena@postgres=# explain select * from b where x =4 or x=5 or x=6 or x =
> 7 or x=8 or x=9;
> QUERY PLAN
> ----------------------------------------------------------------
> Index Scan using x_idx on b (cost=0.28..12.75 rows=6 width=8)
> Index Cond: (x = ANY ('{4,5,6,7,8,9}'::integer[]))
> (2 rows)
>
> Furthermore expressions can be stored in a different order.
> For example, first comes "AND" expr, and then group of "OR" expr, which
> we can convert to "ANY" expr, but we won't do this due to the fact that
> we will exit the loop early, according to this condition:
>
> if (!IsA(sub_rinfo->clause, OpExpr))
> return NULL;
>
> or it may occur due to other conditions.
>
> alena@postgres=# create index x_y_idx on b(x,y);
> CREATE INDEX
> alena@postgres=# analyze;
> ANALYZE
>
> alena@postgres=# explain select * from b where (x = 2 and y =3) or x =4
> or x=5 or x=6 or x = 7 or x=8 or x=9;
> QUERY PLAN
> -----------------------------------------------------------------------------------------------------
> Seq Scan on b (cost=0.00..35.00 rows=6 width=8)
> Filter: (((x = 2) AND (y = 3)) OR (x = 4) OR (x = 5) OR (x = 6) OR
> (x = 7) OR (x = 8) OR (x = 9))
> (2 rows)
>
> Because of these reasons, I tried to save this and that transformation
> together for each column and try to analyze for each expr separately
> which method would be optimal.
Yes, with v27 of the patch, optimization wouldn't work in these cases.
However, you are using quite small table. If you will use larger
table or disable sequential scans, there would be bitmap plans to
handle these queries. So, v27 doesn't make the situation worse. It
just doesn't optimize all that it could potentially optimize and
that's OK.
I've written a separate 0002 patch to address this. Now, before
generation of paths for bitmap OR, similar OR entries are grouped
together. When considering a group of similar entries, they are
considered both together and one-by-one. Ideally we could consider
more sophisticated grouping, but that seems fine for now. You can
check how this patch handles the cases of above.
Also, 0002 address issue of duplicated bitmap scan conditions in
different forms. During generate_bitmap_or_paths() we need to exclude
considered condition for other clauses. It couldn't be as normal
filtered out in the latter stage, because could reach the index in
another form.
> > Do you have a test case
> > illustrating a slow planning time?
> No, I didn't have time to measure it and sorry for that. I'll do it.
> > When v27 performs transformation for a particular column, it just
> > stops facing the first unmatched OR entry. So,
> > match_orclause_to_indexcol() examines just the first OR entry for all
> > the columns excepts at most one. So, the check
> > match_orclause_to_indexcol() does is not much slower than other
> > match_*_to_indexcol() do.
> >
> > I actually think this could help performance in many cases, not hurt
> > it. At least we get rid of O(n^2) complexity over the number of OR
> > entries, which could be very many.
>
> I agree with you that there is an overhead and your patch fixes this
> problem, but optimizer needs to have a good ordering of expressions for
> application.
>
> I think we can try to move the transformation to another place where
> there is already a loop pass, and also save two options "OR" expr and
> "ANY" expr in one place (through BoolExpr) (like find_duplicate_ors
> function) and teach the optimizer to determine which option is better,
> for example, like now in match_orclause_to_indexcol() function.
>
> What do you thing about it?
find_duplicate_ors() and similar places were already tried before.
Please, check upthread. This approach receives severe critics. AFAIU,
the problem is that find_duplicate_ors() during preprocessing, a
cost-blind stage.
This is why I'd like to continue developing ideas of v27, because it
fits the existing framework.
------
Regards,
Alexander Korotkov
Supabase
Attachments:
[application/octet-stream] v29-0002-Teach-bitmap-scan-about-transforming-OR-clauses-.patch (18.9K, ../../CAPpHfdu5iQOjF93vGbjidsQkhHvY2NSm29duENYH_cbhC6x+Mg@mail.gmail.com/2-v29-0002-Teach-bitmap-scan-about-transforming-OR-clauses-.patch)
download | inline diff:
From a56cb787bb302d8bc1a2f53bf1e82bc1cb37fb01 Mon Sep 17 00:00:00 2001
From: Alexander Korotkov <[email protected]>
Date: Sun, 28 Jul 2024 16:36:34 +0300
Subject: [PATCH v29 2/2] Teach bitmap scan about transforming OR clauses to
ANY expression
Now, (expr op C1) OR (expr op C2) ... are transformet to
expr op ANY(ARRAY[C1, C2, ...]) during matching a clause to index.
This commit teaches bitmap scan planning to take advantage of this
transformation.
The similar clauses are grouped together before considering bitmap-OR.
Groups of similar clauses are matched to indexes both together and one-by-one.
---
src/backend/optimizer/path/indxpath.c | 266 ++++++++++++++++++++-
src/test/regress/expected/create_index.out | 28 +--
src/test/regress/expected/join.out | 56 +++--
src/tools/pgindent/typedefs.list | 1 +
4 files changed, 304 insertions(+), 47 deletions(-)
diff --git a/src/backend/optimizer/path/indxpath.c b/src/backend/optimizer/path/indxpath.c
index 4fd0bbce2ce..f697b95db39 100644
--- a/src/backend/optimizer/path/indxpath.c
+++ b/src/backend/optimizer/path/indxpath.c
@@ -1177,6 +1177,248 @@ build_paths_for_OR(PlannerInfo *root, RelOptInfo *rel,
return result;
}
+typedef struct
+{
+ int indexnum;
+ int colnum;
+ Oid opno;
+ int argindex;
+} OrArgIndexMatch;
+
+static int
+or_arg_index_match_cmp(const void *a, const void *b)
+{
+ const OrArgIndexMatch *match_a = (const OrArgIndexMatch *) a;
+ const OrArgIndexMatch *match_b = (const OrArgIndexMatch *) b;
+
+ if (match_a->indexnum < match_b->indexnum)
+ return -1;
+ else if (match_a->indexnum > match_b->indexnum)
+ return 1;
+
+ if (match_a->colnum < match_b->colnum)
+ return -1;
+ else if (match_a->colnum > match_b->colnum)
+ return 1;
+
+ if (match_a->opno < match_b->opno)
+ return -1;
+ else if (match_a->opno > match_b->opno)
+ return 1;
+
+ if (match_a->argindex < match_b->argindex)
+ return -1;
+ else if (match_a->argindex > match_b->argindex)
+ return 1;
+
+ return 0;
+}
+
+/*
+ * Group clauses "col op const" belonging to the single index clause into
+ * dedicated ORs.
+ */
+static List *
+group_or_args(PlannerInfo *root, RelOptInfo *rel,
+ RestrictInfo *rinfo, List *orargs)
+{
+ int n = list_length(orargs);
+ int i;
+ int group_start;
+ OrArgIndexMatch *matches;
+ ListCell *lc;
+ ListCell *lc2;
+ List *result = NIL;
+
+ /*
+ * Find corresponding index column for each clause in target form.
+ */
+ i = -1;
+ matches = (OrArgIndexMatch *) palloc(sizeof(OrArgIndexMatch) * n);
+ foreach(lc, orargs)
+ {
+ Node *arg = lfirst(lc);
+ RestrictInfo *argrinfo;
+ OpExpr *clause;
+ Oid opno;
+ Node *leftop,
+ *rightop;
+ Node *nconst_expr;
+ int indexnum;
+ int colnum;
+
+ i++;
+ matches[i].argindex = i;
+ matches[i].indexnum = -1;
+ matches[i].colnum = -1;
+ matches[i].opno = InvalidOid;
+
+ if (!IsA(arg, RestrictInfo))
+ continue;
+
+ argrinfo = castNode(RestrictInfo, arg);
+
+ if (!IsA(argrinfo->clause, OpExpr))
+ continue;
+
+ clause = (OpExpr *) argrinfo->clause;
+ opno = clause->opno;
+
+ leftop = get_leftop(clause);
+ if (IsA(leftop, RelabelType))
+ leftop = (Node *) ((RelabelType *) leftop)->arg;
+
+ rightop = get_rightop(clause);
+ if (IsA(rightop, RelabelType))
+ rightop = (Node *) ((RelabelType *) rightop)->arg;
+
+ if (IsA(leftop, Const) || IsA(leftop, Param))
+ {
+ opno = get_commutator(opno);
+
+ if (!OidIsValid(opno))
+ {
+ /* commutator doesn't exist, we can't reverse the order */
+ continue;
+ }
+
+ nconst_expr = rightop;
+ }
+ else if (IsA(rightop, Const) || IsA(rightop, Param))
+ {
+ nconst_expr = leftop;
+ }
+ else
+ {
+ continue;
+ }
+
+ indexnum = 0;
+ foreach(lc2, rel->indexlist)
+ {
+ IndexOptInfo *index = (IndexOptInfo *) lfirst(lc2);
+
+ /* Ignore index if it doesn't support bitmap scans */
+ if (!index->amhasgetbitmap)
+ continue;
+
+ for (colnum = 0; colnum < index->nkeycolumns; colnum++)
+ {
+ if (match_index_to_operand(nconst_expr, colnum, index))
+ {
+ matches[i].indexnum = indexnum;
+ matches[i].colnum = colnum;
+ matches[i].opno = opno;
+ }
+ }
+ indexnum++;
+ }
+ }
+
+ /* Sort clauses to make similar clauses go together */
+ pg_qsort(matches, n, sizeof(OrArgIndexMatch), or_arg_index_match_cmp);
+
+ /* Group similar clauses */
+ group_start = 0;
+ for (i = 1; i <= n; i++)
+ {
+ if (group_start >= 0 &&
+ (i == n ||
+ matches[i].indexnum != matches[group_start].indexnum ||
+ matches[i].colnum != matches[group_start].colnum ||
+ matches[i].opno != matches[group_start].opno ||
+ matches[i].indexnum == -1))
+ {
+ if (i - group_start == 1)
+ {
+ result = lappend(result, list_nth(orargs, matches[group_start].argindex));
+ }
+ else
+ {
+ List *args = NIL;
+ RestrictInfo *subrinfo = makeNode(RestrictInfo);
+ int j;
+
+ for (j = group_start; j < i; j++)
+ args = lappend(args, list_nth(orargs, matches[j].argindex));
+
+ *subrinfo = *rinfo;
+ subrinfo->clause = make_orclause(args);
+ subrinfo->orclause = subrinfo->clause;
+ result = lappend(result, subrinfo);
+ }
+
+ group_start = i;
+ }
+ }
+ return result;
+}
+
+/*
+ * Generate bitmap paths for group produced by group_or_args()
+ */
+static List *
+make_bitmap_paths_for_or_group(PlannerInfo *root, RelOptInfo *rel,
+ RestrictInfo *ri, List *other_clauses)
+{
+ List *jointlist = NIL;
+ List *splitlist = NIL;
+ ListCell *lc;
+ List *orargs;
+ List *args = ((BoolExpr *) ri->clause)->args;
+ Cost jointcost = 0.0,
+ splitcost = 0.0;
+ Path *bitmapqual;
+ List *indlist;
+
+ /*
+ * First, try to match the whole group to the one index.
+ */
+ orargs = list_make1(ri);
+ indlist = build_paths_for_OR(root, rel,
+ orargs,
+ other_clauses);
+ if (indlist != NIL)
+ {
+ bitmapqual = choose_bitmap_and(root, rel, indlist);
+ jointcost = bitmapqual->total_cost;
+ jointlist = list_make1(bitmapqual);
+ }
+
+ /*
+ * Also try to match all containing clauses one-by-one.
+ */
+ foreach(lc, args)
+ {
+ orargs = list_make1(lfirst(lc));
+
+ indlist = build_paths_for_OR(root, rel,
+ orargs,
+ other_clauses);
+
+ if (indlist == NIL)
+ {
+ splitlist = NIL;
+ break;
+ }
+
+ bitmapqual = choose_bitmap_and(root, rel, indlist);
+ splitcost += bitmapqual->total_cost;
+ splitlist = lappend(splitlist, bitmapqual);
+ }
+
+ /*
+ * Pick the best option.
+ */
+ if (splitlist == NIL)
+ return jointlist;
+ else if (jointlist == NIL)
+ return splitlist;
+ else
+ return (jointcost < splitcost) ? jointlist : splitlist;
+}
+
+
/*
* generate_bitmap_or_paths
* Look through the list of clauses to find OR clauses, and generate
@@ -1207,6 +1449,7 @@ generate_bitmap_or_paths(PlannerInfo *root, RelOptInfo *rel,
List *pathlist;
Path *bitmapqual;
ListCell *j;
+ List *grouped;
/* Ignore RestrictInfos that aren't ORs */
if (!restriction_is_or_clause(rinfo))
@@ -1217,7 +1460,8 @@ generate_bitmap_or_paths(PlannerInfo *root, RelOptInfo *rel,
* the OR, else we can't use it.
*/
pathlist = NIL;
- foreach(j, ((BoolExpr *) rinfo->orclause)->args)
+ grouped = group_or_args(root, rel, rinfo, ((BoolExpr *) rinfo->orclause)->args);
+ foreach(j, grouped)
{
Node *orarg = (Node *) lfirst(j);
List *indlist;
@@ -1237,12 +1481,28 @@ generate_bitmap_or_paths(PlannerInfo *root, RelOptInfo *rel,
andargs,
all_clauses));
}
+ else if (restriction_is_or_clause(castNode(RestrictInfo, orarg)))
+ {
+ RestrictInfo *ri = castNode(RestrictInfo, orarg);
+
+ indlist = make_bitmap_paths_for_or_group(root, rel, ri, list_delete(all_clauses, rinfo));
+
+ if (indlist == NIL)
+ {
+ pathlist = NIL;
+ break;
+ }
+ else
+ {
+ pathlist = list_concat(pathlist, indlist);
+ continue;
+ }
+ }
else
{
RestrictInfo *ri = castNode(RestrictInfo, orarg);
List *orargs;
- Assert(!restriction_is_or_clause(ri));
orargs = list_make1(ri);
indlist = build_paths_for_OR(root, rel,
@@ -2878,7 +3138,7 @@ match_orclause_to_indexcol(PlannerInfo *root,
if (!OidIsValid(opno))
{
/* commutator doesn't exist, we can't reverse the order */
- return false;
+ return NULL;
}
nconst_expr = rightop;
diff --git a/src/test/regress/expected/create_index.out b/src/test/regress/expected/create_index.out
index c2b25936c8c..c6feef03810 100644
--- a/src/test/regress/expected/create_index.out
+++ b/src/test/regress/expected/create_index.out
@@ -1982,25 +1982,24 @@ SELECT count(*) FROM tenk1
EXPLAIN (COSTS OFF)
SELECT count(*) FROM tenk1
WHERE hundred = 42 AND (thousand = 42 OR thousand = 99 OR tenthous < 2) OR thousand = 41;
- QUERY PLAN
-------------------------------------------------------------------------------------------------------------------------
+ QUERY PLAN
+-----------------------------------------------------------------------------------------------------------------------------
Aggregate
-> Bitmap Heap Scan on tenk1
- Recheck Cond: (((hundred = 42) AND ((thousand = 42) OR (thousand = 99) OR (tenthous < 2))) OR (thousand = 41))
+ Recheck Cond: (((hundred = 42) AND ((thousand = ANY ('{42,99}'::integer[])) OR (tenthous < 2))) OR (thousand = 41))
+ Filter: (((hundred = 42) AND ((thousand = 42) OR (thousand = 99) OR (tenthous < 2))) OR (thousand = 41))
-> BitmapOr
-> BitmapAnd
-> Bitmap Index Scan on tenk1_hundred
Index Cond: (hundred = 42)
-> BitmapOr
-> Bitmap Index Scan on tenk1_thous_tenthous
- Index Cond: (thousand = 42)
- -> Bitmap Index Scan on tenk1_thous_tenthous
- Index Cond: (thousand = 99)
+ Index Cond: (thousand = ANY ('{42,99}'::integer[]))
-> Bitmap Index Scan on tenk1_thous_tenthous
Index Cond: (tenthous < 2)
-> Bitmap Index Scan on tenk1_thous_tenthous
Index Cond: (thousand = 41)
-(16 rows)
+(15 rows)
SELECT count(*) FROM tenk1
WHERE hundred = 42 AND (thousand = 42 OR thousand = 99 OR tenthous < 2) OR thousand = 41;
@@ -2012,22 +2011,21 @@ SELECT count(*) FROM tenk1
EXPLAIN (COSTS OFF)
SELECT count(*) FROM tenk1
WHERE hundred = 42 AND (thousand = 42 OR thousand = 41 OR thousand = 99 AND tenthous = 2);
- QUERY PLAN
--------------------------------------------------------------------------------------------------------------------------
+ QUERY PLAN
+------------------------------------------------------------------------------------------------------------------------------
Aggregate
-> Bitmap Heap Scan on tenk1
- Recheck Cond: ((hundred = 42) AND ((thousand = 42) OR (thousand = 41) OR ((thousand = 99) AND (tenthous = 2))))
+ Recheck Cond: ((hundred = 42) AND (((thousand = 99) AND (tenthous = 2)) OR (thousand = ANY ('{42,41}'::integer[]))))
+ 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 = 42)
- -> Bitmap Index Scan on tenk1_thous_tenthous
- Index Cond: (thousand = 41)
-> Bitmap Index Scan on tenk1_thous_tenthous
Index Cond: ((thousand = 99) AND (tenthous = 2))
-(13 rows)
+ -> Bitmap Index Scan on tenk1_thous_tenthous
+ Index Cond: (thousand = ANY ('{42,41}'::integer[]))
+(12 rows)
SELECT count(*) FROM tenk1
WHERE hundred = 42 AND (thousand = 42 OR thousand = 41 OR thousand = 99 AND tenthous = 2);
diff --git a/src/test/regress/expected/join.out b/src/test/regress/expected/join.out
index abe98ff3c53..d26a93831d5 100644
--- a/src/test/regress/expected/join.out
+++ b/src/test/regress/expected/join.out
@@ -4226,20 +4226,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: ((unique1 = 2) OR (hundred = 4))
+ Recheck Cond: ((hundred = 4) OR (unique1 = 2))
-> BitmapOr
- -> Bitmap Index Scan on tenk1_unique1
- Index Cond: (unique1 = 2)
-> Bitmap Index Scan on tenk1_hundred
Index Cond: (hundred = 4)
+ -> Bitmap Index Scan on tenk1_unique1
+ Index Cond: (unique1 = 2)
-> Materialize
-> Bitmap Heap Scan on tenk1 a
- Recheck Cond: ((unique1 = 1) OR (unique2 = 3))
+ Recheck Cond: ((unique2 = 3) OR (unique1 = 1))
-> BitmapOr
- -> Bitmap Index Scan on tenk1_unique1
- Index Cond: (unique1 = 1)
-> Bitmap Index Scan on tenk1_unique2
Index Cond: (unique2 = 3)
+ -> Bitmap Index Scan on tenk1_unique1
+ Index Cond: (unique1 = 1)
(17 rows)
explain (costs off)
@@ -4253,12 +4253,12 @@ select * from tenk1 a join tenk1 b on
Filter: ((unique1 = 2) OR (ten = 4))
-> Materialize
-> Bitmap Heap Scan on tenk1 a
- Recheck Cond: ((unique1 = 1) OR (unique2 = 3))
+ Recheck Cond: ((unique2 = 3) OR (unique1 = 1))
-> BitmapOr
- -> Bitmap Index Scan on tenk1_unique1
- Index Cond: (unique1 = 1)
-> Bitmap Index Scan on tenk1_unique2
Index Cond: (unique2 = 3)
+ -> Bitmap Index Scan on tenk1_unique1
+ Index Cond: (unique1 = 1)
(12 rows)
explain (costs off)
@@ -4270,21 +4270,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: ((unique1 = 2) OR (hundred = 4))
+ Recheck Cond: ((hundred = 4) OR (unique1 = 2))
-> BitmapOr
- -> Bitmap Index Scan on tenk1_unique1
- Index Cond: (unique1 = 2)
-> Bitmap Index Scan on tenk1_hundred
Index Cond: (hundred = 4)
+ -> Bitmap Index Scan on tenk1_unique1
+ Index Cond: (unique1 = 2)
-> Materialize
-> Bitmap Heap Scan on tenk1 a
- Recheck Cond: ((unique1 = 1) OR (unique2 = ANY ('{3,7}'::integer[])))
+ Recheck Cond: ((unique2 = ANY ('{3,7}'::integer[])) OR (unique1 = 1))
Filter: ((unique1 = 1) OR (unique2 = 3) OR (unique2 = 7))
-> BitmapOr
- -> Bitmap Index Scan on tenk1_unique1
- Index Cond: (unique1 = 1)
-> Bitmap Index Scan on tenk1_unique2
Index Cond: (unique2 = ANY ('{3,7}'::integer[]))
+ -> Bitmap Index Scan on tenk1_unique1
+ Index Cond: (unique1 = 1)
(18 rows)
explain (costs off)
@@ -4296,21 +4296,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: ((unique1 = 2) OR (hundred = 4))
+ Recheck Cond: ((hundred = 4) OR (unique1 = 2))
-> BitmapOr
- -> Bitmap Index Scan on tenk1_unique1
- Index Cond: (unique1 = 2)
-> Bitmap Index Scan on tenk1_hundred
Index Cond: (hundred = 4)
+ -> Bitmap Index Scan on tenk1_unique1
+ Index Cond: (unique1 = 2)
-> Materialize
-> Bitmap Heap Scan on tenk1 a
- Recheck Cond: ((unique1 = 1) OR (unique2 = ANY ('{3,7}'::integer[])))
+ Recheck Cond: ((unique2 = ANY ('{3,7}'::integer[])) OR (unique1 = 1))
Filter: ((unique1 = 1) OR (unique2 = 3) OR (unique2 = 7))
-> BitmapOr
- -> Bitmap Index Scan on tenk1_unique1
- Index Cond: (unique1 = 1)
-> Bitmap Index Scan on tenk1_unique2
Index Cond: (unique2 = ANY ('{3,7}'::integer[]))
+ -> Bitmap Index Scan on tenk1_unique1
+ Index Cond: (unique1 = 1)
(18 rows)
explain (costs off)
@@ -4324,18 +4324,16 @@ select * from tenk1 a join tenk1 b on
-> Seq Scan on tenk1 b
-> Materialize
-> Bitmap Heap Scan on tenk1 a
- Recheck Cond: ((unique1 < 20) OR (unique1 = 3) OR (unique1 = 1) OR (unique2 = ANY ('{3,7}'::integer[])))
+ Recheck Cond: ((unique2 = ANY ('{3,7}'::integer[])) OR (unique1 = ANY ('{3,1}'::integer[])) OR (unique1 < 20))
Filter: ((unique1 < 20) OR (unique1 = 3) OR (unique1 = 1) OR (unique2 = 3) OR (unique2 = 7))
-> BitmapOr
- -> Bitmap Index Scan on tenk1_unique1
- Index Cond: (unique1 < 20)
- -> Bitmap Index Scan on tenk1_unique1
- Index Cond: (unique1 = 3)
- -> Bitmap Index Scan on tenk1_unique1
- Index Cond: (unique1 = 1)
-> Bitmap Index Scan on tenk1_unique2
Index Cond: (unique2 = ANY ('{3,7}'::integer[]))
-(16 rows)
+ -> Bitmap Index Scan on tenk1_unique1
+ Index Cond: (unique1 = ANY ('{3,1}'::integer[]))
+ -> Bitmap Index Scan on tenk1_unique1
+ Index Cond: (unique1 < 20)
+(14 rows)
--
-- test placement of movable quals in a parameterized join tree
diff --git a/src/tools/pgindent/typedefs.list b/src/tools/pgindent/typedefs.list
index 992c80f9350..ba66983cf45 100644
--- a/src/tools/pgindent/typedefs.list
+++ b/src/tools/pgindent/typedefs.list
@@ -1764,6 +1764,7 @@ OprCacheKey
OprInfo
OprProofCacheEntry
OprProofCacheKey
+OrArgIndexMatch
OuterJoinClauseInfo
OutputPluginCallbacks
OutputPluginOptions
--
2.39.3 (Apple Git-145)
[application/octet-stream] v29-0001-Transform-OR-clauses-to-ANY-expression.patch (26.8K, ../../CAPpHfdu5iQOjF93vGbjidsQkhHvY2NSm29duENYH_cbhC6x+Mg@mail.gmail.com/3-v29-0001-Transform-OR-clauses-to-ANY-expression.patch)
download | inline diff:
From f540ee7b4fc600c2aedb02b139adcf8824c0f7f1 Mon Sep 17 00:00:00 2001
From: Alena Rybakina <[email protected]>
Date: Thu, 11 Jul 2024 19:01:10 +0300
Subject: [PATCH v29 1/2] Transform OR clauses to ANY expression
Replace (expr op C1) OR (expr op C2) ... with expr op ANY(ARRAY[C1, C2, ...])
during matching a clause to index.
Here Cn is a n-th constant or parameters expression, 'expr' is non-constant
expression, 'op' is an operator which returns boolean result and has a commuter
(for the case of reverse order of constant and non-constant parts of the
expression, like 'Cn op expr').
Discussion: https://postgr.es/m/567ED6CA.2040504%40sigaev.ru
Author: Alena Rybakina <[email protected]>
Author: Andrey Lepikhov <[email protected]>
Reviewed-by: Peter Geoghegan <[email protected]>
Reviewed-by: Ranier Vilela <[email protected]>
Reviewed-by: Alexander Korotkov <[email protected]>
Reviewed-by: Robert Haas <[email protected]>
Reviewed-by: Jian He <[email protected]>
Reviewed-by: Tom Lane <[email protected]>
Reviewed-by: Nikolay Shaplov <[email protected]>
---
src/backend/optimizer/path/indxpath.c | 241 +++++++++++++++++++++
src/test/regress/expected/create_index.out | 183 ++++++++++++++--
src/test/regress/expected/join.out | 57 ++++-
src/test/regress/sql/create_index.sql | 42 ++++
src/test/regress/sql/join.sql | 9 +
src/tools/pgindent/typedefs.list | 1 +
6 files changed, 511 insertions(+), 22 deletions(-)
diff --git a/src/backend/optimizer/path/indxpath.c b/src/backend/optimizer/path/indxpath.c
index c0fcc7d78df..4fd0bbce2ce 100644
--- a/src/backend/optimizer/path/indxpath.c
+++ b/src/backend/optimizer/path/indxpath.c
@@ -19,10 +19,12 @@
#include "access/stratnum.h"
#include "access/sysattr.h"
+#include "catalog/namespace.h"
#include "catalog/pg_am.h"
#include "catalog/pg_operator.h"
#include "catalog/pg_opfamily.h"
#include "catalog/pg_type.h"
+#include "nodes/bitmapset.h"
#include "nodes/makefuncs.h"
#include "nodes/nodeFuncs.h"
#include "nodes/supportnodes.h"
@@ -30,9 +32,14 @@
#include "optimizer/optimizer.h"
#include "optimizer/pathnode.h"
#include "optimizer/paths.h"
+#include "optimizer/planmain.h"
#include "optimizer/prep.h"
#include "optimizer/restrictinfo.h"
+#include "parser/parse_oper.h"
+#include "postgres_ext.h"
+#include "utils/array.h"
#include "utils/lsyscache.h"
+#include "utils/syscache.h"
#include "utils/selfuncs.h"
@@ -177,6 +184,10 @@ static IndexClause *match_rowcompare_to_indexcol(PlannerInfo *root,
RestrictInfo *rinfo,
int indexcol,
IndexOptInfo *index);
+static IndexClause *match_orclause_to_indexcol(PlannerInfo *root,
+ RestrictInfo *rinfo,
+ int indexcol,
+ IndexOptInfo *index);
static IndexClause *expand_indexqual_rowcompare(PlannerInfo *root,
RestrictInfo *rinfo,
int indexcol,
@@ -2248,6 +2259,10 @@ match_clause_to_indexcol(PlannerInfo *root,
{
return match_rowcompare_to_indexcol(root, rinfo, indexcol, index);
}
+ else if (restriction_is_or_clause(rinfo))
+ {
+ return match_orclause_to_indexcol(root, rinfo, indexcol, index);
+ }
else if (index->amsearchnulls && IsA(clause, NullTest))
{
NullTest *nt = (NullTest *) clause;
@@ -2771,6 +2786,232 @@ match_rowcompare_to_indexcol(PlannerInfo *root,
return NULL;
}
+/*
+ * match_orclause_to_indexcol()
+ * Handles the OR-expr case for match_clause_to_indexcol() in the case
+ * where it could be transformed to ScalarArrayOpExpr.
+ */
+static IndexClause *
+match_orclause_to_indexcol(PlannerInfo *root,
+ RestrictInfo *rinfo,
+ int indexcol,
+ IndexOptInfo *index)
+{
+ ListCell *lc;
+ BoolExpr *orclause = (BoolExpr *) rinfo->orclause;
+ Node *indexExpr = NULL;
+ List *consts = NIL;
+ Node *newa = NULL;
+ ScalarArrayOpExpr *saopexpr = NULL;
+ HeapTuple opertup;
+ Form_pg_operator operform;
+ Oid matchOpno = InvalidOid;
+ IndexClause *iclause;
+ Oid consttype = InvalidOid;
+ Oid arraytype = InvalidOid;
+ Oid inputcollid = InvalidOid;
+ bool have_param = false;
+
+ Assert(IsA(orclause, BoolExpr));
+ Assert(orclause->boolop == OR_EXPR);
+
+ if (bms_is_member(index->rel->relid, rinfo->right_relids))
+ return NULL;
+
+ foreach(lc, orclause->args)
+ {
+ RestrictInfo *sub_rinfo;
+ OpExpr *sub_qual;
+ Oid opno;
+ Node *leftop,
+ *rightop;
+ Node *const_expr;
+ Node *nconst_expr;
+
+ if (!IsA(lfirst(lc), RestrictInfo))
+ return NULL;
+
+ sub_rinfo = (RestrictInfo *) lfirst(lc);
+ sub_qual = (OpExpr *) sub_rinfo->clause;
+ opno = sub_qual->opno;
+
+ if (!IsA(sub_rinfo->clause, OpExpr))
+ return NULL;
+
+ if (sub_rinfo->is_pushed_down != rinfo->is_pushed_down ||
+ sub_rinfo->is_clone != rinfo->is_clone ||
+ sub_rinfo->security_level != rinfo->security_level ||
+ !bms_equal(sub_rinfo->required_relids, rinfo->required_relids) ||
+ !bms_equal(sub_rinfo->incompatible_relids, rinfo->incompatible_relids) ||
+ !bms_equal(sub_rinfo->outer_relids, rinfo->outer_relids))
+ {
+ /* RestrictInfo parameters don't match parent, so bail out */
+ return NULL;
+ }
+
+ if (get_op_rettype(opno) != BOOLOID)
+ {
+ /* Only operator returning boolean suits OR -> ANY transformation */
+ return NULL;
+ }
+
+ /*
+ * Detect the constant side of the clause. Recall non-constant
+ * expression can be made not only with Vars, but also with Params,
+ * which is not bonded with any relation. Thus, we detect the const
+ * side - if another side is constant too, the orqual couldn't be an
+ * OpExpr. Get pointers to constant and expression sides of the qual.
+ */
+
+ leftop = get_leftop(sub_qual);
+ if (IsA(leftop, RelabelType))
+ leftop = (Node *) ((RelabelType *) leftop)->arg;
+
+ rightop = get_rightop(sub_qual);
+ if (IsA(rightop, RelabelType))
+ rightop = (Node *) ((RelabelType *) rightop)->arg;
+
+ if (IsA(leftop, Const) || IsA(leftop, Param))
+ {
+ opno = get_commutator(opno);
+
+ if (!OidIsValid(opno))
+ {
+ /* commutator doesn't exist, we can't reverse the order */
+ return false;
+ }
+
+ nconst_expr = rightop;
+ const_expr = leftop;
+ }
+ else if (IsA(rightop, Const) || IsA(rightop, Param))
+ {
+ const_expr = rightop;
+ nconst_expr = leftop;
+ }
+ else
+ {
+ return NULL;
+ }
+
+ if (!match_index_to_operand(nconst_expr, indexcol, index))
+ return NULL;
+
+ /*
+ * Forbid transformation for composite types, records.
+ */
+ if (type_is_rowtype(exprType(nconst_expr)) ||
+ type_is_rowtype(exprType(const_expr)))
+ {
+ return NULL;
+ }
+
+ if (!OidIsValid(matchOpno))
+ {
+ matchOpno = opno;
+ indexExpr = nconst_expr;
+ consttype = exprType(const_expr);
+ arraytype = get_array_type(consttype);
+ inputcollid = sub_qual->inputcollid;
+ if (!OidIsValid(arraytype))
+ return NULL;
+ }
+ else
+ {
+ if (opno != matchOpno ||
+ inputcollid != sub_qual->inputcollid)
+ return NULL;
+ }
+
+ if (IsA(const_expr, Param))
+ have_param = true;
+ consts = lappend(consts, const_expr);
+ }
+
+ if (have_param)
+ {
+ /*
+ * We need to construct an ArrayExpr given we have Param's not just
+ * Const's.
+ */
+ ArrayExpr *arexpr = makeNode(ArrayExpr);
+
+ /* array_collid will be set by parse_collate.c */
+ arexpr->element_typeid = consttype;
+ arexpr->array_typeid = arraytype;
+ arexpr->multidims = false;
+ arexpr->elements = consts;
+ arexpr->location = -1;
+
+ newa = (Node *) arexpr;
+ }
+ else
+ {
+ /* We have only Costs's. Can generate constant array. */
+
+ int16 typlen;
+ bool typbyval;
+ char typalign;
+ Datum *elems;
+ int i = 0;
+ ArrayType *ar;
+
+ get_typlenbyvalalign(consttype, &typlen, &typbyval, &typalign);
+
+ elems = (Datum *) palloc(sizeof(Datum) * list_length(consts));
+ foreach(lc, consts)
+ {
+ Node *elem = (Node *) lfirst(lc);
+
+ elems[i++] = ((Const *) elem)->constvalue;
+ }
+
+ ar = construct_array(elems, i, consttype, typlen, typbyval, typalign);
+ newa = (Node *) makeConst(arraytype, -1, inputcollid, -1, PointerGetDatum(ar), false, false);
+
+ pfree(elems);
+ list_free(consts);
+ }
+
+ opertup = SearchSysCache1(OPEROID,
+ ObjectIdGetDatum(matchOpno));
+ if (!HeapTupleIsValid(opertup))
+ elog(ERROR, "cache lookup failed for operator %u", matchOpno);
+
+ operform = (Form_pg_operator) GETSTRUCT(opertup);
+
+ /* and build the expression node */
+ saopexpr = makeNode(ScalarArrayOpExpr);
+ saopexpr->opno = matchOpno;
+ saopexpr->opfuncid = operform->oprcode;
+ saopexpr->hashfuncid = InvalidOid;
+ saopexpr->negfuncid = InvalidOid;
+ saopexpr->useOr = true;
+ saopexpr->inputcollid = inputcollid;
+ /* inputcollid will be set by parse_collate.c */
+ saopexpr->args = list_make2(indexExpr, newa);
+ saopexpr->location = -1;
+
+ ReleaseSysCache(opertup);
+
+ iclause = makeNode(IndexClause);
+ iclause->rinfo = make_restrictinfo(root,
+ &saopexpr->xpr,
+ rinfo->is_pushed_down,
+ rinfo->has_clone,
+ rinfo->is_clone,
+ rinfo->pseudoconstant,
+ rinfo->security_level,
+ rinfo->required_relids,
+ rinfo->incompatible_relids,
+ rinfo->outer_relids);
+ iclause->indexquals = list_make1(iclause->rinfo);
+ iclause->lossy = false;
+ iclause->indexcol = indexcol;
+ iclause->indexcols = NIL;
+ return iclause;
+}
+
/*
* expand_indexqual_rowcompare --- expand a single indexqual condition
* that is a RowCompareExpr
diff --git a/src/test/regress/expected/create_index.out b/src/test/regress/expected/create_index.out
index cf6eac57349..c2b25936c8c 100644
--- a/src/test/regress/expected/create_index.out
+++ b/src/test/regress/expected/create_index.out
@@ -1844,18 +1844,11 @@ DROP TABLE onek_with_null;
EXPLAIN (COSTS OFF)
SELECT * FROM tenk1
WHERE thousand = 42 AND (tenthous = 1 OR tenthous = 3 OR tenthous = 42);
- QUERY PLAN
------------------------------------------------------------------------------------------------------------------------------------------
- Bitmap Heap Scan on tenk1
- Recheck Cond: (((thousand = 42) AND (tenthous = 1)) OR ((thousand = 42) AND (tenthous = 3)) OR ((thousand = 42) AND (tenthous = 42)))
- -> BitmapOr
- -> Bitmap Index Scan on tenk1_thous_tenthous
- Index Cond: ((thousand = 42) AND (tenthous = 1))
- -> Bitmap Index Scan on tenk1_thous_tenthous
- Index Cond: ((thousand = 42) AND (tenthous = 3))
- -> Bitmap Index Scan on tenk1_thous_tenthous
- Index Cond: ((thousand = 42) AND (tenthous = 42))
-(9 rows)
+ QUERY PLAN
+------------------------------------------------------------------------------
+ Index Scan using tenk1_thous_tenthous on tenk1
+ Index Cond: ((thousand = 42) AND (tenthous = ANY ('{1,3,42}'::integer[])))
+(2 rows)
SELECT * FROM tenk1
WHERE thousand = 42 AND (tenthous = 1 OR tenthous = 3 OR tenthous = 42);
@@ -1864,14 +1857,166 @@ SELECT * FROM tenk1
42 | 5530 | 0 | 2 | 2 | 2 | 42 | 42 | 42 | 42 | 42 | 84 | 85 | QBAAAA | SEIAAA | OOOOxx
(1 row)
+EXPLAIN (COSTS OFF)
+SELECT * FROM tenk1
+ WHERE thousand = 42 AND (tenthous = 1 OR tenthous = (SELECT 1 + 2) OR tenthous = 42);
+ QUERY PLAN
+----------------------------------------------------------------------------------------
+ Index Scan using tenk1_thous_tenthous on tenk1
+ Index Cond: ((thousand = 42) AND (tenthous = ANY (ARRAY[1, (InitPlan 1).col1, 42])))
+ InitPlan 1
+ -> Result
+(4 rows)
+
+SELECT * FROM tenk1
+ WHERE thousand = 42 AND (tenthous = 1 OR tenthous = (SELECT 1 + 2) OR tenthous = 42);
+ unique1 | unique2 | two | four | ten | twenty | hundred | thousand | twothousand | fivethous | tenthous | odd | even | stringu1 | stringu2 | string4
+---------+---------+-----+------+-----+--------+---------+----------+-------------+-----------+----------+-----+------+----------+----------+---------
+ 42 | 5530 | 0 | 2 | 2 | 2 | 42 | 42 | 42 | 42 | 42 | 84 | 85 | QBAAAA | SEIAAA | OOOOxx
+(1 row)
+
EXPLAIN (COSTS OFF)
SELECT count(*) FROM tenk1
WHERE hundred = 42 AND (thousand = 42 OR thousand = 99);
- QUERY PLAN
----------------------------------------------------------------------------------
+ QUERY PLAN
+------------------------------------------------------------------------------------
Aggregate
-> Bitmap Heap Scan on tenk1
- Recheck Cond: ((hundred = 42) AND ((thousand = 42) OR (thousand = 99)))
+ Recheck Cond: ((hundred = 42) AND (thousand = ANY ('{42,99}'::integer[])))
+ -> BitmapAnd
+ -> Bitmap Index Scan on tenk1_hundred
+ Index Cond: (hundred = 42)
+ -> Bitmap Index Scan on tenk1_thous_tenthous
+ Index Cond: (thousand = ANY ('{42,99}'::integer[]))
+(8 rows)
+
+SELECT count(*) FROM tenk1
+ WHERE hundred = 42 AND (thousand = 42 OR thousand = 99);
+ count
+-------
+ 10
+(1 row)
+
+EXPLAIN (COSTS OFF)
+SELECT * FROM tenk1
+ WHERE thousand = 42 AND (tenthous = 1 OR tenthous = 3 OR tenthous = 42);
+ QUERY PLAN
+------------------------------------------------------------------------------
+ Index Scan using tenk1_thous_tenthous on tenk1
+ Index Cond: ((thousand = 42) AND (tenthous = ANY ('{1,3,42}'::integer[])))
+(2 rows)
+
+SELECT * FROM tenk1
+ WHERE thousand = 42 AND (tenthous = 1 OR tenthous = 3 OR tenthous = 42);
+ unique1 | unique2 | two | four | ten | twenty | hundred | thousand | twothousand | fivethous | tenthous | odd | even | stringu1 | stringu2 | string4
+---------+---------+-----+------+-----+--------+---------+----------+-------------+-----------+----------+-----+------+----------+----------+---------
+ 42 | 5530 | 0 | 2 | 2 | 2 | 42 | 42 | 42 | 42 | 42 | 84 | 85 | QBAAAA | SEIAAA | OOOOxx
+(1 row)
+
+EXPLAIN (COSTS OFF)
+SELECT count(*) FROM tenk1
+ WHERE hundred = 42 AND (thousand = 42 OR thousand = 99);
+ QUERY PLAN
+------------------------------------------------------------------------------------
+ Aggregate
+ -> Bitmap Heap Scan on tenk1
+ Recheck Cond: ((hundred = 42) AND (thousand = ANY ('{42,99}'::integer[])))
+ -> BitmapAnd
+ -> Bitmap Index Scan on tenk1_hundred
+ Index Cond: (hundred = 42)
+ -> Bitmap Index Scan on tenk1_thous_tenthous
+ Index Cond: (thousand = ANY ('{42,99}'::integer[]))
+(8 rows)
+
+SELECT count(*) FROM tenk1
+ WHERE hundred = 42 AND (thousand = 42 OR thousand = 99);
+ count
+-------
+ 10
+(1 row)
+
+EXPLAIN (COSTS OFF)
+SELECT count(*) FROM tenk1
+ WHERE hundred = 42 AND (thousand < 42 OR thousand < 99 OR 43 > thousand OR 42 > thousand);
+ QUERY PLAN
+------------------------------------------------------------------------------------------
+ Aggregate
+ -> Bitmap Heap Scan on tenk1
+ Recheck Cond: ((hundred = 42) AND (thousand < ANY ('{42,99,43,42}'::integer[])))
+ -> BitmapAnd
+ -> Bitmap Index Scan on tenk1_hundred
+ Index Cond: (hundred = 42)
+ -> Bitmap Index Scan on tenk1_thous_tenthous
+ Index Cond: (thousand < ANY ('{42,99,43,42}'::integer[]))
+(8 rows)
+
+SELECT count(*) FROM tenk1
+ WHERE hundred = 42 AND (thousand < 42 OR thousand < 99 OR 43 > thousand OR 42 > thousand);
+ count
+-------
+ 10
+(1 row)
+
+EXPLAIN (COSTS OFF)
+SELECT count(*) FROM tenk1
+ WHERE thousand = 42 AND (tenthous = 1 OR tenthous = 3) OR thousand = 41;
+ QUERY PLAN
+--------------------------------------------------------------------------------------------------------
+ Aggregate
+ -> Bitmap Heap Scan on tenk1
+ Recheck Cond: (((thousand = 42) AND (tenthous = ANY ('{1,3}'::integer[]))) OR (thousand = 41))
+ -> BitmapOr
+ -> Bitmap Index Scan on tenk1_thous_tenthous
+ Index Cond: ((thousand = 42) AND (tenthous = ANY ('{1,3}'::integer[])))
+ -> Bitmap Index Scan on tenk1_thous_tenthous
+ Index Cond: (thousand = 41)
+(8 rows)
+
+SELECT count(*) FROM tenk1
+ WHERE thousand = 42 AND (tenthous = 1 OR tenthous = 3) OR thousand = 41;
+ count
+-------
+ 10
+(1 row)
+
+EXPLAIN (COSTS OFF)
+SELECT count(*) FROM tenk1
+ WHERE hundred = 42 AND (thousand = 42 OR thousand = 99 OR tenthous < 2) OR thousand = 41;
+ QUERY PLAN
+------------------------------------------------------------------------------------------------------------------------
+ Aggregate
+ -> Bitmap Heap Scan on tenk1
+ Recheck Cond: (((hundred = 42) AND ((thousand = 42) OR (thousand = 99) OR (tenthous < 2))) OR (thousand = 41))
+ -> BitmapOr
+ -> BitmapAnd
+ -> Bitmap Index Scan on tenk1_hundred
+ Index Cond: (hundred = 42)
+ -> BitmapOr
+ -> Bitmap Index Scan on tenk1_thous_tenthous
+ Index Cond: (thousand = 42)
+ -> Bitmap Index Scan on tenk1_thous_tenthous
+ Index Cond: (thousand = 99)
+ -> Bitmap Index Scan on tenk1_thous_tenthous
+ Index Cond: (tenthous < 2)
+ -> Bitmap Index Scan on tenk1_thous_tenthous
+ Index Cond: (thousand = 41)
+(16 rows)
+
+SELECT count(*) FROM tenk1
+ WHERE hundred = 42 AND (thousand = 42 OR thousand = 99 OR tenthous < 2) OR thousand = 41;
+ count
+-------
+ 20
+(1 row)
+
+EXPLAIN (COSTS OFF)
+SELECT count(*) FROM tenk1
+ WHERE hundred = 42 AND (thousand = 42 OR thousand = 41 OR thousand = 99 AND tenthous = 2);
+ QUERY PLAN
+-------------------------------------------------------------------------------------------------------------------------
+ Aggregate
+ -> Bitmap Heap Scan on tenk1
+ Recheck Cond: ((hundred = 42) AND ((thousand = 42) OR (thousand = 41) OR ((thousand = 99) AND (tenthous = 2))))
-> BitmapAnd
-> Bitmap Index Scan on tenk1_hundred
Index Cond: (hundred = 42)
@@ -1879,11 +2024,13 @@ SELECT count(*) FROM tenk1
-> Bitmap Index Scan on tenk1_thous_tenthous
Index Cond: (thousand = 42)
-> Bitmap Index Scan on tenk1_thous_tenthous
- Index Cond: (thousand = 99)
-(11 rows)
+ Index Cond: (thousand = 41)
+ -> Bitmap Index Scan on tenk1_thous_tenthous
+ Index Cond: ((thousand = 99) AND (tenthous = 2))
+(13 rows)
SELECT count(*) FROM tenk1
- WHERE hundred = 42 AND (thousand = 42 OR thousand = 99);
+ WHERE hundred = 42 AND (thousand = 42 OR thousand = 41 OR thousand = 99 AND tenthous = 2);
count
-------
10
diff --git a/src/test/regress/expected/join.out b/src/test/regress/expected/join.out
index 53f70d72ed6..abe98ff3c53 100644
--- a/src/test/regress/expected/join.out
+++ b/src/test/regress/expected/join.out
@@ -4278,15 +4278,64 @@ select * from tenk1 a join tenk1 b on
Index Cond: (hundred = 4)
-> Materialize
-> Bitmap Heap Scan on tenk1 a
- Recheck Cond: ((unique1 = 1) OR (unique2 = 3) OR (unique2 = 7))
+ Recheck Cond: ((unique1 = 1) OR (unique2 = ANY ('{3,7}'::integer[])))
+ Filter: ((unique1 = 1) OR (unique2 = 3) OR (unique2 = 7))
-> BitmapOr
-> Bitmap Index Scan on tenk1_unique1
Index Cond: (unique1 = 1)
-> Bitmap Index Scan on tenk1_unique2
- Index Cond: (unique2 = 3)
+ Index Cond: (unique2 = ANY ('{3,7}'::integer[]))
+(18 rows)
+
+explain (costs off)
+select * from tenk1 a join tenk1 b on
+ (a.unique1 = 1 and b.unique1 = 2) or
+ ((a.unique2 = 3 or a.unique2 = 7) and b.hundred = 4);
+ QUERY PLAN
+----------------------------------------------------------------------------------------------------------------------
+ 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: ((unique1 = 2) OR (hundred = 4))
+ -> BitmapOr
+ -> 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: ((unique1 = 1) OR (unique2 = ANY ('{3,7}'::integer[])))
+ Filter: ((unique1 = 1) OR (unique2 = 3) OR (unique2 = 7))
+ -> BitmapOr
+ -> Bitmap Index Scan on tenk1_unique1
+ Index Cond: (unique1 = 1)
-> Bitmap Index Scan on tenk1_unique2
- Index Cond: (unique2 = 7)
-(19 rows)
+ Index Cond: (unique2 = ANY ('{3,7}'::integer[]))
+(18 rows)
+
+explain (costs off)
+select * from tenk1 a join tenk1 b on
+ (a.unique1 < 20 or a.unique1 = 3 or a.unique1 = 1 and b.unique1 = 2) or
+ ((a.unique2 = 3 or a.unique2 = 7) and b.hundred = 4);
+ QUERY PLAN
+-------------------------------------------------------------------------------------------------------------------------------------------------------------
+ Nested Loop
+ Join Filter: ((a.unique1 < 20) OR (a.unique1 = 3) OR ((a.unique1 = 1) AND (b.unique1 = 2)) OR (((a.unique2 = 3) OR (a.unique2 = 7)) AND (b.hundred = 4)))
+ -> Seq Scan on tenk1 b
+ -> Materialize
+ -> Bitmap Heap Scan on tenk1 a
+ Recheck Cond: ((unique1 < 20) OR (unique1 = 3) OR (unique1 = 1) OR (unique2 = ANY ('{3,7}'::integer[])))
+ Filter: ((unique1 < 20) OR (unique1 = 3) OR (unique1 = 1) OR (unique2 = 3) OR (unique2 = 7))
+ -> BitmapOr
+ -> Bitmap Index Scan on tenk1_unique1
+ Index Cond: (unique1 < 20)
+ -> Bitmap Index Scan on tenk1_unique1
+ Index Cond: (unique1 = 3)
+ -> Bitmap Index Scan on tenk1_unique1
+ Index Cond: (unique1 = 1)
+ -> Bitmap Index Scan on tenk1_unique2
+ Index Cond: (unique2 = ANY ('{3,7}'::integer[]))
+(16 rows)
--
-- test placement of movable quals in a parameterized join tree
diff --git a/src/test/regress/sql/create_index.sql b/src/test/regress/sql/create_index.sql
index e296891cab8..f74ad415fbf 100644
--- a/src/test/regress/sql/create_index.sql
+++ b/src/test/regress/sql/create_index.sql
@@ -726,6 +726,24 @@ DROP TABLE onek_with_null;
-- Check bitmap index path planning
--
+EXPLAIN (COSTS OFF)
+SELECT * FROM tenk1
+ WHERE thousand = 42 AND (tenthous = 1 OR tenthous = 3 OR tenthous = 42);
+SELECT * FROM tenk1
+ WHERE thousand = 42 AND (tenthous = 1 OR tenthous = 3 OR tenthous = 42);
+
+EXPLAIN (COSTS OFF)
+SELECT * FROM tenk1
+ WHERE thousand = 42 AND (tenthous = 1 OR tenthous = (SELECT 1 + 2) OR tenthous = 42);
+SELECT * FROM tenk1
+ WHERE thousand = 42 AND (tenthous = 1 OR tenthous = (SELECT 1 + 2) OR tenthous = 42);
+
+EXPLAIN (COSTS OFF)
+SELECT count(*) FROM tenk1
+ WHERE hundred = 42 AND (thousand = 42 OR thousand = 99);
+SELECT count(*) FROM tenk1
+ WHERE hundred = 42 AND (thousand = 42 OR thousand = 99);
+
EXPLAIN (COSTS OFF)
SELECT * FROM tenk1
WHERE thousand = 42 AND (tenthous = 1 OR tenthous = 3 OR tenthous = 42);
@@ -738,6 +756,30 @@ SELECT count(*) FROM tenk1
SELECT count(*) FROM tenk1
WHERE hundred = 42 AND (thousand = 42 OR thousand = 99);
+EXPLAIN (COSTS OFF)
+SELECT count(*) FROM tenk1
+ WHERE hundred = 42 AND (thousand < 42 OR thousand < 99 OR 43 > thousand OR 42 > thousand);
+SELECT count(*) FROM tenk1
+ WHERE hundred = 42 AND (thousand < 42 OR thousand < 99 OR 43 > thousand OR 42 > thousand);
+
+EXPLAIN (COSTS OFF)
+SELECT count(*) FROM tenk1
+ WHERE thousand = 42 AND (tenthous = 1 OR tenthous = 3) OR thousand = 41;
+SELECT count(*) FROM tenk1
+ WHERE thousand = 42 AND (tenthous = 1 OR tenthous = 3) OR thousand = 41;
+
+EXPLAIN (COSTS OFF)
+SELECT count(*) FROM tenk1
+ WHERE hundred = 42 AND (thousand = 42 OR thousand = 99 OR tenthous < 2) OR thousand = 41;
+SELECT count(*) FROM tenk1
+ WHERE hundred = 42 AND (thousand = 42 OR thousand = 99 OR tenthous < 2) OR thousand = 41;
+
+EXPLAIN (COSTS OFF)
+SELECT count(*) FROM tenk1
+ WHERE hundred = 42 AND (thousand = 42 OR thousand = 41 OR thousand = 99 AND tenthous = 2);
+SELECT count(*) FROM tenk1
+ WHERE hundred = 42 AND (thousand = 42 OR thousand = 41 OR thousand = 99 AND tenthous = 2);
+
--
-- Check behavior with duplicate index column contents
--
diff --git a/src/test/regress/sql/join.sql b/src/test/regress/sql/join.sql
index d81ff63be53..4473b8f04d5 100644
--- a/src/test/regress/sql/join.sql
+++ b/src/test/regress/sql/join.sql
@@ -1433,6 +1433,15 @@ select * from tenk1 a join tenk1 b on
(a.unique1 = 1 and b.unique1 = 2) or
((a.unique2 = 3 or a.unique2 = 7) and b.hundred = 4);
+explain (costs off)
+select * from tenk1 a join tenk1 b on
+ (a.unique1 = 1 and b.unique1 = 2) or
+ ((a.unique2 = 3 or a.unique2 = 7) and b.hundred = 4);
+explain (costs off)
+select * from tenk1 a join tenk1 b on
+ (a.unique1 < 20 or a.unique1 = 3 or a.unique1 = 1 and b.unique1 = 2) or
+ ((a.unique2 = 3 or a.unique2 = 7) and b.hundred = 4);
+
--
-- test placement of movable quals in a parameterized join tree
--
diff --git a/src/tools/pgindent/typedefs.list b/src/tools/pgindent/typedefs.list
index b4d7f9217ce..992c80f9350 100644
--- a/src/tools/pgindent/typedefs.list
+++ b/src/tools/pgindent/typedefs.list
@@ -1717,6 +1717,7 @@ NumericVar
OM_uint32
OP
OSAPerGroupState
+OrClauseGroup
OSAPerQueryState
OSInfo
OSSLCipher
--
2.39.3 (Apple Git-145)
^ permalink raw reply [nested|flat] 8+ messages in thread
end of thread, other threads:[~2024-07-29 02:36 UTC | newest]
Thread overview: 8+ messages (download: mbox mbox.gz follow: Atom feed)
-- links below jump to the message on this page --
2021-07-05 10:45 [PATCH] Allow Sort nodes to use the fast "single datum" tuplesort. Ronan Dunklau <[email protected]>
2024-07-21 22:53 Re: POC, WIP: OR-clause support for indexes Alena Rybakina <[email protected]>
2024-07-22 00:52 ` Re: POC, WIP: OR-clause support for indexes Alexander Korotkov <[email protected]>
2024-07-22 00:54 ` Re: POC, WIP: OR-clause support for indexes Alexander Korotkov <[email protected]>
2024-07-25 14:04 ` Re: POC, WIP: OR-clause support for indexes Alena Rybakina <[email protected]>
2024-07-27 10:56 ` Re: POC, WIP: OR-clause support for indexes Alexander Korotkov <[email protected]>
2024-07-28 09:59 ` Re: POC, WIP: OR-clause support for indexes Alena Rybakina <[email protected]>
2024-07-29 02:36 ` Re: POC, WIP: OR-clause support for indexes Alexander Korotkov <[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