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

From: Alena Rybakina <[email-masked]>
Date: Thu, 30 Nov 2023 13:57:26 +0300

On 30.11.2023 11:00, Alena Rybakina wrote:
> Hi!
>
>>
>>> Honestly, it seems very hard to avoid the conclusion that this
>>> transformation is being done at too early a stage. Parse analysis is
>>> not the time to try to do query optimization. I can't really believe
>>> that there's a way to produce a committable patch along these lines.
>>> Ideally, a transformation like this should be done after we know what
>>> plan shape we're using (or considering using), so that we can make
>>> cost-based decisions about whether to transform or not. But at the
>>> very least it should happen somewhere in the planner. There's really
>>> no justification for parse analysis rewriting the SQL that the user
>>> entered.
>>
>> Here, we assume that array operation is generally better than many ORs.
>> As a result, it should be more effective to make OR->ANY 
>> transformation in the parser (it is a relatively lightweight 
>> operation here) and, as a second phase, decompose that in the optimizer.
>> We implemented earlier prototypes in different places of the 
>> optimizer, and I'm convinced that only this approach resolves the 
>> issues we found.
>> Does this approach look weird? Maybe. We can debate it in this thread.
>
> I think this is incorrect, and the example of A. Korotkov confirms 
> this. If we perform the conversion at the parsing stage, we will skip 
> the more important conversion using OR expressions. I'll show you in 
> the example below.
>
> First of all, I will describe my idea to combine two approaches to 
> obtaining plans with OR to ANY transformation and ANY to OR 
> transformation. I think they are both good, and we can't work with 
> just one of them, we should consider both the option of OR 
> expressions, and with ANY.
>

Just in case, I have attached a patch or->any transformation where this 
happens at the index creation stage.

I get diff file during make check, but judging by the changes, it shows 
that the transformation is going well. I also attached it.

-- 
Regards,
Alena Rybakina
Postgres Professional
From 9f75b58525b4892db2c360401771f69599ed21c8 Mon Sep 17 00:00:00 2001
From: Alena Rybakina <[email-masked]>
Date: Wed, 29 Nov 2023 18:58:55 +0300
Subject: [PATCH] Transform OR clause to ANY expressions.

Replace (X=N1) OR (X=N2) ... with X = ANY(N1, N2) on the preliminary stage of
optimization when we are still working with a tree expression.
Sometimes it can lead to not optimal plan. But we think it is better to have
array of elements instead of a lot of OR clauses. Here is a room for further
optimizations on decomposing that array into more optimal parts.

---
 src/backend/nodes/queryjumblefuncs.c          |  30 ++
 src/backend/optimizer/path/indxpath.c         | 394 +++++++++++++++++-
 src/backend/utils/misc/guc_tables.c           |  10 +
 src/backend/utils/misc/postgresql.conf.sample |   1 +
 src/include/nodes/queryjumble.h               |   1 +
 src/include/optimizer/paths.h                 |   1 +
 src/test/regress/expected/create_index.out    | 120 ++++++
 src/test/regress/expected/guc.out             |   3 +-
 src/test/regress/expected/join.out            |  48 +++
 src/test/regress/expected/partition_prune.out | 179 ++++++++
 src/test/regress/expected/sysviews.out        |   3 +-
 src/test/regress/expected/tidscan.out         |  17 +
 src/test/regress/sql/create_index.sql         |  32 ++
 src/test/regress/sql/join.sql                 |  10 +
 src/test/regress/sql/partition_prune.sql      |  22 +
 src/test/regress/sql/tidscan.sql              |   6 +
 src/tools/pgindent/typedefs.list              |   1 +
 17 files changed, 875 insertions(+), 3 deletions(-)

diff --git a/src/backend/nodes/queryjumblefuncs.c b/src/backend/nodes/queryjumblefuncs.c
index 281907a4d83..c98fda73d17 100644
--- a/src/backend/nodes/queryjumblefuncs.c
+++ b/src/backend/nodes/queryjumblefuncs.c
@@ -283,6 +283,36 @@ _jumbleNode(JumbleState *jstate, Node *node)
 	}
 }
 
+JumbleState *
+JumbleExpr(Expr *expr, uint64 *queryId)
+{
+	JumbleState *jstate = NULL;
+
+	Assert(queryId != NULL);
+
+	jstate = (JumbleState *) palloc(sizeof(JumbleState));
+
+	/* Set up workspace for query jumbling */
+	jstate->jumble = (unsigned char *) palloc(JUMBLE_SIZE);
+	jstate->jumble_len = 0;
+	jstate->clocations_buf_size = 32;
+	jstate->clocations = (LocationLen *)
+		palloc(jstate->clocations_buf_size * sizeof(LocationLen));
+	jstate->clocations_count = 0;
+	jstate->highest_extern_param_id = 0;
+
+	/* Compute query ID */
+	_jumbleNode(jstate, (Node *) expr);
+	*queryId = DatumGetUInt64(hash_any_extended(jstate->jumble,
+												jstate->jumble_len,
+												0));
+
+	if (*queryId == UINT64CONST(0))
+		*queryId = UINT64CONST(1);
+
+	return jstate;
+}
+
 static void
 _jumbleList(JumbleState *jstate, Node *node)
 {
diff --git a/src/backend/optimizer/path/indxpath.c b/src/backend/optimizer/path/indxpath.c
index 03a5fbdc6dc..acf4937db01 100644
--- a/src/backend/optimizer/path/indxpath.c
+++ b/src/backend/optimizer/path/indxpath.c
@@ -34,7 +34,12 @@
 #include "optimizer/restrictinfo.h"
 #include "utils/lsyscache.h"
 #include "utils/selfuncs.h"
-
+#include "parser/parse_coerce.h"
+#include "common/hashfn.h"
+#include "catalog/pg_operator.h"
+#include "nodes/queryjumble.h"
+#include "utils/syscache.h"
+#include "catalog/namespace.h"
 
 /* XXX see PartCollMatchesExprColl */
 #define IndexCollMatchesExprColl(idxcollation, exprcollation) \
@@ -193,6 +198,390 @@ static bool ec_member_matches_indexcol(PlannerInfo *root, RelOptInfo *rel,
 									   EquivalenceClass *ec, EquivalenceMember *em,
 									   void *arg);
 
+bool		enable_or_transformation = true;
+typedef struct OrClauseGroupKey
+{
+	Expr   *expr; /* Pointer to the expression tree which has been a source for
+					the hashkey value */
+	Oid		opno;
+	Oid		exprtype;
+} OrClauseGroupKey;
+
+typedef struct OrClauseGroupEntry
+{
+	OrClauseGroupKey key;
+	Node		   *node;
+	List		   *consts;
+	Oid				collation;
+	RestrictInfo   *rinfo;
+	List 		   *exprs;
+} OrClauseGroupEntry;
+
+/*
+ * Hash function that's compatible with guc_name_compare
+ */
+static uint32
+orclause_hash(const void *data, Size keysize)
+{
+	OrClauseGroupKey   *key = (OrClauseGroupKey *) data;
+	uint64				hash;
+
+	(void) JumbleExpr(key->expr, &hash);
+	hash = ((uint64) key->opno + (uint64) key->exprtype) % UINT64_MAX;
+	return hash;
+}
+
+static void *
+orclause_keycopy(void *dest, const void *src, Size keysize)
+{
+	OrClauseGroupKey *src_key = (OrClauseGroupKey *) src;
+	OrClauseGroupKey *dst_key = (OrClauseGroupKey *) dest;
+
+	Assert(sizeof(OrClauseGroupKey) == keysize);
+
+	dst_key->expr = src_key->expr;
+	dst_key->opno = src_key->opno;
+	dst_key->exprtype = src_key->exprtype;
+	return dst_key;
+}
+
+/*
+ * Dynahash match function to use in guc_hashtab
+ */
+static int
+orclause_match(const void *data1, const void *data2, Size keysize)
+{
+	OrClauseGroupKey   *key1 = (OrClauseGroupKey *) data1;
+	OrClauseGroupKey   *key2 = (OrClauseGroupKey *) data2;
+
+	Assert(sizeof(OrClauseGroupKey) == keysize);
+
+	if (key1->opno == key2->opno && key1->exprtype == key2->exprtype &&
+		equal(key1->expr, key2->expr))
+		return 0;
+
+	return 1;
+}
+
+/*
+ * Pass through baserestrictinfo clauses and try to convert OR clauses into IN
+ * Return a modified clause list or just the same baserestrictinfo, if no
+ * changes have made.
+ * XXX: do not change source list of clauses at all.
+ */
+static List *
+transform_ors(PlannerInfo *root, List *baserestrictinfo)
+{
+	ListCell   *lc;
+	List	   *modified_rinfo = NIL;
+	bool		something_changed = false;
+
+	/*
+	 * Complexity of a clause could be arbitrarily sophisticated. Here, we will
+	 * look up only on the top level of clause list.
+	 * XXX: It is substantiated? Could we change something here?
+	 */
+	foreach (lc, baserestrictinfo)
+	{
+		RestrictInfo   *rinfo = lfirst_node(RestrictInfo, lc);
+		RestrictInfo   *rinfo_base = copyObject(rinfo);
+		List		   *or_list = NIL;
+		ListCell	   *lc_eargs,
+					   *lc_rargs;
+		bool			change_apply = false;
+		HASHCTL			info;
+		HTAB 		   *or_group_htab = NULL;
+		int 			len_ors;
+		HASH_SEQ_STATUS		hash_seq;
+		OrClauseGroupEntry *gentry;
+
+		if (!enable_or_transformation || !restriction_is_or_clause(rinfo))
+		{
+			/* Add a clause without changes */
+			modified_rinfo = lappend(modified_rinfo, rinfo);
+			continue;
+		}
+
+		len_ors = ((BoolExpr *) rinfo->clause)->args? list_length(((BoolExpr *) rinfo->clause)->args) : 0;
+
+		if (len_ors < 2)
+		{
+			/* Add a clause without changes */
+			modified_rinfo = lappend(modified_rinfo, rinfo);
+			continue;
+		}
+
+		MemSet(&info, 0, sizeof(info));
+		info.keysize = sizeof(OrClauseGroupKey);
+		info.entrysize = sizeof(OrClauseGroupEntry);
+		info.hash = orclause_hash;
+		info.keycopy = orclause_keycopy;
+		info.match = orclause_match;
+		or_group_htab = hash_create("OR Groups",
+									len_ors,
+									&info,
+									HASH_ELEM | HASH_FUNCTION | HASH_COMPARE | HASH_KEYCOPY);
+
+		/*
+		 * NOTE:
+		 * It is an OR-clause. So, rinfo->orclause is a BoolExpr node, contains
+		 * a list of sub-restrictinfo args, and rinfo->clause - which is the
+		 * same expression, made from bare clauses. To not break selectivity
+		 * caches and other optimizations, use both:
+		 * - use rinfos from orclause if no transformation needed
+		 * - use  bare quals from rinfo->clause in the case of transformation,
+		 * to create new RestrictInfo: in this case we have no options to avoid
+		 * selectivity estimation procedure.
+		 */
+		forboth(lc_eargs, ((BoolExpr *) rinfo->clause)->args,
+				lc_rargs, ((BoolExpr *) rinfo->orclause)->args)
+		{
+			Expr			   *or_qual = (Expr *) lfirst(lc_eargs);
+			RestrictInfo	   *sub_rinfo;
+			Node			   *const_expr;
+			Node			   *nconst_expr;
+			OrClauseGroupKey		hashkey;
+			bool found = false;
+
+			/* It may be one more boolean expression, skip it for now */
+			if (!IsA(lfirst(lc_rargs), RestrictInfo))
+			{
+				or_list = lappend(or_list, (void *) or_qual);
+				continue;
+			}
+
+			sub_rinfo = lfirst_node(RestrictInfo, lc_rargs);
+
+			/* Check: it is an expr of the form 'F(x) oper ConstExpr' */
+			if (!IsA(or_qual, OpExpr) ||
+				!(bms_is_empty(sub_rinfo->left_relids) ^
+				bms_is_empty(sub_rinfo->right_relids)) ||
+				contain_volatile_functions((Node *) or_qual))
+			{
+				/* Again, it's not the expr we can transform */
+				or_list = lappend(or_list, (void *) or_qual);
+				continue;
+			}
+
+			/* Get pointers to constant and expression sides of the clause */
+			const_expr =bms_is_empty(sub_rinfo->left_relids) ?
+												get_leftop(sub_rinfo->clause) :
+												get_rightop(sub_rinfo->clause);
+			nconst_expr = bms_is_empty(sub_rinfo->left_relids) ?
+												get_rightop(sub_rinfo->clause) :
+												get_leftop(sub_rinfo->clause);
+
+			if (!op_mergejoinable(((OpExpr *) sub_rinfo->clause)->opno, exprType(nconst_expr)))
+			{
+				/* And again, filter out non-equality operators */
+				or_list = lappend(or_list, (void *) or_qual);
+				continue;
+			}
+
+			/*
+			 * At this point we definitely have a transformable clause.
+			 * Classify it and add into specific group of clauses, or create new
+			 * group.
+			 */
+			hashkey.expr = (Expr *) nconst_expr;
+			hashkey.opno = ((OpExpr *) or_qual)->opno;
+			hashkey.exprtype = exprType(nconst_expr);
+			gentry = hash_search(or_group_htab, &hashkey, HASH_ENTER, &found);
+
+			if (unlikely(found))
+			{
+				gentry->consts = lappend(gentry->consts, const_expr);
+				gentry->exprs = lappend(gentry->exprs, or_qual);
+			}
+			else
+			{
+				gentry->node = nconst_expr;
+				gentry->consts = list_make1(const_expr);
+				gentry->exprs = list_make1(or_qual);
+				gentry->rinfo = sub_rinfo;
+				gentry->collation = exprInputCollation((Node *)sub_rinfo->clause);
+			}
+		}
+
+		if (list_length(or_list) == len_ors)
+		{
+			/*
+			* No any transformations possible with this list of arguments. Here we
+			* already made all underlying transformations. Thus, just return the
+			* transformed bool expression.
+			*/
+			modified_rinfo = lappend(modified_rinfo, rinfo);
+			continue;
+		}
+
+		if (!or_group_htab && hash_get_num_entries(or_group_htab) < 1)
+		{
+			/*
+			 * No any transformations possible with this rinfo, just add itself
+			 * to the list and go further.
+			 */
+			modified_rinfo = lappend(modified_rinfo, rinfo);
+			continue;
+		}
+
+		hash_seq_init(&hash_seq, or_group_htab);
+
+		/* Let's convert each group of clauses to an IN operation. */
+
+		/*
+		* Go through the list of groups and convert each, where number of
+		* consts more than 1. trivial groups move to OR-list again
+		*/
+
+		while ((gentry = (OrClauseGroupEntry *) hash_seq_search(&hash_seq)) != NULL)
+		{
+			Oid				    scalar_type;
+			Oid					array_type;
+
+			Assert(list_length(gentry->consts) > 0);
+			Assert(list_length(gentry->exprs) == list_length(gentry->consts));
+
+			if (list_length(gentry->consts) == 1)
+			{
+				/*
+				* Only one element in the class. Return rinfo into the BoolExpr
+				* args list unchanged.
+				*/
+				list_free(gentry->consts);
+				or_list = list_concat(or_list, gentry->exprs);
+				continue;
+			}
+
+			/*
+			* Do the transformation.
+			*
+			* First of all, try to select a common type for the array elements.
+			* Note that since the LHS' type is first in the list, it will be
+			* preferred when there is doubt (eg, when all the RHS items are
+			* unknown literals).
+			*
+			* Note: use list_concat here not lcons, to avoid damaging rnonvars.
+			*
+			* As a source of insides, use make_scalar_array_op()
+			*/
+			scalar_type = gentry->key.exprtype;
+
+			if (scalar_type != RECORDOID && OidIsValid(scalar_type))
+				array_type = get_array_type(scalar_type);
+			else
+				array_type = InvalidOid;
+
+			if (array_type != InvalidOid && scalar_type != InvalidOid)
+			{
+				/*
+				* OK: coerce all the right-hand non-Var inputs to the common
+				* type and build an ArrayExpr for them.
+				*/
+				List	   *aexprs = NULL;
+				ArrayExpr  *newa = NULL;
+				ScalarArrayOpExpr *saopexpr = NULL;
+				HeapTuple			opertup;
+				Form_pg_operator	operform;
+				List			   *namelist = NIL;
+
+				aexprs = gentry->consts;
+
+				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;
+
+				opertup = SearchSysCache1(OPEROID,
+									  ObjectIdGetDatum(gentry->key.opno));
+
+				if (!HeapTupleIsValid(opertup))
+					elog(ERROR, "cache lookup failed for operator %u",
+						gentry->key.opno);
+
+				operform = (Form_pg_operator) GETSTRUCT(opertup);
+				if (!OperatorIsVisible(gentry->key.opno))
+					namelist = lappend(namelist, makeString(get_namespace_name(operform->oprnamespace)));
+
+				namelist = lappend(namelist, makeString(pstrdup(NameStr(operform->oprname))));
+				ReleaseSysCache(opertup);
+
+				saopexpr = makeNode(ScalarArrayOpExpr);
+				saopexpr->opno = ((OpExpr *) gentry->rinfo->clause)->opno;
+				saopexpr->useOr = true;
+				saopexpr->inputcollid = gentry->collation;
+				saopexpr->args = list_make2(gentry->node, newa);
+				saopexpr->location = -1;
+
+
+				or_list = lappend(or_list, (void *) saopexpr);
+
+				something_changed = true;
+				change_apply = true;
+
+			}
+			else
+			{
+				list_free(gentry->consts);
+				or_list = lappend(or_list, (void *) gentry->rinfo->clause);
+			}
+			hash_search(or_group_htab, &gentry->key, HASH_REMOVE, NULL);
+		}
+
+		hash_destroy(or_group_htab);
+
+		if (!change_apply)
+		{
+			/*
+			 * Each group contains only one element - use rinfo as is.
+			 */
+			modified_rinfo = lappend(modified_rinfo, rinfo);
+			list_free(or_list);
+			continue;
+		}
+
+		/*
+		 * Make a new version of the restriction. Remember source restriction
+		 * can be used in another path (SeqScan, for example).
+		 */
+
+		/* One more trick: assemble correct clause */
+		rinfo = make_restrictinfo(root,
+				  list_length(or_list) > 1 ? makeBoolExpr(OR_EXPR, or_list, ((BoolExpr *) rinfo->clause)->location) :
+											 linitial(or_list),
+				  rinfo->is_pushed_down,
+				  rinfo->has_clone,
+				  rinfo->is_clone,
+				  rinfo->pseudoconstant,
+				  rinfo->security_level,
+				  rinfo->required_relids,
+				  rinfo->incompatible_relids,
+				  rinfo->outer_relids);
+		rinfo->eval_cost=rinfo_base->eval_cost;
+		rinfo->norm_selec=rinfo_base->norm_selec;
+		rinfo->outer_selec=rinfo_base->outer_selec;
+		rinfo->left_bucketsize=rinfo_base->left_bucketsize;
+		rinfo->right_bucketsize=rinfo_base->right_bucketsize;
+		rinfo->left_mcvfreq=rinfo_base->left_mcvfreq;
+		rinfo->right_mcvfreq=rinfo_base->right_mcvfreq;
+		modified_rinfo = lappend(modified_rinfo, rinfo);
+		something_changed = true;
+	}
+
+	/*
+	 * Check if transformation has made. If nothing changed - return
+	 * baserestrictinfo as is.
+	 */
+	if (something_changed)
+	{
+		return modified_rinfo;
+	}
+
+	list_free(modified_rinfo);
+	return baserestrictinfo;
+}
 
 /*
  * create_index_paths()
@@ -719,6 +1108,9 @@ get_index_paths(PlannerInfo *root, RelOptInfo *rel,
 	bool		skip_lower_saop = false;
 	ListCell   *lc;
 
+	if (rel->reloptkind == RELOPT_BASEREL)
+		rel->baserestrictinfo = transform_ors(root, rel->baserestrictinfo);
+
 	/*
 	 * Build simple index paths using the clauses.  Allow ScalarArrayOpExpr
 	 * clauses only if the index AM supports them natively, and skip any such
diff --git a/src/backend/utils/misc/guc_tables.c b/src/backend/utils/misc/guc_tables.c
index b764ef69980..2ca8a21caf0 100644
--- a/src/backend/utils/misc/guc_tables.c
+++ b/src/backend/utils/misc/guc_tables.c
@@ -1048,6 +1048,16 @@ struct config_bool ConfigureNamesBool[] =
 		true,
 		NULL, NULL, NULL
 	},
+	{
+		{"enable_or_transformation", PGC_USERSET, QUERY_TUNING_OTHER,
+			gettext_noop("Transform a sequence of OR clauses to an IN expression."),
+			gettext_noop("The planner will replace clauses like 'x=c1 OR x=c2 .."
+						 "to the clause 'x IN (c1,c2,...)'")
+		},
+		&enable_or_transformation,
+		true,
+		NULL, NULL, NULL
+	},
 	{
 		/*
 		 * Not for general use --- used by SET SESSION AUTHORIZATION and SET
diff --git a/src/backend/utils/misc/postgresql.conf.sample b/src/backend/utils/misc/postgresql.conf.sample
index e48c066a5b1..f31778074b4 100644
--- a/src/backend/utils/misc/postgresql.conf.sample
+++ b/src/backend/utils/misc/postgresql.conf.sample
@@ -370,6 +370,7 @@
 
 # - Planner Method Configuration -
 
+#enable_or_transformation = on
 #enable_async_append = on
 #enable_bitmapscan = on
 #enable_gathermerge = on
diff --git a/src/include/nodes/queryjumble.h b/src/include/nodes/queryjumble.h
index 0769081c7ab..4aaa31aa80e 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 *queryId);
 extern void EnableQueryId(void);
 
 extern PGDLLIMPORT bool query_id_enabled;
diff --git a/src/include/optimizer/paths.h b/src/include/optimizer/paths.h
index 9e7408c7ecf..f8be9f9f605 100644
--- a/src/include/optimizer/paths.h
+++ b/src/include/optimizer/paths.h
@@ -24,6 +24,7 @@ extern PGDLLIMPORT bool enable_geqo;
 extern PGDLLIMPORT int geqo_threshold;
 extern PGDLLIMPORT int min_parallel_table_scan_size;
 extern PGDLLIMPORT int min_parallel_index_scan_size;
+extern PGDLLIMPORT bool enable_or_transformation;
 
 /* Hook for plugins to get control in set_rel_pathlist() */
 typedef void (*set_rel_pathlist_hook_type) (PlannerInfo *root,
diff --git a/src/test/regress/expected/create_index.out b/src/test/regress/expected/create_index.out
index acfd9d1f4f7..5a73c8f51a6 100644
--- a/src/test/regress/expected/create_index.out
+++ b/src/test/regress/expected/create_index.out
@@ -1883,6 +1883,126 @@ SELECT count(*) FROM tenk1
     10
 (1 row)
 
+SET enable_or_transformation = on;
+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 (ARRAY[1, 3, 42])))
+(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 (ARRAY[42, 99])))
+         ->  BitmapAnd
+               ->  Bitmap Index Scan on tenk1_hundred
+                     Index Cond: (hundred = 42)
+               ->  Bitmap Index Scan on tenk1_thous_tenthous
+                     Index Cond: (thousand = ANY (ARRAY[42, 99]))
+(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 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) AND (tenthous = 1))
+                     ->  Bitmap Index Scan on tenk1_thous_tenthous
+                           Index Cond: ((thousand = 42) AND (tenthous = 3))
+               ->  Bitmap Index Scan on tenk1_thous_tenthous
+                     Index Cond: (thousand = 41)
+(11 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 = 99) AND (tenthous = 2)) OR (thousand = ANY (ARRAY[42, 41]))))
+         ->  BitmapAnd
+               ->  Bitmap Index Scan on tenk1_hundred
+                     Index Cond: (hundred = 42)
+               ->  BitmapOr
+                     ->  Bitmap Index Scan on tenk1_thous_tenthous
+                           Index Cond: ((thousand = 99) AND (tenthous = 2))
+                     ->  Bitmap Index Scan on tenk1_thous_tenthous
+                           Index Cond: (thousand = ANY (ARRAY[42, 41]))
+(11 rows)
+
+SELECT count(*) FROM tenk1
+  WHERE hundred = 42 AND (thousand = 42 OR thousand = 41 OR thousand = 99 AND tenthous = 2);
+ count 
+-------
+    10
+(1 row)
+
+RESET enable_or_transformation;
 --
 -- Check behavior with duplicate index column contents
 --
diff --git a/src/test/regress/expected/guc.out b/src/test/regress/expected/guc.out
index 127c9532976..0f2b1b16200 100644
--- a/src/test/regress/expected/guc.out
+++ b/src/test/regress/expected/guc.out
@@ -861,7 +861,8 @@ SELECT name FROM tab_settings_flags
            name            
 ---------------------------
  default_statistics_target
-(1 row)
+ enable_or_transformation
+(2 rows)
 
 -- Runtime-computed GUCs should be part of the preset category.
 SELECT name FROM tab_settings_flags
diff --git a/src/test/regress/expected/join.out b/src/test/regress/expected/join.out
index 2c73270143b..54b8fdb2e88 100644
--- a/src/test/regress/expected/join.out
+++ b/src/test/regress/expected/join.out
@@ -4233,6 +4233,54 @@ select * from tenk1 a join tenk1 b on
                            Index Cond: (unique2 = 7)
 (19 rows)
 
+SET enable_or_transformation = on;
+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: ((unique2 = ANY (ARRAY[3, 7])) OR (unique1 = 1))
+               ->  BitmapOr
+                     ->  Bitmap Index Scan on tenk1_unique2
+                           Index Cond: (unique2 = ANY (ARRAY[3, 7]))
+                     ->  Bitmap Index Scan on tenk1_unique1
+                           Index Cond: (unique1 = 1)
+(17 rows)
+
+explain (costs off)
+select * from tenk1 a join tenk1 b on
+  (a.unique1 < 20 or a.unique1 = 3 or a.unique1 = 1 and b.unique1 = 2) or
+  ((a.unique2 = 3 or a.unique2 = 7) and b.hundred = 4);
+                                                                         QUERY PLAN                                                                          
+-------------------------------------------------------------------------------------------------------------------------------------------------------------
+ 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 = ANY (ARRAY[3, 1])) OR (unique2 = ANY (ARRAY[3, 7])))
+               ->  BitmapOr
+                     ->  Bitmap Index Scan on tenk1_unique1
+                           Index Cond: (unique1 < 20)
+                     ->  Bitmap Index Scan on tenk1_unique1
+                           Index Cond: (unique1 = ANY (ARRAY[3, 1]))
+                     ->  Bitmap Index Scan on tenk1_unique2
+                           Index Cond: (unique2 = ANY (ARRAY[3, 7]))
+(13 rows)
+
+RESET enable_or_transformation;
 --
 -- test placement of movable quals in a parameterized join tree
 --
diff --git a/src/test/regress/expected/partition_prune.out b/src/test/regress/expected/partition_prune.out
index 9a4c48c0556..38b4ec98403 100644
--- a/src/test/regress/expected/partition_prune.out
+++ b/src/test/regress/expected/partition_prune.out
@@ -101,6 +101,28 @@ explain (costs off) select * from lp where a is not null and (a = 'a' or a = 'c'
          Filter: ((a IS NOT NULL) AND ((a = 'a'::bpchar) OR (a = 'c'::bpchar)))
 (5 rows)
 
+SET enable_or_transformation = on;
+explain (costs off) select * from lp where a = 'a' or a = 'c';
+                        QUERY PLAN                        
+----------------------------------------------------------
+ Append
+   ->  Seq Scan on lp_ad lp_1
+         Filter: ((a = 'a'::bpchar) OR (a = 'c'::bpchar))
+   ->  Seq Scan on lp_bc lp_2
+         Filter: ((a = 'a'::bpchar) OR (a = 'c'::bpchar))
+(5 rows)
+
+explain (costs off) select * from lp where a is not null and (a = 'a' or a = 'c');
+                                   QUERY PLAN                                   
+--------------------------------------------------------------------------------
+ Append
+   ->  Seq Scan on lp_ad lp_1
+         Filter: ((a IS NOT NULL) AND ((a = 'a'::bpchar) OR (a = 'c'::bpchar)))
+   ->  Seq Scan on lp_bc lp_2
+         Filter: ((a IS NOT NULL) AND ((a = 'a'::bpchar) OR (a = 'c'::bpchar)))
+(5 rows)
+
+RESET enable_or_transformation;
 explain (costs off) select * from lp where a <> 'g';
              QUERY PLAN             
 ------------------------------------
@@ -671,6 +693,163 @@ explain (costs off) select * from rlp where (a = 1 and a = 3) or (a > 1 and a =
          Filter: (((a = 1) AND (a = 3)) OR ((a > 1) AND (a = 15)))
 (11 rows)
 
+SET enable_or_transformation = on;
+explain (costs off) select * from rlp where a = 1 or a = 7;
+           QUERY PLAN           
+--------------------------------
+ Seq Scan on rlp2 rlp
+   Filter: ((a = 1) OR (a = 7))
+(2 rows)
+
+explain (costs off) select * from rlp where a = 1 or b = 'ab';
+                      QUERY PLAN                       
+-------------------------------------------------------
+ Append
+   ->  Seq Scan on rlp1 rlp_1
+         Filter: ((a = 1) OR ((b)::text = 'ab'::text))
+   ->  Seq Scan on rlp2 rlp_2
+         Filter: ((a = 1) OR ((b)::text = 'ab'::text))
+   ->  Seq Scan on rlp3abcd rlp_3
+         Filter: ((a = 1) OR ((b)::text = 'ab'::text))
+   ->  Seq Scan on rlp4_1 rlp_4
+         Filter: ((a = 1) OR ((b)::text = 'ab'::text))
+   ->  Seq Scan on rlp4_2 rlp_5
+         Filter: ((a = 1) OR ((b)::text = 'ab'::text))
+   ->  Seq Scan on rlp4_default rlp_6
+         Filter: ((a = 1) OR ((b)::text = 'ab'::text))
+   ->  Seq Scan on rlp5_1 rlp_7
+         Filter: ((a = 1) OR ((b)::text = 'ab'::text))
+   ->  Seq Scan on rlp5_default rlp_8
+         Filter: ((a = 1) OR ((b)::text = 'ab'::text))
+   ->  Seq Scan on rlp_default_10 rlp_9
+         Filter: ((a = 1) OR ((b)::text = 'ab'::text))
+   ->  Seq Scan on rlp_default_30 rlp_10
+         Filter: ((a = 1) OR ((b)::text = 'ab'::text))
+   ->  Seq Scan on rlp_default_null rlp_11
+         Filter: ((a = 1) OR ((b)::text = 'ab'::text))
+   ->  Seq Scan on rlp_default_default rlp_12
+         Filter: ((a = 1) OR ((b)::text = 'ab'::text))
+(25 rows)
+
+explain (costs off) select * from rlp where a > 20 and a < 27;
+               QUERY PLAN                
+-----------------------------------------
+ Append
+   ->  Seq Scan on rlp4_1 rlp_1
+         Filter: ((a > 20) AND (a < 27))
+   ->  Seq Scan on rlp4_2 rlp_2
+         Filter: ((a > 20) AND (a < 27))
+(5 rows)
+
+explain (costs off) select * from rlp where a = 29;
+          QUERY PLAN          
+------------------------------
+ Seq Scan on rlp4_default rlp
+   Filter: (a = 29)
+(2 rows)
+
+explain (costs off) select * from rlp where a >= 29;
+                 QUERY PLAN                  
+---------------------------------------------
+ Append
+   ->  Seq Scan on rlp4_default rlp_1
+         Filter: (a >= 29)
+   ->  Seq Scan on rlp5_1 rlp_2
+         Filter: (a >= 29)
+   ->  Seq Scan on rlp5_default rlp_3
+         Filter: (a >= 29)
+   ->  Seq Scan on rlp_default_30 rlp_4
+         Filter: (a >= 29)
+   ->  Seq Scan on rlp_default_default rlp_5
+         Filter: (a >= 29)
+(11 rows)
+
+explain (costs off) select * from rlp where a < 1 or (a > 20 and a < 25);
+                      QUERY PLAN                      
+------------------------------------------------------
+ Append
+   ->  Seq Scan on rlp1 rlp_1
+         Filter: ((a < 1) OR ((a > 20) AND (a < 25)))
+   ->  Seq Scan on rlp4_1 rlp_2
+         Filter: ((a < 1) OR ((a > 20) AND (a < 25)))
+(5 rows)
+
+explain (costs off) select * from rlp where a = 20 or a = 40;
+               QUERY PLAN               
+----------------------------------------
+ Append
+   ->  Seq Scan on rlp4_1 rlp_1
+         Filter: ((a = 20) OR (a = 40))
+   ->  Seq Scan on rlp5_default rlp_2
+         Filter: ((a = 20) OR (a = 40))
+(5 rows)
+
+explain (costs off) select * from rlp3 where a = 20;   /* empty */
+        QUERY PLAN        
+--------------------------
+ Result
+   One-Time Filter: false
+(2 rows)
+
+explain (costs off) select * from rlp where a > 1 and a = 10;	/* only default */
+            QUERY PLAN            
+----------------------------------
+ Seq Scan on rlp_default_10 rlp
+   Filter: ((a > 1) AND (a = 10))
+(2 rows)
+
+explain (costs off) select * from rlp where a > 1 and a >=15;	/* rlp3 onwards, including default */
+                  QUERY PLAN                  
+----------------------------------------------
+ Append
+   ->  Seq Scan on rlp3abcd rlp_1
+         Filter: ((a > 1) AND (a >= 15))
+   ->  Seq Scan on rlp3efgh rlp_2
+         Filter: ((a > 1) AND (a >= 15))
+   ->  Seq Scan on rlp3nullxy rlp_3
+         Filter: ((a > 1) AND (a >= 15))
+   ->  Seq Scan on rlp3_default rlp_4
+         Filter: ((a > 1) AND (a >= 15))
+   ->  Seq Scan on rlp4_1 rlp_5
+         Filter: ((a > 1) AND (a >= 15))
+   ->  Seq Scan on rlp4_2 rlp_6
+         Filter: ((a > 1) AND (a >= 15))
+   ->  Seq Scan on rlp4_default rlp_7
+         Filter: ((a > 1) AND (a >= 15))
+   ->  Seq Scan on rlp5_1 rlp_8
+         Filter: ((a > 1) AND (a >= 15))
+   ->  Seq Scan on rlp5_default rlp_9
+         Filter: ((a > 1) AND (a >= 15))
+   ->  Seq Scan on rlp_default_30 rlp_10
+         Filter: ((a > 1) AND (a >= 15))
+   ->  Seq Scan on rlp_default_default rlp_11
+         Filter: ((a > 1) AND (a >= 15))
+(23 rows)
+
+explain (costs off) select * from rlp where a = 1 and a = 3;	/* empty */
+        QUERY PLAN        
+--------------------------
+ Result
+   One-Time Filter: false
+(2 rows)
+
+explain (costs off) select * from rlp where (a = 1 and a = 3) or (a > 1 and a = 15);
+                            QUERY PLAN                             
+-------------------------------------------------------------------
+ Append
+   ->  Seq Scan on rlp2 rlp_1
+         Filter: (((a = 1) AND (a = 3)) OR ((a > 1) AND (a = 15)))
+   ->  Seq Scan on rlp3abcd rlp_2
+         Filter: (((a = 1) AND (a = 3)) OR ((a > 1) AND (a = 15)))
+   ->  Seq Scan on rlp3efgh rlp_3
+         Filter: (((a = 1) AND (a = 3)) OR ((a > 1) AND (a = 15)))
+   ->  Seq Scan on rlp3nullxy rlp_4
+         Filter: (((a = 1) AND (a = 3)) OR ((a > 1) AND (a = 15)))
+   ->  Seq Scan on rlp3_default rlp_5
+         Filter: (((a = 1) AND (a = 3)) OR ((a > 1) AND (a = 15)))
+(11 rows)
+
+RESET enable_or_transformation;
 -- multi-column keys
 create table mc3p (a int, b int, c int) partition by range (a, abs(b), c);
 create table mc3p_default partition of mc3p default;
diff --git a/src/test/regress/expected/sysviews.out b/src/test/regress/expected/sysviews.out
index 271313ebf86..566f51df428 100644
--- a/src/test/regress/expected/sysviews.out
+++ b/src/test/regress/expected/sysviews.out
@@ -123,6 +123,7 @@ select name, setting from pg_settings where name like 'enable%';
  enable_memoize                 | on
  enable_mergejoin               | on
  enable_nestloop                | on
+ enable_or_transformation       | off
  enable_parallel_append         | on
  enable_parallel_hash           | on
  enable_partition_pruning       | on
@@ -133,7 +134,7 @@ select name, setting from pg_settings where name like 'enable%';
  enable_seqscan                 | on
  enable_sort                    | on
  enable_tidscan                 | on
-(22 rows)
+(23 rows)
 
 -- There are always wait event descriptions for various types.
 select type, count(*) > 0 as ok FROM pg_wait_events
diff --git a/src/test/regress/expected/tidscan.out b/src/test/regress/expected/tidscan.out
index f133b5a4ac7..2e12944bd13 100644
--- a/src/test/regress/expected/tidscan.out
+++ b/src/test/regress/expected/tidscan.out
@@ -56,6 +56,23 @@ SELECT ctid, * FROM tidscan WHERE ctid = '(0,2)' OR '(0,1)' = ctid;
  (0,2) |  2
 (2 rows)
 
+SET enable_or_transformation = on;
+EXPLAIN (COSTS OFF)
+SELECT ctid, * FROM tidscan WHERE ctid = '(0,2)' OR '(0,1)' = ctid;
+                          QUERY PLAN                          
+--------------------------------------------------------------
+ Tid Scan on tidscan
+   TID Cond: (ctid = ANY (ARRAY['(0,2)'::tid, '(0,1)'::tid]))
+(2 rows)
+
+SELECT ctid, * FROM tidscan WHERE ctid = '(0,2)' OR '(0,1)' = ctid;
+ ctid  | id 
+-------+----
+ (0,1) |  1
+ (0,2) |  2
+(2 rows)
+
+RESET enable_or_transformation;
 -- ctid = ScalarArrayOp - implemented as tidscan
 EXPLAIN (COSTS OFF)
 SELECT ctid, * FROM tidscan WHERE ctid = ANY(ARRAY['(0,1)', '(0,2)']::tid[]);
diff --git a/src/test/regress/sql/create_index.sql b/src/test/regress/sql/create_index.sql
index d49ce9f3007..48bb1bc0a0a 100644
--- a/src/test/regress/sql/create_index.sql
+++ b/src/test/regress/sql/create_index.sql
@@ -737,6 +737,38 @@ SELECT count(*) FROM tenk1
 SELECT count(*) FROM tenk1
   WHERE hundred = 42 AND (thousand = 42 OR thousand = 99);
 
+SET enable_or_transformation = on;
+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 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 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);
+RESET enable_or_transformation;
+
 --
 -- Check behavior with duplicate index column contents
 --
diff --git a/src/test/regress/sql/join.sql b/src/test/regress/sql/join.sql
index 8a8a63bd2f1..55d7e2ae7d6 100644
--- a/src/test/regress/sql/join.sql
+++ b/src/test/regress/sql/join.sql
@@ -1408,6 +1408,16 @@ 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);
+SET enable_or_transformation = on;
+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);
+RESET enable_or_transformation;
 
 --
 -- 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 7bf3920827f..1e270ae9c06 100644
--- a/src/test/regress/sql/partition_prune.sql
+++ b/src/test/regress/sql/partition_prune.sql
@@ -21,6 +21,12 @@ 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');
+
+SET enable_or_transformation = on;
+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');
+RESET enable_or_transformation;
+
 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');
@@ -99,6 +105,22 @@ explain (costs off) select * from rlp where a > 1 and a >=15;	/* rlp3 onwards, i
 explain (costs off) select * from rlp where a = 1 and a = 3;	/* empty */
 explain (costs off) select * from rlp where (a = 1 and a = 3) or (a > 1 and a = 15);
 
+
+SET enable_or_transformation = on;
+explain (costs off) select * from rlp where a = 1 or a = 7;
+explain (costs off) select * from rlp where a = 1 or b = 'ab';
+explain (costs off) select * from rlp where a > 20 and a < 27;
+explain (costs off) select * from rlp where a = 29;
+explain (costs off) select * from rlp where a >= 29;
+explain (costs off) select * from rlp where a < 1 or (a > 20 and a < 25);
+explain (costs off) select * from rlp where a = 20 or a = 40;
+explain (costs off) select * from rlp3 where a = 20;   /* empty */
+explain (costs off) select * from rlp where a > 1 and a = 10;	/* only default */
+explain (costs off) select * from rlp where a > 1 and a >=15;	/* rlp3 onwards, including default */
+explain (costs off) select * from rlp where a = 1 and a = 3;	/* empty */
+explain (costs off) select * from rlp where (a = 1 and a = 3) or (a > 1 and a = 15);
+RESET enable_or_transformation;
+
 -- multi-column keys
 create table mc3p (a int, b int, c int) partition by range (a, abs(b), c);
 create table mc3p_default partition of mc3p default;
diff --git a/src/test/regress/sql/tidscan.sql b/src/test/regress/sql/tidscan.sql
index 313e0fb9b67..0499bedb9eb 100644
--- a/src/test/regress/sql/tidscan.sql
+++ b/src/test/regress/sql/tidscan.sql
@@ -22,6 +22,12 @@ EXPLAIN (COSTS OFF)
 SELECT ctid, * FROM tidscan WHERE ctid = '(0,2)' OR '(0,1)' = ctid;
 SELECT ctid, * FROM tidscan WHERE ctid = '(0,2)' OR '(0,1)' = ctid;
 
+SET enable_or_transformation = on;
+EXPLAIN (COSTS OFF)
+SELECT ctid, * FROM tidscan WHERE ctid = '(0,2)' OR '(0,1)' = ctid;
+SELECT ctid, * FROM tidscan WHERE ctid = '(0,2)' OR '(0,1)' = ctid;
+RESET enable_or_transformation;
+
 -- ctid = ScalarArrayOp - implemented as tidscan
 EXPLAIN (COSTS OFF)
 SELECT ctid, * FROM tidscan WHERE ctid = ANY(ARRAY['(0,1)', '(0,2)']::tid[]);
diff --git a/src/tools/pgindent/typedefs.list b/src/tools/pgindent/typedefs.list
index dba3498a13e..c9004250a5f 100644
--- a/src/tools/pgindent/typedefs.list
+++ b/src/tools/pgindent/typedefs.list
@@ -1641,6 +1641,7 @@ NumericVar
 OM_uint32
 OP
 OSAPerGroupState
+OrClauseGroupEntry
 OSAPerQueryState
 OSInfo
 OSSLCipher
-- 
2.34.1

diff -U3 /home/alena/postgrespro__copy32/src/test/regress/expected/create_index.out /home/alena/postgrespro__copy32/src/test/regress/results/create_index.out
--- /home/alena/postgrespro__copy32/src/test/regress/expected/create_index.out	2023-11-30 13:50:34.576537110 +0300
+++ /home/alena/postgrespro__copy32/src/test/regress/results/create_index.out	2023-11-30 13:52:10.940412842 +0300
@@ -1838,18 +1838,14 @@
 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)
+   Filter: (tenthous = ANY (ARRAY[1, 3, 42]))
+   ->  Bitmap Index Scan on tenk1_thous_tenthous
+         Index Cond: (thousand = 42)
+(5 rows)
 
 SELECT * FROM tenk1
   WHERE thousand = 42 AND (tenthous = 1 OR tenthous = 3 OR tenthous = 42);
@@ -1861,20 +1857,15 @@
 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)))
-         ->  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)
-(11 rows)
+         Recheck Cond: (hundred = 42)
+         Filter: (thousand = ANY (ARRAY[42, 99]))
+         ->  Bitmap Index Scan on tenk1_hundred
+               Index Cond: (hundred = 42)
+(6 rows)
 
 SELECT count(*) FROM tenk1
   WHERE hundred = 42 AND (thousand = 42 OR thousand = 99);
@@ -1887,11 +1878,14 @@
 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 (ARRAY[1, 3, 42])))
-(2 rows)
+                   QUERY PLAN                    
+-------------------------------------------------
+ Bitmap Heap Scan on tenk1
+   Recheck Cond: (thousand = 42)
+   Filter: (tenthous = ANY (ARRAY[1, 3, 42]))
+   ->  Bitmap Index Scan on tenk1_thous_tenthous
+         Index Cond: (thousand = 42)
+(5 rows)
 
 SELECT * FROM tenk1
   WHERE thousand = 42 AND (tenthous = 1 OR tenthous = 3 OR tenthous = 42);
@@ -1903,17 +1897,15 @@
 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 = ANY (ARRAY[42, 99])))
-         ->  BitmapAnd
-               ->  Bitmap Index Scan on tenk1_hundred
-                     Index Cond: (hundred = 42)
-               ->  Bitmap Index Scan on tenk1_thous_tenthous
-                     Index Cond: (thousand = ANY (ARRAY[42, 99]))
-(8 rows)
+         Recheck Cond: (hundred = 42)
+         Filter: (thousand = ANY (ARRAY[42, 99]))
+         ->  Bitmap Index Scan on tenk1_hundred
+               Index Cond: (hundred = 42)
+(6 rows)
 
 SELECT count(*) FROM tenk1
   WHERE hundred = 42 AND (thousand = 42 OR thousand = 99);
diff -U3 /home/alena/postgrespro__copy32/src/test/regress/expected/join.out /home/alena/postgrespro__copy32/src/test/regress/results/join.out
--- /home/alena/postgrespro__copy32/src/test/regress/expected/join.out	2023-11-30 13:50:34.576537110 +0300
+++ /home/alena/postgrespro__copy32/src/test/regress/results/join.out	2023-11-30 13:52:14.972407590 +0300
@@ -4223,15 +4223,13 @@
                      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 (ARRAY[3, 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)
+                           Index Cond: (unique2 = ANY (ARRAY[3, 7]))
+(17 rows)
 
 SET enable_or_transformation = on;
 explain (costs off)
@@ -4251,12 +4249,12 @@
                      Index Cond: (hundred = 4)
    ->  Materialize
          ->  Bitmap Heap Scan on tenk1 a
-               Recheck Cond: ((unique2 = ANY (ARRAY[3, 7])) OR (unique1 = 1))
+               Recheck Cond: ((unique1 = 1) OR (unique2 = ANY (ARRAY[3, 7])))
                ->  BitmapOr
-                     ->  Bitmap Index Scan on tenk1_unique2
-                           Index Cond: (unique2 = ANY (ARRAY[3, 7]))
                      ->  Bitmap Index Scan on tenk1_unique1
                            Index Cond: (unique1 = 1)
+                     ->  Bitmap Index Scan on tenk1_unique2
+                           Index Cond: (unique2 = ANY (ARRAY[3, 7]))
 (17 rows)
 
 explain (costs off)
diff -U3 /home/alena/postgrespro__copy32/src/test/regress/expected/sysviews.out /home/alena/postgrespro__copy32/src/test/regress/results/sysviews.out
--- /home/alena/postgrespro__copy32/src/test/regress/expected/sysviews.out	2023-11-30 13:50:34.584537100 +0300
+++ /home/alena/postgrespro__copy32/src/test/regress/results/sysviews.out	2023-11-30 13:52:24.524395130 +0300
@@ -123,7 +123,7 @@
  enable_memoize                 | on
  enable_mergejoin               | on
  enable_nestloop                | on
- enable_or_transformation       | off
+ enable_or_transformation       | on
  enable_parallel_append         | on
  enable_parallel_hash           | on
  enable_partition_pruning       | on
diff -U3 /home/alena/postgrespro__copy32/src/test/regress/expected/tidscan.out /home/alena/postgrespro__copy32/src/test/regress/results/tidscan.out
--- /home/alena/postgrespro__copy32/src/test/regress/expected/tidscan.out	2023-11-30 13:50:34.584537100 +0300
+++ /home/alena/postgrespro__copy32/src/test/regress/results/tidscan.out	2023-11-30 13:52:24.328395386 +0300
@@ -62,7 +62,7 @@
                           QUERY PLAN                          
 --------------------------------------------------------------
  Tid Scan on tidscan
-   TID Cond: (ctid = ANY (ARRAY['(0,2)'::tid, '(0,1)'::tid]))
+   TID Cond: ((ctid = '(0,2)'::tid) OR ('(0,1)'::tid = ctid))
 (2 rows)
 
 SELECT ctid, * FROM tidscan WHERE ctid = '(0,2)' OR '(0,1)' = ctid;

---

From: Andrei Lepikhov <[email-masked]>
Date: Mon, 4 Dec 2023 13:50:34 +0700

Hi,

Here is the next version of the patch where, I think, all of Roberts's 
claims related to the code have been fixed.
For example, expression 'x < 1 OR x < 2' is transformed to
'x < ANY (1,2)'.

Here, we still need to deal with the architectural issues. I like the 
approach mentioned by Peter: try to transform the expression tree to 
some 'normal' form, which is more laconic and simple; delay the search 
for any optimization ways to the following stages.

Also, it doesn't pass pg_dump test. At first glance, it is a problem of 
regex expression, which should be corrected further.

-- 
regards,
Andrei Lepikhov
Postgres Professional
From 73031b7acae68494ddd0f9b1faf4c94aae3bd6b0 Mon Sep 17 00:00:00 2001
From: "Andrey V. Lepikhov" <[email-masked]>
Date: Thu, 23 Nov 2023 16:00:13 +0700
Subject: [PATCH] Transform OR clause to ANY expressions.

Replace (expr op C1) OR (expr op C2) ... with expr op ANY(C1, C2, ...) on the
preliminary stage of optimization when we are still working with the tree
expression.
Here C<X> is a constant 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 'CX op expr').
Sometimes it can lead to not optimal plan. But we think it is better to have
array of elements instead of a lot of OR clauses. Here is a room for further
optimizations on decomposing that array into more optimal parts.
---
 .../postgres_fdw/expected/postgres_fdw.out    |  16 +-
 src/backend/nodes/queryjumblefuncs.c          |  30 ++
 src/backend/parser/parse_expr.c               | 310 +++++++++++++++++-
 src/backend/utils/misc/guc_tables.c           |  11 +
 src/backend/utils/misc/postgresql.conf.sample |   1 +
 src/include/nodes/queryjumble.h               |   1 +
 src/include/parser/parse_expr.h               |   1 +
 src/test/regress/expected/create_index.out    | 156 ++++++++-
 src/test/regress/expected/inherit.out         |   2 +-
 src/test/regress/expected/join.out            |  62 +++-
 src/test/regress/expected/partition_prune.out | 219 +++++++++++--
 src/test/regress/expected/rules.out           |   4 +-
 src/test/regress/expected/stats_ext.out       |  12 +-
 src/test/regress/expected/sysviews.out        |   3 +-
 src/test/regress/expected/tidscan.out         |  23 +-
 src/test/regress/sql/create_index.sql         |  35 ++
 src/test/regress/sql/join.sql                 |  10 +
 src/test/regress/sql/partition_prune.sql      |  22 ++
 src/test/regress/sql/tidscan.sql              |   6 +
 src/tools/pgindent/typedefs.list              |   2 +
 20 files changed, 859 insertions(+), 67 deletions(-)

diff --git a/contrib/postgres_fdw/expected/postgres_fdw.out b/contrib/postgres_fdw/expected/postgres_fdw.out
index 0a5bdf8bcc..ff69b2cd3b 100644
--- a/contrib/postgres_fdw/expected/postgres_fdw.out
+++ b/contrib/postgres_fdw/expected/postgres_fdw.out
@@ -1349,7 +1349,7 @@ SELECT t1.c1, t1.c2, t2.c1, t2.c2 FROM ft4 t1 LEFT JOIN (SELECT * FROM ft5 WHERE
  Foreign Scan
    Output: t1.c1, t1.c2, ft5.c1, ft5.c2
    Relations: (public.ft4 t1) LEFT JOIN (public.ft5)
-   Remote SQL: SELECT r1.c1, r1.c2, r4.c1, r4.c2 FROM ("S 1"."T 3" r1 LEFT JOIN "S 1"."T 4" r4 ON (((r1.c1 = r4.c1)) AND ((r4.c1 < 10)))) WHERE (((r4.c1 < 10) OR (r4.c1 IS NULL))) AND ((r1.c1 < 10))
+   Remote SQL: SELECT r1.c1, r1.c2, r4.c1, r4.c2 FROM ("S 1"."T 3" r1 LEFT JOIN "S 1"."T 4" r4 ON (((r1.c1 = r4.c1)) AND ((r4.c1 < 10)))) WHERE (((r4.c1 IS NULL) OR (r4.c1 < 10))) AND ((r1.c1 < 10))
 (4 rows)
 
 SELECT t1.c1, t1.c2, t2.c1, t2.c2 FROM ft4 t1 LEFT JOIN (SELECT * FROM ft5 WHERE c1 < 10) t2 ON (t1.c1 = t2.c1)
@@ -3112,7 +3112,7 @@ select array_agg(distinct (t1.c1)%5) from ft4 t1 full join ft5 t2 on (t1.c1 = t2
  Foreign Scan
    Output: (array_agg(DISTINCT (t1.c1 % 5))), ((t2.c1 % 3))
    Relations: Aggregate on ((public.ft4 t1) FULL JOIN (public.ft5 t2))
-   Remote SQL: SELECT array_agg(DISTINCT (r1.c1 % 5)), (r2.c1 % 3) FROM ("S 1"."T 3" r1 FULL JOIN "S 1"."T 4" r2 ON (((r1.c1 = r2.c1)))) WHERE (((r1.c1 < 20) OR ((r1.c1 IS NULL) AND (r2.c1 < 5)))) GROUP BY 2 ORDER BY array_agg(DISTINCT (r1.c1 % 5)) ASC NULLS LAST
+   Remote SQL: SELECT array_agg(DISTINCT (r1.c1 % 5)), (r2.c1 % 3) FROM ("S 1"."T 3" r1 FULL JOIN "S 1"."T 4" r2 ON (((r1.c1 = r2.c1)))) WHERE ((((r1.c1 IS NULL) AND (r2.c1 < 5)) OR (r1.c1 < 20))) GROUP BY 2 ORDER BY array_agg(DISTINCT (r1.c1 % 5)) ASC NULLS LAST
 (4 rows)
 
 select array_agg(distinct (t1.c1)%5) from ft4 t1 full join ft5 t2 on (t1.c1 = t2.c1) where t1.c1 < 20 or (t1.c1 is null and t2.c1 < 5) group by (t2.c1)%3 order by 1;
@@ -3130,7 +3130,7 @@ select array_agg(distinct (t1.c1)%5 order by (t1.c1)%5) from ft4 t1 full join ft
  Foreign Scan
    Output: (array_agg(DISTINCT (t1.c1 % 5) ORDER BY (t1.c1 % 5))), ((t2.c1 % 3))
    Relations: Aggregate on ((public.ft4 t1) FULL JOIN (public.ft5 t2))
-   Remote SQL: SELECT array_agg(DISTINCT (r1.c1 % 5) ORDER BY ((r1.c1 % 5)) ASC NULLS LAST), (r2.c1 % 3) FROM ("S 1"."T 3" r1 FULL JOIN "S 1"."T 4" r2 ON (((r1.c1 = r2.c1)))) WHERE (((r1.c1 < 20) OR ((r1.c1 IS NULL) AND (r2.c1 < 5)))) GROUP BY 2 ORDER BY array_agg(DISTINCT (r1.c1 % 5) ORDER BY ((r1.c1 % 5)) ASC NULLS LAST) ASC NULLS LAST
+   Remote SQL: SELECT array_agg(DISTINCT (r1.c1 % 5) ORDER BY ((r1.c1 % 5)) ASC NULLS LAST), (r2.c1 % 3) FROM ("S 1"."T 3" r1 FULL JOIN "S 1"."T 4" r2 ON (((r1.c1 = r2.c1)))) WHERE ((((r1.c1 IS NULL) AND (r2.c1 < 5)) OR (r1.c1 < 20))) GROUP BY 2 ORDER BY array_agg(DISTINCT (r1.c1 % 5) ORDER BY ((r1.c1 % 5)) ASC NULLS LAST) ASC NULLS LAST
 (4 rows)
 
 select array_agg(distinct (t1.c1)%5 order by (t1.c1)%5) from ft4 t1 full join ft5 t2 on (t1.c1 = t2.c1) where t1.c1 < 20 or (t1.c1 is null and t2.c1 < 5) group by (t2.c1)%3 order by 1;
@@ -3147,7 +3147,7 @@ select array_agg(distinct (t1.c1)%5 order by (t1.c1)%5 desc nulls last) from ft4
  Foreign Scan
    Output: (array_agg(DISTINCT (t1.c1 % 5) ORDER BY (t1.c1 % 5) DESC NULLS LAST)), ((t2.c1 % 3))
    Relations: Aggregate on ((public.ft4 t1) FULL JOIN (public.ft5 t2))
-   Remote SQL: SELECT array_agg(DISTINCT (r1.c1 % 5) ORDER BY ((r1.c1 % 5)) DESC NULLS LAST), (r2.c1 % 3) FROM ("S 1"."T 3" r1 FULL JOIN "S 1"."T 4" r2 ON (((r1.c1 = r2.c1)))) WHERE (((r1.c1 < 20) OR ((r1.c1 IS NULL) AND (r2.c1 < 5)))) GROUP BY 2 ORDER BY array_agg(DISTINCT (r1.c1 % 5) ORDER BY ((r1.c1 % 5)) DESC NULLS LAST) ASC NULLS LAST
+   Remote SQL: SELECT array_agg(DISTINCT (r1.c1 % 5) ORDER BY ((r1.c1 % 5)) DESC NULLS LAST), (r2.c1 % 3) FROM ("S 1"."T 3" r1 FULL JOIN "S 1"."T 4" r2 ON (((r1.c1 = r2.c1)))) WHERE ((((r1.c1 IS NULL) AND (r2.c1 < 5)) OR (r1.c1 < 20))) GROUP BY 2 ORDER BY array_agg(DISTINCT (r1.c1 % 5) ORDER BY ((r1.c1 % 5)) DESC NULLS LAST) ASC NULLS LAST
 (4 rows)
 
 select array_agg(distinct (t1.c1)%5 order by (t1.c1)%5 desc nulls last) from ft4 t1 full join ft5 t2 on (t1.c1 = t2.c1) where t1.c1 < 20 or (t1.c1 is null and t2.c1 < 5) group by (t2.c1)%3 order by 1;
@@ -8537,18 +8537,18 @@ insert into utrtest values (2, 'qux');
 -- Check case where the foreign partition is a subplan target rel
 explain (verbose, costs off)
 update utrtest set a = 1 where a = 1 or a = 2 returning *;
-                                             QUERY PLAN                                             
-----------------------------------------------------------------------------------------------------
+                                                  QUERY PLAN                                                  
+--------------------------------------------------------------------------------------------------------------
  Update on public.utrtest
    Output: utrtest_1.a, utrtest_1.b
    Foreign Update on public.remp utrtest_1
    Update on public.locp utrtest_2
    ->  Append
          ->  Foreign Update on public.remp utrtest_1
-               Remote SQL: UPDATE public.loct SET a = 1 WHERE (((a = 1) OR (a = 2))) RETURNING a, b
+               Remote SQL: UPDATE public.loct SET a = 1 WHERE ((a = ANY ('{1,2}'::integer[]))) RETURNING a, b
          ->  Seq Scan on public.locp utrtest_2
                Output: 1, utrtest_2.tableoid, utrtest_2.ctid, NULL::record
-               Filter: ((utrtest_2.a = 1) OR (utrtest_2.a = 2))
+               Filter: (utrtest_2.a = ANY ('{1,2}'::integer[]))
 (10 rows)
 
 -- The new values are concatenated with ' triggered !'
diff --git a/src/backend/nodes/queryjumblefuncs.c b/src/backend/nodes/queryjumblefuncs.c
index 281907a4d8..99207a8670 100644
--- a/src/backend/nodes/queryjumblefuncs.c
+++ b/src/backend/nodes/queryjumblefuncs.c
@@ -135,6 +135,36 @@ JumbleQuery(Query *query)
 	return jstate;
 }
 
+JumbleState *
+JumbleExpr(Expr *expr, uint64 *queryId)
+{
+	JumbleState *jstate = NULL;
+
+	Assert(queryId != NULL);
+
+	jstate = (JumbleState *) palloc(sizeof(JumbleState));
+
+	/* Set up workspace for query jumbling */
+	jstate->jumble = (unsigned char *) palloc(JUMBLE_SIZE);
+	jstate->jumble_len = 0;
+	jstate->clocations_buf_size = 32;
+	jstate->clocations = (LocationLen *)
+		palloc(jstate->clocations_buf_size * sizeof(LocationLen));
+	jstate->clocations_count = 0;
+	jstate->highest_extern_param_id = 0;
+
+	/* Compute query ID */
+	_jumbleNode(jstate, (Node *) expr);
+	*queryId = DatumGetUInt64(hash_any_extended(jstate->jumble,
+												jstate->jumble_len,
+												0));
+
+	if (*queryId == UINT64CONST(0))
+		*queryId = UINT64CONST(1);
+
+	return jstate;
+}
+
 /*
  * Enables query identifier computation.
  *
diff --git a/src/backend/parser/parse_expr.c b/src/backend/parser/parse_expr.c
index 64c582c344..9f4d43572c 100644
--- a/src/backend/parser/parse_expr.c
+++ b/src/backend/parser/parse_expr.c
@@ -16,12 +16,14 @@
 #include "postgres.h"
 
 #include "catalog/pg_aggregate.h"
+#include "catalog/pg_operator.h"
 #include "catalog/pg_proc.h"
 #include "catalog/pg_type.h"
 #include "commands/dbcommands.h"
 #include "miscadmin.h"
 #include "nodes/makefuncs.h"
 #include "nodes/nodeFuncs.h"
+#include "nodes/queryjumble.h"
 #include "optimizer/optimizer.h"
 #include "parser/analyze.h"
 #include "parser/parse_agg.h"
@@ -38,11 +40,13 @@
 #include "utils/date.h"
 #include "utils/fmgroids.h"
 #include "utils/lsyscache.h"
+#include "utils/syscache.h"
 #include "utils/timestamp.h"
 #include "utils/xml.h"
 
 /* GUC parameters */
 bool		Transform_null_equals = false;
+bool		enable_or_transformation = true;

 static Node *transformExprRecurse(ParseState *pstate, Node *expr);
@@ -99,6 +103,310 @@ static Expr *make_distinct_op(ParseState *pstate, List *opname,
 static Node *make_nulltest_from_distinct(ParseState *pstate,
 										 A_Expr *distincta, Node *arg);
 
+typedef struct OrClauseGroupKey
+{
+	Expr   *expr; /* Pointer to the expression tree which has been a source for
+					the hashkey value */
+	Oid		opno;
+	Oid		exprtype;
+} OrClauseGroupKey;
+
+typedef struct OrClauseGroupEntry
+{
+	OrClauseGroupKey key;
+
+	Node		   *node;
+	List		   *consts;
+	Oid				scalar_type;
+	List 		   *exprs;
+} OrClauseGroupEntry;
+
+/*
+ * Hash function that's compatible with guc_name_compare
+ */
+static uint32
+orclause_hash(const void *data, Size keysize)
+{
+	OrClauseGroupKey   *key = (OrClauseGroupKey *) data;
+	uint64				hash;
+
+	(void) JumbleExpr(key->expr, &hash);
+	hash += ((uint64) key->opno + (uint64) key->exprtype) % UINT64_MAX;
+	return hash;
+}
+
+static void *
+orclause_keycopy(void *dest, const void *src, Size keysize)
+{
+	OrClauseGroupKey *src_key = (OrClauseGroupKey *) src;
+	OrClauseGroupKey *dst_key = (OrClauseGroupKey *) dest;
+
+	Assert(sizeof(OrClauseGroupKey) == keysize);
+
+	dst_key->expr = src_key->expr;
+	dst_key->opno = src_key->opno;
+	dst_key->exprtype = src_key->exprtype;
+	return dst_key;
+}
+
+/*
+ * Dynahash match function to use in guc_hashtab
+ */
+static int
+orclause_match(const void *data1, const void *data2, Size keysize)
+{
+	OrClauseGroupKey   *key1 = (OrClauseGroupKey *) data1;
+	OrClauseGroupKey   *key2 = (OrClauseGroupKey *) data2;
+
+	Assert(sizeof(OrClauseGroupKey) == keysize);
+
+	if (key1->opno == key2->opno && key1->exprtype == key2->exprtype &&
+		equal(key1->expr, key2->expr))
+		return 0;
+
+	return 1;
+}
+
+static Node *
+transformBoolExprOr(ParseState *pstate, BoolExpr *expr)
+{
+	List				   *or_list = NIL;
+	List				   *entries = NIL;
+	ListCell			   *lc;
+	HASHCTL					info;
+	HTAB 				   *or_group_htab = NULL;
+	int 					len_ors = list_length(expr->args);
+	OrClauseGroupEntry	   *entry = NULL;
+
+	/* If this is not an 'OR' expression, skip the transformation */
+	if (!enable_or_transformation || expr->boolop != OR_EXPR || len_ors < 2)
+		return transformBoolExpr(pstate, (BoolExpr *) expr);
+
+	MemSet(&info, 0, sizeof(info));
+	info.keysize = sizeof(OrClauseGroupKey);
+	info.entrysize = sizeof(OrClauseGroupEntry);
+	info.hash = orclause_hash;
+	info.keycopy = orclause_keycopy;
+	info.match = orclause_match;
+	or_group_htab = hash_create("OR Groups",
+								len_ors,
+								&info,
+								HASH_ELEM | HASH_FUNCTION | HASH_COMPARE | HASH_KEYCOPY);
+
+	foreach(lc, expr->args)
+	{
+		Node				   *arg = lfirst(lc);
+		Node				   *orqual;
+		Node				   *const_expr;
+		Node				   *nconst_expr;
+		OrClauseGroupKey		hashkey;
+		bool					found;
+		Oid						opno;
+		Node				   *leftop, *rightop;
+
+		/* At first, transform the arg and evaluate constant expressions. */
+		orqual = transformExprRecurse(pstate, (Node *) arg);
+		orqual = coerce_to_boolean(pstate, orqual, "OR");
+
+		if (!IsA(orqual, OpExpr))
+		{
+			or_list = lappend(or_list, orqual);
+			continue;
+		}
+
+		opno = ((OpExpr *) orqual)->opno;
+		if (get_op_rettype(opno) != BOOLOID)
+		{
+			/* Only operator returning boolean suits OR -> ANY transformation */
+			or_list = lappend(or_list, orqual);
+			continue;
+		}
+
+		/*
+		 * 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))
+		{
+			opno = get_commutator(opno);
+
+			if (!OidIsValid(opno))
+			{
+				/* Commuter doesn't exist, we can't reverse the order */
+				or_list = lappend(or_list, orqual);
+				continue;
+			}
+
+			nconst_expr = get_rightop(orqual);
+			const_expr = get_leftop(orqual);
+		}
+		else if (IsA(rightop, Const))
+		{
+			const_expr = get_rightop(orqual);
+			nconst_expr = get_leftop(orqual);
+		}
+		else
+		{
+			or_list = lappend(or_list, orqual);
+			continue;
+		}
+
+		/*
+		* At this point we definitely have a transformable clause.
+		* Classify it and add into specific group of clauses, or create new
+		* group.
+		*/
+		hashkey.expr = (Expr *) nconst_expr;
+		hashkey.opno = opno;
+		hashkey.exprtype = exprType(nconst_expr);
+		entry = hash_search(or_group_htab, &hashkey, HASH_ENTER, &found);
+
+		if (unlikely(found))
+		{
+			entry->consts = lappend(entry->consts, const_expr);
+			entry->exprs = lappend(entry->exprs, orqual);
+		}
+		else
+		{
+			entry->node = nconst_expr;
+			entry->consts = list_make1(const_expr);
+			entry->exprs = list_make1(orqual);
+
+			/*
+			 * 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 IN operation. */
+
+	/*
+	 * 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;
+
+		entry = (OrClauseGroupEntry *) 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 in the class. Return origin expression into
+			 * the BoolExpr args list unchanged.
+			 */
+			list_free(entry->consts);
+			or_list = list_concat(or_list, entry->exprs);
+			continue;
+		}
+
+		/*
+		 * Do the transformation.
+		 */
+
+		scalar_type = entry->key.exprtype;
+		if (scalar_type != RECORDOID && OidIsValid(scalar_type))
+			array_type = get_array_type(scalar_type);
+		else
+			array_type = InvalidOid;
+
+		if (array_type != InvalidOid)
+		{
+			/*
+			 * 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;
+			ListCell		   *lc1;
+
+			foreach(lc1, entry->consts)
+			{
+				Node   *rexpr = (Node *) lfirst(lc1);
+
+				rexpr = coerce_to_common_type(pstate, rexpr,
+											  scalar_type,
+											  "IN");
+				aexprs = lappend(aexprs, rexpr);
+			}
+
+			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;
+
+			opertup = SearchSysCache1(OPEROID,
+									  ObjectIdGetDatum(entry->key.opno));
+			if (!HeapTupleIsValid(opertup))
+				elog(ERROR, "cache lookup failed for operator %u",
+					 entry->key.opno);
+
+			operform = (Form_pg_operator) GETSTRUCT(opertup);
+			if (!OperatorIsVisible(entry->key.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(pstate,
+										 namelist,
+										 true,
+										 entry->node,
+										 (Node *) newa,
+										 -1);
+
+			or_list = lappend(or_list, (void *) saopexpr);
+		}
+		else
+		{
+			/*
+			 * This part works on intarray test (OR there is made on
+			 * elements of a custom type)
+			 */
+			list_free(entry->consts);
+			or_list = list_concat(or_list, entry->exprs);
+		}
+	}
+	hash_destroy(or_group_htab);
+	list_free(entries);
+
+	/* One more trick: assemble correct clause */
+	return (Node *) ((list_length(or_list) > 1) ?
+					 makeBoolExpr(OR_EXPR, or_list, expr->location) :
+					 linitial(or_list));
+}
 
 /*
  * transformExpr -
@@ -212,7 +520,7 @@ transformExprRecurse(ParseState *pstate, Node *expr)
 			}
 
 		case T_BoolExpr:
-			result = transformBoolExpr(pstate, (BoolExpr *) expr);
+			result = transformBoolExprOr(pstate, (BoolExpr *) expr);
 			break;
 
 		case T_FuncCall:
diff --git a/src/backend/utils/misc/guc_tables.c b/src/backend/utils/misc/guc_tables.c
index 6474e35ec0..4baca65bfe 100644
--- a/src/backend/utils/misc/guc_tables.c
+++ b/src/backend/utils/misc/guc_tables.c
@@ -1048,6 +1048,17 @@ struct config_bool ConfigureNamesBool[] =
 		true,
 		NULL, NULL, NULL
 	},
+	{
+		{"enable_or_transformation", PGC_USERSET, QUERY_TUNING_OTHER,
+			gettext_noop("Transform a sequence of OR clauses to an IN expression."),
+			gettext_noop("The planner will replace clauses like 'x=c1 OR x=c2 .."
+						 "to the clause 'x IN (c1,c2,...)'"),
+			GUC_EXPLAIN
+		},
+		&enable_or_transformation,
+		true,
+		NULL, NULL, NULL
+	},
 	{
 		/*
 		 * Not for general use --- used by SET SESSION AUTHORIZATION and SET
diff --git a/src/backend/utils/misc/postgresql.conf.sample b/src/backend/utils/misc/postgresql.conf.sample
index cf9f283cfe..3d5b5fbc58 100644
--- a/src/backend/utils/misc/postgresql.conf.sample
+++ b/src/backend/utils/misc/postgresql.conf.sample
@@ -374,6 +374,7 @@
 # - Planner Method Configuration -
 
 #enable_hashagg = on
index 0769081c7a..4aaa31aa80 100644

 extern PGDLLIMPORT bool query_id_enabled;
diff --git a/src/include/parser/parse_expr.h b/src/include/parser/parse_expr.h
index 7d38ca75f7..3a87de0285 100644
--- a/src/include/parser/parse_expr.h
+++ b/src/include/parser/parse_expr.h
@@ -17,6 +17,7 @@
 
 /* GUC parameters */
 extern PGDLLIMPORT bool Transform_null_equals;
+extern PGDLLIMPORT bool enable_or_transformation;
 
 extern Node *transformExpr(ParseState *pstate, Node *expr, ParseExprKind exprKind);
 
diff --git a/src/test/regress/expected/create_index.out b/src/test/regress/expected/create_index.out
index acfd9d1f4f..daf497d3e3 100644
--- a/src/test/regress/expected/create_index.out
+++ b/src/test/regress/expected/create_index.out
@@ -1838,18 +1838,50 @@ 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);
+ 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)
+
+SET enable_or_transformation = on;
+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);
@@ -1861,28 +1893,116 @@ 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 = 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)
+
+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 = ANY ('{42,99}'::integer[])) 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 = 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)
+(14 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 = 99)))
+         Recheck Cond: ((hundred = 42) AND (((thousand = 99) AND (tenthous = 2)) OR (thousand = ANY ('{42,41}'::integer[]))))
          ->  BitmapAnd
                ->  Bitmap Index Scan on tenk1_hundred
                      Index Cond: (hundred = 42)
                ->  BitmapOr
                      ->  Bitmap Index Scan on tenk1_thous_tenthous
-                           Index Cond: (thousand = 42)
+                           Index Cond: ((thousand = 99) AND (tenthous = 2))
                      ->  Bitmap Index Scan on tenk1_thous_tenthous
-                           Index Cond: (thousand = 99)
+                           Index Cond: (thousand = ANY ('{42,41}'::integer[]))
 (11 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
 (1 row)
 
+RESET enable_or_transformation;
 --
 -- Check behavior with duplicate index column contents
 --
diff --git a/src/test/regress/expected/inherit.out b/src/test/regress/expected/inherit.out
index 0f1aa831f6..1781250122 100644
--- a/src/test/regress/expected/inherit.out
+++ b/src/test/regress/expected/inherit.out
@@ -2560,7 +2560,7 @@ explain (costs off) select * from list_parted where a = 'ab' or a in (null, 'cd'
                                    QUERY PLAN                                    
 ---------------------------------------------------------------------------------
  Seq Scan on part_ab_cd list_parted
-   Filter: (((a)::text = 'ab'::text) OR ((a)::text = ANY ('{NULL,cd}'::text[])))
+   Filter: (((a)::text = ANY ('{NULL,cd}'::text[])) OR ((a)::text = 'ab'::text))
 (2 rows)
 
 explain (costs off) select * from list_parted where a = 'ab';
diff --git a/src/test/regress/expected/join.out b/src/test/regress/expected/join.out
index 2c73270143..36dce0b84b 100644
--- a/src/test/regress/expected/join.out
+++ b/src/test/regress/expected/join.out
@@ -4210,10 +4210,10 @@ 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                                                      
-----------------------------------------------------------------------------------------------------------------------
+                                                       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)))
+   Join Filter: (((a.unique1 = 1) AND (b.unique1 = 2)) OR ((a.unique2 = ANY ('{3,7}'::integer[])) AND (b.hundred = 4)))
    ->  Bitmap Heap Scan on tenk1 b
          Recheck Cond: ((unique1 = 2) OR (hundred = 4))
          ->  BitmapOr
@@ -4223,16 +4223,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[])))
                ->  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[]))
+(17 rows)
+
+SET enable_or_transformation = on;
+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 = ANY ('{3,7}'::integer[])) 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[])))
+               ->  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[]))
+(17 rows)
+
+explain (costs off)
+select * from tenk1 a join tenk1 b on
+  (a.unique1 < 20 or a.unique1 = 3 or a.unique1 = 1 and b.unique1 = 2) or
+  ((a.unique2 = 3 or a.unique2 = 7) and b.hundred = 4);
+                                                                          QUERY PLAN                                                                           
+---------------------------------------------------------------------------------------------------------------------------------------------------------------
+ Nested Loop
+   Join Filter: (((a.unique1 = 1) AND (b.unique1 = 2)) OR ((a.unique2 = ANY ('{3,7}'::integer[])) AND (b.hundred = 4)) OR (a.unique1 < 20) OR (a.unique1 = 3))
+   ->  Seq Scan on tenk1 b
+   ->  Materialize
+         ->  Bitmap Heap Scan on tenk1 a
+               Recheck Cond: ((unique1 = 1) OR (unique2 = ANY ('{3,7}'::integer[])) OR (unique1 < 20) OR (unique1 = 3))
+               ->  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 < 20)
+                     ->  Bitmap Index Scan on tenk1_unique1
+                           Index Cond: (unique1 = 3)
+(15 rows)
 
+RESET enable_or_transformation;
 --
 -- test placement of movable quals in a parameterized join tree
 --
diff --git a/src/test/regress/expected/partition_prune.out b/src/test/regress/expected/partition_prune.out
index 9a4c48c055..3423af4768 100644
--- a/src/test/regress/expected/partition_prune.out
+++ b/src/test/regress/expected/partition_prune.out
@@ -82,25 +82,47 @@ explain (costs off) select * from lp where a is null;
 (2 rows)
 
 explain (costs off) select * from lp where a = 'a' or a = 'c';
-                        QUERY PLAN                        
-----------------------------------------------------------
+                  QUERY PLAN                   
+-----------------------------------------------
  Append
    ->  Seq Scan on lp_ad lp_1
-         Filter: ((a = 'a'::bpchar) OR (a = 'c'::bpchar))
+         Filter: (a = ANY ('{a,c}'::bpchar[]))
    ->  Seq Scan on lp_bc lp_2
-         Filter: ((a = 'a'::bpchar) OR (a = 'c'::bpchar))
+         Filter: (a = ANY ('{a,c}'::bpchar[]))
 (5 rows)
 
 explain (costs off) select * from lp where a is not null and (a = 'a' or a = 'c');
-                                   QUERY PLAN                                   
---------------------------------------------------------------------------------
+                             QUERY PLAN                              
+---------------------------------------------------------------------
  Append
    ->  Seq Scan on lp_ad lp_1
-         Filter: ((a IS NOT NULL) AND ((a = 'a'::bpchar) OR (a = 'c'::bpchar)))
+         Filter: ((a IS NOT NULL) AND (a = ANY ('{a,c}'::bpchar[])))
    ->  Seq Scan on lp_bc lp_2
-         Filter: ((a IS NOT NULL) AND ((a = 'a'::bpchar) OR (a = 'c'::bpchar)))
+         Filter: ((a IS NOT NULL) AND (a = ANY ('{a,c}'::bpchar[])))
 (5 rows)
 
+SET enable_or_transformation = on;
+explain (costs off) select * from lp where a = 'a' or a = 'c';
+                  QUERY PLAN                   
+-----------------------------------------------
+ Append
+   ->  Seq Scan on lp_ad lp_1
+         Filter: (a = ANY ('{a,c}'::bpchar[]))
+   ->  Seq Scan on lp_bc lp_2
+         Filter: (a = ANY ('{a,c}'::bpchar[]))
+(5 rows)
+
+explain (costs off) select * from lp where a is not null and (a = 'a' or a = 'c');
+                             QUERY PLAN                              
+---------------------------------------------------------------------
+ Append
+   ->  Seq Scan on lp_ad lp_1
+         Filter: ((a IS NOT NULL) AND (a = ANY ('{a,c}'::bpchar[])))
+   ->  Seq Scan on lp_bc lp_2
+         Filter: ((a IS NOT NULL) AND (a = ANY ('{a,c}'::bpchar[])))
+(5 rows)
+
+RESET enable_or_transformation;
 explain (costs off) select * from lp where a <> 'g';
              QUERY PLAN             
 ------------------------------------
@@ -515,10 +537,10 @@ explain (costs off) select * from rlp where a <= 31;
 (27 rows)
 
 explain (costs off) select * from rlp where a = 1 or a = 7;
-           QUERY PLAN           
---------------------------------
+                QUERY PLAN                
+------------------------------------------
  Seq Scan on rlp2 rlp
-   Filter: ((a = 1) OR (a = 7))
+   Filter: (a = ANY ('{1,7}'::integer[]))
 (2 rows)
 
 explain (costs off) select * from rlp where a = 1 or b = 'ab';
@@ -589,20 +611,20 @@ explain (costs off) select * from rlp where a < 1 or (a > 20 and a < 25);
 ------------------------------------------------------
  Append
    ->  Seq Scan on rlp1 rlp_1
-         Filter: ((a < 1) OR ((a > 20) AND (a < 25)))
+         Filter: (((a > 20) AND (a < 25)) OR (a < 1))
    ->  Seq Scan on rlp4_1 rlp_2
-         Filter: ((a < 1) OR ((a > 20) AND (a < 25)))
+         Filter: (((a > 20) AND (a < 25)) OR (a < 1))
 (5 rows)
 
 -- where clause contradicts sub-partition's constraint
 explain (costs off) select * from rlp where a = 20 or a = 40;
-               QUERY PLAN               
-----------------------------------------
+                    QUERY PLAN                    
+--------------------------------------------------
  Append
    ->  Seq Scan on rlp4_1 rlp_1
-         Filter: ((a = 20) OR (a = 40))
+         Filter: (a = ANY ('{20,40}'::integer[]))
    ->  Seq Scan on rlp5_default rlp_2
-         Filter: ((a = 20) OR (a = 40))
+         Filter: (a = ANY ('{20,40}'::integer[]))
 (5 rows)
 
 explain (costs off) select * from rlp3 where a = 20;   /* empty */
@@ -671,6 +693,163 @@ explain (costs off) select * from rlp where (a = 1 and a = 3) or (a > 1 and a =
          Filter: (((a = 1) AND (a = 3)) OR ((a > 1) AND (a = 15)))
 (11 rows)
 
+------------------------------------------
+   Filter: (a = ANY ('{1,7}'::integer[]))
+         Filter: (((a > 20) AND (a < 25)) OR (a < 1))
+         Filter: (((a > 20) AND (a < 25)) OR (a < 1))
+         Filter: (a = ANY ('{20,40}'::integer[]))
+         Filter: (a = ANY ('{20,40}'::integer[]))
@@ -1933,10 +2112,10 @@ explain (costs off) select * from hp where a = 1 and b = 'abcde';
 
 explain (costs off) select * from hp where a = 1 and b = 'abcde' and
   (c = 2 or c = 3);
-                              QUERY PLAN                              
-----------------------------------------------------------------------
+                                   QUERY PLAN                                   
+--------------------------------------------------------------------------------
  Seq Scan on hp2 hp
-   Filter: ((a = 1) AND (b = 'abcde'::text) AND ((c = 2) OR (c = 3)))
+   Filter: ((c = ANY ('{2,3}'::integer[])) AND (a = 1) AND (b = 'abcde'::text))
 (2 rows)
 
 drop table hp2;
diff --git a/src/test/regress/expected/rules.out b/src/test/regress/expected/rules.out
index 05070393b9..c927c21dd4 100644
--- a/src/test/regress/expected/rules.out
+++ b/src/test/regress/expected/rules.out
@@ -2495,7 +2495,7 @@ pg_stats| SELECT n.nspname AS schemaname,
      JOIN pg_class c ON ((c.oid = s.starelid)))
      JOIN pg_attribute a ON (((c.oid = a.attrelid) AND (a.attnum = s.staattnum))))
      LEFT JOIN pg_namespace n ON ((n.oid = c.relnamespace)))
-  WHERE ((NOT a.attisdropped) AND has_column_privilege(c.oid, a.attnum, 'select'::text) AND ((c.relrowsecurity = false) OR (NOT row_security_active(c.oid))));
+  WHERE ((NOT a.attisdropped) AND has_column_privilege(c.oid, a.attnum, 'select'::text) AND ((NOT row_security_active(c.oid)) OR (c.relrowsecurity = false)));
 pg_stats_ext| SELECT cn.nspname AS schemaname,
     c.relname AS tablename,
     sn.nspname AS statistics_schemaname,
@@ -2526,7 +2526,7 @@ pg_stats_ext| SELECT cn.nspname AS schemaname,
   WHERE ((NOT (EXISTS ( SELECT 1
            FROM (unnest(s.stxkeys) k(k)
              JOIN pg_attribute a ON (((a.attrelid = s.stxrelid) AND (a.attnum = k.k))))
-          WHERE (NOT has_column_privilege(c.oid, a.attnum, 'select'::text))))) AND ((c.relrowsecurity = false) OR (NOT row_security_active(c.oid))));
+          WHERE (NOT has_column_privilege(c.oid, a.attnum, 'select'::text))))) AND ((NOT row_security_active(c.oid)) OR (c.relrowsecurity = false)));
 pg_stats_ext_exprs| SELECT cn.nspname AS schemaname,
     c.relname AS tablename,
     sn.nspname AS statistics_schemaname,
diff --git a/src/test/regress/expected/stats_ext.out b/src/test/regress/expected/stats_ext.out
index a430153b22..659d712f75 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
index 271313ebf8..c6c6b9fb8d 100644
 
 -- There are always wait event descriptions for various types.
 select type, count(*) > 0 as ok FROM pg_wait_events
diff --git a/src/test/regress/expected/tidscan.out b/src/test/regress/expected/tidscan.out
index f133b5a4ac..2a079e996b 100644
--- a/src/test/regress/expected/tidscan.out
+++ b/src/test/regress/expected/tidscan.out
@@ -43,10 +43,26 @@ 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 = ANY ('{"(0,2)","(0,1)"}'::tid[]))
+(2 rows)
+
+SELECT ctid, * FROM tidscan WHERE ctid = '(0,2)' OR '(0,1)' = ctid;
+ ctid  | id 
+-------+----
+ (0,1) |  1
+ (0,2) |  2
+(2 rows)
+
+SET enable_or_transformation = on;
+EXPLAIN (COSTS OFF)
+SELECT ctid, * FROM tidscan WHERE ctid = '(0,2)' OR '(0,1)' = ctid;
+                      QUERY PLAN                       
+-------------------------------------------------------
  Tid Scan on tidscan
-   TID Cond: ((ctid = '(0,2)'::tid) OR ('(0,1)'::tid = ctid))
+   TID Cond: (ctid = ANY ('{"(0,2)","(0,1)"}'::tid[]))
 (2 rows)
 
 SELECT ctid, * FROM tidscan WHERE ctid = '(0,2)' OR '(0,1)' = ctid;
@@ -56,6 +72,7 @@ SELECT ctid, * FROM tidscan WHERE ctid = '(0,2)' OR '(0,1)' = ctid;
  (0,2) |  2
 (2 rows)
 
index d49ce9f300..56fde15bc1 100644
@@ -737,6 +737,41 @@ SELECT count(*) FROM tenk1
 
+  WHERE hundred = 42 AND (thousand < 42 OR thousand < 99 OR 43 > thousand OR 42 > thousand);
index 8a8a63bd2f..55d7e2ae7d 100644
 
index 7bf3920827..1e270ae9c0 100644
 
+
index 313e0fb9b6..0499bedb9e 100644
 
index d659adbfd6..9591d0d084 100644
@@ -1645,6 +1645,8 @@ NumericVar
 OM_uint32
 OP
 OSAPerGroupState
+OrClauseGroupEntry
+OrClauseGroupKey
 OSAPerQueryState
 OSInfo
 OSSLCipher
-- 
2.43.0

---

From: Andrei Lepikhov <[email-masked]>
Date: Tue, 5 Dec 2023 17:55:00 +0700

Here is fresh version with the pg_dump.pl regex fixed. Now it must pass 
buildfarm.

Under development:
1. Explanation of the general idea in comments (Robert's note)
2. Issue with hiding some optimizations (Alexander's note and example 
with overlapping clauses on two partial indexes)

-- 
regards,
Andrei Lepikhov
Postgres Professional
From 71746caae3eb0c771792b563fd53244fc1ac575b Mon Sep 17 00:00:00 2001
From: "Andrey V. Lepikhov" <[email-masked]>
Date: Thu, 23 Nov 2023 16:00:13 +0700
Subject: [PATCH] Transform OR clause to ANY expressions.

 src/bin/pg_dump/t/002_pg_dump.pl              |   6 +-
 21 files changed, 862 insertions(+), 70 deletions(-)

 

 
 
+JumbleState *

 /* GUC parameters */

 
 /*
  * transformExpr -
 
 		case T_BoolExpr:
 
 		case T_FuncCall:
 
 #enable_async_append = on
+#enable_or_transformation = on
 #enable_bitmapscan = on
 #enable_gathermerge = on
 #enable_hashagg = on
diff --git a/src/bin/pg_dump/t/002_pg_dump.pl b/src/bin/pg_dump/t/002_pg_dump.pl
index eb3ec534b4..452617bbb5 100644
--- a/src/bin/pg_dump/t/002_pg_dump.pl
+++ b/src/bin/pg_dump/t/002_pg_dump.pl
@@ -2059,9 +2059,9 @@ my %tests = (
 		regexp => qr/^
 			\QCREATE DOMAIN dump_test.us_postal_code AS text COLLATE pg_catalog."C" DEFAULT '10014'::text\E\n\s+
 			\QCONSTRAINT us_postal_code_check CHECK \E
-			\Q(((VALUE ~ '^\d{5}\E
-			\$\Q'::text) OR (VALUE ~ '^\d{5}-\d{4}\E\$
-			\Q'::text)));\E(.|\n)*
+			\Q((VALUE ~ ANY (ARRAY['^\d{5}\E
+			\$\Q'::text, '^\d{5}-\d{4}\E\$
+			\Q'::text])));\E(.|\n)*
 			\QCOMMENT ON CONSTRAINT us_postal_code_check ON DOMAIN dump_test.us_postal_code IS 'check it';\E
 			/xm,
 		like =>
diff --git a/src/include/nodes/queryjumble.h b/src/include/nodes/queryjumble.h
index 0769081c7a..4aaa31aa80 100644
--- a/src/include/nodes/queryjumble.h
+++ b/src/include/nodes/queryjumble.h
@@ -65,6 +65,7 @@ extern PGDLLIMPORT int compute_query_id;

 
 /* GUC parameters */

 
 SELECT * FROM tenk1

 

 

 

 

 drop table hp2;

 

 

 

 
+

---

From: vignesh C <[email-masked]>
Date: Sat, 27 Jan 2024 08:28:53 +0530

> with overlapping clauses on two partial indexes)

CFBot shows that the patch does not apply anymore as in [1]:
=== Applying patches on top of PostgreSQL commit ID
64444ce071f6b04d3fc836f436fa08108a6d11e2 ===
=== applying patch ./v14-1-0001-Transform-OR-clause-to-ANY-expressions.patch
....
patching file src/test/regress/expected/sysviews.out
Hunk #1 succeeded at 124 (offset 1 line).
Hunk #2 FAILED at 134.
1 out of 2 hunks FAILED -- saving rejects to file
src/test/regress/expected/sysviews.out.rej

Please post an updated version for the same.

[1] - http://cfbot.cputube.org/patch_46_4450.log

Regards,
Vignesh

---

From: jian he <[email-masked]>
Date: Tue, 30 Jan 2024 22:15:20 +0800

+JumbleState *

+/*

correct me if i am wrong:
in orclause_hash, you just want to return a uint32, then why does the
JumbleExpr function return struct JumbleState.
here JumbleExpr, we just simply hash part of a Query struct,
so JumbleExpr's queryId would be confused with JumbleQuery function's queryId.

not sure the purpose of the following:
+ if (*queryId == UINT64CONST(0))
+ *queryId = UINT64CONST(1);

even if  *queryId is 0
`hash += ((uint64) key->opno + (uint64) key->exprtype) % UINT64_MAX;`
will make the hash return non-zero?

+ MemSet(&info, 0, sizeof(info));
i am not sure this is necessary.

Some comments on OrClauseGroupEntry would be great.

seems there is no doc.

create or replace function retint(int) returns int as
$func$
begin return $1 + round(10 * random()); end
$func$ LANGUAGE plpgsql;

set enable_or_transformation to on;
EXPLAIN (COSTS OFF)
SELECT count(*) FROM tenk1
WHERE thousand = 42 AND (tenthous * retint(1) = NULL OR tenthous *
retint(1) = 3) OR thousand = 41;

returns:
                                                    QUERY PLAN
-------------------------------------------------------------------------------------------------------------------
 Aggregate
   ->  Seq Scan on tenk1
         Filter: (((thousand = 42) AND ((tenthous * retint(1)) = ANY
('{NULL,3}'::integer[]))) OR (thousand = 41))
(3 rows)

Based on the query plan, retint executed once, but here it should be
executed twice?
maybe we need to use contain_volatile_functions to check through the
other part of the operator expression.

do we need to skip this transformation for the const type is anyarray?

---

From: jian he <[email-masked]>
Date: Wed, 31 Jan 2024 10:55:56 +0800

+/*

looks strange. `hash` is uint64, but here you return uint32.

based on my understanding of
https://www.postgresql.org/docs/current/xoper-optimization.html#XOPER-COMMUTATOR
I think you need move commutator check right after the `if
(get_op_rettype(opno) != BOOLOID)` branch

select  po.oprname,po.oprkind,po.oprcanhash,po.oprleft::regtype,po.oprright,po.oprresult,
po1.oprname
from    pg_operator po join pg_operator po1
on      po.oprcom = po1.oid
where   po.oprresult = 16;

I am wondering, are all these types as long as the return type is bool
suitable for this transformation?

---

From: jian he <[email-masked]>
Date: Wed, 31 Jan 2024 18:15:00 +0800

> (get_op_rettype(opno) != BOOLOID)` branch
I was wrong about this part. sorry for the noise.

I have made some changes (attachment).
* if the operator expression left or right side type category is
{array | domain | composite}, then don't do the transformation.
(i am not 10% sure with composite)

* if the left side of the operator expression node contains volatile
functions, then don't do the transformation.

* some other minor  cosmetic changes.

---

From: Alena Rybakina <[email-masked]>
Date: Wed, 31 Jan 2024 14:10:44 +0300

Hi, thank you for your review and interest in this subject.

On 31.01.2024 13:15, jian he wrote:
> On Wed, Jan 31, 2024 at 10:55 AM jian he<[email-masked]>  wrote:

To be honest, I'm not sure about this check, because we check the type 
of variable there:

if (!IsA(orqual, OpExpr))
         {
             or_list = lappend(or_list, orqual);
             continue;
         }
And below:
if (IsA(leftop, Const))
         {
             opno = get_commutator(opno);

             if (!OidIsValid(opno))
             {
                 /* Commuter doesn't exist, we can't reverse the order */
                 or_list = lappend(or_list, orqual);
                 continue;
             }

             nconst_expr = get_rightop(orqual);
             const_expr = get_leftop(orqual);
         }
         else if (IsA(rightop, Const))
         {
             const_expr = get_rightop(orqual);
             nconst_expr = get_leftop(orqual);
         }
         else
         {
             or_list = lappend(or_list, orqual);
             continue;
         }

Isn't that enough?

Besides, some of examples (with ARRAY) works fine:

postgres=# CREATE TABLE sal_emp (
     pay_by_quarter  integer[],
     pay_by_quater1 integer[]
);
CREATE TABLE
postgres=# INSERT INTO sal_emp
     VALUES (
     '{10000, 10000, 10000, 10000}',
     '{1,2,3,4}');
INSERT 0 1
postgres=# select * from sal_emp where pay_by_quarter[1] = 10000 or 
pay_by_quarter[1]=2;
       pay_by_quarter       | pay_by_quater1
---------------------------+----------------
  {10000,10000,10000,10000} | {1,2,3,4}
(1 row)

postgres=# explain select * from sal_emp where pay_by_quarter[1] = 10000 
or pay_by_quarter[1]=2;
                           QUERY PLAN
--------------------------------------------------------------
  Seq Scan on sal_emp  (cost=0.00..21.00 rows=9 width=64)
    Filter: (pay_by_quarter[1] = ANY ('{10000,2}'::integer[]))
(2 rows)

> functions, then don't do the transformation.

I'm also not sure about the volatility check function, because we 
perform such a conversion at the parsing stage, and at this stage we 
don't have a RelOptInfo variable and especially a RestictInfo such as 
PathTarget.

Speaking of NextValueExpr, I couldn't find any examples where the 
current patch wouldn't work. I wrote one of them below:

postgres=# create table foo (f1 int, f2 int generated always as identity);
CREATE TABLE
postgres=# insert into foo values(1);
INSERT 0 1

postgres=# explain verbose update foo set f1 = 2 where f1=1 or f1=2 ;
                             QUERY PLAN
-------------------------------------------------------------------
  Update on public.foo  (cost=0.00..38.25 rows=0 width=0)
    ->  Seq Scan on public.foo  (cost=0.00..38.25 rows=23 width=10)
          Output: 2, ctid
          Filter: (foo.f1 = ANY ('{1,2}'::integer[]))
(4 rows)

Maybe I missed something. Do you have any examples?

> * some other minor  cosmetic changes.
Thank you, I agree with them.

-- 
Regards,
Alena Rybakina
Postgres Professional:http://www.postgrespro.com
The Russian Postgres Company

---

From: jian he <[email-masked]>
Date: Thu, 1 Feb 2024 13:00:00 +0800

On Wed, Jan 31, 2024 at 7:10 PM Alena Rybakina
<[email-masked]> wrote:
> To be honest, I'm not sure about this check, because we check the type of variable there:
>

alter table tenk1 add column arr int[];
set enable_or_transformation to on;
EXPLAIN (COSTS OFF)
SELECT count(*) FROM tenk1
WHERE arr = '{1,2,3}' or arr = '{1,2}';

the above query will not do the OR transformation. because array type
doesn't have array type.
`
scalar_type = entry->key.exprtype;
if (scalar_type != RECORDOID && OidIsValid(scalar_type))
array_type = get_array_type(scalar_type);
else
array_type = InvalidOid;
`

If either side of the operator expression is array or array related type,
we can be sure it cannot do the transformation
(get_array_type will return InvalidOid for anyarray type).
we can check it earlier, so hash related code will not be invoked for
array related types.

> postgres=# select * from sal_emp where pay_by_quarter[1] = 10000 or pay_by_quarter[1]=2;
> postgres=# explain select * from sal_emp where pay_by_quarter[1] = 10000 or pay_by_quarter[1]=2;
>                           QUERY PLAN
> I'm also not sure about the volatility check function, because we perform such a conversion at the parsing stage, and at this stage we don't have a RelOptInfo variable and especially a RestictInfo such as PathTarget.
>
 see the example in here:
https://www.postgresql.org/message-id/CACJufxGXhJ823cdAdp2Ho7qC-HZ3_-dtdj-myaAi_u9RQLn45g%40mail.gmail.com

set enable_or_transformation to on;
create or replace function retint(int) returns int as
$func$
begin raise notice 'hello';
        return $1 + round(10 * random()); end
$func$ LANGUAGE plpgsql;

SELECT count(*) FROM tenk1 WHERE thousand = 42;
will return 10 rows.

SELECT count(*) FROM tenk1 WHERE thousand = 42 AND (retint(1) = 4 OR
retint(1) = 3);
this query I should return 20 notices 'hello', but now only 10.

EXPLAIN (COSTS OFF)
SELECT count(*) FROM tenk1
WHERE thousand = 42 AND (retint(1) = 4 OR  retint(1) = 3);
                                  QUERY PLAN
------------------------------------------------------------------------------
 Aggregate
   ->  Seq Scan on tenk1
         Filter: ((thousand = 42) AND (retint(1) = ANY ('{4,3}'::integer[])))
(3 rows)

---

From: Alena Rybakina <[email-masked]>
Date: Fri, 2 Feb 2024 22:06:17 +0300

> we can check it earlier, so hash related code will not be invoked for
Agree.
> WHERE thousand = 42 AND (retint(1) = 4 OR  retint(1) = 3);

Agree.

I added your code to the patch.

-- 
Regards,
Alena Rybakina
Postgres Professional:http://www.postgrespro.com
The Russian Postgres Company
From 0fcad72153c9eaaf436e5b417c803a70fbeaf8ac Mon Sep 17 00:00:00 2001
From: Alena Rybakina <[email-masked]>
Date: Fri, 2 Feb 2024 22:01:09 +0300
Subject: [PATCH] Transform OR clause to ANY expressions.

Replace (expr op C1) OR (expr op C2) ... with expr op ANY(C1, C2, ...) on the
preliminary stage of optimization when we are still working with the tree
expression.
Here C<X> is a constant 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 'CX op expr').
Sometimes it can lead to not optimal plan. But we think it is better to have
array of elements instead of a lot of OR clauses. Here is a room for further
optimizations on decomposing that array into more optimal parts.
Authors: Alena Rybakina <[email-masked]>, Andrey Lepikhov <[email-masked]>
Reviewed-by: Peter Geoghegan <[email-masked]>, Ranier Vilela <[email-masked]>
Reviewed-by: Alexander Korotkov <[email-masked]>, Robert Haas <[email-masked]>
Reviewed-by: jian he <[email-masked]>
---
 .../postgres_fdw/expected/postgres_fdw.out    |  16 +-
 src/backend/nodes/queryjumblefuncs.c          |  30 ++
 src/backend/parser/parse_expr.c               | 340 +++++++++++++++++-
 src/backend/utils/misc/guc_tables.c           |  11 +
 src/backend/utils/misc/postgresql.conf.sample |   1 +
 src/bin/pg_dump/t/002_pg_dump.pl              |   6 +-
 src/include/nodes/queryjumble.h               |   1 +
 src/include/parser/parse_expr.h               |   1 +
 src/test/regress/expected/create_index.out    | 156 +++++++-
 src/test/regress/expected/inherit.out         |   2 +-
 src/test/regress/expected/join.out            |  62 +++-
 src/test/regress/expected/partition_prune.out | 219 +++++++++--
 src/test/regress/expected/rules.out           |   4 +-
 src/test/regress/expected/stats_ext.out       |  12 +-
 src/test/regress/expected/sysviews.out        |   3 +-
 src/test/regress/expected/tidscan.out         |  23 +-
 src/test/regress/sql/create_index.sql         |  35 ++
 src/test/regress/sql/join.sql                 |  10 +
 src/test/regress/sql/partition_prune.sql      |  22 ++
 src/test/regress/sql/tidscan.sql              |   6 +
 src/tools/pgindent/typedefs.list              |   2 +
 21 files changed, 892 insertions(+), 70 deletions(-)

index b5a38aeb214..a07aefc9e51 100644
 
@@ -3105,7 +3105,7 @@ select array_agg(distinct (t1.c1)%5) from ft4 t1 full join ft5 t2 on (t1.c1 = t2
 
@@ -3123,7 +3123,7 @@ select array_agg(distinct (t1.c1)%5 order by (t1.c1)%5) from ft4 t1 full join ft
 
@@ -3140,7 +3140,7 @@ select array_agg(distinct (t1.c1)%5 order by (t1.c1)%5 desc nulls last) from ft4
 
@@ -8797,18 +8797,18 @@ insert into utrtest values (2, 'qux');
 
index e489bfceb56..4e77cfe925c 100644
 
+JumbleState *
index 9300c7b9abc..fb199230cbf 100644

 /* GUC parameters */

 static Node *transformExprRecurse(ParseState *pstate, Node *expr);
@@ -99,6 +103,340 @@ static Expr *make_distinct_op(ParseState *pstate, List *opname,
 static Node *make_nulltest_from_distinct(ParseState *pstate,
 										 A_Expr *distincta, Node *arg);
 
+		TYPCATEGORY 			category;
+				/* commutator doesn't exist, we can't reverse the order */
+		/* transformation only works with both side type is not { array | compoiste | domain } */
+		category = TypeCategory(exprType(const_expr));
+		if (category == TYPCATEGORY_ARRAY || category == TYPTYPE_DOMAIN
+			|| category == TYPTYPE_COMPOSITE)
+		category = TypeCategory(exprType(nconst_expr));
+		if (category == TYPCATEGORY_ARRAY || category == TYPTYPE_DOMAIN
+			|| category == TYPTYPE_COMPOSITE)
+		 * if the non-const (left side of operator expression) contain voltain functions
+		 * then we cannot do the transformation
+		if (contain_volatile_functions((Node *) nconst_expr))
+		if (OidIsValid(array_type))
+			 * If the const node (right side of operator expression) 's type
+			 *  don't have “true” array type, then we cannnot do the transformation.
+			 * We simply concatenate the expression node.
 
 /*
  * transformExpr -
@@ -212,7 +550,7 @@ transformExprRecurse(ParseState *pstate, Node *expr)
 			}
 
 		case T_BoolExpr:
 
 		case T_FuncCall:
index 7fe58518d7d..ddda2d3c488 100644
@@ -1071,6 +1071,17 @@ struct config_bool ConfigureNamesBool[] =
index da10b43dac3..6876d73392a 100644
@@ -379,6 +379,7 @@
 
index 00b5092713d..d28bf617dbe 100644
@@ -2095,9 +2095,9 @@ my %tests = (
index f1c55c8067f..a9ae048af52 100644

index 9b46dfd9ecc..4ff4adc77d2 100644
 
 /* GUC parameters */

index 79fa117cb54..b8653c09ea2 100644
 
 SELECT * FROM tenk1

index 130a9242288..684886336cd 100644
@@ -2600,7 +2600,7 @@ explain (costs off) select * from list_parted where a = 'ab' or a in (null, 'cd'
 
index 9c08d0134ca..256ed8acb5c 100644
 
index 9a4c48c0556..3423af47684 100644

 

 

 
 
 drop table hp2;
index abc944e8b82..3ec614c4376 100644
@@ -2500,7 +2500,7 @@ pg_stats| SELECT n.nspname AS schemaname,
@@ -2531,7 +2531,7 @@ pg_stats_ext| SELECT cn.nspname AS schemaname,
index 10903bdab09..6f55b9e3ec1 100644

 

 
 -- OR clauses referencing different attributes
diff --git a/src/test/regress/expected/sysviews.out b/src/test/regress/expected/sysviews.out
index 9be7aca2b8a..1f9029b5b2a 100644
--- a/src/test/regress/expected/sysviews.out
+++ b/src/test/regress/expected/sysviews.out
@@ -124,6 +124,7 @@ select name, setting from pg_settings where name like 'enable%';
  enable_memoize                 | on
  enable_mergejoin               | on
  enable_nestloop                | on
+ enable_or_transformation       | on
  enable_parallel_append         | on
  enable_parallel_hash           | on
  enable_partition_pruning       | on
@@ -134,7 +135,7 @@ select name, setting from pg_settings where name like 'enable%';
  enable_seqscan                 | on
  enable_sort                    | on
  enable_tidscan                 | on
-(23 rows)
+(24 rows)
 
index f133b5a4ac7..2a079e996b2 100644

index d49ce9f3007..56fde15bc15 100644
 
index e1db2025db6..353deecef03 100644

+
 
index 91433d439b7..adae668b370 100644
@@ -1654,6 +1654,8 @@ NumericVar
 OM_uint32
 OP
 OSAPerGroupState
+OrClauseGroupEntry
+OrClauseGroupKey
 OSAPerQueryState
 OSInfo
 OSSLCipher
-- 
2.34.1

---

From: Andrei Lepikhov <[email-masked]>
Date: Thu, 8 Feb 2024 12:34:38 +0700

> I added your code to the patch.
Thanks Alena and Jian for the detailed scrutiny!

A couple of questions:
1. As I see, transformAExprIn uses the same logic as we invented but 
allows composite and domain types. Could you add a comment explaining 
why we forbid row types in general, in contrast to the transformAExprIn 
routine?
2. Could you provide the tests to check issues covered by the recent (in 
v.15) changes?

Patch 0001-* in the attachment incorporates changes induced by Jian's 
notes from [1].
Patch 0002-* contains a transformation of the SAOP clause, which allows 
the optimizer to utilize partial indexes if they cover all values in 
this array. Also, it is an answer to Alexander's note [2] on performance 
degradation. This first version may be a bit raw, but I need your 
opinion: Does it resolve the issue?

Skimming through the thread, I see that, in general, all issues have 
been covered for now. Only Robert's note on a lack of documentation is 
still needs to be resolved.

[1] 
https://www.postgresql.org/message-id/CACJufxGXhJ823cdAdp2Ho7qC-HZ3_-dtdj-myaAi_u9RQLn45g%40mail.gmail.com
[2] 
https://www.postgresql.org/message-id/CAPpHfduJtO0s9E%3DSHUTzrCD88BH0eik0UNog1_q3XBF2wLmH6g%40mail.gmail.com

-- 
regards,
Andrei Lepikhov
Postgres Professional
From 0ac511ab94959e87d1525d5ea8c4855643a6ccbe Mon Sep 17 00:00:00 2001
From: Alena Rybakina <[email-masked]>
Date: Fri, 2 Feb 2024 22:01:09 +0300
Subject: [PATCH 1/2] Transform OR clause to ANY expressions.

 src/backend/nodes/queryjumblefuncs.c          |  27 ++
 src/backend/parser/parse_expr.c               | 327 +++++++++++++++++-
 src/include/optimizer/optimizer.h             |   1 +
 src/test/regress/expected/partition_prune.out | 219 ++++++++++--
 21 files changed, 876 insertions(+), 70 deletions(-)

index b5a38aeb21..a07aefc9e5 100644

 

 -- The new values are concatenated with ' triggered !'
diff --git a/src/backend/nodes/queryjumblefuncs.c b/src/backend/nodes/queryjumblefuncs.c
index e489bfceb5..ee3d67c832 100644
--- a/src/backend/nodes/queryjumblefuncs.c
+++ b/src/backend/nodes/queryjumblefuncs.c
@@ -135,6 +135,33 @@ JumbleQuery(Query *query)
 	return jstate;
 }
 
+JumbleState *
index 9300c7b9ab..598bab7d1f 100644

 /* GUC parameters */

 static Node *transformExprRecurse(ParseState *pstate, Node *expr);
@@ -99,6 +103,327 @@ static Expr *make_distinct_op(ParseState *pstate, List *opname,
 static Node *make_nulltest_from_distinct(ParseState *pstate,
 										 A_Expr *distincta, Node *arg);
 
+ * Hash function to find candidate clauses.
+	Assert(keysize == sizeof(OrClauseGroupKey));
+	hash += ((uint64) key->opno + (uint64) key->exprtype);
+	return (uint32) (hash % UINT32_MAX);
+		 * Transformation only works with both side type is not
+		 * { array | composite | domain | record }.
+		 * Also, forbid it for volatile expressions.
+		exprtype = exprType(nconst_expr);
+		if (type_is_rowtype(exprType(const_expr)) ||
+			type_is_rowtype(exprtype) ||
+			contain_volatile_functions((Node *) nconst_expr))
+		hashkey.exprtype = exprtype;
+		array_type = OidIsValid(scalar_type) ? get_array_type(scalar_type) :
+											   InvalidOid;
 
 /*
  * transformExpr -
@@ -212,7 +537,7 @@ transformExprRecurse(ParseState *pstate, Node *expr)
 			}
 
 		case T_BoolExpr:
 
 		case T_FuncCall:
index 7fe58518d7..ddda2d3c48 100644
index da10b43dac..6876d73392 100644
 
index 00b5092713..d28bf617db 100644
index f1c55c8067..a9ae048af5 100644

 extern PGDLLIMPORT bool query_id_enabled;
diff --git a/src/include/optimizer/optimizer.h b/src/include/optimizer/optimizer.h
index 7b63c5cf71..35ab577501 100644
--- a/src/include/optimizer/optimizer.h
+++ b/src/include/optimizer/optimizer.h
@@ -50,6 +50,7 @@ struct PlannedStmt;
 struct ParamListInfoData;
 struct HeapTupleData;

 /* in path/clausesel.c: */
 
index 79fa117cb5..b8653c09ea 100644
 
 SELECT * FROM tenk1

index 130a924228..684886336c 100644
 
index 9c08d0134c..256ed8acb5 100644

 

 

 

 drop table hp2;
index abc944e8b8..3ec614c437 100644
index 10903bdab0..6f55b9e3ec 100644

 

 
index 9be7aca2b8..1f9029b5b2 100644

 
 
index e1db2025db..353deecef0 100644

+
 
index 91433d439b..adae668b37 100644

From 2b157a43fa2e88650cc3b25c523068b15ac99ea6 Mon Sep 17 00:00:00 2001
From: "Andrey V. Lepikhov" <[email-masked]>
Date: Wed, 24 Jan 2024 14:07:17 +0700
Subject: [PATCH 2/2] Teach generate_bitmap_or_paths to build BitmapOr paths
 over SAOP clauses.

Likewise OR clauses, discover SAOP array and try to split its elements
between smaller sized arrays to fit a set of partial indexes.
---
 src/backend/optimizer/path/indxpath.c     | 272 +++++++++++++++++----
 src/backend/optimizer/util/clauses.c      |   1 +
 src/backend/optimizer/util/predtest.c     |  94 ++++++++
 src/backend/optimizer/util/restrictinfo.c |  13 +
 src/include/optimizer/optimizer.h         |  10 +
 src/include/optimizer/restrictinfo.h      |   1 +
 src/test/regress/expected/select.out      | 282 ++++++++++++++++++++++
 src/test/regress/sql/select.sql           |  82 +++++++
 8 files changed, 702 insertions(+), 53 deletions(-)

diff --git a/src/backend/optimizer/path/indxpath.c b/src/backend/optimizer/path/indxpath.c
index 32c6a8bbdc..7062ec57dd 100644
--- a/src/backend/optimizer/path/indxpath.c
+++ b/src/backend/optimizer/path/indxpath.c
@@ -1220,11 +1220,146 @@ build_paths_for_OR(PlannerInfo *root, RelOptInfo *rel,
 	return result;
 }
 
+/*
+ * Building index paths over SAOP clause differs from the logic of OR clauses.
+ * Here we iterate across all the array elements and split them to SAOPs,
+ * corresponding to different indexes. We must match each element to an index.
+ */
+static List *
+build_paths_for_SAOP(PlannerInfo *root, RelOptInfo *rel, RestrictInfo *rinfo,
+					 List *other_clauses)
+{
+	List			   *result = NIL;
+	List			   *predicate_lists = NIL;
+	ListCell		   *lc;
+	PredicatesData	   *pd;
+	ScalarArrayOpExpr  *saop = (ScalarArrayOpExpr *) rinfo->clause;
+
+	Assert(saop->useOr);
+
+	/* Collect predicates */
+	foreach(lc, rel->indexlist)
+	{
+		IndexOptInfo *index = (IndexOptInfo *) lfirst(lc);
+
+		/* Take into consideration partial indexes supporting bitmap scans */
+		if (!index->amhasgetbitmap || index->indpred == NIL || index->predOK)
+			continue;
+
+		pd = palloc0(sizeof(PredicatesData));
+		pd->id = foreach_current_index(lc);
+		/* The trick with reducing recursion is stolen from predicate_implied_by */
+		pd->predicate = list_length(index->indpred) == 1 ?
+										(Node *) linitial(index->indpred) :
+										(Node *) index->indpred;
+		predicate_lists = lappend(predicate_lists, (void *) pd);
+	}
+
+	/* Split the array data according to index predicates. */
+	if (predicate_lists == NIL ||
+		!saop_covered_by_predicates(saop, predicate_lists))
+		return NIL;
+
+	other_clauses = list_delete_ptr(other_clauses, rinfo);
+
+	foreach(lc, predicate_lists)
+	{
+		PredicatesData *pd = (PredicatesData *) lfirst(lc);
+		IndexOptInfo   *index;
+		IndexClauseSet	clauseset;
+		List		   *indexpaths;
+		RestrictInfo   *rinfo1;
+		Expr		   *clause;
+
+		if (pd->elems == NIL)
+			continue;
+
+		index = list_nth(rel->indexlist, pd->id);
+		clause = (Expr *) estimate_expression_value(root, (Node *) pd->saop);
+
+		/*
+		 * Create new RestrictInfo. It maybe more heavy than just copy node, but
+		 * remember some internals: the serial number, selectivity cache etc.
+		 */
+		rinfo1 = make_restrictinfo(root, clause,
+								   rinfo->is_pushed_down,
+								   rinfo->has_clone,
+								   rinfo->is_clone,
+								   rinfo->pseudoconstant,
+								   rinfo->security_level,
+								   rinfo->required_relids,
+								   rinfo->incompatible_relids,
+								   rinfo->outer_relids);
+
+		if (!predicate_implied_by(index->indpred, list_make1(rinfo1), true))
+			elog(ERROR, "Logical mistake in OR <-> ANY transformation code");
+
+		if (predicate_implied_by(index->indpred, other_clauses, false))
+			return NIL;
+
+		/* Time to generate index paths */
+		MemSet(&clauseset, 0, sizeof(clauseset));
+		match_clauses_to_index(root, list_make1(rinfo1), index, &clauseset);
+		match_clauses_to_index(root, other_clauses, index, &clauseset);
+
+		/* Predicate has found already. So, it is ok for the empty match */
+
+		/*
+		 * Construct paths if possible.
+		 */
+		indexpaths = build_index_paths(root, rel,
+									   index, &clauseset,
+									   true,
+									   ST_BITMAPSCAN,
+									   NULL,
+									   NULL);
+		result = lappend(result, indexpaths);
+	}
+	return result;
+}
+
+static List *
+generate_saop_pathlist(PlannerInfo *root, RelOptInfo *rel,
+					   RestrictInfo *rinfo, List *all_clauses)
+{
+	List	   *pathlist = NIL;
+	Path	   *bitmapqual;
+	List	   *indlist;
+	ListCell   *lc;
+
+	if (!enable_or_transformation)
+		return NIL;
+
+
+	/*
+	 * We must be able to match at least one index to each element of
+	 * the array, else we can't use it.
+	 */
+	indlist = build_paths_for_SAOP(root, rel, rinfo, all_clauses);
+	if (indlist == NIL)
+		return NIL;
+
+	/*
+	 * OK, pick the most promising AND combination, and add it to
+	 * pathlist.
+	 */
+	foreach (lc, indlist)
+	{
+		List *plist = lfirst_node(List, lc);
+
+		bitmapqual = choose_bitmap_and(root, rel, plist);
+		pathlist = lappend(pathlist, bitmapqual);
+	}
+
+	return pathlist;
+}
+
 /*
  * generate_bitmap_or_paths
- *		Look through the list of clauses to find OR clauses, and generate
- *		a BitmapOrPath for each one we can handle that way.  Return a list
- *		of the generated BitmapOrPaths.
+ *		Look through the list of clauses to find OR and SAOP clauses, and
+ *		Each saop clause are splitted to be covered by partial indexes.
+ *		generate a BitmapOrPath for each one we can handle that way.
+ *		Return a list of the generated BitmapOrPaths.
  *
  * other_clauses is a list of additional clauses that can be assumed true
  * for the purpose of generating indexquals, but are not to be searched for
@@ -1247,68 +1382,99 @@ generate_bitmap_or_paths(PlannerInfo *root, RelOptInfo *rel,
 	foreach(lc, clauses)
 	{
 		RestrictInfo *rinfo = lfirst_node(RestrictInfo, lc);
-		List	   *pathlist;
+		List	   *pathlist = NIL;
 		Path	   *bitmapqual;
 		ListCell   *j;
 
-		/* Ignore RestrictInfos that aren't ORs */
-		if (!restriction_is_or_clause(rinfo))
+		if (restriction_is_saop_clause(rinfo))
+		{
+			pathlist = generate_saop_pathlist(root, rel, rinfo,
+											  all_clauses);
+		}
+		else if (!restriction_is_or_clause(rinfo))
+			/* Ignore RestrictInfos that aren't ORs */
 			continue;
-
-		/*
-		 * We must be able to match at least one index to each of the arms of
-		 * the OR, else we can't use it.
-		 */
-		pathlist = NIL;
-		foreach(j, ((BoolExpr *) rinfo->orclause)->args)
+		else
 		{
-			Node	   *orarg = (Node *) lfirst(j);
-			List	   *indlist;
-
-			/* OR arguments should be ANDs or sub-RestrictInfos */
-			if (is_andclause(orarg))
+			/*
+			 * We must be able to match at least one index to each of the arms of
+			 * the OR, else we can't use it.
+			 */
+			foreach(j, ((BoolExpr *) rinfo->orclause)->args)
 			{
-				List	   *andargs = ((BoolExpr *) orarg)->args;
+				Node	   *orarg = (Node *) lfirst(j);
+				List	   *indlist;
 
-				indlist = build_paths_for_OR(root, rel,
-											 andargs,
-											 all_clauses);
+				/* OR arguments should be ANDs or sub-RestrictInfos */
+				if (is_andclause(orarg))
+				{
+					List	   *andargs = ((BoolExpr *) orarg)->args;
 
-				/* Recurse in case there are sub-ORs */
-				indlist = list_concat(indlist,
-									  generate_bitmap_or_paths(root, rel,
-															   andargs,
-															   all_clauses));
-			}
-			else
-			{
-				RestrictInfo *ri = castNode(RestrictInfo, orarg);
-				List	   *orargs;
+					indlist = build_paths_for_OR(root, rel,
+												 andargs,
+												 all_clauses);
 
-				Assert(!restriction_is_or_clause(ri));
-				orargs = list_make1(ri);
+					/* Recurse in case there are sub-ORs */
+					indlist = list_concat(indlist,
+										  generate_bitmap_or_paths(root, rel,
+																   andargs,
+																   all_clauses));
+				}
+				else
+				{
+					RestrictInfo *ri = castNode(RestrictInfo, orarg);
+					List	   *orargs;
 
-				indlist = build_paths_for_OR(root, rel,
-											 orargs,
-											 all_clauses);
-			}
+					Assert(!restriction_is_or_clause(ri));
 
-			/*
-			 * If nothing matched this arm, we can't do anything with this OR
-			 * clause.
-			 */
-			if (indlist == NIL)
-			{
-				pathlist = NIL;
-				break;
-			}
+					orargs = list_make1(ri);
 
-			/*
-			 * OK, pick the most promising AND combination, and add it to
-			 * pathlist.
-			 */
-			bitmapqual = choose_bitmap_and(root, rel, indlist);
-			pathlist = lappend(pathlist, bitmapqual);
+					if (restriction_is_saop_clause(ri))
+					{
+						List *paths;
+
+						paths = generate_saop_pathlist(root, rel, ri,
+														 all_clauses);
+
+						if (paths != NIL)
+						{
+							/*
+							 * Add paths to pathlist and immediately jump to the
+							 * next element of the OR clause.
+							 */
+							pathlist = list_concat(pathlist, paths);
+							continue;
+						}
+
+						/*
+						 * Pass down out of this if construction:
+						 * If saop isn't covered by partial indexes, try to
+						 * build scan path for the saop as a whole.
+						 */
+					}
+
+					indlist = build_paths_for_OR(root, rel,
+												 orargs,
+												 all_clauses);
+				}
+
+				/*
+				 * If nothing matched this arm, we can't do anything with this OR
+				 * clause.
+				 */
+				if (indlist == NIL)
+				{
+					pathlist = NIL;
+					break;
+				}
+
+				/*
+				 * OK, pick the most promising AND combination, and add it to
+				 * pathlist.
+				 */
+				bitmapqual = choose_bitmap_and(root, rel, indlist);
+				pathlist = lappend(pathlist, bitmapqual);
+			}
 		}
 
 		/*
diff --git a/src/backend/optimizer/util/clauses.c b/src/backend/optimizer/util/clauses.c
index 94eb56a1e7..35a46ca979 100644
--- a/src/backend/optimizer/util/clauses.c
+++ b/src/backend/optimizer/util/clauses.c
@@ -3708,6 +3708,7 @@ contain_non_const_walker(Node *node, void *context)
 	if (IsA(node, List))
 		return expression_tree_walker(node, contain_non_const_walker, context);
 	/* Otherwise, abort the tree traversal and return true */
+
 	return true;
 }
 
diff --git a/src/backend/optimizer/util/predtest.c b/src/backend/optimizer/util/predtest.c
index c37b416e24..274fac8a3a 100644
--- a/src/backend/optimizer/util/predtest.c
+++ b/src/backend/optimizer/util/predtest.c
@@ -112,6 +112,100 @@ static Oid	get_btree_test_op(Oid pred_op, Oid clause_op, bool refute_it);
 static void InvalidateOprProofCacheCallBack(Datum arg, int cacheid, uint32 hashvalue);

+/*
+ * Could this ANY () expression can be split into a set of ANYs over partial
+ * indexes? If yes, return these saops in the PredicatesData structure.
+ */
+bool
+saop_covered_by_predicates(ScalarArrayOpExpr *saop, List *predicate_lists)
+{
+	ListCell		   *lc;
+	PredIterInfoData	clause_info;
+	bool				result = false;
+	bool				isConstArray;
+
+	Assert(IsA(saop, ScalarArrayOpExpr));
+
+	if (predicate_classify((Node *) saop, &clause_info) != CLASS_OR)
+		return false;
+
+	iterate_begin(pitem, (Node *) saop, clause_info)
+	{
+		result = false;
+
+		foreach(lc, predicate_lists)
+		{
+			PredicatesData *pd = (PredicatesData *) lfirst(lc);
+
+			if (!predicate_implied_by_recurse(pitem, pd->predicate, false))
+				continue;
+
+			/* Predicate is found. Add the elem to the saop clause */
+			Assert(IsA(pitem, OpExpr));
+
+			/* Extract constant from the expression */
+			pd->elems = lappend(pd->elems,
+					copyObject(lsecond_node(Const, ((OpExpr *) pitem)->args)));
+			result = true;
+			break;
+		}
+
+		if (!result)
+			/*
+			 * The element doesn't fit any index. Interrupt the process immediately
+			 */
+			break;
+	}
+	iterate_end(clause_info);
+
+	if (!result)
+		return false;
+
+	/* Build saops, separately for each index */
+	isConstArray = IsA(lsecond(saop->args), Const) ? true : false;
+
+	foreach(lc, predicate_lists)
+	{
+		PredicatesData *pd = (PredicatesData *) lfirst(lc);
+		ArrayType	   *arrayval = NULL;
+		ArrayExpr	   *c = NULL;
+
+		if (pd->elems == NIL)
+			continue;
+
+		if (isConstArray)
+		{
+			Const	   *arrayconst = lsecond_node(Const, saop->args);
+
+			arrayval = DatumGetArrayTypeP(arrayconst->constvalue);
+			c = makeNode(ArrayExpr);
+			c->array_collid = arrayconst->constcollid;
+			c->array_typeid = arrayconst->consttype;
+			c->element_typeid = arrayval->elemtype;
+			c->elements = pd->elems;
+			c->location = -1;
+			c->multidims = false;
+		}
+		else
+		{
+			Assert(IsA(lsecond(saop->args), ArrayExpr));
+		}
+
+		if (pd->saop == NULL)
+		{
+			/* First time initialization */
+			pd->saop = makeNode(ScalarArrayOpExpr);
+			memcpy(pd->saop, saop, sizeof(ScalarArrayOpExpr));
+			Assert(IsA(lsecond(saop->args), ArrayExpr) ||
+				   IsA(lsecond(saop->args), Const));
+			Assert(c != NULL);
+			pd->saop->args = list_make2(linitial(saop->args), c);
+		}
+	}
+
+	return true;
+}
+
 /*
  * predicate_implied_by
  *	  Recursively checks whether the clauses in clause_list imply that the
diff --git a/src/backend/optimizer/util/restrictinfo.c b/src/backend/optimizer/util/restrictinfo.c
index 0b406e9334..627596a34c 100644
--- a/src/backend/optimizer/util/restrictinfo.c
+++ b/src/backend/optimizer/util/restrictinfo.c
@@ -421,6 +421,19 @@ restriction_is_or_clause(RestrictInfo *restrictinfo)
 		return false;
 }
 
+bool
+restriction_is_saop_clause(RestrictInfo *restrictinfo)
+{
+	if (IsA(restrictinfo->clause, ScalarArrayOpExpr))
+	{
+		ScalarArrayOpExpr *saop = (ScalarArrayOpExpr *) restrictinfo->clause;
+
+		if (saop->useOr)
+			return true;
+	}
+	return false;
+}
+
 /*
  * restriction_is_securely_promotable
  *
diff --git a/src/include/optimizer/optimizer.h b/src/include/optimizer/optimizer.h
index 35ab577501..92c8b14352 100644
--- a/src/include/optimizer/optimizer.h
+++ b/src/include/optimizer/optimizer.h
@@ -160,6 +160,16 @@ extern List *expand_function_arguments(List *args, bool include_out_arguments,
 
 /* in util/predtest.c: */
 
+typedef struct PredicatesData
+{
+	int					id;
+	Node			   *predicate;
+	List			   *elems;
+	ScalarArrayOpExpr  *saop;
+} PredicatesData;
+
+extern bool saop_covered_by_predicates(ScalarArrayOpExpr *saop,
+									  List *predicate_lists);
 extern bool predicate_implied_by(List *predicate_list, List *clause_list,
 								 bool weak);
 extern bool predicate_refuted_by(List *predicate_list, List *clause_list,
diff --git a/src/include/optimizer/restrictinfo.h b/src/include/optimizer/restrictinfo.h
index 1b42c832c5..2cd5fbf943 100644
--- a/src/include/optimizer/restrictinfo.h
+++ b/src/include/optimizer/restrictinfo.h
@@ -34,6 +34,7 @@ extern RestrictInfo *make_restrictinfo(PlannerInfo *root,
 									   Relids outer_relids);
 extern RestrictInfo *commute_restrictinfo(RestrictInfo *rinfo, Oid comm_op);
 extern bool restriction_is_or_clause(RestrictInfo *restrictinfo);
+extern bool restriction_is_saop_clause(RestrictInfo *restrictinfo);
 extern bool restriction_is_securely_promotable(RestrictInfo *restrictinfo,
 											   RelOptInfo *rel);
 extern List *get_actual_clauses(List *restrictinfo_list);
diff --git a/src/test/regress/expected/select.out b/src/test/regress/expected/select.out
index 33a6dceb0e..070202b0f0 100644
--- a/src/test/regress/expected/select.out
+++ b/src/test/regress/expected/select.out
@@ -907,6 +907,288 @@ select unique1, unique2 from onek2
        0 |     998
 (2 rows)
 
+SET enable_seqscan TO off;
+SET enable_indexscan TO off; -- Only BitmapScan is a subject matter here
+SET enable_or_transformation = 'off';
+explain (costs off)
+SELECT count(*) FROM onek2 WHERE stringu1 = 'A' OR stringu1 = 'J';
+                                QUERY PLAN                                
+--------------------------------------------------------------------------
+ Aggregate
+   ->  Bitmap Heap Scan on onek2
+         Recheck Cond: ((stringu1 < 'B'::name) OR (stringu1 = 'J'::name))
+         Filter: ((stringu1 = 'A'::name) OR (stringu1 = 'J'::name))
+         ->  BitmapOr
+               ->  Bitmap Index Scan on onek2_u2_prtl
+               ->  Bitmap Index Scan on onek2_stu1_prtl
+                     Index Cond: (stringu1 = 'J'::name)
+(8 rows)
+
+-- Without the transformation only seqscan possible here
+explain (costs off)
+SELECT unique2, stringu1 FROM onek2
+WHERE unique2 < 1 AND stringu1 IN ('A','J') AND stringu1 < 'Z';
+                                         QUERY PLAN                                          
+---------------------------------------------------------------------------------------------
+ Seq Scan on onek2
+   Filter: ((unique2 < 1) AND (stringu1 = ANY ('{A,J}'::name[])) AND (stringu1 < 'Z'::name))
+(2 rows)
+
+-- Use partial indexes
+explain (costs off)
+SELECT count(*) FROM onek2
+WHERE stringu1 IN ('B','J') AND (stringu1 = 'A' OR unique1 = 1);
+                                             QUERY PLAN                                             
+----------------------------------------------------------------------------------------------------
+ Aggregate
+   ->  Bitmap Heap Scan on onek2
+         Recheck Cond: ((stringu1 < 'B'::name) OR (unique1 = 1))
+         Filter: ((stringu1 = ANY ('{B,J}'::name[])) AND ((stringu1 = 'A'::name) OR (unique1 = 1)))
+         ->  BitmapOr
+               ->  Bitmap Index Scan on onek2_u2_prtl
+               ->  Bitmap Index Scan on onek2_u1_prtl
+                     Index Cond: (unique1 = 1)
+(8 rows)
+
+explain (costs off)
+SELECT unique2, stringu1 FROM onek2
+WHERE unique1 < 1 OR (stringu1 = 'A' OR stringu1 = 'J');
+                                     QUERY PLAN                                      
+-------------------------------------------------------------------------------------
+ Bitmap Heap Scan on onek2
+   Recheck Cond: ((unique1 < 1) OR (stringu1 < 'B'::name) OR (stringu1 = 'J'::name))
+   Filter: ((unique1 < 1) OR (stringu1 = 'A'::name) OR (stringu1 = 'J'::name))
+   ->  BitmapOr
+         ->  Bitmap Index Scan on onek2_u1_prtl
+               Index Cond: (unique1 < 1)
+         ->  Bitmap Index Scan on onek2_u2_prtl
+         ->  Bitmap Index Scan on onek2_stu1_prtl
+               Index Cond: (stringu1 = 'J'::name)
+(9 rows)
+
+explain (costs off)
+SELECT unique2, stringu1 FROM onek2
+WHERE unique1 = 1 OR unique2 = PI()::integer;
+                 QUERY PLAN                 
+--------------------------------------------
+ Seq Scan on onek2
+   Filter: ((unique1 = 1) OR (unique2 = 3))
+(2 rows)
+
+RESET enable_or_transformation;
+-- OR <-> ANY transformation must find a path with partial indexes scan
+-- regardless the clause representation.
+explain (costs off)
+SELECT count(*) FROM onek2 WHERE stringu1 = 'A' OR stringu1 = 'J';
+                                     QUERY PLAN                                     
+------------------------------------------------------------------------------------
+ Aggregate
+   ->  Bitmap Heap Scan on onek2
+         Recheck Cond: ((stringu1 = ANY ('{J}'::name[])) OR (stringu1 < 'B'::name))
+         Filter: (stringu1 = ANY ('{A,J}'::name[]))
+         ->  BitmapOr
+               ->  Bitmap Index Scan on onek2_stu1_prtl
+                     Index Cond: (stringu1 = ANY ('{J}'::name[]))
+               ->  Bitmap Index Scan on onek2_u2_prtl
+(8 rows)
+
+explain (costs off)
+SELECT count(*) FROM onek2 WHERE stringu1 IN ('A','J');
+                                     QUERY PLAN                                     
+------------------------------------------------------------------------------------
+ Aggregate
+   ->  Bitmap Heap Scan on onek2
+         Recheck Cond: ((stringu1 = ANY ('{J}'::name[])) OR (stringu1 < 'B'::name))
+         Filter: (stringu1 = ANY ('{A,J}'::name[]))
+         ->  BitmapOr
+               ->  Bitmap Index Scan on onek2_stu1_prtl
+                     Index Cond: (stringu1 = ANY ('{J}'::name[]))
+               ->  Bitmap Index Scan on onek2_u2_prtl
+(8 rows)
+
+explain (costs off)
+SELECT count(*) FROM onek2 WHERE stringu1 = ANY ('{A,J}');
+                                     QUERY PLAN                                     
+------------------------------------------------------------------------------------
+ Aggregate
+   ->  Bitmap Heap Scan on onek2
+         Recheck Cond: ((stringu1 = ANY ('{J}'::name[])) OR (stringu1 < 'B'::name))
+         Filter: (stringu1 = ANY ('{A,J}'::name[]))
+         ->  BitmapOr
+               ->  Bitmap Index Scan on onek2_stu1_prtl
+                     Index Cond: (stringu1 = ANY ('{J}'::name[]))
+               ->  Bitmap Index Scan on onek2_u2_prtl
+(8 rows)
+
+explain (costs off)
+SELECT count(*) FROM onek2 WHERE stringu1 IN ('A') OR stringu1 IN ('J');
+                                     QUERY PLAN                                     
+------------------------------------------------------------------------------------
+ Aggregate
+   ->  Bitmap Heap Scan on onek2
+         Recheck Cond: ((stringu1 = ANY ('{J}'::name[])) OR (stringu1 < 'B'::name))
+         Filter: (stringu1 = ANY ('{A,J}'::name[]))
+         ->  BitmapOr
+               ->  Bitmap Index Scan on onek2_stu1_prtl
+                     Index Cond: (stringu1 = ANY ('{J}'::name[]))
+               ->  Bitmap Index Scan on onek2_u2_prtl
+(8 rows)
+
+-- Don't scan partial indexes because of extra value.
+explain (costs off)
+SELECT count(*) FROM onek2 WHERE stringu1 IN ('A', 'J', 'C');
+                      QUERY PLAN                      
+------------------------------------------------------
+ Aggregate
+   ->  Seq Scan on onek2
+         Filter: (stringu1 = ANY ('{A,J,C}'::name[]))
+(3 rows)
+
+explain (costs off)
+SELECT unique2 FROM onek2
+WHERE stringu1 IN ('A', 'A') AND (stringu1 = 'A' OR stringu1 = 'A');
+                                      QUERY PLAN                                       
+---------------------------------------------------------------------------------------
+ Bitmap Heap Scan on onek2
+   Recheck Cond: (stringu1 < 'B'::name)
+   Filter: ((stringu1 = ANY ('{A,A}'::name[])) AND (stringu1 = ANY ('{A,A}'::name[])))
+   ->  Bitmap Index Scan on onek2_u2_prtl
+(4 rows)
+
+explain (costs off)
+SELECT unique2, stringu1 FROM onek2
+WHERE unique2 < 1 AND stringu1 IN ('A','J') AND stringu1 < 'Z';
+                                                          QUERY PLAN                                                           
+-------------------------------------------------------------------------------------------------------------------------------
+ Bitmap Heap Scan on onek2
+   Recheck Cond: (((stringu1 = ANY ('{J}'::name[])) AND (stringu1 < 'Z'::name)) OR ((unique2 < 1) AND (stringu1 < 'B'::name)))
+   Filter: ((unique2 < 1) AND (stringu1 = ANY ('{A,J}'::name[])))
+   ->  BitmapOr
+         ->  Bitmap Index Scan on onek2_stu1_prtl
+               Index Cond: ((stringu1 = ANY ('{J}'::name[])) AND (stringu1 < 'Z'::name))
+         ->  Bitmap Index Scan on onek2_u2_prtl
+               Index Cond: (unique2 < 1)
+(8 rows)
+
+explain (costs off)
+SELECT unique2, stringu1 FROM onek2
+WHERE unique1 = 1 OR unique1 = PI()::integer;
+                    QUERY PLAN                    
+--------------------------------------------------
+ Bitmap Heap Scan on onek2
+   Recheck Cond: ((unique1 = 3) OR (unique1 = 1))
+   ->  BitmapOr
+         ->  Bitmap Index Scan on onek2_u1_prtl
+               Index Cond: (unique1 = 3)
+         ->  Bitmap Index Scan on onek2_u1_prtl
+               Index Cond: (unique1 = 1)
+(7 rows)
+
+explain (costs off)
+SELECT unique2, stringu1 FROM onek2
+WHERE unique1 IN (1, PI()::integer); -- TODO: why it is differs from previous example?
+                        QUERY PLAN                        
+----------------------------------------------------------
+ Bitmap Heap Scan on onek2
+   Recheck Cond: (unique1 = ANY ('{1,3}'::integer[]))
+   ->  Bitmap Index Scan on onek2_u1_prtl
+         Index Cond: (unique1 = ANY ('{1,3}'::integer[]))
+(4 rows)
+
+-- Don't apply the optimization to clauses, containing volatile functions
+EXPLAIN (COSTS OFF)
+SELECT unique2,stringu1 FROM onek2
+WHERE unique1 = (random()*2)::integer OR unique1 = (random()*3)::integer;
+                                                             QUERY PLAN                                                             
+------------------------------------------------------------------------------------------------------------------------------------
+ Seq Scan on onek2
+   Filter: ((unique1 = ((random() * '2'::double precision))::integer) OR (unique1 = ((random() * '3'::double precision))::integer))
+(2 rows)
+
+EXPLAIN (COSTS OFF)
+SELECT unique2,stringu1 FROM onek2
+WHERE unique1 IN ((random()*2)::integer, (random()*3)::integer);
+                                                           QUERY PLAN                                                            
+---------------------------------------------------------------------------------------------------------------------------------
+ Seq Scan on onek2
+   Filter: (unique1 = ANY (ARRAY[((random() * '2'::double precision))::integer, ((random() * '3'::double precision))::integer]))
+(2 rows)
+
+-- Combine different saops. Soe of them doesnt' fit a set of partial indexes,
+-- but other fits.
+-- Unfortunately, we don't combine saop and OR clauses so far.
+EXPLAIN (COSTS OFF)
+SELECT unique2,stringu1 FROM onek2
+WHERE
+  unique1 IN (1,2,21) AND
+  (stringu1 IN ('A','J') OR unique1 IN (3,4) OR stringu1 = 'J');
+                                                                                          QUERY PLAN                                                                                          
+----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
+ Bitmap Heap Scan on onek2
+   Recheck Cond: ((stringu1 = ANY ('{J}'::name[])) OR (stringu1 < 'B'::name) OR ((unique1 = ANY ('{3,4}'::integer[])) AND (unique1 = ANY ('{1,2,21}'::integer[]))) OR (stringu1 = 'J'::name))
+   Filter: ((unique1 = ANY ('{1,2,21}'::integer[])) AND ((stringu1 = ANY ('{A,J}'::name[])) OR (unique1 = ANY ('{3,4}'::integer[])) OR (stringu1 = 'J'::name)))
+   ->  BitmapOr
+         ->  Bitmap Index Scan on onek2_stu1_prtl
+               Index Cond: (stringu1 = ANY ('{J}'::name[]))
+         ->  Bitmap Index Scan on onek2_u2_prtl
+         ->  Bitmap Index Scan on onek2_u1_prtl
+               Index Cond: ((unique1 = ANY ('{3,4}'::integer[])) AND (unique1 = ANY ('{1,2,21}'::integer[])))
+         ->  Bitmap Index Scan on onek2_stu1_prtl
+               Index Cond: (stringu1 = 'J'::name)
+(11 rows)
+
+-- Check recursive combination of OR and SAOP expressions
+explain (costs off)
+SELECT unique2, stringu1 FROM onek2
+WHERE unique1 < 1 OR (stringu1 = 'A' OR stringu1 = 'J');
+                                          QUERY PLAN                                           
+-----------------------------------------------------------------------------------------------
+ Bitmap Heap Scan on onek2
+   Recheck Cond: ((stringu1 = ANY ('{J}'::name[])) OR (stringu1 < 'B'::name) OR (unique1 < 1))
+   Filter: ((stringu1 = ANY ('{A,J}'::name[])) OR (unique1 < 1))
+   ->  BitmapOr
+         ->  Bitmap Index Scan on onek2_stu1_prtl
+               Index Cond: (stringu1 = ANY ('{J}'::name[]))
+         ->  Bitmap Index Scan on onek2_u2_prtl
+         ->  Bitmap Index Scan on onek2_u1_prtl
+               Index Cond: (unique1 < 1)
+(9 rows)
+
+explain (costs off)
+SELECT unique2, stringu1 FROM onek2
+WHERE (unique1 < 1 OR stringu1 IN ('A','J'));
+                                          QUERY PLAN                                           
+-----------------------------------------------------------------------------------------------
+ Bitmap Heap Scan on onek2
+   Recheck Cond: ((stringu1 = ANY ('{J}'::name[])) OR (stringu1 < 'B'::name) OR (unique1 < 1))
+   Filter: ((stringu1 = ANY ('{A,J}'::name[])) OR (unique1 < 1))
+   ->  BitmapOr
+         ->  Bitmap Index Scan on onek2_stu1_prtl
+               Index Cond: (stringu1 = ANY ('{J}'::name[]))
+         ->  Bitmap Index Scan on onek2_u2_prtl
+         ->  Bitmap Index Scan on onek2_u1_prtl
+               Index Cond: (unique1 < 1)
+(9 rows)
+
+-- Although SAOP doesn't fit partial indexes fully, we can use anded OR clause
+-- to scan another couple of partial indexes.
+explain (costs off)
+SELECT count(*) FROM onek2
+WHERE stringu1 IN ('B','J') AND (stringu1 = 'A' OR unique1 = 1);
+                                             QUERY PLAN                                             
+----------------------------------------------------------------------------------------------------
+ Aggregate
+   ->  Bitmap Heap Scan on onek2
+         Recheck Cond: ((stringu1 < 'B'::name) OR (unique1 = 1))
+         Filter: ((stringu1 = ANY ('{B,J}'::name[])) AND ((stringu1 = 'A'::name) OR (unique1 = 1)))
+         ->  BitmapOr
+               ->  Bitmap Index Scan on onek2_u2_prtl
+               ->  Bitmap Index Scan on onek2_u1_prtl
+                     Index Cond: (unique1 = 1)
+(8 rows)
+
+RESET enable_indexscan;
+RESET enable_seqscan;
 --
 -- Test some corner cases that have been known to confuse the planner
 --
diff --git a/src/test/regress/sql/select.sql b/src/test/regress/sql/select.sql
index 019f1e7673..0e650a2301 100644
--- a/src/test/regress/sql/select.sql
+++ b/src/test/regress/sql/select.sql
@@ -234,6 +234,88 @@ select unique1, unique2 from onek2
 select unique1, unique2 from onek2
   where (unique2 = 11 and stringu1 < 'B') or unique1 = 0;
 
+SET enable_seqscan TO off;
+SET enable_indexscan TO off; -- Only BitmapScan is a subject matter here
+SET enable_or_transformation = 'off';
+explain (costs off)
+SELECT count(*) FROM onek2 WHERE stringu1 = 'A' OR stringu1 = 'J';
+-- Without the transformation only seqscan possible here
+explain (costs off)
+SELECT unique2, stringu1 FROM onek2
+WHERE unique2 < 1 AND stringu1 IN ('A','J') AND stringu1 < 'Z';
+-- Use partial indexes
+explain (costs off)
+SELECT count(*) FROM onek2
+WHERE stringu1 IN ('B','J') AND (stringu1 = 'A' OR unique1 = 1);
+explain (costs off)
+SELECT unique2, stringu1 FROM onek2
+WHERE unique1 < 1 OR (stringu1 = 'A' OR stringu1 = 'J');
+explain (costs off)
+SELECT unique2, stringu1 FROM onek2
+WHERE unique1 = 1 OR unique2 = PI()::integer;
+RESET enable_or_transformation;
+
+-- OR <-> ANY transformation must find a path with partial indexes scan
+-- regardless the clause representation.
+explain (costs off)
+SELECT count(*) FROM onek2 WHERE stringu1 = 'A' OR stringu1 = 'J';
+explain (costs off)
+SELECT count(*) FROM onek2 WHERE stringu1 IN ('A','J');
+explain (costs off)
+SELECT count(*) FROM onek2 WHERE stringu1 = ANY ('{A,J}');
+explain (costs off)
+SELECT count(*) FROM onek2 WHERE stringu1 IN ('A') OR stringu1 IN ('J');
+
+-- Don't scan partial indexes because of extra value.
+explain (costs off)
+SELECT count(*) FROM onek2 WHERE stringu1 IN ('A', 'J', 'C');
+explain (costs off)
+SELECT unique2 FROM onek2
+WHERE stringu1 IN ('A', 'A') AND (stringu1 = 'A' OR stringu1 = 'A');
+
+explain (costs off)
+SELECT unique2, stringu1 FROM onek2
+WHERE unique2 < 1 AND stringu1 IN ('A','J') AND stringu1 < 'Z';
+explain (costs off)
+SELECT unique2, stringu1 FROM onek2
+WHERE unique1 = 1 OR unique1 = PI()::integer;
+explain (costs off)
+SELECT unique2, stringu1 FROM onek2
+WHERE unique1 IN (1, PI()::integer); -- TODO: why it is differs from previous example?
+
+-- Don't apply the optimization to clauses, containing volatile functions
+EXPLAIN (COSTS OFF)
+SELECT unique2,stringu1 FROM onek2
+WHERE unique1 = (random()*2)::integer OR unique1 = (random()*3)::integer;
+EXPLAIN (COSTS OFF)
+SELECT unique2,stringu1 FROM onek2
+WHERE unique1 IN ((random()*2)::integer, (random()*3)::integer);
+
+-- Combine different saops. Soe of them doesnt' fit a set of partial indexes,
+-- but other fits.
+-- Unfortunately, we don't combine saop and OR clauses so far.
+EXPLAIN (COSTS OFF)
+SELECT unique2,stringu1 FROM onek2
+WHERE
+  unique1 IN (1,2,21) AND
+  (stringu1 IN ('A','J') OR unique1 IN (3,4) OR stringu1 = 'J');
+
+-- Check recursive combination of OR and SAOP expressions
+explain (costs off)
+SELECT unique2, stringu1 FROM onek2
+WHERE unique1 < 1 OR (stringu1 = 'A' OR stringu1 = 'J');
+explain (costs off)
+SELECT unique2, stringu1 FROM onek2
+WHERE (unique1 < 1 OR stringu1 IN ('A','J'));
+-- Although SAOP doesn't fit partial indexes fully, we can use anded OR clause
+-- to scan another couple of partial indexes.
+explain (costs off)
+SELECT count(*) FROM onek2
+WHERE stringu1 IN ('B','J') AND (stringu1 = 'A' OR unique1 = 1);
+
+RESET enable_indexscan;
+RESET enable_seqscan;
+
 --
 -- Test some corner cases that have been known to confuse the planner
 --
-- 
2.43.0

---

From: jian he <[email-masked]>
Date: Sat, 10 Feb 2024 13:00:00 +0800

> opinion: Does it resolve the issue?
yes. It resolved the partial index performance degradation issue.
The v16, 0002 extra code overhead is limited.

Here is how I test it.
drop table if exists test;
create table test as (select (random()*100)::int x, (random()*1000) y
from generate_series(1,1000000) i);
create index test_x_1_y on test (y) where x = 1;
create index test_x_2_y on test (y) where x = 2;
create index test_x_3_y on test (y) where x = 3;
create index test_x_4_y on test (y) where x = 4;
create index test_x_5_y on test (y) where x = 5;
create index test_x_6_y on test (y) where x = 6;
create index test_x_7_y on test (y) where x = 7;
create index test_x_8_y on test (y) where x = 8;
create index test_x_9_y on test (y) where x = 9;
create index test_x_10_y on test (y) where x = 10;

set enable_or_transformation to on;
explain(analyze, costs off)
select * from test
where (x = 1 or x = 2 or x = 3 or x = 4 or x = 5 or x = 6 or x = 7 or
x = 8 or x = 9 or x = 10);

set enable_or_transformation to off;
explain(analyze, costs off)
select * from test
where (x = 1 or x = 2 or x = 3 or x = 4 or x = 5 or x = 6 or x = 7 or
x = 8 or x = 9 or x = 10);

FAILED: src/backend/postgres_lib.a.p/optimizer_path_indxpath.c.o
ccache cc -Isrc/backend/postgres_lib.a.p -Isrc/include
-I../../Desktop/pg_src/src8/postgres/src/include
-I/usr/include/libxml2 -fdiagnostics-color=always --coverage
-D_FILE_OFFSET_BITS=64 -Wall -Winvalid-pch -Werror -O0 -g
-fno-strict-aliasing -fwrapv -fexcess-precision=standard -D_GNU_SOURCE
-Wmissing-prototypes -Wpointer-arith -Werror=vla -Wendif-labels
-Wmissing-format-attribute -Wimplicit-fallthrough=3
-Wcast-function-type -Wshadow=compatible-local -Wformat-security
-Wdeclaration-after-statement -Wno-format-truncation
-Wno-stringop-truncation -Wunused-variable -Wuninitialized
-Werror=maybe-uninitialized -Wreturn-type
-DWRITE_READ_PARSE_PLAN_TREES -DCOPY_PARSE_PLAN_TREES
-DREALLOCATE_BITMAPSETS -DRAW_EXPRESSION_COVERAGE_TEST
-fno-omit-frame-pointer -fPIC -pthread -DBUILDING_DLL -MD -MQ
src/backend/postgres_lib.a.p/optimizer_path_indxpath.c.o -MF
src/backend/postgres_lib.a.p/optimizer_path_indxpath.c.o.d -o
src/backend/postgres_lib.a.p/optimizer_path_indxpath.c.o -c
../../Desktop/pg_src/src8/postgres/src/backend/optimizer/path/indxpath.c
../../Desktop/pg_src/src8/postgres/src/backend/optimizer/path/indxpath.c:
In function ‘build_paths_for_SAOP’:
../../Desktop/pg_src/src8/postgres/src/backend/optimizer/path/indxpath.c:1267:33:
error: declaration of ‘pd’ shadows a previous local
[-Werror=shadow=compatible-local]
 1267 |                 PredicatesData *pd = (PredicatesData *) lfirst(lc);
      |                                 ^~
../../Desktop/pg_src/src8/postgres/src/backend/optimizer/path/indxpath.c:1235:29:
note: shadowed declaration is here
 1235 |         PredicatesData     *pd;
      |                             ^~
cc1: all warnings being treated as errors
[32/126] Compiling C object src/backend/postgres_lib.a.p/utils_adt_ruleutils.c.o
ninja: build stopped: subcommand failed.

+ if (!predicate_implied_by(index->indpred, list_make1(rinfo1), true))
+ elog(ERROR, "Logical mistake in OR <-> ANY transformation code");
the error message seems not clear?
What is a "Logical mistake"?

static List *
build_paths_for_SAOP(PlannerInfo *root, RelOptInfo *rel, RestrictInfo *rinfo,
List *other_clauses)
I am not sure what's `other_clauses`, and `rinfo` refers to? adding
some comments would be great.

struct PredicatesData needs some comments, I think.

+bool
+saop_covered_by_predicates(ScalarArrayOpExpr *saop, List *predicate_lists)
+{
+ ListCell   *lc;
+ PredIterInfoData clause_info;
+ bool result = false;
+ bool isConstArray;
+
+ Assert(IsA(saop, ScalarArrayOpExpr));
is this Assert necessary?

For the function build_paths_for_SAOP, I think I understand the first
part of the code.
But I am not 100% sure of the second part of the `foreach(lc,
predicate_lists)` code.
more comments in `foreach(lc, predicate_lists)` would be helpful.

do you need to add `PredicatesData` to src/tools/pgindent/typedefs.list?

I also did some minor refactoring of generate_saop_pathlist.

type_is_rowtype does not check if the type is array type.
transformBoolExprOr the OR QUAL, the Const part cannot be an array.
simple example:
alter table tenk1 add column arr int[];
set enable_or_transformation to on;
EXPLAIN (COSTS OFF)
SELECT count(*) FROM tenk1
WHERE arr = '{1,2,3}' or arr = '{1,2}';

instead of let it go to `foreach (lc, entries)`,
we can reject the Const array at `foreach(lc, expr->args)`

also `foreach(lc, expr->args)` do we need to reject cases like
`contain_subplans((Node *) nconst_expr)`?
maybe let the nconst_expr be a Var node would be far more easier.

---

From: Andrei Lepikhov <[email-masked]>
Date: Mon, 12 Feb 2024 12:52:13 +0700

Thanks for the review!
It was the first version for discussion. Of course, refactoring and 
polishing cycles will be needed, even so we can discuss the general idea 
earlier.

>   1235 |         PredicatesData     *pd;
Thanks

> the error message seems not clear?
Yeah, have rewritten

> struct PredicatesData needs some comments, I think.
Added, not so much though
> is this Assert necessary?
Not sure. Moved it into another routine.
> more comments in `foreach(lc, predicate_lists)` would be helpful.
Done
> do you need to add `PredicatesData` to src/tools/pgindent/typedefs.list?
Done
> I also did some minor refactoring of generate_saop_pathlist.
Partially agree
> we can reject the Const array at `foreach(lc, expr->args)`
Yeah, I just think we can go further and transform two const arrays into 
a new one if we have the same clause and operator. In that case, we 
should allow it to pass through this cycle down to the classification stage.
> maybe let the nconst_expr be a Var node would be far more easier.
It's contradictory. On the one hand, we simplify the comparison 
procedure and can avoid expr jumbling at all. On the other hand - we 
restrict the feature. IMO, it would be better to unite such clauses
complex_clause1 IN (..) OR complex_clause1 IN (..)
into
complex_clause1 IN (.., ..)
and don't do duplicated work computing complex clauses.
In the attachment - the next version of the second patch.

-- 
regards,
Andrei Lepikhov
Postgres Professional
From c1e5fc35778acd01cca67e63fdf80c5605af03f2 Mon Sep 17 00:00:00 2001
From: "Andrey V. Lepikhov" <[email-masked]>
Date: Wed, 24 Jan 2024 14:07:17 +0700
Subject: [PATCH 2/2] Teach generate_bitmap_or_paths to build BitmapOr paths
 over SAOP clauses.

Likewise OR clauses, discover SAOP array and try to split its elements
between smaller sized arrays to fit a set of partial indexes.
---
 src/backend/optimizer/path/indxpath.c     | 304 ++++++++++++++++++----
 src/backend/optimizer/util/predtest.c     |  46 ++++
 src/backend/optimizer/util/restrictinfo.c |  13 +
 src/include/optimizer/optimizer.h         |  16 ++
 src/include/optimizer/restrictinfo.h      |   1 +
 src/test/regress/expected/select.out      | 282 ++++++++++++++++++++
 src/test/regress/sql/select.sql           |  82 ++++++
 src/tools/pgindent/typedefs.list          |   1 +
 8 files changed, 692 insertions(+), 53 deletions(-)

diff --git a/src/backend/optimizer/path/indxpath.c b/src/backend/optimizer/path/indxpath.c
index 32c6a8bbdc..5383cb76dc 100644
--- a/src/backend/optimizer/path/indxpath.c
+++ b/src/backend/optimizer/path/indxpath.c
@@ -32,6 +32,7 @@
 #include "optimizer/paths.h"
 #include "optimizer/prep.h"
 #include "optimizer/restrictinfo.h"
+#include "utils/array.h"
 #include "utils/lsyscache.h"
 #include "utils/selfuncs.h"
 
@@ -1220,11 +1221,177 @@ build_paths_for_OR(PlannerInfo *root, RelOptInfo *rel,
 	return result;
 }
 
+/*
+ * Building index paths over SAOP clause differs from the logic of OR clauses.
+ * Here we iterate across all the array elements and split them to SAOPs,
+ * corresponding to different indexes. We must match each element to an index.
+ */
+static List *
+build_paths_for_SAOP(PlannerInfo *root, RelOptInfo *rel, RestrictInfo *rinfo,
+					 List *other_clauses)
+{
+	List			   *result = NIL;
+	List			   *predicate_lists = NIL;
+	ListCell		   *lc;
+	PredicatesData	   *pd;
+	ScalarArrayOpExpr  *saop = (ScalarArrayOpExpr *) rinfo->clause;
+
+	Assert(IsA(saop, ScalarArrayOpExpr) && saop->useOr);
+
+	if (!IsA(lsecond(saop->args), Const))
+		/*
+		 * Has it practical outcome to merge arrays which couldn't constantified
+		 * before that step?
+		 */
+		return NIL;
+
+	/* Collect predicates */
+	foreach(lc, rel->indexlist)
+	{
+		IndexOptInfo *index = (IndexOptInfo *) lfirst(lc);
+
+		/* Take into consideration partial indexes supporting bitmap scans */
+		if (!index->amhasgetbitmap || index->indpred == NIL || index->predOK)
+			continue;
+
+		pd = palloc0(sizeof(PredicatesData));
+		pd->id = foreach_current_index(lc);
+		/* The trick with reducing recursion is stolen from predicate_implied_by */
+		pd->predicate = list_length(index->indpred) == 1 ?
+										(Node *) linitial(index->indpred) :
+										(Node *) index->indpred;
+		predicate_lists = lappend(predicate_lists, (void *) pd);
+	}
+
+	/* Split the array data according to index predicates. */
+	if (predicate_lists == NIL ||
+		!saop_covered_by_predicates(saop, predicate_lists))
+		return NIL;
+
+	other_clauses = list_delete_ptr(other_clauses, rinfo);
+
+	/*
+	 * Having incoming SAOP split to set of smaller SAOPs which can be applied
+	 * to partial indexes, generate paths for each one.
+	 */
+	foreach(lc, predicate_lists)
+	{
+		IndexOptInfo   *index;
+		IndexClauseSet	clauseset;
+		List		   *indexpaths;
+		RestrictInfo   *rinfo1 = NULL;
+		Expr		   *clause;
+
+		pd = (PredicatesData *) lfirst(lc);
+		if (pd->elems == NIL)
+			/* The index doesn't participate in this operation */
+			continue;
+		else
+		{
+			ArrayType		   *arrayval = NULL;
+			ArrayExpr		   *arr = NULL;
+			Const			   *arrayconst = lsecond_node(Const, saop->args);
+			ScalarArrayOpExpr  *dest = makeNode(ScalarArrayOpExpr);
+
+			/* Make up new array */
+			arrayval = DatumGetArrayTypeP(arrayconst->constvalue);
+			arr = makeNode(ArrayExpr);
+			arr->array_collid = arrayconst->constcollid;
+			arr->array_typeid = arrayconst->consttype;
+			arr->element_typeid = arrayval->elemtype;
+			arr->elements = pd->elems;
+			arr->location = -1;
+			arr->multidims = false;
+
+			/* Compose new SAOP, partially covering the source one */
+			memcpy(dest, saop, sizeof(ScalarArrayOpExpr));
+			dest->args = list_make2(linitial(saop->args), arr);
+
+			clause = (Expr *) estimate_expression_value(root, (Node *) dest);
+
+			/*
+			 * Create new RestrictInfo. It maybe more heavy than just copy node,
+			 * but remember some internals: the serial number, selectivity
+			 * cache etc.
+			 */
+			rinfo1 = make_restrictinfo(root, clause,
+									   rinfo->is_pushed_down,
+									   rinfo->has_clone,
+									   rinfo->is_clone,
+									   rinfo->pseudoconstant,
+									   rinfo->security_level,
+									   rinfo->required_relids,
+									   rinfo->incompatible_relids,
+									   rinfo->outer_relids);
+		}
+
+		index = list_nth(rel->indexlist, pd->id);
+		Assert(predicate_implied_by(index->indpred, list_make1(rinfo1), true));
+
+		/* Excluding partial indexes with predOK we make this statement false */
+		Assert(!predicate_implied_by(index->indpred, other_clauses, false));
+
+		/* Time to generate index paths */
+
+		MemSet(&clauseset, 0, sizeof(clauseset));
+		match_clauses_to_index(root, list_make1(rinfo1), index, &clauseset);
+		match_clauses_to_index(root, other_clauses, index, &clauseset);
+
+		/* Predicate has found already. So, it is ok for the empty match */
+
+		indexpaths = build_index_paths(root, rel,
+									   index, &clauseset,
+									   true,
+									   ST_BITMAPSCAN,
+									   NULL,
+									   NULL);
+		Assert(indexpaths != NIL);
+		result = lappend(result, indexpaths);
+	}
+	return result;
+}
+
+static List *
+generate_saop_pathlist(PlannerInfo *root, RelOptInfo *rel,
+					   RestrictInfo *rinfo, List *all_clauses)
+{
+	List	   *pathlist = NIL;
+	Path	   *bitmapqual;
+	List	   *indlist;
+	ListCell   *lc;
+
+	if (!enable_or_transformation)
+		return NIL;
+
+	/*
+	 * We must be able to match at least one index to each element of
+	 * the array, else we can't use it.
+	 */
+	indlist = build_paths_for_SAOP(root, rel, rinfo, all_clauses);
+	if (indlist == NIL)
+		return NIL;
+
+	/*
+	 * OK, pick the most promising AND combination, and add it to
+	 * pathlist.
+	 */
+	foreach (lc, indlist)
+	{
+		List *plist = lfirst_node(List, lc);
+
+		bitmapqual = choose_bitmap_and(root, rel, plist);
+		pathlist = lappend(pathlist, bitmapqual);
+	}
+
+	return pathlist;
+}
+
 /*
  * generate_bitmap_or_paths
- *		Look through the list of clauses to find OR clauses, and generate
- *		a BitmapOrPath for each one we can handle that way.  Return a list
- *		of the generated BitmapOrPaths.
+ *		Look through the list of clauses to find OR and SAOP clauses, and
+ *		Each saop clause are splitted to be covered by partial indexes.
+ *		generate a BitmapOrPath for each one we can handle that way.
+ *		Return a list of the generated BitmapOrPaths.
  *
  * other_clauses is a list of additional clauses that can be assumed true
  * for the purpose of generating indexquals, but are not to be searched for
@@ -1247,68 +1414,99 @@ generate_bitmap_or_paths(PlannerInfo *root, RelOptInfo *rel,
 	foreach(lc, clauses)
 	{
 		RestrictInfo *rinfo = lfirst_node(RestrictInfo, lc);
-		List	   *pathlist;
+		List	   *pathlist = NIL;
 		Path	   *bitmapqual;
 		ListCell   *j;

 

 
-			/*
 
-			/*
 
 		/*
diff --git a/src/backend/optimizer/util/predtest.c b/src/backend/optimizer/util/predtest.c
index c37b416e24..8ed80a78b4 100644
--- a/src/backend/optimizer/util/predtest.c
+++ b/src/backend/optimizer/util/predtest.c
@@ -112,6 +112,52 @@ static Oid	get_btree_test_op(Oid pred_op, Oid clause_op, bool refute_it);
 static void InvalidateOprProofCacheCallBack(Datum arg, int cacheid, uint32 hashvalue);

+/*
 
+bool
+restriction_is_saop_clause(RestrictInfo *restrictinfo)
+{
+	if (IsA(restrictinfo->clause, ScalarArrayOpExpr))
+	{
+		ScalarArrayOpExpr *saop = (ScalarArrayOpExpr *) restrictinfo->clause;
+
+		if (saop->useOr)
+			return true;
+	}
+	return false;
+}
+
 /*
  * restriction_is_securely_promotable
  *
diff --git a/src/include/optimizer/optimizer.h b/src/include/optimizer/optimizer.h
index 35ab577501..232afcd00c 100644
--- a/src/include/optimizer/optimizer.h
+++ b/src/include/optimizer/optimizer.h
@@ -160,6 +160,22 @@ extern List *expand_function_arguments(List *args, bool include_out_arguments,

+/*
+ * Contains information needed to extract from saop a set of elements which can
+ * be covered by the partial index:
+ * id - caller's identification of the index.
+ * predicate - predicate expression of the index
+ * elems - returning list of array elements which corresponds to this predicate
+ */

index adae668b37..a1d43283db 100644
@@ -2138,6 +2138,7 @@ PredIterInfoData
 PredXactList
 PredicateLockData
 PredicateLockTargetType
+PredicatesData
 PrefetchBufferResult
 PrepParallelRestorePtrType
 PrepareStmt
-- 
2.43.0

---

From: Alena Rybakina <[email-masked]>
Date: Mon, 12 Feb 2024 11:55:40 +0300

Hi!

I can't unnderstand this part of code:

/* Time to generate index paths */

MemSet(&clauseset, 0, sizeof(clauseset));
match_clauses_to_index(root, list_make1(rinfo1), index, &clauseset);

As I understand it, match_clauses_to_index is necessary if you have a 
RestrictInfo (rinfo1) variable, so maybe we should run it after the 
make_restrictonfo procedure, otherwise calling it, I think, is useless.

---

From: Andrei Lepikhov <[email-masked]>
Date: Mon, 12 Feb 2024 16:01:50 +0700

> make_restrictonfo procedure, otherwise calling it, I think, is useless.
I think you must explain your note in more detail. Before this call, we 
already called make_restrictinfo() and built rinfo1, haven't we?

-- 
regards,
Andrei Lepikhov
Postgres Professional

---

From: Alena Rybakina <[email-masked]>
Date: Mon, 12 Feb 2024 13:51:45 +0300

On 12.02.2024 12:01, Andrei Lepikhov wrote:
> I think you must explain your note in more detail. Before this call, 
> we already called make_restrictinfo() and built rinfo1, haven't we?
>
I got it, I think, I was confused by the “else“ block when we can 
process the index, otherwise we move on to the next element.

I think maybe “else“ block of creating restrictinfo with the indexpaths 
list creation should be moved to a separate function or just remove "else"?

I think we need to check that rinfo->clause is not empty, because if it 
is we can miss calling build_paths_for_OR function. We should add it there:

restriction_is_saop_clause(RestrictInfo *restrictinfo)
{
     if (IsA(restrictinfo->clause, ScalarArrayOpExpr))
...

By the way, I think we need to add a check that the clauseset is not 
empty (if (!clauseset.nonempty)) otherwise we could get an error. The 
same check I noticed in build_paths_for_OR function.

-- 
Regards,
Alena Rybakina
Postgres Professional: http://www.postgrespro.com
The Russian Postgres Company

---

From: jian he <[email-masked]>
Date: Tue, 13 Feb 2024 08:00:00 +0800

I am confused by the comments `array_collid will be set by
parse_collate.c`, can you further explain it?
if OR expression right arm is not plain Const, but with collation
specification, eg.
`where a  = 'a' collate "C" or a = 'b' collate "C";`

then the rightop is not Const, it will be CollateExpr, it will not be
used in transformation.
---------------------------------------------------------------------------------------------------------------------
Maybe the previous thread mentioned it, but this thread is very long.
after apply
v16-0001-Transform-OR-clause-to-ANY-expressions.patch
and 0002-Teach-generate_bitmap_or_paths-to-build-BitmapOr-pat-20240212.patch
I found a performance degradation case:

vacuum analyze test;

set enable_or_transformation to off;
explain(timing off, analyze, costs off)
select * from test where (x = 1 or x = 2 or x = 3 or x = 4 or x = 5 or
x = 6 or x = 7 or x = 8 or x = 9 ) \watch i=0.1 c=10
50.887 ms

set enable_or_transformation to on;
explain(timing off, analyze, costs off)
select * from test where (x = 1 or x = 2 or x = 3 or x = 4 or x = 5 or
x = 6 or x = 7 or x = 8 or x = 9 ) \watch i=0.1 c=10
92.001 ms

---------------------------------------------------------------------------------------------------------------------
but for aggregate count(*), it indeed increased the performance:

set enable_or_transformation to off;
explain(timing off, analyze, costs off)
select count(*) from test where (x = 1 or x = 2 or x = 3 or x = 4 or x
= 5 or x = 6 or x = 7 or x = 8 or x = 9 ) \watch i=0.1 c=10
46.818 ms

set enable_or_transformation to on;
explain(timing off, analyze, costs off)
select count(*) from test where (x = 1 or x = 2 or x = 3 or x = 4 or x
= 5 or x = 6 or x = 7 or x = 8 or x = 9 ) \watch i=0.1 c=10
35.376 ms

The time is the last result of the 10 iterations.

---

From: Andrei Lepikhov <[email-masked]>
Date: Tue, 13 Feb 2024 17:03:20 +0700

> parse_collate.c`, can you further explain it?
I wonder if the second paragraph of comments on commit b310b6e will be 
enough to dive into details.

> then the rightop is not Const, it will be CollateExpr, it will not be
Yes, it is done for simplicity right now. I'm not sure about corner 
cases of merging such expressions.

> The time is the last result of the 10 iterations.
The reason here - parallel workers.
If you see into the plan you will find parallel workers without 
optimization and absence of them in the case of optimization:

Gather  (cost=1000.00..28685.37 rows=87037 width=12)
	(actual rows=90363 loops=1)
    Workers Planned: 2
    Workers Launched: 2
    ->  Parallel Seq Scan on test
          Filter: ((x = 1) OR (x = 2) OR (x = 3) OR (x = 4) OR (x = 5) 
OR (x = 6) OR (x = 7) OR (x = 8) OR (x = 9))

Seq Scan on test  (cost=0.02..20440.02 rows=90600 width=12)
		  (actual rows=90363 loops=1)
    Filter: (x = ANY ('{1,2,3,4,5,6,7,8,9}'::integer[]))

Having 90600 tuples returned we estimate it into 87000 (less precisely) 
without transformation and 90363 (more precisely) with the transformation.
But if you play with parallel_tuple_cost and parallel_setup_cost, you 
will end up having these parallel workers:

  Gather  (cost=0.12..11691.03 rows=90600 width=12)
	 (actual rows=90363 loops=1)
    Workers Planned: 2
    Workers Launched: 2
    ->  Parallel Seq Scan on test
          Filter: (x = ANY ('{1,2,3,4,5,6,7,8,9}'::integer[]))
          Rows Removed by Filter: 303212

And some profit about 25%, on my laptop.
I'm not sure about the origins of such behavior, but it seems to be an 
issue of parallel workers, not this specific optimization.

-- 
regards,
Andrei Lepikhov
Postgres Professional

---

From: Andrei Lepikhov <[email-masked]>
Date: Tue, 13 Feb 2024 17:43:21 +0700

> list creation should be moved to a separate function or just remove "else"?
IMO, it is a matter of taste. But if you are really confused, maybe it 
will make understanding for someone else simpler. So, changed.
>      if (IsA(restrictinfo->clause, ScalarArrayOpExpr))
I wonder if we should add here assertion, not NULL check. In what case 
we could get NULL clause here? But added for surety.

> same check I noticed in build_paths_for_OR function.
I don't. Feel free to provide counterexample.

-- 
regards,
Andrei Lepikhov
Postgres Professional
From 2b088a1bd662c614ee491a797d2fcb67e2fb2391 Mon Sep 17 00:00:00 2001
From: "Andrey V. Lepikhov" <[email-masked]>
Date: Wed, 24 Jan 2024 14:07:17 +0700
Subject: [PATCH 2/2] Teach generate_bitmap_or_paths to build BitmapOr paths
 over SAOP clauses.

 src/backend/optimizer/path/indxpath.c     | 301 ++++++++++++++++++----
 8 files changed, 689 insertions(+), 53 deletions(-)

index 32c6a8bbdc..56b04541db 100644
 
@@ -1220,11 +1221,174 @@ build_paths_for_OR(PlannerInfo *root, RelOptInfo *rel,
 	return result;
 }
 
+/*
@@ -1247,68 +1411,99 @@ generate_bitmap_or_paths(PlannerInfo *root, RelOptInfo *rel,

 

 
-			/*
 
-			/*
 
 		/*

+/*
index 0b406e9334..1dad1dc654 100644
 
+bool
+	if (restrictinfo->clause && IsA(restrictinfo->clause, ScalarArrayOpExpr))

+/*

---

From: Andrei Lepikhov <[email-masked]>
Date: Wed, 14 Feb 2024 10:21:41 +0700

> issue of parallel workers, not this specific optimization.
Having written that, I'd got a backburner. And to close that issue, I 
explored get_restriction_qual_cost(). A close look shows us that "x IN 
(..)" cheaper than its equivalent "x=N1 OR ...". Just numbers:

ANY: startup_cost = 0.0225; total_cost = 0.005
OR: startup_cost==0; total_cost = 0.0225

Expression total_cost is calculated per tuple. In your example, we have 
many tuples, so the low cost of expression per tuple dominates over the 
significant startup cost.

According to the above, SAOP adds 6250 to the cost of SeqScan; OR - 
13541. So, the total cost of the query with SAOP is less than with OR, 
and the optimizer doesn't choose heavy parallel workers. And it is the 
answer.

So, this example is more about the subtle balance between 
parallel/sequential execution, which can vary from one platform to another.

-- 
regards,
Andrei Lepikhov
Postgres Professional

---

From: jian he <[email-masked]>
Date: Fri, 16 Feb 2024 08:00:00 +0800

> parallel/sequential execution, which can vary from one platform to another.

Hi, here I attached two files, expression_num_or_1_100.sql,
expression_num_or_1_10000.sql
it has step by step test cases, also with the tests output.

For both sql files, I already set the max_parallel_workers_per_gather to
10, work_mem to 4GB.
I think the parameters setting should be fine.

in expression_num_or_1_100.sql:
main test table:
create table test_1_100 as (select
(random()*1000)::int x, (random()*1000) y from
generate_series(1,1_000_000) i);

if the number of OR exceeds 29,
the performance with enable_or_transformation (ON) begins to outpace
enable_or_transformation (OFF).

if the number of OR less than 29,
the performance with enable_or_transformation (OFF) is better than
enable_or_transformation (ON).

expression_num_or_1_10000.sql
enable_or_transformation (ON) is always better than
enable_or_transformation (OFF).

My OS: Ubuntu 22.04.3 LTS
I already set the max_parallel_workers_per_gather to 10.
So for all cases, it should use parallelism first?

a better question would be:
how to make the number of OR less than 29 still faster when
enable_or_transformation is ON by only set parameters?

---

From: Andrei Lepikhov <[email-masked]>
Date: Fri, 16 Feb 2024 12:32:36 +0700

> enable_or_transformation is ON by only set parameters?
In my test environment this example gives some subtle supremacy to ORs 
over ANY with only 3 ors and less.
Please, provide next EXPLAIN ANALYZE results for the case you want to 
discuss here:
1. with enable_or_transformation enabled
2. with enable_or_transformation disabled
3. with enable_or_transformation disabled but with manual transformation 
OR -> ANY done, to check the overhead of this optimization.

-- 
regards,
Andrei Lepikhov
Postgres Professional

---

From: jian he <[email-masked]>
Date: Fri, 16 Feb 2024 20:54:16 +0800

> OR -> ANY done, to check the overhead of this optimization.

you previously mentioned playing with parallel_tuple_cost and
parallel_setup_cost.
(https://www.postgresql.org/message-id/e3338e82-a28d-4631-9eec-b9c0984b32d5%40postgrespro.ru)

So I did by
`
SET parallel_setup_cost = 0;
SET parallel_tuple_cost = 0;
`

After setting these parameters, overall enable_or_transformation ON is
performance better.
sorry for the noise.
so now I didn't find any corner case where enable_or_transformation is
ON peforms worse than when it's OFF.

I found that the field `scalar_type` was never used.