0002-Teach-generate_bitmap_or_paths-to-build-BitmapOr-pat-20240213.patch

From 2b088a1bd662c614ee491a797d2fcb67e2fb2391 Mon Sep 17 00:00:00 2001
From: "Andrey V. Lepikhov" <a.lepikhov@postgrespro.ru>
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     | 301 ++++++++++++++++++----
 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, 689 insertions(+), 53 deletions(-)

diff --git a/src/backend/optimizer/path/indxpath.c b/src/backend/optimizer/path/indxpath.c
index 32c6a8bbdc..56b04541db 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,174 @@ 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;
+		ArrayType		   *arrayval = NULL;
+		ArrayExpr		   *arr = NULL;
+		Const			   *arrayconst = lsecond_node(Const, saop->args);
+		ScalarArrayOpExpr  *dest = makeNode(ScalarArrayOpExpr);
+
+		pd = (PredicatesData *) lfirst(lc);
+		if (pd->elems == NIL)
+			/* The index doesn't participate in this operation */
+			continue;
+
+		/* 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 +1411,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/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);
 
 
+/*
+ * 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;
+
+	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);
+
+	return result;
+}
+
 /*
  * 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..1dad1dc654 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 (restrictinfo->clause && 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,
 
 /* in util/predtest.c: */
 
+/*
+ * 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
+ */
+typedef struct PredicatesData
+{
+	int		id;
+	Node   *predicate;
+	List   *elems;
+} 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
 --
diff --git a/src/tools/pgindent/typedefs.list b/src/tools/pgindent/typedefs.list
index adae668b37..a1d43283db 100644
--- a/src/tools/pgindent/typedefs.list
+++ b/src/tools/pgindent/typedefs.list
@@ -2138,6 +2138,7 @@ PredIterInfoData
 PredXactList
 PredicateLockData
 PredicateLockTargetType
+PredicatesData
 PrefetchBufferResult
 PrepParallelRestorePtrType
 PrepareStmt
-- 
2.43.0