Teach btree to handle ScalarArrayOpExpr quals natively.

This allows "indexedcol op ANY(ARRAY[...])" conditions to be used in plain
indexscans, and particularly in index-only scans.

2 files changed, 36 insertions, 6 deletions

diff --git a/src/include/access/nbtree.h b/src/include/access/nbtree.h
index 199fc940267..347d9423ba3 100644
--- a/src/include/access/nbtree.h
+++ b/src/include/access/nbtree.h
@@ -525,6 +525,15 @@ typedef BTScanPosData *BTScanPos;
 
 #define BTScanPosIsValid(scanpos) BufferIsValid((scanpos).buf)
 
+/* We need one of these for each equality-type SK_SEARCHARRAY scan key */
+typedef struct BTArrayKeyInfo
+{
+	int			scan_key;		/* index of associated key in arrayKeyData */
+	int			cur_elem;		/* index of current element in elem_values */
+	int			num_elems;		/* number of elems in current array value */
+	Datum	   *elem_values;	/* array of num_elems Datums */
+} BTArrayKeyInfo;
+
 typedef struct BTScanOpaqueData
 {
 	/* these fields are set by _bt_preprocess_keys(): */
@@ -532,6 +541,13 @@ typedef struct BTScanOpaqueData
 	int			numberOfKeys;	/* number of preprocessed scan keys */
 	ScanKey		keyData;		/* array of preprocessed scan keys */
 
+	/* workspace for SK_SEARCHARRAY support */
+	ScanKey		arrayKeyData;	/* modified copy of scan->keyData */
+	int			numArrayKeys;	/* number of equality-type array keys (-1 if
+								 * there are any unsatisfiable array keys) */
+	BTArrayKeyInfo *arrayKeys;	/* info about each equality-type array key */
+	MemoryContext arrayContext;	/* scan-lifespan context for array data */
+
 	/* info about killed items if any (killedItems is NULL if never used) */
 	int		   *killedItems;	/* currPos.items indexes of killed items */
 	int			numKilled;		/* number of currently stored items */
@@ -639,6 +655,9 @@ extern ScanKey _bt_mkscankey(Relation rel, IndexTuple itup);
 extern ScanKey _bt_mkscankey_nodata(Relation rel);
 extern void _bt_freeskey(ScanKey skey);
 extern void _bt_freestack(BTStack stack);
+extern void _bt_preprocess_array_keys(IndexScanDesc scan);
+extern void _bt_start_array_keys(IndexScanDesc scan, ScanDirection dir);
+extern bool _bt_advance_array_keys(IndexScanDesc scan, ScanDirection dir);
 extern void _bt_preprocess_keys(IndexScanDesc scan);
 extern IndexTuple _bt_checkkeys(IndexScanDesc scan,
 			  Page page, OffsetNumber offnum,
diff --git a/src/include/access/skey.h b/src/include/access/skey.h
index a82e46ee0e1..b9c61cd10ae 100644
--- a/src/include/access/skey.h
+++ b/src/include/access/skey.h
@@ -55,18 +55,27 @@ typedef uint16 StrategyNumber;
  * If the operator is collation-sensitive, sk_collation must be set
  * correctly as well.
  *
+ * A ScanKey can also represent a ScalarArrayOpExpr, that is a condition
+ * "column op ANY(ARRAY[...])".  This is signaled by the SK_SEARCHARRAY
+ * flag bit.  The sk_argument is not a value of the operator's right-hand
+ * argument type, but rather an array of such values, and the per-element
+ * comparisons are to be ORed together.
+ *
  * A ScanKey can also represent a condition "column IS NULL" or "column
  * IS NOT NULL"; these cases are signaled by the SK_SEARCHNULL and
  * SK_SEARCHNOTNULL flag bits respectively.  The argument is always NULL,
  * and the sk_strategy, sk_subtype, sk_collation, and sk_func fields are
- * not used (unless set by the index AM).  Currently, SK_SEARCHNULL and
- * SK_SEARCHNOTNULL are supported only for index scans, not heap scans;
- * and not all index AMs support them.
+ * not used (unless set by the index AM).
+ *
+ * SK_SEARCHARRAY, SK_SEARCHNULL and SK_SEARCHNOTNULL are supported only
+ * for index scans, not heap scans; and not all index AMs support them,
+ * only those that set amsearcharray or amsearchnulls respectively.
  *
  * A ScanKey can also represent an ordering operator invocation, that is
  * an ordering requirement "ORDER BY indexedcol op constant".  This looks
  * the same as a comparison operator, except that the operator doesn't
  * (usually) yield boolean.  We mark such ScanKeys with SK_ORDER_BY.
+ * SK_SEARCHARRAY, SK_SEARCHNULL, SK_SEARCHNOTNULL cannot be used here.
  *
  * Note: in some places, ScanKeys are used as a convenient representation
  * for the invocation of an access method support procedure.  In this case
@@ -114,6 +123,7 @@ typedef ScanKeyData *ScanKey;
  *				opclass, NOT the operator's implementation function.
  * sk_strategy must be the same in all elements of the subsidiary array,
  * that is, the same as in the header entry.
+ * SK_SEARCHARRAY, SK_SEARCHNULL, SK_SEARCHNOTNULL cannot be used here.
  */
 
 /*
@@ -128,10 +138,11 @@ typedef ScanKeyData *ScanKey;
 #define SK_ROW_HEADER		0x0004		/* row comparison header (see above) */
 #define SK_ROW_MEMBER		0x0008		/* row comparison member (see above) */
 #define SK_ROW_END			0x0010		/* last row comparison member */
-#define SK_SEARCHNULL		0x0020		/* scankey represents "col IS NULL" */
-#define SK_SEARCHNOTNULL	0x0040		/* scankey represents "col IS NOT
+#define SK_SEARCHARRAY		0x0020		/* scankey represents ScalarArrayOp */
+#define SK_SEARCHNULL		0x0040		/* scankey represents "col IS NULL" */
+#define SK_SEARCHNOTNULL	0x0080		/* scankey represents "col IS NOT
 										 * NULL" */
-#define SK_ORDER_BY			0x0080		/* scankey is for ORDER BY op */
+#define SK_ORDER_BY			0x0100		/* scankey is for ORDER BY op */
 
 
 /*