public inbox for [email protected]
help / color / mirror / Atom feedFrom: Alexander Korotkov <[email protected]>
To: Andrei Lepikhov <[email protected]>
Cc: jian he <[email protected]>
Cc: Alena Rybakina <[email protected]>
Cc: Robert Haas <[email protected]>
Cc: [email protected]
Cc: Peter Geoghegan <[email protected]>
Cc: Finnerty, Jim <[email protected]>
Cc: Marcos Pegoraro <[email protected]>
Cc: [email protected]
Cc: Tomas Vondra <[email protected]>
Cc: Peter Eisentraut <[email protected]>
Cc: Ranier Vilela <[email protected]>
Subject: Re: POC, WIP: OR-clause support for indexes
Date: Fri, 14 Jun 2024 15:00:33 +0300
Message-ID: <CAPpHfduah1PLzajBJFDmp7+MZuaWYpie2p+GsV0r03fcGghQ-g@mail.gmail.com> (raw)
In-Reply-To: <CAPpHfdtGmUHv=E4QWGWHk2QUuJ-x0mTNBssW_Ehv2dcOQ2L66g@mail.gmail.com>
References: <[email protected]>
<[email protected]>
<CACJufxE6eG3ATnTfO9ubs7CjyfgjpCQrSt85oU33EZj00PdcbQ@mail.gmail.com>
<[email protected]>
<[email protected]>
<CAPpHfdtACtU_XbuNf9mgDBsTH1cN=i+uASXKBX_rvQk6zQ3MdQ@mail.gmail.com>
<[email protected]>
<CAPpHfdsAWGF2VvcszNofc32Sa2pefBpgY1nw2aYV=FTG7Q3wyA@mail.gmail.com>
<[email protected]>
<CAPpHfdutHt31sdt2rfU=4fsDMWxf6tvtnHARgCzLY2Tf21+fgw@mail.gmail.com>
<[email protected]>
<CAPpHfdsADL+agHnnjvi_42hNJWQdHK76SVPbNjsqAyHzxOxv8w@mail.gmail.com>
<[email protected]>
<CAPpHfdtSXxhdv3mLOLjEewGeXJ+Ftfhjqodn1WWuq5JLsKx48g@mail.gmail.com>
<[email protected]>
<CAPpHfdu4YJa5xCaOQnLzk4qsutRWrJGbcffVuZ=6R=eTAdMLig@mail.gmail.com>
<[email protected]>
<CAPpHfdtGmUHv=E4QWGWHk2QUuJ-x0mTNBssW_Ehv2dcOQ2L66g@mail.gmail.com>
On Mon, Apr 8, 2024 at 1:34 AM Alexander Korotkov <[email protected]> wrote:
>
> I've revised the patch. Did some beautification, improvements for
> documentation, commit messages etc.
>
> I've pushed the 0001 patch without 0002. I think 0001 is good by
> itself given that there is the or_to_any_transform_limit GUC option.
> The more similar OR clauses are here the more likely grouping them
> into SOAP will be a win. But I've changed the default value to 5.
> This will make it less invasive and affect only queries with obvious
> repeating patterns. That also reduced the changes in the regression
> tests expected outputs.
>
> Regarding 0002, it seems questionable since it could cause a planning
> slowdown for SAOP's with large arrays. Also, it might reduce the win
> of transformation made by 0001. So, I think we should skip it for
> now.
The patch has been reverted from pg17. Let me propose a new version
for pg18 based on the valuable feedback from Tom Lane [1][2].
* The transformation is moved to the stage of adding restrictinfos to
the base relation (in particular add_base_clause_to_rel()). This
leads to interesting consequences. While this allows IndexScans to
use transformed clauses, BitmapScans and SeqScans seem unaffected.
Therefore, I wasn't able to find a planning regression.
* As soon as there is no planning regression anymore, I've removed
or_to_any_transform_limit GUC, which was a source of critics.
* Now, not only Consts allowed in the SAOP's list, but also Params.
* The criticized hash based on expression jumbling has been removed.
Now, the plain list is used instead.
* OrClauseGroup now gets a legal node tag. That allows to mix it in
the list with other nodes without hacks.
I think this patch shouldn't be as good as before for optimizing
performance of large OR lists, given that BitmapScans and SeqScans
still deal with ORs. However, it allows IndexScans to handle more,
doesn't seem to cause planning regression and therefore introduce no
extra GUC. Overall, this seems like a good compromise.
This patch could use some polishing, but I'd like to first hear some
feedback on general design.
Links
1. https://www.postgresql.org/message-id/3604469.1712628736%40sss.pgh.pa.us
2. https://www.postgresql.org/message-id/3649287.1712642139%40sss.pgh.pa.us
------
Regards,
Alexander Korotkov
Supabase
Attachments:
[application/octet-stream] v25-0001-Transform-OR-clauses-to-ANY-expression.patch (34.3K, ../CAPpHfduah1PLzajBJFDmp7+MZuaWYpie2p+GsV0r03fcGghQ-g@mail.gmail.com/2-v25-0001-Transform-OR-clauses-to-ANY-expression.patch)
download | inline diff:
From cac9a150852a390f89e5322821224453c664f567 Mon Sep 17 00:00:00 2001
From: Alexander Korotkov <[email protected]>
Date: Fri, 14 Jun 2024 10:16:22 +0300
Subject: [PATCH v25] Transform OR clauses to ANY expression
Replace (expr op C1) OR (expr op C2) ... with expr op ANY(ARRAY[C1, C2, ...])
during adding restrictinfo's to the base relation.
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]>
---
src/backend/optimizer/plan/initsplan.c | 310 ++++++++++++++++++++-
src/include/nodes/pathnodes.h | 29 ++
src/include/nodes/queryjumble.h | 1 +
src/test/regress/expected/create_index.out | 189 +++++++++++--
src/test/regress/expected/join.out | 52 ++++
src/test/regress/expected/stats_ext.out | 12 +-
src/test/regress/expected/tidscan.out | 9 +-
src/test/regress/sql/create_index.sql | 42 +++
src/test/regress/sql/join.sql | 9 +
src/test/regress/sql/partition_prune.sql | 1 +
src/tools/pgindent/typedefs.list | 1 +
11 files changed, 627 insertions(+), 28 deletions(-)
diff --git a/src/backend/optimizer/plan/initsplan.c b/src/backend/optimizer/plan/initsplan.c
index e2c68fe6f99..0022535318d 100644
--- a/src/backend/optimizer/plan/initsplan.c
+++ b/src/backend/optimizer/plan/initsplan.c
@@ -14,9 +14,13 @@
*/
#include "postgres.h"
+#include "catalog/namespace.h"
+#include "catalog/pg_operator.h"
#include "catalog/pg_type.h"
+#include "common/hashfn.h"
#include "nodes/makefuncs.h"
#include "nodes/nodeFuncs.h"
+#include "nodes/queryjumble.h"
#include "optimizer/clauses.h"
#include "optimizer/cost.h"
#include "optimizer/inherit.h"
@@ -29,8 +33,11 @@
#include "optimizer/planner.h"
#include "optimizer/restrictinfo.h"
#include "parser/analyze.h"
+#include "parser/parse_coerce.h"
+#include "parser/parse_oper.h"
#include "rewrite/rewriteManip.h"
#include "utils/lsyscache.h"
+#include "utils/syscache.h"
#include "utils/rel.h"
#include "utils/typcache.h"
@@ -38,7 +45,6 @@
int from_collapse_limit;
int join_collapse_limit;
-
/*
* deconstruct_jointree requires multiple passes over the join tree, because we
* need to finish computing JoinDomains before we start distributing quals.
@@ -2617,6 +2623,296 @@ check_redundant_nullability_qual(PlannerInfo *root, Node *clause)
return false;
}
+/*
+ * 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, List *orlist)
+{
+ List *neworlist = NIL;
+ List *entries = NIL;
+ ListCell *lc;
+ int len_ors = list_length(orlist);
+ OrClauseGroup *entry = NULL;
+
+ Assert(len_ors >= 2);
+
+ foreach(lc, orlist)
+ {
+ RestrictInfo *rinfo = (RestrictInfo *) lfirst(lc);
+ OpExpr *orqual;
+ Node *const_expr;
+ Node *nconst_expr;
+ bool found = false;
+ Oid opno;
+ Oid consttype;
+ Node *leftop,
+ *rightop;
+ ListCell *lc2;
+
+ if (!IsA(rinfo, RestrictInfo) || !IsA(rinfo->clause, OpExpr))
+ {
+ entries = lappend(entries, rinfo);
+ continue;
+ }
+
+ orqual = (OpExpr *) rinfo->clause;
+ opno = orqual->opno;
+ if (get_op_rettype(opno) != BOOLOID)
+ {
+ /* Only operator returning boolean suits OR -> ANY transformation */
+ entries = lappend(entries, rinfo);
+ continue;
+ }
+
+ /*
+ * 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 */
+ entries = lappend(entries, rinfo);
+ continue;
+ }
+
+ 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
+ {
+ entries = lappend(entries, rinfo);
+ continue;
+ }
+
+ /*
+ * 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))
+ {
+ entries = lappend(entries, rinfo);
+ continue;
+ }
+
+ foreach(lc2, entries)
+ {
+ if (!IsA(lfirst(lc2), OrClauseGroup))
+ continue;
+
+ entry = (OrClauseGroup *) lfirst(lc2);
+
+ if (entry->opno == opno &&
+ entry->consttype == consttype &&
+ entry->inputcollid == exprCollation(const_expr) &&
+ equal(entry->expr, nconst_expr))
+ {
+ found = true;
+ break;
+ }
+ }
+
+ if (unlikely(found))
+ {
+ entry->consts = lappend(entry->consts, const_expr);
+ entry->exprs = lappend(entry->exprs, rinfo);
+ }
+ else
+ {
+ entry = makeNode(OrClauseGroup);
+ entry->expr = (Expr *) nconst_expr;
+ entry->opno = opno;
+ entry->consttype = consttype;
+ entry->inputcollid = exprCollation(const_expr);
+
+ entry->consts = list_make1(const_expr);
+ entry->exprs = list_make1(rinfo);
+
+ /*
+ * Add the 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.
+ */
+ entries = lappend(entries, entry);
+ }
+ }
+
+ /* 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, entries)
+ {
+ Oid scalar_type;
+ Oid array_type;
+
+ if (!IsA(lfirst(lc), OrClauseGroup))
+ {
+ neworlist = lappend(neworlist, lfirst(lc));
+ continue;
+ }
+
+ entry = (OrClauseGroup *) lfirst(lc);
+
+ Assert(list_length(entry->consts) > 0);
+ Assert(list_length(entry->exprs) == list_length(entry->consts));
+
+ if (list_length(entry->consts) == 1)
+ {
+ /*
+ * Only one element returns origin expression into the BoolExpr
+ * args list unchanged.
+ */
+ list_free(entry->consts);
+ neworlist = list_concat(neworlist, entry->exprs);
+ continue;
+ }
+
+ /*
+ * Do the transformation.
+ */
+ scalar_type = entry->consttype;
+ array_type = OidIsValid(scalar_type) ? get_array_type(scalar_type) :
+ InvalidOid;
+
+ if (OidIsValid(array_type))
+ {
+ /*
+ * OK: coerce all the right-hand non-Var inputs to the common type
+ * and build an ArrayExpr for them.
+ */
+ List *aexprs = NIL;
+ ArrayExpr *newa = NULL;
+ ScalarArrayOpExpr *saopexpr = NULL;
+ HeapTuple opertup;
+ Form_pg_operator operform;
+ List *namelist = NIL;
+ bool is_pushed_down = false;
+ bool has_clone = false;
+ Index security_level = 0;
+ Relids required_relids = NULL;
+ Relids incompatible_relids = NULL;
+ Relids outer_relids = NULL;
+ ListCell *lc2;
+
+ foreach(lc2, entry->consts)
+ {
+ Node *node = (Node *) lfirst(lc2);
+
+ node = coerce_to_common_type(NULL, node, scalar_type,
+ "OR ANY Transformation");
+ aexprs = lappend(aexprs, node);
+ }
+
+ foreach(lc2, entry->exprs)
+ {
+ RestrictInfo *rinfo = (RestrictInfo *) lfirst(lc2);
+
+ is_pushed_down = is_pushed_down || rinfo->is_pushed_down;
+ has_clone = has_clone || rinfo->is_pushed_down;
+ security_level = Max(security_level, rinfo->security_level);
+ required_relids = bms_union(required_relids, rinfo->required_relids);
+ incompatible_relids = bms_union(incompatible_relids, rinfo->incompatible_relids);
+ outer_relids = bms_union(outer_relids, rinfo->outer_relids);
+ }
+
+ newa = makeNode(ArrayExpr);
+ /* array_collid will be set by parse_collate.c */
+ newa->element_typeid = scalar_type;
+ newa->array_typeid = array_type;
+ newa->multidims = false;
+ newa->elements = aexprs;
+ newa->location = -1;
+
+ /*
+ * Try to cast this expression to Const. Due to current strict
+ * transformation rules it should be done [almost] every time.
+ */
+ newa = (ArrayExpr *) eval_const_expressions(NULL, (Node *) newa);
+
+ opertup = SearchSysCache1(OPEROID,
+ ObjectIdGetDatum(entry->opno));
+ if (!HeapTupleIsValid(opertup))
+ elog(ERROR, "cache lookup failed for operator %u",
+ entry->opno);
+
+ operform = (Form_pg_operator) GETSTRUCT(opertup);
+ if (!OperatorIsVisible(entry->opno))
+ namelist = lappend(namelist, makeString(get_namespace_name(operform->oprnamespace)));
+
+ namelist = lappend(namelist, makeString(pstrdup(NameStr(operform->oprname))));
+ ReleaseSysCache(opertup);
+
+ saopexpr =
+ (ScalarArrayOpExpr *)
+ make_scalar_array_op(NULL,
+ namelist,
+ true,
+ (Node *) entry->expr,
+ (Node *) newa,
+ -1);
+ saopexpr->inputcollid = entry->inputcollid;
+
+ neworlist = lappend(neworlist, make_restrictinfo(root, (Expr *) saopexpr, is_pushed_down, has_clone, false, false, security_level, required_relids, incompatible_relids, outer_relids));
+ }
+ else
+ {
+ /*
+ * If the const node's (right side of operator expression) type
+ * don't have “true” array type, then we cannnot do the
+ * transformation. We simply concatenate the expression node.
+ */
+ list_free(entry->consts);
+ neworlist = list_concat(neworlist, entry->exprs);
+ }
+ }
+ list_free(entries);
+
+ /* One more trick: assemble correct clause */
+ return neworlist;
+}
+
/*
* add_base_clause_to_rel
* Add 'restrictinfo' as a baserestrictinfo to the base relation denoted
@@ -2677,6 +2973,18 @@ add_base_clause_to_rel(PlannerInfo *root, Index relid,
}
}
+ if (restriction_is_or_clause(restrictinfo))
+ {
+ BoolExpr *orExpr = (BoolExpr *) restrictinfo->orclause;
+
+ Assert(is_orclause(restrictinfo->orclause));
+
+ if (list_length(orExpr->args) >= 2)
+ {
+ orExpr->args = transform_or_to_any(root, orExpr->args);
+ }
+ }
+
/* Add clause to rel's restriction list */
rel->baserestrictinfo = lappend(rel->baserestrictinfo, restrictinfo);
diff --git a/src/include/nodes/pathnodes.h b/src/include/nodes/pathnodes.h
index 2ba297c1172..9d6c2da0f87 100644
--- a/src/include/nodes/pathnodes.h
+++ b/src/include/nodes/pathnodes.h
@@ -2708,6 +2708,35 @@ 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;
+} 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/include/nodes/queryjumble.h b/src/include/nodes/queryjumble.h
index f1c55c8067f..5643ee8f651 100644
--- a/src/include/nodes/queryjumble.h
+++ b/src/include/nodes/queryjumble.h
@@ -65,6 +65,7 @@ extern PGDLLIMPORT int compute_query_id;
extern const char *CleanQuerytext(const char *query, int *location, int *len);
extern JumbleState *JumbleQuery(Query *query);
+extern JumbleState *JumbleExpr(Expr *expr, uint64 *exprId);
extern void EnableQueryId(void);
extern PGDLLIMPORT bool query_id_enabled;
diff --git a/src/test/regress/expected/create_index.out b/src/test/regress/expected/create_index.out
index cf6eac57349..421a645fae0 100644
--- a/src/test/regress/expected/create_index.out
+++ b/src/test/regress/expected/create_index.out
@@ -1844,18 +1844,73 @@ 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
------------------------------------------------------------------------------------------------------------------------------------------
+ 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)
+ Recheck Cond: ((thousand = 42) AND (tenthous = ANY ('{1,3,42}'::integer[])))
+ -> Bitmap Index Scan on tenk1_thous_tenthous
+ Index Cond: ((thousand = 42) AND (tenthous = ANY ('{1,3,42}'::integer[])))
+(4 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 * FROM tenk1
+ WHERE thousand = 42 AND (tenthous = 1 OR tenthous = (SELECT 1 + 2) OR tenthous = 42);
+ QUERY PLAN
+----------------------------------------------------------------------------------------------
+ Bitmap Heap Scan on tenk1
+ Recheck Cond: ((thousand = 42) AND (tenthous = ANY (ARRAY[1, (InitPlan 1).col1, 42])))
+ InitPlan 1
+ -> Result
+ -> Bitmap Index Scan on tenk1_thous_tenthous
+ Index Cond: ((thousand = 42) AND (tenthous = ANY (ARRAY[1, (InitPlan 1).col1, 42])))
+(6 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
+------------------------------------------------------------------------------------
+ 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 * 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 = ANY ('{1,3,42}'::integer[])))
+ -> Bitmap Index Scan on tenk1_thous_tenthous
+ Index Cond: ((thousand = 42) AND (tenthous = ANY ('{1,3,42}'::integer[])))
+(4 rows)
SELECT * FROM tenk1
WHERE thousand = 42 AND (tenthous = 1 OR tenthous = 3 OR tenthous = 42);
@@ -1867,23 +1922,123 @@ SELECT * FROM tenk1
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 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 = 1)) OR ((thousand = 42) AND (tenthous = 3))) OR (thousand = 41))
+ -> BitmapOr
-> BitmapOr
-> Bitmap Index Scan on tenk1_thous_tenthous
- Index Cond: (thousand = 42)
+ Index Cond: ((thousand = 42) AND (tenthous = 1))
-> Bitmap Index Scan on tenk1_thous_tenthous
- Index Cond: (thousand = 99)
+ Index Cond: ((thousand = 42) AND (tenthous = 3))
+ -> Bitmap Index Scan on tenk1_thous_tenthous
+ Index Cond: (thousand = 41)
(11 rows)
SELECT count(*) FROM tenk1
- WHERE hundred = 42 AND (thousand = 42 OR thousand = 99);
+ 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 = ANY ('{42,41}'::integer[])) OR ((thousand = 99) AND (tenthous = 2))))
+ Filter: ((thousand = 42) OR (thousand = 41) OR ((thousand = 99) AND (tenthous = 2)))
+ -> BitmapAnd
+ -> Bitmap Index Scan on tenk1_hundred
+ Index Cond: (hundred = 42)
+ -> BitmapOr
+ -> Bitmap Index Scan on tenk1_thous_tenthous
+ Index Cond: (thousand = ANY ('{42,41}'::integer[]))
+ -> Bitmap Index Scan on tenk1_thous_tenthous
+ Index Cond: ((thousand = 99) AND (tenthous = 2))
+(12 rows)
+
+SELECT count(*) FROM tenk1
+ 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 6b16c3a6769..3cfc8d4e146 100644
--- a/src/test/regress/expected/join.out
+++ b/src/test/regress/expected/join.out
@@ -4233,6 +4233,58 @@ select * from tenk1 a join tenk1 b on
Index Cond: (unique2 = 7)
(19 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 = 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)
+ -> Bitmap Index Scan on tenk1_unique2
+ Index Cond: (unique2 = 7)
+(19 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 = 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 = 3)
+ -> Bitmap Index Scan on tenk1_unique2
+ Index Cond: (unique2 = 7)
+(17 rows)
+
--
-- test placement of movable quals in a parameterized join tree
--
diff --git a/src/test/regress/expected/stats_ext.out b/src/test/regress/expected/stats_ext.out
index 8c4da955084..7678744181c 100644
--- a/src/test/regress/expected/stats_ext.out
+++ b/src/test/regress/expected/stats_ext.out
@@ -1322,19 +1322,19 @@ SELECT * FROM check_estimated_rows('SELECT * FROM functional_dependencies WHERE
SELECT * FROM check_estimated_rows('SELECT * FROM functional_dependencies WHERE (a = 1 OR a = 51) AND b = ''1''');
estimated | actual
-----------+--------
- 99 | 100
+ 100 | 100
(1 row)
SELECT * FROM check_estimated_rows('SELECT * FROM functional_dependencies WHERE (a = 1 OR a = 51) AND (b = ''1'' OR b = ''2'')');
estimated | actual
-----------+--------
- 99 | 100
+ 100 | 100
(1 row)
SELECT * FROM check_estimated_rows('SELECT * FROM functional_dependencies WHERE (a = 1 OR a = 2 OR a = 51 OR a = 52) AND (b = ''1'' OR b = ''2'')');
estimated | actual
-----------+--------
- 197 | 200
+ 200 | 200
(1 row)
-- OR clauses referencing different attributes are incompatible
@@ -1664,19 +1664,19 @@ SELECT * FROM check_estimated_rows('SELECT * FROM functional_dependencies WHERE
SELECT * FROM check_estimated_rows('SELECT * FROM functional_dependencies WHERE ((a * 2) = 2 OR (a * 2) = 102) AND upper(b) = ''1''');
estimated | actual
-----------+--------
- 99 | 100
+ 100 | 100
(1 row)
SELECT * FROM check_estimated_rows('SELECT * FROM functional_dependencies WHERE ((a * 2) = 2 OR (a * 2) = 102) AND (upper(b) = ''1'' OR upper(b) = ''2'')');
estimated | actual
-----------+--------
- 99 | 100
+ 100 | 100
(1 row)
SELECT * FROM check_estimated_rows('SELECT * FROM functional_dependencies WHERE ((a * 2) = 2 OR (a * 2) = 4 OR (a * 2) = 102 OR (a * 2) = 104) AND (upper(b) = ''1'' OR upper(b) = ''2'')');
estimated | actual
-----------+--------
- 197 | 200
+ 200 | 200
(1 row)
-- OR clauses referencing different attributes
diff --git a/src/test/regress/expected/tidscan.out b/src/test/regress/expected/tidscan.out
index f133b5a4ac7..0f6d3d323d4 100644
--- a/src/test/regress/expected/tidscan.out
+++ b/src/test/regress/expected/tidscan.out
@@ -43,11 +43,12 @@ SELECT ctid, * FROM tidscan WHERE '(0,1)' = ctid;
-- OR'd clauses
EXPLAIN (COSTS OFF)
SELECT ctid, * FROM tidscan WHERE ctid = '(0,2)' OR '(0,1)' = ctid;
- QUERY PLAN
---------------------------------------------------------------
+ QUERY PLAN
+------------------------------------------------------------
Tid Scan on tidscan
- TID Cond: ((ctid = '(0,2)'::tid) OR ('(0,1)'::tid = ctid))
-(2 rows)
+ TID Cond: (ctid = ANY ('{"(0,2)","(0,1)"}'::tid[]))
+ Filter: ((ctid = '(0,2)'::tid) OR ('(0,1)'::tid = ctid))
+(3 rows)
SELECT ctid, * FROM tidscan WHERE ctid = '(0,2)' OR '(0,1)' = ctid;
ctid | id
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 8bfe3b7ba67..608b9ae7b6e 100644
--- a/src/test/regress/sql/join.sql
+++ b/src/test/regress/sql/join.sql
@@ -1409,6 +1409,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/test/regress/sql/partition_prune.sql b/src/test/regress/sql/partition_prune.sql
index a09b27d820c..1511c99801e 100644
--- a/src/test/regress/sql/partition_prune.sql
+++ b/src/test/regress/sql/partition_prune.sql
@@ -21,6 +21,7 @@ explain (costs off) select * from lp where a is not null;
explain (costs off) select * from lp where a is null;
explain (costs off) select * from lp where a = 'a' or a = 'c';
explain (costs off) select * from lp where a is not null and (a = 'a' or a = 'c');
+
explain (costs off) select * from lp where a <> 'g';
explain (costs off) select * from lp where a <> 'a' and a <> 'd';
explain (costs off) select * from lp where a not in ('a', 'd');
diff --git a/src/tools/pgindent/typedefs.list b/src/tools/pgindent/typedefs.list
index 4f57078d133..7278d047c8c 100644
--- a/src/tools/pgindent/typedefs.list
+++ b/src/tools/pgindent/typedefs.list
@@ -1714,6 +1714,7 @@ NumericVar
OM_uint32
OP
OSAPerGroupState
+OrClauseGroup
OSAPerQueryState
OSInfo
OSSLCipher
--
2.39.3 (Apple Git-145)
view thread (41+ messages) latest in thread
reply
Reply instructions:
You may reply publicly to this message via plain-text email
using any one of the following methods:
* Reply to all the recipients using the --to and --cc options:
reply via email
To: [email protected]
Cc: [email protected], [email protected], [email protected], [email protected], [email protected], [email protected], [email protected], [email protected], [email protected], [email protected], [email protected], [email protected]
Subject: Re: POC, WIP: OR-clause support for indexes
In-Reply-To: <CAPpHfduah1PLzajBJFDmp7+MZuaWYpie2p+GsV0r03fcGghQ-g@mail.gmail.com>
* Save the following mbox file, import it into your mail client,
and reply-to-all from there: mbox
This inbox is served by agora; see mirroring instructions
for how to clone and mirror all data and code used for this inbox