LCOV - code coverage report
Current view: top level - src/backend/access/nbtree - nbtpreprocesskeys.c (source / functions) Hit Total Coverage
Test: PostgreSQL 19devel Lines: 694 782 88.7 %
Date: 2025-08-31 07:17:45 Functions: 20 20 100.0 %
Legend: Lines: hit not hit

          Line data    Source code
       1             : /*-------------------------------------------------------------------------
       2             :  *
       3             :  * nbtpreprocesskeys.c
       4             :  *    Preprocessing for Postgres btree scan keys.
       5             :  *
       6             :  * Portions Copyright (c) 1996-2025, PostgreSQL Global Development Group
       7             :  * Portions Copyright (c) 1994, Regents of the University of California
       8             :  *
       9             :  *
      10             :  * IDENTIFICATION
      11             :  *    src/backend/access/nbtree/nbtpreprocesskeys.c
      12             :  *
      13             :  *-------------------------------------------------------------------------
      14             :  */
      15             : 
      16             : #include "postgres.h"
      17             : 
      18             : #include "access/nbtree.h"
      19             : #include "access/relscan.h"
      20             : #include "common/int.h"
      21             : #include "lib/qunique.h"
      22             : #include "utils/array.h"
      23             : #include "utils/lsyscache.h"
      24             : #include "utils/memutils.h"
      25             : #include "utils/rel.h"
      26             : 
      27             : typedef struct BTScanKeyPreproc
      28             : {
      29             :     ScanKey     inkey;
      30             :     int         inkeyi;
      31             :     int         arrayidx;
      32             : } BTScanKeyPreproc;
      33             : 
      34             : typedef struct BTSortArrayContext
      35             : {
      36             :     FmgrInfo   *sortproc;
      37             :     Oid         collation;
      38             :     bool        reverse;
      39             : } BTSortArrayContext;
      40             : 
      41             : static bool _bt_fix_scankey_strategy(ScanKey skey, int16 *indoption);
      42             : static void _bt_mark_scankey_required(ScanKey skey);
      43             : static bool _bt_compare_scankey_args(IndexScanDesc scan, ScanKey op,
      44             :                                      ScanKey leftarg, ScanKey rightarg,
      45             :                                      BTArrayKeyInfo *array, FmgrInfo *orderproc,
      46             :                                      bool *result);
      47             : static bool _bt_compare_array_scankey_args(IndexScanDesc scan,
      48             :                                            ScanKey arraysk, ScanKey skey,
      49             :                                            FmgrInfo *orderproc, BTArrayKeyInfo *array,
      50             :                                            bool *qual_ok);
      51             : static bool _bt_saoparray_shrink(IndexScanDesc scan, ScanKey arraysk,
      52             :                                  ScanKey skey, FmgrInfo *orderproc,
      53             :                                  BTArrayKeyInfo *array, bool *qual_ok);
      54             : static bool _bt_skiparray_shrink(IndexScanDesc scan, ScanKey skey,
      55             :                                  BTArrayKeyInfo *array, bool *qual_ok);
      56             : static void _bt_skiparray_strat_adjust(IndexScanDesc scan, ScanKey arraysk,
      57             :                                        BTArrayKeyInfo *array);
      58             : static void _bt_skiparray_strat_decrement(IndexScanDesc scan, ScanKey arraysk,
      59             :                                           BTArrayKeyInfo *array);
      60             : static void _bt_skiparray_strat_increment(IndexScanDesc scan, ScanKey arraysk,
      61             :                                           BTArrayKeyInfo *array);
      62             : static void _bt_unmark_keys(IndexScanDesc scan, int *keyDataMap);
      63             : static int  _bt_reorder_array_cmp(const void *a, const void *b);
      64             : static ScanKey _bt_preprocess_array_keys(IndexScanDesc scan, int *new_numberOfKeys);
      65             : static void _bt_preprocess_array_keys_final(IndexScanDesc scan, int *keyDataMap);
      66             : static int  _bt_num_array_keys(IndexScanDesc scan, Oid *skip_eq_ops_out,
      67             :                                int *numSkipArrayKeys_out);
      68             : static Datum _bt_find_extreme_element(IndexScanDesc scan, ScanKey skey,
      69             :                                       Oid elemtype, StrategyNumber strat,
      70             :                                       Datum *elems, int nelems);
      71             : static void _bt_setup_array_cmp(IndexScanDesc scan, ScanKey skey, Oid elemtype,
      72             :                                 FmgrInfo *orderproc, FmgrInfo **sortprocp);
      73             : static int  _bt_sort_array_elements(ScanKey skey, FmgrInfo *sortproc,
      74             :                                     bool reverse, Datum *elems, int nelems);
      75             : static bool _bt_merge_arrays(IndexScanDesc scan, ScanKey skey,
      76             :                              FmgrInfo *sortproc, bool reverse,
      77             :                              Oid origelemtype, Oid nextelemtype,
      78             :                              Datum *elems_orig, int *nelems_orig,
      79             :                              Datum *elems_next, int nelems_next);
      80             : static int  _bt_compare_array_elements(const void *a, const void *b, void *arg);
      81             : 
      82             : 
      83             : /*
      84             :  *  _bt_preprocess_keys() -- Preprocess scan keys
      85             :  *
      86             :  * The given search-type keys (taken from scan->keyData[])
      87             :  * are copied to so->keyData[] with possible transformation.
      88             :  * scan->numberOfKeys is the number of input keys, so->numberOfKeys gets
      89             :  * the number of output keys.  Calling here a second or subsequent time
      90             :  * (during the same btrescan) is a no-op.
      91             :  *
      92             :  * The output keys are marked with additional sk_flags bits beyond the
      93             :  * system-standard bits supplied by the caller.  The DESC and NULLS_FIRST
      94             :  * indoption bits for the relevant index attribute are copied into the flags.
      95             :  * Also, for a DESC column, we commute (flip) all the sk_strategy numbers
      96             :  * so that the index sorts in the desired direction.
      97             :  *
      98             :  * One key purpose of this routine is to discover which scan keys must be
      99             :  * satisfied to continue the scan.  It also attempts to eliminate redundant
     100             :  * keys and detect contradictory keys.  (If the index opfamily provides
     101             :  * incomplete sets of cross-type operators, we may fail to detect redundant
     102             :  * or contradictory keys, but we can survive that.)
     103             :  *
     104             :  * Required output keys are sorted by index attribute.  Presently we expect
     105             :  * (but verify) that the input keys are already so sorted --- this is done
     106             :  * by match_clauses_to_index() in indxpath.c.  Some reordering of the keys
     107             :  * within each attribute may be done as a byproduct of the processing here.
     108             :  * That process must leave array scan keys (within an attribute) in the same
     109             :  * order as corresponding entries from the scan's BTArrayKeyInfo array info.
     110             :  * We might also construct skip array scan keys that weren't present in the
     111             :  * original input keys; these are also output in standard attribute order.
     112             :  *
     113             :  * The output keys are marked with flags SK_BT_REQFWD and/or SK_BT_REQBKWD
     114             :  * if they must be satisfied in order to continue the scan forward or backward
     115             :  * respectively.  _bt_checkkeys uses these flags.  For example, if the quals
     116             :  * are "x = 1 AND y < 4 AND z < 5", then _bt_checkkeys will reject a tuple
     117             :  * (1,2,7), but we must continue the scan in case there are tuples (1,3,z).
     118             :  * But once we reach tuples like (1,4,z) we can stop scanning because no
     119             :  * later tuples could match.  This is reflected by marking the x and y keys,
     120             :  * but not the z key, with SK_BT_REQFWD.  In general, the keys for leading
     121             :  * attributes with "=" keys are marked both SK_BT_REQFWD and SK_BT_REQBKWD.
     122             :  * For the first attribute without an "=" key, any "<" and "<=" keys are
     123             :  * marked SK_BT_REQFWD while any ">" and ">=" keys are marked SK_BT_REQBKWD.
     124             :  * This can be seen to be correct by considering the above example.
     125             :  *
     126             :  * If we never generated skip array scan keys, it would be possible for "gaps"
     127             :  * to appear that make it unsafe to mark any subsequent input scan keys
     128             :  * (copied from scan->keyData[]) as required to continue the scan.  Prior to
     129             :  * Postgres 18, a qual like "WHERE y = 4" always resulted in a full scan.
     130             :  * This qual now becomes "WHERE x = ANY('{every possible x value}') and y = 4"
     131             :  * on output.  In other words, preprocessing now adds a skip array on "x".
     132             :  * This has the potential to be much more efficient than a full index scan
     133             :  * (though it behaves like a full scan when there's many distinct "x" values).
     134             :  *
     135             :  * Typically, redundant keys are eliminated: we keep only the tightest
     136             :  * >/>= bound and the tightest </<= bound, and if there's an = key then
     137             :  * that's the only one returned.  (So, we return either a single = key,
     138             :  * or one or two boundary-condition keys for each attr.)  However, if we
     139             :  * cannot compare two keys for lack of a suitable cross-type operator,
     140             :  * we cannot eliminate either key.
     141             :  *
     142             :  * When all redundant keys could not be eliminated, we'll output a key array
     143             :  * that can more or less be treated as if it had no redundant keys.  Suppose
     144             :  * we have "x > 4::int AND x > 10::bigint AND x < 70", and we are unable to
     145             :  * determine which > key is more restrictive for lack of a suitable cross-type
     146             :  * operator.  We'll arbitrarily pick one of the > keys; the other > key won't
     147             :  * be marked required.  Obviously, the scan will be less efficient if we
     148             :  * choose x > 4 over x > 10 -- but it can still largely proceed as if there
     149             :  * was only a single > condition.  "x > 10" will be placed at the end of the
     150             :  * so->keyData[] output array.  It'll always be evaluated last, after the keys
     151             :  * that could be marked required in the usual way (after "x > 4 AND x < 70").
     152             :  * This can sometimes result in so->keyData[] keys that aren't even in index
     153             :  * attribute order (if the qual involves multiple attributes).  The scan's
     154             :  * required keys will still be in attribute order, though, so it can't matter.
     155             :  *
     156             :  * This scheme ensures that _bt_first always uses the same set of keys at the
     157             :  * start of a forwards scan as those _bt_checkkeys uses to determine when to
     158             :  * end a similar backwards scan (and vice-versa).  _bt_advance_array_keys
     159             :  * depends on this: it expects to be able to reliably predict what the next
     160             :  * _bt_first call will do by testing whether _bt_checkkeys' routines report
     161             :  * that the final tuple on the page is past the end of matches for the scan's
     162             :  * keys with the scan direction flipped.  If it is (if continuescan=false),
     163             :  * then it follows that calling _bt_first will, at a minimum, relocate the
     164             :  * scan to the very next leaf page (in the current scan direction).
     165             :  *
     166             :  * As a byproduct of this work, we can detect contradictory quals such
     167             :  * as "x = 1 AND x > 2".  If we see that, we return so->qual_ok = false,
     168             :  * indicating the scan need not be run at all since no tuples can match.
     169             :  * (In this case we do not bother completing the output key array!)
     170             :  * Again, missing cross-type operators might cause us to fail to prove the
     171             :  * quals contradictory when they really are, but the scan will work correctly.
     172             :  *
     173             :  * Skip array = keys will even be generated in the presence of "contradictory"
     174             :  * inequality quals when it'll enable marking later input quals as required.
     175             :  * We'll merge any such inequalities into the generated skip array by setting
     176             :  * its array.low_compare or array.high_compare key field.  The resulting skip
     177             :  * array will generate its array elements from a range that's constrained by
     178             :  * any merged input inequalities (which won't get output in so->keyData[]).
     179             :  *
     180             :  * Row comparison keys currently have a couple of notable limitations.
     181             :  * Right now we just transfer them into the preprocessed array without any
     182             :  * editorialization.  We can treat them the same as an ordinary inequality
     183             :  * comparison on the row's first index column, for the purposes of the logic
     184             :  * about required keys.  Also, we are unable to merge a row comparison key
     185             :  * into a skip array (only ordinary inequalities are merged).  A key that
     186             :  * comes after a Row comparison key is therefore never marked as required.
     187             :  *
     188             :  * Note: the reason we have to copy the preprocessed scan keys into private
     189             :  * storage is that we are modifying the array based on comparisons of the
     190             :  * key argument values, which could change on a rescan.  Therefore we can't
     191             :  * overwrite the source data.
     192             :  */
     193             : void
     194    15801748 : _bt_preprocess_keys(IndexScanDesc scan)
     195             : {
     196    15801748 :     BTScanOpaque so = (BTScanOpaque) scan->opaque;
     197    15801748 :     int         numberOfKeys = scan->numberOfKeys;
     198    15801748 :     int16      *indoption = scan->indexRelation->rd_indoption;
     199             :     int         new_numberOfKeys;
     200             :     int         numberOfEqualCols;
     201             :     ScanKey     inkeys;
     202             :     BTScanKeyPreproc xform[BTMaxStrategyNumber];
     203             :     bool        test_result,
     204    15801748 :                 redundant_key_kept = false;
     205             :     AttrNumber  attno;
     206             :     ScanKey     arrayKeyData;
     207    15801748 :     int        *keyDataMap = NULL;
     208    15801748 :     int         arrayidx = 0;
     209             : 
     210    15801748 :     if (so->numberOfKeys > 0)
     211             :     {
     212             :         /*
     213             :          * Only need to do preprocessing once per btrescan, at most.  All
     214             :          * calls after the first are handled as no-ops.
     215             :          */
     216     8208158 :         return;
     217             :     }
     218             : 
     219             :     /* initialize result variables */
     220    15784218 :     so->qual_ok = true;
     221    15784218 :     so->numberOfKeys = 0;
     222             : 
     223    15784218 :     if (numberOfKeys < 1)
     224       13238 :         return;                 /* done if qual-less scan */
     225             : 
     226             :     /* If any keys are SK_SEARCHARRAY type, set up array-key info */
     227    15770980 :     arrayKeyData = _bt_preprocess_array_keys(scan, &numberOfKeys);
     228    15770980 :     if (!so->qual_ok)
     229             :     {
     230             :         /* unmatchable array, so give up */
     231          18 :         return;
     232             :     }
     233             : 
     234             :     /*
     235             :      * Treat arrayKeyData[] (a partially preprocessed copy of scan->keyData[])
     236             :      * as our input if _bt_preprocess_array_keys just allocated it, else just
     237             :      * use scan->keyData[]
     238             :      */
     239    15770962 :     if (arrayKeyData)
     240             :     {
     241       71096 :         inkeys = arrayKeyData;
     242             : 
     243             :         /* Also maintain keyDataMap for remapping so->orderProcs[] later */
     244       71096 :         keyDataMap = MemoryContextAlloc(so->arrayContext,
     245             :                                         numberOfKeys * sizeof(int));
     246             : 
     247             :         /*
     248             :          * Also enlarge output array when it might otherwise not have room for
     249             :          * a skip array's scan key
     250             :          */
     251       71096 :         if (numberOfKeys > scan->numberOfKeys)
     252        3804 :             so->keyData = repalloc(so->keyData,
     253             :                                    numberOfKeys * sizeof(ScanKeyData));
     254             :     }
     255             :     else
     256    15699866 :         inkeys = scan->keyData;
     257             : 
     258             :     /* we check that input keys are correctly ordered */
     259    15770962 :     if (inkeys[0].sk_attno < 1)
     260           0 :         elog(ERROR, "btree index keys must be ordered by attribute");
     261             : 
     262             :     /* We can short-circuit most of the work if there's just one key */
     263    15770962 :     if (numberOfKeys == 1)
     264             :     {
     265             :         /* Apply indoption to scankey (might change sk_strategy!) */
     266     8176390 :         if (!_bt_fix_scankey_strategy(&inkeys[0], indoption))
     267        1044 :             so->qual_ok = false;
     268     8176390 :         memcpy(&so->keyData[0], &inkeys[0], sizeof(ScanKeyData));
     269     8176390 :         so->numberOfKeys = 1;
     270             :         /* We can mark the qual as required if it's for first index col */
     271     8176390 :         if (inkeys[0].sk_attno == 1)
     272     8176390 :             _bt_mark_scankey_required(&so->keyData[0]);
     273             :         if (arrayKeyData)
     274             :         {
     275             :             /*
     276             :              * Don't call _bt_preprocess_array_keys_final in this fast path
     277             :              * (we'll miss out on the single value array transformation, but
     278             :              * that's not nearly as important when there's only one scan key)
     279             :              */
     280             :             Assert(so->keyData[0].sk_flags & SK_SEARCHARRAY);
     281             :             Assert(so->keyData[0].sk_strategy != BTEqualStrategyNumber ||
     282             :                    (so->arrayKeys[0].scan_key == 0 &&
     283             :                     !(so->keyData[0].sk_flags & SK_BT_SKIP) &&
     284             :                     OidIsValid(so->orderProcs[0].fn_oid)));
     285             :         }
     286             : 
     287     8176390 :         return;
     288             :     }
     289             : 
     290             :     /*
     291             :      * Otherwise, do the full set of pushups.
     292             :      */
     293     7594572 :     new_numberOfKeys = 0;
     294     7594572 :     numberOfEqualCols = 0;
     295             : 
     296             :     /*
     297             :      * Initialize for processing of keys for attr 1.
     298             :      *
     299             :      * xform[i] points to the currently best scan key of strategy type i+1; it
     300             :      * is NULL if we haven't yet found such a key for this attr.
     301             :      */
     302     7594572 :     attno = 1;
     303     7594572 :     memset(xform, 0, sizeof(xform));
     304             : 
     305             :     /*
     306             :      * Loop iterates from 0 to numberOfKeys inclusive; we use the last pass to
     307             :      * handle after-last-key processing.  Actual exit from the loop is at the
     308             :      * "break" statement below.
     309             :      */
     310     7594572 :     for (int i = 0;; i++)
     311    16701202 :     {
     312    24295774 :         ScanKey     inkey = inkeys + i;
     313             :         int         j;
     314             : 
     315    24295774 :         if (i < numberOfKeys)
     316             :         {
     317             :             /* Apply indoption to scankey (might change sk_strategy!) */
     318    16702148 :             if (!_bt_fix_scankey_strategy(inkey, indoption))
     319             :             {
     320             :                 /* NULL can't be matched, so give up */
     321         940 :                 so->qual_ok = false;
     322         940 :                 return;
     323             :             }
     324             :         }
     325             : 
     326             :         /*
     327             :          * If we are at the end of the keys for a particular attr, finish up
     328             :          * processing and emit the cleaned-up keys.
     329             :          */
     330    24294834 :         if (i == numberOfKeys || inkey->sk_attno != attno)
     331             :         {
     332    16698714 :             int         priorNumberOfEqualCols = numberOfEqualCols;
     333             : 
     334             :             /* check input keys are correctly ordered */
     335    16698714 :             if (i < numberOfKeys && inkey->sk_attno < attno)
     336           0 :                 elog(ERROR, "btree index keys must be ordered by attribute");
     337             : 
     338             :             /*
     339             :              * If = has been specified, all other keys can be eliminated as
     340             :              * redundant.  Note that this is no less true if the = key is
     341             :              * SEARCHARRAY; the only real difference is that the inequality
     342             :              * key _becomes_ redundant by making _bt_compare_scankey_args
     343             :              * eliminate the subset of elements that won't need to be matched
     344             :              * (with SAOP arrays and skip arrays alike).
     345             :              *
     346             :              * If we have a case like "key = 1 AND key > 2", we set qual_ok to
     347             :              * false and abandon further processing.  We'll do the same thing
     348             :              * given a case like "key IN (0, 1) AND key > 2".
     349             :              *
     350             :              * We also have to deal with the case of "key IS NULL", which is
     351             :              * unsatisfiable in combination with any other index condition. By
     352             :              * the time we get here, that's been classified as an equality
     353             :              * check, and we've rejected any combination of it with a regular
     354             :              * equality condition; but not with other types of conditions.
     355             :              */
     356    16698714 :             if (xform[BTEqualStrategyNumber - 1].inkey)
     357             :             {
     358    15077792 :                 ScanKey     eq = xform[BTEqualStrategyNumber - 1].inkey;
     359    15077792 :                 BTArrayKeyInfo *array = NULL;
     360    15077792 :                 FmgrInfo   *orderproc = NULL;
     361             : 
     362    15077792 :                 if (arrayKeyData && (eq->sk_flags & SK_SEARCHARRAY))
     363             :                 {
     364             :                     int         eq_in_ikey,
     365             :                                 eq_arrayidx;
     366             : 
     367        4644 :                     eq_in_ikey = xform[BTEqualStrategyNumber - 1].inkeyi;
     368        4644 :                     eq_arrayidx = xform[BTEqualStrategyNumber - 1].arrayidx;
     369        4644 :                     array = &so->arrayKeys[eq_arrayidx - 1];
     370        4644 :                     orderproc = so->orderProcs + eq_in_ikey;
     371             : 
     372             :                     Assert(array->scan_key == eq_in_ikey);
     373             :                     Assert(OidIsValid(orderproc->fn_oid));
     374             :                 }
     375             : 
     376    90466596 :                 for (j = BTMaxStrategyNumber; --j >= 0;)
     377             :                 {
     378    75388840 :                     ScanKey     chk = xform[j].inkey;
     379             : 
     380    75388840 :                     if (!chk || j == (BTEqualStrategyNumber - 1))
     381    75388278 :                         continue;
     382             : 
     383         562 :                     if (eq->sk_flags & SK_SEARCHNULL)
     384             :                     {
     385             :                         /* IS NULL is contradictory to anything else */
     386          24 :                         so->qual_ok = false;
     387          24 :                         return;
     388             :                     }
     389             : 
     390         538 :                     if (_bt_compare_scankey_args(scan, chk, eq, chk,
     391             :                                                  array, orderproc,
     392             :                                                  &test_result))
     393             :                     {
     394         532 :                         if (!test_result)
     395             :                         {
     396             :                             /* keys proven mutually contradictory */
     397          12 :                             so->qual_ok = false;
     398          12 :                             return;
     399             :                         }
     400             :                         /* else discard the redundant non-equality key */
     401         520 :                         xform[j].inkey = NULL;
     402         520 :                         xform[j].inkeyi = -1;
     403             :                     }
     404             :                     else
     405           6 :                         redundant_key_kept = true;
     406             :                 }
     407             :                 /* track number of attrs for which we have "=" keys */
     408    15077756 :                 numberOfEqualCols++;
     409             :             }
     410             : 
     411             :             /* try to keep only one of <, <= */
     412    16698678 :             if (xform[BTLessStrategyNumber - 1].inkey &&
     413        1908 :                 xform[BTLessEqualStrategyNumber - 1].inkey)
     414             :             {
     415           6 :                 ScanKey     lt = xform[BTLessStrategyNumber - 1].inkey;
     416           6 :                 ScanKey     le = xform[BTLessEqualStrategyNumber - 1].inkey;
     417             : 
     418           6 :                 if (_bt_compare_scankey_args(scan, le, lt, le, NULL, NULL,
     419             :                                              &test_result))
     420             :                 {
     421           6 :                     if (test_result)
     422           6 :                         xform[BTLessEqualStrategyNumber - 1].inkey = NULL;
     423             :                     else
     424           0 :                         xform[BTLessStrategyNumber - 1].inkey = NULL;
     425             :                 }
     426             :                 else
     427           0 :                     redundant_key_kept = true;
     428             :             }
     429             : 
     430             :             /* try to keep only one of >, >= */
     431    16698678 :             if (xform[BTGreaterStrategyNumber - 1].inkey &&
     432     1616672 :                 xform[BTGreaterEqualStrategyNumber - 1].inkey)
     433             :             {
     434           6 :                 ScanKey     gt = xform[BTGreaterStrategyNumber - 1].inkey;
     435           6 :                 ScanKey     ge = xform[BTGreaterEqualStrategyNumber - 1].inkey;
     436             : 
     437           6 :                 if (_bt_compare_scankey_args(scan, ge, gt, ge, NULL, NULL,
     438             :                                              &test_result))
     439             :                 {
     440           6 :                     if (test_result)
     441           0 :                         xform[BTGreaterEqualStrategyNumber - 1].inkey = NULL;
     442             :                     else
     443           6 :                         xform[BTGreaterStrategyNumber - 1].inkey = NULL;
     444             :                 }
     445             :                 else
     446           0 :                     redundant_key_kept = true;
     447             :             }
     448             : 
     449             :             /*
     450             :              * Emit the cleaned-up keys into the so->keyData[] array, and then
     451             :              * mark them if they are required.  They are required (possibly
     452             :              * only in one direction) if all attrs before this one had "=".
     453             :              *
     454             :              * In practice we'll rarely output non-required scan keys here;
     455             :              * typically, _bt_preprocess_array_keys has already added "=" keys
     456             :              * sufficient to form an unbroken series of "=" constraints on all
     457             :              * attrs prior to the attr from the final scan->keyData[] key.
     458             :              */
     459   100192068 :             for (j = BTMaxStrategyNumber; --j >= 0;)
     460             :             {
     461    83493390 :                 if (xform[j].inkey)
     462             :                 {
     463    16700514 :                     ScanKey     outkey = &so->keyData[new_numberOfKeys++];
     464             : 
     465    16700514 :                     memcpy(outkey, xform[j].inkey, sizeof(ScanKeyData));
     466    16700514 :                     if (arrayKeyData)
     467        9522 :                         keyDataMap[new_numberOfKeys - 1] = xform[j].inkeyi;
     468    16700514 :                     if (priorNumberOfEqualCols == attno - 1)
     469    16700514 :                         _bt_mark_scankey_required(outkey);
     470             :                 }
     471             :             }
     472             : 
     473             :             /*
     474             :              * Exit loop here if done.
     475             :              */
     476    16698678 :             if (i == numberOfKeys)
     477     7593590 :                 break;
     478             : 
     479             :             /* Re-initialize for new attno */
     480     9105088 :             attno = inkey->sk_attno;
     481     9105088 :             memset(xform, 0, sizeof(xform));
     482             :         }
     483             : 
     484             :         /* check strategy this key's operator corresponds to */
     485    16701208 :         j = inkey->sk_strategy - 1;
     486             : 
     487    16701208 :         if (inkey->sk_strategy == BTEqualStrategyNumber &&
     488    15077840 :             (inkey->sk_flags & SK_SEARCHARRAY))
     489             :         {
     490             :             /* must track how input scan keys map to arrays */
     491             :             Assert(arrayKeyData);
     492        4650 :             arrayidx++;
     493             :         }
     494             : 
     495             :         /*
     496             :          * have we seen a scan key for this same attribute and using this same
     497             :          * operator strategy before now?
     498             :          */
     499    16701208 :         if (xform[j].inkey == NULL)
     500             :         {
     501             :             /* nope, so this scan key wins by default (at least for now) */
     502    16701142 :             xform[j].inkey = inkey;
     503    16701142 :             xform[j].inkeyi = i;
     504    16701142 :             xform[j].arrayidx = arrayidx;
     505             :         }
     506             :         else
     507             :         {
     508          66 :             FmgrInfo   *orderproc = NULL;
     509          66 :             BTArrayKeyInfo *array = NULL;
     510             : 
     511             :             /*
     512             :              * Seen one of these before, so keep only the more restrictive key
     513             :              * if possible
     514             :              */
     515          66 :             if (j == (BTEqualStrategyNumber - 1) && arrayKeyData)
     516             :             {
     517             :                 /*
     518             :                  * Have to set up array keys
     519             :                  */
     520          18 :                 if (inkey->sk_flags & SK_SEARCHARRAY)
     521             :                 {
     522           0 :                     array = &so->arrayKeys[arrayidx - 1];
     523           0 :                     orderproc = so->orderProcs + i;
     524             : 
     525             :                     Assert(array->scan_key == i);
     526             :                     Assert(OidIsValid(orderproc->fn_oid));
     527             :                     Assert(!(inkey->sk_flags & SK_BT_SKIP));
     528             :                 }
     529          18 :                 else if (xform[j].inkey->sk_flags & SK_SEARCHARRAY)
     530             :                 {
     531          12 :                     array = &so->arrayKeys[xform[j].arrayidx - 1];
     532          12 :                     orderproc = so->orderProcs + xform[j].inkeyi;
     533             : 
     534             :                     Assert(array->scan_key == xform[j].inkeyi);
     535             :                     Assert(OidIsValid(orderproc->fn_oid));
     536             :                     Assert(!(xform[j].inkey->sk_flags & SK_BT_SKIP));
     537             :                 }
     538             : 
     539             :                 /*
     540             :                  * Both scan keys might have arrays, in which case we'll
     541             :                  * arbitrarily pass only one of the arrays.  That won't
     542             :                  * matter, since _bt_compare_scankey_args is aware that two
     543             :                  * SEARCHARRAY scan keys mean that _bt_preprocess_array_keys
     544             :                  * failed to eliminate redundant arrays through array merging.
     545             :                  * _bt_compare_scankey_args just returns false when it sees
     546             :                  * this; it won't even try to examine either array.
     547             :                  */
     548             :             }
     549             : 
     550          66 :             if (_bt_compare_scankey_args(scan, inkey, inkey, xform[j].inkey,
     551             :                                          array, orderproc, &test_result))
     552             :             {
     553             :                 /* Have all we need to determine redundancy */
     554          66 :                 if (test_result)
     555             :                 {
     556             :                     /*
     557             :                      * New key is more restrictive, and so replaces old key...
     558             :                      */
     559          54 :                     if (j != (BTEqualStrategyNumber - 1) ||
     560          18 :                         !(xform[j].inkey->sk_flags & SK_SEARCHARRAY))
     561             :                     {
     562          48 :                         xform[j].inkey = inkey;
     563          48 :                         xform[j].inkeyi = i;
     564          48 :                         xform[j].arrayidx = arrayidx;
     565             :                     }
     566             :                     else
     567             :                     {
     568             :                         /*
     569             :                          * ...unless we have to keep the old key because it's
     570             :                          * an array that rendered the new key redundant.  We
     571             :                          * need to make sure that we don't throw away an array
     572             :                          * scan key.  _bt_preprocess_array_keys_final expects
     573             :                          * us to keep all of the arrays that weren't already
     574             :                          * eliminated by _bt_preprocess_array_keys earlier on.
     575             :                          */
     576             :                         Assert(!(inkey->sk_flags & SK_SEARCHARRAY));
     577             :                     }
     578             :                 }
     579          12 :                 else if (j == (BTEqualStrategyNumber - 1))
     580             :                 {
     581             :                     /* key == a && key == b, but a != b */
     582           6 :                     so->qual_ok = false;
     583           6 :                     return;
     584             :                 }
     585             :                 /* else old key is more restrictive, keep it */
     586             :             }
     587             :             else
     588             :             {
     589             :                 /*
     590             :                  * We can't determine which key is more restrictive.  Push
     591             :                  * xform[j] directly to the output array, then set xform[j] to
     592             :                  * the new scan key.
     593             :                  *
     594             :                  * Note: We do things this way around so that our arrays are
     595             :                  * always in the same order as their corresponding scan keys.
     596             :                  * _bt_preprocess_array_keys_final expects this.
     597             :                  */
     598           0 :                 ScanKey     outkey = &so->keyData[new_numberOfKeys++];
     599             : 
     600           0 :                 memcpy(outkey, xform[j].inkey, sizeof(ScanKeyData));
     601           0 :                 if (arrayKeyData)
     602           0 :                     keyDataMap[new_numberOfKeys - 1] = xform[j].inkeyi;
     603           0 :                 if (numberOfEqualCols == attno - 1)
     604           0 :                     _bt_mark_scankey_required(outkey);
     605           0 :                 xform[j].inkey = inkey;
     606           0 :                 xform[j].inkeyi = i;
     607           0 :                 xform[j].arrayidx = arrayidx;
     608           0 :                 redundant_key_kept = true;
     609             :             }
     610             :         }
     611             :     }
     612             : 
     613     7593590 :     so->numberOfKeys = new_numberOfKeys;
     614             : 
     615             :     /*
     616             :      * Now that we've built a temporary mapping from so->keyData[] (output
     617             :      * scan keys) to arrayKeyData[] (our input scan keys), fix array->scan_key
     618             :      * references.  Also consolidate the so->orderProcs[] array such that it
     619             :      * can be subscripted using so->keyData[]-wise offsets.
     620             :      */
     621     7593590 :     if (arrayKeyData)
     622        4302 :         _bt_preprocess_array_keys_final(scan, keyDataMap);
     623             : 
     624             :     /*
     625             :      * If there are remaining redundant inequality keys, we must make sure
     626             :      * that each index attribute has no more than one required >/>= key, and
     627             :      * no more than one required </<= key.  Attributes that have one or more
     628             :      * required = keys now must keep only one required key (the first = key).
     629             :      */
     630     7593590 :     if (unlikely(redundant_key_kept) && so->qual_ok)
     631           6 :         _bt_unmark_keys(scan, keyDataMap);
     632             : 
     633             :     /* Could pfree arrayKeyData/keyDataMap now, but not worth the cycles */
     634             : }
     635             : 
     636             : /*
     637             :  * Adjust a scankey's strategy and flags setting as needed for indoptions.
     638             :  *
     639             :  * We copy the appropriate indoption value into the scankey sk_flags
     640             :  * (shifting to avoid clobbering system-defined flag bits).  Also, if
     641             :  * the DESC option is set, commute (flip) the operator strategy number.
     642             :  *
     643             :  * A secondary purpose is to check for IS NULL/NOT NULL scankeys and set up
     644             :  * the strategy field correctly for them.
     645             :  *
     646             :  * Lastly, for ordinary scankeys (not IS NULL/NOT NULL), we check for a
     647             :  * NULL comparison value.  Since all btree operators are assumed strict,
     648             :  * a NULL means that the qual cannot be satisfied.  We return true if the
     649             :  * comparison value isn't NULL, or false if the scan should be abandoned.
     650             :  *
     651             :  * This function is applied to the *input* scankey structure; therefore
     652             :  * on a rescan we will be looking at already-processed scankeys.  Hence
     653             :  * we have to be careful not to re-commute the strategy if we already did it.
     654             :  * It's a bit ugly to modify the caller's copy of the scankey but in practice
     655             :  * there shouldn't be any problem, since the index's indoptions are certainly
     656             :  * not going to change while the scankey survives.
     657             :  */
     658             : static bool
     659    24878538 : _bt_fix_scankey_strategy(ScanKey skey, int16 *indoption)
     660             : {
     661             :     int         addflags;
     662             : 
     663    24878538 :     addflags = indoption[skey->sk_attno - 1] << SK_BT_INDOPTION_SHIFT;
     664             : 
     665             :     /*
     666             :      * We treat all btree operators as strict (even if they're not so marked
     667             :      * in pg_proc). This means that it is impossible for an operator condition
     668             :      * with a NULL comparison constant to succeed, and we can reject it right
     669             :      * away.
     670             :      *
     671             :      * However, we now also support "x IS NULL" clauses as search conditions,
     672             :      * so in that case keep going. The planner has not filled in any
     673             :      * particular strategy in this case, so set it to BTEqualStrategyNumber
     674             :      * --- we can treat IS NULL as an equality operator for purposes of search
     675             :      * strategy.
     676             :      *
     677             :      * Likewise, "x IS NOT NULL" is supported.  We treat that as either "less
     678             :      * than NULL" in a NULLS LAST index, or "greater than NULL" in a NULLS
     679             :      * FIRST index.
     680             :      *
     681             :      * Note: someday we might have to fill in sk_collation from the index
     682             :      * column's collation.  At the moment this is a non-issue because we'll
     683             :      * never actually call the comparison operator on a NULL.
     684             :      */
     685    24878538 :     if (skey->sk_flags & SK_ISNULL)
     686             :     {
     687             :         /* SK_ISNULL shouldn't be set in a row header scankey */
     688             :         Assert(!(skey->sk_flags & SK_ROW_HEADER));
     689             : 
     690             :         /* Set indoption flags in scankey (might be done already) */
     691      122586 :         skey->sk_flags |= addflags;
     692             : 
     693             :         /* Set correct strategy for IS NULL or NOT NULL search */
     694      122586 :         if (skey->sk_flags & SK_SEARCHNULL)
     695             :         {
     696         152 :             skey->sk_strategy = BTEqualStrategyNumber;
     697         152 :             skey->sk_subtype = InvalidOid;
     698         152 :             skey->sk_collation = InvalidOid;
     699             :         }
     700      122434 :         else if (skey->sk_flags & SK_SEARCHNOTNULL)
     701             :         {
     702      120456 :             if (skey->sk_flags & SK_BT_NULLS_FIRST)
     703          36 :                 skey->sk_strategy = BTGreaterStrategyNumber;
     704             :             else
     705      120420 :                 skey->sk_strategy = BTLessStrategyNumber;
     706      120456 :             skey->sk_subtype = InvalidOid;
     707      120456 :             skey->sk_collation = InvalidOid;
     708             :         }
     709             :         else
     710             :         {
     711             :             /* regular qual, so it cannot be satisfied */
     712        1978 :             return false;
     713             :         }
     714             : 
     715             :         /* Needn't do the rest */
     716      120608 :         return true;
     717             :     }
     718             : 
     719             :     /* Adjust strategy for DESC, if we didn't already */
     720    24755952 :     if ((addflags & SK_BT_DESC) && !(skey->sk_flags & SK_BT_DESC))
     721          78 :         skey->sk_strategy = BTCommuteStrategyNumber(skey->sk_strategy);
     722    24755952 :     skey->sk_flags |= addflags;
     723             : 
     724             :     /* If it's a row header, fix row member flags and strategies similarly */
     725    24755952 :     if (skey->sk_flags & SK_ROW_HEADER)
     726             :     {
     727          84 :         ScanKey     subkey = (ScanKey) DatumGetPointer(skey->sk_argument);
     728             : 
     729          84 :         if (subkey->sk_flags & SK_ISNULL)
     730             :         {
     731             :             /* First row member is NULL, so RowCompare is unsatisfiable */
     732             :             Assert(subkey->sk_flags & SK_ROW_MEMBER);
     733           6 :             return false;
     734             :         }
     735             : 
     736             :         for (;;)
     737             :         {
     738          78 :             Assert(subkey->sk_flags & SK_ROW_MEMBER);
     739         156 :             addflags = indoption[subkey->sk_attno - 1] << SK_BT_INDOPTION_SHIFT;
     740         156 :             if ((addflags & SK_BT_DESC) && !(subkey->sk_flags & SK_BT_DESC))
     741           0 :                 subkey->sk_strategy = BTCommuteStrategyNumber(subkey->sk_strategy);
     742         156 :             subkey->sk_flags |= addflags;
     743         156 :             if (subkey->sk_flags & SK_ROW_END)
     744          78 :                 break;
     745          78 :             subkey++;
     746             :         }
     747             :     }
     748             : 
     749    24755946 :     return true;
     750             : }
     751             : 
     752             : /*
     753             :  * Mark a scankey as "required to continue the scan".
     754             :  *
     755             :  * Depending on the operator type, the key may be required for both scan
     756             :  * directions or just one.  Also, if the key is a row comparison header,
     757             :  * we have to mark the appropriate subsidiary ScanKeys as required.  In such
     758             :  * cases, the first subsidiary key is required, but subsequent ones are
     759             :  * required only as long as they correspond to successive index columns and
     760             :  * match the leading column as to sort direction.  Otherwise the row
     761             :  * comparison ordering is different from the index ordering and so we can't
     762             :  * stop the scan on the basis of those lower-order columns.
     763             :  *
     764             :  * Note: when we set required-key flag bits in a subsidiary scankey, we are
     765             :  * scribbling on a data structure belonging to the index AM's caller, not on
     766             :  * our private copy.  This should be OK because the marking will not change
     767             :  * from scan to scan within a query, and so we'd just re-mark the same way
     768             :  * anyway on a rescan.  Something to keep an eye on though.
     769             :  */
     770             : static void
     771    24876904 : _bt_mark_scankey_required(ScanKey skey)
     772             : {
     773             :     int         addflags;
     774             : 
     775    24876904 :     switch (skey->sk_strategy)
     776             :     {
     777      123326 :         case BTLessStrategyNumber:
     778             :         case BTLessEqualStrategyNumber:
     779      123326 :             addflags = SK_BT_REQFWD;
     780      123326 :             break;
     781    23131484 :         case BTEqualStrategyNumber:
     782    23131484 :             addflags = SK_BT_REQFWD | SK_BT_REQBKWD;
     783    23131484 :             break;
     784     1622094 :         case BTGreaterEqualStrategyNumber:
     785             :         case BTGreaterStrategyNumber:
     786     1622094 :             addflags = SK_BT_REQBKWD;
     787     1622094 :             break;
     788           0 :         default:
     789           0 :             elog(ERROR, "unrecognized StrategyNumber: %d",
     790             :                  (int) skey->sk_strategy);
     791             :             addflags = 0;       /* keep compiler quiet */
     792             :             break;
     793             :     }
     794             : 
     795    24876904 :     skey->sk_flags |= addflags;
     796             : 
     797    24876904 :     if (skey->sk_flags & SK_ROW_HEADER)
     798             :     {
     799          84 :         ScanKey     subkey = (ScanKey) DatumGetPointer(skey->sk_argument);
     800          84 :         AttrNumber  attno = skey->sk_attno;
     801             : 
     802             :         /* First subkey should be same column/operator as the header */
     803             :         Assert(subkey->sk_attno == attno);
     804             :         Assert(subkey->sk_strategy == skey->sk_strategy);
     805             : 
     806             :         for (;;)
     807             :         {
     808          84 :             Assert(subkey->sk_flags & SK_ROW_MEMBER);
     809         168 :             if (subkey->sk_attno != attno)
     810          12 :                 break;          /* non-adjacent key, so not required */
     811         156 :             if (subkey->sk_strategy != skey->sk_strategy)
     812           0 :                 break;          /* wrong direction, so not required */
     813         156 :             subkey->sk_flags |= addflags;
     814         156 :             if (subkey->sk_flags & SK_ROW_END)
     815          72 :                 break;
     816          84 :             subkey++;
     817          84 :             attno++;
     818             :         }
     819             :     }
     820    24876904 : }
     821             : 
     822             : /*
     823             :  * Compare two scankey values using a specified operator.
     824             :  *
     825             :  * The test we want to perform is logically "leftarg op rightarg", where
     826             :  * leftarg and rightarg are the sk_argument values in those ScanKeys, and
     827             :  * the comparison operator is the one in the op ScanKey.  However, in
     828             :  * cross-data-type situations we may need to look up the correct operator in
     829             :  * the index's opfamily: it is the one having amopstrategy = op->sk_strategy
     830             :  * and amoplefttype/amoprighttype equal to the two argument datatypes.
     831             :  *
     832             :  * If the opfamily doesn't supply a complete set of cross-type operators we
     833             :  * may not be able to make the comparison.  If we can make the comparison
     834             :  * we store the operator result in *result and return true.  We return false
     835             :  * if the comparison could not be made.
     836             :  *
     837             :  * If either leftarg or rightarg are an array, we'll apply array-specific
     838             :  * rules to determine which array elements are redundant on behalf of caller.
     839             :  * It is up to our caller to save whichever of the two scan keys is the array,
     840             :  * and discard the non-array scan key (the non-array scan key is guaranteed to
     841             :  * be redundant with any complete opfamily).  Caller isn't expected to call
     842             :  * here with a pair of array scan keys provided we're dealing with a complete
     843             :  * opfamily (_bt_preprocess_array_keys will merge array keys together to make
     844             :  * sure of that).
     845             :  *
     846             :  * Note: we'll also shrink caller's array as needed to eliminate redundant
     847             :  * array elements.  One reason why caller should prefer to discard non-array
     848             :  * scan keys is so that we'll have the opportunity to shrink the array
     849             :  * multiple times, in multiple calls (for each of several other scan keys on
     850             :  * the same index attribute).
     851             :  *
     852             :  * Note: op always points at the same ScanKey as either leftarg or rightarg.
     853             :  * Since we don't scribble on the scankeys themselves, this aliasing should
     854             :  * cause no trouble.
     855             :  *
     856             :  * Note: this routine needs to be insensitive to any DESC option applied
     857             :  * to the index column.  For example, "x < 4" is a tighter constraint than
     858             :  * "x < 5" regardless of which way the index is sorted.
     859             :  */
     860             : static bool
     861         628 : _bt_compare_scankey_args(IndexScanDesc scan, ScanKey op,
     862             :                          ScanKey leftarg, ScanKey rightarg,
     863             :                          BTArrayKeyInfo *array, FmgrInfo *orderproc,
     864             :                          bool *result)
     865             : {
     866         628 :     Relation    rel = scan->indexRelation;
     867             :     Oid         lefttype,
     868             :                 righttype,
     869             :                 optype,
     870             :                 opcintype,
     871             :                 cmp_op;
     872             :     StrategyNumber strat;
     873             : 
     874             :     Assert(!((leftarg->sk_flags | rightarg->sk_flags) & SK_ROW_MEMBER));
     875             : 
     876             :     /*
     877             :      * First, deal with cases where one or both args are NULL.  This should
     878             :      * only happen when the scankeys represent IS NULL/NOT NULL conditions.
     879             :      */
     880         628 :     if ((leftarg->sk_flags | rightarg->sk_flags) & SK_ISNULL)
     881             :     {
     882             :         bool        leftnull,
     883             :                     rightnull;
     884             : 
     885             :         /* Handle skip array comparison with IS NOT NULL scan key */
     886         174 :         if ((leftarg->sk_flags | rightarg->sk_flags) & SK_BT_SKIP)
     887             :         {
     888             :             /* Shouldn't generate skip array in presence of IS NULL key */
     889             :             Assert(!((leftarg->sk_flags | rightarg->sk_flags) & SK_SEARCHNULL));
     890             :             Assert((leftarg->sk_flags | rightarg->sk_flags) & SK_SEARCHNOTNULL);
     891             : 
     892             :             /* Skip array will have no NULL element/IS NULL scan key */
     893             :             Assert(array->num_elems == -1);
     894          36 :             array->null_elem = false;
     895             : 
     896             :             /* IS NOT NULL key (could be leftarg or rightarg) now redundant */
     897          36 :             *result = true;
     898          36 :             return true;
     899             :         }
     900             : 
     901         138 :         if (leftarg->sk_flags & SK_ISNULL)
     902             :         {
     903             :             Assert(leftarg->sk_flags & (SK_SEARCHNULL | SK_SEARCHNOTNULL));
     904           6 :             leftnull = true;
     905             :         }
     906             :         else
     907         132 :             leftnull = false;
     908         138 :         if (rightarg->sk_flags & SK_ISNULL)
     909             :         {
     910             :             Assert(rightarg->sk_flags & (SK_SEARCHNULL | SK_SEARCHNOTNULL));
     911         138 :             rightnull = true;
     912             :         }
     913             :         else
     914           0 :             rightnull = false;
     915             : 
     916             :         /*
     917             :          * We treat NULL as either greater than or less than all other values.
     918             :          * Since true > false, the tests below work correctly for NULLS LAST
     919             :          * logic.  If the index is NULLS FIRST, we need to flip the strategy.
     920             :          */
     921         138 :         strat = op->sk_strategy;
     922         138 :         if (op->sk_flags & SK_BT_NULLS_FIRST)
     923           0 :             strat = BTCommuteStrategyNumber(strat);
     924             : 
     925         138 :         switch (strat)
     926             :         {
     927         132 :             case BTLessStrategyNumber:
     928         132 :                 *result = (leftnull < rightnull);
     929         132 :                 break;
     930           0 :             case BTLessEqualStrategyNumber:
     931           0 :                 *result = (leftnull <= rightnull);
     932           0 :                 break;
     933           6 :             case BTEqualStrategyNumber:
     934           6 :                 *result = (leftnull == rightnull);
     935           6 :                 break;
     936           0 :             case BTGreaterEqualStrategyNumber:
     937           0 :                 *result = (leftnull >= rightnull);
     938           0 :                 break;
     939           0 :             case BTGreaterStrategyNumber:
     940           0 :                 *result = (leftnull > rightnull);
     941           0 :                 break;
     942           0 :             default:
     943           0 :                 elog(ERROR, "unrecognized StrategyNumber: %d", (int) strat);
     944             :                 *result = false;    /* keep compiler quiet */
     945             :                 break;
     946             :         }
     947         138 :         return true;
     948             :     }
     949             : 
     950             :     /*
     951             :      * We don't yet know how to determine redundancy when it involves a row
     952             :      * compare key (barring simple cases involving IS NULL/IS NOT NULL)
     953             :      */
     954         454 :     if ((leftarg->sk_flags | rightarg->sk_flags) & SK_ROW_HEADER)
     955             :     {
     956             :         Assert(!((leftarg->sk_flags | rightarg->sk_flags) & SK_BT_SKIP));
     957           6 :         return false;
     958             :     }
     959             : 
     960             :     /*
     961             :      * If either leftarg or rightarg are equality-type array scankeys, we need
     962             :      * specialized handling (since by now we know that IS NULL wasn't used)
     963             :      */
     964         448 :     if (array)
     965             :     {
     966             :         bool        leftarray,
     967             :                     rightarray;
     968             : 
     969         628 :         leftarray = ((leftarg->sk_flags & SK_SEARCHARRAY) &&
     970         308 :                      leftarg->sk_strategy == BTEqualStrategyNumber);
     971         332 :         rightarray = ((rightarg->sk_flags & SK_SEARCHARRAY) &&
     972          12 :                       rightarg->sk_strategy == BTEqualStrategyNumber);
     973             : 
     974             :         /*
     975             :          * _bt_preprocess_array_keys is responsible for merging together array
     976             :          * scan keys, and will do so whenever the opfamily has the required
     977             :          * cross-type support.  If it failed to do that, we handle it just
     978             :          * like the case where we can't make the comparison ourselves.
     979             :          */
     980         320 :         if (leftarray && rightarray)
     981             :         {
     982             :             /* Can't make the comparison */
     983           0 :             *result = false;    /* suppress compiler warnings */
     984             :             Assert(!((leftarg->sk_flags | rightarg->sk_flags) & SK_BT_SKIP));
     985           0 :             return false;
     986             :         }
     987             : 
     988             :         /*
     989             :          * Otherwise we need to determine if either one of leftarg or rightarg
     990             :          * uses an array, then pass this through to a dedicated helper
     991             :          * function.
     992             :          */
     993         320 :         if (leftarray)
     994         308 :             return _bt_compare_array_scankey_args(scan, leftarg, rightarg,
     995             :                                                   orderproc, array, result);
     996          12 :         else if (rightarray)
     997          12 :             return _bt_compare_array_scankey_args(scan, rightarg, leftarg,
     998             :                                                   orderproc, array, result);
     999             : 
    1000             :         /* FALL THRU */
    1001             :     }
    1002             : 
    1003             :     /*
    1004             :      * The opfamily we need to worry about is identified by the index column.
    1005             :      */
    1006             :     Assert(leftarg->sk_attno == rightarg->sk_attno);
    1007             : 
    1008         128 :     opcintype = rel->rd_opcintype[leftarg->sk_attno - 1];
    1009             : 
    1010             :     /*
    1011             :      * Determine the actual datatypes of the ScanKey arguments.  We have to
    1012             :      * support the convention that sk_subtype == InvalidOid means the opclass
    1013             :      * input type; this is a hack to simplify life for ScanKeyInit().
    1014             :      */
    1015         128 :     lefttype = leftarg->sk_subtype;
    1016         128 :     if (lefttype == InvalidOid)
    1017           0 :         lefttype = opcintype;
    1018         128 :     righttype = rightarg->sk_subtype;
    1019         128 :     if (righttype == InvalidOid)
    1020           0 :         righttype = opcintype;
    1021         128 :     optype = op->sk_subtype;
    1022         128 :     if (optype == InvalidOid)
    1023           0 :         optype = opcintype;
    1024             : 
    1025             :     /*
    1026             :      * If leftarg and rightarg match the types expected for the "op" scankey,
    1027             :      * we can use its already-looked-up comparison function.
    1028             :      */
    1029         128 :     if (lefttype == opcintype && righttype == optype)
    1030             :     {
    1031         122 :         *result = DatumGetBool(FunctionCall2Coll(&op->sk_func,
    1032             :                                                  op->sk_collation,
    1033             :                                                  leftarg->sk_argument,
    1034             :                                                  rightarg->sk_argument));
    1035         122 :         return true;
    1036             :     }
    1037             : 
    1038             :     /*
    1039             :      * Otherwise, we need to go to the syscache to find the appropriate
    1040             :      * operator.  (This cannot result in infinite recursion, since no
    1041             :      * indexscan initiated by syscache lookup will use cross-data-type
    1042             :      * operators.)
    1043             :      *
    1044             :      * If the sk_strategy was flipped by _bt_fix_scankey_strategy, we have to
    1045             :      * un-flip it to get the correct opfamily member.
    1046             :      */
    1047           6 :     strat = op->sk_strategy;
    1048           6 :     if (op->sk_flags & SK_BT_DESC)
    1049           0 :         strat = BTCommuteStrategyNumber(strat);
    1050             : 
    1051           6 :     cmp_op = get_opfamily_member(rel->rd_opfamily[leftarg->sk_attno - 1],
    1052             :                                  lefttype,
    1053             :                                  righttype,
    1054             :                                  strat);
    1055           6 :     if (OidIsValid(cmp_op))
    1056             :     {
    1057           6 :         RegProcedure cmp_proc = get_opcode(cmp_op);
    1058             : 
    1059           6 :         if (RegProcedureIsValid(cmp_proc))
    1060             :         {
    1061           6 :             *result = DatumGetBool(OidFunctionCall2Coll(cmp_proc,
    1062             :                                                         op->sk_collation,
    1063             :                                                         leftarg->sk_argument,
    1064             :                                                         rightarg->sk_argument));
    1065           6 :             return true;
    1066             :         }
    1067             :     }
    1068             : 
    1069             :     /* Can't make the comparison */
    1070           0 :     *result = false;            /* suppress compiler warnings */
    1071           0 :     return false;
    1072             : }
    1073             : 
    1074             : /*
    1075             :  * Compare an array scan key to a scalar scan key, eliminating contradictory
    1076             :  * array elements such that the scalar scan key becomes redundant.
    1077             :  *
    1078             :  * If the opfamily is incomplete we may not be able to determine which
    1079             :  * elements are contradictory.  When we return true we'll have validly set
    1080             :  * *qual_ok, guaranteeing that at least the scalar scan key can be considered
    1081             :  * redundant.  We return false if the comparison could not be made (caller
    1082             :  * must keep both scan keys when this happens).
    1083             :  *
    1084             :  * Note: it's up to caller to deal with IS [NOT] NULL scan keys, as well as
    1085             :  * row comparison scan keys.  We only deal with scalar scan keys.
    1086             :  */
    1087             : static bool
    1088         320 : _bt_compare_array_scankey_args(IndexScanDesc scan, ScanKey arraysk, ScanKey skey,
    1089             :                                FmgrInfo *orderproc, BTArrayKeyInfo *array,
    1090             :                                bool *qual_ok)
    1091             : {
    1092             :     Assert(arraysk->sk_attno == skey->sk_attno);
    1093             :     Assert(!(arraysk->sk_flags & (SK_ISNULL | SK_ROW_HEADER | SK_ROW_MEMBER)));
    1094             :     Assert((arraysk->sk_flags & SK_SEARCHARRAY) &&
    1095             :            arraysk->sk_strategy == BTEqualStrategyNumber);
    1096             :     /* don't expect to have to deal with NULLs/row comparison scan keys */
    1097             :     Assert(!(skey->sk_flags & (SK_ISNULL | SK_ROW_HEADER | SK_ROW_MEMBER)));
    1098             :     Assert(!(skey->sk_flags & SK_SEARCHARRAY) ||
    1099             :            skey->sk_strategy != BTEqualStrategyNumber);
    1100             : 
    1101             :     /*
    1102             :      * Just call the appropriate helper function based on whether it's a SAOP
    1103             :      * array or a skip array.  Both helpers will set *qual_ok in passing.
    1104             :      */
    1105         320 :     if (array->num_elems != -1)
    1106          30 :         return _bt_saoparray_shrink(scan, arraysk, skey, orderproc, array,
    1107             :                                     qual_ok);
    1108             :     else
    1109         290 :         return _bt_skiparray_shrink(scan, skey, array, qual_ok);
    1110             : }
    1111             : 
    1112             : /*
    1113             :  * Preprocessing of SAOP array scan key, used to determine which array
    1114             :  * elements are eliminated as contradictory by a non-array scalar key.
    1115             :  *
    1116             :  * _bt_compare_array_scankey_args helper function.
    1117             :  *
    1118             :  * Array elements can be eliminated as contradictory when excluded by some
    1119             :  * other operator on the same attribute.  For example, with an index scan qual
    1120             :  * "WHERE a IN (1, 2, 3) AND a < 2", all array elements except the value "1"
    1121             :  * are eliminated, and the < scan key is eliminated as redundant.  Cases where
    1122             :  * every array element is eliminated by a redundant scalar scan key have an
    1123             :  * unsatisfiable qual, which we handle by setting *qual_ok=false for caller.
    1124             :  */
    1125             : static bool
    1126          30 : _bt_saoparray_shrink(IndexScanDesc scan, ScanKey arraysk, ScanKey skey,
    1127             :                      FmgrInfo *orderproc, BTArrayKeyInfo *array, bool *qual_ok)
    1128             : {
    1129          30 :     Relation    rel = scan->indexRelation;
    1130          30 :     Oid         opcintype = rel->rd_opcintype[arraysk->sk_attno - 1];
    1131          30 :     int         cmpresult = 0,
    1132          30 :                 cmpexact = 0,
    1133             :                 matchelem,
    1134          30 :                 new_nelems = 0;
    1135             :     FmgrInfo    crosstypeproc;
    1136          30 :     FmgrInfo   *orderprocp = orderproc;
    1137             : 
    1138             :     Assert(array->num_elems > 0);
    1139             :     Assert(!(arraysk->sk_flags & SK_BT_SKIP));
    1140             : 
    1141             :     /*
    1142             :      * _bt_binsrch_array_skey searches an array for the entry best matching a
    1143             :      * datum of opclass input type for the index's attribute (on-disk type).
    1144             :      * We can reuse the array's ORDER proc whenever the non-array scan key's
    1145             :      * type is a match for the corresponding attribute's input opclass type.
    1146             :      * Otherwise, we have to do another ORDER proc lookup so that our call to
    1147             :      * _bt_binsrch_array_skey applies the correct comparator.
    1148             :      *
    1149             :      * Note: we have to support the convention that sk_subtype == InvalidOid
    1150             :      * means the opclass input type; this is a hack to simplify life for
    1151             :      * ScanKeyInit().
    1152             :      */
    1153          30 :     if (skey->sk_subtype != opcintype && skey->sk_subtype != InvalidOid)
    1154             :     {
    1155             :         RegProcedure cmp_proc;
    1156             :         Oid         arraysk_elemtype;
    1157             : 
    1158             :         /*
    1159             :          * Need an ORDER proc lookup to detect redundancy/contradictoriness
    1160             :          * with this pair of scankeys.
    1161             :          *
    1162             :          * Scalar scan key's argument will be passed to _bt_compare_array_skey
    1163             :          * as its tupdatum/lefthand argument (rhs arg is for array elements).
    1164             :          */
    1165           6 :         arraysk_elemtype = arraysk->sk_subtype;
    1166           6 :         if (arraysk_elemtype == InvalidOid)
    1167           0 :             arraysk_elemtype = rel->rd_opcintype[arraysk->sk_attno - 1];
    1168           6 :         cmp_proc = get_opfamily_proc(rel->rd_opfamily[arraysk->sk_attno - 1],
    1169             :                                      skey->sk_subtype, arraysk_elemtype,
    1170             :                                      BTORDER_PROC);
    1171           6 :         if (!RegProcedureIsValid(cmp_proc))
    1172             :         {
    1173             :             /* Can't make the comparison */
    1174           0 :             *qual_ok = false;   /* suppress compiler warnings */
    1175           0 :             return false;
    1176             :         }
    1177             : 
    1178             :         /* We have all we need to determine redundancy/contradictoriness */
    1179           6 :         orderprocp = &crosstypeproc;
    1180           6 :         fmgr_info(cmp_proc, orderprocp);
    1181             :     }
    1182             : 
    1183          30 :     matchelem = _bt_binsrch_array_skey(orderprocp, false,
    1184             :                                        NoMovementScanDirection,
    1185             :                                        skey->sk_argument, false, array,
    1186             :                                        arraysk, &cmpresult);
    1187             : 
    1188          30 :     switch (skey->sk_strategy)
    1189             :     {
    1190           6 :         case BTLessStrategyNumber:
    1191           6 :             cmpexact = 1;       /* exclude exact match, if any */
    1192             :             /* FALL THRU */
    1193           6 :         case BTLessEqualStrategyNumber:
    1194           6 :             if (cmpresult >= cmpexact)
    1195           0 :                 matchelem++;
    1196             :             /* Resize, keeping elements from the start of the array */
    1197           6 :             new_nelems = matchelem;
    1198           6 :             break;
    1199          12 :         case BTEqualStrategyNumber:
    1200          12 :             if (cmpresult != 0)
    1201             :             {
    1202             :                 /* qual is unsatisfiable */
    1203           6 :                 new_nelems = 0;
    1204             :             }
    1205             :             else
    1206             :             {
    1207             :                 /* Shift matching element to the start of the array, resize */
    1208           6 :                 array->elem_values[0] = array->elem_values[matchelem];
    1209           6 :                 new_nelems = 1;
    1210             :             }
    1211          12 :             break;
    1212           6 :         case BTGreaterEqualStrategyNumber:
    1213           6 :             cmpexact = 1;       /* include exact match, if any */
    1214             :             /* FALL THRU */
    1215          12 :         case BTGreaterStrategyNumber:
    1216          12 :             if (cmpresult >= cmpexact)
    1217           6 :                 matchelem++;
    1218             :             /* Shift matching elements to the start of the array, resize */
    1219          12 :             new_nelems = array->num_elems - matchelem;
    1220          12 :             memmove(array->elem_values, array->elem_values + matchelem,
    1221             :                     sizeof(Datum) * new_nelems);
    1222          12 :             break;
    1223           0 :         default:
    1224           0 :             elog(ERROR, "unrecognized StrategyNumber: %d",
    1225             :                  (int) skey->sk_strategy);
    1226             :             break;
    1227             :     }
    1228             : 
    1229             :     Assert(new_nelems >= 0);
    1230             :     Assert(new_nelems <= array->num_elems);
    1231             : 
    1232          30 :     array->num_elems = new_nelems;
    1233          30 :     *qual_ok = new_nelems > 0;
    1234             : 
    1235          30 :     return true;
    1236             : }
    1237             : 
    1238             : /*
    1239             :  * Preprocessing of skip array scan key, used to determine redundancy against
    1240             :  * a non-array scalar scan key (must be an inequality).
    1241             :  *
    1242             :  * _bt_compare_array_scankey_args helper function.
    1243             :  *
    1244             :  * Skip arrays work by procedurally generating their elements as needed, so we
    1245             :  * just store the inequality as the skip array's low_compare or high_compare
    1246             :  * (except when there's already a more restrictive low_compare/high_compare).
    1247             :  * The array's final elements are the range of values that still satisfy the
    1248             :  * array's final low_compare and high_compare.
    1249             :  */
    1250             : static bool
    1251         290 : _bt_skiparray_shrink(IndexScanDesc scan, ScanKey skey, BTArrayKeyInfo *array,
    1252             :                      bool *qual_ok)
    1253             : {
    1254             :     bool        test_result;
    1255             : 
    1256             :     Assert(array->num_elems == -1);
    1257             : 
    1258             :     /*
    1259             :      * Array's index attribute will be constrained by a strict operator/key.
    1260             :      * Array must not "contain a NULL element" (i.e. the scan must not apply
    1261             :      * "IS NULL" qual when it reaches the end of the index that stores NULLs).
    1262             :      */
    1263         290 :     array->null_elem = false;
    1264         290 :     *qual_ok = true;
    1265             : 
    1266             :     /*
    1267             :      * Consider if we should treat caller's scalar scan key as the skip
    1268             :      * array's high_compare or low_compare.
    1269             :      *
    1270             :      * In general the current array element must either be a copy of a value
    1271             :      * taken from an index tuple, or a derivative value generated by opclass's
    1272             :      * skip support function.  That way the scan can always safely assume that
    1273             :      * it's okay to use the only-input-opclass-type proc from so->orderProcs[]
    1274             :      * (they can be cross-type with SAOP arrays, but never with skip arrays).
    1275             :      *
    1276             :      * This approach is enabled by MINVAL/MAXVAL sentinel key markings, which
    1277             :      * can be thought of as representing either the lowest or highest matching
    1278             :      * array element (excluding the NULL element, where applicable, though as
    1279             :      * just discussed it isn't applicable to this range skip array anyway).
    1280             :      * Array keys marked MINVAL/MAXVAL never have a valid datum in their
    1281             :      * sk_argument field.  The scan directly applies the array's low_compare
    1282             :      * key when it encounters MINVAL in the array key proper (just as it
    1283             :      * applies high_compare when it sees MAXVAL set in the array key proper).
    1284             :      * The scan must never use the array's so->orderProcs[] proc against
    1285             :      * low_compare's/high_compare's sk_argument, either (so->orderProcs[] is
    1286             :      * only intended to be used with rhs datums from the array proper/index).
    1287             :      */
    1288         290 :     switch (skey->sk_strategy)
    1289             :     {
    1290         148 :         case BTLessStrategyNumber:
    1291             :         case BTLessEqualStrategyNumber:
    1292         148 :             if (array->high_compare)
    1293             :             {
    1294             :                 /* replace existing high_compare with caller's key? */
    1295           6 :                 if (!_bt_compare_scankey_args(scan, array->high_compare, skey,
    1296             :                                               array->high_compare, NULL, NULL,
    1297             :                                               &test_result))
    1298           0 :                     return false;   /* can't determine more restrictive key */
    1299             : 
    1300           6 :                 if (!test_result)
    1301           6 :                     return true;    /* no, just discard caller's key */
    1302             : 
    1303             :                 /* yes, replace existing high_compare with caller's key */
    1304             :             }
    1305             : 
    1306             :             /* caller's key becomes skip array's high_compare */
    1307         142 :             array->high_compare = skey;
    1308         142 :             break;
    1309         142 :         case BTGreaterEqualStrategyNumber:
    1310             :         case BTGreaterStrategyNumber:
    1311         142 :             if (array->low_compare)
    1312             :             {
    1313             :                 /* replace existing low_compare with caller's key? */
    1314           6 :                 if (!_bt_compare_scankey_args(scan, array->low_compare, skey,
    1315             :                                               array->low_compare, NULL, NULL,
    1316             :                                               &test_result))
    1317           0 :                     return false;   /* can't determine more restrictive key */
    1318             : 
    1319           6 :                 if (!test_result)
    1320           0 :                     return true;    /* no, just discard caller's key */
    1321             : 
    1322             :                 /* yes, replace existing low_compare with caller's key */
    1323             :             }
    1324             : 
    1325             :             /* caller's key becomes skip array's low_compare */
    1326         142 :             array->low_compare = skey;
    1327         142 :             break;
    1328           0 :         case BTEqualStrategyNumber:
    1329             :         default:
    1330           0 :             elog(ERROR, "unrecognized StrategyNumber: %d",
    1331             :                  (int) skey->sk_strategy);
    1332             :             break;
    1333             :     }
    1334             : 
    1335         284 :     return true;
    1336             : }
    1337             : 
    1338             : /*
    1339             :  * Applies the opfamily's skip support routine to convert the skip array's >
    1340             :  * low_compare key (if any) into a >= key, and to convert its < high_compare
    1341             :  * key (if any) into a <= key.  Decrements the high_compare key's sk_argument,
    1342             :  * and/or increments the low_compare key's sk_argument (also adjusts their
    1343             :  * operator strategies, while changing the operator as appropriate).
    1344             :  *
    1345             :  * This optional optimization reduces the number of descents required within
    1346             :  * _bt_first.  Whenever _bt_first is called with a skip array whose current
    1347             :  * array element is the sentinel value MINVAL, using a transformed >= key
    1348             :  * instead of using the original > key makes it safe to include lower-order
    1349             :  * scan keys in the insertion scan key (there must be lower-order scan keys
    1350             :  * after the skip array).  We will avoid an extra _bt_first to find the first
    1351             :  * value in the index > sk_argument -- at least when the first real matching
    1352             :  * value in the index happens to be an exact match for the sk_argument value
    1353             :  * that we produced here by incrementing the original input key's sk_argument.
    1354             :  * (Backwards scans derive the same benefit when they encounter the sentinel
    1355             :  * value MAXVAL, by converting the high_compare key from < to <=.)
    1356             :  *
    1357             :  * Note: The transformation is only correct when it cannot allow the scan to
    1358             :  * overlook matching tuples, but we don't have enough semantic information to
    1359             :  * safely make sure that can't happen during scans with cross-type operators.
    1360             :  * That's why we'll never apply the transformation in cross-type scenarios.
    1361             :  * For example, if we attempted to convert "sales_ts > '2024-01-01'::date"
    1362             :  * into "sales_ts >= '2024-01-02'::date" given a "sales_ts" attribute whose
    1363             :  * input opclass is timestamp_ops, the scan would overlook almost all (or all)
    1364             :  * tuples for sales that fell on '2024-01-01'.
    1365             :  *
    1366             :  * Note: We can safely modify array->low_compare/array->high_compare in place
    1367             :  * because they just point to copies of our scan->keyData[] input scan keys
    1368             :  * (namely the copies returned by _bt_preprocess_array_keys to be used as
    1369             :  * input into the standard preprocessing steps in _bt_preprocess_keys).
    1370             :  * Everything will be reset if there's a rescan.
    1371             :  */
    1372             : static void
    1373          78 : _bt_skiparray_strat_adjust(IndexScanDesc scan, ScanKey arraysk,
    1374             :                            BTArrayKeyInfo *array)
    1375             : {
    1376          78 :     BTScanOpaque so = (BTScanOpaque) scan->opaque;
    1377             :     MemoryContext oldContext;
    1378             : 
    1379             :     /*
    1380             :      * Called last among all preprocessing steps, when the skip array's final
    1381             :      * low_compare and high_compare have both been chosen
    1382             :      */
    1383             :     Assert(arraysk->sk_flags & SK_BT_SKIP);
    1384             :     Assert(array->num_elems == -1 && !array->null_elem && array->sksup);
    1385             : 
    1386          78 :     oldContext = MemoryContextSwitchTo(so->arrayContext);
    1387             : 
    1388          78 :     if (array->high_compare &&
    1389          24 :         array->high_compare->sk_strategy == BTLessStrategyNumber)
    1390          18 :         _bt_skiparray_strat_decrement(scan, arraysk, array);
    1391             : 
    1392          78 :     if (array->low_compare &&
    1393          18 :         array->low_compare->sk_strategy == BTGreaterStrategyNumber)
    1394          12 :         _bt_skiparray_strat_increment(scan, arraysk, array);
    1395             : 
    1396          78 :     MemoryContextSwitchTo(oldContext);
    1397          78 : }
    1398             : 
    1399             : /*
    1400             :  * Convert skip array's > low_compare key into a >= key
    1401             :  */
    1402             : static void
    1403          18 : _bt_skiparray_strat_decrement(IndexScanDesc scan, ScanKey arraysk,
    1404             :                               BTArrayKeyInfo *array)
    1405             : {
    1406          18 :     Relation    rel = scan->indexRelation;
    1407          18 :     Oid         opfamily = rel->rd_opfamily[arraysk->sk_attno - 1],
    1408          18 :                 opcintype = rel->rd_opcintype[arraysk->sk_attno - 1],
    1409             :                 leop;
    1410             :     RegProcedure cmp_proc;
    1411          18 :     ScanKey     high_compare = array->high_compare;
    1412          18 :     Datum       orig_sk_argument = high_compare->sk_argument,
    1413             :                 new_sk_argument;
    1414             :     bool        uflow;
    1415             : 
    1416             :     Assert(high_compare->sk_strategy == BTLessStrategyNumber);
    1417             : 
    1418             :     /*
    1419             :      * Only perform the transformation when the operator type matches the
    1420             :      * index attribute's input opclass type
    1421             :      */
    1422          18 :     if (high_compare->sk_subtype != opcintype &&
    1423           0 :         high_compare->sk_subtype != InvalidOid)
    1424           0 :         return;
    1425             : 
    1426             :     /* Decrement, handling underflow by marking the qual unsatisfiable */
    1427          18 :     new_sk_argument = array->sksup->decrement(rel, orig_sk_argument, &uflow);
    1428          18 :     if (uflow)
    1429             :     {
    1430           0 :         BTScanOpaque so = (BTScanOpaque) scan->opaque;
    1431             : 
    1432           0 :         so->qual_ok = false;
    1433           0 :         return;
    1434             :     }
    1435             : 
    1436             :     /* Look up <= operator (might fail) */
    1437          18 :     leop = get_opfamily_member(opfamily, opcintype, opcintype,
    1438             :                                BTLessEqualStrategyNumber);
    1439          18 :     if (!OidIsValid(leop))
    1440           0 :         return;
    1441          18 :     cmp_proc = get_opcode(leop);
    1442          18 :     if (RegProcedureIsValid(cmp_proc))
    1443             :     {
    1444             :         /* Transform < high_compare key into <= key */
    1445          18 :         fmgr_info(cmp_proc, &high_compare->sk_func);
    1446          18 :         high_compare->sk_argument = new_sk_argument;
    1447          18 :         high_compare->sk_strategy = BTLessEqualStrategyNumber;
    1448             :     }
    1449             : }
    1450             : 
    1451             : /*
    1452             :  * Convert skip array's < low_compare key into a <= key
    1453             :  */
    1454             : static void
    1455          12 : _bt_skiparray_strat_increment(IndexScanDesc scan, ScanKey arraysk,
    1456             :                               BTArrayKeyInfo *array)
    1457             : {
    1458          12 :     Relation    rel = scan->indexRelation;
    1459          12 :     Oid         opfamily = rel->rd_opfamily[arraysk->sk_attno - 1],
    1460          12 :                 opcintype = rel->rd_opcintype[arraysk->sk_attno - 1],
    1461             :                 geop;
    1462             :     RegProcedure cmp_proc;
    1463          12 :     ScanKey     low_compare = array->low_compare;
    1464          12 :     Datum       orig_sk_argument = low_compare->sk_argument,
    1465             :                 new_sk_argument;
    1466             :     bool        oflow;
    1467             : 
    1468             :     Assert(low_compare->sk_strategy == BTGreaterStrategyNumber);
    1469             : 
    1470             :     /*
    1471             :      * Only perform the transformation when the operator type matches the
    1472             :      * index attribute's input opclass type
    1473             :      */
    1474          12 :     if (low_compare->sk_subtype != opcintype &&
    1475           0 :         low_compare->sk_subtype != InvalidOid)
    1476           0 :         return;
    1477             : 
    1478             :     /* Increment, handling overflow by marking the qual unsatisfiable */
    1479          12 :     new_sk_argument = array->sksup->increment(rel, orig_sk_argument, &oflow);
    1480          12 :     if (oflow)
    1481             :     {
    1482           0 :         BTScanOpaque so = (BTScanOpaque) scan->opaque;
    1483             : 
    1484           0 :         so->qual_ok = false;
    1485           0 :         return;
    1486             :     }
    1487             : 
    1488             :     /* Look up >= operator (might fail) */
    1489          12 :     geop = get_opfamily_member(opfamily, opcintype, opcintype,
    1490             :                                BTGreaterEqualStrategyNumber);
    1491          12 :     if (!OidIsValid(geop))
    1492           0 :         return;
    1493          12 :     cmp_proc = get_opcode(geop);
    1494          12 :     if (RegProcedureIsValid(cmp_proc))
    1495             :     {
    1496             :         /* Transform > low_compare key into >= key */
    1497          12 :         fmgr_info(cmp_proc, &low_compare->sk_func);
    1498          12 :         low_compare->sk_argument = new_sk_argument;
    1499          12 :         low_compare->sk_strategy = BTGreaterEqualStrategyNumber;
    1500             :     }
    1501             : }
    1502             : 
    1503             : /*
    1504             :  *  _bt_unmark_keys() -- make superfluous required keys nonrequired after all
    1505             :  *
    1506             :  * When _bt_preprocess_keys fails to eliminate one or more redundant keys, it
    1507             :  * calls here to make sure that no index attribute has more than one > or >=
    1508             :  * key marked required, and no more than one required < or <= key.  Attributes
    1509             :  * with = keys will always get one = key as their required key.  All other
    1510             :  * keys that were initially marked required get "unmarked" here.  That way,
    1511             :  * _bt_first and _bt_checkkeys will reliably agree on which keys to use to
    1512             :  * start and/or to end the scan.
    1513             :  *
    1514             :  * We also relocate keys that become/started out nonrequired to the end of
    1515             :  * so->keyData[].  That way, _bt_first and _bt_checkkeys cannot fail to reach
    1516             :  * a required key due to some earlier nonrequired key getting in the way.
    1517             :  *
    1518             :  * Only call here when _bt_compare_scankey_args returned false at least once
    1519             :  * (otherwise, calling here will just waste cycles).
    1520             :  */
    1521             : static void
    1522           6 : _bt_unmark_keys(IndexScanDesc scan, int *keyDataMap)
    1523             : {
    1524           6 :     BTScanOpaque so = (BTScanOpaque) scan->opaque;
    1525             :     AttrNumber  attno;
    1526             :     bool       *unmarkikey;
    1527             :     int         nunmark,
    1528             :                 nunmarked,
    1529             :                 nkept,
    1530             :                 firsti;
    1531             :     ScanKey     keepKeys,
    1532             :                 unmarkKeys;
    1533           6 :     FmgrInfo   *keepOrderProcs = NULL,
    1534           6 :                *unmarkOrderProcs = NULL;
    1535             :     bool        haveReqEquals,
    1536             :                 haveReqForward,
    1537             :                 haveReqBackward;
    1538             : 
    1539             :     /*
    1540             :      * Do an initial pass over so->keyData[] that determines which keys to
    1541             :      * keep as required.  We expect so->keyData[] to still be in attribute
    1542             :      * order when we're called (though we don't expect any particular order
    1543             :      * among each attribute's keys).
    1544             :      *
    1545             :      * When both equality and inequality keys remain on a single attribute, we
    1546             :      * *must* make sure that exactly one of the equalities remains required.
    1547             :      * Any requiredness markings that we might leave on later keys/attributes
    1548             :      * are predicated on there being required = keys on all prior columns.
    1549             :      */
    1550           6 :     unmarkikey = palloc0(so->numberOfKeys * sizeof(bool));
    1551           6 :     nunmark = 0;
    1552             : 
    1553             :     /* Set things up for first key's attribute */
    1554           6 :     attno = so->keyData[0].sk_attno;
    1555           6 :     firsti = 0;
    1556           6 :     haveReqEquals = false;
    1557           6 :     haveReqForward = false;
    1558           6 :     haveReqBackward = false;
    1559          30 :     for (int i = 0; i < so->numberOfKeys; i++)
    1560             :     {
    1561          24 :         ScanKey     origkey = &so->keyData[i];
    1562             : 
    1563          24 :         if (origkey->sk_attno != attno)
    1564             :         {
    1565             :             /* Reset for next attribute */
    1566          12 :             attno = origkey->sk_attno;
    1567          12 :             firsti = i;
    1568             : 
    1569          12 :             haveReqEquals = false;
    1570          12 :             haveReqForward = false;
    1571          12 :             haveReqBackward = false;
    1572             :         }
    1573             : 
    1574             :         /* Equalities get priority over inequalities */
    1575          24 :         if (haveReqEquals)
    1576             :         {
    1577             :             /*
    1578             :              * We already found the first "=" key for this attribute.  We've
    1579             :              * already decided that all its other keys will be unmarked.
    1580             :              */
    1581             :             Assert(!(origkey->sk_flags & SK_SEARCHNULL));
    1582           0 :             unmarkikey[i] = true;
    1583           0 :             nunmark++;
    1584           0 :             continue;
    1585             :         }
    1586          24 :         else if ((origkey->sk_flags & SK_BT_REQFWD) &&
    1587          18 :                  (origkey->sk_flags & SK_BT_REQBKWD))
    1588             :         {
    1589             :             /*
    1590             :              * Found the first "=" key for attno.  All other attno keys will
    1591             :              * be unmarked.
    1592             :              */
    1593             :             Assert(origkey->sk_strategy == BTEqualStrategyNumber);
    1594             : 
    1595          18 :             haveReqEquals = true;
    1596          24 :             for (int j = firsti; j < i; j++)
    1597             :             {
    1598             :                 /* Unmark any prior inequality keys on attno after all */
    1599           6 :                 if (!unmarkikey[j])
    1600             :                 {
    1601           6 :                     unmarkikey[j] = true;
    1602           6 :                     nunmark++;
    1603             :                 }
    1604             :             }
    1605          18 :             continue;
    1606             :         }
    1607             : 
    1608             :         /* Deal with inequalities next */
    1609           6 :         if ((origkey->sk_flags & SK_BT_REQFWD) && !haveReqForward)
    1610             :         {
    1611           0 :             haveReqForward = true;
    1612           0 :             continue;
    1613             :         }
    1614           6 :         else if ((origkey->sk_flags & SK_BT_REQBKWD) && !haveReqBackward)
    1615             :         {
    1616           6 :             haveReqBackward = true;
    1617           6 :             continue;
    1618             :         }
    1619             : 
    1620             :         /*
    1621             :          * We have either a redundant inequality key that will be unmarked, or
    1622             :          * we have a key that wasn't marked required in the first place
    1623             :          */
    1624           0 :         unmarkikey[i] = true;
    1625           0 :         nunmark++;
    1626             :     }
    1627             : 
    1628             :     /* Should only be called when _bt_compare_scankey_args reported failure */
    1629             :     Assert(nunmark > 0);
    1630             : 
    1631             :     /*
    1632             :      * Next, allocate temp arrays: one for required keys that'll remain
    1633             :      * required, the other for all remaining keys
    1634             :      */
    1635           6 :     unmarkKeys = palloc(nunmark * sizeof(ScanKeyData));
    1636           6 :     keepKeys = palloc((so->numberOfKeys - nunmark) * sizeof(ScanKeyData));
    1637           6 :     nunmarked = 0;
    1638           6 :     nkept = 0;
    1639           6 :     if (so->numArrayKeys)
    1640             :     {
    1641           6 :         unmarkOrderProcs = palloc(nunmark * sizeof(FmgrInfo));
    1642           6 :         keepOrderProcs = palloc((so->numberOfKeys - nunmark) * sizeof(FmgrInfo));
    1643             :     }
    1644             : 
    1645             :     /*
    1646             :      * Next, copy the contents of so->keyData[] into the appropriate temp
    1647             :      * array.
    1648             :      *
    1649             :      * Scans with = array keys need us to maintain invariants around the order
    1650             :      * of so->orderProcs[] and so->arrayKeys[] relative to so->keyData[].  See
    1651             :      * _bt_preprocess_array_keys_final for a full explanation.
    1652             :      */
    1653          30 :     for (int i = 0; i < so->numberOfKeys; i++)
    1654             :     {
    1655          24 :         ScanKey     origkey = &so->keyData[i];
    1656             :         ScanKey     unmark;
    1657             : 
    1658          24 :         if (!unmarkikey[i])
    1659             :         {
    1660             :             /*
    1661             :              * Key gets to keep its original requiredness markings.
    1662             :              *
    1663             :              * Key will stay in its original position, unless we're going to
    1664             :              * unmark an earlier key (in which case this key gets moved back).
    1665             :              */
    1666          18 :             memcpy(keepKeys + nkept, origkey, sizeof(ScanKeyData));
    1667             : 
    1668          18 :             if (so->numArrayKeys)
    1669             :             {
    1670          18 :                 keyDataMap[i] = nkept;
    1671          18 :                 memcpy(keepOrderProcs + nkept, &so->orderProcs[i],
    1672             :                        sizeof(FmgrInfo));
    1673             :             }
    1674             : 
    1675          18 :             nkept++;
    1676          18 :             continue;
    1677             :         }
    1678             : 
    1679             :         /*
    1680             :          * Key will be unmarked as needed, and moved to the end of the array,
    1681             :          * next to other keys that will become (or always were) nonrequired
    1682             :          */
    1683           6 :         unmark = unmarkKeys + nunmarked;
    1684           6 :         memcpy(unmark, origkey, sizeof(ScanKeyData));
    1685             : 
    1686           6 :         if (so->numArrayKeys)
    1687             :         {
    1688           6 :             keyDataMap[i] = (so->numberOfKeys - nunmark) + nunmarked;
    1689           6 :             memcpy(&unmarkOrderProcs[nunmarked], &so->orderProcs[i],
    1690             :                    sizeof(FmgrInfo));
    1691             :         }
    1692             : 
    1693             :         /*
    1694             :          * Preprocessing only generates skip arrays when it knows that they'll
    1695             :          * be the only required = key on the attr.  We'll never unmark them.
    1696             :          */
    1697             :         Assert(!(unmark->sk_flags & SK_BT_SKIP));
    1698             : 
    1699             :         /*
    1700             :          * Also shouldn't have to unmark an IS NULL or an IS NOT NULL key.
    1701             :          * They aren't cross-type, so an incomplete opfamily can't matter.
    1702             :          */
    1703             :         Assert(!(unmark->sk_flags & SK_ISNULL) ||
    1704             :                !(unmark->sk_flags & (SK_BT_REQFWD | SK_BT_REQBKWD)));
    1705             : 
    1706             :         /* Clear requiredness flags on redundant key (and on any subkeys) */
    1707           6 :         unmark->sk_flags &= ~(SK_BT_REQFWD | SK_BT_REQBKWD);
    1708           6 :         if (unmark->sk_flags & SK_ROW_HEADER)
    1709             :         {
    1710           6 :             ScanKey     subkey = (ScanKey) DatumGetPointer(unmark->sk_argument);
    1711             : 
    1712             :             Assert(subkey->sk_strategy == unmark->sk_strategy);
    1713             :             for (;;)
    1714             :             {
    1715           6 :                 Assert(subkey->sk_flags & SK_ROW_MEMBER);
    1716          12 :                 subkey->sk_flags &= ~(SK_BT_REQFWD | SK_BT_REQBKWD);
    1717          12 :                 if (subkey->sk_flags & SK_ROW_END)
    1718           6 :                     break;
    1719           6 :                 subkey++;
    1720             :             }
    1721             :         }
    1722             : 
    1723           6 :         nunmarked++;
    1724             :     }
    1725             : 
    1726             :     /* Copy both temp arrays back into so->keyData[] to reorder */
    1727             :     Assert(nkept == so->numberOfKeys - nunmark);
    1728             :     Assert(nunmarked == nunmark);
    1729           6 :     memcpy(so->keyData, keepKeys, sizeof(ScanKeyData) * nkept);
    1730           6 :     memcpy(so->keyData + nkept, unmarkKeys, sizeof(ScanKeyData) * nunmarked);
    1731             : 
    1732             :     /* Done with temp arrays */
    1733           6 :     pfree(unmarkikey);
    1734           6 :     pfree(keepKeys);
    1735           6 :     pfree(unmarkKeys);
    1736             : 
    1737             :     /*
    1738             :      * Now copy so->orderProcs[] temp entries needed by scans with = array
    1739             :      * keys back (just like with the so->keyData[] temp arrays)
    1740             :      */
    1741           6 :     if (so->numArrayKeys)
    1742             :     {
    1743           6 :         memcpy(so->orderProcs, keepOrderProcs, sizeof(FmgrInfo) * nkept);
    1744           6 :         memcpy(so->orderProcs + nkept, unmarkOrderProcs,
    1745             :                sizeof(FmgrInfo) * nunmarked);
    1746             : 
    1747             :         /* Also fix-up array->scan_key references */
    1748          18 :         for (int arridx = 0; arridx < so->numArrayKeys; arridx++)
    1749             :         {
    1750          12 :             BTArrayKeyInfo *array = &so->arrayKeys[arridx];
    1751             : 
    1752          12 :             array->scan_key = keyDataMap[array->scan_key];
    1753             :         }
    1754             : 
    1755             :         /*
    1756             :          * Sort so->arrayKeys[] based on its new BTArrayKeyInfo.scan_key
    1757             :          * offsets, so that its order matches so->keyData[] order as expected
    1758             :          */
    1759           6 :         qsort(so->arrayKeys, so->numArrayKeys, sizeof(BTArrayKeyInfo),
    1760             :               _bt_reorder_array_cmp);
    1761             : 
    1762             :         /* Done with temp arrays */
    1763           6 :         pfree(unmarkOrderProcs);
    1764           6 :         pfree(keepOrderProcs);
    1765             :     }
    1766           6 : }
    1767             : 
    1768             : /*
    1769             :  * qsort comparator for reordering so->arrayKeys[] BTArrayKeyInfo entries
    1770             :  */
    1771             : static int
    1772           6 : _bt_reorder_array_cmp(const void *a, const void *b)
    1773             : {
    1774           6 :     BTArrayKeyInfo *arraya = (BTArrayKeyInfo *) a;
    1775           6 :     BTArrayKeyInfo *arrayb = (BTArrayKeyInfo *) b;
    1776             : 
    1777           6 :     return pg_cmp_s32(arraya->scan_key, arrayb->scan_key);
    1778             : }
    1779             : 
    1780             : /*
    1781             :  *  _bt_preprocess_array_keys() -- Preprocess SK_SEARCHARRAY scan keys
    1782             :  *
    1783             :  * If there are any SK_SEARCHARRAY scan keys, deconstruct the array(s) and
    1784             :  * set up BTArrayKeyInfo info for each one that is an equality-type key.
    1785             :  * Returns modified scan keys as input for further, standard preprocessing.
    1786             :  *
    1787             :  * Currently we perform two kinds of preprocessing to deal with redundancies.
    1788             :  * For inequality array keys, it's sufficient to find the extreme element
    1789             :  * value and replace the whole array with that scalar value.  This eliminates
    1790             :  * all but one array element as redundant.  Similarly, we are capable of
    1791             :  * "merging together" multiple equality array keys (from two or more input
    1792             :  * scan keys) into a single output scan key containing only the intersecting
    1793             :  * array elements.  This can eliminate many redundant array elements, as well
    1794             :  * as eliminating whole array scan keys as redundant.  It can also allow us to
    1795             :  * detect contradictory quals.
    1796             :  *
    1797             :  * Caller must pass *new_numberOfKeys to give us a way to change the number of
    1798             :  * scan keys that caller treats as input to standard preprocessing steps.  The
    1799             :  * returned array is smaller than scan->keyData[] when we could eliminate a
    1800             :  * redundant array scan key (redundant with another array scan key).  It is
    1801             :  * convenient for _bt_preprocess_keys caller to have to deal with no more than
    1802             :  * one equality strategy array scan key per index attribute.  We'll always be
    1803             :  * able to set things up that way when complete opfamilies are used.
    1804             :  *
    1805             :  * We're also responsible for generating skip arrays (and their associated
    1806             :  * scan keys) here.  This enables skip scan.  We do this for index attributes
    1807             :  * that initially lacked an equality condition within scan->keyData[], iff
    1808             :  * doing so allows a later scan key (that was passed to us in scan->keyData[])
    1809             :  * to be marked required by our _bt_preprocess_keys caller.
    1810             :  *
    1811             :  * We set the scan key references from the scan's BTArrayKeyInfo info array to
    1812             :  * offsets into the temp modified input array returned to caller.  Scans that
    1813             :  * have array keys should call _bt_preprocess_array_keys_final when standard
    1814             :  * preprocessing steps are complete.  This will convert the scan key offset
    1815             :  * references into references to the scan's so->keyData[] output scan keys.
    1816             :  *
    1817             :  * Note: the reason we need to return a temp scan key array, rather than just
    1818             :  * modifying scan->keyData[], is that callers are permitted to call btrescan
    1819             :  * without supplying a new set of scankey data.  Certain other preprocessing
    1820             :  * routines (e.g., _bt_fix_scankey_strategy) _can_ modify scan->keyData[], but
    1821             :  * we can't make that work here because our modifications are non-idempotent.
    1822             :  */
    1823             : static ScanKey
    1824    15770980 : _bt_preprocess_array_keys(IndexScanDesc scan, int *new_numberOfKeys)
    1825             : {
    1826    15770980 :     BTScanOpaque so = (BTScanOpaque) scan->opaque;
    1827    15770980 :     Relation    rel = scan->indexRelation;
    1828    15770980 :     int16      *indoption = rel->rd_indoption;
    1829             :     Oid         skip_eq_ops[INDEX_MAX_KEYS];
    1830             :     int         numArrayKeys,
    1831             :                 numSkipArrayKeys,
    1832             :                 numArrayKeyData;
    1833    15770980 :     AttrNumber  attno_skip = 1;
    1834    15770980 :     int         origarrayatt = InvalidAttrNumber,
    1835    15770980 :                 origarraykey = -1;
    1836    15770980 :     Oid         origelemtype = InvalidOid;
    1837             :     MemoryContext oldContext;
    1838             :     ScanKey     arrayKeyData;   /* modified copy of scan->keyData */
    1839             : 
    1840             :     /*
    1841             :      * Check the number of input array keys within scan->keyData[] input keys
    1842             :      * (also checks if we should add extra skip arrays based on input keys)
    1843             :      */
    1844    15770980 :     numArrayKeys = _bt_num_array_keys(scan, skip_eq_ops, &numSkipArrayKeys);
    1845             : 
    1846             :     /* Quit if nothing to do. */
    1847    15770980 :     if (numArrayKeys == 0)
    1848    15699866 :         return NULL;
    1849             : 
    1850             :     /*
    1851             :      * Estimated final size of arrayKeyData[] array we'll return to our caller
    1852             :      * is the size of the original scan->keyData[] input array, plus space for
    1853             :      * any additional skip array scan keys we'll need to generate below
    1854             :      */
    1855       71114 :     numArrayKeyData = scan->numberOfKeys + numSkipArrayKeys;
    1856             : 
    1857             :     /*
    1858             :      * Make a scan-lifespan context to hold array-associated data, or reset it
    1859             :      * if we already have one from a previous rescan cycle.
    1860             :      */
    1861       71114 :     if (so->arrayContext == NULL)
    1862        4562 :         so->arrayContext = AllocSetContextCreate(CurrentMemoryContext,
    1863             :                                                  "BTree array context",
    1864             :                                                  ALLOCSET_SMALL_SIZES);
    1865             :     else
    1866       66552 :         MemoryContextReset(so->arrayContext);
    1867             : 
    1868       71114 :     oldContext = MemoryContextSwitchTo(so->arrayContext);
    1869             : 
    1870             :     /* Create output scan keys in the workspace context */
    1871       71114 :     arrayKeyData = (ScanKey) palloc(numArrayKeyData * sizeof(ScanKeyData));
    1872             : 
    1873             :     /* Allocate space for per-array data in the workspace context */
    1874       71114 :     so->skipScan = (numSkipArrayKeys > 0);
    1875       71114 :     so->arrayKeys = (BTArrayKeyInfo *) palloc(numArrayKeys * sizeof(BTArrayKeyInfo));
    1876             : 
    1877             :     /* Allocate space for ORDER procs used to help _bt_checkkeys */
    1878       71114 :     so->orderProcs = (FmgrInfo *) palloc(numArrayKeyData * sizeof(FmgrInfo));
    1879             : 
    1880       71114 :     numArrayKeys = 0;
    1881       71114 :     numArrayKeyData = 0;
    1882      144018 :     for (int input_ikey = 0; input_ikey < scan->numberOfKeys; input_ikey++)
    1883             :     {
    1884       72922 :         ScanKey     inkey = scan->keyData + input_ikey,
    1885             :                     cur;
    1886             :         FmgrInfo    sortproc;
    1887       72922 :         FmgrInfo   *sortprocp = &sortproc;
    1888             :         Oid         elemtype;
    1889             :         bool        reverse;
    1890             :         ArrayType  *arrayval;
    1891             :         int16       elmlen;
    1892             :         bool        elmbyval;
    1893             :         char        elmalign;
    1894             :         int         num_elems;
    1895             :         Datum      *elem_values;
    1896             :         bool       *elem_nulls;
    1897             :         int         num_nonnulls;
    1898             : 
    1899             :         /* set up next output scan key */
    1900       72922 :         cur = &arrayKeyData[numArrayKeyData];
    1901             : 
    1902             :         /* Backfill skip arrays for attrs < or <= input key's attr? */
    1903       76732 :         while (numSkipArrayKeys && attno_skip <= inkey->sk_attno)
    1904             :         {
    1905        4632 :             Oid         opfamily = rel->rd_opfamily[attno_skip - 1];
    1906        4632 :             Oid         opcintype = rel->rd_opcintype[attno_skip - 1];
    1907        4632 :             Oid         collation = rel->rd_indcollation[attno_skip - 1];
    1908        4632 :             Oid         eq_op = skip_eq_ops[attno_skip - 1];
    1909             :             CompactAttribute *attr;
    1910             :             RegProcedure cmp_proc;
    1911             : 
    1912        4632 :             if (!OidIsValid(eq_op))
    1913             :             {
    1914             :                 /*
    1915             :                  * Attribute already has an = input key, so don't output a
    1916             :                  * skip array for attno_skip.  Just copy attribute's = input
    1917             :                  * key into arrayKeyData[] once outside this inner loop.
    1918             :                  *
    1919             :                  * Note: When we get here there must be a later attribute that
    1920             :                  * lacks an equality input key, and still needs a skip array
    1921             :                  * (if there wasn't then numSkipArrayKeys would be 0 by now).
    1922             :                  */
    1923             :                 Assert(attno_skip == inkey->sk_attno);
    1924             :                 /* inkey can't be last input key to be marked required: */
    1925             :                 Assert(input_ikey < scan->numberOfKeys - 1);
    1926             : #if 0
    1927             :                 /* Could be a redundant input scan key, so can't do this: */
    1928             :                 Assert(inkey->sk_strategy == BTEqualStrategyNumber ||
    1929             :                        (inkey->sk_flags & SK_SEARCHNULL));
    1930             : #endif
    1931             : 
    1932         822 :                 attno_skip++;
    1933         822 :                 break;
    1934             :             }
    1935             : 
    1936        3810 :             cmp_proc = get_opcode(eq_op);
    1937        3810 :             if (!RegProcedureIsValid(cmp_proc))
    1938           0 :                 elog(ERROR, "missing oprcode for skipping equals operator %u", eq_op);
    1939             : 
    1940        3810 :             ScanKeyEntryInitialize(cur,
    1941             :                                    SK_SEARCHARRAY | SK_BT_SKIP, /* flags */
    1942             :                                    attno_skip,  /* skipped att number */
    1943             :                                    BTEqualStrategyNumber,   /* equality strategy */
    1944             :                                    InvalidOid,  /* opclass input subtype */
    1945             :                                    collation,   /* index column's collation */
    1946             :                                    cmp_proc,    /* equality operator's proc */
    1947             :                                    (Datum) 0);  /* constant */
    1948             : 
    1949             :             /* Initialize generic BTArrayKeyInfo fields */
    1950        3810 :             so->arrayKeys[numArrayKeys].scan_key = numArrayKeyData;
    1951        3810 :             so->arrayKeys[numArrayKeys].num_elems = -1;
    1952             : 
    1953             :             /* Initialize skip array specific BTArrayKeyInfo fields */
    1954        3810 :             attr = TupleDescCompactAttr(RelationGetDescr(rel), attno_skip - 1);
    1955        3810 :             reverse = (indoption[attno_skip - 1] & INDOPTION_DESC) != 0;
    1956        3810 :             so->arrayKeys[numArrayKeys].attlen = attr->attlen;
    1957        3810 :             so->arrayKeys[numArrayKeys].attbyval = attr->attbyval;
    1958        3810 :             so->arrayKeys[numArrayKeys].null_elem = true;    /* for now */
    1959        7620 :             so->arrayKeys[numArrayKeys].sksup =
    1960        3810 :                 PrepareSkipSupportFromOpclass(opfamily, opcintype, reverse);
    1961        3810 :             so->arrayKeys[numArrayKeys].low_compare = NULL; /* for now */
    1962        3810 :             so->arrayKeys[numArrayKeys].high_compare = NULL; /* for now */
    1963             : 
    1964             :             /*
    1965             :              * We'll need a 3-way ORDER proc.  Set that up now.
    1966             :              */
    1967        3810 :             _bt_setup_array_cmp(scan, cur, opcintype,
    1968        3810 :                                 &so->orderProcs[numArrayKeyData], NULL);
    1969             : 
    1970        3810 :             numArrayKeys++;
    1971        3810 :             numArrayKeyData++;  /* keep this scan key/array */
    1972             : 
    1973             :             /* set up next output scan key */
    1974        3810 :             cur = &arrayKeyData[numArrayKeyData];
    1975             : 
    1976             :             /* remember having output this skip array and scan key */
    1977        3810 :             numSkipArrayKeys--;
    1978        3810 :             attno_skip++;
    1979             :         }
    1980             : 
    1981             :         /*
    1982             :          * Provisionally copy scan key into arrayKeyData[] array we'll return
    1983             :          * to _bt_preprocess_keys caller
    1984             :          */
    1985       72922 :         *cur = *inkey;
    1986             : 
    1987       72922 :         if (!(cur->sk_flags & SK_SEARCHARRAY))
    1988             :         {
    1989        5300 :             numArrayKeyData++;  /* keep this non-array scan key */
    1990        5318 :             continue;
    1991             :         }
    1992             : 
    1993             :         /*
    1994             :          * Process SAOP array scan key
    1995             :          */
    1996             :         Assert(!(cur->sk_flags & (SK_ROW_HEADER | SK_SEARCHNULL | SK_SEARCHNOTNULL)));
    1997             : 
    1998             :         /* If array is null as a whole, the scan qual is unsatisfiable */
    1999       67622 :         if (cur->sk_flags & SK_ISNULL)
    2000             :         {
    2001           6 :             so->qual_ok = false;
    2002          18 :             break;
    2003             :         }
    2004             : 
    2005             :         /*
    2006             :          * Deconstruct the array into elements
    2007             :          */
    2008       67616 :         arrayval = DatumGetArrayTypeP(cur->sk_argument);
    2009             :         /* We could cache this data, but not clear it's worth it */
    2010       67616 :         get_typlenbyvalalign(ARR_ELEMTYPE(arrayval),
    2011             :                              &elmlen, &elmbyval, &elmalign);
    2012       67616 :         deconstruct_array(arrayval,
    2013             :                           ARR_ELEMTYPE(arrayval),
    2014             :                           elmlen, elmbyval, elmalign,
    2015             :                           &elem_values, &elem_nulls, &num_elems);
    2016             : 
    2017             :         /*
    2018             :          * Compress out any null elements.  We can ignore them since we assume
    2019             :          * all btree operators are strict.
    2020             :          */
    2021       67616 :         num_nonnulls = 0;
    2022      267910 :         for (int j = 0; j < num_elems; j++)
    2023             :         {
    2024      200294 :             if (!elem_nulls[j])
    2025      200276 :                 elem_values[num_nonnulls++] = elem_values[j];
    2026             :         }
    2027             : 
    2028             :         /* We could pfree(elem_nulls) now, but not worth the cycles */
    2029             : 
    2030             :         /* If there's no non-nulls, the scan qual is unsatisfiable */
    2031       67616 :         if (num_nonnulls == 0)
    2032             :         {
    2033           6 :             so->qual_ok = false;
    2034           6 :             break;
    2035             :         }
    2036             : 
    2037             :         /*
    2038             :          * Determine the nominal datatype of the array elements.  We have to
    2039             :          * support the convention that sk_subtype == InvalidOid means the
    2040             :          * opclass input type; this is a hack to simplify life for
    2041             :          * ScanKeyInit().
    2042             :          */
    2043       67610 :         elemtype = cur->sk_subtype;
    2044       67610 :         if (elemtype == InvalidOid)
    2045           0 :             elemtype = rel->rd_opcintype[cur->sk_attno - 1];
    2046             : 
    2047             :         /*
    2048             :          * If the comparison operator is not equality, then the array qual
    2049             :          * degenerates to a simple comparison against the smallest or largest
    2050             :          * non-null array element, as appropriate.
    2051             :          */
    2052       67610 :         switch (cur->sk_strategy)
    2053             :         {
    2054           6 :             case BTLessStrategyNumber:
    2055             :             case BTLessEqualStrategyNumber:
    2056           6 :                 cur->sk_argument =
    2057           6 :                     _bt_find_extreme_element(scan, cur, elemtype,
    2058             :                                              BTGreaterStrategyNumber,
    2059             :                                              elem_values, num_nonnulls);
    2060           6 :                 numArrayKeyData++;  /* keep this transformed scan key */
    2061           6 :                 continue;
    2062       67598 :             case BTEqualStrategyNumber:
    2063             :                 /* proceed with rest of loop */
    2064       67598 :                 break;
    2065           6 :             case BTGreaterEqualStrategyNumber:
    2066             :             case BTGreaterStrategyNumber:
    2067           6 :                 cur->sk_argument =
    2068           6 :                     _bt_find_extreme_element(scan, cur, elemtype,
    2069             :                                              BTLessStrategyNumber,
    2070             :                                              elem_values, num_nonnulls);
    2071           6 :                 numArrayKeyData++;  /* keep this transformed scan key */
    2072           6 :                 continue;
    2073           0 :             default:
    2074           0 :                 elog(ERROR, "unrecognized StrategyNumber: %d",
    2075             :                      (int) cur->sk_strategy);
    2076             :                 break;
    2077             :         }
    2078             : 
    2079             :         /*
    2080             :          * We'll need a 3-way ORDER proc to perform binary searches for the
    2081             :          * next matching array element.  Set that up now.
    2082             :          *
    2083             :          * Array scan keys with cross-type equality operators will require a
    2084             :          * separate same-type ORDER proc for sorting their array.  Otherwise,
    2085             :          * sortproc just points to the same proc used during binary searches.
    2086             :          */
    2087       67598 :         _bt_setup_array_cmp(scan, cur, elemtype,
    2088       67598 :                             &so->orderProcs[numArrayKeyData], &sortprocp);
    2089             : 
    2090             :         /*
    2091             :          * Sort the non-null elements and eliminate any duplicates.  We must
    2092             :          * sort in the same ordering used by the index column, so that the
    2093             :          * arrays can be advanced in lockstep with the scan's progress through
    2094             :          * the index's key space.
    2095             :          */
    2096       67598 :         reverse = (indoption[cur->sk_attno - 1] & INDOPTION_DESC) != 0;
    2097       67598 :         num_elems = _bt_sort_array_elements(cur, sortprocp, reverse,
    2098             :                                             elem_values, num_nonnulls);
    2099             : 
    2100       67598 :         if (origarrayatt == cur->sk_attno)
    2101             :         {
    2102          12 :             BTArrayKeyInfo *orig = &so->arrayKeys[origarraykey];
    2103             : 
    2104             :             /*
    2105             :              * This array scan key is redundant with a previous equality
    2106             :              * operator array scan key.  Merge the two arrays together to
    2107             :              * eliminate contradictory non-intersecting elements (or try to).
    2108             :              *
    2109             :              * We merge this next array back into attribute's original array.
    2110             :              */
    2111             :             Assert(arrayKeyData[orig->scan_key].sk_attno == cur->sk_attno);
    2112             :             Assert(arrayKeyData[orig->scan_key].sk_collation ==
    2113             :                    cur->sk_collation);
    2114          12 :             if (_bt_merge_arrays(scan, cur, sortprocp, reverse,
    2115             :                                  origelemtype, elemtype,
    2116             :                                  orig->elem_values, &orig->num_elems,
    2117             :                                  elem_values, num_elems))
    2118             :             {
    2119             :                 /* Successfully eliminated this array */
    2120          12 :                 pfree(elem_values);
    2121             : 
    2122             :                 /*
    2123             :                  * If no intersecting elements remain in the original array,
    2124             :                  * the scan qual is unsatisfiable
    2125             :                  */
    2126          12 :                 if (orig->num_elems == 0)
    2127             :                 {
    2128           6 :                     so->qual_ok = false;
    2129           6 :                     break;
    2130             :                 }
    2131             : 
    2132             :                 /* Throw away this scan key/array */
    2133           6 :                 continue;
    2134             :             }
    2135             : 
    2136             :             /*
    2137             :              * Unable to merge this array with previous array due to a lack of
    2138             :              * suitable cross-type opfamily support.  Will need to keep both
    2139             :              * scan keys/arrays.
    2140             :              */
    2141             :         }
    2142             :         else
    2143             :         {
    2144             :             /*
    2145             :              * This array is the first for current index attribute.
    2146             :              *
    2147             :              * If it turns out to not be the last array (that is, if the next
    2148             :              * array is redundantly applied to this same index attribute),
    2149             :              * we'll then treat this array as the attribute's "original" array
    2150             :              * when merging.
    2151             :              */
    2152       67586 :             origarrayatt = cur->sk_attno;
    2153       67586 :             origarraykey = numArrayKeys;
    2154       67586 :             origelemtype = elemtype;
    2155             :         }
    2156             : 
    2157             :         /* Initialize generic BTArrayKeyInfo fields */
    2158       67586 :         so->arrayKeys[numArrayKeys].scan_key = numArrayKeyData;
    2159       67586 :         so->arrayKeys[numArrayKeys].num_elems = num_elems;
    2160             : 
    2161             :         /* Initialize SAOP array specific BTArrayKeyInfo fields */
    2162       67586 :         so->arrayKeys[numArrayKeys].elem_values = elem_values;
    2163       67586 :         so->arrayKeys[numArrayKeys].cur_elem = -1;   /* i.e. invalid */
    2164             : 
    2165       67586 :         numArrayKeys++;
    2166       67586 :         numArrayKeyData++;      /* keep this scan key/array */
    2167             :     }
    2168             : 
    2169             :     Assert(numSkipArrayKeys == 0 || !so->qual_ok);
    2170             : 
    2171             :     /* Set final number of equality-type array keys */
    2172       71114 :     so->numArrayKeys = numArrayKeys;
    2173             :     /* Set number of scan keys in arrayKeyData[] */
    2174       71114 :     *new_numberOfKeys = numArrayKeyData;
    2175             : 
    2176       71114 :     MemoryContextSwitchTo(oldContext);
    2177             : 
    2178       71114 :     return arrayKeyData;
    2179             : }
    2180             : 
    2181             : /*
    2182             :  *  _bt_preprocess_array_keys_final() -- fix up array scan key references
    2183             :  *
    2184             :  * When _bt_preprocess_array_keys performed initial array preprocessing, it
    2185             :  * set each array's array->scan_key to its scankey's arrayKeyData[] offset.
    2186             :  * This function handles translation of the scan key references from the
    2187             :  * BTArrayKeyInfo info array, from input scan key references (to the keys in
    2188             :  * arrayKeyData[]), into output references (to the keys in so->keyData[]).
    2189             :  * Caller's keyDataMap[] array tells us how to perform this remapping.
    2190             :  *
    2191             :  * Also finalizes so->orderProcs[] for the scan.  Arrays already have an ORDER
    2192             :  * proc, which might need to be repositioned to its so->keyData[]-wise offset
    2193             :  * (very much like the remapping that we apply to array->scan_key references).
    2194             :  * Non-array equality strategy scan keys (that survived preprocessing) don't
    2195             :  * yet have an so->orderProcs[] entry, so we set one for them here.
    2196             :  *
    2197             :  * Also converts single-element array scan keys into equivalent non-array
    2198             :  * equality scan keys, which decrements so->numArrayKeys.  It's possible that
    2199             :  * this will leave this new btrescan without any arrays at all.  This isn't
    2200             :  * necessary for correctness; it's just an optimization.  Non-array equality
    2201             :  * scan keys are slightly faster than equivalent array scan keys at runtime.
    2202             :  */
    2203             : static void
    2204        4302 : _bt_preprocess_array_keys_final(IndexScanDesc scan, int *keyDataMap)
    2205             : {
    2206        4302 :     BTScanOpaque so = (BTScanOpaque) scan->opaque;
    2207        4302 :     Relation    rel = scan->indexRelation;
    2208        4302 :     int         arrayidx = 0;
    2209        4302 :     int         last_equal_output_ikey PG_USED_FOR_ASSERTS_ONLY = -1;
    2210             : 
    2211             :     Assert(so->qual_ok);
    2212             : 
    2213             :     /*
    2214             :      * Nothing for us to do when _bt_preprocess_array_keys only had to deal
    2215             :      * with array inequalities
    2216             :      */
    2217        4302 :     if (so->numArrayKeys == 0)
    2218           0 :         return;
    2219             : 
    2220       13788 :     for (int output_ikey = 0; output_ikey < so->numberOfKeys; output_ikey++)
    2221             :     {
    2222        9498 :         ScanKey     outkey = so->keyData + output_ikey;
    2223             :         int         input_ikey;
    2224        9498 :         bool        found PG_USED_FOR_ASSERTS_ONLY = false;
    2225             : 
    2226             :         Assert(outkey->sk_strategy != InvalidStrategy);
    2227             : 
    2228        9498 :         if (outkey->sk_strategy != BTEqualStrategyNumber)
    2229         104 :             continue;
    2230             : 
    2231        9394 :         input_ikey = keyDataMap[output_ikey];
    2232             : 
    2233             :         Assert(last_equal_output_ikey < output_ikey);
    2234             :         Assert(last_equal_output_ikey < input_ikey);
    2235        9394 :         last_equal_output_ikey = output_ikey;
    2236             : 
    2237             :         /*
    2238             :          * We're lazy about looking up ORDER procs for non-array keys, since
    2239             :          * not all input keys become output keys.  Take care of it now.
    2240             :          */
    2241        9394 :         if (!(outkey->sk_flags & SK_SEARCHARRAY))
    2242        4732 :         {
    2243             :             Oid         elemtype;
    2244             : 
    2245             :             /* No need for an ORDER proc given an IS NULL scan key */
    2246        4786 :             if (outkey->sk_flags & SK_SEARCHNULL)
    2247          54 :                 continue;
    2248             : 
    2249             :             /*
    2250             :              * A non-required scan key doesn't need an ORDER proc, either
    2251             :              * (unless it's associated with an array, which this one isn't)
    2252             :              */
    2253        4732 :             if (!(outkey->sk_flags & SK_BT_REQFWD))
    2254           0 :                 continue;
    2255             : 
    2256        4732 :             elemtype = outkey->sk_subtype;
    2257        4732 :             if (elemtype == InvalidOid)
    2258        2550 :                 elemtype = rel->rd_opcintype[outkey->sk_attno - 1];
    2259             : 
    2260        4732 :             _bt_setup_array_cmp(scan, outkey, elemtype,
    2261        4732 :                                 &so->orderProcs[output_ikey], NULL);
    2262        4732 :             continue;
    2263             :         }
    2264             : 
    2265             :         /*
    2266             :          * Reorder existing array scan key so->orderProcs[] entries.
    2267             :          *
    2268             :          * Doing this in-place is safe because preprocessing is required to
    2269             :          * output all equality strategy scan keys in original input order
    2270             :          * (among each group of entries against the same index attribute).
    2271             :          * This is also the order that the arrays themselves appear in.
    2272             :          */
    2273        4608 :         so->orderProcs[output_ikey] = so->orderProcs[input_ikey];
    2274             : 
    2275             :         /* Fix-up array->scan_key references for arrays */
    2276        4608 :         for (; arrayidx < so->numArrayKeys; arrayidx++)
    2277             :         {
    2278        4608 :             BTArrayKeyInfo *array = &so->arrayKeys[arrayidx];
    2279             : 
    2280             :             /*
    2281             :              * All skip arrays must be marked required, and final column can
    2282             :              * never have a skip array
    2283             :              */
    2284             :             Assert(array->num_elems > 0 || array->num_elems == -1);
    2285             :             Assert(array->num_elems != -1 || outkey->sk_flags & SK_BT_REQFWD);
    2286             :             Assert(array->num_elems != -1 ||
    2287             :                    outkey->sk_attno < IndexRelationGetNumberOfKeyAttributes(rel));
    2288             : 
    2289        4608 :             if (array->scan_key == input_ikey)
    2290             :             {
    2291             :                 /* found it */
    2292        4608 :                 array->scan_key = output_ikey;
    2293        4608 :                 found = true;
    2294             : 
    2295             :                 /*
    2296             :                  * Transform array scan keys that have exactly 1 element
    2297             :                  * remaining (following all prior preprocessing) into
    2298             :                  * equivalent non-array scan keys.
    2299             :                  */
    2300        4608 :                 if (array->num_elems == 1)
    2301             :                 {
    2302          18 :                     outkey->sk_flags &= ~SK_SEARCHARRAY;
    2303          18 :                     outkey->sk_argument = array->elem_values[0];
    2304          18 :                     so->numArrayKeys--;
    2305             : 
    2306             :                     /* If we're out of array keys, we can quit right away */
    2307          18 :                     if (so->numArrayKeys == 0)
    2308          12 :                         return;
    2309             : 
    2310             :                     /* Shift other arrays forward */
    2311           6 :                     memmove(array, array + 1,
    2312             :                             sizeof(BTArrayKeyInfo) *
    2313           6 :                             (so->numArrayKeys - arrayidx));
    2314             : 
    2315             :                     /*
    2316             :                      * Don't increment arrayidx (there was an entry that was
    2317             :                      * just shifted forward to the offset at arrayidx, which
    2318             :                      * will still need to be matched)
    2319             :                      */
    2320             :                 }
    2321             :                 else
    2322             :                 {
    2323             :                     /*
    2324             :                      * Any skip array low_compare and high_compare scan keys
    2325             :                      * are now final.  Transform the array's > low_compare key
    2326             :                      * into a >= key (and < high_compare keys into a <= key).
    2327             :                      */
    2328        4590 :                     if (array->num_elems == -1 && array->sksup &&
    2329        3272 :                         !array->null_elem)
    2330          78 :                         _bt_skiparray_strat_adjust(scan, outkey, array);
    2331             : 
    2332             :                     /* Match found, so done with this array */
    2333        4590 :                     arrayidx++;
    2334             :                 }
    2335             : 
    2336        4596 :                 break;
    2337             :             }
    2338             :         }
    2339             : 
    2340             :         Assert(found);
    2341             :     }
    2342             : 
    2343             :     /*
    2344             :      * Parallel index scans require space in shared memory to store the
    2345             :      * current array elements (for arrays kept by preprocessing) to schedule
    2346             :      * the next primitive index scan.  The underlying structure is protected
    2347             :      * using an LWLock, so defensively limit its size.  In practice this can
    2348             :      * only affect parallel scans that use an incomplete opfamily.
    2349             :      */
    2350        4290 :     if (scan->parallel_scan && so->numArrayKeys > INDEX_MAX_KEYS)
    2351           0 :         ereport(ERROR,
    2352             :                 (errcode(ERRCODE_PROGRAM_LIMIT_EXCEEDED),
    2353             :                  errmsg_internal("number of array scan keys left by preprocessing (%d) exceeds the maximum allowed by parallel btree index scans (%d)",
    2354             :                                  so->numArrayKeys, INDEX_MAX_KEYS)));
    2355             : }
    2356             : 
    2357             : /*
    2358             :  *  _bt_num_array_keys() -- determine # of BTArrayKeyInfo entries
    2359             :  *
    2360             :  * _bt_preprocess_array_keys helper function.  Returns the estimated size of
    2361             :  * the scan's BTArrayKeyInfo array, which is guaranteed to be large enough to
    2362             :  * fit every so->arrayKeys[] entry.
    2363             :  *
    2364             :  * Also sets *numSkipArrayKeys_out to the number of skip arrays caller must
    2365             :  * add to the scan keys it'll output.  Caller must add this many skip arrays:
    2366             :  * one array for each of the most significant attributes that lack a = input
    2367             :  * key (IS NULL keys count as = input keys here).  The specific attributes
    2368             :  * that need skip arrays are indicated by initializing skip_eq_ops_out[] arg
    2369             :  * 0-based attribute offset to a valid = op strategy Oid.  We'll only ever set
    2370             :  * skip_eq_ops_out[] entries to InvalidOid for attributes that already have an
    2371             :  * equality key in scan->keyData[] input keys -- and only when there's some
    2372             :  * later "attribute gap" for us to "fill-in" with a skip array.
    2373             :  *
    2374             :  * We're optimistic about skipping working out: we always add exactly the skip
    2375             :  * arrays needed to maximize the number of input scan keys that can ultimately
    2376             :  * be marked as required to continue the scan (but no more).  Given a
    2377             :  * multi-column index on (a, b, c, d), we add skip arrays as follows:
    2378             :  *
    2379             :  * Input keys                       Output keys (after all preprocessing)
    2380             :  * ----------                       -------------------------------------
    2381             :  * a = 1                            a = 1 (no skip arrays)
    2382             :  * b = 42                           skip a AND b = 42
    2383             :  * a = 1 AND b = 42                 a = 1 AND b = 42 (no skip arrays)
    2384             :  * a >= 1 AND b = 42             range skip a AND b = 42
    2385             :  * a = 1 AND b > 42                  a = 1 AND b > 42 (no skip arrays)
    2386             :  * a >= 1 AND a <= 3 AND b = 42       range skip a AND b = 42
    2387             :  * a = 1 AND c <= 27             a = 1 AND skip b AND c <= 27
    2388             :  * a = 1 AND d >= 1                  a = 1 AND skip b AND skip c AND d >= 1
    2389             :  * a = 1 AND b >= 42 AND d > 1        a = 1 AND range skip b AND skip c AND d > 1
    2390             :  */
    2391             : static int
    2392    15770980 : _bt_num_array_keys(IndexScanDesc scan, Oid *skip_eq_ops_out,
    2393             :                    int *numSkipArrayKeys_out)
    2394             : {
    2395    15770980 :     Relation    rel = scan->indexRelation;
    2396    15770980 :     AttrNumber  attno_skip = 1,
    2397    15770980 :                 attno_inkey = 1;
    2398    15770980 :     bool        attno_has_equal = false,
    2399    15770980 :                 attno_has_rowcompare = false;
    2400             :     int         numSAOPArrayKeys,
    2401             :                 numSkipArrayKeys,
    2402             :                 prev_numSkipArrayKeys;
    2403             : 
    2404             :     Assert(scan->numberOfKeys);
    2405             : 
    2406             :     /* Initial pass over input scan keys counts the number of SAOP arrays */
    2407    15770980 :     numSAOPArrayKeys = 0;
    2408    15770980 :     *numSkipArrayKeys_out = prev_numSkipArrayKeys = numSkipArrayKeys = 0;
    2409    40646660 :     for (int i = 0; i < scan->numberOfKeys; i++)
    2410             :     {
    2411    24875680 :         ScanKey     inkey = scan->keyData + i;
    2412             : 
    2413    24875680 :         if (inkey->sk_flags & SK_SEARCHARRAY)
    2414       67622 :             numSAOPArrayKeys++;
    2415             :     }
    2416             : 
    2417             : #ifdef DEBUG_DISABLE_SKIP_SCAN
    2418             :     /* don't attempt to add skip arrays */
    2419             :     return numSAOPArrayKeys;
    2420             : #endif
    2421             : 
    2422    15770980 :     for (int i = 0;; i++)
    2423    24875650 :     {
    2424    40646630 :         ScanKey     inkey = scan->keyData + i;
    2425             : 
    2426             :         /*
    2427             :          * Backfill skip arrays for any wholly omitted attributes prior to
    2428             :          * attno_inkey
    2429             :          */
    2430    40647188 :         while (attno_skip < attno_inkey)
    2431             :         {
    2432         558 :             Oid         opfamily = rel->rd_opfamily[attno_skip - 1];
    2433         558 :             Oid         opcintype = rel->rd_opcintype[attno_skip - 1];
    2434             : 
    2435             :             /* Look up input opclass's equality operator (might fail) */
    2436        1116 :             skip_eq_ops_out[attno_skip - 1] =
    2437         558 :                 get_opfamily_member(opfamily, opcintype, opcintype,
    2438             :                                     BTEqualStrategyNumber);
    2439         558 :             if (!OidIsValid(skip_eq_ops_out[attno_skip - 1]))
    2440             :             {
    2441             :                 /*
    2442             :                  * Cannot generate a skip array for this or later attributes
    2443             :                  * (input opclass lacks an equality strategy operator)
    2444             :                  */
    2445           0 :                 *numSkipArrayKeys_out = prev_numSkipArrayKeys;
    2446           0 :                 return numSAOPArrayKeys + prev_numSkipArrayKeys;
    2447             :             }
    2448             : 
    2449             :             /* plan on adding a backfill skip array for this attribute */
    2450         558 :             numSkipArrayKeys++;
    2451         558 :             attno_skip++;
    2452             :         }
    2453             : 
    2454    40646630 :         prev_numSkipArrayKeys = numSkipArrayKeys;
    2455             : 
    2456             :         /*
    2457             :          * Stop once past the final input scan key.  We deliberately never add
    2458             :          * a skip array for the last input scan key's attribute -- even when
    2459             :          * there are only inequality keys on that attribute.
    2460             :          */
    2461    40646630 :         if (i == scan->numberOfKeys)
    2462    15770962 :             break;
    2463             : 
    2464             :         /*
    2465             :          * Later preprocessing steps cannot merge a RowCompare into a skip
    2466             :          * array, so stop adding skip arrays once we see one.  (Note that we
    2467             :          * can backfill skip arrays before a RowCompare, which will allow keys
    2468             :          * up to and including the RowCompare to be marked required.)
    2469             :          *
    2470             :          * Skip arrays work by maintaining a current array element value,
    2471             :          * which anchors lower-order keys via an implied equality constraint.
    2472             :          * This is incompatible with the current nbtree row comparison design,
    2473             :          * which compares all columns together, as an indivisible group.
    2474             :          * Alternative designs that can be used alongside skip arrays are
    2475             :          * possible, but it's not clear that they're really worth pursuing.
    2476             :          *
    2477             :          * A RowCompare qual "(a, b, c) > (10, 'foo', 42)" is equivalent to
    2478             :          * "(a=10 AND b='foo' AND c>42) OR (a=10 AND b>'foo') OR (a>10)".
    2479             :          * Decomposing this RowCompare into these 3 disjuncts allows each
    2480             :          * disjunct to be executed as a separate "single value" index scan.
    2481             :          * That'll give all 3 scans the ability to add skip arrays in the
    2482             :          * usual way (when there are any scalar keys after the RowCompare).
    2483             :          * Under this scheme, a qual "(a, b, c) > (10, 'foo', 42) AND d = 99"
    2484             :          * performs 3 separate scans, each of which can mark keys up to and
    2485             :          * including its "d = 99" key as required to continue the scan.
    2486             :          */
    2487    24875668 :         if (attno_has_rowcompare)
    2488          18 :             break;
    2489             : 
    2490             :         /*
    2491             :          * Now consider next attno_inkey (or keep going if this is an
    2492             :          * additional scan key against the same attribute)
    2493             :          */
    2494    24875650 :         if (attno_inkey < inkey->sk_attno)
    2495             :         {
    2496             :             /*
    2497             :              * Now add skip array for previous scan key's attribute, though
    2498             :              * only if the attribute has no equality strategy scan keys
    2499             :              */
    2500     9105458 :             if (attno_has_equal)
    2501             :             {
    2502             :                 /* Attributes with an = key must have InvalidOid eq_op set */
    2503     9102206 :                 skip_eq_ops_out[attno_skip - 1] = InvalidOid;
    2504             :             }
    2505             :             else
    2506             :             {
    2507        3252 :                 Oid         opfamily = rel->rd_opfamily[attno_skip - 1];
    2508        3252 :                 Oid         opcintype = rel->rd_opcintype[attno_skip - 1];
    2509             : 
    2510             :                 /* Look up input opclass's equality operator (might fail) */
    2511        6504 :                 skip_eq_ops_out[attno_skip - 1] =
    2512        3252 :                     get_opfamily_member(opfamily, opcintype, opcintype,
    2513             :                                         BTEqualStrategyNumber);
    2514             : 
    2515        3252 :                 if (!OidIsValid(skip_eq_ops_out[attno_skip - 1]))
    2516             :                 {
    2517             :                     /*
    2518             :                      * Input opclass lacks an equality strategy operator, so
    2519             :                      * don't generate a skip array that definitely won't work
    2520             :                      */
    2521           0 :                     break;
    2522             :                 }
    2523             : 
    2524             :                 /* plan on adding a backfill skip array for this attribute */
    2525        3252 :                 numSkipArrayKeys++;
    2526             :             }
    2527             : 
    2528             :             /* Set things up for this new attribute */
    2529     9105458 :             attno_skip++;
    2530     9105458 :             attno_inkey = inkey->sk_attno;
    2531     9105458 :             attno_has_equal = false;
    2532             :         }
    2533             : 
    2534             :         /*
    2535             :          * Track if this attribute's scan keys include any equality strategy
    2536             :          * scan keys (IS NULL keys count as equality keys here).  Also track
    2537             :          * if it has any RowCompare keys.
    2538             :          */
    2539    24875650 :         if (inkey->sk_strategy == BTEqualStrategyNumber ||
    2540     1746162 :             (inkey->sk_flags & SK_SEARCHNULL))
    2541    23129632 :             attno_has_equal = true;
    2542    24875650 :         if (inkey->sk_flags & SK_ROW_HEADER)
    2543          84 :             attno_has_rowcompare = true;
    2544             :     }
    2545             : 
    2546    15770980 :     *numSkipArrayKeys_out = numSkipArrayKeys;
    2547    15770980 :     return numSAOPArrayKeys + numSkipArrayKeys;
    2548             : }
    2549             : 
    2550             : /*
    2551             :  * _bt_find_extreme_element() -- get least or greatest array element
    2552             :  *
    2553             :  * scan and skey identify the index column, whose opfamily determines the
    2554             :  * comparison semantics.  strat should be BTLessStrategyNumber to get the
    2555             :  * least element, or BTGreaterStrategyNumber to get the greatest.
    2556             :  */
    2557             : static Datum
    2558          12 : _bt_find_extreme_element(IndexScanDesc scan, ScanKey skey, Oid elemtype,
    2559             :                          StrategyNumber strat,
    2560             :                          Datum *elems, int nelems)
    2561             : {
    2562          12 :     Relation    rel = scan->indexRelation;
    2563             :     Oid         cmp_op;
    2564             :     RegProcedure cmp_proc;
    2565             :     FmgrInfo    flinfo;
    2566             :     Datum       result;
    2567             :     int         i;
    2568             : 
    2569             :     /*
    2570             :      * Look up the appropriate comparison operator in the opfamily.
    2571             :      *
    2572             :      * Note: it's possible that this would fail, if the opfamily is
    2573             :      * incomplete, but it seems quite unlikely that an opfamily would omit
    2574             :      * non-cross-type comparison operators for any datatype that it supports
    2575             :      * at all.
    2576             :      */
    2577             :     Assert(skey->sk_strategy != BTEqualStrategyNumber);
    2578             :     Assert(OidIsValid(elemtype));
    2579          12 :     cmp_op = get_opfamily_member(rel->rd_opfamily[skey->sk_attno - 1],
    2580             :                                  elemtype,
    2581             :                                  elemtype,
    2582             :                                  strat);
    2583          12 :     if (!OidIsValid(cmp_op))
    2584           0 :         elog(ERROR, "missing operator %d(%u,%u) in opfamily %u",
    2585             :              strat, elemtype, elemtype,
    2586             :              rel->rd_opfamily[skey->sk_attno - 1]);
    2587          12 :     cmp_proc = get_opcode(cmp_op);
    2588          12 :     if (!RegProcedureIsValid(cmp_proc))
    2589           0 :         elog(ERROR, "missing oprcode for operator %u", cmp_op);
    2590             : 
    2591          12 :     fmgr_info(cmp_proc, &flinfo);
    2592             : 
    2593             :     Assert(nelems > 0);
    2594          12 :     result = elems[0];
    2595          36 :     for (i = 1; i < nelems; i++)
    2596             :     {
    2597          24 :         if (DatumGetBool(FunctionCall2Coll(&flinfo,
    2598             :                                            skey->sk_collation,
    2599          24 :                                            elems[i],
    2600             :                                            result)))
    2601           6 :             result = elems[i];
    2602             :     }
    2603             : 
    2604          12 :     return result;
    2605             : }
    2606             : 
    2607             : /*
    2608             :  * _bt_setup_array_cmp() -- Set up array comparison functions
    2609             :  *
    2610             :  * Sets ORDER proc in caller's orderproc argument, which is used during binary
    2611             :  * searches of arrays during the index scan.  Also sets a same-type ORDER proc
    2612             :  * in caller's *sortprocp argument, which is used when sorting the array.
    2613             :  *
    2614             :  * Preprocessing calls here with all equality strategy scan keys (when scan
    2615             :  * uses equality array keys), including those not associated with any array.
    2616             :  * See _bt_advance_array_keys for an explanation of why it'll need to treat
    2617             :  * simple scalar equality scan keys as degenerate single element arrays.
    2618             :  *
    2619             :  * Caller should pass an orderproc pointing to space that'll store the ORDER
    2620             :  * proc for the scan, and a *sortprocp pointing to its own separate space.
    2621             :  * When calling here for a non-array scan key, sortprocp arg should be NULL.
    2622             :  *
    2623             :  * In the common case where we don't need to deal with cross-type operators,
    2624             :  * only one ORDER proc is actually required by caller.  We'll set *sortprocp
    2625             :  * to point to the same memory that caller's orderproc continues to point to.
    2626             :  * Otherwise, *sortprocp will continue to point to caller's own space.  Either
    2627             :  * way, *sortprocp will point to a same-type ORDER proc (since that's the only
    2628             :  * safe way to sort/deduplicate the array associated with caller's scan key).
    2629             :  */
    2630             : static void
    2631       76140 : _bt_setup_array_cmp(IndexScanDesc scan, ScanKey skey, Oid elemtype,
    2632             :                     FmgrInfo *orderproc, FmgrInfo **sortprocp)
    2633             : {
    2634       76140 :     BTScanOpaque so = (BTScanOpaque) scan->opaque;
    2635       76140 :     Relation    rel = scan->indexRelation;
    2636             :     RegProcedure cmp_proc;
    2637       76140 :     Oid         opcintype = rel->rd_opcintype[skey->sk_attno - 1];
    2638             : 
    2639             :     Assert(skey->sk_strategy == BTEqualStrategyNumber);
    2640             :     Assert(OidIsValid(elemtype));
    2641             : 
    2642             :     /*
    2643             :      * If scankey operator is not a cross-type comparison, we can use the
    2644             :      * cached comparison function; otherwise gotta look it up in the catalogs
    2645             :      */
    2646       76140 :     if (elemtype == opcintype)
    2647             :     {
    2648             :         /* Set same-type ORDER procs for caller */
    2649       75870 :         *orderproc = *index_getprocinfo(rel, skey->sk_attno, BTORDER_PROC);
    2650       75870 :         if (sortprocp)
    2651       67592 :             *sortprocp = orderproc;
    2652             : 
    2653       75870 :         return;
    2654             :     }
    2655             : 
    2656             :     /*
    2657             :      * Look up the appropriate cross-type comparison function in the opfamily.
    2658             :      *
    2659             :      * Use the opclass input type as the left hand arg type, and the array
    2660             :      * element type as the right hand arg type (since binary searches use an
    2661             :      * index tuple's attribute value to search for a matching array element).
    2662             :      *
    2663             :      * Note: it's possible that this would fail, if the opfamily is
    2664             :      * incomplete, but only in cases where it's quite likely that _bt_first
    2665             :      * would fail in just the same way (had we not failed before it could).
    2666             :      */
    2667         270 :     cmp_proc = get_opfamily_proc(rel->rd_opfamily[skey->sk_attno - 1],
    2668             :                                  opcintype, elemtype, BTORDER_PROC);
    2669         270 :     if (!RegProcedureIsValid(cmp_proc))
    2670           0 :         elog(ERROR, "missing support function %d(%u,%u) for attribute %d of index \"%s\"",
    2671             :              BTORDER_PROC, opcintype, elemtype, skey->sk_attno,
    2672             :              RelationGetRelationName(rel));
    2673             : 
    2674             :     /* Set cross-type ORDER proc for caller */
    2675         270 :     fmgr_info_cxt(cmp_proc, orderproc, so->arrayContext);
    2676             : 
    2677             :     /* Done if caller doesn't actually have an array they'll need to sort */
    2678         270 :     if (!sortprocp)
    2679         264 :         return;
    2680             : 
    2681             :     /*
    2682             :      * Look up the appropriate same-type comparison function in the opfamily.
    2683             :      *
    2684             :      * Note: it's possible that this would fail, if the opfamily is
    2685             :      * incomplete, but it seems quite unlikely that an opfamily would omit
    2686             :      * non-cross-type comparison procs for any datatype that it supports at
    2687             :      * all.
    2688             :      */
    2689           6 :     cmp_proc = get_opfamily_proc(rel->rd_opfamily[skey->sk_attno - 1],
    2690             :                                  elemtype, elemtype, BTORDER_PROC);
    2691           6 :     if (!RegProcedureIsValid(cmp_proc))
    2692           0 :         elog(ERROR, "missing support function %d(%u,%u) for attribute %d of index \"%s\"",
    2693             :              BTORDER_PROC, elemtype, elemtype,
    2694             :              skey->sk_attno, RelationGetRelationName(rel));
    2695             : 
    2696             :     /* Set same-type ORDER proc for caller */
    2697           6 :     fmgr_info_cxt(cmp_proc, *sortprocp, so->arrayContext);
    2698             : }
    2699             : 
    2700             : /*
    2701             :  * _bt_sort_array_elements() -- sort and de-dup array elements
    2702             :  *
    2703             :  * The array elements are sorted in-place, and the new number of elements
    2704             :  * after duplicate removal is returned.
    2705             :  *
    2706             :  * skey identifies the index column whose opfamily determines the comparison
    2707             :  * semantics, and sortproc is a corresponding ORDER proc.  If reverse is true,
    2708             :  * we sort in descending order.
    2709             :  */
    2710             : static int
    2711       67598 : _bt_sort_array_elements(ScanKey skey, FmgrInfo *sortproc, bool reverse,
    2712             :                         Datum *elems, int nelems)
    2713             : {
    2714             :     BTSortArrayContext cxt;
    2715             : 
    2716       67598 :     if (nelems <= 1)
    2717          52 :         return nelems;          /* no work to do */
    2718             : 
    2719             :     /* Sort the array elements */
    2720       67546 :     cxt.sortproc = sortproc;
    2721       67546 :     cxt.collation = skey->sk_collation;
    2722       67546 :     cxt.reverse = reverse;
    2723       67546 :     qsort_arg(elems, nelems, sizeof(Datum),
    2724             :               _bt_compare_array_elements, &cxt);
    2725             : 
    2726             :     /* Now scan the sorted elements and remove duplicates */
    2727       67546 :     return qunique_arg(elems, nelems, sizeof(Datum),
    2728             :                        _bt_compare_array_elements, &cxt);
    2729             : }
    2730             : 
    2731             : /*
    2732             :  * _bt_merge_arrays() -- merge next array's elements into an original array
    2733             :  *
    2734             :  * Called when preprocessing encounters a pair of array equality scan keys,
    2735             :  * both against the same index attribute (during initial array preprocessing).
    2736             :  * Merging reorganizes caller's original array (the left hand arg) in-place,
    2737             :  * without ever copying elements from one array into the other. (Mixing the
    2738             :  * elements together like this would be wrong, since they don't necessarily
    2739             :  * use the same underlying element type, despite all the other similarities.)
    2740             :  *
    2741             :  * Both arrays must have already been sorted and deduplicated by calling
    2742             :  * _bt_sort_array_elements.  sortproc is the same-type ORDER proc that was
    2743             :  * just used to sort and deduplicate caller's "next" array.  We'll usually be
    2744             :  * able to reuse that order PROC to merge the arrays together now.  If not,
    2745             :  * then we'll perform a separate ORDER proc lookup.
    2746             :  *
    2747             :  * If the opfamily doesn't supply a complete set of cross-type ORDER procs we
    2748             :  * may not be able to determine which elements are contradictory.  If we have
    2749             :  * the required ORDER proc then we return true (and validly set *nelems_orig),
    2750             :  * guaranteeing that at least the next array can be considered redundant.  We
    2751             :  * return false if the required comparisons cannot be made (caller must keep
    2752             :  * both arrays when this happens).
    2753             :  */
    2754             : static bool
    2755          12 : _bt_merge_arrays(IndexScanDesc scan, ScanKey skey, FmgrInfo *sortproc,
    2756             :                  bool reverse, Oid origelemtype, Oid nextelemtype,
    2757             :                  Datum *elems_orig, int *nelems_orig,
    2758             :                  Datum *elems_next, int nelems_next)
    2759             : {
    2760          12 :     Relation    rel = scan->indexRelation;
    2761          12 :     BTScanOpaque so = (BTScanOpaque) scan->opaque;
    2762             :     BTSortArrayContext cxt;
    2763          12 :     int         nelems_orig_start = *nelems_orig,
    2764          12 :                 nelems_orig_merged = 0;
    2765          12 :     FmgrInfo   *mergeproc = sortproc;
    2766             :     FmgrInfo    crosstypeproc;
    2767             : 
    2768             :     Assert(skey->sk_strategy == BTEqualStrategyNumber);
    2769             :     Assert(OidIsValid(origelemtype) && OidIsValid(nextelemtype));
    2770             : 
    2771          12 :     if (origelemtype != nextelemtype)
    2772             :     {
    2773             :         RegProcedure cmp_proc;
    2774             : 
    2775             :         /*
    2776             :          * Cross-array-element-type merging is required, so can't just reuse
    2777             :          * sortproc when merging
    2778             :          */
    2779           6 :         cmp_proc = get_opfamily_proc(rel->rd_opfamily[skey->sk_attno - 1],
    2780             :                                      origelemtype, nextelemtype, BTORDER_PROC);
    2781           6 :         if (!RegProcedureIsValid(cmp_proc))
    2782             :         {
    2783             :             /* Can't make the required comparisons */
    2784           0 :             return false;
    2785             :         }
    2786             : 
    2787             :         /* We have all we need to determine redundancy/contradictoriness */
    2788           6 :         mergeproc = &crosstypeproc;
    2789           6 :         fmgr_info_cxt(cmp_proc, mergeproc, so->arrayContext);
    2790             :     }
    2791             : 
    2792          12 :     cxt.sortproc = mergeproc;
    2793          12 :     cxt.collation = skey->sk_collation;
    2794          12 :     cxt.reverse = reverse;
    2795             : 
    2796          54 :     for (int i = 0, j = 0; i < nelems_orig_start && j < nelems_next;)
    2797             :     {
    2798          42 :         Datum      *oelem = elems_orig + i,
    2799          42 :                    *nelem = elems_next + j;
    2800          42 :         int         res = _bt_compare_array_elements(oelem, nelem, &cxt);
    2801             : 
    2802          42 :         if (res == 0)
    2803             :         {
    2804           6 :             elems_orig[nelems_orig_merged++] = *oelem;
    2805           6 :             i++;
    2806           6 :             j++;
    2807             :         }
    2808          36 :         else if (res < 0)
    2809          24 :             i++;
    2810             :         else                    /* res > 0 */
    2811          12 :             j++;
    2812             :     }
    2813             : 
    2814          12 :     *nelems_orig = nelems_orig_merged;
    2815             : 
    2816          12 :     return true;
    2817             : }
    2818             : 
    2819             : /*
    2820             :  * qsort_arg comparator for sorting array elements
    2821             :  */
    2822             : static int
    2823      301788 : _bt_compare_array_elements(const void *a, const void *b, void *arg)
    2824             : {
    2825      301788 :     Datum       da = *((const Datum *) a);
    2826      301788 :     Datum       db = *((const Datum *) b);
    2827      301788 :     BTSortArrayContext *cxt = (BTSortArrayContext *) arg;
    2828             :     int32       compare;
    2829             : 
    2830      301788 :     compare = DatumGetInt32(FunctionCall2Coll(cxt->sortproc,
    2831             :                                               cxt->collation,
    2832             :                                               da, db));
    2833      301788 :     if (cxt->reverse)
    2834          30 :         INVERT_COMPARE_RESULT(compare);
    2835      301788 :     return compare;
    2836             : }

Generated by: LCOV version 1.16