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
<a.rybak...@postgrespro.ru> 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.gmail.com
2.https://www.postgresql.org/message-id/CAPpHfdtSXxhdv3mLOLjEewGeXJ%2BFtfhjqodn1WWuq5JLsKx48g%40mail.gmail.com
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
From 31f58b8ad85e77534d38d099368168d9f775149f Mon Sep 17 00:00:00 2001
From: Alena Rybakina <a.rybak...@postgrespro.ru>
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 <lena.riback...@yandex.ru>
Author: Andrey Lepikhov <a.lepik...@postgrespro.ru>
Reviewed-by: Peter Geoghegan <p...@bowt.ie>
Reviewed-by: Ranier Vilela <ranier...@gmail.com>
Reviewed-by: Alexander Korotkov <aekorot...@gmail.com>
Reviewed-by: Robert Haas <robertmh...@gmail.com>
Reviewed-by: Jian He <jian.universal...@gmail.com>
Reviewed-by: Tom Lane <t...@sss.pgh.pa.us>
Reviewed-by: Nikolay Shaplov <dh...@nataraj.su>
---
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
