[PATCH] Add support function for containment operators

[Kim Johan Andersson]

I had noticed that performance wasn't great when using the @> or <@ 
operators when examining if an element is contained in a range.
Based on the discussion in [1] I would like to suggest the following 
changes:


This patch attempts to improve the row estimation, as well as opening 
the possibility of using a btree index scan when using the containment 
operators.


This is done via a new support function handling the following 2 requests:

* SupportRequestIndexCondition
find_index_quals will build an operator clause, given at least one 
finite RangeBound.


* SupportRequestSimplify
find_simplified_clause will rewrite the containment operator into a 
clause using inequality operators from the btree family (if available 
for the element type).


A boolean constant is returned if the range is either empty or has no 
bounds.


Performing the rewrite here lets the clausesel machinery provide the 
same estimates as for normal scalar inequalities.


In both cases build_bound_expr is used to build the operator clauses 
from RangeBounds.


Thanks to Laurenz Albe for giving the patch a look before submission.

[1] 
https://www.postgresql.org/message-id/222c75fd-43b8-db3e-74a6-bb4fe22f7...@kimmet.dk


Regards,
Kim Johan Anderssondiff --git a/src/backend/utils/adt/rangetypes.c 
b/src/backend/utils/adt/rangetypes.c
index d65e5625c7..f20ca76d87 100644
--- a/src/backend/utils/adt/rangetypes.c
+++ b/src/backend/utils/adt/rangetypes.c
@@ -31,13 +31,19 @@
 #include "postgres.h"
 
 #include "access/tupmacs.h"
+#include "access/stratnum.h"
 #include "common/hashfn.h"
 #include "lib/stringinfo.h"
 #include "libpq/pqformat.h"
 #include "miscadmin.h"
+#include "nodes/supportnodes.h"
+#include "nodes/makefuncs.h"
+#include "nodes/nodeFuncs.h"
+#include "nodes/pg_list.h"
 #include "nodes/miscnodes.h"
 #include "port/pg_bitutils.h"
 #include "utils/builtins.h"
+#include "utils/fmgroids.h"
 #include "utils/date.h"
 #include "utils/lsyscache.h"
 #include "utils/rangetypes.h"
@@ -69,7 +75,13 @@ static Size datum_compute_size(Size data_length, Datum val, 
bool typbyval,
   char typalign, int16 
typlen, char typstorage);
 static Pointer datum_write(Pointer ptr, Datum datum, bool typbyval,
   char typalign, int16 typlen, 
char typstorage);
-
+static Expr *build_bound_expr(Oid opfamily, TypeCacheEntry *typeCache,
+ bool isLowerBound, 
bool isInclusive,
+ Datum val, Expr 
*otherExpr);
+static Node *find_index_quals(Const *rangeConst, Expr *otherExpr,
+ Oid opfamily);
+static Node *find_simplified_clause(Const *rangeConst, Expr *otherExpr);
+static Node *match_support_request(Node *rawreq);
 
 /*
  *--
@@ -558,7 +570,6 @@ elem_contained_by_range(PG_FUNCTION_ARGS)
PG_RETURN_BOOL(range_contains_elem_internal(typcache, r, val));
 }
 
-
 /* range, range -> bool functions */
 
 /* equality (internal version) */
@@ -2173,6 +2184,29 @@ make_empty_range(TypeCacheEntry *typcache)
return make_range(typcache, &lower, &upper, true, NULL);
 }
 
+/*
+ * Planner support function for elem_contained_by_range operator
+ */
+Datum
+elem_contained_by_range_support(PG_FUNCTION_ARGS)
+{
+   Node   *rawreq = (Node *) PG_GETARG_POINTER(0);
+   Node   *ret = match_support_request(rawreq);
+
+   PG_RETURN_POINTER(ret);
+}
+
+/*
+ * Planner support function for range_contains_elem operator
+ */
+Datum
+range_contains_elem_support(PG_FUNCTION_ARGS)
+{
+   Node   *rawreq = (Node *) PG_GETARG_POINTER(0);
+   Node   *ret = match_support_request(rawreq);
+
+   PG_RETURN_POINTER(ret);
+}
 
 /*
  *--
@@ -2714,3 +2748,277 @@ datum_write(Pointer ptr, Datum datum, bool typbyval, 
char typalign,
 
return ptr;
 }
+
+static Expr *
+build_bound_expr(Oid opfamily, TypeCacheEntry *typeCache, bool isLowerBound, 
bool isInclusive, Datum val, Expr *otherExpr)
+{
+   Oid elemType = typeCache->type_id;
+   int16   elemTypeLen = typeCache->typlen;
+   boolelemByValue = typeCache->typbyval;
+   Oid elemCollation = typeCache->typcollation;
+   int16   strategy;
+   Oid oproid;
+   Expr   *constExpr;
+
+   if (isLowerBound)
+   strategy = isInclusive ? BTGreaterEqualStrategyNumber : 
BTGreaterStrategyNumber;
+   else
+   strategy = isInclusive ? BTLessEqualStrategyNumber : 
BTLessStrategyNumber;
+
+   oproid = get_opfamily_member(opfamily, elemType, elemType, strategy);
+
+   if (!OidIsValid(oproid))
+   return NULL;
+
+   constExpr = (Expr *) makeConst(

Re: [PATCH] Add support function for containment operators

[Kim Johan Andersson]

On 12-11-2023 20:20, Laurenz Albe wrote:

On Sun, 2023-11-12 at 18:15 +0100, Laurenz Albe wrote:

I adjusted your patch according to my comments; what do you think?


I have added the patch to the January commitfest, with Jian and Kim as authors.
I hope that is OK with you.


Sounds great to me. Thanks to Jian for picking this up.

Regards,
Kim Johan Andersson

Re: [PATCH] Add support function for containment operators

[Kim Johan Andersson]

Any thoughts on this change?

Re: [PATCH] Add support function for containment operators

[Kim Johan Andersson]

On 07-07-2023 13:20, Laurenz Albe wrote:

I wrote:

You implement both "SupportRequestIndexCondition" and "SupportRequestSimplify",
but when I experimented, the former was never called.  That does not
surprise me, since any expression of the shape "expr <@ range constant"
can be simplified.  Is the "SupportRequestIndexCondition" branch dead code?
If not, do you have an example that triggers it?


I would think it is dead code, I came to the same conclusion. So we can 
drop SupportRequestIndexCondition, since the simplification happens to 
take care of everything.




I had an idea about this:
So far, you only consider constant ranges.  But if we have a STABLE range
expression, you could use an index scan for "expr <@ range", for example
Index Cond (expr >= lower(range) AND expr < upper(range)).



I will try to look into this. Originally that was what I was hoping for, 
but didn't see way of going about it.


Thanks for your comments, I will also look at the locale-related 
breakage you spotted.


Regards,
Kimjand