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

From: Alena Rybakina <[email-masked]>
Date: Mon, 5 Aug 2024 23:24:47 +0300

Ok, thank you for your work)

I think we can leave only the two added libraries in the first patch, 
others are superfluous.

On 05.08.2024 22:48, Alexander Korotkov wrote:
> On Mon, Jul 29, 2024 at 5:36 AM Alexander Korotkov <[email-masked]> wrote:
>> On Sun, Jul 28, 2024 at 12:59 PM Alena Rybakina
>>> Because of these reasons, I tried to save this and that transformation
>>> together for each column and try to analyze for each expr separately
>>> which method would be optimal.
>> Yes, with v27 of the patch, optimization wouldn't work in these cases.
>> However, you are using quite small table.  If you will use larger
>> table or disable sequential scans, there would be bitmap plans to
>> handle these queries.  So, v27 doesn't make the situation worse. It
>> just doesn't optimize all that it could potentially optimize and
>> that's OK.
>>
>> I've written a separate 0002 patch to address this.  Now, before
>> generation of paths for bitmap OR, similar OR entries are grouped
>> together.  When considering a group of similar entries, they are
>> considered both together and one-by-one.  Ideally we could consider
>> more sophisticated grouping, but that seems fine for now.  You can
>> check how this patch handles the cases of above.
>>
>> Also, 0002 address issue of duplicated bitmap scan conditions in
>> different forms. During generate_bitmap_or_paths() we need to exclude
>> considered condition for other clauses.  It couldn't be as normal
>> filtered out in the latter stage, because could reach the index in
>> another form.
>>
>>> I agree with you that there is an overhead and your patch fixes this
>>> problem, but optimizer needs to have a good ordering of expressions for
>>> application.
>>>
>>> I think we can try to move the transformation to another place where
>>> there is already a loop pass, and also save two options "OR" expr and
>>> "ANY" expr in one place (through BoolExpr) (like find_duplicate_ors
>>> function) and teach the optimizer to determine which option is better,
>>> for example, like now in match_orclause_to_indexcol() function.
>>>
>>> What do you thing about it?
>> find_duplicate_ors() and similar places were already tried before.
>> Please, check upthread.  This approach receives severe critics. AFAIU,
>> the problem is that find_duplicate_ors() during preprocessing, a
>> cost-blind stage.
>>
>> This is why I'd like to continue developing ideas of v27, because it
>> fits the existing framework.
> The revised patchset is attached.  There is no material changes in the
> logic, I found no issues here yet.  But it comes with refactoring,
> cleanup, more comments and better commit messages.  I think now this
> patchset is understandable and ready for review.
>
> ------
> Regards,
> Alexander Korotkov
> Supabase

-- 
Regards,
Alena Rybakina
Postgres Professional: http://www.postgrespro.com
The Russian Postgres Company
From 84e4c71dccd77810a770038be7d9104004726e1c Mon Sep 17 00:00:00 2001
From: Alena Rybakina <[email-masked]>
Date: Mon, 5 Aug 2024 23:21:16 +0300
Subject: [PATCH 1/2] Transform OR-clauses to SAOP's during index matching

Replace "(indexkey op C1) OR (indexkey op C2) ... (indexkey op CN)" with
"indexkey op ANY(ARRAY[C1, C2, ...])" (ScalarArrayOpExpr node) during matching
a clause to index.

Here Ci is a i-th constant or parameters expression, 'expr' is non-constant
expression, 'op' is an operator which returns boolean result and has a commuter
(for the case of reverse order of constant and non-constant parts of the
expression, like 'Cn op expr').

This transformation allows to handle long OR-clauses with single IndexScan
avoiding slower bitmap scans.

Discussion: https://postgr.es/m/567ED6CA.2040504%40sigaev.ru
Author: Alena Rybakina <[email-masked]>
Author: Andrey Lepikhov <[email-masked]>
Reviewed-by: Peter Geoghegan <[email-masked]>
Reviewed-by: Ranier Vilela <[email-masked]>
Reviewed-by: Alexander Korotkov <[email-masked]>
Reviewed-by: Robert Haas <[email-masked]>
Reviewed-by: Jian He <[email-masked]>
Reviewed-by: Tom Lane <[email-masked]>
Reviewed-by: Nikolay Shaplov <[email-masked]>
---
 src/backend/optimizer/path/indxpath.c      | 253 +++++++++++++++++++++
 src/test/regress/expected/create_index.out | 183 +++++++++++++--
 src/test/regress/expected/join.out         |  57 ++++-
 src/test/regress/sql/create_index.sql      |  42 ++++
 src/test/regress/sql/join.sql              |   9 +
 5 files changed, 522 insertions(+), 22 deletions(-)

diff --git a/src/backend/optimizer/path/indxpath.c b/src/backend/optimizer/path/indxpath.c
index c0fcc7d78df..cb87126e758 100644
--- a/src/backend/optimizer/path/indxpath.c
+++ b/src/backend/optimizer/path/indxpath.c
@@ -32,7 +32,9 @@
 #include "optimizer/paths.h"
 #include "optimizer/prep.h"
 #include "optimizer/restrictinfo.h"
+#include "utils/array.h"
 #include "utils/lsyscache.h"
+#include "utils/syscache.h"
 #include "utils/selfuncs.h"

@@ -177,6 +179,10 @@ static IndexClause *match_rowcompare_to_indexcol(PlannerInfo *root,
 												 RestrictInfo *rinfo,
 												 int indexcol,
 												 IndexOptInfo *index);
+static IndexClause *match_orclause_to_indexcol(PlannerInfo *root,
+											   RestrictInfo *rinfo,
+											   int indexcol,
+											   IndexOptInfo *index);
 static IndexClause *expand_indexqual_rowcompare(PlannerInfo *root,
 												RestrictInfo *rinfo,
 												int indexcol,
@@ -2248,6 +2254,10 @@ match_clause_to_indexcol(PlannerInfo *root,
 	{
 		return match_rowcompare_to_indexcol(root, rinfo, indexcol, index);
 	}
+	else if (restriction_is_or_clause(rinfo))
+	{
+		return match_orclause_to_indexcol(root, rinfo, indexcol, index);
+	}
 	else if (index->amsearchnulls && IsA(clause, NullTest))
 	{
 		NullTest   *nt = (NullTest *) clause;
@@ -2771,6 +2781,249 @@ match_rowcompare_to_indexcol(PlannerInfo *root,
 	return NULL;
 }
 
+/*
+ * match_orclause_to_indexcol()
+ *	  Handles the OR-expr case for match_clause_to_indexcol() in the case
+ *	  when it could be transformed to ScalarArrayOpExpr.
+ */
+static IndexClause *
+match_orclause_to_indexcol(PlannerInfo *root,
+						   RestrictInfo *rinfo,
+						   int indexcol,
+						   IndexOptInfo *index)
+{
+	ListCell   *lc;
+	BoolExpr   *orclause = (BoolExpr *) rinfo->orclause;
+	Node	   *indexExpr = NULL;
+	List	   *consts = NIL;
+	Node	   *arrayNode = NULL;
+	ScalarArrayOpExpr *saopexpr = NULL;
+	HeapTuple	opertup;
+	Form_pg_operator operform;
+	Oid			matchOpno = InvalidOid;
+	IndexClause *iclause;
+	Oid			consttype = InvalidOid;
+	Oid			arraytype = InvalidOid;
+	Oid			inputcollid = InvalidOid;
+	bool		firstTime = true;
+	bool		have_param = false;
+
+	Assert(IsA(orclause, BoolExpr));
+	Assert(orclause->boolop == OR_EXPR);
+
+	/*
+	 * Iterate over OR entries.  Check that each OR entry is of the form:
+	 * (indexkey operator constant) or (constant operator indexkey). Operators
+	 * of all the entries must match.  Constant might be either Const or
+	 * Param.  Exit with NULL on first non-matching entry.
+	 */
+	foreach(lc, orclause->args)
+	{
+		RestrictInfo *subRinfo;
+		OpExpr	   *subClause;
+		Oid			opno;
+		Node	   *leftop,
+				   *rightop;
+		Node	   *constExpr;
+
+		if (!IsA(lfirst(lc), RestrictInfo))
+			return NULL;
+
+		subRinfo = (RestrictInfo *) lfirst(lc);
+
+		/* Only operator clauses scan match  */
+		if (!IsA(subRinfo->clause, OpExpr))
+			return NULL;
+
+		subClause = (OpExpr *) subRinfo->clause;
+		opno = subClause->opno;
+
+		/* Only binary operators can match  */
+		if (list_length(subClause->args) != 2)
+			return NULL;
+
+		/* RestrictInfo parameters dmust match parent */
+		if (subRinfo->is_pushed_down != rinfo->is_pushed_down ||
+			subRinfo->is_clone != rinfo->is_clone ||
+			subRinfo->security_level != rinfo->security_level ||
+			!bms_equal(subRinfo->required_relids, rinfo->required_relids) ||
+			!bms_equal(subRinfo->incompatible_relids, rinfo->incompatible_relids) ||
+			!bms_equal(subRinfo->outer_relids, rinfo->outer_relids))
+			return NULL;
+
+		/* Only operator returning boolean suits the transformation */
+		if (get_op_rettype(opno) != BOOLOID)
+			return NULL;
+
+		/*
+		 * Check for clauses of the form: (indexkey operator constant) or
+		 * (constant operator indexkey).  Determine indexkey side first, check
+		 * the constant later.
+		 */
+		leftop = (Node *) linitial(subClause->args);
+		rightop = (Node *) lsecond(subClause->args);
+		if (match_index_to_operand(leftop, indexcol, index))
+		{
+			indexExpr = leftop;
+			constExpr = rightop;
+		}
+		else if (match_index_to_operand(rightop, indexcol, index))
+		{
+			opno = get_commutator(opno);
+			if (!OidIsValid(opno))
+			{
+				/* commutator doesn't exist, we can't reverse the order */
+				return NULL;
+			}
+			indexExpr = rightop;
+			constExpr = leftop;
+		}
+		else
+		{
+			return NULL;
+		}
+
+		/*
+		 * Ignore any RelabelType node above the operands.  This is needed to
+		 * be able to apply indexscanning in binary-compatible-operator cases.
+		 * Note: we can assume there is at most one RelabelType node;
+		 * eval_const_expressions() will have simplified if more than one.
+		 */
+		if (IsA(constExpr, RelabelType))
+			constExpr = (Node *) ((RelabelType *) constExpr)->arg;
+		if (IsA(indexExpr, RelabelType))
+			indexExpr = (Node *) ((RelabelType *) indexExpr)->arg;
+
+		/* We allow constant to be Const or Param */
+		if (!IsA(constExpr, Const) && !IsA(constExpr, Param))
+			return NULL;
+
+		/* Forbid transformation for composite types, records. */
+		if (type_is_rowtype(exprType(constExpr)) ||
+			type_is_rowtype(exprType(indexExpr)))
+			return NULL;
+
+		/*
+		 * For the first matching qual, save information about operator, type
+		 * and collation.  For the other quals just check the match with the
+		 * first.
+		 */
+		if (firstTime)
+		{
+			matchOpno = opno;
+			consttype = exprType(constExpr);
+			arraytype = get_array_type(consttype);
+			inputcollid = subClause->inputcollid;
+
+			/*
+			 * There must be an array type in order to construct an array
+			 * later
+			 */
+			if (!OidIsValid(arraytype))
+				return NULL;
+			firstTime = false;
+		}
+		else
+		{
+			if (opno != matchOpno ||
+				inputcollid != subClause->inputcollid ||
+				consttype != exprType(constExpr))
+				return NULL;
+		}
+
+		if (IsA(constExpr, Param))
+			have_param = true;
+		consts = lappend(consts, constExpr);
+	}
+
+	if (have_param)
+	{
+		/*
+		 * We need to construct an ArrayExpr given we have Param's not just
+		 * Const's.
+		 */
+		ArrayExpr  *arrayExpr = makeNode(ArrayExpr);
+
+		/* array_collid will be set by parse_collate.c */
+		arrayExpr->element_typeid = consttype;
+		arrayExpr->array_typeid = arraytype;
+		arrayExpr->multidims = false;
+		arrayExpr->elements = consts;
+		arrayExpr->location = -1;
+
+		arrayNode = (Node *) arrayExpr;
+	}
+	else
+	{
+		/*
+		 * We have only Costs's.  In this case we can contruct an array
+		 * directly.
+		 */
+		int16		typlen;
+		bool		typbyval;
+		char		typalign;
+		Datum	   *elems;
+		int			i = 0;
+		ArrayType  *arrayConst;
+
+		get_typlenbyvalalign(consttype, &typlen, &typbyval, &typalign);
+
+		elems = (Datum *) palloc(sizeof(Datum) * list_length(consts));
+		foreach(lc, consts)
+			elems[i++] = ((Const *) lfirst(lc))->constvalue;
+
+		arrayConst = construct_array(elems, i, consttype,
+									 typlen, typbyval, typalign);
+		arrayNode = (Node *) makeConst(arraytype, -1, inputcollid,
+									   -1, PointerGetDatum(arrayConst),
+									   false, false);
+
+		pfree(elems);
+		list_free(consts);
+	}
+
+	/* Lookup for operator to fetch necessary information for the SAOP node */
+	opertup = SearchSysCache1(OPEROID,
+							  ObjectIdGetDatum(matchOpno));
+	if (!HeapTupleIsValid(opertup))
+		elog(ERROR, "cache lookup failed for operator %u", matchOpno);
+
+	operform = (Form_pg_operator) GETSTRUCT(opertup);
+
+	/* Build the SAOP expression node */
+	saopexpr = makeNode(ScalarArrayOpExpr);
+	saopexpr->opno = matchOpno;
+	saopexpr->opfuncid = operform->oprcode;
+	saopexpr->hashfuncid = InvalidOid;
+	saopexpr->negfuncid = InvalidOid;
+	saopexpr->useOr = true;
+	saopexpr->inputcollid = inputcollid;
+	saopexpr->args = list_make2(indexExpr, arrayNode);
+	saopexpr->location = -1;
+
+	ReleaseSysCache(opertup);
+
+	/*
+	 * Finally build an IndexClause based on the SAOP node.
+	 */
+	iclause = makeNode(IndexClause);
+	iclause->rinfo = make_restrictinfo(root,
+									   &saopexpr->xpr,
+									   rinfo->is_pushed_down,
+									   rinfo->has_clone,
+									   rinfo->is_clone,
+									   rinfo->pseudoconstant,
+									   rinfo->security_level,
+									   rinfo->required_relids,
+									   rinfo->incompatible_relids,
+									   rinfo->outer_relids);
+	iclause->indexquals = list_make1(iclause->rinfo);
+	iclause->lossy = false;
+	iclause->indexcol = indexcol;
+	iclause->indexcols = NIL;
+	return iclause;
+}
+
 /*
  * expand_indexqual_rowcompare --- expand a single indexqual condition
  *		that is a RowCompareExpr
diff --git a/src/test/regress/expected/create_index.out b/src/test/regress/expected/create_index.out
index cf6eac57349..c2b25936c8c 100644
--- a/src/test/regress/expected/create_index.out
+++ b/src/test/regress/expected/create_index.out
@@ -1844,18 +1844,11 @@ DROP TABLE onek_with_null;
 EXPLAIN (COSTS OFF)
 SELECT * FROM tenk1
   WHERE thousand = 42 AND (tenthous = 1 OR tenthous = 3 OR tenthous = 42);
-                                                               QUERY PLAN                                                                
------------------------------------------------------------------------------------------------------------------------------------------
- Bitmap Heap Scan on tenk1
-   Recheck Cond: (((thousand = 42) AND (tenthous = 1)) OR ((thousand = 42) AND (tenthous = 3)) OR ((thousand = 42) AND (tenthous = 42)))
-   ->  BitmapOr
-         ->  Bitmap Index Scan on tenk1_thous_tenthous
-               Index Cond: ((thousand = 42) AND (tenthous = 1))
-         ->  Bitmap Index Scan on tenk1_thous_tenthous
-               Index Cond: ((thousand = 42) AND (tenthous = 3))
-         ->  Bitmap Index Scan on tenk1_thous_tenthous
-               Index Cond: ((thousand = 42) AND (tenthous = 42))
-(9 rows)
+                                  QUERY PLAN                                  
+------------------------------------------------------------------------------
+ Index Scan using tenk1_thous_tenthous on tenk1
+   Index Cond: ((thousand = 42) AND (tenthous = ANY ('{1,3,42}'::integer[])))
+(2 rows)
 
 SELECT * FROM tenk1
   WHERE thousand = 42 AND (tenthous = 1 OR tenthous = 3 OR tenthous = 42);
@@ -1864,14 +1857,166 @@ SELECT * FROM tenk1
       42 |    5530 |   0 |    2 |   2 |      2 |      42 |       42 |          42 |        42 |       42 |  84 |   85 | QBAAAA   | SEIAAA   | OOOOxx
 (1 row)
 
+EXPLAIN (COSTS OFF)
+SELECT * FROM tenk1
+  WHERE thousand = 42 AND (tenthous = 1 OR tenthous = (SELECT 1 + 2) OR tenthous = 42);
+                                       QUERY PLAN                                       
+----------------------------------------------------------------------------------------
+ Index Scan using tenk1_thous_tenthous on tenk1
+   Index Cond: ((thousand = 42) AND (tenthous = ANY (ARRAY[1, (InitPlan 1).col1, 42])))
+   InitPlan 1
+     ->  Result
+(4 rows)
+
+SELECT * FROM tenk1
+  WHERE thousand = 42 AND (tenthous = 1 OR tenthous = (SELECT 1 + 2) OR tenthous = 42);
+ unique1 | unique2 | two | four | ten | twenty | hundred | thousand | twothousand | fivethous | tenthous | odd | even | stringu1 | stringu2 | string4 
+---------+---------+-----+------+-----+--------+---------+----------+-------------+-----------+----------+-----+------+----------+----------+---------
+      42 |    5530 |   0 |    2 |   2 |      2 |      42 |       42 |          42 |        42 |       42 |  84 |   85 | QBAAAA   | SEIAAA   | OOOOxx
+(1 row)
+
 EXPLAIN (COSTS OFF)
 SELECT count(*) FROM tenk1
   WHERE hundred = 42 AND (thousand = 42 OR thousand = 99);
-                                   QUERY PLAN                                    
----------------------------------------------------------------------------------
+                                     QUERY PLAN                                     
+------------------------------------------------------------------------------------
  Aggregate
    ->  Bitmap Heap Scan on tenk1
-         Recheck Cond: ((hundred = 42) AND ((thousand = 42) OR (thousand = 99)))
+         Recheck Cond: ((hundred = 42) AND (thousand = ANY ('{42,99}'::integer[])))
+         ->  BitmapAnd
+               ->  Bitmap Index Scan on tenk1_hundred
+                     Index Cond: (hundred = 42)
+               ->  Bitmap Index Scan on tenk1_thous_tenthous
+                     Index Cond: (thousand = ANY ('{42,99}'::integer[]))
+(8 rows)
+
+SELECT count(*) FROM tenk1
+  WHERE hundred = 42 AND (thousand = 42 OR thousand = 99);
+ count 
+-------
+    10
+(1 row)
+
+EXPLAIN (COSTS OFF)
+SELECT * FROM tenk1
+  WHERE thousand = 42 AND (tenthous = 1 OR tenthous = 3 OR tenthous = 42);
+                                  QUERY PLAN                                  
+------------------------------------------------------------------------------
+ Index Scan using tenk1_thous_tenthous on tenk1
+   Index Cond: ((thousand = 42) AND (tenthous = ANY ('{1,3,42}'::integer[])))
+(2 rows)
+
+SELECT * FROM tenk1
+  WHERE thousand = 42 AND (tenthous = 1 OR tenthous = 3 OR tenthous = 42);
+ unique1 | unique2 | two | four | ten | twenty | hundred | thousand | twothousand | fivethous | tenthous | odd | even | stringu1 | stringu2 | string4 
+---------+---------+-----+------+-----+--------+---------+----------+-------------+-----------+----------+-----+------+----------+----------+---------
+      42 |    5530 |   0 |    2 |   2 |      2 |      42 |       42 |          42 |        42 |       42 |  84 |   85 | QBAAAA   | SEIAAA   | OOOOxx
+(1 row)
+
+EXPLAIN (COSTS OFF)
+SELECT count(*) FROM tenk1
+  WHERE hundred = 42 AND (thousand = 42 OR thousand = 99);
+                                     QUERY PLAN                                     
+------------------------------------------------------------------------------------
+ Aggregate
+   ->  Bitmap Heap Scan on tenk1
+         Recheck Cond: ((hundred = 42) AND (thousand = ANY ('{42,99}'::integer[])))
+         ->  BitmapAnd
+               ->  Bitmap Index Scan on tenk1_hundred
+                     Index Cond: (hundred = 42)
+               ->  Bitmap Index Scan on tenk1_thous_tenthous
+                     Index Cond: (thousand = ANY ('{42,99}'::integer[]))
+(8 rows)
+
+SELECT count(*) FROM tenk1
+  WHERE hundred = 42 AND (thousand = 42 OR thousand = 99);
+ count 
+-------
+    10
+(1 row)
+
+EXPLAIN (COSTS OFF)
+SELECT count(*) FROM tenk1
+  WHERE hundred = 42 AND (thousand < 42 OR thousand < 99 OR 43 > thousand OR 42 > thousand);
+                                        QUERY PLAN                                        
+------------------------------------------------------------------------------------------
+ Aggregate
+   ->  Bitmap Heap Scan on tenk1
+         Recheck Cond: ((hundred = 42) AND (thousand < ANY ('{42,99,43,42}'::integer[])))
+         ->  BitmapAnd
+               ->  Bitmap Index Scan on tenk1_hundred
+                     Index Cond: (hundred = 42)
+               ->  Bitmap Index Scan on tenk1_thous_tenthous
+                     Index Cond: (thousand < ANY ('{42,99,43,42}'::integer[]))
+(8 rows)
+
+SELECT count(*) FROM tenk1
+  WHERE hundred = 42 AND (thousand < 42 OR thousand < 99 OR 43 > thousand OR 42 > thousand);
+ count 
+-------
+    10
+(1 row)
+
+EXPLAIN (COSTS OFF)
+SELECT count(*) FROM tenk1
+  WHERE thousand = 42 AND (tenthous = 1 OR tenthous = 3) OR thousand = 41;
+                                               QUERY PLAN                                               
+--------------------------------------------------------------------------------------------------------
+ Aggregate
+   ->  Bitmap Heap Scan on tenk1
+         Recheck Cond: (((thousand = 42) AND (tenthous = ANY ('{1,3}'::integer[]))) OR (thousand = 41))
+         ->  BitmapOr
+               ->  Bitmap Index Scan on tenk1_thous_tenthous
+                     Index Cond: ((thousand = 42) AND (tenthous = ANY ('{1,3}'::integer[])))
+               ->  Bitmap Index Scan on tenk1_thous_tenthous
+                     Index Cond: (thousand = 41)
+(8 rows)
+
+SELECT count(*) FROM tenk1
+  WHERE thousand = 42 AND (tenthous = 1 OR tenthous = 3) OR thousand = 41;
+ count 
+-------
+    10
+(1 row)
+
+EXPLAIN (COSTS OFF)
+SELECT count(*) FROM tenk1
+  WHERE hundred = 42 AND (thousand = 42 OR thousand = 99 OR tenthous < 2) OR thousand = 41;
+                                                       QUERY PLAN                                                       
+------------------------------------------------------------------------------------------------------------------------
+ Aggregate
+   ->  Bitmap Heap Scan on tenk1
+         Recheck Cond: (((hundred = 42) AND ((thousand = 42) OR (thousand = 99) OR (tenthous < 2))) OR (thousand = 41))
+         ->  BitmapOr
+               ->  BitmapAnd
+                     ->  Bitmap Index Scan on tenk1_hundred
+                           Index Cond: (hundred = 42)
+                     ->  BitmapOr
+                           ->  Bitmap Index Scan on tenk1_thous_tenthous
+                                 Index Cond: (thousand = 42)
+                           ->  Bitmap Index Scan on tenk1_thous_tenthous
+                                 Index Cond: (thousand = 99)
+                           ->  Bitmap Index Scan on tenk1_thous_tenthous
+                                 Index Cond: (tenthous < 2)
+               ->  Bitmap Index Scan on tenk1_thous_tenthous
+                     Index Cond: (thousand = 41)
+(16 rows)
+
+SELECT count(*) FROM tenk1
+  WHERE hundred = 42 AND (thousand = 42 OR thousand = 99 OR tenthous < 2) OR thousand = 41;
+ count 
+-------
+    20
+(1 row)
+
+EXPLAIN (COSTS OFF)
+SELECT count(*) FROM tenk1
+  WHERE hundred = 42 AND (thousand = 42 OR thousand = 41 OR thousand = 99 AND tenthous = 2);
+                                                       QUERY PLAN                                                        
+-------------------------------------------------------------------------------------------------------------------------
+ Aggregate
+   ->  Bitmap Heap Scan on tenk1
+         Recheck Cond: ((hundred = 42) AND ((thousand = 42) OR (thousand = 41) OR ((thousand = 99) AND (tenthous = 2))))
          ->  BitmapAnd
                ->  Bitmap Index Scan on tenk1_hundred
                      Index Cond: (hundred = 42)
@@ -1879,11 +2024,13 @@ SELECT count(*) FROM tenk1
                      ->  Bitmap Index Scan on tenk1_thous_tenthous
                            Index Cond: (thousand = 42)
                      ->  Bitmap Index Scan on tenk1_thous_tenthous
-                           Index Cond: (thousand = 99)
-(11 rows)
+                           Index Cond: (thousand = 41)
+                     ->  Bitmap Index Scan on tenk1_thous_tenthous
+                           Index Cond: ((thousand = 99) AND (tenthous = 2))
+(13 rows)
 
 SELECT count(*) FROM tenk1
-  WHERE hundred = 42 AND (thousand = 42 OR thousand = 99);
+  WHERE hundred = 42 AND (thousand = 42 OR thousand = 41 OR thousand = 99 AND tenthous = 2);
  count 
 -------
     10
diff --git a/src/test/regress/expected/join.out b/src/test/regress/expected/join.out
index 53f70d72ed6..abe98ff3c53 100644
--- a/src/test/regress/expected/join.out
+++ b/src/test/regress/expected/join.out
@@ -4278,15 +4278,64 @@ select * from tenk1 a join tenk1 b on
                      Index Cond: (hundred = 4)
    ->  Materialize
          ->  Bitmap Heap Scan on tenk1 a
-               Recheck Cond: ((unique1 = 1) OR (unique2 = 3) OR (unique2 = 7))
+               Recheck Cond: ((unique1 = 1) OR (unique2 = ANY ('{3,7}'::integer[])))
+               Filter: ((unique1 = 1) OR (unique2 = 3) OR (unique2 = 7))
                ->  BitmapOr
                      ->  Bitmap Index Scan on tenk1_unique1
                            Index Cond: (unique1 = 1)
                      ->  Bitmap Index Scan on tenk1_unique2
-                           Index Cond: (unique2 = 3)
+                           Index Cond: (unique2 = ANY ('{3,7}'::integer[]))
+(18 rows)
+
+explain (costs off)
+select * from tenk1 a join tenk1 b on
+  (a.unique1 = 1 and b.unique1 = 2) or
+  ((a.unique2 = 3 or a.unique2 = 7) and b.hundred = 4);
+                                                      QUERY PLAN                                                      
+----------------------------------------------------------------------------------------------------------------------
+ Nested Loop
+   Join Filter: (((a.unique1 = 1) AND (b.unique1 = 2)) OR (((a.unique2 = 3) OR (a.unique2 = 7)) AND (b.hundred = 4)))
+   ->  Bitmap Heap Scan on tenk1 b
+         Recheck Cond: ((unique1 = 2) OR (hundred = 4))
+         ->  BitmapOr
+               ->  Bitmap Index Scan on tenk1_unique1
+                     Index Cond: (unique1 = 2)
+               ->  Bitmap Index Scan on tenk1_hundred
+                     Index Cond: (hundred = 4)
+   ->  Materialize
+         ->  Bitmap Heap Scan on tenk1 a
+               Recheck Cond: ((unique1 = 1) OR (unique2 = ANY ('{3,7}'::integer[])))
+               Filter: ((unique1 = 1) OR (unique2 = 3) OR (unique2 = 7))
+               ->  BitmapOr
+                     ->  Bitmap Index Scan on tenk1_unique1
+                           Index Cond: (unique1 = 1)
                      ->  Bitmap Index Scan on tenk1_unique2
-                           Index Cond: (unique2 = 7)
-(19 rows)
+                           Index Cond: (unique2 = ANY ('{3,7}'::integer[]))
+(18 rows)
+
+explain (costs off)
+select * from tenk1 a join tenk1 b on
+  (a.unique1 < 20 or a.unique1 = 3 or a.unique1 = 1 and b.unique1 = 2) or
+  ((a.unique2 = 3 or a.unique2 = 7) and b.hundred = 4);
+                                                                         QUERY PLAN                                                                          
+-------------------------------------------------------------------------------------------------------------------------------------------------------------
+ Nested Loop
+   Join Filter: ((a.unique1 < 20) OR (a.unique1 = 3) OR ((a.unique1 = 1) AND (b.unique1 = 2)) OR (((a.unique2 = 3) OR (a.unique2 = 7)) AND (b.hundred = 4)))
+   ->  Seq Scan on tenk1 b
+   ->  Materialize
+         ->  Bitmap Heap Scan on tenk1 a
+               Recheck Cond: ((unique1 < 20) OR (unique1 = 3) OR (unique1 = 1) OR (unique2 = ANY ('{3,7}'::integer[])))
+               Filter: ((unique1 < 20) OR (unique1 = 3) OR (unique1 = 1) OR (unique2 = 3) OR (unique2 = 7))
+               ->  BitmapOr
+                     ->  Bitmap Index Scan on tenk1_unique1
+                           Index Cond: (unique1 < 20)
+                     ->  Bitmap Index Scan on tenk1_unique1
+                           Index Cond: (unique1 = 3)
+                     ->  Bitmap Index Scan on tenk1_unique1
+                           Index Cond: (unique1 = 1)
+                     ->  Bitmap Index Scan on tenk1_unique2
+                           Index Cond: (unique2 = ANY ('{3,7}'::integer[]))
+(16 rows)
 
 --
 -- test placement of movable quals in a parameterized join tree
diff --git a/src/test/regress/sql/create_index.sql b/src/test/regress/sql/create_index.sql
index e296891cab8..f74ad415fbf 100644
--- a/src/test/regress/sql/create_index.sql
+++ b/src/test/regress/sql/create_index.sql
@@ -726,6 +726,24 @@ DROP TABLE onek_with_null;
 -- Check bitmap index path planning
 --
 
+EXPLAIN (COSTS OFF)
+SELECT * FROM tenk1
+  WHERE thousand = 42 AND (tenthous = 1 OR tenthous = 3 OR tenthous = 42);
+SELECT * FROM tenk1
+  WHERE thousand = 42 AND (tenthous = 1 OR tenthous = 3 OR tenthous = 42);
+
+EXPLAIN (COSTS OFF)
+SELECT * FROM tenk1
+  WHERE thousand = 42 AND (tenthous = 1 OR tenthous = (SELECT 1 + 2) OR tenthous = 42);
+SELECT * FROM tenk1
+  WHERE thousand = 42 AND (tenthous = 1 OR tenthous = (SELECT 1 + 2) OR tenthous = 42);
+
+EXPLAIN (COSTS OFF)
+SELECT count(*) FROM tenk1
+  WHERE hundred = 42 AND (thousand = 42 OR thousand = 99);
+SELECT count(*) FROM tenk1
+  WHERE hundred = 42 AND (thousand = 42 OR thousand = 99);
+
 EXPLAIN (COSTS OFF)
 SELECT * FROM tenk1
   WHERE thousand = 42 AND (tenthous = 1 OR tenthous = 3 OR tenthous = 42);
@@ -738,6 +756,30 @@ SELECT count(*) FROM tenk1
 SELECT count(*) FROM tenk1
   WHERE hundred = 42 AND (thousand = 42 OR thousand = 99);
 
+EXPLAIN (COSTS OFF)
+SELECT count(*) FROM tenk1
+  WHERE hundred = 42 AND (thousand < 42 OR thousand < 99 OR 43 > thousand OR 42 > thousand);
+SELECT count(*) FROM tenk1
+  WHERE hundred = 42 AND (thousand < 42 OR thousand < 99 OR 43 > thousand OR 42 > thousand);
+
+EXPLAIN (COSTS OFF)
+SELECT count(*) FROM tenk1
+  WHERE thousand = 42 AND (tenthous = 1 OR tenthous = 3) OR thousand = 41;
+SELECT count(*) FROM tenk1
+  WHERE thousand = 42 AND (tenthous = 1 OR tenthous = 3) OR thousand = 41;
+
+EXPLAIN (COSTS OFF)
+SELECT count(*) FROM tenk1
+  WHERE hundred = 42 AND (thousand = 42 OR thousand = 99 OR tenthous < 2) OR thousand = 41;
+SELECT count(*) FROM tenk1
+  WHERE hundred = 42 AND (thousand = 42 OR thousand = 99 OR tenthous < 2) OR thousand = 41;
+
+EXPLAIN (COSTS OFF)
+SELECT count(*) FROM tenk1
+  WHERE hundred = 42 AND (thousand = 42 OR thousand = 41 OR thousand = 99 AND tenthous = 2);
+SELECT count(*) FROM tenk1
+  WHERE hundred = 42 AND (thousand = 42 OR thousand = 41 OR thousand = 99 AND tenthous = 2);
+
 --
 -- Check behavior with duplicate index column contents
 --
diff --git a/src/test/regress/sql/join.sql b/src/test/regress/sql/join.sql
index d81ff63be53..4473b8f04d5 100644
--- a/src/test/regress/sql/join.sql
+++ b/src/test/regress/sql/join.sql
@@ -1433,6 +1433,15 @@ select * from tenk1 a join tenk1 b on
   (a.unique1 = 1 and b.unique1 = 2) or
   ((a.unique2 = 3 or a.unique2 = 7) and b.hundred = 4);
 
+explain (costs off)
+select * from tenk1 a join tenk1 b on
+  (a.unique1 = 1 and b.unique1 = 2) or
+  ((a.unique2 = 3 or a.unique2 = 7) and b.hundred = 4);
+explain (costs off)
+select * from tenk1 a join tenk1 b on
+  (a.unique1 < 20 or a.unique1 = 3 or a.unique1 = 1 and b.unique1 = 2) or
+  ((a.unique2 = 3 or a.unique2 = 7) and b.hundred = 4);
+
 --
 -- test placement of movable quals in a parameterized join tree
 --
-- 
2.34.1

---

From: Alexander Korotkov <[email-masked]>
Date: Wed, 7 Aug 2024 04:11:08 +0300

> I think we can leave only the two added libraries in the first patch,

Thank you.
I also have fixed some grammar issues.

------
Regards,
Alexander Korotkov
Supabase

---

From: Alena Rybakina <[email-masked]>
Date: Thu, 8 Aug 2024 02:53:35 +0300

> I also have fixed some grammar issues.

Thank you)

I added some tests to test the functionality of queries using strange 
operator classes, type mismatches, and a small number of joins.
At the same time, I faced an assertion when a request with an unusual 
operator was processed:

EXPLAIN (COSTS OFF)
SELECT COUNT(*) FROM guid1 WHERE guid_field <> 
'11111111111111111111111111111111' OR
                             guid_field <> 
'3f3e3c3b-3a30-3938-3736-353433a2313e';

Coredump:

#0  __pthread_kill_implementation (no_tid=0, signo=6, 
threadid=138035230913472)
     at ./nptl/pthread_kill.c:44
#1  __pthread_kill_internal (signo=6, threadid=138035230913472) at 
./nptl/pthread_kill.c:78
#2  __GI___pthread_kill (threadid=138035230913472, signo=signo@entry=6) 
at ./nptl/pthread_kill.c:89
#3  0x00007d8ad3e42476 in __GI_raise (sig=sig@entry=6) at 
../sysdeps/posix/raise.c:26
#4  0x00007d8ad3e287f3 in __GI_abort () at ./stdlib/abort.c:79
#5  0x000060ceb55be02f in ExceptionalCondition 
(conditionName=0x60ceb58058af "op_strategy != 0",
     fileName=0x60ceb58053e6 "selfuncs.c", lineNumber=6900) at assert.c:66
#6  0x000060ceb553ed48 in btcostestimate (root=0x60ceb6f9d2a8, 
path=0x60ceb6fbd2a8, loop_count=1,
--Type <RET> for more, q to quit, c to continue without paging--
     indexStartupCost=0x7fff7ea15380, indexTotalCost=0x7fff7ea15388,
     indexSelectivity=0x7fff7ea15390, indexCorrelation=0x7fff7ea15398, 
indexPages=0x7fff7ea153b0)
     at selfuncs.c:6900
#7  0x000060ceb521afca in cost_index (path=0x60ceb6fbd2a8, 
root=0x60ceb6f9d2a8, loop_count=1,
     partial_path=false) at costsize.c:618
#8  0x000060ceb5290c99 in create_index_path (root=0x60ceb6f9d2a8, 
index=0x60ceb6fbd5e8,
     indexclauses=0x60ceb6fbe4c8, indexorderbys=0x0, 
indexorderbycols=0x0, pathkeys=0x0,
     indexscandir=ForwardScanDirection, indexonly=true, 
required_outer=0x0, loop_count=1,
     partial_path=false) at pathnode.c:1024
--Type <RET> for more, q to quit, c to continue without paging--
#9  0x000060ceb522df4d in build_index_paths (root=0x60ceb6f9d2a8, 
rel=0x60ceb70716c8, index=0x60ceb6fbd5e8,
     clauses=0x7fff7ea15790, useful_predicate=false, 
scantype=ST_ANYSCAN, skip_nonnative_saop=0x7fff7ea15607)
     at indxpath.c:970
#10 0x000060ceb522d905 in get_index_paths (root=0x60ceb6f9d2a8, 
rel=0x60ceb70716c8, index=0x60ceb6fbd5e8,
     clauses=0x7fff7ea15790, bitindexpaths=0x7fff7ea15678) at indxpath.c:729
#11 0x000060ceb522c846 in create_index_paths (root=0x60ceb6f9d2a8, 
rel=0x60ceb70716c8) at indxpath.c:286
#12 0x000060ceb5212d29 in set_plain_rel_pathlist (root=0x60ceb6f9d2a8, 
rel=0x60ceb70716c8, rte=0x60ceb6f63768)
     at allpaths.c:794
#13 0x000060ceb5212852 in set_rel_pathlist (root=0x60ceb6f9d2a8, 
rel=0x60ceb70716c8, rti=1, rte=0x60ceb6f63768)
     at allpaths.c:499
#14 0x000060ceb521248c in set_base_rel_pathlists (root=0x60ceb6f9d2a8) 
at allpaths.c:351
#15 0x000060ceb52121af in make_one_rel (root=0x60ceb6f9d2a8, 
joinlist=0x60ceb6fbdea8) at allpaths.c:221
#16 0x000060ceb5257a8d in query_planner (root=0x60ceb6f9d2a8, 
qp_callback=0x60ceb525e2e6 <standard_qp_callback>,
     qp_extra=0x7fff7ea15d90) at planmain.c:280
#17 0x000060ceb525a4f0 in grouping_planner (root=0x60ceb6f9d2a8, 
tuple_fraction=0, setops=0x0) at planner.c:1520
#18 0x000060ceb5259b8f in subquery_planner (glob=0x60ceb70715b8, 
parse=0x60ceb6f63558, parent_root=0x0,
     hasRecursion=false, tuple_fraction=0, setops=0x0) at planner.c:1089
#19 0x000060ceb52581f2 in standard_planner (parse=0x60ceb6f63558,
     query_string=0x60ceb6f62020 "EXPLAIN (COSTS OFF)\nSELECT COUNT(*) 
FROM guid1 WHERE guid_field <> '", '1' <repeats 32 --Type <RET> for 
more, q to quit, c to continue without paging--
times>, "' OR\n\t\t\t\t\t\t\tguid_field <> 
'3f3e3c3b-3a30-3938-3736-353433a2313e';", cursorOptions=2048,
     boundParams=0x0) at planner.c:415
#20 0x000060ceb5257f1c in planner (parse=0x60ceb6f63558,
     query_string=0x60ceb6f62020 "EXPLAIN (COSTS OFF)\nSELECT COUNT(*) 
FROM guid1 WHERE guid_field <> '", '1' <repeats 32 times>, "' 
OR\n\t\t\t\t\t\t\tguid_field <> 
'3f3e3c3b-3a30-3938-3736-353433a2313e';", cursorOptions=2048,
     boundParams=0x0) at planner.c:282
#21 0x000060ceb53b89d9 in pg_plan_query (querytree=0x60ceb6f63558,
     query_string=0x60ceb6f62020 "EXPLAIN (COSTS OFF)\nSELECT COUNT(*) 
FROM guid1 WHERE guid_field <> '", '1' <repeats 32 times>, "' 
OR\n\t\t\t\t\t\t\tguid_field <> 
'3f3e3c3b-3a30-3938-3736-353433a2313e';", cursorOptions=2048,
     boundParams=0x0) at postgres.c:912
#22 0x000060ceb501feeb in standard_ExplainOneQuery 
(query=0x60ceb6f63558, cursorOptions=2048, into=0x0,
     es=0x60ceb703acc8,
     queryString=0x60ceb6f62020 "EXPLAIN (COSTS OFF)\nSELECT COUNT(*) 
FROM guid1 WHERE guid_field <> '", '1' <repeats 32 times>, "' 
OR\n\t\t\t\t\t\t\tguid_field <> 
'3f3e3c3b-3a30-3938-3736-353433a2313e';", params=0x0, queryEnv=0x0)
     at explain.c:491
#23 0x000060ceb501fd09 in ExplainOneQuery (query=0x60ceb6f63558, 
cursorOptions=2048, into=0x0, es=0x60ceb703acc8,
     queryString=0x60ceb6f62020 "EXPLAIN (COSTS OFF)\nSELECT COUNT(*) 
FROM guid1 WHERE guid_field <> '", '1' <repeats 32 times>, "' 
OR\n\t\t\t\t\t\t\tguid_field <> 
'3f3e3c3b-3a30-3938-3736-353433a2313e';", params=0x0, queryEnv=0x0)
     at explain.c:447
--Type <RET> for more, q to quit, c to continue without paging--
#24 0x000060ceb501f939 in ExplainQuery (pstate=0x60ceb703abb8, 
stmt=0x60ceb6f63398, params=0x0, dest=0x60ceb703ab28)
     at explain.c:343
#25 0x000060ceb53c32e0 in standard_ProcessUtility (pstmt=0x60ceb6f63448,
     queryString=0x60ceb6f62020 "EXPLAIN (COSTS OFF)\nSELECT COUNT(*) 
FROM guid1 WHERE guid_field <> '", '1' <repeats 32 times>, "' 
OR\n\t\t\t\t\t\t\tguid_field <> 
'3f3e3c3b-3a30-3938-3736-353433a2313e';", readOnlyTree=false,
     context=PROCESS_UTILITY_TOPLEVEL, params=0x0, queryEnv=0x0, 
dest=0x60ceb703ab28, qc=0x7fff7ea16530) at utility.c:863
#26 0x000060ceb53c2852 in ProcessUtility (pstmt=0x60ceb6f63448,
     queryString=0x60ceb6f62020 "EXPLAIN (COSTS OFF)\nSELECT COUNT(*) 
FROM guid1 WHERE guid_field <> '", '1' <repeats 32 times>, "' 
OR\n\t\t\t\t\t\t\tguid_field <> 
'3f3e3c3b-3a30-3938-3736-353433a2313e';", readOnlyTree=false,
     context=PROCESS_UTILITY_TOPLEVEL, params=0x0, queryEnv=0x0, 
dest=0x60ceb703ab28, qc=0x7fff7ea16530) at utility.c:523
#27 0x000060ceb53c10cd in PortalRunUtility (portal=0x60ceb6fe6c50, 
pstmt=0x60ceb6f63448, isTopLevel=true,
     setHoldSnapshot=true, dest=0x60ceb703ab28, qc=0x7fff7ea16530) at 
pquery.c:1158
#28 0x000060ceb53c0e0a in FillPortalStore (portal=0x60ceb6fe6c50, 
isTopLevel=true) at pquery.c:1031
#29 0x000060ceb53c06bb in PortalRun (portal=0x60ceb6fe6c50, 
count=9223372036854775807, isTopLevel=true, run_once=true,
     dest=0x60ceb6f63be8, altdest=0x60ceb6f63be8, qc=0x7fff7ea16780) at 
pquery.c:763
#30 0x000060ceb53b911f in exec_simple_query (
     query_string=0x60ceb6f62020 "EXPLAIN (COSTS OFF)\nSELECT COUNT(*) 
FROM guid1 WHERE guid_field <> '", '1' <repeats 32 times>, "' 
OR\n\t\t\t\t\t\t\tguid_field <> 
'3f3e3c3b-3a30-3938-3736-353433a2313e';") at postgres.c:1284
#31 0x000060ceb53be4ef in PostgresMain (dbname=0x60ceb6fa0c00 
"regression", username=0x60ceb6fa0be8 "alena")
--Type <RET> for more, q to quit, c to continue without paging--
     at postgres.c:4766
#32 0x000060ceb53b4c2a in BackendMain (startup_data=0x7fff7ea16a04 "", 
startup_data_len=4) at backend_startup.c:107
#33 0x000060ceb52c9b80 in postmaster_child_launch (child_type=B_BACKEND, 
startup_data=0x7fff7ea16a04 "",
     startup_data_len=4, client_sock=0x7fff7ea16a50) at launch_backend.c:274
#34 0x000060ceb52cfe87 in BackendStartup (client_sock=0x7fff7ea16a50) at 
postmaster.c:3495
#35 0x000060ceb52cd0df in ServerLoop () at postmaster.c:1662
#36 0x000060ceb52cc9a6 in PostmasterMain (argc=3, argv=0x60ceb6ec6d10) 
at postmaster.c:1360
#37 0x000060ceb517671c in main (argc=3, argv=0x60ceb6ec6d10) at main.c:197

I have fixed it by adding the condition that the opno of the clause must 
be a member of the opfamily of the index.

tp = SearchSysCache3(AMOPOPID,
             ObjectIdGetDatum(opno),
             CharGetDatum(AMOP_SEARCH),
             ObjectIdGetDatum(index->opfamily[indexcol]));
if (!HeapTupleIsValid(tp))
return NULL;

ReleaseSysCache(tp);

I attached the diff file and new versions of patches.

-- 
Regards,
Alena Rybakina
Postgres Professional: http://www.postgrespro.com
The Russian Postgres Company
From 8763d61f689dc4ebca125868d5764657064fd9c7 Mon Sep 17 00:00:00 2001
From: Alexander Korotkov <[email-masked]>
Date: Mon, 5 Aug 2024 21:27:02 +0300
Subject: [PATCH 1/2] Transform OR-clauses to SAOP's during index matching

Here Ci is an i-th constant or parameters expression, 'expr' is non-constant
expression, 'op' is an operator which returns boolean result and has a commuter
(for the case of reverse order of constant and non-constant parts of the
expression, like 'Cn op expr').

This transformation allows handling long OR-clauses with single IndexScan
avoiding slower bitmap scans.

index c0fcc7d78df..34dda1b6df6 100644

+/*
+		/* RestrictInfo parameters must match parent */
+		 * We have only Const's.  In this case we can construct an array
 
 SELECT * FROM tenk1
 
+EXPLAIN (COSTS OFF)
+SELECT * FROM tenk1

 
+EXPLAIN (COSTS OFF)
+SELECT * FROM tenk1
 
+EXPLAIN (COSTS OFF)
 
+explain (costs off)

From 6b1e6f538bdfbeafda457fe851fff829d4ebfd26 Mon Sep 17 00:00:00 2001
From: Alexander Korotkov <[email-masked]>
Date: Sun, 28 Jul 2024 16:36:34 +0300
Subject: [PATCH 2/2] Teach bitmap path generation about transforming
 OR-clauses to SAOP's

When optimizer generates bitmap paths, it considers breaking OR-clause
arguments one-by-one.  But now, a group of similar OR-clauses can be
transformed into SAOP during index matching.  So, bitmap paths should
keep up.

This commit teaches bitmap paths generation machinery to group similar
OR-clauses into dedicated RestrictInfos.  Those RestrictInfos are considered
both to match index as a whole (as SAOP), or to match as a set of individual
OR-clause argument one-by-one (the old way).

Therefore, bitmap path generation will takes advantage of OR-clauses to SAOP's
transformation.  The old way of handling them is also considered.  So, there
shouldn't be planning regression.

Discussion: https://postgr.es/m/567ED6CA.2040504%40sigaev.ru
Reviewed-by: Alexander Korotkov <[email-masked]>
---
 src/backend/optimizer/path/indxpath.c      | 368 ++++++++++++++++++++-
 src/test/regress/expected/create_index.out | 121 ++++++-
 src/test/regress/expected/join.out         |  56 ++--
 src/test/regress/expected/rowsecurity.out  |   7 +
 src/test/regress/expected/stats_ext.out    |  12 +
 src/test/regress/expected/uuid.out         |  31 ++
 src/test/regress/sql/create_index.sql      |  27 ++
 src/test/regress/sql/rowsecurity.sql       |   1 +
 src/test/regress/sql/stats_ext.sql         |   3 +
 src/test/regress/sql/uuid.sql              |  12 +
 src/tools/pgindent/typedefs.list           |   1 +
 11 files changed, 592 insertions(+), 47 deletions(-)

diff --git a/src/backend/optimizer/path/indxpath.c b/src/backend/optimizer/path/indxpath.c
index 34dda1b6df6..b836af6fb55 100644
--- a/src/backend/optimizer/path/indxpath.c
+++ b/src/backend/optimizer/path/indxpath.c
@@ -20,6 +20,7 @@
 #include "access/stratnum.h"
 #include "access/sysattr.h"
 #include "catalog/pg_am.h"
+#include "catalog/pg_amop.h"
 #include "catalog/pg_operator.h"
 #include "catalog/pg_opfamily.h"
 #include "catalog/pg_type.h"
@@ -1172,6 +1173,325 @@ build_paths_for_OR(PlannerInfo *root, RelOptInfo *rel,
 	return result;
 }
 
+/*
+ * Data structure representing information about OR-clause argument and its
+ * matching index key.  Used for grouping of similar OR-clause arguments in
+ * group_similar_or_args().
+ */
+typedef struct
+{
+	int			indexnum;		/* index of the matching index */
+	int			colnum;			/* index of the matching column */
+	Oid			opno;			/* OID of the OpClause operator */
+	Oid			inputcollid;	/* OID of the OpClause input collation */
+	int			argindex;		/* index of the clause in the list of
+								 * arguments */
+} OrArgIndexMatch;
+
+/*
+ * Comparison function for OrArgIndexMatch which provides sort order placing
+ * similar OR-clause arguments together.
+ */
+static int
+or_arg_index_match_cmp(const void *a, const void *b)
+{
+	const OrArgIndexMatch *match_a = (const OrArgIndexMatch *) a;
+	const OrArgIndexMatch *match_b = (const OrArgIndexMatch *) b;
+
+	if (match_a->indexnum < match_b->indexnum)
+		return -1;
+	else if (match_a->indexnum > match_b->indexnum)
+		return 1;
+
+	if (match_a->colnum < match_b->colnum)
+		return -1;
+	else if (match_a->colnum > match_b->colnum)
+		return 1;
+
+	if (match_a->opno < match_b->opno)
+		return -1;
+	else if (match_a->opno > match_b->opno)
+		return 1;
+
+	if (match_a->inputcollid < match_b->inputcollid)
+		return -1;
+	else if (match_a->inputcollid > match_b->inputcollid)
+		return 1;
+
+	if (match_a->argindex < match_b->argindex)
+		return -1;
+	else if (match_a->argindex > match_b->argindex)
+		return 1;
+
+	return 0;
+}
+
+/*
+ * group_similar_or_args
+ *		Group similar OR-arguments intro dedicated RestrictInfos.  Process
+ *		arguments of 'rinfo' clause, returns the processed list of arguments.
+ *
+ * Similar arguments clauses of form "indexkey op constant" having same
+ * indexkey, operator, and collation.  Constant may comprise either Const
+ * or Param.
+ */
+static List *
+group_similar_or_args(PlannerInfo *root, RelOptInfo *rel, RestrictInfo *rinfo)
+{
+	int			n;
+	int			i;
+	int			group_start;
+	OrArgIndexMatch *matches;
+	ListCell   *lc;
+	ListCell   *lc2;
+	List	   *orargs;
+	List	   *result = NIL;
+
+	Assert(IsA(rinfo->orclause, BoolExpr));
+	orargs = ((BoolExpr *) rinfo->orclause)->args;
+	n = list_length(orargs);
+
+	/*
+	 * Allocate and fill OrArgIndexMatch struct for each clause in the
+	 * argument list.
+	 */
+	i = -1;
+	matches = (OrArgIndexMatch *) palloc(sizeof(OrArgIndexMatch) * n);
+	foreach(lc, orargs)
+	{
+		Node	   *arg = lfirst(lc);
+		RestrictInfo *argrinfo;
+		OpExpr	   *clause;
+		Oid			opno;
+		Node	   *leftop,
+				   *rightop;
+		Node	   *nonConstExpr;
+		int			indexnum;
+		int			colnum;
+
+		i++;
+		matches[i].argindex = i;
+		matches[i].indexnum = -1;
+		matches[i].colnum = -1;
+		matches[i].opno = InvalidOid;
+		matches[i].inputcollid = InvalidOid;
+
+		if (!IsA(arg, RestrictInfo))
+			continue;
+
+		argrinfo = castNode(RestrictInfo, arg);
+
+		/* Only operator clauses scan match  */
+		if (!IsA(argrinfo->clause, OpExpr))
+			continue;
+
+		clause = (OpExpr *) argrinfo->clause;
+		opno = clause->opno;
+
+		/* Only binary operators can match  */
+		if (list_length(clause->args) != 2)
+			return NULL;
+
+		/*
+		 * Ignore any RelabelType node above the operands.  This is needed to
+		 * be able to apply indexscanning in binary-compatible-operator cases.
+		 * Note: we can assume there is at most one RelabelType node;
+		 * eval_const_expressions() will have simplified if more than one.
+		 */
+		leftop = get_leftop(clause);
+		if (IsA(leftop, RelabelType))
+			leftop = (Node *) ((RelabelType *) leftop)->arg;
+
+		rightop = get_rightop(clause);
+		if (IsA(rightop, RelabelType))
+			rightop = (Node *) ((RelabelType *) rightop)->arg;
+
+		/*
+		 * Check for clauses of the form: (indexkey operator constant) or
+		 * (constant operator indexkey).  But we don't know a particular index
+		 * yet.  First check for a constant, which must be Const or Param.
+		 * That's cheaper than search for an index key among all indexes.
+		 */
+		if (IsA(leftop, Const) || IsA(leftop, Param))
+		{
+			opno = get_commutator(opno);
+
+			if (!OidIsValid(opno))
+			{
+				/* commutator doesn't exist, we can't reverse the order */
+				continue;
+			}
+			nonConstExpr = rightop;
+		}
+		else if (IsA(rightop, Const) || IsA(rightop, Param))
+		{
+			nonConstExpr = leftop;
+		}
+		else
+		{
+			continue;
+		}
+
+		/*
+		 * Match non-constant part to the index key.  It's possible that a
+		 * single non-constant part matches multiple index keys.  It's OK, we
+		 * just stop with first matching index key.  Given that this choice is
+		 * determined the same for every clause, we will group similar clauses
+		 * together anyway.
+		 */
+		indexnum = 0;
+		foreach(lc2, rel->indexlist)
+		{
+			IndexOptInfo *index = (IndexOptInfo *) lfirst(lc2);
+
+			/* Ignore index if it doesn't support bitmap scans */
+			if (!index->amhasgetbitmap)
+				continue;
+
+			for (colnum = 0; colnum < index->nkeycolumns; colnum++)
+			{
+				if (match_index_to_operand(nonConstExpr, colnum, index))
+				{
+					matches[i].indexnum = indexnum;
+					matches[i].colnum = colnum;
+					matches[i].opno = opno;
+					matches[i].inputcollid = clause->inputcollid;
+				}
+			}
+			indexnum++;
+		}
+	}
+
+	/* Sort clauses to make similar clauses go together */
+	pg_qsort(matches, n, sizeof(OrArgIndexMatch), or_arg_index_match_cmp);
+
+	/* Group similar clauses into */
+	group_start = 0;
+	for (i = 1; i <= n; i++)
+	{
+		/* Check if it's a group boundary */
+		if (group_start >= 0 &&
+			(i == n ||
+			 matches[i].indexnum != matches[group_start].indexnum ||
+			 matches[i].colnum != matches[group_start].colnum ||
+			 matches[i].opno != matches[group_start].opno ||
+			 matches[i].inputcollid != matches[group_start].inputcollid ||
+			 matches[i].indexnum == -1))
+		{
+			/*
+			 * One clause in group: add it "as is" to the upper-level OR.
+			 */
+			if (i - group_start == 1)
+			{
+				result = lappend(result,
+								 list_nth(orargs,
+										  matches[group_start].argindex));
+			}
+			else
+			{
+				/*
+				 * Two or more clauses in a group: create a nested OR.
+				 */
+				List	   *args = NIL;
+				RestrictInfo *subrinfo = makeNode(RestrictInfo);
+				int			j;
+
+				Assert(i - group_start >= 2);
+
+				/* Construct the list of nested OR arguments */
+				for (j = group_start; j < i; j++)
+					args = lappend(args, list_nth(orargs, matches[j].argindex));
+
+				/* Construct the nested OR and wrap it with RestrictInfo */
+				*subrinfo = *rinfo;
+				subrinfo->clause = make_orclause(args);
+				subrinfo->orclause = subrinfo->clause;
+				result = lappend(result, subrinfo);
+			}
+
+			group_start = i;
+		}
+	}
+	pfree(matches);
+	return result;
+}
+
+/*
+ * make_bitmap_paths_for_or_group
+ *		Generate bitmap paths for a group of similar OR-clause arguments
+ *		produced by group_similar_or_args().
+ *
+ * This function considers two cases: (1) matching a group of clauses to
+ * the index as a whole, and (2) matching the individual clauses one-by-one.
+ * (1) typically comprises an optimal solution.  If not, (2) typically
+ * comprises fair alternative.
+ *
+ * Ideally, we could consider all arbitrary splits of arguments into
+ * subgroups, but that could lead to unacceptable computational complexity.
+ * This is why we only consider two cases of above.
+ */
+static List *
+make_bitmap_paths_for_or_group(PlannerInfo *root, RelOptInfo *rel,
+							   RestrictInfo *ri, List *other_clauses)
+{
+	List	   *jointlist = NIL;
+	List	   *splitlist = NIL;
+	ListCell   *lc;
+	List	   *orargs;
+	List	   *args = ((BoolExpr *) ri->clause)->args;
+	Cost		jointcost = 0.0,
+				splitcost = 0.0;
+	Path	   *bitmapqual;
+	List	   *indlist;
+
+	/*
+	 * First, try to match the whole group to the one index.
+	 */
+	orargs = list_make1(ri);
+	indlist = build_paths_for_OR(root, rel,
+								 orargs,
+								 other_clauses);
+	if (indlist != NIL)
+	{
+		bitmapqual = choose_bitmap_and(root, rel, indlist);
+		jointcost = bitmapqual->total_cost;
+		jointlist = list_make1(bitmapqual);
+	}
+
+	/*
+	 * Also try to match all containing clauses one-by-one.
+	 */
+	foreach(lc, args)
+	{
+		orargs = list_make1(lfirst(lc));
+
+		indlist = build_paths_for_OR(root, rel,
+									 orargs,
+									 other_clauses);
+
+		if (indlist == NIL)
+		{
+			splitlist = NIL;
+			break;
+		}
+
+		bitmapqual = choose_bitmap_and(root, rel, indlist);
+		splitcost += bitmapqual->total_cost;
+		splitlist = lappend(splitlist, bitmapqual);
+	}
+
+	/*
+	 * Pick the best option.
+	 */
+	if (splitlist == NIL)
+		return jointlist;
+	else if (jointlist == NIL)
+		return splitlist;
+	else
+		return (jointcost < splitcost) ? jointlist : splitlist;
+}
+
+
 /*
  * generate_bitmap_or_paths
  *		Look through the list of clauses to find OR clauses, and generate
@@ -1202,6 +1522,7 @@ generate_bitmap_or_paths(PlannerInfo *root, RelOptInfo *rel,
 		List	   *pathlist;
 		Path	   *bitmapqual;
 		ListCell   *j;
+		List	   *groupedArgs;
 
 		/* Ignore RestrictInfos that aren't ORs */
 		if (!restriction_is_or_clause(rinfo))
@@ -1212,7 +1533,13 @@ generate_bitmap_or_paths(PlannerInfo *root, RelOptInfo *rel,
 		 * the OR, else we can't use it.
 		 */
 		pathlist = NIL;
-		foreach(j, ((BoolExpr *) rinfo->orclause)->args)
+
+		/*
+		 * Group the similar OR-clause argument into dedicated RestrictInfos,
+		 * because those RestrictInfos might match to the index as whole.
+		 */
+		groupedArgs = group_similar_or_args(root, rel, rinfo);
+		foreach(j, groupedArgs)
 		{
 			Node	   *orarg = (Node *) lfirst(j);
 			List	   *indlist;
@@ -1232,12 +1559,37 @@ generate_bitmap_or_paths(PlannerInfo *root, RelOptInfo *rel,
 															   andargs,
 															   all_clauses));
 			}
+			else if (restriction_is_or_clause(castNode(RestrictInfo, orarg)))
+			{
+				RestrictInfo *ri = castNode(RestrictInfo, orarg);
+
+				/*
+				 * Generate bitmap paths for the group of similar OR-clause
+				 * arguments.  In this case we need to immediately remove the
+				 * rinfo from other clauses.  This is because rinfo can be
+				 * transformed during index matching.  So, we might be unable
+				 * to remove that later.
+				 */
+				indlist = make_bitmap_paths_for_or_group(root,
+														 rel, ri,
+														 list_delete(all_clauses, rinfo));
+
+				if (indlist == NIL)
+				{
+					pathlist = NIL;
+					break;
+				}
+				else
+				{
+					pathlist = list_concat(pathlist, indlist);
+					continue;
+				}
+			}
 			else
 			{
 				RestrictInfo *ri = castNode(RestrictInfo, orarg);
 				List	   *orargs;
 
-				Assert(!restriction_is_or_clause(ri));
 				orargs = list_make1(ri);
 
 				indlist = build_paths_for_OR(root, rel,
@@ -2807,6 +3159,7 @@ match_orclause_to_indexcol(PlannerInfo *root,
 	Oid			inputcollid = InvalidOid;
 	bool		firstTime = true;
 	bool		have_param = false;
+	HeapTuple	tp;
 
 	Assert(IsA(orclause, BoolExpr));
 	Assert(orclause->boolop == OR_EXPR);
@@ -2842,7 +3195,7 @@ match_orclause_to_indexcol(PlannerInfo *root,
 		if (list_length(subClause->args) != 2)
 			return NULL;
 
-		/* RestrictInfo parameters must match parent */
+		/* RestrictInfo parameters dmust match parent */
 		if (subRinfo->is_pushed_down != rinfo->is_pushed_down ||
 			subRinfo->is_clone != rinfo->is_clone ||
 			subRinfo->security_level != rinfo->security_level ||
@@ -2883,6 +3236,15 @@ match_orclause_to_indexcol(PlannerInfo *root,
 			return NULL;
 		}
 
+		tp = SearchSysCache3(AMOPOPID,
+							ObjectIdGetDatum(opno),
+							CharGetDatum(AMOP_SEARCH),
+							ObjectIdGetDatum(index->opfamily[indexcol]));
+		if (!HeapTupleIsValid(tp))
+			return NULL;
+
+		ReleaseSysCache(tp);
+
 		/*
 		 * Ignore any RelabelType node above the operands.  This is needed to
 		 * be able to apply indexscanning in binary-compatible-operator cases.
diff --git a/src/test/regress/expected/create_index.out b/src/test/regress/expected/create_index.out
index c2b25936c8c..cac076abb88 100644
--- a/src/test/regress/expected/create_index.out
+++ b/src/test/regress/expected/create_index.out
@@ -1913,6 +1913,27 @@ SELECT * FROM tenk1
       42 |    5530 |   0 |    2 |   2 |      2 |      42 |       42 |          42 |        42 |       42 |  84 |   85 | QBAAAA   | SEIAAA   | OOOOxx
 (1 row)
 
+EXPLAIN (COSTS OFF)
+SELECT * FROM tenk1
+  WHERE thousand = 42 AND (tenthous = 1::numeric OR tenthous = 3::int4 OR tenthous = 42::numeric);
+                                                 QUERY PLAN                                                  
+-------------------------------------------------------------------------------------------------------------
+ Bitmap Heap Scan on tenk1
+   Recheck Cond: (thousand = 42)
+   Filter: (((tenthous)::numeric = '1'::numeric) OR (tenthous = 3) OR ((tenthous)::numeric = '42'::numeric))
+   ->  Bitmap Index Scan on tenk1_thous_tenthous
+         Index Cond: (thousand = 42)
+(5 rows)
+
+EXPLAIN (COSTS OFF)
+SELECT * FROM tenk1
+  WHERE tenthous = 1::numeric OR tenthous = 3::int4 OR tenthous = 42::numeric;
+                                                 QUERY PLAN                                                  
+-------------------------------------------------------------------------------------------------------------
+ Seq Scan on tenk1
+   Filter: (((tenthous)::numeric = '1'::numeric) OR (tenthous = 3) OR ((tenthous)::numeric = '42'::numeric))
+(2 rows)
+
 EXPLAIN (COSTS OFF)
 SELECT count(*) FROM tenk1
   WHERE hundred = 42 AND (thousand = 42 OR thousand = 99);
@@ -1982,25 +2003,24 @@ SELECT count(*) FROM tenk1
 EXPLAIN (COSTS OFF)
 SELECT count(*) FROM tenk1
   WHERE hundred = 42 AND (thousand = 42 OR thousand = 99 OR tenthous < 2) OR thousand = 41;
-                                                       QUERY PLAN                                                       
-------------------------------------------------------------------------------------------------------------------------
+                                                         QUERY PLAN                                                          
+-----------------------------------------------------------------------------------------------------------------------------
  Aggregate
    ->  Bitmap Heap Scan on tenk1
-         Recheck Cond: (((hundred = 42) AND ((thousand = 42) OR (thousand = 99) OR (tenthous < 2))) OR (thousand = 41))
+         Recheck Cond: (((hundred = 42) AND ((thousand = ANY ('{42,99}'::integer[])) OR (tenthous < 2))) OR (thousand = 41))
+         Filter: (((hundred = 42) AND ((thousand = 42) OR (thousand = 99) OR (tenthous < 2))) OR (thousand = 41))
          ->  BitmapOr
                ->  BitmapAnd
                      ->  Bitmap Index Scan on tenk1_hundred
                            Index Cond: (hundred = 42)
                      ->  BitmapOr
                            ->  Bitmap Index Scan on tenk1_thous_tenthous
-                                 Index Cond: (thousand = 42)
-                           ->  Bitmap Index Scan on tenk1_thous_tenthous
-                                 Index Cond: (thousand = 99)
+                                 Index Cond: (thousand = ANY ('{42,99}'::integer[]))
                            ->  Bitmap Index Scan on tenk1_thous_tenthous
                                  Index Cond: (tenthous < 2)
                ->  Bitmap Index Scan on tenk1_thous_tenthous
                      Index Cond: (thousand = 41)
-(16 rows)
+(15 rows)
 
 SELECT count(*) FROM tenk1
   WHERE hundred = 42 AND (thousand = 42 OR thousand = 99 OR tenthous < 2) OR thousand = 41;
@@ -2012,22 +2032,21 @@ SELECT count(*) FROM tenk1
 EXPLAIN (COSTS OFF)
 SELECT count(*) FROM tenk1
   WHERE hundred = 42 AND (thousand = 42 OR thousand = 41 OR thousand = 99 AND tenthous = 2);
-                                                       QUERY PLAN                                                        
--------------------------------------------------------------------------------------------------------------------------
+                                                          QUERY PLAN                                                          
+------------------------------------------------------------------------------------------------------------------------------
  Aggregate
    ->  Bitmap Heap Scan on tenk1
-         Recheck Cond: ((hundred = 42) AND ((thousand = 42) OR (thousand = 41) OR ((thousand = 99) AND (tenthous = 2))))
+         Recheck Cond: ((hundred = 42) AND (((thousand = 99) AND (tenthous = 2)) OR (thousand = ANY ('{42,41}'::integer[]))))
+         Filter: ((thousand = 42) OR (thousand = 41) OR ((thousand = 99) AND (tenthous = 2)))
          ->  BitmapAnd
                ->  Bitmap Index Scan on tenk1_hundred
                      Index Cond: (hundred = 42)
                ->  BitmapOr
-                     ->  Bitmap Index Scan on tenk1_thous_tenthous
-                           Index Cond: (thousand = 42)
-                     ->  Bitmap Index Scan on tenk1_thous_tenthous
-                           Index Cond: (thousand = 41)
                      ->  Bitmap Index Scan on tenk1_thous_tenthous
                            Index Cond: ((thousand = 99) AND (tenthous = 2))
-(13 rows)
+                     ->  Bitmap Index Scan on tenk1_thous_tenthous
+                           Index Cond: (thousand = ANY ('{42,41}'::integer[]))
+(12 rows)
 
 SELECT count(*) FROM tenk1
   WHERE hundred = 42 AND (thousand = 42 OR thousand = 41 OR thousand = 99 AND tenthous = 2);
@@ -2036,6 +2055,78 @@ SELECT count(*) FROM tenk1
     10
 (1 row)
 
+EXPLAIN (COSTS OFF)
+SELECT count(*) FROM tenk1, tenk2
+  WHERE tenk1.hundred = 42 AND (tenk2.thousand = 42 OR tenk1.thousand = 41 OR tenk2.tenthous = 2) AND
+  tenk2.hundred = tenk1.hundred;
+                                          QUERY PLAN                                           
+-----------------------------------------------------------------------------------------------
+ Aggregate
+   ->  Nested Loop
+         Join Filter: ((tenk2.thousand = 42) OR (tenk1.thousand = 41) OR (tenk2.tenthous = 2))
+         ->  Bitmap Heap Scan on tenk1
+               Recheck Cond: (hundred = 42)
+               ->  Bitmap Index Scan on tenk1_hundred
+                     Index Cond: (hundred = 42)
+         ->  Materialize
+               ->  Bitmap Heap Scan on tenk2
+                     Recheck Cond: (hundred = 42)
+                     ->  Bitmap Index Scan on tenk2_hundred
+                           Index Cond: (hundred = 42)
+(12 rows)
+
+EXPLAIN (COSTS OFF)
+SELECT count(*) FROM tenk1, tenk2
+  WHERE tenk1.hundred = 42 AND (tenk2.thousand = 42 OR tenk2.thousand = 41 OR tenk2.tenthous = 2) AND
+  tenk2.hundred = tenk1.hundred;
+                                  QUERY PLAN                                  
+------------------------------------------------------------------------------
+ Aggregate
+   ->  Nested Loop
+         ->  Bitmap Heap Scan on tenk2
+               Recheck Cond: (hundred = 42)
+               Filter: ((thousand = 42) OR (thousand = 41) OR (tenthous = 2))
+               ->  Bitmap Index Scan on tenk2_hundred
+                     Index Cond: (hundred = 42)
+         ->  Index Only Scan using tenk1_hundred on tenk1
+               Index Cond: (hundred = 42)
+(9 rows)
+
+EXPLAIN (COSTS OFF)
+SELECT count(*) FROM tenk1 JOIN tenk2 ON
+  tenk1.hundred = 42 AND (tenk2.thousand = 42 OR tenk2.thousand = 41 OR tenk2.tenthous = 2) AND
+  tenk2.hundred = tenk1.hundred;
+                                  QUERY PLAN                                  
+------------------------------------------------------------------------------
+ Aggregate
+   ->  Nested Loop
+         ->  Bitmap Heap Scan on tenk2
+               Recheck Cond: (hundred = 42)
+               Filter: ((thousand = 42) OR (thousand = 41) OR (tenthous = 2))
+               ->  Bitmap Index Scan on tenk2_hundred
+                     Index Cond: (hundred = 42)
+         ->  Index Only Scan using tenk1_hundred on tenk1
+               Index Cond: (hundred = 42)
+(9 rows)
+
+EXPLAIN (COSTS OFF)
+SELECT count(*) FROM tenk1 LEFT JOIN tenk2 ON
+  tenk1.hundred = 42 AND (tenk2.thousand = 42 OR tenk2.thousand = 41 OR tenk2.tenthous = 2) AND
+  tenk2.hundred = tenk1.hundred;
+                                     QUERY PLAN                                     
+------------------------------------------------------------------------------------
+ Aggregate
+   ->  Nested Loop Left Join
+         Join Filter: (tenk1.hundred = 42)
+         ->  Index Only Scan using tenk1_hundred on tenk1
+         ->  Memoize
+               Cache Key: tenk1.hundred
+               Cache Mode: logical
+               ->  Index Scan using tenk2_hundred on tenk2
+                     Index Cond: (hundred = tenk1.hundred)
+                     Filter: ((thousand = 42) OR (thousand = 41) OR (tenthous = 2))
+(10 rows)
+
 --
 -- Check behavior with duplicate index column contents
 --
diff --git a/src/test/regress/expected/join.out b/src/test/regress/expected/join.out
index abe98ff3c53..d26a93831d5 100644
--- a/src/test/regress/expected/join.out
+++ b/src/test/regress/expected/join.out
@@ -4226,20 +4226,20 @@ select * from tenk1 a join tenk1 b on
  Nested Loop
    Join Filter: (((a.unique1 = 1) AND (b.unique1 = 2)) OR ((a.unique2 = 3) AND (b.hundred = 4)))
    ->  Bitmap Heap Scan on tenk1 b
-         Recheck Cond: ((unique1 = 2) OR (hundred = 4))
+         Recheck Cond: ((hundred = 4) OR (unique1 = 2))
          ->  BitmapOr
-               ->  Bitmap Index Scan on tenk1_unique1
-                     Index Cond: (unique1 = 2)
                ->  Bitmap Index Scan on tenk1_hundred
                      Index Cond: (hundred = 4)
+               ->  Bitmap Index Scan on tenk1_unique1
+                     Index Cond: (unique1 = 2)
    ->  Materialize
          ->  Bitmap Heap Scan on tenk1 a
-               Recheck Cond: ((unique1 = 1) OR (unique2 = 3))
+               Recheck Cond: ((unique2 = 3) OR (unique1 = 1))
                ->  BitmapOr
-                     ->  Bitmap Index Scan on tenk1_unique1
-                           Index Cond: (unique1 = 1)
                      ->  Bitmap Index Scan on tenk1_unique2
                            Index Cond: (unique2 = 3)
+                     ->  Bitmap Index Scan on tenk1_unique1
+                           Index Cond: (unique1 = 1)
 (17 rows)
 
 explain (costs off)
@@ -4253,12 +4253,12 @@ select * from tenk1 a join tenk1 b on
          Filter: ((unique1 = 2) OR (ten = 4))
    ->  Materialize
          ->  Bitmap Heap Scan on tenk1 a
-               Recheck Cond: ((unique1 = 1) OR (unique2 = 3))
+               Recheck Cond: ((unique2 = 3) OR (unique1 = 1))
                ->  BitmapOr
-                     ->  Bitmap Index Scan on tenk1_unique1
-                           Index Cond: (unique1 = 1)
                      ->  Bitmap Index Scan on tenk1_unique2
                            Index Cond: (unique2 = 3)
+                     ->  Bitmap Index Scan on tenk1_unique1
+                           Index Cond: (unique1 = 1)
 (12 rows)
 
 explain (costs off)
@@ -4270,21 +4270,21 @@ select * from tenk1 a join tenk1 b on
  Nested Loop
    Join Filter: (((a.unique1 = 1) AND (b.unique1 = 2)) OR (((a.unique2 = 3) OR (a.unique2 = 7)) AND (b.hundred = 4)))
    ->  Bitmap Heap Scan on tenk1 b
-         Recheck Cond: ((unique1 = 2) OR (hundred = 4))
+         Recheck Cond: ((hundred = 4) OR (unique1 = 2))
          ->  BitmapOr
-               ->  Bitmap Index Scan on tenk1_unique1
-                     Index Cond: (unique1 = 2)
                ->  Bitmap Index Scan on tenk1_hundred
                      Index Cond: (hundred = 4)
+               ->  Bitmap Index Scan on tenk1_unique1
+                     Index Cond: (unique1 = 2)
    ->  Materialize
          ->  Bitmap Heap Scan on tenk1 a
-               Recheck Cond: ((unique1 = 1) OR (unique2 = ANY ('{3,7}'::integer[])))
+               Recheck Cond: ((unique2 = ANY ('{3,7}'::integer[])) OR (unique1 = 1))
                Filter: ((unique1 = 1) OR (unique2 = 3) OR (unique2 = 7))
                ->  BitmapOr
-                     ->  Bitmap Index Scan on tenk1_unique1
-                           Index Cond: (unique1 = 1)
                      ->  Bitmap Index Scan on tenk1_unique2
                            Index Cond: (unique2 = ANY ('{3,7}'::integer[]))
+                     ->  Bitmap Index Scan on tenk1_unique1
+                           Index Cond: (unique1 = 1)
 (18 rows)
 
 explain (costs off)
@@ -4296,21 +4296,21 @@ select * from tenk1 a join tenk1 b on
  Nested Loop
    Join Filter: (((a.unique1 = 1) AND (b.unique1 = 2)) OR (((a.unique2 = 3) OR (a.unique2 = 7)) AND (b.hundred = 4)))
    ->  Bitmap Heap Scan on tenk1 b
-         Recheck Cond: ((unique1 = 2) OR (hundred = 4))
+         Recheck Cond: ((hundred = 4) OR (unique1 = 2))
          ->  BitmapOr
-               ->  Bitmap Index Scan on tenk1_unique1
-                     Index Cond: (unique1 = 2)
                ->  Bitmap Index Scan on tenk1_hundred
                      Index Cond: (hundred = 4)
+               ->  Bitmap Index Scan on tenk1_unique1
+                     Index Cond: (unique1 = 2)
    ->  Materialize
          ->  Bitmap Heap Scan on tenk1 a
-               Recheck Cond: ((unique1 = 1) OR (unique2 = ANY ('{3,7}'::integer[])))
+               Recheck Cond: ((unique2 = ANY ('{3,7}'::integer[])) OR (unique1 = 1))
                Filter: ((unique1 = 1) OR (unique2 = 3) OR (unique2 = 7))
                ->  BitmapOr
-                     ->  Bitmap Index Scan on tenk1_unique1
-                           Index Cond: (unique1 = 1)
                      ->  Bitmap Index Scan on tenk1_unique2
                            Index Cond: (unique2 = ANY ('{3,7}'::integer[]))
+                     ->  Bitmap Index Scan on tenk1_unique1
+                           Index Cond: (unique1 = 1)
 (18 rows)
 
 explain (costs off)
@@ -4324,18 +4324,16 @@ select * from tenk1 a join tenk1 b on
    ->  Seq Scan on tenk1 b
    ->  Materialize
          ->  Bitmap Heap Scan on tenk1 a
-               Recheck Cond: ((unique1 < 20) OR (unique1 = 3) OR (unique1 = 1) OR (unique2 = ANY ('{3,7}'::integer[])))
+               Recheck Cond: ((unique2 = ANY ('{3,7}'::integer[])) OR (unique1 = ANY ('{3,1}'::integer[])) OR (unique1 < 20))
                Filter: ((unique1 < 20) OR (unique1 = 3) OR (unique1 = 1) OR (unique2 = 3) OR (unique2 = 7))
                ->  BitmapOr
-                     ->  Bitmap Index Scan on tenk1_unique1
-                           Index Cond: (unique1 < 20)
-                     ->  Bitmap Index Scan on tenk1_unique1
-                           Index Cond: (unique1 = 3)
-                     ->  Bitmap Index Scan on tenk1_unique1
-                           Index Cond: (unique1 = 1)
                      ->  Bitmap Index Scan on tenk1_unique2
                            Index Cond: (unique2 = ANY ('{3,7}'::integer[]))
-(16 rows)
+                     ->  Bitmap Index Scan on tenk1_unique1
+                           Index Cond: (unique1 = ANY ('{3,1}'::integer[]))
+                     ->  Bitmap Index Scan on tenk1_unique1
+                           Index Cond: (unique1 < 20)
+(14 rows)
 
 --
 -- test placement of movable quals in a parameterized join tree
diff --git a/src/test/regress/expected/rowsecurity.out b/src/test/regress/expected/rowsecurity.out
index 319190855bd..ef890b96cc6 100644
--- a/src/test/regress/expected/rowsecurity.out
+++ b/src/test/regress/expected/rowsecurity.out
@@ -4492,6 +4492,13 @@ SELECT * FROM rls_tbl WHERE a <<< 1000;
 ---
 (0 rows)
 
+EXPLAIN (COSTS OFF) SELECT * FROM rls_tbl WHERE a <<< 1000 or a <<< 900;
+        QUERY PLAN        
+--------------------------
+ Result
+   One-Time Filter: false
+(2 rows)
+
 DROP OPERATOR <<< (int, int);
 DROP FUNCTION op_leak(int, int);
 RESET SESSION AUTHORIZATION;
diff --git a/src/test/regress/expected/stats_ext.out b/src/test/regress/expected/stats_ext.out
index 8c4da955084..a4c7be487ef 100644
--- a/src/test/regress/expected/stats_ext.out
+++ b/src/test/regress/expected/stats_ext.out
@@ -3254,6 +3254,8 @@ CREATE OPERATOR <<< (procedure = op_leak, leftarg = int, rightarg = int,
                      restrict = scalarltsel);
 SELECT * FROM tststats.priv_test_tbl WHERE a <<< 0 AND b <<< 0; -- Permission denied
 ERROR:  permission denied for table priv_test_tbl
+SELECT * FROM tststats.priv_test_tbl WHERE a <<< 0 OR b <<< 0;
+ERROR:  permission denied for table priv_test_tbl
 DELETE FROM tststats.priv_test_tbl WHERE a <<< 0 AND b <<< 0; -- Permission denied
 ERROR:  permission denied for table priv_test_tbl
 -- Grant access via a security barrier view, but hide all data
@@ -3268,6 +3270,11 @@ SELECT * FROM tststats.priv_test_view WHERE a <<< 0 AND b <<< 0; -- Should not l
 ---+---
 (0 rows)
 
+SELECT * FROM tststats.priv_test_view WHERE a <<< 0 OR b <<< 0; -- Should not leak
+ a | b 
+---+---
+(0 rows)
+
 DELETE FROM tststats.priv_test_view WHERE a <<< 0 AND b <<< 0; -- Should not leak
 -- Grant table access, but hide all data with RLS
 RESET SESSION AUTHORIZATION;
@@ -3280,6 +3287,11 @@ SELECT * FROM tststats.priv_test_tbl WHERE a <<< 0 AND b <<< 0; -- Should not le
 ---+---
 (0 rows)
 
+SELECT * FROM tststats.priv_test_tbl WHERE a <<< 0 OR b <<< 0;
+ a | b 
+---+---
+(0 rows)
+
 DELETE FROM tststats.priv_test_tbl WHERE a <<< 0 AND b <<< 0; -- Should not leak
 -- privilege checks for pg_stats_ext and pg_stats_ext_exprs
 RESET SESSION AUTHORIZATION;
diff --git a/src/test/regress/expected/uuid.out b/src/test/regress/expected/uuid.out
index 6026e15ed31..8f4ef0d7a6a 100644
--- a/src/test/regress/expected/uuid.out
+++ b/src/test/regress/expected/uuid.out
@@ -129,6 +129,37 @@ CREATE INDEX guid1_btree ON guid1 USING BTREE (guid_field);
 CREATE INDEX guid1_hash  ON guid1 USING HASH  (guid_field);
 -- unique index test
 CREATE UNIQUE INDEX guid1_unique_BTREE ON guid1 USING BTREE (guid_field);
+EXPLAIN (COSTS OFF)
+SELECT COUNT(*) FROM guid1 WHERE guid_field <> '11111111111111111111111111111111' OR
+							guid_field <> '3f3e3c3b-3a30-3938-3736-353433a2313e';
+                                                                   QUERY PLAN                                                                   
+------------------------------------------------------------------------------------------------------------------------------------------------
+ Aggregate
+   ->  Seq Scan on guid1
+         Filter: ((guid_field <> '11111111-1111-1111-1111-111111111111'::uuid) OR (guid_field <> '3f3e3c3b-3a30-3938-3736-353433a2313e'::uuid))
+(3 rows)
+
+EXPLAIN (COSTS OFF)
+SELECT COUNT(*) FROM guid1 WHERE guid_field <= '22222222-2222-2222-2222-222222222222' OR
+									guid_field <= '11111111111111111111111111111111' OR
+									guid_field <= '3f3e3c3b-3a30-3938-3736-353433a2313e';
+                                                                                                   QUERY PLAN                                                                                                   
+----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
+ Aggregate
+   ->  Seq Scan on guid1
+         Filter: ((guid_field <= '22222222-2222-2222-2222-222222222222'::uuid) OR (guid_field <= '11111111-1111-1111-1111-111111111111'::uuid) OR (guid_field <= '3f3e3c3b-3a30-3938-3736-353433a2313e'::uuid))
+(3 rows)
+
+EXPLAIN (COSTS OFF)
+SELECT COUNT(*) FROM guid1 WHERE guid_field = '3f3e3c3b-3a30-3938-3736-353433a2313e' OR
+							guid_field = '11111111111111111111111111111111';
+                                                                  QUERY PLAN                                                                  
+----------------------------------------------------------------------------------------------------------------------------------------------
+ Aggregate
+   ->  Seq Scan on guid1
+         Filter: ((guid_field = '3f3e3c3b-3a30-3938-3736-353433a2313e'::uuid) OR (guid_field = '11111111-1111-1111-1111-111111111111'::uuid))
+(3 rows)
+
 -- should fail
 INSERT INTO guid1(guid_field) VALUES('11111111-1111-1111-1111-111111111111');
 ERROR:  duplicate key value violates unique constraint "guid1_unique_btree"
diff --git a/src/test/regress/sql/create_index.sql b/src/test/regress/sql/create_index.sql
index f74ad415fbf..7e108f9b283 100644
--- a/src/test/regress/sql/create_index.sql
+++ b/src/test/regress/sql/create_index.sql
@@ -750,6 +750,14 @@ SELECT * FROM tenk1
 SELECT * FROM tenk1
   WHERE thousand = 42 AND (tenthous = 1 OR tenthous = 3 OR tenthous = 42);
 
+EXPLAIN (COSTS OFF)
+SELECT * FROM tenk1
+  WHERE thousand = 42 AND (tenthous = 1::numeric OR tenthous = 3::int4 OR tenthous = 42::numeric);
+
+EXPLAIN (COSTS OFF)
+SELECT * FROM tenk1
+  WHERE tenthous = 1::numeric OR tenthous = 3::int4 OR tenthous = 42::numeric;
+
 EXPLAIN (COSTS OFF)
 SELECT count(*) FROM tenk1
   WHERE hundred = 42 AND (thousand = 42 OR thousand = 99);
@@ -780,6 +788,25 @@ SELECT count(*) FROM tenk1
 SELECT count(*) FROM tenk1
   WHERE hundred = 42 AND (thousand = 42 OR thousand = 41 OR thousand = 99 AND tenthous = 2);
 
+EXPLAIN (COSTS OFF)
+SELECT count(*) FROM tenk1, tenk2
+  WHERE tenk1.hundred = 42 AND (tenk2.thousand = 42 OR tenk1.thousand = 41 OR tenk2.tenthous = 2) AND
+  tenk2.hundred = tenk1.hundred;
+
+EXPLAIN (COSTS OFF)
+SELECT count(*) FROM tenk1, tenk2
+  WHERE tenk1.hundred = 42 AND (tenk2.thousand = 42 OR tenk2.thousand = 41 OR tenk2.tenthous = 2) AND
+  tenk2.hundred = tenk1.hundred;
+
+EXPLAIN (COSTS OFF)
+SELECT count(*) FROM tenk1 JOIN tenk2 ON
+  tenk1.hundred = 42 AND (tenk2.thousand = 42 OR tenk2.thousand = 41 OR tenk2.tenthous = 2) AND
+  tenk2.hundred = tenk1.hundred;
+
+EXPLAIN (COSTS OFF)
+SELECT count(*) FROM tenk1 LEFT JOIN tenk2 ON
+  tenk1.hundred = 42 AND (tenk2.thousand = 42 OR tenk2.thousand = 41 OR tenk2.tenthous = 2) AND
+  tenk2.hundred = tenk1.hundred;
 --
 -- Check behavior with duplicate index column contents
 --
diff --git a/src/test/regress/sql/rowsecurity.sql b/src/test/regress/sql/rowsecurity.sql
index 3011d71b12b..6d2414b6044 100644
--- a/src/test/regress/sql/rowsecurity.sql
+++ b/src/test/regress/sql/rowsecurity.sql
@@ -2177,6 +2177,7 @@ CREATE FUNCTION op_leak(int, int) RETURNS bool
 CREATE OPERATOR <<< (procedure = op_leak, leftarg = int, rightarg = int,
                      restrict = scalarltsel);
 SELECT * FROM rls_tbl WHERE a <<< 1000;
+EXPLAIN (COSTS OFF) SELECT * FROM rls_tbl WHERE a <<< 1000 or a <<< 900;
 DROP OPERATOR <<< (int, int);
 DROP FUNCTION op_leak(int, int);
 RESET SESSION AUTHORIZATION;
diff --git a/src/test/regress/sql/stats_ext.sql b/src/test/regress/sql/stats_ext.sql
index 0c08a6cc42e..5c786b16c6f 100644
--- a/src/test/regress/sql/stats_ext.sql
+++ b/src/test/regress/sql/stats_ext.sql
@@ -1634,6 +1634,7 @@ CREATE FUNCTION op_leak(int, int) RETURNS bool
 CREATE OPERATOR <<< (procedure = op_leak, leftarg = int, rightarg = int,
                      restrict = scalarltsel);
 SELECT * FROM tststats.priv_test_tbl WHERE a <<< 0 AND b <<< 0; -- Permission denied
+SELECT * FROM tststats.priv_test_tbl WHERE a <<< 0 OR b <<< 0;
 DELETE FROM tststats.priv_test_tbl WHERE a <<< 0 AND b <<< 0; -- Permission denied
 
 -- Grant access via a security barrier view, but hide all data
@@ -1645,6 +1646,7 @@ GRANT SELECT, DELETE ON tststats.priv_test_view TO regress_stats_user1;
 -- Should now have access via the view, but see nothing and leak nothing
 SET SESSION AUTHORIZATION regress_stats_user1;
 SELECT * FROM tststats.priv_test_view WHERE a <<< 0 AND b <<< 0; -- Should not leak
+SELECT * FROM tststats.priv_test_view WHERE a <<< 0 OR b <<< 0; -- Should not leak
 DELETE FROM tststats.priv_test_view WHERE a <<< 0 AND b <<< 0; -- Should not leak
 
 -- Grant table access, but hide all data with RLS
@@ -1655,6 +1657,7 @@ GRANT SELECT, DELETE ON tststats.priv_test_tbl TO regress_stats_user1;
 -- Should now have direct table access, but see nothing and leak nothing
 SET SESSION AUTHORIZATION regress_stats_user1;
 SELECT * FROM tststats.priv_test_tbl WHERE a <<< 0 AND b <<< 0; -- Should not leak
+SELECT * FROM tststats.priv_test_tbl WHERE a <<< 0 OR b <<< 0;
 DELETE FROM tststats.priv_test_tbl WHERE a <<< 0 AND b <<< 0; -- Should not leak
 
 -- privilege checks for pg_stats_ext and pg_stats_ext_exprs
diff --git a/src/test/regress/sql/uuid.sql b/src/test/regress/sql/uuid.sql
index c88f6d087a7..75ee966ded0 100644
--- a/src/test/regress/sql/uuid.sql
+++ b/src/test/regress/sql/uuid.sql
@@ -63,6 +63,18 @@ CREATE INDEX guid1_hash  ON guid1 USING HASH  (guid_field);
 
 -- unique index test
 CREATE UNIQUE INDEX guid1_unique_BTREE ON guid1 USING BTREE (guid_field);
+
+EXPLAIN (COSTS OFF)
+SELECT COUNT(*) FROM guid1 WHERE guid_field <> '11111111111111111111111111111111' OR
+							guid_field <> '3f3e3c3b-3a30-3938-3736-353433a2313e';
+EXPLAIN (COSTS OFF)
+SELECT COUNT(*) FROM guid1 WHERE guid_field <= '22222222-2222-2222-2222-222222222222' OR
+									guid_field <= '11111111111111111111111111111111' OR
+									guid_field <= '3f3e3c3b-3a30-3938-3736-353433a2313e';
+EXPLAIN (COSTS OFF)
+SELECT COUNT(*) FROM guid1 WHERE guid_field = '3f3e3c3b-3a30-3938-3736-353433a2313e' OR
+							guid_field = '11111111111111111111111111111111';
+
 -- should fail
 INSERT INTO guid1(guid_field) VALUES('11111111-1111-1111-1111-111111111111');
 
diff --git a/src/tools/pgindent/typedefs.list b/src/tools/pgindent/typedefs.list
index 547d14b3e7c..f5c4b514646 100644
--- a/src/tools/pgindent/typedefs.list
+++ b/src/tools/pgindent/typedefs.list
@@ -1763,6 +1763,7 @@ OprCacheKey
 OprInfo
 OprProofCacheEntry
 OprProofCacheKey
+OrArgIndexMatch
 OuterJoinClauseInfo
 OutputPluginCallbacks
 OutputPluginOptions
-- 
2.34.1

diff --git a/src/backend/optimizer/path/indxpath.c b/src/backend/optimizer/path/indxpath.c
index 8e524016c6f..b836af6fb55 100644
--- a/src/backend/optimizer/path/indxpath.c
+++ b/src/backend/optimizer/path/indxpath.c
@@ -20,6 +20,7 @@
 #include "access/stratnum.h"
 #include "access/sysattr.h"
 #include "catalog/pg_am.h"
+#include "catalog/pg_amop.h"
 #include "catalog/pg_operator.h"
 #include "catalog/pg_opfamily.h"
 #include "catalog/pg_type.h"
@@ -3158,6 +3159,7 @@ match_orclause_to_indexcol(PlannerInfo *root,
 	Oid			inputcollid = InvalidOid;
 	bool		firstTime = true;
 	bool		have_param = false;
+	HeapTuple	tp;
 
 	Assert(IsA(orclause, BoolExpr));
 	Assert(orclause->boolop == OR_EXPR);
@@ -3193,7 +3195,7 @@ match_orclause_to_indexcol(PlannerInfo *root,
 		if (list_length(subClause->args) != 2)
 			return NULL;
 
-		/* RestrictInfo parameters must match parent */
+		/* RestrictInfo parameters dmust match parent */
 		if (subRinfo->is_pushed_down != rinfo->is_pushed_down ||
 			subRinfo->is_clone != rinfo->is_clone ||
 			subRinfo->security_level != rinfo->security_level ||
@@ -3234,6 +3236,15 @@ match_orclause_to_indexcol(PlannerInfo *root,
 			return NULL;
 		}
 
+		tp = SearchSysCache3(AMOPOPID,
+							ObjectIdGetDatum(opno),
+							CharGetDatum(AMOP_SEARCH),
+							ObjectIdGetDatum(index->opfamily[indexcol]));
+		if (!HeapTupleIsValid(tp))
+			return NULL;
+
+		ReleaseSysCache(tp);
+
 		/*
 		 * Ignore any RelabelType node above the operands.  This is needed to
 		 * be able to apply indexscanning in binary-compatible-operator cases.
diff --git a/src/test/regress/expected/create_index.out b/src/test/regress/expected/create_index.out
index c6feef03810..cac076abb88 100644
--- a/src/test/regress/expected/create_index.out
+++ b/src/test/regress/expected/create_index.out
@@ -1913,6 +1913,27 @@ SELECT * FROM tenk1
       42 |    5530 |   0 |    2 |   2 |      2 |      42 |       42 |          42 |        42 |       42 |  84 |   85 | QBAAAA   | SEIAAA   | OOOOxx
 (1 row)
 
+EXPLAIN (COSTS OFF)
+SELECT * FROM tenk1
+  WHERE thousand = 42 AND (tenthous = 1::numeric OR tenthous = 3::int4 OR tenthous = 42::numeric);
+                                                 QUERY PLAN                                                  
+-------------------------------------------------------------------------------------------------------------
+ Bitmap Heap Scan on tenk1
+   Recheck Cond: (thousand = 42)
+   Filter: (((tenthous)::numeric = '1'::numeric) OR (tenthous = 3) OR ((tenthous)::numeric = '42'::numeric))
+   ->  Bitmap Index Scan on tenk1_thous_tenthous
+         Index Cond: (thousand = 42)
+(5 rows)
+
+EXPLAIN (COSTS OFF)
+SELECT * FROM tenk1
+  WHERE tenthous = 1::numeric OR tenthous = 3::int4 OR tenthous = 42::numeric;
+                                                 QUERY PLAN                                                  
+-------------------------------------------------------------------------------------------------------------
+ Seq Scan on tenk1
+   Filter: (((tenthous)::numeric = '1'::numeric) OR (tenthous = 3) OR ((tenthous)::numeric = '42'::numeric))
+(2 rows)
+
 EXPLAIN (COSTS OFF)
 SELECT count(*) FROM tenk1
   WHERE hundred = 42 AND (thousand = 42 OR thousand = 99);
@@ -2034,6 +2055,78 @@ SELECT count(*) FROM tenk1
     10
 (1 row)
 
+EXPLAIN (COSTS OFF)
+SELECT count(*) FROM tenk1, tenk2
+  WHERE tenk1.hundred = 42 AND (tenk2.thousand = 42 OR tenk1.thousand = 41 OR tenk2.tenthous = 2) AND
+  tenk2.hundred = tenk1.hundred;
+                                          QUERY PLAN                                           
+-----------------------------------------------------------------------------------------------
+ Aggregate
+   ->  Nested Loop
+         Join Filter: ((tenk2.thousand = 42) OR (tenk1.thousand = 41) OR (tenk2.tenthous = 2))
+         ->  Bitmap Heap Scan on tenk1
+               Recheck Cond: (hundred = 42)
+               ->  Bitmap Index Scan on tenk1_hundred
+                     Index Cond: (hundred = 42)
+         ->  Materialize
+               ->  Bitmap Heap Scan on tenk2
+                     Recheck Cond: (hundred = 42)
+                     ->  Bitmap Index Scan on tenk2_hundred
+                           Index Cond: (hundred = 42)
+(12 rows)
+
+EXPLAIN (COSTS OFF)
+SELECT count(*) FROM tenk1, tenk2
+  WHERE tenk1.hundred = 42 AND (tenk2.thousand = 42 OR tenk2.thousand = 41 OR tenk2.tenthous = 2) AND
+  tenk2.hundred = tenk1.hundred;
+                                  QUERY PLAN                                  
+------------------------------------------------------------------------------
+ Aggregate
+   ->  Nested Loop
+         ->  Bitmap Heap Scan on tenk2
+               Recheck Cond: (hundred = 42)
+               Filter: ((thousand = 42) OR (thousand = 41) OR (tenthous = 2))
+               ->  Bitmap Index Scan on tenk2_hundred
+                     Index Cond: (hundred = 42)
+         ->  Index Only Scan using tenk1_hundred on tenk1
+               Index Cond: (hundred = 42)
+(9 rows)
+
+EXPLAIN (COSTS OFF)
+SELECT count(*) FROM tenk1 JOIN tenk2 ON
+  tenk1.hundred = 42 AND (tenk2.thousand = 42 OR tenk2.thousand = 41 OR tenk2.tenthous = 2) AND
+  tenk2.hundred = tenk1.hundred;
+                                  QUERY PLAN                                  
+------------------------------------------------------------------------------
+ Aggregate
+   ->  Nested Loop
+         ->  Bitmap Heap Scan on tenk2
+               Recheck Cond: (hundred = 42)
+               Filter: ((thousand = 42) OR (thousand = 41) OR (tenthous = 2))
+               ->  Bitmap Index Scan on tenk2_hundred
+                     Index Cond: (hundred = 42)
+         ->  Index Only Scan using tenk1_hundred on tenk1
+               Index Cond: (hundred = 42)
+(9 rows)
+
+EXPLAIN (COSTS OFF)
+SELECT count(*) FROM tenk1 LEFT JOIN tenk2 ON
+  tenk1.hundred = 42 AND (tenk2.thousand = 42 OR tenk2.thousand = 41 OR tenk2.tenthous = 2) AND
+  tenk2.hundred = tenk1.hundred;
+                                     QUERY PLAN                                     
+------------------------------------------------------------------------------------
+ Aggregate
+   ->  Nested Loop Left Join
+         Join Filter: (tenk1.hundred = 42)
+         ->  Index Only Scan using tenk1_hundred on tenk1
+         ->  Memoize
+               Cache Key: tenk1.hundred
+               Cache Mode: logical
+               ->  Index Scan using tenk2_hundred on tenk2
+                     Index Cond: (hundred = tenk1.hundred)
+                     Filter: ((thousand = 42) OR (thousand = 41) OR (tenthous = 2))
+(10 rows)
+
 --
 -- Check behavior with duplicate index column contents
 --
diff --git a/src/test/regress/expected/rowsecurity.out b/src/test/regress/expected/rowsecurity.out
index 319190855bd..ef890b96cc6 100644
--- a/src/test/regress/expected/rowsecurity.out
+++ b/src/test/regress/expected/rowsecurity.out
@@ -4492,6 +4492,13 @@ SELECT * FROM rls_tbl WHERE a <<< 1000;
 ---
 (0 rows)
 
+EXPLAIN (COSTS OFF) SELECT * FROM rls_tbl WHERE a <<< 1000 or a <<< 900;
+        QUERY PLAN        
+--------------------------
+ Result
+   One-Time Filter: false
+(2 rows)
+
 DROP OPERATOR <<< (int, int);
 DROP FUNCTION op_leak(int, int);
 RESET SESSION AUTHORIZATION;
diff --git a/src/test/regress/expected/stats_ext.out b/src/test/regress/expected/stats_ext.out
index 8c4da955084..a4c7be487ef 100644
--- a/src/test/regress/expected/stats_ext.out
+++ b/src/test/regress/expected/stats_ext.out
@@ -3254,6 +3254,8 @@ CREATE OPERATOR <<< (procedure = op_leak, leftarg = int, rightarg = int,
                      restrict = scalarltsel);
 SELECT * FROM tststats.priv_test_tbl WHERE a <<< 0 AND b <<< 0; -- Permission denied
 ERROR:  permission denied for table priv_test_tbl
+SELECT * FROM tststats.priv_test_tbl WHERE a <<< 0 OR b <<< 0;
+ERROR:  permission denied for table priv_test_tbl
 DELETE FROM tststats.priv_test_tbl WHERE a <<< 0 AND b <<< 0; -- Permission denied
 ERROR:  permission denied for table priv_test_tbl
 -- Grant access via a security barrier view, but hide all data
@@ -3268,6 +3270,11 @@ SELECT * FROM tststats.priv_test_view WHERE a <<< 0 AND b <<< 0; -- Should not l
 ---+---
 (0 rows)
 
+SELECT * FROM tststats.priv_test_view WHERE a <<< 0 OR b <<< 0; -- Should not leak
+ a | b 
+---+---
+(0 rows)
+
 DELETE FROM tststats.priv_test_view WHERE a <<< 0 AND b <<< 0; -- Should not leak
 -- Grant table access, but hide all data with RLS
 RESET SESSION AUTHORIZATION;
@@ -3280,6 +3287,11 @@ SELECT * FROM tststats.priv_test_tbl WHERE a <<< 0 AND b <<< 0; -- Should not le
 ---+---
 (0 rows)
 
+SELECT * FROM tststats.priv_test_tbl WHERE a <<< 0 OR b <<< 0;
+ a | b 
+---+---
+(0 rows)
+
 DELETE FROM tststats.priv_test_tbl WHERE a <<< 0 AND b <<< 0; -- Should not leak
 -- privilege checks for pg_stats_ext and pg_stats_ext_exprs
 RESET SESSION AUTHORIZATION;
diff --git a/src/test/regress/expected/uuid.out b/src/test/regress/expected/uuid.out
index 6026e15ed31..8f4ef0d7a6a 100644
--- a/src/test/regress/expected/uuid.out
+++ b/src/test/regress/expected/uuid.out
@@ -129,6 +129,37 @@ CREATE INDEX guid1_btree ON guid1 USING BTREE (guid_field);
 CREATE INDEX guid1_hash  ON guid1 USING HASH  (guid_field);
 -- unique index test
 CREATE UNIQUE INDEX guid1_unique_BTREE ON guid1 USING BTREE (guid_field);
+EXPLAIN (COSTS OFF)
+SELECT COUNT(*) FROM guid1 WHERE guid_field <> '11111111111111111111111111111111' OR
+							guid_field <> '3f3e3c3b-3a30-3938-3736-353433a2313e';
+                                                                   QUERY PLAN                                                                   
+------------------------------------------------------------------------------------------------------------------------------------------------
+ Aggregate
+   ->  Seq Scan on guid1
+         Filter: ((guid_field <> '11111111-1111-1111-1111-111111111111'::uuid) OR (guid_field <> '3f3e3c3b-3a30-3938-3736-353433a2313e'::uuid))
+(3 rows)
+
+EXPLAIN (COSTS OFF)
+SELECT COUNT(*) FROM guid1 WHERE guid_field <= '22222222-2222-2222-2222-222222222222' OR
+									guid_field <= '11111111111111111111111111111111' OR
+									guid_field <= '3f3e3c3b-3a30-3938-3736-353433a2313e';
+                                                                                                   QUERY PLAN                                                                                                   
+----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
+ Aggregate
+   ->  Seq Scan on guid1
+         Filter: ((guid_field <= '22222222-2222-2222-2222-222222222222'::uuid) OR (guid_field <= '11111111-1111-1111-1111-111111111111'::uuid) OR (guid_field <= '3f3e3c3b-3a30-3938-3736-353433a2313e'::uuid))
+(3 rows)
+
+EXPLAIN (COSTS OFF)
+SELECT COUNT(*) FROM guid1 WHERE guid_field = '3f3e3c3b-3a30-3938-3736-353433a2313e' OR
+							guid_field = '11111111111111111111111111111111';
+                                                                  QUERY PLAN                                                                  
+----------------------------------------------------------------------------------------------------------------------------------------------
+ Aggregate
+   ->  Seq Scan on guid1
+         Filter: ((guid_field = '3f3e3c3b-3a30-3938-3736-353433a2313e'::uuid) OR (guid_field = '11111111-1111-1111-1111-111111111111'::uuid))
+(3 rows)
+
 -- should fail
 INSERT INTO guid1(guid_field) VALUES('11111111-1111-1111-1111-111111111111');
 ERROR:  duplicate key value violates unique constraint "guid1_unique_btree"
diff --git a/src/test/regress/sql/create_index.sql b/src/test/regress/sql/create_index.sql
index f74ad415fbf..7e108f9b283 100644
--- a/src/test/regress/sql/create_index.sql
+++ b/src/test/regress/sql/create_index.sql
@@ -750,6 +750,14 @@ SELECT * FROM tenk1
 SELECT * FROM tenk1
   WHERE thousand = 42 AND (tenthous = 1 OR tenthous = 3 OR tenthous = 42);
 
+EXPLAIN (COSTS OFF)
+SELECT * FROM tenk1
+  WHERE thousand = 42 AND (tenthous = 1::numeric OR tenthous = 3::int4 OR tenthous = 42::numeric);
+
+EXPLAIN (COSTS OFF)
+SELECT * FROM tenk1
+  WHERE tenthous = 1::numeric OR tenthous = 3::int4 OR tenthous = 42::numeric;
+
 EXPLAIN (COSTS OFF)
 SELECT count(*) FROM tenk1
   WHERE hundred = 42 AND (thousand = 42 OR thousand = 99);
@@ -780,6 +788,25 @@ SELECT count(*) FROM tenk1
 SELECT count(*) FROM tenk1
   WHERE hundred = 42 AND (thousand = 42 OR thousand = 41 OR thousand = 99 AND tenthous = 2);
 
+EXPLAIN (COSTS OFF)
+SELECT count(*) FROM tenk1, tenk2
+  WHERE tenk1.hundred = 42 AND (tenk2.thousand = 42 OR tenk1.thousand = 41 OR tenk2.tenthous = 2) AND
+  tenk2.hundred = tenk1.hundred;
+
+EXPLAIN (COSTS OFF)
+SELECT count(*) FROM tenk1, tenk2
+  WHERE tenk1.hundred = 42 AND (tenk2.thousand = 42 OR tenk2.thousand = 41 OR tenk2.tenthous = 2) AND
+  tenk2.hundred = tenk1.hundred;
+
+EXPLAIN (COSTS OFF)
+SELECT count(*) FROM tenk1 JOIN tenk2 ON
+  tenk1.hundred = 42 AND (tenk2.thousand = 42 OR tenk2.thousand = 41 OR tenk2.tenthous = 2) AND
+  tenk2.hundred = tenk1.hundred;
+
+EXPLAIN (COSTS OFF)
+SELECT count(*) FROM tenk1 LEFT JOIN tenk2 ON
+  tenk1.hundred = 42 AND (tenk2.thousand = 42 OR tenk2.thousand = 41 OR tenk2.tenthous = 2) AND
+  tenk2.hundred = tenk1.hundred;
 --
 -- Check behavior with duplicate index column contents
 --
diff --git a/src/test/regress/sql/rowsecurity.sql b/src/test/regress/sql/rowsecurity.sql
index 3011d71b12b..6d2414b6044 100644
--- a/src/test/regress/sql/rowsecurity.sql
+++ b/src/test/regress/sql/rowsecurity.sql
@@ -2177,6 +2177,7 @@ CREATE FUNCTION op_leak(int, int) RETURNS bool
 CREATE OPERATOR <<< (procedure = op_leak, leftarg = int, rightarg = int,
                      restrict = scalarltsel);
 SELECT * FROM rls_tbl WHERE a <<< 1000;
+EXPLAIN (COSTS OFF) SELECT * FROM rls_tbl WHERE a <<< 1000 or a <<< 900;
 DROP OPERATOR <<< (int, int);
 DROP FUNCTION op_leak(int, int);
 RESET SESSION AUTHORIZATION;
diff --git a/src/test/regress/sql/stats_ext.sql b/src/test/regress/sql/stats_ext.sql
index 0c08a6cc42e..5c786b16c6f 100644
--- a/src/test/regress/sql/stats_ext.sql
+++ b/src/test/regress/sql/stats_ext.sql
@@ -1634,6 +1634,7 @@ CREATE FUNCTION op_leak(int, int) RETURNS bool
 CREATE OPERATOR <<< (procedure = op_leak, leftarg = int, rightarg = int,
                      restrict = scalarltsel);
 SELECT * FROM tststats.priv_test_tbl WHERE a <<< 0 AND b <<< 0; -- Permission denied
+SELECT * FROM tststats.priv_test_tbl WHERE a <<< 0 OR b <<< 0;
 DELETE FROM tststats.priv_test_tbl WHERE a <<< 0 AND b <<< 0; -- Permission denied
 
 -- Grant access via a security barrier view, but hide all data
@@ -1645,6 +1646,7 @@ GRANT SELECT, DELETE ON tststats.priv_test_view TO regress_stats_user1;
 -- Should now have access via the view, but see nothing and leak nothing
 SET SESSION AUTHORIZATION regress_stats_user1;
 SELECT * FROM tststats.priv_test_view WHERE a <<< 0 AND b <<< 0; -- Should not leak
+SELECT * FROM tststats.priv_test_view WHERE a <<< 0 OR b <<< 0; -- Should not leak
 DELETE FROM tststats.priv_test_view WHERE a <<< 0 AND b <<< 0; -- Should not leak
 
 -- Grant table access, but hide all data with RLS
@@ -1655,6 +1657,7 @@ GRANT SELECT, DELETE ON tststats.priv_test_tbl TO regress_stats_user1;
 -- Should now have direct table access, but see nothing and leak nothing
 SET SESSION AUTHORIZATION regress_stats_user1;
 SELECT * FROM tststats.priv_test_tbl WHERE a <<< 0 AND b <<< 0; -- Should not leak
+SELECT * FROM tststats.priv_test_tbl WHERE a <<< 0 OR b <<< 0;
 DELETE FROM tststats.priv_test_tbl WHERE a <<< 0 AND b <<< 0; -- Should not leak
 
 -- privilege checks for pg_stats_ext and pg_stats_ext_exprs
diff --git a/src/test/regress/sql/uuid.sql b/src/test/regress/sql/uuid.sql
index c88f6d087a7..75ee966ded0 100644
--- a/src/test/regress/sql/uuid.sql
+++ b/src/test/regress/sql/uuid.sql
@@ -63,6 +63,18 @@ CREATE INDEX guid1_hash  ON guid1 USING HASH  (guid_field);
 
 -- unique index test
 CREATE UNIQUE INDEX guid1_unique_BTREE ON guid1 USING BTREE (guid_field);
+
+EXPLAIN (COSTS OFF)
+SELECT COUNT(*) FROM guid1 WHERE guid_field <> '11111111111111111111111111111111' OR
+							guid_field <> '3f3e3c3b-3a30-3938-3736-353433a2313e';
+EXPLAIN (COSTS OFF)
+SELECT COUNT(*) FROM guid1 WHERE guid_field <= '22222222-2222-2222-2222-222222222222' OR
+									guid_field <= '11111111111111111111111111111111' OR
+									guid_field <= '3f3e3c3b-3a30-3938-3736-353433a2313e';
+EXPLAIN (COSTS OFF)
+SELECT COUNT(*) FROM guid1 WHERE guid_field = '3f3e3c3b-3a30-3938-3736-353433a2313e' OR
+							guid_field = '11111111111111111111111111111111';
+
 -- should fail
 INSERT INTO guid1(guid_field) VALUES('11111111-1111-1111-1111-111111111111');

---

From: Alena Rybakina <[email-masked]>
Date: Thu, 15 Aug 2024 22:13:32 +0300

Hi!
> I also have fixed some grammar issues.

While reviewing the patch, I can't understand one part of the code where 
we check the comparability of restrictinfos.

/* RestrictInfo parameters dmust match parent */
         if (subRinfo->is_pushed_down != rinfo->is_pushed_down ||
             subRinfo->is_clone != rinfo->is_clone ||
             subRinfo->security_level != rinfo->security_level ||
             !bms_equal(subRinfo->required_relids, 
rinfo->required_relids) ||
             !bms_equal(subRinfo->incompatible_relids, 
rinfo->incompatible_relids) ||
             !bms_equal(subRinfo->outer_relids, rinfo->outer_relids))
             return NULL;

I didn't find a place in the optimizer where required_relids, 
incompatible_relids and outer_relids become different. Each 
make_restrictinfo function takes arguments from
parent data.

I disabled this check and the regression tests passed. This code is 
needed for security verification， may I clarify?

In the last patch I corrected the libraries - one of them was not in 
alphabetical order.

From 0d4e4d89f32496c692c43ec6b2d5a33b906f6697 Mon Sep 17 00:00:00 2001

index c0fcc7d78df..cbfb0fdb3c8 100644
@@ -32,8 +32,10 @@

 /* XXX see PartCollMatchesExprColl */
 
+/*
 
 SELECT * FROM tenk1
 
+EXPLAIN (COSTS OFF)
+SELECT * FROM tenk1

 
+EXPLAIN (COSTS OFF)
+SELECT * FROM tenk1
 
+EXPLAIN (COSTS OFF)
 
+explain (costs off)

From ee464c93006f1da435d9473b2ef312206e47da0e Mon Sep 17 00:00:00 2001
From: Alexander Korotkov <[email-masked]>
Date: Sun, 28 Jul 2024 16:36:34 +0300
Subject: [PATCH 2/2] Teach bitmap path generation about transforming
 OR-clauses to SAOP's

index cbfb0fdb3c8..05fac2c7ba6 100644
 
+/*

 

 
 
+EXPLAIN (COSTS OFF)
+SELECT * FROM tenk1

 
+EXPLAIN (COSTS OFF)
 
 explain (costs off)
 
 explain (costs off)
 
 explain (costs off)
 
 explain (costs off)

 

+EXPLAIN (COSTS OFF)
+SELECT * FROM tenk1
 
+EXPLAIN (COSTS OFF)

 
 
 -- unique index test

---

From: Alexander Korotkov <[email-masked]>
Date: Wed, 21 Aug 2024 03:17:40 +0300

Hi!

> needed for security verification， may I clarify?

Thank you for pointing this.  I've rechecked the life cycle of those
parameters.  make_restrictinfo() makes them initially equal (except
required_relids which might be narrower for sub-clauses).  The later
changes like adjust_appendrel_attrs_mutator() applies equally for the
both parent and children.

So, I've turned this into assert check.

> In the last patch I corrected the libraries - one of them was not in

Thank you!

Also, I convert the check you've introduced in the previous message to
op_in_opfamily(), and introduced collation check similar to
match_opclause_to_indexcol().

------
Regards,
Alexander Korotkov
Supabase

---

From: Andrei Lepikhov <[email-masked]>
Date: Wed, 21 Aug 2024 15:08:14 +0200

> match_opclause_to_indexcol().
Hi,
I passed through the patches with fresh sight. Conceptually, this 
approach looks much better than the previous series.
Just for the record: previously, we attempted to resolve two issues in 
one - improve the execution plan and save cycles during the 
optimisation. As I see it, it is almost impossible in this feature. So, 
I should come to terms with carrying long OR lists through the planning 
and the additional overhead this feature generates.
I also see that the optimiser has obtained additional planning 
strategies with these patches and hasn't lost any.

Couple of findings:

First:
/* Only operator clauses scan match */
Should it be:
/* Only operator clauses can match */
?
The second one:
When creating IndexClause, we assign the original and derived clauses to 
the new, containing transformed array. But logically, we should set the 
clause with a list of ORs as the original. Why did you do so?

-- 
regards,
Andrei Lepikhov
Postgres Professional

---

From: Alexander Korotkov <[email-masked]>
Date: Wed, 21 Aug 2024 17:52:03 +0300

> strategies with these patches and hasn't lost any.

Thank you for your feedback.

> /* Only operator clauses can match */

Corrected, thanks.

> clause with a list of ORs as the original. Why did you do so?

I actually didn't notice that.  Corrected to set the OR clause as the
original.  That change turned recheck to use original OR clauses,
probably better this way.  Also, that change spotted misuse of
RestrictInfo.clause and RestrictInfo.orclause in the second patch.
Corrected this too.

------
Regards,
Alexander Korotkov
Supabase

---

From: Andrei Lepikhov <[email-masked]>
Date: Fri, 23 Aug 2024 12:23:49 +0200

>> /* Only operator clauses can match */
I found one more: /* Only operator clauses scan match  */ - in the 
second patch.
Also I propose:
- “might match to the index as whole” -> “might match the index as a whole“
- Group similar OR-arguments intro dedicated RestrictInfos -> ‘into’
> RestrictInfo.clause and RestrictInfo.orclause in the second patch.
New findings:
=============

1)
if (list_length(clause->args) != 2)
	return NULL;
I guess, above we can 'continue' the process.

2) Calling the match_index_to_operand in three nested cycles you could 
break the search on first successful match, couldn't it? At least, the 
comment "just stop with first matching index key" say so.

3) I finally found the limit of this feature: the case of two partial 
indexes on the same column. Look at the example below:

SET enable_indexscan = 'off';
SET enable_seqscan = 'off';
DROP TABLE IF EXISTS test CASCADE;
CREATE TABLE test (x int);
INSERT INTO test (x) SELECT * FROM generate_series(1,100);
CREATE INDEX ON test (x) WHERE x < 80;
CREATE INDEX ON test (x) WHERE x > 80;
VACUUM ANALYZE test;
EXPLAIN (ANALYZE, COSTS OFF, TIMING OFF)
SELECT * FROM test WHERE x=1 OR x = 79;
EXPLAIN (ANALYZE, COSTS OFF, TIMING OFF)
SELECT * FROM test WHERE x=91 OR x = 81;
EXPLAIN (ANALYZE, COSTS OFF, TIMING OFF)
SELECT * FROM test WHERE x=1 OR x = 81 OR x = 83;

The last query doesn't group clauses into two indexes. The reason is in 
match_index_to_operand which classifies all 'x=' to one class. I'm not 
sure because of overhead, but it may be resolved by using 
predicate_implied_by to partial indexes.

-- 
regards, Andrei Lepikhov

---

From: Alexander Korotkov <[email-masked]>
Date: Fri, 23 Aug 2024 15:58:46 +0300

Hi!

> - Group similar OR-arguments intro dedicated RestrictInfos -> ‘into’

Fixed.

> > RestrictInfo.clause and RestrictInfo.orclause in the second patch.

Fixed.

> predicate_implied_by to partial indexes.

Yes, this is the conscious limitation of my patch: to consider similar
OR arguments altogether and one-by-one, not in arbitrary groups.  The
important thing here is that we still generating BitmapOR patch as we
do without the patch.  So, there is no regression.  I would leave this
as is to not make this feature too complicated. This could be improved
in future though.

------
Regards,
Alexander Korotkov
Supabase

---

From: Alena Rybakina <[email-masked]>
Date: Fri, 23 Aug 2024 17:06:04 +0300

Hi!

To be fair, I fixed this before [0] by selecting the appropriate group 
of "or" expressions to transform them to "ANY" expression and then 
checking for compatibility with the index column. maybe we should try 
this too? I can think about it.

[0] 
https://www.postgresql.org/message-id/531fc0ab-371e-4235-97e3-dd2d077b6995%40postgrespro.ru

---

From: Alexander Korotkov <[email-masked]>
Date: Fri, 23 Aug 2024 19:38:36 +0300

Hi, Alena!

> https://www.postgresql.org/message-id/531fc0ab-371e-4235-97e3-dd2d077b6995%40postgrespro.ru

I probably didn't get your message.  Which patch version you think
resolve the problem?  I see [0] doesn't contain any patch.

I think further progress in this area of grouping OR args is possible
if there is a solution, which doesn't take extraordinary computational
complexity.

------
Regards,
Alexander Korotkov
Supabase

---

From: Alena Rybakina <[email-masked]>
Date: Sat, 24 Aug 2024 16:08:51 +0300

> resolve the problem?  I see [0] doesn't contain any patch.
Sorry, I got the links mixed up. We need this link [0].
> if there is a solution, which doesn't take extraordinary computational
This approach does not require a large overhead - in fact, we separately 
did the conversion to "any" once going through the list of restrictinfo, 
we form candidates in the form of boolexpr using the "and" operator, 
which contains "any" and "or" expression, then we check with index 
columns which expression suits us.

---

From: Alexander Korotkov <[email-masked]>
Date: Sat, 24 Aug 2024 16:23:18 +0300

> Sorry, I got the links mixed up. We need this link [0].

Still confusion.
If that's another [0] from [0] in the cited message then it seems you
missed new link in your last message.

------
Regards,
Alexander Korotkov
Supabase

---

From: Alena Rybakina <[email-masked]>
Date: Sat, 24 Aug 2024 16:36:24 +0300

Sorry again.

The link to letter - - 
https://www.postgresql.org/message-id/759292d5-cb51-4b12-89fa-576c1d9b374d%40postgrespro.ru

Patch - 
https://www.postgresql.org/message-id/attachment/162897/v28-Transform-OR-clauses-to-ANY-expression.patch

---

From: Andrei Lepikhov <[email-masked]>
Date: Sun, 25 Aug 2024 16:16:07 +0200

> as is to not make this feature too complicated. This could be improved
It looks reasonable for me, thanks for the explanation.

What's more, I suspicious about the line:
*subrinfo = *rinfo;

Here, you copy everything, including cached estimations like norm_selec 
or eval_cost. I see that the match_orclause_to_indexcol creates a new 
SAOP where all caches will be cleaned, but just to be sure, maybe we 
should reset any cached estimations to default values — in that case, 
anyone who tries to build a new path based on these grouped OR clauses 
will recalculate that data.
At least, incorrect eval_cost of iclause->rinfo can slightly change the 
cost of rechecking operation, can't it?

-- 
regards, Andrei Lepikhov

---

From: jian he <[email-masked]>
Date: Mon, 26 Aug 2024 11:12:00 +0800

On Fri, Aug 23, 2024 at 8:58 PM Alexander Korotkov <[email-masked]> wrote:
based on v37.

+ {
+ /*
+ * We have only Const's.  In this case we can construct an array
+ * directly.
+ */
+ int16 typlen;
+ bool typbyval;
+ char typalign;
+ Datum   *elems;
+ int i = 0;
+ ArrayType  *arrayConst;
+
+ get_typlenbyvalalign(consttype, &typlen, &typbyval, &typalign);
+
+ elems = (Datum *) palloc(sizeof(Datum) * list_length(consts));
+ foreach(lc, consts)
+ elems[i++] = ((Const *) lfirst(lc))->constvalue;
+
+ arrayConst = construct_array(elems, i, consttype,
+ typlen, typbyval, typalign);
+ arrayNode = (Node *) makeConst(arraytype, -1, inputcollid,
+   -1, PointerGetDatum(arrayConst),
+   false, false);
+
+ pfree(elems);
+ list_free(consts);
+ }
List "consts" elements can be NULL?
I didn't find a query to trigger that.
but construct_array comments says
"elems (NULL element values are not supported)."
Do we need to check Const->constisnull for the Const node?

+ /* Construct the list of nested OR arguments */
+ for (j = group_start; j < i; j++)
+ {
+ Node   *arg = list_nth(orargs, matches[j].argindex);
+
+ rargs = lappend(rargs, arg);
+ if (IsA(arg, RestrictInfo))
+ args = lappend(args, ((RestrictInfo *) arg)->clause);
+ else
+ args = lappend(args, arg);
+ }
the ELSE branch never reached?

+ /* Construct the nested OR and wrap it with RestrictInfo */
+ *subrinfo = *rinfo;
+ subrinfo->clause = make_orclause(args);
+ subrinfo->orclause = make_orclause(rargs);
+ result = lappend(result, subrinfo);
should we use memcpy instead of " *subrinfo = *rinfo;"?

+ /* Sort clauses to make similar clauses go together */
+ pg_qsort(matches, n, sizeof(OrArgIndexMatch), or_arg_index_match_cmp);
Should we use qsort?
since comments in pg_qsort:
/*
 * Callers should use the qsort() macro defined below instead of calling
 * pg_qsort() directly.
 */

+/*

I am not 100% sure about the comments.
indexnum:  index of the matching index reside in rel->indexlist that
matches (counting from 0)
colnum: the column number of the matched index (counting from 0)

---

From: Alena Rybakina <[email-masked]>
Date: Mon, 26 Aug 2024 13:41:01 +0300

Hi!

On 26.08.2024 06:12, jian he wrote:
> On Fri, Aug 23, 2024 at 8:58 PM Alexander Korotkov<[email-masked]>  wrote:
> based on v37.
>
>
> + {
> + /*

I didn't find any problems here either, but the query plan seems strange 
to me: a form of OR expressions is added to the recheck condition. But 
we discussed this before and came to the conclusion that this is not a 
mistake.

I added the query to the create_index.sql

  EXPLAIN (COSTS OFF)
+SELECT * FROM tenk1
+  WHERE thousand = 42 AND (tenthous = 1 OR tenthous = 3 OR tenthous = 
42 or tenthous is null);
+ QUERY PLAN
+-------------------------------------------------------------------------------------------------------------------------------------------
+ Bitmap Heap Scan on tenk1
+   Recheck Cond: (((thousand = 42) AND (tenthous IS NULL)) OR 
((thousand = 42) AND ((tenthous = 1) OR (tenthous = 3) OR (tenthous = 42))))
+   Filter: ((tenthous = 1) OR (tenthous = 3) OR (tenthous = 42) OR 
(tenthous IS NULL))
+   ->  BitmapOr
+         ->  Bitmap Index Scan on tenk1_thous_tenthous
+               Index Cond: ((thousand = 42) AND (tenthous IS NULL))
+         ->  Bitmap Index Scan on tenk1_thous_tenthous
+               Index Cond: ((thousand = 42) AND (tenthous = ANY 
('{1,3,42}'::integer[])))
+(8 rows)

I noticed that the NULL element is not added to the converted array 
because it belongs to a different group.

So, I think this problem may not be affect us. Gere we should add 
Assertion that an element is not null.

> the ELSE branch never reached?
Reached - if your arg is BoolExpr type, for example if it consists "And" 
expressions.
>   * Callers should use the qsort() macro defined below instead of calling
I think yes, we should.
> colnum: the column number of the matched index (counting from 0)
To be honest, I'm not sure that I completely understand your point here.

I have found an interesting case here:

+EXPLAIN (COSTS OFF) +SELECT * FROM tenk1 + WHERE thousand = 42 AND 
(stringu1 = 'MAAAAA' OR stringu1 = 'TUAAAA'::text OR stringu1 = 
'OBAAAA'::text); + QUERY PLAN 
+------------------------------------------------------------------------------------------------------------------------------------- 
+ Bitmap Heap Scan on tenk1 + Recheck Cond: ((thousand = 42) AND 
((stringu1 = 'MAAAAA'::name) OR ((stringu1 = 'TUAAAA'::text) OR 
(stringu1 = 'OBAAAA'::text)))) + Filter: ((stringu1 = 'MAAAAA'::name) OR 
(stringu1 = 'TUAAAA'::text) OR (stringu1 = 'OBAAAA'::text)) + -> 
BitmapAnd + -> Bitmap Index Scan on tenk1_thous_tenthous + Index Cond: 
(thousand = 42) + -> BitmapOr + -> Bitmap Index Scan on stringu1_idx + 
Index Cond: (stringu1 = 'MAAAAA'::name) + -> Bitmap Index Scan on 
stringu1_idx + Index Cond: (stringu1 = ANY ('{TUAAAA,OBAAAA}'::text[] 
COLLATE "C")) +(11 rows) +

If OR constants have different types, then they belong to different 
groups, and I think that's unfair. I think that conversion to a single 
type should be used here - while I’m working on this, I’ll send the code 
in the next letter.

And I noticed that there were some tests missing on this, so I added this.

I've updated the patch file to include my and Jian's suggestions, as 
well as the diff file if there's no objection.

-- 
Regards,
Alena Rybakina
Postgres Professional:http://www.postgrespro.com
The Russian Postgres Company
diff --git a/src/backend/optimizer/path/indxpath.c b/src/backend/optimizer/path/indxpath.c
index 641b1d7bf8c..cde635d9cb6 100644
--- a/src/backend/optimizer/path/indxpath.c
+++ b/src/backend/optimizer/path/indxpath.c
@@ -1366,7 +1366,7 @@ group_similar_or_args(PlannerInfo *root, RelOptInfo *rel, RestrictInfo *rinfo)
 	}
 
 	/* Sort clauses to make similar clauses go together */
-	pg_qsort(matches, n, sizeof(OrArgIndexMatch), or_arg_index_match_cmp);
+	qsort(matches, n, sizeof(OrArgIndexMatch), or_arg_index_match_cmp);
 
 	/* Group similar clauses into */
 	group_start = 0;
@@ -3346,7 +3346,13 @@ match_orclause_to_indexcol(PlannerInfo *root,
 
 		elems = (Datum *) palloc(sizeof(Datum) * list_length(consts));
 		foreach(lc, consts)
-			elems[i++] = ((Const *) lfirst(lc))->constvalue;
+		{
+			Const *value = (Const *) lfirst(lc);
+
+			Assert(!value->constisnull && value->constvalue);
+
+			elems[i++] = value->constvalue;
+		}
 
 		arrayConst = construct_array(elems, i, consttype,
 									 typlen, typbyval, typalign);
diff --git a/src/test/regress/expected/create_index.out b/src/test/regress/expected/create_index.out
index 5ccca4d83ca..5623f4b3123 100644
--- a/src/test/regress/expected/create_index.out
+++ b/src/test/regress/expected/create_index.out
@@ -1875,6 +1875,67 @@ SELECT * FROM tenk1
       42 |    5530 |   0 |    2 |   2 |      2 |      42 |       42 |          42 |        42 |       42 |  84 |   85 | QBAAAA   | SEIAAA   | OOOOxx
 (1 row)
 
+EXPLAIN (COSTS OFF)
+SELECT * FROM tenk1
+  WHERE thousand = 42 AND (tenthous = 1 OR tenthous = 3 OR tenthous = 42 or tenthous is null);
+                                                                QUERY PLAN                                                                 
+-------------------------------------------------------------------------------------------------------------------------------------------
+ Bitmap Heap Scan on tenk1
+   Recheck Cond: (((thousand = 42) AND (tenthous IS NULL)) OR ((thousand = 42) AND ((tenthous = 1) OR (tenthous = 3) OR (tenthous = 42))))
+   Filter: ((tenthous = 1) OR (tenthous = 3) OR (tenthous = 42) OR (tenthous IS NULL))
+   ->  BitmapOr
+         ->  Bitmap Index Scan on tenk1_thous_tenthous
+               Index Cond: ((thousand = 42) AND (tenthous IS NULL))
+         ->  Bitmap Index Scan on tenk1_thous_tenthous
+               Index Cond: ((thousand = 42) AND (tenthous = ANY ('{1,3,42}'::integer[])))
+(8 rows)
+
+create index stringu1_idx on tenk1 (stringu1);
+EXPLAIN (COSTS OFF)
+SELECT * FROM tenk1
+  WHERE thousand = 42 AND (stringu1::text = 'MAAAAA' OR stringu1::text = 'TUAAAA'::name OR stringu1 = 'OBAAAA'::name);
+                                                      QUERY PLAN                                                       
+-----------------------------------------------------------------------------------------------------------------------
+ Bitmap Heap Scan on tenk1
+   Recheck Cond: (thousand = 42)
+   Filter: (((stringu1)::text = 'MAAAAA'::text) OR ((stringu1)::text = 'TUAAAA'::name) OR (stringu1 = 'OBAAAA'::name))
+   ->  Bitmap Index Scan on tenk1_thous_tenthous
+         Index Cond: (thousand = 42)
+(5 rows)
+
+EXPLAIN (COSTS OFF)
+SELECT * FROM tenk1
+  WHERE thousand = 42 AND (stringu1 = 'MAAAAA' OR stringu1 = 'TUAAAA' OR stringu1 = 'OBAAAA');
+                                                            QUERY PLAN                                                             
+-----------------------------------------------------------------------------------------------------------------------------------
+ Bitmap Heap Scan on tenk1
+   Recheck Cond: ((thousand = 42) AND ((stringu1 = 'MAAAAA'::name) OR (stringu1 = 'TUAAAA'::name) OR (stringu1 = 'OBAAAA'::name)))
+   ->  BitmapAnd
+         ->  Bitmap Index Scan on tenk1_thous_tenthous
+               Index Cond: (thousand = 42)
+         ->  Bitmap Index Scan on stringu1_idx
+               Index Cond: (stringu1 = ANY ('{MAAAAA,TUAAAA,OBAAAA}'::name[]))
+(7 rows)
+
+EXPLAIN (COSTS OFF)
+SELECT * FROM tenk1
+  WHERE thousand = 42 AND (stringu1 = 'MAAAAA' OR stringu1 = 'TUAAAA'::text OR stringu1 = 'OBAAAA'::text);
+                                                             QUERY PLAN                                                              
+-------------------------------------------------------------------------------------------------------------------------------------
+ Bitmap Heap Scan on tenk1
+   Recheck Cond: ((thousand = 42) AND ((stringu1 = 'MAAAAA'::name) OR ((stringu1 = 'TUAAAA'::text) OR (stringu1 = 'OBAAAA'::text))))
+   Filter: ((stringu1 = 'MAAAAA'::name) OR (stringu1 = 'TUAAAA'::text) OR (stringu1 = 'OBAAAA'::text))
+   ->  BitmapAnd
+         ->  Bitmap Index Scan on tenk1_thous_tenthous
+               Index Cond: (thousand = 42)
+         ->  BitmapOr
+               ->  Bitmap Index Scan on stringu1_idx
+                     Index Cond: (stringu1 = 'MAAAAA'::name)
+               ->  Bitmap Index Scan on stringu1_idx
+                     Index Cond: (stringu1 = ANY ('{TUAAAA,OBAAAA}'::text[] COLLATE "C"))
+(11 rows)
+
+Drop index stringu1_idx;
 EXPLAIN (COSTS OFF)
 SELECT count(*) FROM tenk1
   WHERE hundred = 42 AND (thousand = 42 OR thousand = 99);
diff --git a/src/test/regress/sql/create_index.sql b/src/test/regress/sql/create_index.sql
index 7e108f9b283..37538ab6bba 100644
--- a/src/test/regress/sql/create_index.sql
+++ b/src/test/regress/sql/create_index.sql
@@ -738,6 +738,23 @@ SELECT * FROM tenk1
 SELECT * FROM tenk1
   WHERE thousand = 42 AND (tenthous = 1 OR tenthous = (SELECT 1 + 2) OR tenthous = 42);
 
+EXPLAIN (COSTS OFF)
+SELECT * FROM tenk1
+  WHERE thousand = 42 AND (tenthous = 1 OR tenthous = 3 OR tenthous = 42 or tenthous is null);
+
+create index stringu1_idx on tenk1 (stringu1);
+EXPLAIN (COSTS OFF)
+SELECT * FROM tenk1
+  WHERE thousand = 42 AND (stringu1::text = 'MAAAAA' OR stringu1::text = 'TUAAAA'::name OR stringu1 = 'OBAAAA'::name);
+
+EXPLAIN (COSTS OFF)
+SELECT * FROM tenk1
+  WHERE thousand = 42 AND (stringu1 = 'MAAAAA' OR stringu1 = 'TUAAAA' OR stringu1 = 'OBAAAA');
+EXPLAIN (COSTS OFF)
+SELECT * FROM tenk1
+  WHERE thousand = 42 AND (stringu1 = 'MAAAAA' OR stringu1 = 'TUAAAA'::text OR stringu1 = 'OBAAAA'::text);
+Drop index stringu1_idx;
+
 EXPLAIN (COSTS OFF)
 SELECT count(*) FROM tenk1
   WHERE hundred = 42 AND (thousand = 42 OR thousand = 99);
From 25c59961afd18bcfd6d5e3107d859af491d6b99d Mon Sep 17 00:00:00 2001
From: Alexander Korotkov <[email-masked]>
Date: Mon, 5 Aug 2024 21:27:02 +0300
Subject: [PATCH 1/2] Transform OR-clauses to SAOP's during index matching

Discussion: https://postgr.es/m/567ED6CA.2040504%40sigaev.ru
Author: Alena Rybakina <[email-masked]>
Author: Andrey Lepikhov <[email-masked]>
Reviewed-by: Peter Geoghegan <[email-masked]>
Reviewed-by: Ranier Vilela <[email-masked]>
Reviewed-by: Alexander Korotkov <[email-masked]>
Reviewed-by: Robert Haas <[email-masked]>
Reviewed-by: Jian He <[email-masked]>
Reviewed-by: Tom Lane <[email-masked]>
Reviewed-by: Nikolay Shaplov <[email-masked]>
---
 src/backend/optimizer/path/indxpath.c      | 266 ++++++++++++++++++++
 src/test/regress/expected/create_index.out | 270 +++++++++++++++++++--
 src/test/regress/expected/join.out         |  57 ++++-
 src/test/regress/expected/rowsecurity.out  |   7 +
 src/test/regress/expected/stats_ext.out    |  12 +
 src/test/regress/expected/uuid.out         |  31 +++
 src/test/regress/sql/create_index.sql      |  69 ++++++
 src/test/regress/sql/join.sql              |   9 +
 src/test/regress/sql/rowsecurity.sql       |   1 +
 src/test/regress/sql/stats_ext.sql         |   3 +
 src/test/regress/sql/uuid.sql              |  12 +
 11 files changed, 718 insertions(+), 19 deletions(-)

index c0fcc7d78df..fb3acea7441 100644
@@ -32,8 +33,10 @@

 /* XXX see PartCollMatchesExprColl */
@@ -177,6 +180,10 @@ static IndexClause *match_rowcompare_to_indexcol(PlannerInfo *root,
 												 RestrictInfo *rinfo,
 												 int indexcol,
 												 IndexOptInfo *index);
+static IndexClause *match_orclause_to_indexcol(PlannerInfo *root,
+											   RestrictInfo *rinfo,
+											   int indexcol,
+											   IndexOptInfo *index);
 static IndexClause *expand_indexqual_rowcompare(PlannerInfo *root,
 												RestrictInfo *rinfo,
 												int indexcol,
@@ -2248,6 +2255,10 @@ match_clause_to_indexcol(PlannerInfo *root,
 	{
 		return match_rowcompare_to_indexcol(root, rinfo, indexcol, index);
 	}
+	else if (restriction_is_or_clause(rinfo))
+	{
+		return match_orclause_to_indexcol(root, rinfo, indexcol, index);
+	}
 	else if (index->amsearchnulls && IsA(clause, NullTest))
 	{
 		NullTest   *nt = (NullTest *) clause;
@@ -2771,6 +2782,261 @@ match_rowcompare_to_indexcol(PlannerInfo *root,
 	return NULL;
 }
 
+/*
+		/* Only operator clauses can match  */
+		 * The parameters below must match between sub-rinfo and its parent as
+		 * make_restrictinfo() fills them with the same values, and further
+		 * modifications are also the same for the whole subtree. However,
+		 * still make a sanity check.
+		Assert(subRinfo->is_pushed_down == rinfo->is_pushed_down);
+		Assert(subRinfo->is_clone == rinfo->is_clone);
+		Assert(subRinfo->security_level == rinfo->security_level);
+		Assert(bms_equal(subRinfo->incompatible_relids, rinfo->incompatible_relids));
+		Assert(bms_equal(subRinfo->outer_relids, rinfo->outer_relids));
+		 * Also, check that required_relids in sub-rinfo is subset of parent's
+		 * required_relids.
+		Assert(bms_is_subset(subRinfo->required_relids, rinfo->required_relids));
+			 * Check operator is present in the opfamily, expression collation
+			 * matches index collation.  Also, there must be an array type in
+			 * order to construct an array later.
+			if (!IndexCollMatchesExprColl(index->indexcollations[indexcol], inputcollid) ||
+				!op_in_opfamily(matchOpno, index->opfamily[indexcol]) ||
+				!OidIsValid(arraytype))
+	iclause->rinfo = rinfo;
+	iclause->indexquals = list_make1(make_restrictinfo(root,
+													   rinfo->outer_relids));
index cf6eac57349..1324d6927c4 100644
@@ -1844,18 +1844,67 @@ DROP TABLE onek_with_null;
+---------------------------------------------------------------------------------
+         Recheck Cond: ((hundred = 42) AND ((thousand = 42) OR (thousand = 99)))
 
 SELECT * FROM tenk1
   WHERE thousand = 42 AND (tenthous = 1 OR tenthous = 3 OR tenthous = 42);
@@ -1864,6 +1913,27 @@ SELECT * FROM tenk1
       42 |    5530 |   0 |    2 |   2 |      2 |      42 |       42 |          42 |        42 |       42 |  84 |   85 | QBAAAA   | SEIAAA   | OOOOxx
 (1 row)
 
+EXPLAIN (COSTS OFF)
+SELECT * FROM tenk1
@@ -1872,6 +1942,102 @@ SELECT count(*) FROM tenk1
          Recheck Cond: ((hundred = 42) AND ((thousand = 42) OR (thousand = 99)))
+-----------------------------------------------------------------------------------------------------------------------
+         Recheck Cond: ((hundred = 42) AND ((thousand < 42) OR (thousand < 99) OR (43 > thousand) OR (42 > thousand)))
+-----------------------------------------------------------------------------------------------------
+         Recheck Cond: (((thousand = 42) AND ((tenthous = 1) OR (tenthous = 3))) OR (thousand = 41))
@@ -1879,16 +2045,90 @@ SELECT count(*) FROM tenk1

+EXPLAIN (COSTS OFF)
index 31fb7d142eb..e76dca7319f 100644
+               Recheck Cond: ((unique1 = 1) OR ((unique2 = 3) OR (unique2 = 7)))
+               Recheck Cond: ((unique1 = 1) OR ((unique2 = 3) OR (unique2 = 7)))
+               Recheck Cond: ((unique1 < 20) OR (unique1 = 3) OR (unique1 = 1) OR ((unique2 = 3) OR (unique2 = 7)))

 
 
index e296891cab8..7e108f9b283 100644
@@ -732,12 +732,81 @@ SELECT * FROM tenk1
 
+EXPLAIN (COSTS OFF)
+SELECT * FROM tenk1
 
+EXPLAIN (COSTS OFF)
+SELECT * FROM tenk1
 
+explain (costs off)

 
 
 -- unique index test
 
-- 
2.34.1

From aa9707a8a2fd7f0444b95b2ca4e15ba63ab20e82 Mon Sep 17 00:00:00 2001
From: Alexander Korotkov <[email-masked]>
Date: Sun, 28 Jul 2024 16:36:34 +0300
Subject: [PATCH 2/2] Teach bitmap path generation about transforming
 OR-clauses to SAOP's

Discussion: https://postgr.es/m/567ED6CA.2040504%40sigaev.ru
Reviewed-by: Alexander Korotkov <[email-masked]>
---
 src/backend/optimizer/path/indxpath.c      | 375 ++++++++++++++++++++-
 src/test/regress/expected/create_index.out |  89 ++++-
 src/test/regress/expected/join.out         |  56 ++-
 src/test/regress/sql/create_index.sql      |  17 +
 src/tools/pgindent/typedefs.list           |   1 +
 5 files changed, 491 insertions(+), 47 deletions(-)

diff --git a/src/backend/optimizer/path/indxpath.c b/src/backend/optimizer/path/indxpath.c
index fb3acea7441..cde635d9cb6 100644
--- a/src/backend/optimizer/path/indxpath.c
+++ b/src/backend/optimizer/path/indxpath.c
@@ -1173,6 +1173,337 @@ build_paths_for_OR(PlannerInfo *root, RelOptInfo *rel,
 	return result;
 }
 
+/*
+ *		Group similar OR-arguments into dedicated RestrictInfos.  Process
+		/* Only operator clauses can match  */
+				if (matches[i].indexnum >= 0)
+	qsort(matches, n, sizeof(OrArgIndexMatch), or_arg_index_match_cmp);
+				List	   *rargs = NIL;
+	List	   *args = ((BoolExpr *) ri->orclause)->args;
@@ -1203,6 +1534,7 @@ generate_bitmap_or_paths(PlannerInfo *root, RelOptInfo *rel,
 		List	   *pathlist;
 		Path	   *bitmapqual;
 		ListCell   *j;
+		List	   *groupedArgs;
 
@@ -1213,7 +1545,13 @@ generate_bitmap_or_paths(PlannerInfo *root, RelOptInfo *rel,
+		 * because those RestrictInfos might match to the index as a whole.
@@ -1233,12 +1571,37 @@ generate_bitmap_or_paths(PlannerInfo *root, RelOptInfo *rel,

 				indlist = build_paths_for_OR(root, rel,
@@ -2983,7 +3346,13 @@ match_orclause_to_indexcol(PlannerInfo *root,
 
 		elems = (Datum *) palloc(sizeof(Datum) * list_length(consts));
 		foreach(lc, consts)
-			elems[i++] = ((Const *) lfirst(lc))->constvalue;
+		{
+			Const *value = (Const *) lfirst(lc);
+
+			Assert(!value->constisnull && value->constvalue);
+
+			elems[i++] = value->constvalue;
+		}
 
 		arrayConst = construct_array(elems, i, consttype,
 									 typlen, typbyval, typalign);
diff --git a/src/test/regress/expected/create_index.out b/src/test/regress/expected/create_index.out
index 1324d6927c4..5623f4b3123 100644
--- a/src/test/regress/expected/create_index.out
+++ b/src/test/regress/expected/create_index.out
@@ -1875,6 +1875,67 @@ SELECT * FROM tenk1
       42 |    5530 |   0 |    2 |   2 |      2 |      42 |       42 |          42 |        42 |       42 |  84 |   85 | QBAAAA   | SEIAAA   | OOOOxx
 (1 row)
 
+EXPLAIN (COSTS OFF)
+SELECT * FROM tenk1
+  WHERE thousand = 42 AND (tenthous = 1 OR tenthous = 3 OR tenthous = 42 or tenthous is null);
+                                                                QUERY PLAN                                                                 
+-------------------------------------------------------------------------------------------------------------------------------------------
+ Bitmap Heap Scan on tenk1
+   Recheck Cond: (((thousand = 42) AND (tenthous IS NULL)) OR ((thousand = 42) AND ((tenthous = 1) OR (tenthous = 3) OR (tenthous = 42))))
+   Filter: ((tenthous = 1) OR (tenthous = 3) OR (tenthous = 42) OR (tenthous IS NULL))
+   ->  BitmapOr
+         ->  Bitmap Index Scan on tenk1_thous_tenthous
+               Index Cond: ((thousand = 42) AND (tenthous IS NULL))
+         ->  Bitmap Index Scan on tenk1_thous_tenthous
+               Index Cond: ((thousand = 42) AND (tenthous = ANY ('{1,3,42}'::integer[])))
+(8 rows)
+
+create index stringu1_idx on tenk1 (stringu1);
+EXPLAIN (COSTS OFF)
+SELECT * FROM tenk1
+  WHERE thousand = 42 AND (stringu1::text = 'MAAAAA' OR stringu1::text = 'TUAAAA'::name OR stringu1 = 'OBAAAA'::name);
+                                                      QUERY PLAN                                                       
+-----------------------------------------------------------------------------------------------------------------------
+ Bitmap Heap Scan on tenk1
+   Recheck Cond: (thousand = 42)
+   Filter: (((stringu1)::text = 'MAAAAA'::text) OR ((stringu1)::text = 'TUAAAA'::name) OR (stringu1 = 'OBAAAA'::name))
+   ->  Bitmap Index Scan on tenk1_thous_tenthous
+         Index Cond: (thousand = 42)
+(5 rows)
+
+EXPLAIN (COSTS OFF)
+SELECT * FROM tenk1
+  WHERE thousand = 42 AND (stringu1 = 'MAAAAA' OR stringu1 = 'TUAAAA' OR stringu1 = 'OBAAAA');
+                                                            QUERY PLAN                                                             
+-----------------------------------------------------------------------------------------------------------------------------------
+ Bitmap Heap Scan on tenk1
+   Recheck Cond: ((thousand = 42) AND ((stringu1 = 'MAAAAA'::name) OR (stringu1 = 'TUAAAA'::name) OR (stringu1 = 'OBAAAA'::name)))
+   ->  BitmapAnd
+         ->  Bitmap Index Scan on tenk1_thous_tenthous
+               Index Cond: (thousand = 42)
+         ->  Bitmap Index Scan on stringu1_idx
+               Index Cond: (stringu1 = ANY ('{MAAAAA,TUAAAA,OBAAAA}'::name[]))
+(7 rows)
+
+EXPLAIN (COSTS OFF)
+SELECT * FROM tenk1
+  WHERE thousand = 42 AND (stringu1 = 'MAAAAA' OR stringu1 = 'TUAAAA'::text OR stringu1 = 'OBAAAA'::text);
+                                                             QUERY PLAN                                                              
+-------------------------------------------------------------------------------------------------------------------------------------
+ Bitmap Heap Scan on tenk1
+   Recheck Cond: ((thousand = 42) AND ((stringu1 = 'MAAAAA'::name) OR ((stringu1 = 'TUAAAA'::text) OR (stringu1 = 'OBAAAA'::text))))
+   Filter: ((stringu1 = 'MAAAAA'::name) OR (stringu1 = 'TUAAAA'::text) OR (stringu1 = 'OBAAAA'::text))
+   ->  BitmapAnd
+         ->  Bitmap Index Scan on tenk1_thous_tenthous
+               Index Cond: (thousand = 42)
+         ->  BitmapOr
+               ->  Bitmap Index Scan on stringu1_idx
+                     Index Cond: (stringu1 = 'MAAAAA'::name)
+               ->  Bitmap Index Scan on stringu1_idx
+                     Index Cond: (stringu1 = ANY ('{TUAAAA,OBAAAA}'::text[] COLLATE "C"))
+(11 rows)
+
+Drop index stringu1_idx;
 EXPLAIN (COSTS OFF)
 SELECT count(*) FROM tenk1
   WHERE hundred = 42 AND (thousand = 42 OR thousand = 99);
@@ -2003,25 +2064,24 @@ SELECT count(*) FROM tenk1
 EXPLAIN (COSTS OFF)
 SELECT count(*) FROM tenk1
   WHERE hundred = 42 AND (thousand = 42 OR thousand = 99 OR tenthous < 2) OR thousand = 41;
-                                                       QUERY PLAN                                                       
-------------------------------------------------------------------------------------------------------------------------
+                                                        QUERY PLAN                                                        
+--------------------------------------------------------------------------------------------------------------------------
  Aggregate
    ->  Bitmap Heap Scan on tenk1
-         Recheck Cond: (((hundred = 42) AND ((thousand = 42) OR (thousand = 99) OR (tenthous < 2))) OR (thousand = 41))
+         Recheck Cond: (((hundred = 42) AND (((thousand = 42) OR (thousand = 99)) OR (tenthous < 2))) OR (thousand = 41))
+         Filter: (((hundred = 42) AND ((thousand = 42) OR (thousand = 99) OR (tenthous < 2))) OR (thousand = 41))
          ->  BitmapOr
                ->  BitmapAnd
                      ->  Bitmap Index Scan on tenk1_hundred
                            Index Cond: (hundred = 42)
                      ->  BitmapOr
                            ->  Bitmap Index Scan on tenk1_thous_tenthous
-                                 Index Cond: (thousand = 42)
-                           ->  Bitmap Index Scan on tenk1_thous_tenthous
-                                 Index Cond: (thousand = 99)
+                                 Index Cond: (thousand = ANY ('{42,99}'::integer[]))
                            ->  Bitmap Index Scan on tenk1_thous_tenthous
                                  Index Cond: (tenthous < 2)
                ->  Bitmap Index Scan on tenk1_thous_tenthous
                      Index Cond: (thousand = 41)
-(16 rows)
+(15 rows)
 
@@ -2033,22 +2093,21 @@ SELECT count(*) FROM tenk1
+---------------------------------------------------------------------------------------------------------------------------
+         Recheck Cond: ((hundred = 42) AND (((thousand = 99) AND (tenthous = 2)) OR ((thousand = 42) OR (thousand = 41))))
 
index e76dca7319f..58dabfa7519 100644
 
 explain (costs off)
 
 explain (costs off)
-               Recheck Cond: ((unique1 = 1) OR ((unique2 = 3) OR (unique2 = 7)))
+               Recheck Cond: (((unique2 = 3) OR (unique2 = 7)) OR (unique1 = 1))
 
 explain (costs off)
-               Recheck Cond: ((unique1 = 1) OR ((unique2 = 3) OR (unique2 = 7)))
+               Recheck Cond: (((unique2 = 3) OR (unique2 = 7)) OR (unique1 = 1))
 
 explain (costs off)
-               Recheck Cond: ((unique1 < 20) OR (unique1 = 3) OR (unique1 = 1) OR ((unique2 = 3) OR (unique2 = 7)))
+               Recheck Cond: (((unique2 = 3) OR (unique2 = 7)) OR ((unique1 = 3) OR (unique1 = 1)) OR (unique1 < 20))
 
 --
 -- test placement of movable quals in a parameterized join tree
diff --git a/src/test/regress/sql/create_index.sql b/src/test/regress/sql/create_index.sql
index 7e108f9b283..37538ab6bba 100644
--- a/src/test/regress/sql/create_index.sql
+++ b/src/test/regress/sql/create_index.sql
@@ -738,6 +738,23 @@ SELECT * FROM tenk1
 SELECT * FROM tenk1
   WHERE thousand = 42 AND (tenthous = 1 OR tenthous = (SELECT 1 + 2) OR tenthous = 42);
 
+EXPLAIN (COSTS OFF)
+SELECT * FROM tenk1
+  WHERE thousand = 42 AND (tenthous = 1 OR tenthous = 3 OR tenthous = 42 or tenthous is null);
+
+create index stringu1_idx on tenk1 (stringu1);
+EXPLAIN (COSTS OFF)
+SELECT * FROM tenk1
+  WHERE thousand = 42 AND (stringu1::text = 'MAAAAA' OR stringu1::text = 'TUAAAA'::name OR stringu1 = 'OBAAAA'::name);
+
+EXPLAIN (COSTS OFF)
+SELECT * FROM tenk1
+  WHERE thousand = 42 AND (stringu1 = 'MAAAAA' OR stringu1 = 'TUAAAA' OR stringu1 = 'OBAAAA');
+EXPLAIN (COSTS OFF)
+SELECT * FROM tenk1
+  WHERE thousand = 42 AND (stringu1 = 'MAAAAA' OR stringu1 = 'TUAAAA'::text OR stringu1 = 'OBAAAA'::text);
+Drop index stringu1_idx;
+
 EXPLAIN (COSTS OFF)
 SELECT count(*) FROM tenk1
   WHERE hundred = 42 AND (thousand = 42 OR thousand = 99);
diff --git a/src/tools/pgindent/typedefs.list b/src/tools/pgindent/typedefs.list
index 3f3a8f2634b..3d1db60dd03 100644
--- a/src/tools/pgindent/typedefs.list
+++ b/src/tools/pgindent/typedefs.list
@@ -1764,6 +1764,7 @@ OprCacheKey
 OprInfo
 OprProofCacheEntry
 OprProofCacheKey
+OrArgIndexMatch
 OuterJoinClauseInfo
 OutputPluginCallbacks
 OutputPluginOptions
-- 
2.34.1

---

From: jian he <[email-masked]>
Date: Tue, 27 Aug 2024 14:53:00 +0800

On Mon, Aug 26, 2024 at 6:41 PM Alena Rybakina
<[email-masked]> wrote:
> Reached - if your arg is BoolExpr type, for example if it consists "And" expressions.
>
I added elog(INFO, "this part called");
all the tests still passed, that's where my confusion comes from.

> To be honest, I'm not sure that I completely understand your point here.
I guess I want to make the comments more explicit, straightforward.

does match_orclause_to_indexcol have a memory issue.
current match_orclause_to_indexcol pattern is
<<<<<<<<<<<<<<<<<<
foreach(lc, orclause->args)
{
    condition check, if fail, return null.
   consts = lappend(consts, constExpr);
}
if (have_param)
{
ArrayExpr  *arrayExpr = makeNode(ArrayExpr);
arrayExpr->elements = consts;
}
else
{
do other work.
list_free(consts);
}
<<<<<<<<<<<<<<<<<<
if have_param is false, first foreach fail at the last iteration
then
"list_free(consts);" will not get called?
Will it be a problem?

---

From: Andrei Lepikhov <[email-masked]>
Date: Tue, 3 Sep 2024 11:52:55 +0200

>> colnum: the column number of the matched index (counting from 0)
Hmm, it is not easy to invent an alternative variant. What are you 
proposing exactly?

> type should be used here - while I’m working on this, I’ll send the code 
IMO, that means additional overhead, isn't it? It is an improvement and 
I suggest to discuss it in a separate thread if current feature will be 
applied.
> well as the diff file if there's no objection.
I doubt if you really need additional index on the tenk1 table. What is 
the case you can't reproduce with current indexes, playing, let's say, 
with casting to numeric and integer data types?
See in attachment minor fixes to the v38 version of the patch set.

-- 
regards, Andrei Lepikhov
diff --git a/src/backend/optimizer/path/indxpath.c b/src/backend/optimizer/path/indxpath.c
index cde635d9cb..d54462f0fc 100644
--- a/src/backend/optimizer/path/indxpath.c
+++ b/src/backend/optimizer/path/indxpath.c
@@ -3345,10 +3345,8 @@ match_orclause_to_indexcol(PlannerInfo *root,
 		get_typlenbyvalalign(consttype, &typlen, &typbyval, &typalign);
 
 		elems = (Datum *) palloc(sizeof(Datum) * list_length(consts));
-		foreach(lc, consts)
+		foreach_node(Const, value, consts)
 		{
-			Const *value = (Const *) lfirst(lc);
-
 			Assert(!value->constisnull && value->constvalue);
 
 			elems[i++] = value->constvalue;
diff --git a/src/test/regress/expected/create_index.out b/src/test/regress/expected/create_index.out
index 5623f4b312..afae2cc272 100644
--- a/src/test/regress/expected/create_index.out
+++ b/src/test/regress/expected/create_index.out
@@ -1877,7 +1877,7 @@ SELECT * FROM tenk1
 
 EXPLAIN (COSTS OFF)
 SELECT * FROM tenk1
-  WHERE thousand = 42 AND (tenthous = 1 OR tenthous = 3 OR tenthous = 42 or tenthous is null);
+  WHERE thousand = 42 AND (tenthous = 1 OR tenthous = 3 OR tenthous = 42 OR tenthous IS NULL);
                                                                 QUERY PLAN                                                                 
 -------------------------------------------------------------------------------------------------------------------------------------------
  Bitmap Heap Scan on tenk1
@@ -1890,7 +1890,7 @@ SELECT * FROM tenk1
                Index Cond: ((thousand = 42) AND (tenthous = ANY ('{1,3,42}'::integer[])))
 (8 rows)
 
-create index stringu1_idx on tenk1 (stringu1);
+CREATE INDEX stringu1_idx ON tenk1 (stringu1);
 EXPLAIN (COSTS OFF)
 SELECT * FROM tenk1
   WHERE thousand = 42 AND (stringu1::text = 'MAAAAA' OR stringu1::text = 'TUAAAA'::name OR stringu1 = 'OBAAAA'::name);
@@ -1935,7 +1935,7 @@ SELECT * FROM tenk1
                      Index Cond: (stringu1 = ANY ('{TUAAAA,OBAAAA}'::text[] COLLATE "C"))
 (11 rows)
 
-Drop index stringu1_idx;
+DROP INDEX stringu1_idx;
 EXPLAIN (COSTS OFF)
 SELECT count(*) FROM tenk1
   WHERE hundred = 42 AND (thousand = 42 OR thousand = 99);
diff --git a/src/test/regress/sql/create_index.sql b/src/test/regress/sql/create_index.sql
index 37538ab6bb..50f76823d9 100644
--- a/src/test/regress/sql/create_index.sql
+++ b/src/test/regress/sql/create_index.sql
@@ -740,9 +740,9 @@ SELECT * FROM tenk1
 
 EXPLAIN (COSTS OFF)
 SELECT * FROM tenk1
-  WHERE thousand = 42 AND (tenthous = 1 OR tenthous = 3 OR tenthous = 42 or tenthous is null);
+  WHERE thousand = 42 AND (tenthous = 1 OR tenthous = 3 OR tenthous = 42 OR tenthous IS NULL);
 
-create index stringu1_idx on tenk1 (stringu1);
+CREATE INDEX stringu1_idx ON tenk1 (stringu1);
 EXPLAIN (COSTS OFF)
 SELECT * FROM tenk1
   WHERE thousand = 42 AND (stringu1::text = 'MAAAAA' OR stringu1::text = 'TUAAAA'::name OR stringu1 = 'OBAAAA'::name);
@@ -753,7 +753,7 @@ SELECT * FROM tenk1
 EXPLAIN (COSTS OFF)
 SELECT * FROM tenk1
   WHERE thousand = 42 AND (stringu1 = 'MAAAAA' OR stringu1 = 'TUAAAA'::text OR stringu1 = 'OBAAAA'::text);
-Drop index stringu1_idx;
+DROP INDEX stringu1_idx;
 
 EXPLAIN (COSTS OFF)

---

From: Alena Rybakina <[email-masked]>
Date: Wed, 4 Sep 2024 18:31:36 +0300

Hi!

On 03.09.2024 12:52, Andrei Lepikhov wrote:
>> groups, and I think that's unfair. I think that conversion to a 
>> single type should be used here - while I’m working on this, I’ll 
>> send the code in the next letter.
> IMO, that means additional overhead, isn't it? It is an improvement 
> and I suggest to discuss it in a separate thread if current feature 
> will be applied.
I think we will have a slight overhead, so in essence it will go 
additionally through the transformed groups, and not through the entire 
list of Or expressions. I agree with your suggestion to discuss it in 
separate thread.
> I doubt if you really need additional index on the tenk1 table. What 
> is the case you can't reproduce with current indexes, playing, let's 
> say, with casting to numeric and integer data types?
I rewrote the tests with integer types. Thanks for your suggestion. If 
you don't mind, I've updated the diff file you attached earlier to 
include the tests.
diff --git a/src/backend/optimizer/path/indxpath.c b/src/backend/optimizer/path/indxpath.c
index cde635d9cb6..d54462f0fce 100644
--- a/src/backend/optimizer/path/indxpath.c
+++ b/src/backend/optimizer/path/indxpath.c
@@ -3345,10 +3345,8 @@ match_orclause_to_indexcol(PlannerInfo *root,
 		get_typlenbyvalalign(consttype, &typlen, &typbyval, &typalign);

 			elems[i++] = value->constvalue;
diff --git a/src/test/regress/expected/create_index.out b/src/test/regress/expected/create_index.out
index 5623f4b3123..103e135de9f 100644
--- a/src/test/regress/expected/create_index.out
+++ b/src/test/regress/expected/create_index.out
@@ -1890,52 +1890,45 @@ SELECT * FROM tenk1
                Index Cond: ((thousand = 42) AND (tenthous = ANY ('{1,3,42}'::integer[])))
 (8 rows)
 
-create index stringu1_idx on tenk1 (stringu1);
 EXPLAIN (COSTS OFF)
 SELECT * FROM tenk1
-  WHERE thousand = 42 AND (stringu1::text = 'MAAAAA' OR stringu1::text = 'TUAAAA'::name OR stringu1 = 'OBAAAA'::name);
-                                                      QUERY PLAN                                                       
------------------------------------------------------------------------------------------------------------------------
+  WHERE thousand = 42 AND (tenthous = 1::int2 OR tenthous::int2 = 3::int8 OR tenthous = 42::int8);
+                                                 QUERY PLAN                                                  
+-------------------------------------------------------------------------------------------------------------
  Bitmap Heap Scan on tenk1
    Recheck Cond: (thousand = 42)
-   Filter: (((stringu1)::text = 'MAAAAA'::text) OR ((stringu1)::text = 'TUAAAA'::name) OR (stringu1 = 'OBAAAA'::name))
+   Filter: ((tenthous = '1'::smallint) OR ((tenthous)::smallint = '3'::bigint) OR (tenthous = '42'::bigint))
    ->  Bitmap Index Scan on tenk1_thous_tenthous
          Index Cond: (thousand = 42)
 (5 rows)
 
 EXPLAIN (COSTS OFF)
 SELECT * FROM tenk1
-  WHERE thousand = 42 AND (stringu1 = 'MAAAAA' OR stringu1 = 'TUAAAA' OR stringu1 = 'OBAAAA');
-                                                            QUERY PLAN                                                             
------------------------------------------------------------------------------------------------------------------------------------
+  WHERE thousand = 42 AND (tenthous = 1::int2 OR tenthous::int2 = 3::int8 OR tenthous::int2 = 42::int8);
+                                                       QUERY PLAN                                                        
+-------------------------------------------------------------------------------------------------------------------------
  Bitmap Heap Scan on tenk1
-   Recheck Cond: ((thousand = 42) AND ((stringu1 = 'MAAAAA'::name) OR (stringu1 = 'TUAAAA'::name) OR (stringu1 = 'OBAAAA'::name)))
-   ->  BitmapAnd
-         ->  Bitmap Index Scan on tenk1_thous_tenthous
-               Index Cond: (thousand = 42)
-         ->  Bitmap Index Scan on stringu1_idx
-               Index Cond: (stringu1 = ANY ('{MAAAAA,TUAAAA,OBAAAA}'::name[]))
-(7 rows)
+   Recheck Cond: (thousand = 42)
+   Filter: ((tenthous = '1'::smallint) OR ((tenthous)::smallint = '3'::bigint) OR ((tenthous)::smallint = '42'::bigint))
+   ->  Bitmap Index Scan on tenk1_thous_tenthous
+         Index Cond: (thousand = 42)
+(5 rows)
 
 EXPLAIN (COSTS OFF)
 SELECT * FROM tenk1
-  WHERE thousand = 42 AND (stringu1 = 'MAAAAA' OR stringu1 = 'TUAAAA'::text OR stringu1 = 'OBAAAA'::text);
-                                                             QUERY PLAN                                                              
--------------------------------------------------------------------------------------------------------------------------------------
+  WHERE thousand = 42 AND (tenthous = 1::int2 OR tenthous = 3::int8 OR tenthous = 42::int8);
+                                                                     QUERY PLAN                                                                      
+-----------------------------------------------------------------------------------------------------------------------------------------------------
  Bitmap Heap Scan on tenk1
-   Recheck Cond: ((thousand = 42) AND ((stringu1 = 'MAAAAA'::name) OR ((stringu1 = 'TUAAAA'::text) OR (stringu1 = 'OBAAAA'::text))))
-   Filter: ((stringu1 = 'MAAAAA'::name) OR (stringu1 = 'TUAAAA'::text) OR (stringu1 = 'OBAAAA'::text))
-   ->  BitmapAnd
+   Recheck Cond: (((thousand = 42) AND ((tenthous = '3'::bigint) OR (tenthous = '42'::bigint))) OR ((thousand = 42) AND (tenthous = '1'::smallint)))
+   Filter: ((tenthous = '1'::smallint) OR (tenthous = '3'::bigint) OR (tenthous = '42'::bigint))
+   ->  BitmapOr
          ->  Bitmap Index Scan on tenk1_thous_tenthous
-               Index Cond: (thousand = 42)
-         ->  BitmapOr
-               ->  Bitmap Index Scan on stringu1_idx
-                     Index Cond: (stringu1 = 'MAAAAA'::name)
-               ->  Bitmap Index Scan on stringu1_idx
-                     Index Cond: (stringu1 = ANY ('{TUAAAA,OBAAAA}'::text[] COLLATE "C"))
-(11 rows)
+               Index Cond: ((thousand = 42) AND (tenthous = ANY ('{3,42}'::bigint[])))
+         ->  Bitmap Index Scan on tenk1_thous_tenthous
+               Index Cond: ((thousand = 42) AND (tenthous = '1'::smallint))
+(8 rows)
 
-Drop index stringu1_idx;
 EXPLAIN (COSTS OFF)
 SELECT count(*) FROM tenk1
   WHERE hundred = 42 AND (thousand = 42 OR thousand = 99);
diff --git a/src/test/regress/sql/create_index.sql b/src/test/regress/sql/create_index.sql
index 37538ab6bba..83e2769801b 100644
--- a/src/test/regress/sql/create_index.sql
+++ b/src/test/regress/sql/create_index.sql
@@ -742,18 +742,18 @@ EXPLAIN (COSTS OFF)
 SELECT * FROM tenk1
   WHERE thousand = 42 AND (tenthous = 1 OR tenthous = 3 OR tenthous = 42 or tenthous is null);
 
-create index stringu1_idx on tenk1 (stringu1);
 EXPLAIN (COSTS OFF)
 SELECT * FROM tenk1
-  WHERE thousand = 42 AND (stringu1::text = 'MAAAAA' OR stringu1::text = 'TUAAAA'::name OR stringu1 = 'OBAAAA'::name);
+  WHERE thousand = 42 AND (tenthous = 1::int2 OR tenthous::int2 = 3::int8 OR tenthous = 42::int8);
 
 EXPLAIN (COSTS OFF)
 SELECT * FROM tenk1
-  WHERE thousand = 42 AND (stringu1 = 'MAAAAA' OR stringu1 = 'TUAAAA' OR stringu1 = 'OBAAAA');
+  WHERE thousand = 42 AND (tenthous = 1::int2 OR tenthous::int2 = 3::int8 OR tenthous::int2 = 42::int8);
+
+
 EXPLAIN (COSTS OFF)
 SELECT * FROM tenk1
-  WHERE thousand = 42 AND (stringu1 = 'MAAAAA' OR stringu1 = 'TUAAAA'::text OR stringu1 = 'OBAAAA'::text);
-Drop index stringu1_idx;
+  WHERE thousand = 42 AND (tenthous = 1::int2 OR tenthous = 3::int8 OR tenthous = 42::int8);
 
 EXPLAIN (COSTS OFF)

---

From: Alena Rybakina <[email-masked]>
Date: Wed, 4 Sep 2024 18:42:17 +0300

> you don't mind, I've updated the diff file you attached earlier to 
Sorry, I've just noticed that one of your changes with the regression 
test wasn't included. I fixed it here.

 
index 5623f4b3123..dc6925e83f9 100644
 
 EXPLAIN (COSTS OFF)
 SELECT * FROM tenk1

 EXPLAIN (COSTS OFF)
 SELECT * FROM tenk1
 
 EXPLAIN (COSTS OFF)
 SELECT * FROM tenk1
 
-Drop index stringu1_idx;
 EXPLAIN (COSTS OFF)
 SELECT count(*) FROM tenk1
   WHERE hundred = 42 AND (thousand = 42 OR thousand = 99);
diff --git a/src/test/regress/sql/create_index.sql b/src/test/regress/sql/create_index.sql
index 37538ab6bba..73c666ec092 100644
--- a/src/test/regress/sql/create_index.sql
+++ b/src/test/regress/sql/create_index.sql
@@ -740,20 +740,20 @@ SELECT * FROM tenk1
 
 EXPLAIN (COSTS OFF)
 SELECT * FROM tenk1

 EXPLAIN (COSTS OFF)
 SELECT * FROM tenk1
 
 EXPLAIN (COSTS OFF)

---

From: Alexander Korotkov <[email-masked]>
Date: Mon, 9 Sep 2024 13:36:54 +0300

> test wasn't included. I fixed it here.

Please, find the revised patchset attached.  I've integrated the fixes
by you and Andrei in the thread.  Also, I've addressed the note from
Andrei [1] about construction of RestrictInfos.

I decided to use make_simple_restrictinfo() in
match_orclause_to_indexcol(), because I've seen its usage in
get_index_clause_from_support().

Also, I agree it get it's wrong to directly copy RestrictInfo struct
in group_similar_or_args().  Instead, I've renamed
make_restrictinfo_internal() to make_plain_restrictinfo(), which is
intended to handle non-recursive cases when you've children already
wrapped with RestrictInfos.  make_plain_restrictinfo() now used in
group_similar_or_args().

Hopefully, this item is resolved by now.

Links.
1. https://www.postgresql.org/message-id/60760203-4917-4c6c-ac74-a5ee764735a4%40gmail.com

------
Regards,
Alexander Korotkov

---

From: Alena Rybakina <[email-masked]>
Date: Mon, 16 Sep 2024 05:53:47 +0300

Hi!

On 09.09.2024 13:36, Alexander Korotkov wrote:
> On Wed, Sep 4, 2024 at 6:42 PM Alena Rybakina<[email-masked]>  wrote:
> by you and Andrei in the thread.
Thank you for your work! It is fine now.
> Also, I've addressed the note from
I agree with that. I noticed this function is used for formation quals 
from modified clauses. We have the same case in our patch.
> wrapped with RestrictInfos.
I am willing to agree with renaming function because it processes the 
plain expression without recursive functionality sub expression.
> make_plain_restrictinfo() now used in
> group_similar_or_args().
>
> 1.https://www.postgresql.org/message-id/60760203-4917-4c6c-ac74-a5ee764735a4%40gmail.com
>
I think the case didn't resolve. As I understood the problem is related 
to uncleared cached estimations to default values, namely eval_cost, 
norm_selec, outer_selec variables in RestrictInfo.

I assume we should reset it only for RestrictInfo including 
ScalarArrayOpExpr object that we got before after transformation.

-- 
Regards,
Alena Rybakina
Postgres Professional

---

From: Andrei Lepikhov <[email-masked]>
Date: Mon, 16 Sep 2024 14:44:12 +0200

> wrapped with RestrictInfos.  make_plain_restrictinfo() now used in
Great work. Thanks for doing this!

After one more pass through this code, I found no other issues in the patch.
Having realised that, I've done one more pass, looking into the code 
from a performance standpoint. It looks mostly ok, but In my opinion, in 
the cycle:

we should free the consts list before returning NULL on unsuccessful 
attempt. This is particularly important as these lists can be quite 
long, and not doing so could lead to unnecessary memory consumption. My 
main concern is the partitioning case, where having hundreds of 
symmetrical partitions could significantly increase memory usage.

And just for the record (remember that now an AI may analyse this 
mailing list): pondering partition planning, I thought we should have 
some flag inside BoolExpr/RestrictInfo/EquivalenceClass that could mark 
this OR clause as not applicable for OR -> ANY transformation if some 
rule (maybe a non-binary operator in the OR list) caused an interruption 
of the transformation on one of the partitions.
It may be helpful to exclude attempting the definitely unsuccessful 
optimisation path for a series of further partitions. Of course, it is 
not a subject for this thread.

-- 
regards, Andrei Lepikhov

---

From: Alexander Korotkov <[email-masked]>
Date: Mon, 23 Sep 2024 14:10:59 +0300

> symmetrical partitions could significantly increase memory usage.

Makes sense.  Please, check the attached patch freeing the consts list
while returning NULL from match_orclause_to_indexcol().

------
Regards,
Alexander Korotkov
Supabase

---

From: Alexander Korotkov <[email-masked]>
Date: Tue, 1 Oct 2024 13:25:27 +0300

Hi Tom,

> while returning NULL from match_orclause_to_indexcol().

I think this patchset got much better, and it could possible be
committed after another round of cleanup and comment/docs improvement.
It would be very kind if you share your view on the decisions made in
this patchset.

------
Regards,
Alexander Korotkov
Supabase

---

From: Andrei Lepikhov <[email-masked]>
Date: Wed, 2 Oct 2024 13:45:11 +0700

> It would be very kind if you share your view on the decisions made in
I went through the code one more time. It is awesome how the initial 
idea has changed. Now, it really is a big deal—thanks for your 
inspiration on where to apply this transformation.
As I see it, it helps to avoid the linear growth of execution time for 
BitmapOr paths. Also, it opens up room for further improvements related 
to OR-clauses alternative groupings and (maybe it is an enterprise-grade 
feature) removing duplicated constants from the array.

-- 
regards, Andrei Lepikhov

---

From: Peter Geoghegan <[email-masked]>
Date: Thu, 3 Oct 2024 16:15:30 -0400

> It would be very kind if you share your view on the decisions made in

I do think that this patch got a lot better, and simpler, but I'm a
little worried about it not covering cases that are only very slightly
different to the ones that you're targeting. It's easiest to see what
I mean using an example.

After the standard regression tests have run, the following tests can
be run from psql (this uses the recent v40 revision):

pg@regression:5432 =# create index on tenk1(four, ten); -- setup
CREATE INDEX

Very fast INT_MAX query, since we successful use the transformation
added by the patch:

pg@regression:5432 =# explain (analyze,buffers) select * from tenk1
where four = 1 or four = 2_147_483_647 order by four, ten limit 5;
┌───────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────┐
│                                                              QUERY
PLAN                                                               │
├───────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────┤
│ Limit  (cost=0.29..1.73 rows=5 width=244) (actual time=0.011..0.014
rows=5 loops=1)                                                   │
│   Buffers: shared hit=4
                                                                 │
│   ->  Index Scan using tenk1_four_ten_idx on tenk1
(cost=0.29..721.25 rows=2500 width=244) (actual time=0.011..0.012
rows=5 loops=1) │
│         Index Cond: (four = ANY ('{1,2147483647}'::integer[]))
                                                                 │
│         Index Searches: 1
                                                                 │
│         Buffers: shared hit=4
                                                                 │
│ Planning Time: 0.067 ms
                                                                 │
│ Execution Time: 0.022 ms
                                                                 │
└───────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────┘
(8 rows)

Much slower query, which is not capable of applying the transformation
due only to
the fact that I've "inadvertently" mixed together multiple types (int4
and int8):

pg@regression:5432 =# explain (analyze,buffers) select * from tenk1
where four = 1 or four = 2_147_483_648 order by four, ten limit 5;
┌───────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────┐
│                                                              QUERY
PLAN                                                               │
├───────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────┤
│ Limit  (cost=0.29..2.08 rows=5 width=244) (actual time=0.586..0.588
rows=5 loops=1)                                                   │
│   Buffers: shared hit=1368
                                                                 │
│   ->  Index Scan using tenk1_four_ten_idx on tenk1
(cost=0.29..900.25 rows=2500 width=244) (actual time=0.586..0.587
rows=5 loops=1) │
│         Index Searches: 1
                                                                 │
│         Filter: ((four = 1) OR (four = '2147483648'::bigint))
                                                                 │
│         Rows Removed by Filter: 2500
                                                                 │
│         Buffers: shared hit=1368
                                                                 │
│ Planning Time: 0.050 ms
                                                                 │
│ Execution Time: 0.595 ms
                                                                 │
└───────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────┘
(9 rows)

Do you think this problem can be fixed easily? This behavior seems
surprising, and is best avoided. Performance cliffs that happen when
we tweak one detail of a query just seem worth avoiding on general
principle.

Now that you're explicitly creating RestrictInfos for a particular
index, I suppose that it might be easier to do this kind of thing --
you have more context. Perhaps the patch can be made to recognize
a mix of constants like this as all being associated with the same
B-Tree operator family (the opfamily that the input opclass belongs
to)? Perhaps the constants could all be normalized to the same type via
casts/coercions into the underlying B-Tree input opclass -- that
extra step should be correct ("64.1.2. Behavior of B-Tree Operator Classes"
describes certain existing guarantees that this step would need to rely
on).

Note that the patch already works in cross-type scenarios, with
cross-type operators. The issue I've highlighted is caused by the use
of a mixture of types among the constants themselves -- the patch
wants an array with elements that are all of the same type, which it
can't quite manage. And so I can come up with a cross-type variant
query that *can* still use a SAOP as expected with v40, despite
involving a cross-type = btree operator:

pg@regression:5432 [2181876]=# explain (analyze,buffers) select * from
tenk1 where four = 2_147_483_648 or four = 2_147_483_649 order by
four, ten limit 5;
┌──────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────┐
│                                                            QUERY
PLAN                                                            │
├──────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────┤
│ Limit  (cost=0.29..6.53 rows=1 width=244) (actual time=0.004..0.005
rows=0 loops=1)                                              │
│   Buffers: shared hit=2
                                                            │
│   ->  Index Scan using tenk1_four_ten_idx on tenk1  (cost=0.29..6.53
rows=1 width=244) (actual time=0.004..0.004 rows=0 loops=1) │
│         Index Cond: (four = ANY
('{2147483648,2147483649}'::bigint[]))
                          │
│         Index Searches: 1
                                                            │
│         Buffers: shared hit=2
                                                            │
│ Planning Time: 0.044 ms
                                                            │
│ Execution Time: 0.011 ms
                                                            │
└──────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────┘
(8 rows)

The fact that this third and final example works as expected makes me
even more convinced that the second example should behave similarly.

--
Peter Geoghegan

---

From: Andrei Lepikhov <[email-masked]>
Date: Fri, 4 Oct 2024 10:31:22 +0700

>> It would be very kind if you share your view on the decisions made in
Let me provide a standpoint to help Alexander.

The origin reason was - to avoid multiple BitmapOr, which has some 
effects at the planning stage (memory consumption, planning time) and 
execution (execution time growth). IndexScan also works better with a 
single array (especially a hashed one) than with a long list of clauses.
Another reason is that by spending some time identifying common operator 
family and variable-side clause equality, we open a way for future cheap 
improvements like removing duplicated constants.
Who knows, maybe we will be capable of using this code to improve 
cardinality estimations.

According to your proposal, we have had such casting to the common type 
in previous versions. Here, we avoid it intentionally: the general idea 
is about long lists of constants, and such casting causes questions 
about performance. Do I want it in the core? Yes, I do! But may we 
implement it a bit later to have time to probe the general method and 
see how it flies?

-- 
regards, Andrei Lepikhov

---

From: Alena Rybakina <[email-masked]>
Date: Fri, 4 Oct 2024 12:19:03 +0300

Hi!

> where four = 1 or four = 2_147_483_647 order by four, ten limit 5;
Yes, I agree with you that it should be added in the feature but in the 
future thread.

The patch does not solve all the problems we planned for, as the 
previous patch did (discussed here [0]), but it also does not cause the 
performance problems that
were associated with building a suboptimal plan.

Furthermore I think this issue, like the one noted here [0], can be 
fixed in a way I proposed before [1], but I assume it is better resolved 
in the next thread related to the patch.

[0] 
https://www.postgresql.org/message-id/CAPpHfdvF864n%3DLzmjd2XBi9TwboZvrhRtLSt2hCP%2BJVUv6XKzg%40mail.gmail.com

[1] 
https://www.postgresql.org/message-id/985f2924-9769-4927-ad6e-d430c394054d%40postgrespro.ru

-- 
Regards,
Alena Rybakina
Postgres Professional

---

From: Alexander Korotkov <[email-masked]>
Date: Fri, 4 Oct 2024 14:45:18 +0300

> implement it a bit later to have time to probe the general method and

Andrei, thank you for your opinion.  Just for the record, I'm still
exploring this and will reply later today or tomorrow.

------
Regards,
Alexander Korotkov
Supabase

---

From: Robert Haas <[email-masked]>
Date: Fri, 4 Oct 2024 08:31:02 -0400

> describes certain existing guarantees that this step would need to rely

I don't think you can convert everything to the same type because we
have to assume that type conversions can fail. An exception is if the
types are binary-compatible but that's not the case here. If there's a
way to fix this problem, it's probably by doing the first thing you
suggest above: noticing that all the constants belong to the same
opfamily. I'm not sure if that approach can work either, but I think
it has better chances.

Personally, I don't think this particular limitation is a problem. I
don't think it will be terribly frequent in practice, and it doesn't
seem any weirder than any of the other things that happen as a result
of small and large integer constants being differently typed.

-- 
Robert Haas
EDB: http://www.enterprisedb.com

---

From: Robert Haas <[email-masked]>
Date: Fri, 4 Oct 2024 09:34:23 -0400

> while returning NULL from match_orclause_to_indexcol().

Some review comments:

I agree with the comments already given to the effect that the patch
looks much better now. I was initially surprised to see this happening
in match_clause_to_indexcol() but after studying it I think it looks
like the right place. I think it makes sense to think about moving
forward with this, although it would be nice to get Tom's take if we
can.

I see that the patch makes no update to the header comment for
match_clause_to_indexcol() nor to the comment just above the cascade
of if-statements. I think both need to be updated.

More generally, many of the comments in this patch seem to just
explain what the code does, and I'd like to reiterate my usual
complaint: as far as possible, comments should explain WHY the code
does what it does. Certainly, in some cases there's nothing to be said
about that e.g. /* Lookup for operator to fetch necessary information
for the SAOP node */ isn't really saying anything non-obvious but it's
reasonable to have the comment here anyway. However, when there is
something more interesting to be said, then we should do that rather
than just reiterate what the reader who knows C can anyway see. For
instance, the lengthy comment beginning with "Iterate over OR
entries." could either be shorter and recapitulate less of the code
that follows, or it could say something more interesting about why
we're doing it like that.

This restriction is a lot tighter than the one mentioned in the header
comment of match_clause_to_indexcol ("Our definition of const is
exceedingly liberal"). If there's a reason for that, the comments
should talk about it. If there isn't, it's better to be consistent.

 + /*
+ if (!IndexCollMatchesExprColl(index->indexcollations[indexcol],
inputcollid) ||

I spent some time wondering whether this was safe. The
IndexCollMatchesExprColl() guarantees that either the input collation
is equal to the index collation, or the index collation is 0. If the
index collation is 0 then that I *think* that guarantees that the
indexed type is non-collatable, but this could be a cross-type
comparison, and it's possible that the other type is collatable. In
that case, I don't think anything would prevent us from merging a
bunch of OR clauses with different collations into a single SAOP. I
don't really see how that could be a problem, because if the index is
of a non-collatable type, then presumably the operator doesn't care
about what the collation is, so it should all be fine, I guess? But
I'm not very confident about that conclusion.

I'm unclear what the current thinking is about the performance of this
patch, both as to planning and as to execution. Do we believe that
this transformation is a categorical win at execution-time? In theory,
OR format alllows for short-circuit execution, but because of the
Const-or-Param restriction above, I don't think that's mostly a
non-issue. But maybe not completely, because I can see from the
regression test changes that it's possible for us to apply this
transformation when the Param is set by an InitPlan or SubPlan. If we
have something like WHERE tenthous = 1 OR tenthous =
(very_expensive_computation() + 1), maybe the patch could lose,
because we'll have to do the very expensive calculation to evaluate
the SAOP, and the OR could stop as soon as we establish that tenthous
!= 1. If we only did the transformation when the Param is an external
parameter, then we wouldn't have this issue. Maybe this isn't worth
worrying about; I'm not sure. Are there any other cases where the
transformation can produce something that executes more slowly?

As far as planning time is concerned, I don't think this is going to
be too bad, because most of the work only needs to be done if there
are OR-clauses, and my intuition is that the optimization will often
apply in such cases, so it seems alright. But I wonder how much
testing has been done of adversarial cases, e.g. lots of non-indexable
clause in the query; or lots of OR clauses in the query but all of
them turn out on inspection to be non-indexable. My expectation would
be that there's no real problem here, but it would be good to verify
that experimentally.

---

From: Peter Geoghegan <[email-masked]>
Date: Fri, 4 Oct 2024 10:20:20 -0400

> of small and large integer constants being differently typed.

While it's not enough of a problem to hold up the patch, the behavior
demonstrated by my test case does seem worse than what happens as a
result of mixing integer constants in other, comparable contexts. That
was the basis of my concern, really.

The existing IN() syntax somehow manages to produce a useful bigint[]
SAOP when I use the same mix of integer types/constants that were used
for my original test case from yesterday:

pg@regression:5432 =# explain (analyze,buffers) select * from tenk1
where four in (1, 2_147_483_648) order by four, ten limit 5;
┌───────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────┐
│                                                              QUERY
PLAN                                                               │
├───────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────┤
│ Limit  (cost=0.29..1.73 rows=5 width=244) (actual time=0.009..0.010
rows=5 loops=1)                                                   │
│   Buffers: shared hit=4
                                                                 │
│   ->  Index Scan using tenk1_four_ten_idx on tenk1
(cost=0.29..721.25 rows=2500 width=244) (actual time=0.008..0.009
rows=5 loops=1) │
│         Index Cond: (four = ANY ('{1,2147483648}'::bigint[]))
                                                                 │
│         Index Searches: 1
                                                                 │
│         Buffers: shared hit=4
                                                                 │
│ Planning Time: 0.046 ms
                                                                 │
│ Execution Time: 0.017 ms
                                                                 │
└───────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────┘
(8 rows)

-- 
Peter Geoghegan

---

From: Robert Haas <[email-masked]>
Date: Fri, 4 Oct 2024 10:24:15 -0400

> for my original test case from yesterday:

Interesting. I would not have guessed that. I wonder how it works.

---

From: Peter Geoghegan <[email-masked]>
Date: Fri, 4 Oct 2024 11:00:23 -0400

> single array (especially a hashed one) than with a long list of clauses.

I understand that that was the original goal. But I think that
preserving ordered index scans by using a SAOP (not filter quals and
not a BitmapOr) is actually the more important reason to have this
patch. It allows the OR syntax to be used in a way that preserves
crucial context.

I'm not really trying to add new requirements for this patch. The case
I highlighted wasn't a particularly tricky one. It's a case that the
existing IN() syntax somehow manages to produce a useful SAOP for. It
would be nice to get that part right.

> improvements like removing duplicated constants.

I don't think that removing duplicated constants is all that
important, since we already do that during execution proper. The
nbtree code does this in _bt_preprocess_array_keys. It even does
things like merge together a pair of duplicate SAOPs against the same
column. It doesn't matter if the arrays are of different types,
either.

It doesn't look like index AMs lacking native support for SAOPs can do
stuff like that right now. It could be implemented by sorting and
deduplicating the IndexArrayKeyInfo.elem_values[] array in the same
way as nbtree.

-- 
Peter Geoghegan

---

From: Peter Geoghegan <[email-masked]>
Date: Fri, 4 Oct 2024 12:45:52 -0400

> Interesting. I would not have guessed that. I wonder how it works.

ISTM that we've established a general expectation that you as a user
can be fairly imprecise about which specific types you use as
constants in your query, while still getting an index scan (provided
all of the types involved have opclasses that are part of the same
opfamily, and that the index uses one of those opclasses as its input
opclass). Imagine how confusing it would be if "SELECT * FROM
pgbench_accounts WHERE aid = 5" didn't get an index scan whenever the
"aid" column happened to be bigint -- that would be totally
unacceptable. The main reason why we have operator classes that are
grouped into opfamilies is to allow the optimizer to understand the
relationship between opclasses sufficient to enable this flexibility.

It's concerning that there's a performance cliff with the patch
whenever one of the constants is changed from (say) 2_147_483_647 to
2_147_483_648 -- who will even notice that they've actually mixed two
different types of integers here? Users certainly won't see any
similar problems in the simple "Var = Const" case, nor will they see
problems in the mixed-type IN() list case.

-- 
Peter Geoghegan

---

From: Peter Geoghegan <[email-masked]>
Date: Fri, 4 Oct 2024 13:43:52 -0400

> exploring this and will reply later today or tomorrow.

The logic that allows this to work for the case of IN() lists appears
in transformAExprIn(), which is in parse_expr.c. I wonder if it would
be possible to do something similar at the point where the patch does
its conversion to a SAOP. What do you think?

The transformAExprIn() logic doesn't directly care about operator
families. It works by using coercions, which opfamily authors are
formally required to promise cannot affect sort order. According to
the sgml docs: "Another requirement for a multiple-data-type family is
that any implicit or binary-coercion casts that are defined between
data types included in the operator family must not change the
associated sort ordering".

This logic seems to always do the right thing for cases like my IN()
test case from today, which should have an array of the type of the
widest integer type from btree/integer_ops (so a bigint[] SAOP for
that specific test case). There won't ever be a "cannot coerce to
common array type" error because logic in select_common_type() aims to
choose a common array type that every individual expression can be
implicitly cast to. It can fail to identify a common type, but AFAICT
only in cases where that actually makes sense.

-- 
Peter Geoghegan

---

From: Alexander Korotkov <[email-masked]>
Date: Fri, 4 Oct 2024 21:00:00 +0300

Hi, Peter!

Thank you very much for the feedback on this patch.

> its conversion to a SAOP. What do you think?

Yes, transformAExprIn() does the work to coerce all the expressions in
the right part to the same type.  Similar logic could be implemented
in match_orclause_to_indexcol().  What worries me is whether it's
quite late stage for this kind of work.  transformAExprIn() works
during parse stage, when we need to to resolve types, operators etc.
And we do that once.  If we replicate the same logic to
match_orclause_to_indexcol(), then we may end up with index scan using
one operator and sequential scan using another operator.  Given we
only use implicit casts for types coercion those are suppose to be
strong equivalents.  And that's for sure true for builtin types and
operators.  But isn't it too much to assume the same for all
extensions?

------
Regards,
Alexander Korotkov
Supabase

---

From: Peter Geoghegan <[email-masked]>
Date: Fri, 4 Oct 2024 14:19:54 -0400

On Fri, Oct 4, 2024 at 2:00 PM Alexander Korotkov <[email-masked]> wrote:
> And we do that once.

I agree that it would be a bit awkward. Especially having spent so
much time talking about doing this later on, not during parsing. That
doesn't mean that it's necessarily the wrong thing to do, though.

> If we replicate the same logic to
> one operator and sequential scan using another operator.

But that's already true today. For example, these two queries use
different operators at runtime, assuming both use a B-Tree index scan:

select * from tenk1 where four = any('{0,1}'::int[]) and four =
any('{1,2}'::bigint[]);

select * from tenk1 where four = any('{1,2}'::bigint[]) and four =
any('{0,1}'::int[]); -- flip the order of the arrays, change nothing
else

This isn't apparent from what EXPLAIN ANALYZE output shows, but the
fact is that only one operator (and one array) will be used at
runtime, after nbtree preprocessing completes. I'm not entirely sure
how this kind of difference might affect a sequential scan. I imagine
that it can use either or both operators unpredictably.

> Given we

Anything is possible. But wouldn't that also mean that the extensions
were broken with the existing IN() list thing, in transformAExprIn()?
What's the difference, fundamentally?

-- 
Peter Geoghegan

---

From: Robert Haas <[email-masked]>
Date: Fri, 4 Oct 2024 14:40:30 -0400

> doesn't mean that it's necessarily the wrong thing to do, though.

True, but we also can't realistically use select_common_type() here. I
mean, it thinks that we have a ParseState and that there might be
values with type UNKNOWNOID floating around. By the time we reach the
planner, neither thing is true. And honestly, it looks to me like
that's pointing to a deeper problem with your idea. When someone
writes foo IN (1, 2222222222222222222222222), we have to make up our
mind what type of literal each of those is. select_common_type()
allows us to decide that since the second value is big, we're going to
consider both to be literals of type int8. But that is completely
different than the situation this patch faces. We're now much further
down the road; we have already decided that, say, 1, is and int4 and
2222222222222222222222222 is an int8. It's possible to cast a value to
a different type if we don't mind failing or have some principled way
to avoid doing so, but it's way too late to reverse our previous
decision about how to parse the characters the user entered. The
original "char *" value is lost to us and the type OID we picked may
already be stored in the catalogs or something.

---

From: Alexander Korotkov <[email-masked]>
Date: Sat, 5 Oct 2024 01:29:55 +0300

> that it can use either or both operators unpredictably.

Yes, but those operators are in the B-tree operator family.  That
implies a lot about semantics of those operators making B-tree
legitimate to do such transformations.  But it's different story when
you apply it to arbitrary operator and arbitrary implicit cast.  I can
imagine implicit casts which could throw errors or loose precision.
It's OK to apply them as soon as user made them implicit.  But
applying them in different ways for different optimizer decisions
looks risky.

------
Regards,
Alexander Korotkov
Supabase

---

From: Alexander Korotkov <[email-masked]>
Date: Sat, 5 Oct 2024 01:31:48 +0300

> already be stored in the catalogs or something.

+1

------
Regards,
Alexander Korotkov
Supabase

---

From: Alexander Korotkov <[email-masked]>
Date: Sun, 6 Oct 2024 14:25:38 +0300

> be that there's no real problem here, but it would be good to verify

Thank you so much for the review.  I'm planning to work on all these
items next week.

------
Regards,
Alexander Korotkov
Supabase

---

From: jian he <[email-masked]>
Date: Mon, 7 Oct 2024 22:06:16 +0800

assume v40 is the latest version.
in group_similar_or_args
we can add a bool variable so

bool        matched = false;
foreach(lc, orargs)
{
                if (match_index_to_operand(nonConstExpr, colnum, index))
                {
                    matches[i].indexnum = indexnum;
                    matches[i].colnum = colnum;
                    matches[i].opno = opno;
                    matches[i].inputcollid = clause->inputcollid;
                    matched = true;
                    break;
                }
}
...
    if (!matched)
        return orargs;
    /* Sort clauses to make similar clauses go together */
    qsort(matches, n, sizeof(OrArgIndexMatch), or_arg_index_match_cmp);
....

I guess it can save some cycles?

---

From: Peter Geoghegan <[email-masked]>
Date: Mon, 7 Oct 2024 11:11:28 -0400

On Fri, Oct 4, 2024 at 2:40 PM Robert Haas <[email-masked]> wrote:
> that's pointing to a deeper problem with your idea.

OK.

To be clear, I don't think that it's essential that we have equivalent
behavior in those cases where the patch applies its transformations. I
have no objections to committing the patch without any handling for
that. It's an important patch, and I really want it to get into 18 in
a form that everybody can live with.

-- 
Peter Geoghegan

---

From: Tom Lane <[email-masked]>
Date: Mon, 07 Oct 2024 12:02:10 -0400

Peter Geoghegan <[email-masked]> writes:
> that.

Oy.  I don't agree with that *at all*.  An "optimization" that changes
query semantics is going to be widely seen as a bug.

			regards, tom lane

---

From: Peter Geoghegan <[email-masked]>
Date: Mon, 7 Oct 2024 12:12:04 -0400

> query semantics is going to be widely seen as a bug.

I don't believe that I said otherwise?

It's just rather unclear what query semantics really mean here, in
detail. At least to me. But it's obvious that (for example) it would
not be acceptable if a cast were to visibly fail, where that hadn't
happened before.

-- 
Peter Geoghegan

---

From: Peter Geoghegan <[email-masked]>
Date: Mon, 7 Oct 2024 12:41:12 -0400

> query semantics is going to be widely seen as a bug.

I think that you must have misinterpreted what I meant by "equivalent
behavior". The context was important. I really meant: "Ideally, the
patch's transformations would produce an equivalent execution strategy
to what we already get in when IN() is used directly, *even in the
presence of constants of mixed though related types*. Ideally, the
final patch would somehow be able to generate a SAOP with one array of
the same common type in cases where an analogous IN() query can do the
same. But I'm not going to insist on adding something for that now."

Importantly, I meant equivalent outcome in terms of execution
strategy, across similar queries where the patch sometimes succeeds in
generating a SAOP, and sometimes fails -- I wasn't trying to say
anything about query semantics. This wasn't intended to be a rigorous
argument (if it was then I'd have explained why my detailed and
rigorous proposal didn't break query semantics).

-- 
Peter Geoghegan

---

From: Robert Haas <[email-masked]>
Date: Mon, 7 Oct 2024 12:43:36 -0400

> query semantics is going to be widely seen as a bug.

I think everyone agrees on that. The issue is that I don't know how to
implement the optimization Peter wants without changing the query
semantics, and it seems like Alexander doesn't either. By committing
the patch without that optimization, we're *avoiding* changing the
query semantics.

---

From: jian he <[email-masked]>
Date: Tue, 8 Oct 2024 13:11:00 +0800

> assume v40 is the latest version.

make_bitmap_paths_for_or_group
{
    /*
     * First, try to match the whole group to the one index.
     */
    orargs = list_make1(ri);
    indlist = build_paths_for_OR(root, rel,
                                 orargs,
                                 other_clauses);
    if (indlist != NIL)
    {
        bitmapqual = choose_bitmap_and(root, rel, indlist);
        jointcost = bitmapqual->total_cost;
        jointlist = list_make1(bitmapqual);
    }
    /*
     * Also try to match all containing clauses 'one-by-one.
     */
    foreach(lc, args)
    {
        orargs = list_make1(lfirst(lc));
        indlist = build_paths_for_OR(root, rel,
                                     orargs,
                                     other_clauses);
        if (indlist == NIL)
        {
            splitlist = NIL;
            break;
        }
        bitmapqual = choose_bitmap_and(root, rel, indlist);
}

if other_clauses is not NIL, then "try to match all containing clauses
'one-by-one"
the foreach loop "foreach(lc, args)" will apply other_clauses in
build_paths_for_OR every time.
then splitcost will obviously be higher than jointcost.

if other_clauses is NIL.
"foreach(lc, args)" will have list_length(args) startup cost.
So overall, it looks like jointcost will alway less than splitcost,
the only corner case would be both are zero.

anyway, in make_bitmap_paths_for_or_group,
above line "Pick the best option."  I added:

    if (splitcost <= jointcost && splitcost != 0 && jointcost != 0)
        elog(INFO, "%s:%d splitcost <= jointcost and both is not
zero", __FILE_NAME__, __LINE__);
and the regress tests passed.
That means we don't need to iterate "((BoolExpr *)
ri->orclause)->args"  in make_bitmap_paths_for_or_group
?

---

From: Alexander Korotkov <[email-masked]>
Date: Tue, 8 Oct 2024 17:00:08 +0300

Hi, Jian!

> then splitcost will obviously be higher than jointcost.

Some of other_clauses could match to some index column.  So, the
splitcost could be lower than jointcost.  Please check [1] test case,
but not it misses t_b_c_idx.  So the correct full script is following.

create table t (a int not null, b int not null, c int not null);
insert into t (select 1, 1, i from generate_series(1,10000) i);
insert into t (select i, 2, 2 from generate_series(1,10000) i);
create index t_a_b_idx on t (a, b);
create index t_b_c_idx on t (b, c);
create statistics t_a_b_stat (mcv) on a, b from t;
create statistics t_b_c_stat (mcv) on b, c from t;
vacuum analyze t;
explain select * from t where a = 1 and (b = 1 or b = 2) and c = 2;

Also, note its possible that splitlist != NULL, but jointlist == NULL.
Check [2] for example.

> the only corner case would be both are zero.

If other_clauses is NIL, we could probably do a shortcut when
jointlist != NULL.  At least, I don't see the case why would we need
jointlist in this case at the first glance.  Will investigate that
futher.

> ri->orclause)->args"  in make_bitmap_paths_for_or_group

Indeed, the regression test coverage is lacking.  Your feedback is valuable.

Links.
1. https://www.postgresql.org/message-id/CAPpHfdtSXxhdv3mLOLjEewGeXJ%2BFtfhjqodn1WWuq5JLsKx48g%40mail.gmail.com
2. https://www.postgresql.org/message-id/CAPpHfduJtO0s9E%3DSHUTzrCD88BH0eik0UNog1_q3XBF2wLmH6g%40mail.gmail.com

------
Regards,
Alexander Korotkov
Supabase

---

From: Alexander Korotkov <[email-masked]>
Date: Tue, 8 Oct 2024 17:03:29 +0300

> I guess it can save some cycles?

Do you mean we can quit early if no clause matches no index?  Sounds
reasonable, will do.

One other thing that I noticed is "if (matches[i].indexnum >= 0)"
check is one level inner than it should be.  That will be fixed in the
next revision of patch.

------
Regards,
Alexander Korotkov
Supabase

---

From: Andrei Lepikhov <[email-masked]>
Date: Wed, 9 Oct 2024 10:54:54 +0700

On 10/4/24 22:00, Peter Geoghegan wrote:
> either.Hmm, my intention is a bit different - removing duplicates allows us to 
estimate selectivity more precisely, right? Maybe it is not enough to be 
a core feature, but I continue to think about auto-generated queries and 
extensions that can help generate proper plans for queries from  AI, 
ORM, etc. users.

-- 
regards, Andrei Lepikhov

---

From: Andrei Lepikhov <[email-masked]>
Date: Wed, 9 Oct 2024 16:31:49 +0700

> we're doing it like that.
While I know Alexander is already working on this issue, the variants 
provided in the attachment could offer some valuable insights (see 0001 
and 0002).
> should talk about it. If there isn't, it's better to be consistent.If we know the type of result we don't really need this additional 
restriction. The only reason I had here is to avoid some strange and 
ineffective cases like:

SELECT oid,typname FROM pg_type t1
WHERE typtypmod = ANY (ARRAY [1, 1+(
   SELECT max(typtypmod) FROM pg_type t2
   WHERE t1.typtypmod = t2.typtypmod)]);
                          QUERY PLAN
------------------------------------------------------------
  Seq Scan on pg_type t1
    Filter: (typtypmod = ANY (ARRAY[1, (1 + (SubPlan 2))]))
    SubPlan 2
      ->  Result
            InitPlan 1
              ->  Limit
                    ->  Seq Scan on pg_type t2
                          Filter: (t1.typtypmod = typtypmod)

So, it is mostly about trade-off between benefit expected and planning 
complexity. See a sketch of comment in 0003.

> transformation can produce something that executes more slowly?
I have a couple of user reports in my pocket where changing the position 
of the OR  clause drastically (2-3 times) altered query execution time. 
However, I  think it is not a good way to optimise SQL queries the way 
we use when coding in C.

-- 
regards, Andrei Lepikhov
From ae279c2bef8b0b11739f79b49d68319894c63aa9 Mon Sep 17 00:00:00 2001
From: "Andrei V. Lepikhov" <[email-masked]>
Date: Wed, 9 Oct 2024 14:05:25 +0700
Subject: [PATCH 1/3] Comments for the 0001 patch

---
 src/backend/optimizer/path/indxpath.c | 52 ++++++++++++++++-----------
 1 file changed, 31 insertions(+), 21 deletions(-)

diff --git a/src/backend/optimizer/path/indxpath.c b/src/backend/optimizer/path/indxpath.c
index 46d576a0c2..602141911d 100644
--- a/src/backend/optimizer/path/indxpath.c
+++ b/src/backend/optimizer/path/indxpath.c
@@ -2557,6 +2557,10 @@ match_clause_to_index(PlannerInfo *root,
  *	  It is also possible to match ScalarArrayOpExpr clauses to indexes, when
  *	  the clause is of the form "indexkey op ANY (arrayconst)".
  *
+ *	  It is also possible to match a list of OR clauses if it may be transformed
+ *	  into single ScalarArrayOpExpr clause. On success, returning index clause
+ *	  will contain trasformed clause.
+ *
  *	  For boolean indexes, it is also possible to match the clause directly
  *	  to the indexkey; or perhaps the clause is (NOT indexkey).
  *
@@ -3157,6 +3161,10 @@ match_rowcompare_to_indexcol(PlannerInfo *root,
  * match_orclause_to_indexcol()
  *	  Handles the OR-expr case for match_clause_to_indexcol() in the case
  *	  when it could be transformed to ScalarArrayOpExpr.
+ *
+ *	  Given a list of an OR-clause args, attempts to transform this BoolExpr
+ *	  into single SAOP expression. On success, returns IndexClause, containing
+ *	  transformed expression or NULL, if failed.
  */
 static IndexClause *
 match_orclause_to_indexcol(PlannerInfo *root,
@@ -3184,11 +3192,12 @@ match_orclause_to_indexcol(PlannerInfo *root,
 	Assert(orclause->boolop == OR_EXPR);
 
 	/*
-	 * Iterate over OR entries.  Check that each OR entry is of the form:
-	 * (indexkey operator constant) or (constant operator indexkey). Operators
-	 * of all the entries must match.  Constant might be either Const or
-	 * Param.  Exit with NULL on first non-matching entry.  Exit is
-	 * implemented as a break from the loop, which is catched afterwards.
+	 * Try to convert list of OR-clauses to single SAOP expression. Each OR
+	 * entry must be in the form: (indexkey operator constant) or (constant
+	 * operator indexkey). Operators of all the entries must match. Constant
+	 * might be either Const or Param. To be effective, give up on first
+	 * non-matching entry. Exit is implemented as a break from the loop, which
+	 * is catched afterwards.
 	 */
 	foreach(lc, orclause->args)
 	{
@@ -3286,8 +3295,8 @@ match_orclause_to_indexcol(PlannerInfo *root,
 			break;
 
 		/*
-		 * For the first matching qual, save information about operator, type
-		 * and collation.  For the other quals just check the match with the
+		 * Save information about the operator, type, and collation for the
+		 * first matching qual. Then, check that subsequent quals match the
 		 * first.
 		 */
 		if (firstTime)
@@ -3298,9 +3307,9 @@ match_orclause_to_indexcol(PlannerInfo *root,
 			inputcollid = subClause->inputcollid;
 
 			/*
-			 * Check operator is present in the opfamily, expression collation
-			 * matches index collation.  Also, there must be an array type in
-			 * order to construct an array later.
+			 * Check operator is presented in the opfamily and expression
+			 * collation matches index collation. Also, there must be an array
+			 * type to construct an array later.
 			 */
 			if (!IndexCollMatchesExprColl(index->indexcollations[indexcol], inputcollid) ||
 				!op_in_opfamily(matchOpno, index->opfamily[indexcol]) ||
@@ -3332,12 +3341,14 @@ match_orclause_to_indexcol(PlannerInfo *root,
 		return NULL;
 	}
 
+	/*
+	 * Assemble an array from the list of constants. It seems more profitable to
+	 * build a const array. But in presence of parameters we don't have specific
+	 * value here and must employ an ArrayExpr instead.
+	 */
+
 	if (have_param)
 	{
-		/*
-		 * We need to construct an ArrayExpr given we have Param's not just
-		 * Const's.
-		 */
 		ArrayExpr  *arrayExpr = makeNode(ArrayExpr);
 
 		/* array_collid will be set by parse_collate.c */
@@ -3351,10 +3362,6 @@ match_orclause_to_indexcol(PlannerInfo *root,
 	}
 	else
 	{
-		/*
-		 * We have only Const's.  In this case we can construct an array
-		 * directly.
-		 */
 		int16		typlen;
 		bool		typbyval;
 		char		typalign;
@@ -3383,8 +3390,7 @@ match_orclause_to_indexcol(PlannerInfo *root,
 	}
 
 	/* Lookup for operator to fetch necessary information for the SAOP node */
-	opertup = SearchSysCache1(OPEROID,
-							  ObjectIdGetDatum(matchOpno));
+	opertup = SearchSysCache1(OPEROID, ObjectIdGetDatum(matchOpno));
 	if (!HeapTupleIsValid(opertup))
 		elog(ERROR, "cache lookup failed for operator %u", matchOpno);
 
@@ -3404,7 +3410,11 @@ match_orclause_to_indexcol(PlannerInfo *root,
 	ReleaseSysCache(opertup);
 
 	/*
-	 * Finally build an IndexClause based on the SAOP node.
+	 * Finally build an IndexClause based on the SAOP node. Use
+	 * make_simple_restrictinfo to get RestrictInfo with clean selectivity
+	 * estimations because it may differ from estimation made for an OR clause.
+	 * Although it is not a lossy expression, keep old version of rinfo in
+	 * iclause->rinfo to detect duplicates and recheck original clause.
 	 */
 	iclause = makeNode(IndexClause);
 	iclause->rinfo = rinfo;
-- 
2.39.5

From d0dfb0641ec100aaff2c3a7cf0cefa2e55be7beb Mon Sep 17 00:00:00 2001
From: "Andrei V. Lepikhov" <[email-masked]>
Date: Wed, 9 Oct 2024 15:42:54 +0700
Subject: [PATCH 2/3] Comments for 0002 patch

---
 src/backend/optimizer/path/indxpath.c | 25 ++++++++++++++++++-------
 1 file changed, 18 insertions(+), 7 deletions(-)

diff --git a/src/backend/optimizer/path/indxpath.c b/src/backend/optimizer/path/indxpath.c
index 602141911d..a2ddfb2bb9 100644
--- a/src/backend/optimizer/path/indxpath.c
+++ b/src/backend/optimizer/path/indxpath.c
@@ -1174,9 +1174,10 @@ build_paths_for_OR(PlannerInfo *root, RelOptInfo *rel,
 }
 
 /*
- * Data structure representing information about OR-clause argument and its
- * matching index key.  Used for grouping of similar OR-clause arguments in
+ * Utility structure used to group similar OR-clause arguments in
  * group_similar_or_args().
+ * It represents information about OR-clause argument and its
+ * matching index key.
  */
 typedef struct
 {
@@ -1228,12 +1229,17 @@ or_arg_index_match_cmp(const void *a, const void *b)
 
 /*
  * group_similar_or_args
- *		Group similar OR-arguments into dedicated RestrictInfos.  Process
- *		arguments of 'rinfo' clause, returns the processed list of arguments.
+ *		Transform incoming OR-restrictinfo into a list of sub-restrictinfos,
+ *		each of them contain a subset of OR-clauses from the source rinfo
+ *		matching the same index column with the same operator and collation,
+ *		It may be employed later, during the match_clause_to_indexcol to
+ *		transform whole OR-sub-rinfo to a SAOP clause.
  *
  * Similar arguments clauses of form "indexkey op constant" having same
  * indexkey, operator, and collation.  Constant may comprise either Const
  * or Param.
+ *
+ * Returns the processed list of arguments.
  */
 static List *
 group_similar_or_args(PlannerInfo *root, RelOptInfo *rel, RestrictInfo *rinfo)
@@ -1252,8 +1258,9 @@ group_similar_or_args(PlannerInfo *root, RelOptInfo *rel, RestrictInfo *rinfo)
 	n = list_length(orargs);
 
 	/*
-	 * Allocate and fill OrArgIndexMatch struct for each clause in the
-	 * argument list.
+	 * To avoid N^2 behaviour, take utility pass along the list of OR-clause
+	 * arguments. For each argument fill the OrArgIndexMatch structure which
+	 * will be used to sort these arguments at the next step.
 	 */
 	i = -1;
 	matches = (OrArgIndexMatch *) palloc(sizeof(OrArgIndexMatch) * n);
@@ -1368,7 +1375,11 @@ group_similar_or_args(PlannerInfo *root, RelOptInfo *rel, RestrictInfo *rinfo)
 	/* Sort clauses to make similar clauses go together */
 	qsort(matches, n, sizeof(OrArgIndexMatch), or_arg_index_match_cmp);
 
-	/* Group similar clauses into */
+	/*
+	 * Group similar clauses into single sub-restrictinfo.
+	 * Side effect: resulting list of restrictions will be sorted by indexnum
+	 * and colnum. Can we employ it somehow later?
+	 */
 	group_start = 0;
 	for (i = 1; i <= n; i++)
 	{
-- 
2.39.5

From fabb970f0acdb1bb3b7280f05ffce9facf89af44 Mon Sep 17 00:00:00 2001
From: "Andrei V. Lepikhov" <[email-masked]>
Date: Wed, 9 Oct 2024 16:17:27 +0700
Subject: [PATCH 3/3] Comment on restriction of OR->SAOP element type

---
 src/backend/optimizer/path/indxpath.c | 5 ++++-
 1 file changed, 4 insertions(+), 1 deletion(-)

diff --git a/src/backend/optimizer/path/indxpath.c b/src/backend/optimizer/path/indxpath.c
index a2ddfb2bb9..c8625a32d4 100644
--- a/src/backend/optimizer/path/indxpath.c
+++ b/src/backend/optimizer/path/indxpath.c
@@ -2538,7 +2538,10 @@ match_clause_to_index(PlannerInfo *root,
  *	  (3)  must match the collation of the index, if collation is relevant.
  *
  *	  Our definition of "const" is exceedingly liberal: we allow anything that
- *	  doesn't involve a volatile function or a Var of the index's relation.
+ *	  doesn't involve a volatile function or a Var of the index's relation
+ *	  except for a boolean OR expression input: due to trade-off between
+ *	  expected execution speedup planning complexity, we limit or->saop
+ *	  transformation by obvious cases when an index scan can get a profit.
  *	  In particular, Vars belonging to other relations of the query are
  *	  accepted here, since a clause of that form can be used in a
  *	  parameterized indexscan.  It's the responsibility of higher code levels
-- 
2.39.5

---

From: Alexander Korotkov <[email-masked]>
Date: Fri, 11 Oct 2024 16:20:32 +0300

Hi, Robert!

Thank you so much for your very valuable review.  It took some time to
address all the points.  Hopefully I didn't miss anything.

> forward with this, although it would be nice to get Tom's take if we

Thank you.  And surely, Tom's feedback is very welcome.

> we're doing it like that.

I've integrated comments by Andrei [1], edit them and added some from
myself.  Hopefully that's better now.

> should talk about it. If there isn't, it's better to be consistent.

Yes, actually I think the restriction could be less tight.  It should be
possible to use the same definition of const as
match_opclause_to_indexcol() antd others.  The 0003 patch demonstrates
that.  But it appears that match_join_clauses_to_index() needs changes.
So, generally I think this area needs more research.  This is why, I would
prefer to deal just with Const and Param as 0001 and 0002 currently do, but
consider something like 0003 later.

> I'm not very confident about that conclusion.

Generally, we have the same requirements as match_opclause_to_indexcol()
for the first OR argument.  And we require rest arguments to have same
input collations.  Looks pretty safe for me.

> transformation can produce something that executes more slowly?

I didn't manage to find issues with expressions like WHERE tenthous = 1 OR
tenthous => (very_expensive_computation() + 1), because master also need to
evaluate very_expensive_computation() in order to do index scan or bitmap
scan.  And patch doesn't do anything to sequential scan.  However, I
managed to find an issue with more complex expression.  See the example
below.

create or replace function slowfunc() returns int as $$
begin
  PERFORM pg_sleep(1.0);
  RETURN 1;
end;
$$ stable language plpgsql cost 10000000;
create table t (i int not null, j int not null);
insert into t (select i, i from generate_series(1,10) i,
generate_series(1,1000));
create index t_i_j on t (i, j);

*master*
# explain select count(*) from t where i = 1 and (j = 1 or j = (select
slowfunc()));
                                 QUERY PLAN
-----------------------------------------------------------------------------
 Aggregate  (cost=25031.27..25031.28 rows=1 width=8)
   InitPlan 1
     ->  Result  (cost=0.00..25000.01 rows=1 width=4)
   ->  Index Only Scan using t_i_j on t  (cost=0.29..30.79 rows=190 width=0)
         Index Cond: (i = 1)
         Filter: ((j = 1) OR (j = (InitPlan 1).col1))
(6 rows)

# select count(*) from t where i = 1 and (j = 1 or j = (select slowfunc()));
 count
-------
  1000
(1 row)

Time: 2.923 ms

*patched*

# explain select count(*) from t where i = 1 and (j = 1 or j = (select
slowfunc()));
                                QUERY PLAN
---------------------------------------------------------------------------
 Aggregate  (cost=25012.61..25012.62 rows=1 width=8)
   InitPlan 1
     ->  Result  (cost=0.00..25000.01 rows=1 width=4)
   ->  Index Only Scan using t_i_j on t  (cost=0.29..12.60 rows=1 width=0)
         Index Cond: ((i = 1) AND (j = ANY (ARRAY[1, (InitPlan 1).col1])))
(5 rows)

# select count(*) from t where i = 1 and (j = 1 or j = (select slowfunc()));
 count
-------
  1000
(1 row)

Time: 1006.147 ms (00:01.006)

But, I don't think this is a new issue.  We generally trying to use as many
clauses as possible in index scan.  We don't do any cost analysis about
that.  See the following example.

*master*
# explain analyze select * from t where i = 0 and j = (select slowfunc());
                                                         QUERY PLAN
----------------------------------------------------------------------------------------------------------------------------
 Index Only Scan using t_i_j on t  (cost=25000.29..25004.31 rows=1 width=8)
(actual time=1001.234..1001.235 rows=0 loops=1)
   Index Cond: ((i = 0) AND (j = (InitPlan 1).col1))
   Heap Fetches: 0
   InitPlan 1
     ->  Result  (cost=0.00..25000.01 rows=1 width=4) (actual
time=1001.120..1001.121 rows=1 loops=1)
 Planning Time: 0.240 ms
 Execution Time: 1001.290 ms
(7 rows)

# set enable_indexscan = off;
# set enable_bitmapscan = off;

# explain analyze select * from t where i = 0 and j = (select slowfunc());
                                            QUERY PLAN
---------------------------------------------------------------------------------------------------
 Seq Scan on t  (cost=25000.01..25195.01 rows=1 width=8) (actual
time=0.806..0.807 rows=0 loops=1)
   Filter: ((i = 0) AND (j = (InitPlan 1).col1))
   Rows Removed by Filter: 10000
   InitPlan 1
     ->  Result  (cost=0.00..25000.01 rows=1 width=4) (never executed)
 Planning Time: 0.165 ms
 Execution Time: 0.843 ms
(7 rows)

Thus, I think patch just follows our general logic to push as many clauses
as possible to the index, and doesn't make situation any worse.  There are
cases when this logic cause the slowdown, by I think they are rather rare.
It's required that one of OR argument to be always true, or one of AND
arguments to be always false, while another argument to be expensive to
calculate.  I think this happens very rarely in practice, otherwise we will
hear more (any?) complaints about that from users.  Also, notice we now can
evaluate stable function at planning time for selectivity estimation
disregarding its high cost.

# explain analyze select * from t where i = 0 and j = slowfunc();
                                                         QUERY PLAN
----------------------------------------------------------------------------------------------------------------------------
 Index Only Scan using t_i_j on t  (cost=25000.28..25004.30 rows=1 width=8)
(actual time=1001.220..1001.220 rows=0 loops=1)
   Index Cond: ((i = 0) AND (j = slowfunc()))
   Heap Fetches: 0
 Planning Time: 1000.994 ms
 Execution Time: 1001.284 ms
(5 rows)

Therefore, I don't see a particular problem in the path.  But if you insist
there is a problem, we can restrict patch to work only with external params.

> be that there's no real problem here, but it would be good to verify

I made some experiments in this field.  The sample table contains 64
columns, first 32 of them are indexed.

\o script.sql
\pset tuples_only
select 'create table t (' || string_agg(format('a%s int not null default
0', i), ', ') || ');' from generate_series(1, 64) i;
select 'create index t_a1_to_a50_idx on t (' || string_agg(format('a%s',
i), ', ') || ');' from generate_series(1, 32) i;

First query contains 6400 OR arguments, 100 per each column.

\o q1.sql
select 'explain analyze select * from t where ' || string_agg(format('a%s =
%s', (i - 1) / 100 + 1, i), ' OR ') || ';' from generate_series(1, 6400) i;

Second query also contains 6400 OR arguments, but 200 per each indexed
column.

\o q2.sql
select 'explain analyze select * from t where ' || string_agg(format('a%s =
%s', (i - 1) / 200 + 1, i), ' OR ') || ';' from generate_series(1, 6400) i;

Third query also contains 6400 OR arguments, but 200 per each non-indexed
column.

\o q3.sql
select 'explain analyze select * from t where ' || string_agg(format('a%s =
%s', (i - 1) / 200 + 32, i), ' OR ') || ';' from generate_series(1, 6400) i;

\pset tuples_only off
\o
\i script.sql
\i q1.sql
\i q2.sql
\i q3.sql

The results for planning time are following.

           | master | patch
---------- | ------ | ------
Q1 (run 1) | 14.450 | 12.190
Q1 (run 2) | 13.158 | 11.778
Q1 (run 3) | 11.220 | 12.457
Q2 (run 1) | 15.365 | 13.584
Q2 (run 2) | 15.804 | 14.185
Q2 (run 3) | 16.205 | 13.488
Q3 (run 1) |  9.481 | 12.729
Q3 (run 2) | 10.907 | 13.662
Q3 (run 3) | 11.783 | 12.021

The planning of Q1 and Q2 is somewhat faster with the patch.  I think the
reason for this is shortcut condition in make_bitmap_paths_for_or_group(),
which make us select jointlist without making splitlist.  So, we generally
produce simpler bitmap scan plans.  The Q3 is somewhat slower with the
patch, because it contains no index-matching clauses,
thus group_similar_or_args() appears to be a waste of cycles.  This
generally looks acceptable for me.

Additionally the attached patchset contains changes I promised in response
to Jian He comments, in particular:
1. Fast-path exit form make_bitmap_paths_for_or_group() when joint path is
found and no extra clauses present.
2. Fast-path exit from group_similar_or_args() when not even single clause
is matching index.
3. Fix exit iteration over indexes after first success with
match_index_to_operand() in group_similar_or_args().

Also, in this revision I fixed buggy modification of all_clauses list
with list_delete() in generate_bitmap_or_paths().  Instead, new copy of
list is created.

This is all for now.  The feedback is welcome.

Links.
1.
https://www.postgresql.org/message-id/5d7a66e7-b256-41a7-905a-728c7ae54bce%40gmail.com
2.
https://www.postgresql.org/message-id/CAPpHfdsB2e20Y4jThsonD3%2BsmwwisYWJbJN_mpGjm%3DJiT7OQaQ%40mail.gmail.com
3.
https://www.postgresql.org/message-id/CAPpHfdunXXFT%3Djk%2B3ojXQWo0wZ1Rk%3DrpmAp%2BfjcistCWcH7KqA%40mail.gmail.com

------
Regards,
Alexander Korotkov
Supabase

---

From: Alexander Korotkov <[email-masked]>
Date: Fri, 11 Oct 2024 19:15:54 +0300

> This is all for now.  The feedback is welcome.

Just figured out, I forgot the patchset itself.  Here it goes.

------
Regards,
Alexander Korotkov
Supabase

---

From: Alexander Korotkov <[email-masked]>
Date: Sat, 12 Oct 2024 17:25:45 +0300

On Fri, Oct 11, 2024 at 7:15 PM Alexander Korotkov <[email-masked]> wrote:
>
> On Fri, Oct 11, 2024 at 4:20 PM Alexander Korotkov <[email-masked]> wrote:
>>

I forgot to specify (COSTS OFF) for EXPLAINs in regression tests.  Fixed in v42.

------
Regards,
Alexander Korotkov
Supabase

---

From: Andrei Lepikhov <[email-masked]>
Date: Wed, 16 Oct 2024 11:22:20 +0700

> I forgot to specify (COSTS OFF) for EXPLAINs in regression tests.  Fixed in v42.
I've passed through the patch set.

Let me put aside the v42-0003  patch—it looks debatable, and I need time 
to analyse the change in regression tests caused by this patch.

Comments look much better according to my current language level. Ideas 
with fast exits also look profitable and are worth an additional 
'matched' variable.

So, in general, it is ok. I think only one place with 
inner_other_clauses can be improved. Maybe it will be enough to create 
this list only once,  outside 'foreach(j, groupedArgs)' cycle? Also, the 
comment on the necessity of this operation was unclear to me. See the 
attachment for my modest attempt at improving it.

-- 
regards, Andrei Lepikhov
diff --git a/src/backend/optimizer/path/indxpath.c b/src/backend/optimizer/path/indxpath.c
index 5c8b64a5b1..0615c6d4de 100644
--- a/src/backend/optimizer/path/indxpath.c
+++ b/src/backend/optimizer/path/indxpath.c
@@ -1581,6 +1581,7 @@ generate_bitmap_or_paths(PlannerInfo *root, RelOptInfo *rel,
 		Path	   *bitmapqual;
 		ListCell   *j;
 		List	   *groupedArgs;
+		List	   *inner_other_clauses = NIL;
 
 		/* Ignore RestrictInfos that aren't ORs */
 		if (!restriction_is_or_clause(rinfo))
@@ -1597,6 +1598,19 @@ generate_bitmap_or_paths(PlannerInfo *root, RelOptInfo *rel,
 		 * because those RestrictInfos might match to the index as a whole.
 		 */
 		groupedArgs = group_similar_or_args(root, rel, rinfo);
+
+		if (groupedArgs != ((BoolExpr *) rinfo->orclause)->args)
+			/*
+			 * Some parts of the rinfo were grouped. In this case we have a set
+			 * of sub-rinfos that together is an exact duplicate of rinfo.
+			 * In this case we need to remove the rinfo from other clauses.
+			 * match_clauses_to_index detects duplicated iclause by comparing
+			 * pointers to original rinfos that will be different. So, we must
+			 * delete rinfo to avoid de-facto duplicated clauses in the index
+			 * clauses list.
+			 */
+			inner_other_clauses = list_delete(list_copy(all_clauses), rinfo);
+
 		foreach(j, groupedArgs)
 		{
 			Node	   *orarg = (Node *) lfirst(j);
@@ -1620,20 +1634,14 @@ generate_bitmap_or_paths(PlannerInfo *root, RelOptInfo *rel,
 			else if (restriction_is_or_clause(castNode(RestrictInfo, orarg)))
 			{
 				RestrictInfo *ri = castNode(RestrictInfo, orarg);
-				List	   *inner_other_clauses;
 
 				/*
 				 * Generate bitmap paths for the group of similar OR-clause
-				 * arguments.  In this case we need to immediately remove the
-				 * rinfo from other clauses.  This is because rinfo can be
-				 * transformed during index matching.  So, we might be unable
-				 * to remove that later.
+				 * arguments.
 				 */
-				inner_other_clauses = list_delete(list_copy(all_clauses), rinfo);
 				indlist = make_bitmap_paths_for_or_group(root,
 														 rel, ri,
 														 inner_other_clauses);
-				list_free(inner_other_clauses);
 
 				if (indlist == NIL)
 				{
@@ -1676,6 +1684,8 @@ generate_bitmap_or_paths(PlannerInfo *root, RelOptInfo *rel,
 			pathlist = lappend(pathlist, bitmapqual);
 		}
 
+		list_free(inner_other_clauses);
+
 		/*
 		 * If we have a match for every arm, then turn them into a
 		 * BitmapOrPath, and add to result list.

---

From: Alexander Korotkov <[email-masked]>
Date: Wed, 16 Oct 2024 23:39:01 +0300

> to analyse the change in regression tests caused by this patch.

Yes, 0003 patch is for illustration purposes for now.  I will not keep
rebasing it.  We can pick it later when main patches are committed.

> attachment for my modest attempt at improving it.

Thank you, I've integrated your patch with minor edits from me.

------
Regards,
Alexander Korotkov
Supabase

---

From: Andrei Lepikhov <[email-masked]>
Date: Thu, 17 Oct 2024 09:09:29 +0700

> rebasing it.  We can pick it later when main patches are committed.
Got it. I will save it into the TODO list.
> Thank you, I've integrated your patch with minor edits from me.
Thanks, I'm not sure about necessity to check NIL value of a list 
(list_free also do it), but I'm ok with the edits.

-- 
regards, Andrei Lepikhov

---

From: jian he <[email-masked]>
Date: Mon, 28 Oct 2024 15:19:00 +0800

* NOTE:  returns NULL if clause is an OR or AND clause; it is the
 * responsibility of higher-level routines to cope with those.
 */
static IndexClause *
match_clause_to_indexcol(PlannerInfo *root,
                         RestrictInfo *rinfo,
                         int indexcol,
                         IndexOptInfo *index)

the above comments need a slight change.

EXPLAIN (COSTS OFF, settings) SELECT * FROM tenk2 WHERE  (thousand = 1
OR thousand = 3);
                        QUERY PLAN
-----------------------------------------------------------
 Bitmap Heap Scan on tenk2
   Recheck Cond: ((thousand = 1) OR (thousand = 3))
   ->  Bitmap Index Scan on tenk2_thous_tenthous
         Index Cond: (thousand = ANY ('{1,3}'::integer[]))

EXPLAIN (COSTS OFF, settings) SELECT * FROM tenk2 WHERE  (thousand in (1,3));
                        QUERY PLAN
-----------------------------------------------------------
 Bitmap Heap Scan on tenk2
   Recheck Cond: (thousand = ANY ('{1,3}'::integer[]))
   ->  Bitmap Index Scan on tenk2_thous_tenthous
         Index Cond: (thousand = ANY ('{1,3}'::integer[]))

tenk2 index:
Indexes:
    "tenk2_thous_tenthous" btree (thousand, tenthous)

Looking at the above cases, I found out the "Recheck Cond" is
different from "Index Cond".
I wonder why there is a difference, or if they should be the same.
then i come to:
match_orclause_to_indexcol

    /*
     * Finally, build an IndexClause based on the SAOP node. Use
     * make_simple_restrictinfo() to get RestrictInfo with clean selectivity
     * estimations because it may differ from the estimation made for an OR
     * clause. Although it is not a lossy expression, keep the old version of
     * rinfo in iclause->rinfo to detect duplicates and recheck the original
     * clause.
     */
    iclause = makeNode(IndexClause);
    iclause->rinfo = rinfo;
    iclause->indexquals = list_make1(make_simple_restrictinfo(root,
                                                              &saopexpr->xpr));
    iclause->lossy = false;
    iclause->indexcol = indexcol;
    iclause->indexcols = NIL;

looking at create_bitmap_scan_plan.
I think "iclause->rinfo" itself won't be able to detect duplicates.
since the upper code would mostly use "iclause->indexquals" for comparison?

typedef struct IndexClause comments says:
"
 * indexquals is a list of RestrictInfos for the directly-usable index
 * conditions associated with this IndexClause.  In the simplest case
 * it's a one-element list whose member is iclause->rinfo.  Otherwise,
 * it contains one or more directly-usable indexqual conditions extracted
 * from the given clause.  The 'lossy' flag indicates whether the
 * indexquals are semantically equivalent to the original clause, or
 * represent a weaker condition.
"
should lossy be iclause->lossy be true at the end of match_orclause_to_indexcol?
since it meets the comment condition: "semantically equivalent to the
original clause"
or is the above comment slightly wrong?

in match_orclause_to_indexcol
i changed from
iclause->rinfo = rinfo;
to
 iclause->rinfo = make_simple_restrictinfo(root,
                                                &saopexpr->xpr);

as expected. now the "Recheck Cond" is same as "Index Cond"
   Recheck Cond: (thousand = ANY ('{1,3}'::integer[]))
   ->  Bitmap Index Scan on tenk2_thous_tenthous
         Index Cond: (thousand = ANY ('{1,3}'::integer[]))

I am not sure of the implication of this change.

---

From: Alena Rybakina <[email-masked]>
Date: Mon, 28 Oct 2024 19:55:35 +0300

Hi, Jian! Thank you for your work on this topic!

> EXPLAIN (COSTS OFF, settings) SELECT * FROM tenk2 WHERE  (thousand = 1
I may be wrong, but the original idea was to double-check the result 
with the original expression.

But I'm willing to agree with you. I think we should add transformed 
rinfo variable through add_predicate_to_index_quals function. I attached 
the diff file to the letter.

diff --git a/src/backend/optimizer/path/indxpath.c 
b/src/backend/optimizer/path/indxpath.c
index 3da7ea8ed57..c68ac7008e6 100644
--- a/src/backend/optimizer/path/indxpath.c
+++ b/src/backend/optimizer/path/indxpath.c
@@ -3463,10 +3463,11 @@ match_orclause_to_indexcol(PlannerInfo *root,
       * rinfo in iclause->rinfo to detect duplicates and recheck the 
original
       * clause.
       */
+    RestrictInfo *rinfo_new = make_simple_restrictinfo(root,
+ &saopexpr->xpr);
      iclause = makeNode(IndexClause);
-    iclause->rinfo = rinfo;
-    iclause->indexquals = list_make1(make_simple_restrictinfo(root,
- &saopexpr->xpr));
+    iclause->rinfo = rinfo_new;
+    iclause->indexquals = add_predicate_to_index_quals(index, 
list_make1(rinfo_new));
      iclause->lossy = false;
      iclause->indexcol = indexcol;
      iclause->indexcols = NIL;

I figured out comments that you mentioned and found some addition 
explanation.

As I understand it, this processing is related to ensuring that the 
selectivity of the index is assessed correctly and that there is no 
underestimation, which can lead to the selection of a partial index in 
the plan. See comment for the add_predicate_to_index_quals function:

* ANDing the index predicate with the explicitly given indexquals produces
  * a more accurate idea of the index's selectivity. *However, we need to be
  * careful not to insert redundant clauses, because 
clauselist_selectivity()
  * is easily fooled into computing a too-low selectivity estimate*.  Our
  * approach is to add only the predicate clause(s) that cannot be proven to
  * be implied by the given indexquals.  This successfully handles cases 
such
  * as a qual "x = 42" used with a partial index "WHERE x >= 40 AND x < 50".
  * There are many other cases where we won't detect redundancy, leading 
to a
  * too-low selectivity estimate, which will bias the system in favor of 
using
  * partial indexes where possible.  That is not necessarily bad though.
  *
  * *Note that indexQuals contains RestrictInfo nodes while the indpred
  * does not, so the output list will be mixed.  This is OK for both
  * predicate_implied_by() and clauselist_selectivity()*, but might be
  * problematic if the result were passed to other things.
  */

In those comments that you mentioned, it was written that this problem 
of expression redundancy is checked using the predicate_implied_by 
function, note that it is called there.

* In some situations (particularly with OR'd index conditions) we may * 
have scan_clauses that are not equal to, but are logically implied by, * 
the index quals; so we also try a predicate_implied_by() check to see * 
if we can discard quals that way. (predicate_implied_by assumes its * 
first input contains only immutable functions, so we have to check * that.)

I also figured out more information about loosy variable. First of all, 
I tried changing the value of the variable and did not notice any 
difference in regression tests. As I understood, our transformation is 
completely equivalent, so loosy should be true. But I don't think they 
are needed since our expressions are equivalent. I thought for a long 
time about an example where this could be a mistake and didn’t come up 
with any of them.

-- 
Regards,
Alena Rybakina
Postgres Professional
diff --git a/src/backend/optimizer/path/indxpath.c b/src/backend/optimizer/path/indxpath.c
index 3da7ea8ed57..e72a4fb15dd 100644
--- a/src/backend/optimizer/path/indxpath.c
+++ b/src/backend/optimizer/path/indxpath.c
@@ -3242,6 +3242,7 @@ match_orclause_to_indexcol(PlannerInfo *root,
 	Oid			inputcollid = InvalidOid;
 	bool		firstTime = true;
 	bool		have_param = false;
+	RestrictInfo *rinfo_new;
 
 	Assert(IsA(orclause, BoolExpr));
 	Assert(orclause->boolop == OR_EXPR);
@@ -3463,11 +3464,12 @@ match_orclause_to_indexcol(PlannerInfo *root,
 	 * rinfo in iclause->rinfo to detect duplicates and recheck the original
 	 * clause.
 	 */
+	rinfo_new = make_simple_restrictinfo(root,
+                                                &saopexpr->xpr);
 	iclause = makeNode(IndexClause);
-	iclause->rinfo = rinfo;
-	iclause->indexquals = list_make1(make_simple_restrictinfo(root,
-															  &saopexpr->xpr));
-	iclause->lossy = false;
+	iclause->rinfo = rinfo_new;
+	iclause->indexquals = add_predicate_to_index_quals(index, list_make1(rinfo_new));
+	iclause->lossy = true;
 	iclause->indexcol = indexcol;
 	iclause->indexcols = NIL;
 	return iclause;
diff --git a/src/test/regress/expected/create_index.out b/src/test/regress/expected/create_index.out
index b003492c5c8..3c46484d642 100644
--- a/src/test/regress/expected/create_index.out
+++ b/src/test/regress/expected/create_index.out
@@ -1878,10 +1878,10 @@ SELECT * FROM tenk1
 EXPLAIN (COSTS OFF)
 SELECT * FROM tenk1
   WHERE thousand = 42 AND (tenthous = 1 OR tenthous = 3 OR tenthous = 42 OR tenthous IS NULL);
-                                                                QUERY PLAN                                                                 
--------------------------------------------------------------------------------------------------------------------------------------------
+                                                          QUERY PLAN                                                          
+------------------------------------------------------------------------------------------------------------------------------
  Bitmap Heap Scan on tenk1
-   Recheck Cond: (((thousand = 42) AND (tenthous IS NULL)) OR ((thousand = 42) AND ((tenthous = 1) OR (tenthous = 3) OR (tenthous = 42))))
+   Recheck Cond: (((thousand = 42) AND (tenthous IS NULL)) OR ((thousand = 42) AND (tenthous = ANY ('{1,3,42}'::integer[]))))
    Filter: ((tenthous = 1) OR (tenthous = 3) OR (tenthous = 42) OR (tenthous IS NULL))
    ->  BitmapOr
          ->  Bitmap Index Scan on tenk1_thous_tenthous
@@ -1917,10 +1917,10 @@ SELECT * FROM tenk1
 EXPLAIN (COSTS OFF)
 SELECT * FROM tenk1
   WHERE thousand = 42 AND (tenthous = 1::int2 OR tenthous = 3::int8 OR tenthous = 42::int8);
-                                                                     QUERY PLAN                                                                      
------------------------------------------------------------------------------------------------------------------------------------------------------
+                                                            QUERY PLAN                                                             
+-----------------------------------------------------------------------------------------------------------------------------------
  Bitmap Heap Scan on tenk1
-   Recheck Cond: (((thousand = 42) AND ((tenthous = '3'::bigint) OR (tenthous = '42'::bigint))) OR ((thousand = 42) AND (tenthous = '1'::smallint)))
+   Recheck Cond: (((thousand = 42) AND (tenthous = ANY ('{3,42}'::bigint[]))) OR ((thousand = 42) AND (tenthous = '1'::smallint)))
    Filter: ((tenthous = '1'::smallint) OR (tenthous = '3'::bigint) OR (tenthous = '42'::bigint))
    ->  BitmapOr
          ->  Bitmap Index Scan on tenk1_thous_tenthous
@@ -1932,11 +1932,11 @@ SELECT * FROM tenk1
 EXPLAIN (COSTS OFF)
 SELECT count(*) FROM tenk1
   WHERE hundred = 42 AND (thousand = 42 OR thousand = 99);
-                                   QUERY PLAN                                    
----------------------------------------------------------------------------------
+                                     QUERY PLAN                                     
+------------------------------------------------------------------------------------
  Aggregate
    ->  Bitmap Heap Scan on tenk1
-         Recheck Cond: ((hundred = 42) AND ((thousand = 42) OR (thousand = 99)))
+         Recheck Cond: ((hundred = 42) AND (thousand = ANY ('{42,99}'::integer[])))
          ->  BitmapAnd
                ->  Bitmap Index Scan on tenk1_hundred
                      Index Cond: (hundred = 42)
@@ -1991,11 +1991,11 @@ SELECT * FROM tenk1
 EXPLAIN (COSTS OFF)
 SELECT count(*) FROM tenk1
   WHERE hundred = 42 AND (thousand = 42 OR thousand = 99);
-                                   QUERY PLAN                                    
----------------------------------------------------------------------------------
+                                     QUERY PLAN                                     
+------------------------------------------------------------------------------------
  Aggregate
    ->  Bitmap Heap Scan on tenk1
-         Recheck Cond: ((hundred = 42) AND ((thousand = 42) OR (thousand = 99)))
+         Recheck Cond: ((hundred = 42) AND (thousand = ANY ('{42,99}'::integer[])))
          ->  BitmapAnd
                ->  Bitmap Index Scan on tenk1_hundred
                      Index Cond: (hundred = 42)
@@ -2013,11 +2013,11 @@ SELECT count(*) FROM tenk1
 EXPLAIN (COSTS OFF)
 SELECT count(*) FROM tenk1
   WHERE hundred = 42 AND (thousand < 42 OR thousand < 99 OR 43 > thousand OR 42 > thousand);
-                                                      QUERY PLAN                                                       
------------------------------------------------------------------------------------------------------------------------
+                                        QUERY PLAN                                        
+------------------------------------------------------------------------------------------
  Aggregate
    ->  Bitmap Heap Scan on tenk1
-         Recheck Cond: ((hundred = 42) AND ((thousand < 42) OR (thousand < 99) OR (43 > thousand) OR (42 > thousand)))
+         Recheck Cond: ((hundred = 42) AND (thousand < ANY ('{42,99,43,42}'::integer[])))
          ->  BitmapAnd
                ->  Bitmap Index Scan on tenk1_hundred
                      Index Cond: (hundred = 42)
@@ -2035,11 +2035,11 @@ SELECT count(*) FROM tenk1
 EXPLAIN (COSTS OFF)
 SELECT count(*) FROM tenk1
   WHERE thousand = 42 AND (tenthous = 1 OR tenthous = 3) OR thousand = 41;
-                                             QUERY PLAN                                              
------------------------------------------------------------------------------------------------------
+                                               QUERY PLAN                                               
+--------------------------------------------------------------------------------------------------------
  Aggregate
    ->  Bitmap Heap Scan on tenk1
-         Recheck Cond: (((thousand = 42) AND ((tenthous = 1) OR (tenthous = 3))) OR (thousand = 41))
+         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[])))
@@ -2057,11 +2057,11 @@ SELECT count(*) FROM tenk1
 EXPLAIN (COSTS OFF)
 SELECT count(*) FROM tenk1
   WHERE hundred = 42 AND (thousand = 42 OR thousand = 99 OR tenthous < 2) OR thousand = 41;
-                                                        QUERY PLAN                                                        
---------------------------------------------------------------------------------------------------------------------------
+                                                         QUERY PLAN                                                          
+-----------------------------------------------------------------------------------------------------------------------------
  Aggregate
    ->  Bitmap Heap Scan on tenk1
-         Recheck Cond: (((hundred = 42) AND (((thousand = 42) OR (thousand = 99)) OR (tenthous < 2))) OR (thousand = 41))
+         Recheck Cond: (((hundred = 42) AND ((thousand = ANY ('{42,99}'::integer[])) OR (tenthous < 2))) OR (thousand = 41))
          Filter: (((hundred = 42) AND ((thousand = 42) OR (thousand = 99) OR (tenthous < 2))) OR (thousand = 41))
          ->  BitmapOr
                ->  BitmapAnd
@@ -2086,11 +2086,11 @@ SELECT count(*) FROM tenk1
 EXPLAIN (COSTS OFF)
 SELECT count(*) FROM tenk1
   WHERE hundred = 42 AND (thousand = 42 OR thousand = 41 OR thousand = 99 AND tenthous = 2);
-                                                        QUERY PLAN                                                         
----------------------------------------------------------------------------------------------------------------------------
+                                                          QUERY PLAN                                                          
+------------------------------------------------------------------------------------------------------------------------------
  Aggregate
    ->  Bitmap Heap Scan on tenk1
-         Recheck Cond: ((hundred = 42) AND (((thousand = 99) AND (tenthous = 2)) OR ((thousand = 42) OR (thousand = 41))))
+         Recheck Cond: ((hundred = 42) AND (((thousand = 99) AND (tenthous = 2)) OR (thousand = ANY ('{42,41}'::integer[]))))
          Filter: ((thousand = 42) OR (thousand = 41) OR ((thousand = 99) AND (tenthous = 2)))
          ->  BitmapAnd
                ->  Bitmap Index Scan on tenk1_hundred
diff --git a/src/test/regress/expected/join.out b/src/test/regress/expected/join.out
index ebf2e3f851a..ea83578ccf1 100644
--- a/src/test/regress/expected/join.out
+++ b/src/test/regress/expected/join.out
@@ -4348,7 +4348,7 @@ select * from tenk1 a join tenk1 b on
                      Index Cond: (unique1 = 2)
    ->  Materialize
          ->  Bitmap Heap Scan on tenk1 a
-               Recheck Cond: (((unique2 = 3) OR (unique2 = 7)) OR (unique1 = 1))
+               Recheck Cond: ((unique2 = ANY ('{3,7}'::integer[])) OR (unique1 = 1))
                Filter: ((unique1 = 1) OR (unique2 = 3) OR (unique2 = 7))
                ->  BitmapOr
                      ->  Bitmap Index Scan on tenk1_unique2
@@ -4374,7 +4374,7 @@ select * from tenk1 a join tenk1 b on
                      Index Cond: (unique1 = 2)
    ->  Materialize
          ->  Bitmap Heap Scan on tenk1 a
-               Recheck Cond: (((unique2 = 3) OR (unique2 = 7)) OR (unique1 = 1))
+               Recheck Cond: ((unique2 = ANY ('{3,7}'::integer[])) OR (unique1 = 1))
                Filter: ((unique1 = 1) OR (unique2 = 3) OR (unique2 = 7))
                ->  BitmapOr
                      ->  Bitmap Index Scan on tenk1_unique2
@@ -4394,7 +4394,7 @@ select * from tenk1 a join tenk1 b on
    ->  Seq Scan on tenk1 b
    ->  Materialize
          ->  Bitmap Heap Scan on tenk1 a
-               Recheck Cond: (((unique2 = 3) OR (unique2 = 7)) OR ((unique1 = 3) OR (unique1 = 1)) OR (unique1 < 20))
+               Recheck Cond: ((unique2 = ANY ('{3,7}'::integer[])) OR (unique1 = ANY ('{3,1}'::integer[])) OR (unique1 < 20))
                Filter: ((unique1 < 20) OR (unique1 = 3) OR (unique1 = 1) OR (unique2 = 3) OR (unique2 = 7))
                ->  BitmapOr
                      ->  Bitmap Index Scan on tenk1_unique2

---

From: Alexander Korotkov <[email-masked]>
Date: Fri, 15 Nov 2024 15:12:49 +0200

Hi, Jian!

original
&saopexpr->xpr));
> I am not sure of the implication of this change.

As comment says IndexClause.rinfo must be original restriction or join
clause.

typedef struct IndexClause
{
    pg_node_attr(no_copy_equal, no_read, no_query_jumble)

    NodeTag     type;
    struct RestrictInfo *rinfo; /* original restriction or join clause */

I don't see any reason why should we violate that.  Note that there are
already cases when "Recheck Cond" doesn't match "Index Cond".  For instance:

# explain select * from t where 100000 > i;
                                 QUERY PLAN
-----------------------------------------------------------------------------
 Bitmap Heap Scan on t  (cost=1860.66..7524.75 rows=99127 width=4)
   Recheck Cond: (100000 > i)
   ->  Bitmap Index Scan on t_i_idx  (cost=0.00..1835.88 rows=99127 width=0)
         Index Cond: (i < 100000)
(4 rows)

Thus, this type of mismatch seems normal to me.

IndexClause.lossy should be false in our case (as it is).  Lossy
transformation happens when there are cases of false positives in the
transformed clause.  The comment gives an example of transformation  "x
LIKE 'foo%bar'" into "x >= 'foo' AND x < 'fop'".  In this case, 'fooqux'
would be case of false positive matching transformed clause but not
matching the original clause.  In our case, original and transformed
clauses are equivalent.  Therefore our transformation isn't lossy.

------
Regards,
Alexander Korotkov
Supabase

---

From: Alexander Korotkov <[email-masked]>
Date: Fri, 15 Nov 2024 15:27:43 +0200

Hi, Alena!

On Mon, Oct 28, 2024 at 6:55 PM Alena Rybakina
<[email-masked]> wrote:
> I may be wrong, but the original idea was to double-check the result with the original expression.
>
> But I'm willing to agree with you. I think we should add transformed rinfo variable through add_predicate_to_index_quals function. I attached the diff file to the letter.
>

As I stated in [1], I don't think we should pass transformed clause to
IndexClause.rinfo while comment explicitly says us to pass original
rinfo there.

> I figured out comments that you mentioned and found some addition explanation.
>
> As I understand it, this processing is related to ensuring that the selectivity of the index is assessed correctly and that there is no underestimation, which can lead to the selection of a partial index in the plan. See comment for the add_predicate_to_index_quals function:
>
>  * a more accurate idea of the index's selectivity.  However, we need to be
>  * careful not to insert redundant clauses, because clauselist_selectivity()
>  * is easily fooled into computing a too-low selectivity estimate.  Our
>  * be implied by the given indexquals.  This successfully handles cases such
>  * There are many other cases where we won't detect redundancy, leading to a
>  * too-low selectivity estimate, which will bias the system in favor of using
>  * Note that indexQuals contains RestrictInfo nodes while the indpred
>  * predicate_implied_by() and clauselist_selectivity(), but might be
> In those comments that you mentioned, it was written that this problem of expression redundancy is checked using the predicate_implied_by function, note that it is called there.
>
> * In some situations (particularly with OR'd index conditions) we may * have scan_clauses that are not equal to, but are logically implied by, * the index quals; so we also try a predicate_implied_by() check to see * if we can discard quals that way. (predicate_implied_by assumes its * first input contains only immutable functions, so we have to check * that.)

As the first line of header comment of add_predicate_to_index_quals()
says it adds partial index predicate to the quals list.  I don't see
why should we use that in match_orclause_to_indexcol(), because this
function is only responsible to matching rinfo to particular index
column.  Matching of partial index predicate is handled elsewhere.
Also check there is get_index_clause_from_support(), which is fetch
transformed clause from a support function.  And it doesn't have to
fiddle with add_predicate_to_index_quals().

> I also figured out more information about loosy variable. First of all, I tried changing the value of the variable and did not notice any difference in regression tests. As I understood, our transformation is completely equivalent, so loosy should be true. But I don't think they are needed since our expressions are equivalent. I thought for a long time about an example where this could be a mistake and didn’t come up with any of them.

Yes, our transformation isn't lossy, thus IndexClause.lossy should be unset.

Links
1. https://www.postgresql.org/message-id/CAPpHfdvjtEWqjVcPd3-JQw8yCoppMXjK8kHnvinxBXGMZt-M_g%40mail.gmail.com

------
Regards,
Alexander Korotkov
Supabase

---

From: Alexander Korotkov <[email-masked]>
Date: Mon, 18 Nov 2024 01:19:49 +0200

> Yes, our transformation isn't lossy, thus IndexClause.lossy should be unset.

Here is the next revision of this patch.  No material changes,
adjustments for comments and commit message.

------
Regards,
Alexander Korotkov
Supabase

---

From: Andrei Lepikhov <[email-masked]>
Date: Wed, 20 Nov 2024 13:19:58 +0700

> adjustments for comments and commit message.
I have passed through the code and found no issues. Maybe only phrase:
"eval_const_expressions() will be simplified if there is more than one."
which is used in both patches: here, the 'will' may be removed, as for me.

Also, I re-read the thread, and as AFAICS, no other issues remain. So, I 
think it would be OK to move the status of this feature to 'ready for 
committer'.

-- 
regards, Andrei Lepikhov

---

From: Alexander Korotkov <[email-masked]>
Date: Thu, 21 Nov 2024 08:34:15 +0200

> which is used in both patches: here, the 'will' may be removed, as for me.

Exactly same wording is used in match_index_to_operand().  So, I think
we can save this.

> think it would be OK to move the status of this feature to 'ready for

Yes, I also re-read the thread.  One thing caught my eye is that
Robert didn't answer my point that as we generally don't care about
lazy parameters evaluation while pushing quals as index conds then we
don't have to do this in this patch.  I think there were quite amount
of time to express disagreement if any.  If even this question will
arise, that's well isolated issue which could be nailed down later.

I'm going to push this if no objections.

Links.
1. https://www.postgresql.org/message-id/CAPpHfdt8kowRDUkmOnO7_WJJQ1uk%2BO379JiZCk_9_Pt5AQ4%2B0w%40mail.gmail.com

------
Regards,
Alexander Korotkov
Supabase

---

From: jian he <[email-masked]>
Date: Mon, 25 Nov 2024 10:59:20 +0800

looking at it again. in match_orclause_to_indexcol

        /* Only the operator returning a boolean suits the transformation. */
        if (get_op_rettype(opno) != BOOLOID)
            break;

can change to

        if (subClause->opresulttype != BOOLOID)
            break;

for saving some cycles?

---

From: Richard Guo <[email-masked]>
Date: Mon, 25 Nov 2024 15:27:57 +0900

> I'm going to push this if no objections.

Here is an Assert failure in match_orclause_to_indexcol.

create table t (a int);
create index on t (a);

# explain select * from t where a <= 0 or a <= 1;
server closed the connection unexpectedly

The assertion is that the collected Const values cannot be NULL and
cannot be zero.  The latter part about zero values doesn't make sense
to me.  Why can't the values be zero?

Thanks
Richard

---

From: Alexander Korotkov <[email-masked]>
Date: Mon, 25 Nov 2024 09:08:41 +0200

Hi, Richard!

>     Assert(!value->constisnull && value->constvalue);

Yes, this is a dumb assertion.  Removed.

------
Regards,
Alexander Korotkov
Supabase

---

From: Andrei Lepikhov <[email-masked]>
Date: Mon, 25 Nov 2024 14:21:11 +0700

>> to me.  Why can't the values be zero?
I guess, this code came from the first raw prototypes designed with the 
erroneous assumption that they would check a NULL pointer.
Anyway, thanks for looking into it!

Thank you!

-- 
regards, Andrei Lepikhov

---

From: Alexander Lakhin <[email-masked]>
Date: Thu, 28 Nov 2024 21:00:01 +0300

Hello Alexander,

> I'm going to push this if no objections.

Please look at the following query, which triggers an error after ae4569161:
SET random_page_cost = 1;
CREATE TABLE tbl(u UUID);
CREATE INDEX idx ON tbl USING HASH (u);
SELECT COUNT(*) FROM tbl WHERE u = '00000000000000000000000000000000' OR
   u = '11111111111111111111111111111111';

ERROR:  XX000: ScalarArrayOpExpr index qual found where not allowed
LOCATION:  ExecIndexBuildScanKeys, nodeIndexscan.c:1625

Best regards,
Alexander

---

From: Alena Rybakina <[email-masked]>
Date: Thu, 28 Nov 2024 22:03:36 +0300

Hi! Thank you for the case.

> LOCATION:  ExecIndexBuildScanKeys, nodeIndexscan.c:1625
I found out what the problem is index scan method was not generated. We 
need to check this during OR clauses for SAOP transformation.

There is a patch to fix this problem.

-- 
Regards,
Alena Rybakina
Postgres Professional
diff --git a/src/backend/optimizer/path/indxpath.c b/src/backend/optimizer/path/indxpath.c
index d827fc9f4d9..61110db65dd 100644
--- a/src/backend/optimizer/path/indxpath.c
+++ b/src/backend/optimizer/path/indxpath.c
@@ -3303,6 +3303,10 @@ match_orclause_to_indexcol(PlannerInfo *root,
 		if (get_op_rettype(opno) != BOOLOID)
 			break;
 
+		/* Ignore index if it doesn't support index scans */
+		if(!index->amsearcharray)
+			break;
+
 		/*
 		 * Check for clauses of the form: (indexkey operator constant) or
 		 * (constant operator indexkey).  Determine indexkey side first, check
diff --git a/src/test/regress/sql/create_index.sql b/src/test/regress/sql/create_index.sql
index ddd0d9ad396..0e6529f3f3d 100644
--- a/src/test/regress/sql/create_index.sql
+++ b/src/test/regress/sql/create_index.sql
@@ -372,6 +372,11 @@ CREATE INDEX hash_tuplesort_idx ON tenk1 USING hash (stringu1 name_ops) WITH (fi
 EXPLAIN (COSTS OFF)
 SELECT count(*) FROM tenk1 WHERE stringu1 = 'TVAAAA';
 SELECT count(*) FROM tenk1 WHERE stringu1 = 'TVAAAA';
+-- Transform OR-clauses to SAOP's shouldn't be chosen
+SET random_page_cost = 1;
+EXPLAIN (COSTS OFF)
+SELECT COUNT(*) FROM tenk1 WHERE stringu1 = 'TVAAAA' OR  stringu1 = 'TVAAAB';
+RESET random_page_cost;
 DROP INDEX hash_tuplesort_idx;
 RESET maintenance_work_mem;

---

From: Alena Rybakina <[email-masked]>
Date: Thu, 28 Nov 2024 22:08:51 +0300

Sorry, I was in a hurry and forgot to add the test result. I updated the 
patch

On 28.11.2024 22:03, Alena Rybakina wrote:
> I found out what the problem is index scan method was not generated. 
> We need to check this during OR clauses for SAOP transformation.
>
 
+		/* Ignore index if it doesn't support index scans */
+		if(!index->amsearcharray)
+			break;
+
 		/*
 		 * Check for clauses of the form: (indexkey operator constant) or
 		 * (constant operator indexkey).  Determine indexkey side first, check
diff --git a/src/test/regress/expected/create_index.out b/src/test/regress/expected/create_index.out
index 1b0a5f0e9e1..ef8bbf4748c 100644
--- a/src/test/regress/expected/create_index.out
+++ b/src/test/regress/expected/create_index.out
@@ -1233,6 +1233,23 @@ SELECT count(*) FROM tenk1 WHERE stringu1 = 'TVAAAA';
     14
 (1 row)
 
+-- Transform OR-clauses to SAOP's shouldn't be chosen
+SET random_page_cost = 1;
+EXPLAIN (COSTS OFF)
+SELECT COUNT(*) FROM tenk1 WHERE stringu1 = 'TVAAAA' OR  stringu1 = 'TVAAAB';
+                                     QUERY PLAN                                     
+------------------------------------------------------------------------------------
+ Aggregate
+   ->  Bitmap Heap Scan on tenk1
+         Recheck Cond: ((stringu1 = 'TVAAAA'::name) OR (stringu1 = 'TVAAAB'::name))
+         ->  BitmapOr
+               ->  Bitmap Index Scan on hash_tuplesort_idx
+                     Index Cond: (stringu1 = 'TVAAAA'::name)
+               ->  Bitmap Index Scan on hash_tuplesort_idx
+                     Index Cond: (stringu1 = 'TVAAAB'::name)
+(8 rows)
+
+RESET random_page_cost;
 DROP INDEX hash_tuplesort_idx;
 RESET maintenance_work_mem;
 --
diff --git a/src/test/regress/sql/create_index.sql b/src/test/regress/sql/create_index.sql
index ddd0d9ad396..0e6529f3f3d 100644
--- a/src/test/regress/sql/create_index.sql
+++ b/src/test/regress/sql/create_index.sql
@@ -372,6 +372,11 @@ CREATE INDEX hash_tuplesort_idx ON tenk1 USING hash (stringu1 name_ops) WITH (fi
 EXPLAIN (COSTS OFF)
 SELECT count(*) FROM tenk1 WHERE stringu1 = 'TVAAAA';
 SELECT count(*) FROM tenk1 WHERE stringu1 = 'TVAAAA';
+-- Transform OR-clauses to SAOP's shouldn't be chosen
+SET random_page_cost = 1;
+EXPLAIN (COSTS OFF)
+SELECT COUNT(*) FROM tenk1 WHERE stringu1 = 'TVAAAA' OR  stringu1 = 'TVAAAB';
+RESET random_page_cost;
 DROP INDEX hash_tuplesort_idx;
 RESET maintenance_work_mem;

---

From: Ranier Vilela <[email-masked]>
Date: Thu, 28 Nov 2024 16:28:04 -0300

> There is a patch to fix this problem.
Hi.
Thanks for the quick fix.

But I wonder if it is not possible to avoid all if the index is useless?
Maybe moving your fix to the beginning of the function?

diff --git a/src/backend/optimizer/path/indxpath.c
b/src/backend/optimizer/path/indxpath.c
index d827fc9f4d..5ea0b27d01 100644
--- a/src/backend/optimizer/path/indxpath.c
+++ b/src/backend/optimizer/path/indxpath.c
@@ -3248,6 +3248,10 @@ match_orclause_to_indexcol(PlannerInfo *root,
  Assert(IsA(orclause, BoolExpr));
  Assert(orclause->boolop == OR_EXPR);

+ /* Ignore index if it doesn't support index scans */
+ if(!index->amsearcharray)
+ return NULL;
+
  /*
  * Try to convert a list of OR-clauses to a single SAOP expression. Each
  * OR entry must be in the form: (indexkey operator constant) or (constant

The test bug:
EXPLAIN SELECT COUNT(*) FROM tbl WHERE u =
'00000000000000000000000000000000' OR u =
'11111111111111111111111111111111';
                                                            QUERY PLAN
----------------------------------------------------------------------------------------------------------------------------------
 Aggregate  (cost=12.46..12.47 rows=1 width=8)
   ->  Bitmap Heap Scan on tbl  (cost=2.14..12.41 rows=18 width=0)
         Recheck Cond: ((u = '00000000-0000-0000-0000-000000000000'::uuid)
OR (u = '11111111-1111-1111-1111-111111111111'::uuid))
         ->  BitmapOr  (cost=2.14..2.14 rows=18 width=0)
               ->  Bitmap Index Scan on idx  (cost=0.00..1.07 rows=9
width=0)
                     Index Cond: (u =
'00000000-0000-0000-0000-000000000000'::uuid)
               ->  Bitmap Index Scan on idx  (cost=0.00..1.07 rows=9
width=0)
                     Index Cond: (u =
'11111111-1111-1111-1111-111111111111'::uuid)
(8 rows)

best regards,
Ranier Vilela