PostgreSQL Source Code git master
Data Structures | Typedefs | Functions
nbtpreprocesskeys.c File Reference
#include "postgres.h"
#include "access/nbtree.h"
#include "access/relscan.h"
#include "common/int.h"
#include "lib/qunique.h"
#include "utils/array.h"
#include "utils/lsyscache.h"
#include "utils/memutils.h"
#include "utils/rel.h"
Include dependency graph for nbtpreprocesskeys.c:

Go to the source code of this file.

Data Structures

struct   BTScanKeyPreproc
 
struct   BTSortArrayContext
 

Typedefs

typedef struct BTScanKeyPreproc  BTScanKeyPreproc
 
typedef struct BTSortArrayContext  BTSortArrayContext
 

Functions

static bool  _bt_fix_scankey_strategy (ScanKey skey, int16 *indoption)
 
static void  _bt_mark_scankey_required (ScanKey skey)
 
static bool  _bt_compare_scankey_args (IndexScanDesc scan, ScanKey op, ScanKey leftarg, ScanKey rightarg, BTArrayKeyInfo *array, FmgrInfo *orderproc, bool *result)
 
static bool  _bt_compare_array_scankey_args (IndexScanDesc scan, ScanKey arraysk, ScanKey skey, FmgrInfo *orderproc, BTArrayKeyInfo *array, bool *qual_ok)
 
static bool  _bt_saoparray_shrink (IndexScanDesc scan, ScanKey arraysk, ScanKey skey, FmgrInfo *orderproc, BTArrayKeyInfo *array, bool *qual_ok)
 
static bool  _bt_skiparray_shrink (IndexScanDesc scan, ScanKey skey, BTArrayKeyInfo *array, bool *qual_ok)
 
static void  _bt_skiparray_strat_adjust (IndexScanDesc scan, ScanKey arraysk, BTArrayKeyInfo *array)
 
static void  _bt_skiparray_strat_decrement (IndexScanDesc scan, ScanKey arraysk, BTArrayKeyInfo *array)
 
static void  _bt_skiparray_strat_increment (IndexScanDesc scan, ScanKey arraysk, BTArrayKeyInfo *array)
 
static void  _bt_unmark_keys (IndexScanDesc scan, int *keyDataMap)
 
static int  _bt_reorder_array_cmp (const void *a, const void *b)
 
static ScanKey  _bt_preprocess_array_keys (IndexScanDesc scan, int *new_numberOfKeys)
 
static void  _bt_preprocess_array_keys_final (IndexScanDesc scan, int *keyDataMap)
 
static int  _bt_num_array_keys (IndexScanDesc scan, Oid *skip_eq_ops_out, int *numSkipArrayKeys_out)
 
static Datum  _bt_find_extreme_element (IndexScanDesc scan, ScanKey skey, Oid elemtype, StrategyNumber strat, Datum *elems, int nelems)
 
static void  _bt_setup_array_cmp (IndexScanDesc scan, ScanKey skey, Oid elemtype, FmgrInfo *orderproc, FmgrInfo **sortprocp)
 
static int  _bt_sort_array_elements (ScanKey skey, FmgrInfo *sortproc, bool reverse, Datum *elems, int nelems)
 
static bool  _bt_merge_arrays (IndexScanDesc scan, ScanKey skey, FmgrInfo *sortproc, bool reverse, Oid origelemtype, Oid nextelemtype, Datum *elems_orig, int *nelems_orig, Datum *elems_next, int nelems_next)
 
static int  _bt_compare_array_elements (const void *a, const void *b, void *arg)
 
void  _bt_preprocess_keys (IndexScanDesc scan)
 

Typedef Documentation

◆ BTScanKeyPreproc

typedef struct BTScanKeyPreproc BTScanKeyPreproc

◆ BTSortArrayContext

typedef struct BTSortArrayContext BTSortArrayContext

Function Documentation

◆ _bt_compare_array_elements()

static int _bt_compare_array_elements ( const void *  a,
const void *  b,
void *  arg 
)
static

Definition at line 2835 of file nbtpreprocesskeys.c.

2836{
2837 Datum da = *((const Datum *) a);
2838 Datum db = *((const Datum *) b);
2840 int32 compare;
2841
2843 cxt->collation,
2844 da, db));
2845 if (cxt->reverse)
2847 return compare;
2848}
#define INVERT_COMPARE_RESULT(var)
Definition: c.h:1105
int32_t int32
Definition: c.h:534
Datum FunctionCall2Coll(FmgrInfo *flinfo, Oid collation, Datum arg1, Datum arg2)
Definition: fmgr.c:1150
static int compare(const void *arg1, const void *arg2)
Definition: geqo_pool.c:145
b
int b
Definition: isn.c:74
a
int a
Definition: isn.c:73
void * arg
uint64_t Datum
Definition: postgres.h:70
static int32 DatumGetInt32(Datum X)
Definition: postgres.h:212

References a, arg, b, BTSortArrayContext::collation, compare(), DatumGetInt32(), FunctionCall2Coll(), INVERT_COMPARE_RESULT, BTSortArrayContext::reverse, and BTSortArrayContext::sortproc.

Referenced by _bt_merge_arrays(), and _bt_sort_array_elements().

◆ _bt_compare_array_scankey_args()

static bool _bt_compare_array_scankey_args ( IndexScanDesc  scan,
ScanKey  arraysk,
ScanKey  skey,
FmgrInfo *  orderproc,
BTArrayKeyInfo *  array,
bool *  qual_ok 
)
static

Definition at line 1088 of file nbtpreprocesskeys.c.

1091{
1092 Assert(arraysk->sk_attno == skey->sk_attno);
1094 Assert((arraysk->sk_flags & SK_SEARCHARRAY) &&
1096 /* don't expect to have to deal with NULLs/row comparison scan keys */
1098 Assert(!(skey->sk_flags & SK_SEARCHARRAY) ||
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 if (array->num_elems != -1)
1106 return _bt_saoparray_shrink(scan, arraysk, skey, orderproc, array,
1107 qual_ok);
1108 else
1109 return _bt_skiparray_shrink(scan, skey, array, qual_ok);
1110}
Assert(PointerIsAligned(start, uint64))
static bool _bt_saoparray_shrink(IndexScanDesc scan, ScanKey arraysk, ScanKey skey, FmgrInfo *orderproc, BTArrayKeyInfo *array, bool *qual_ok)
static bool _bt_skiparray_shrink(IndexScanDesc scan, ScanKey skey, BTArrayKeyInfo *array, bool *qual_ok)
#define SK_ROW_HEADER
Definition: skey.h:117
#define SK_SEARCHARRAY
Definition: skey.h:120
#define SK_ROW_MEMBER
Definition: skey.h:118
#define SK_ISNULL
Definition: skey.h:115
#define BTEqualStrategyNumber
Definition: stratnum.h:31
int num_elems
Definition: nbtree.h:1038
int sk_flags
Definition: skey.h:66
StrategyNumber sk_strategy
Definition: skey.h:68
AttrNumber sk_attno
Definition: skey.h:67

References _bt_saoparray_shrink(), _bt_skiparray_shrink(), Assert(), BTEqualStrategyNumber, BTArrayKeyInfo::num_elems, ScanKeyData::sk_attno, ScanKeyData::sk_flags, SK_ISNULL, SK_ROW_HEADER, SK_ROW_MEMBER, SK_SEARCHARRAY, and ScanKeyData::sk_strategy.

Referenced by _bt_compare_scankey_args().

◆ _bt_compare_scankey_args()

static bool _bt_compare_scankey_args ( IndexScanDesc  scan,
ScanKey  op,
ScanKey  leftarg,
ScanKey  rightarg,
BTArrayKeyInfo *  array,
FmgrInfo *  orderproc,
bool *  result 
)
static

Definition at line 861 of file nbtpreprocesskeys.c.

865{
866 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 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 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 array->null_elem = false;
895
896 /* IS NOT NULL key (could be leftarg or rightarg) now redundant */
897 *result = true;
898 return true;
899 }
900
901 if (leftarg->sk_flags & SK_ISNULL)
902 {
904 leftnull = true;
905 }
906 else
907 leftnull = false;
908 if (rightarg->sk_flags & SK_ISNULL)
909 {
911 rightnull = true;
912 }
913 else
914 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 strat = op->sk_strategy;
922 if (op->sk_flags & SK_BT_NULLS_FIRST)
923 strat = BTCommuteStrategyNumber(strat);
924
925 switch (strat)
926 {
928 *result = (leftnull < rightnull);
929 break;
931 *result = (leftnull <= rightnull);
932 break;
934 *result = (leftnull == rightnull);
935 break;
937 *result = (leftnull >= rightnull);
938 break;
940 *result = (leftnull > rightnull);
941 break;
942 default:
943 elog(ERROR, "unrecognized StrategyNumber: %d", (int) strat);
944 *result = false; /* keep compiler quiet */
945 break;
946 }
947 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 if ((leftarg->sk_flags | rightarg->sk_flags) & SK_ROW_HEADER)
955 {
956 Assert(!((leftarg->sk_flags | rightarg->sk_flags) & SK_BT_SKIP));
957 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 if (array)
965 {
966 bool leftarray,
967 rightarray;
968
969 leftarray = ((leftarg->sk_flags & SK_SEARCHARRAY) &&
971 rightarray = ((rightarg->sk_flags & SK_SEARCHARRAY) &&
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 if (leftarray && rightarray)
981 {
982 /* Can't make the comparison */
983 *result = false; /* suppress compiler warnings */
984 Assert(!((leftarg->sk_flags | rightarg->sk_flags) & SK_BT_SKIP));
985 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 if (leftarray)
994 return _bt_compare_array_scankey_args(scan, leftarg, rightarg,
995 orderproc, array, result);
996 else if (rightarray)
997 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 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 lefttype = leftarg->sk_subtype;
1016 if (lefttype == InvalidOid)
1017 lefttype = opcintype;
1018 righttype = rightarg->sk_subtype;
1019 if (righttype == InvalidOid)
1020 righttype = opcintype;
1021 optype = op->sk_subtype;
1022 if (optype == InvalidOid)
1023 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 if (lefttype == opcintype && righttype == optype)
1030 {
1031 *result = DatumGetBool(FunctionCall2Coll(&op->sk_func,
1032 op->sk_collation,
1033 leftarg->sk_argument,
1034 rightarg->sk_argument));
1035 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 strat = op->sk_strategy;
1048 if (op->sk_flags & SK_BT_DESC)
1049 strat = BTCommuteStrategyNumber(strat);
1050
1051 cmp_op = get_opfamily_member(rel->rd_opfamily[leftarg->sk_attno - 1],
1052 lefttype,
1053 righttype,
1054 strat);
1055 if (OidIsValid(cmp_op))
1056 {
1057 RegProcedure cmp_proc = get_opcode(cmp_op);
1058
1059 if (RegProcedureIsValid(cmp_proc))
1060 {
1061 *result = DatumGetBool(OidFunctionCall2Coll(cmp_proc,
1062 op->sk_collation,
1063 leftarg->sk_argument,
1064 rightarg->sk_argument));
1065 return true;
1066 }
1067 }
1068
1069 /* Can't make the comparison */
1070 *result = false; /* suppress compiler warnings */
1071 return false;
1072}
#define RegProcedureIsValid(p)
Definition: c.h:776
regproc RegProcedure
Definition: c.h:655
#define OidIsValid(objectId)
Definition: c.h:774
#define ERROR
Definition: elog.h:39
#define elog(elevel,...)
Definition: elog.h:226
Datum OidFunctionCall2Coll(Oid functionId, Oid collation, Datum arg1, Datum arg2)
Definition: fmgr.c:1422
RegProcedure get_opcode(Oid opno)
Definition: lsyscache.c:1452
Oid get_opfamily_member(Oid opfamily, Oid lefttype, Oid righttype, int16 strategy)
Definition: lsyscache.c:168
static bool _bt_compare_array_scankey_args(IndexScanDesc scan, ScanKey arraysk, ScanKey skey, FmgrInfo *orderproc, BTArrayKeyInfo *array, bool *qual_ok)
#define SK_BT_SKIP
Definition: nbtree.h:1137
#define SK_BT_NULLS_FIRST
Definition: nbtree.h:1148
#define SK_BT_DESC
Definition: nbtree.h:1147
#define BTCommuteStrategyNumber(strat)
Definition: nbtree.h:686
static bool DatumGetBool(Datum X)
Definition: postgres.h:100
#define InvalidOid
Definition: postgres_ext.h:37
unsigned int Oid
Definition: postgres_ext.h:32
#define SK_SEARCHNOTNULL
Definition: skey.h:122
#define SK_SEARCHNULL
Definition: skey.h:121
uint16 StrategyNumber
Definition: stratnum.h:22
#define BTGreaterStrategyNumber
Definition: stratnum.h:33
#define BTLessStrategyNumber
Definition: stratnum.h:29
#define BTLessEqualStrategyNumber
Definition: stratnum.h:30
#define BTGreaterEqualStrategyNumber
Definition: stratnum.h:32
bool null_elem
Definition: nbtree.h:1047
Relation indexRelation
Definition: relscan.h:137
Definition: rel.h:56
Oid * rd_opcintype
Definition: rel.h:208
Oid * rd_opfamily
Definition: rel.h:207
Datum sk_argument
Definition: skey.h:72
FmgrInfo sk_func
Definition: skey.h:71
Oid sk_subtype
Definition: skey.h:69
Oid sk_collation
Definition: skey.h:70

References _bt_compare_array_scankey_args(), Assert(), BTCommuteStrategyNumber, BTEqualStrategyNumber, BTGreaterEqualStrategyNumber, BTGreaterStrategyNumber, BTLessEqualStrategyNumber, BTLessStrategyNumber, DatumGetBool(), elog, ERROR, FunctionCall2Coll(), get_opcode(), get_opfamily_member(), IndexScanDescData::indexRelation, InvalidOid, BTArrayKeyInfo::null_elem, BTArrayKeyInfo::num_elems, OidFunctionCall2Coll(), OidIsValid, RelationData::rd_opcintype, RelationData::rd_opfamily, RegProcedureIsValid, ScanKeyData::sk_argument, ScanKeyData::sk_attno, SK_BT_DESC, SK_BT_NULLS_FIRST, SK_BT_SKIP, ScanKeyData::sk_collation, ScanKeyData::sk_flags, ScanKeyData::sk_func, SK_ISNULL, SK_ROW_HEADER, SK_ROW_MEMBER, SK_SEARCHARRAY, SK_SEARCHNOTNULL, SK_SEARCHNULL, ScanKeyData::sk_strategy, and ScanKeyData::sk_subtype.

Referenced by _bt_preprocess_keys(), and _bt_skiparray_shrink().

◆ _bt_find_extreme_element()

static Datum _bt_find_extreme_element ( IndexScanDesc  scan,
ScanKey  skey,
Oid  elemtype,
StrategyNumber  strat,
Datum *  elems,
int  nelems 
)
static

Definition at line 2570 of file nbtpreprocesskeys.c.

2573{
2574 Relation rel = scan->indexRelation;
2575 Oid cmp_op;
2576 RegProcedure cmp_proc;
2577 FmgrInfo flinfo;
2578 Datum result;
2579 int i;
2580
2581 /*
2582 * Look up the appropriate comparison operator in the opfamily.
2583 *
2584 * Note: it's possible that this would fail, if the opfamily is
2585 * incomplete, but it seems quite unlikely that an opfamily would omit
2586 * non-cross-type comparison operators for any datatype that it supports
2587 * at all.
2588 */
2590 Assert(OidIsValid(elemtype));
2591 cmp_op = get_opfamily_member(rel->rd_opfamily[skey->sk_attno - 1],
2592 elemtype,
2593 elemtype,
2594 strat);
2595 if (!OidIsValid(cmp_op))
2596 elog(ERROR, "missing operator %d(%u,%u) in opfamily %u",
2597 strat, elemtype, elemtype,
2598 rel->rd_opfamily[skey->sk_attno - 1]);
2599 cmp_proc = get_opcode(cmp_op);
2600 if (!RegProcedureIsValid(cmp_proc))
2601 elog(ERROR, "missing oprcode for operator %u", cmp_op);
2602
2603 fmgr_info(cmp_proc, &flinfo);
2604
2605 Assert(nelems > 0);
2606 result = elems[0];
2607 for (i = 1; i < nelems; i++)
2608 {
2609 if (DatumGetBool(FunctionCall2Coll(&flinfo,
2610 skey->sk_collation,
2611 elems[i],
2612 result)))
2613 result = elems[i];
2614 }
2615
2616 return result;
2617}
void fmgr_info(Oid functionId, FmgrInfo *finfo)
Definition: fmgr.c:128
i
int i
Definition: isn.c:77
Definition: fmgr.h:57

References Assert(), BTEqualStrategyNumber, DatumGetBool(), elog, ERROR, fmgr_info(), FunctionCall2Coll(), get_opcode(), get_opfamily_member(), i, IndexScanDescData::indexRelation, OidIsValid, RelationData::rd_opfamily, RegProcedureIsValid, ScanKeyData::sk_attno, ScanKeyData::sk_collation, and ScanKeyData::sk_strategy.

Referenced by _bt_preprocess_array_keys().

◆ _bt_fix_scankey_strategy()

static bool _bt_fix_scankey_strategy ( ScanKey  skey,
int16 *  indoption 
)
static

Definition at line 659 of file nbtpreprocesskeys.c.

660{
661 int addflags;
662
663 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 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 skey->sk_flags |= addflags;
692
693 /* Set correct strategy for IS NULL or NOT NULL search */
694 if (skey->sk_flags & SK_SEARCHNULL)
695 {
697 skey->sk_subtype = InvalidOid;
698 skey->sk_collation = InvalidOid;
699 }
700 else if (skey->sk_flags & SK_SEARCHNOTNULL)
701 {
702 if (skey->sk_flags & SK_BT_NULLS_FIRST)
704 else
706 skey->sk_subtype = InvalidOid;
707 skey->sk_collation = InvalidOid;
708 }
709 else
710 {
711 /* regular qual, so it cannot be satisfied */
712 return false;
713 }
714
715 /* Needn't do the rest */
716 return true;
717 }
718
719 /* Adjust strategy for DESC, if we didn't already */
720 if ((addflags & SK_BT_DESC) && !(skey->sk_flags & SK_BT_DESC))
722 skey->sk_flags |= addflags;
723
724 /* If it's a row header, fix row member flags and strategies similarly */
725 if (skey->sk_flags & SK_ROW_HEADER)
726 {
727 ScanKey subkey = (ScanKey) DatumGetPointer(skey->sk_argument);
728
729 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 return false;
734 }
735
736 for (;;)
737 {
738 Assert(subkey->sk_flags & SK_ROW_MEMBER);
739 addflags = indoption[subkey->sk_attno - 1] << SK_BT_INDOPTION_SHIFT;
740 if ((addflags & SK_BT_DESC) && !(subkey->sk_flags & SK_BT_DESC))
742 subkey->sk_flags |= addflags;
743 if (subkey->sk_flags & SK_ROW_END)
744 break;
745 subkey++;
746 }
747 }
748
749 return true;
750}
#define SK_BT_INDOPTION_SHIFT
Definition: nbtree.h:1146
static Pointer DatumGetPointer(Datum X)
Definition: postgres.h:322
#define SK_ROW_END
Definition: skey.h:119
ScanKeyData * ScanKey
Definition: skey.h:75
Definition: skey.h:65

References Assert(), BTCommuteStrategyNumber, BTEqualStrategyNumber, BTGreaterStrategyNumber, BTLessStrategyNumber, DatumGetPointer(), InvalidOid, ScanKeyData::sk_argument, ScanKeyData::sk_attno, SK_BT_DESC, SK_BT_INDOPTION_SHIFT, SK_BT_NULLS_FIRST, ScanKeyData::sk_collation, ScanKeyData::sk_flags, SK_ISNULL, SK_ROW_END, SK_ROW_HEADER, SK_ROW_MEMBER, SK_SEARCHNOTNULL, SK_SEARCHNULL, ScanKeyData::sk_strategy, and ScanKeyData::sk_subtype.

Referenced by _bt_preprocess_keys().

◆ _bt_mark_scankey_required()

static void _bt_mark_scankey_required ( ScanKey  skey )
static

Definition at line 771 of file nbtpreprocesskeys.c.

772{
773 int addflags;
774
775 switch (skey->sk_strategy)
776 {
779 addflags = SK_BT_REQFWD;
780 break;
782 addflags = SK_BT_REQFWD | SK_BT_REQBKWD;
783 break;
786 addflags = SK_BT_REQBKWD;
787 break;
788 default:
789 elog(ERROR, "unrecognized StrategyNumber: %d",
790 (int) skey->sk_strategy);
791 addflags = 0; /* keep compiler quiet */
792 break;
793 }
794
795 skey->sk_flags |= addflags;
796
797 if (skey->sk_flags & SK_ROW_HEADER)
798 {
799 ScanKey subkey = (ScanKey) DatumGetPointer(skey->sk_argument);
800 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 Assert(subkey->sk_flags & SK_ROW_MEMBER);
809 if (subkey->sk_attno != attno)
810 break; /* non-adjacent key, so not required */
811 if (subkey->sk_strategy != skey->sk_strategy)
812 break; /* wrong direction, so not required */
813 subkey->sk_flags |= addflags;
814 if (subkey->sk_flags & SK_ROW_END)
815 break;
816 subkey++;
817 attno++;
818 }
819 }
820}
int16 AttrNumber
Definition: attnum.h:21
#define SK_BT_REQBKWD
Definition: nbtree.h:1136
#define SK_BT_REQFWD
Definition: nbtree.h:1135

References Assert(), BTEqualStrategyNumber, BTGreaterEqualStrategyNumber, BTGreaterStrategyNumber, BTLessEqualStrategyNumber, BTLessStrategyNumber, DatumGetPointer(), elog, ERROR, ScanKeyData::sk_argument, ScanKeyData::sk_attno, SK_BT_REQBKWD, SK_BT_REQFWD, ScanKeyData::sk_flags, SK_ROW_END, SK_ROW_HEADER, SK_ROW_MEMBER, and ScanKeyData::sk_strategy.

Referenced by _bt_preprocess_keys().

◆ _bt_merge_arrays()

static bool _bt_merge_arrays ( IndexScanDesc  scan,
ScanKey  skey,
FmgrInfo *  sortproc,
bool  reverse,
Oid  origelemtype,
Oid  nextelemtype,
Datum *  elems_orig,
int *  nelems_orig,
Datum *  elems_next,
int  nelems_next 
)
static

Definition at line 2767 of file nbtpreprocesskeys.c.

2771{
2772 Relation rel = scan->indexRelation;
2773 BTScanOpaque so = (BTScanOpaque) scan->opaque;
2775 int nelems_orig_start = *nelems_orig,
2776 nelems_orig_merged = 0;
2777 FmgrInfo *mergeproc = sortproc;
2778 FmgrInfo crosstypeproc;
2779
2781 Assert(OidIsValid(origelemtype) && OidIsValid(nextelemtype));
2782
2783 if (origelemtype != nextelemtype)
2784 {
2785 RegProcedure cmp_proc;
2786
2787 /*
2788 * Cross-array-element-type merging is required, so can't just reuse
2789 * sortproc when merging
2790 */
2791 cmp_proc = get_opfamily_proc(rel->rd_opfamily[skey->sk_attno - 1],
2792 origelemtype, nextelemtype, BTORDER_PROC);
2793 if (!RegProcedureIsValid(cmp_proc))
2794 {
2795 /* Can't make the required comparisons */
2796 return false;
2797 }
2798
2799 /* We have all we need to determine redundancy/contradictoriness */
2800 mergeproc = &crosstypeproc;
2801 fmgr_info_cxt(cmp_proc, mergeproc, so->arrayContext);
2802 }
2803
2804 cxt.sortproc = mergeproc;
2805 cxt.collation = skey->sk_collation;
2806 cxt.reverse = reverse;
2807
2808 for (int i = 0, j = 0; i < nelems_orig_start && j < nelems_next;)
2809 {
2810 Datum *oelem = elems_orig + i,
2811 *nelem = elems_next + j;
2812 int res = _bt_compare_array_elements(oelem, nelem, &cxt);
2813
2814 if (res == 0)
2815 {
2816 elems_orig[nelems_orig_merged++] = *oelem;
2817 i++;
2818 j++;
2819 }
2820 else if (res < 0)
2821 i++;
2822 else /* res > 0 */
2823 j++;
2824 }
2825
2826 *nelems_orig = nelems_orig_merged;
2827
2828 return true;
2829}
void fmgr_info_cxt(Oid functionId, FmgrInfo *finfo, MemoryContext mcxt)
Definition: fmgr.c:138
j
int j
Definition: isn.c:78
Oid get_opfamily_proc(Oid opfamily, Oid lefttype, Oid righttype, int16 procnum)
Definition: lsyscache.c:889
static int _bt_compare_array_elements(const void *a, const void *b, void *arg)
#define BTORDER_PROC
Definition: nbtree.h:717
BTScanOpaqueData * BTScanOpaque
Definition: nbtree.h:1097
MemoryContext arrayContext
Definition: nbtree.h:1068
void * opaque
Definition: relscan.h:153

References _bt_compare_array_elements(), BTScanOpaqueData::arrayContext, Assert(), BTEqualStrategyNumber, BTORDER_PROC, fmgr_info_cxt(), get_opfamily_proc(), i, IndexScanDescData::indexRelation, j, OidIsValid, IndexScanDescData::opaque, RelationData::rd_opfamily, RegProcedureIsValid, ScanKeyData::sk_attno, ScanKeyData::sk_collation, and ScanKeyData::sk_strategy.

Referenced by _bt_preprocess_array_keys().

◆ _bt_num_array_keys()

static int _bt_num_array_keys ( IndexScanDesc  scan,
Oid *  skip_eq_ops_out,
int *  numSkipArrayKeys_out 
)
static

Definition at line 2404 of file nbtpreprocesskeys.c.

2406{
2407 Relation rel = scan->indexRelation;
2408 AttrNumber attno_skip = 1,
2409 attno_inkey = 1;
2410 bool attno_has_equal = false,
2411 attno_has_rowcompare = false;
2412 int numSAOPArrayKeys,
2413 numSkipArrayKeys,
2414 prev_numSkipArrayKeys;
2415
2416 Assert(scan->numberOfKeys);
2417
2418 /* Initial pass over input scan keys counts the number of SAOP arrays */
2419 numSAOPArrayKeys = 0;
2420 *numSkipArrayKeys_out = prev_numSkipArrayKeys = numSkipArrayKeys = 0;
2421 for (int i = 0; i < scan->numberOfKeys; i++)
2422 {
2423 ScanKey inkey = scan->keyData + i;
2424
2425 if (inkey->sk_flags & SK_SEARCHARRAY)
2426 numSAOPArrayKeys++;
2427 }
2428
2429#ifdef DEBUG_DISABLE_SKIP_SCAN
2430 /* don't attempt to add skip arrays */
2431 return numSAOPArrayKeys;
2432#endif
2433
2434 for (int i = 0;; i++)
2435 {
2436 ScanKey inkey = scan->keyData + i;
2437
2438 /*
2439 * Backfill skip arrays for any wholly omitted attributes prior to
2440 * attno_inkey
2441 */
2442 while (attno_skip < attno_inkey)
2443 {
2444 Oid opfamily = rel->rd_opfamily[attno_skip - 1];
2445 Oid opcintype = rel->rd_opcintype[attno_skip - 1];
2446
2447 /* Look up input opclass's equality operator (might fail) */
2448 skip_eq_ops_out[attno_skip - 1] =
2449 get_opfamily_member(opfamily, opcintype, opcintype,
2451 if (!OidIsValid(skip_eq_ops_out[attno_skip - 1]))
2452 {
2453 /*
2454 * Cannot generate a skip array for this or later attributes
2455 * (input opclass lacks an equality strategy operator)
2456 */
2457 *numSkipArrayKeys_out = prev_numSkipArrayKeys;
2458 return numSAOPArrayKeys + prev_numSkipArrayKeys;
2459 }
2460
2461 /* plan on adding a backfill skip array for this attribute */
2462 numSkipArrayKeys++;
2463 attno_skip++;
2464 }
2465
2466 prev_numSkipArrayKeys = numSkipArrayKeys;
2467
2468 /*
2469 * Stop once past the final input scan key. We deliberately never add
2470 * a skip array for the last input scan key's attribute -- even when
2471 * there are only inequality keys on that attribute.
2472 */
2473 if (i == scan->numberOfKeys)
2474 break;
2475
2476 /*
2477 * Later preprocessing steps cannot merge a RowCompare into a skip
2478 * array, so stop adding skip arrays once we see one. (Note that we
2479 * can backfill skip arrays before a RowCompare, which will allow keys
2480 * up to and including the RowCompare to be marked required.)
2481 *
2482 * Skip arrays work by maintaining a current array element value,
2483 * which anchors lower-order keys via an implied equality constraint.
2484 * This is incompatible with the current nbtree row comparison design,
2485 * which compares all columns together, as an indivisible group.
2486 * Alternative designs that can be used alongside skip arrays are
2487 * possible, but it's not clear that they're really worth pursuing.
2488 *
2489 * A RowCompare qual "(a, b, c) > (10, 'foo', 42)" is equivalent to
2490 * "(a=10 AND b='foo' AND c>42) OR (a=10 AND b>'foo') OR (a>10)".
2491 * Decomposing this RowCompare into these 3 disjuncts allows each
2492 * disjunct to be executed as a separate "single value" index scan.
2493 * That'll give all 3 scans the ability to add skip arrays in the
2494 * usual way (when there are any scalar keys after the RowCompare).
2495 * Under this scheme, a qual "(a, b, c) > (10, 'foo', 42) AND d = 99"
2496 * performs 3 separate scans, each of which can mark keys up to and
2497 * including its "d = 99" key as required to continue the scan.
2498 */
2499 if (attno_has_rowcompare)
2500 break;
2501
2502 /*
2503 * Now consider next attno_inkey (or keep going if this is an
2504 * additional scan key against the same attribute)
2505 */
2506 if (attno_inkey < inkey->sk_attno)
2507 {
2508 /*
2509 * Now add skip array for previous scan key's attribute, though
2510 * only if the attribute has no equality strategy scan keys
2511 */
2512 if (attno_has_equal)
2513 {
2514 /* Attributes with an = key must have InvalidOid eq_op set */
2515 skip_eq_ops_out[attno_skip - 1] = InvalidOid;
2516 }
2517 else
2518 {
2519 Oid opfamily = rel->rd_opfamily[attno_skip - 1];
2520 Oid opcintype = rel->rd_opcintype[attno_skip - 1];
2521
2522 /* Look up input opclass's equality operator (might fail) */
2523 skip_eq_ops_out[attno_skip - 1] =
2524 get_opfamily_member(opfamily, opcintype, opcintype,
2526
2527 if (!OidIsValid(skip_eq_ops_out[attno_skip - 1]))
2528 {
2529 /*
2530 * Input opclass lacks an equality strategy operator, so
2531 * don't generate a skip array that definitely won't work
2532 */
2533 break;
2534 }
2535
2536 /* plan on adding a backfill skip array for this attribute */
2537 numSkipArrayKeys++;
2538 }
2539
2540 /* Set things up for this new attribute */
2541 attno_skip++;
2542 attno_inkey = inkey->sk_attno;
2543 attno_has_equal = false;
2544 }
2545
2546 /*
2547 * Track if this attribute's scan keys include any equality strategy
2548 * scan keys (IS NULL keys count as equality keys here). Also track
2549 * if it has any RowCompare keys.
2550 */
2551 if (inkey->sk_strategy == BTEqualStrategyNumber ||
2552 (inkey->sk_flags & SK_SEARCHNULL))
2553 attno_has_equal = true;
2554 if (inkey->sk_flags & SK_ROW_HEADER)
2555 attno_has_rowcompare = true;
2556 }
2557
2558 *numSkipArrayKeys_out = numSkipArrayKeys;
2559 return numSAOPArrayKeys + numSkipArrayKeys;
2560}
struct ScanKeyData * keyData
Definition: relscan.h:141
int numberOfKeys
Definition: relscan.h:139

References Assert(), BTEqualStrategyNumber, get_opfamily_member(), i, IndexScanDescData::indexRelation, InvalidOid, IndexScanDescData::keyData, IndexScanDescData::numberOfKeys, OidIsValid, RelationData::rd_opcintype, RelationData::rd_opfamily, ScanKeyData::sk_attno, ScanKeyData::sk_flags, SK_ROW_HEADER, SK_SEARCHARRAY, SK_SEARCHNULL, and ScanKeyData::sk_strategy.

Referenced by _bt_preprocess_array_keys().

◆ _bt_preprocess_array_keys()

static ScanKey _bt_preprocess_array_keys ( IndexScanDesc  scan,
int *  new_numberOfKeys 
)
static

Definition at line 1836 of file nbtpreprocesskeys.c.

1837{
1838 BTScanOpaque so = (BTScanOpaque) scan->opaque;
1839 Relation rel = scan->indexRelation;
1840 int16 *indoption = rel->rd_indoption;
1841 Oid skip_eq_ops[INDEX_MAX_KEYS];
1842 int numArrayKeys,
1843 numSkipArrayKeys,
1844 numArrayKeyData;
1845 AttrNumber attno_skip = 1;
1846 int origarrayatt = InvalidAttrNumber,
1847 origarraykey = -1;
1848 Oid origelemtype = InvalidOid;
1849 MemoryContext oldContext;
1850 ScanKey arrayKeyData; /* modified copy of scan->keyData */
1851
1852 /*
1853 * Check the number of input array keys within scan->keyData[] input keys
1854 * (also checks if we should add extra skip arrays based on input keys)
1855 */
1856 numArrayKeys = _bt_num_array_keys(scan, skip_eq_ops, &numSkipArrayKeys);
1857 so->skipScan = (numSkipArrayKeys > 0);
1858
1859 /* Quit if nothing to do. */
1860 if (numArrayKeys == 0)
1861 return NULL;
1862
1863 /*
1864 * Estimated final size of arrayKeyData[] array we'll return to our caller
1865 * is the size of the original scan->keyData[] input array, plus space for
1866 * any additional skip array scan keys we'll need to generate below
1867 */
1868 numArrayKeyData = scan->numberOfKeys + numSkipArrayKeys;
1869
1870 /*
1871 * Make a scan-lifespan context to hold array-associated data, or reset it
1872 * if we already have one from a previous rescan cycle.
1873 */
1874 if (so->arrayContext == NULL)
1876 "BTree array context",
1878 else
1880
1881 oldContext = MemoryContextSwitchTo(so->arrayContext);
1882
1883 /* Create output scan keys in the workspace context */
1884 arrayKeyData = (ScanKey) palloc(numArrayKeyData * sizeof(ScanKeyData));
1885
1886 /* Allocate space for per-array data in the workspace context */
1887 so->arrayKeys = (BTArrayKeyInfo *) palloc(numArrayKeys * sizeof(BTArrayKeyInfo));
1888
1889 /* Allocate space for ORDER procs used to help _bt_checkkeys */
1890 so->orderProcs = (FmgrInfo *) palloc(numArrayKeyData * sizeof(FmgrInfo));
1891
1892 numArrayKeys = 0;
1893 numArrayKeyData = 0;
1894 for (int input_ikey = 0; input_ikey < scan->numberOfKeys; input_ikey++)
1895 {
1896 ScanKey inkey = scan->keyData + input_ikey,
1897 cur;
1898 FmgrInfo sortproc;
1899 FmgrInfo *sortprocp = &sortproc;
1900 Oid elemtype;
1901 bool reverse;
1902 ArrayType *arrayval;
1903 int16 elmlen;
1904 bool elmbyval;
1905 char elmalign;
1906 int num_elems;
1907 Datum *elem_values;
1908 bool *elem_nulls;
1909 int num_nonnulls;
1910
1911 /* set up next output scan key */
1912 cur = &arrayKeyData[numArrayKeyData];
1913
1914 /* Backfill skip arrays for attrs < or <= input key's attr? */
1915 while (numSkipArrayKeys && attno_skip <= inkey->sk_attno)
1916 {
1917 Oid opfamily = rel->rd_opfamily[attno_skip - 1];
1918 Oid opcintype = rel->rd_opcintype[attno_skip - 1];
1919 Oid collation = rel->rd_indcollation[attno_skip - 1];
1920 Oid eq_op = skip_eq_ops[attno_skip - 1];
1921 CompactAttribute *attr;
1922 RegProcedure cmp_proc;
1923
1924 if (!OidIsValid(eq_op))
1925 {
1926 /*
1927 * Attribute already has an = input key, so don't output a
1928 * skip array for attno_skip. Just copy attribute's = input
1929 * key into arrayKeyData[] once outside this inner loop.
1930 *
1931 * Note: When we get here there must be a later attribute that
1932 * lacks an equality input key, and still needs a skip array
1933 * (if there wasn't then numSkipArrayKeys would be 0 by now).
1934 */
1935 Assert(attno_skip == inkey->sk_attno);
1936 /* inkey can't be last input key to be marked required: */
1937 Assert(input_ikey < scan->numberOfKeys - 1);
1938#if 0
1939 /* Could be a redundant input scan key, so can't do this: */
1941 (inkey->sk_flags & SK_SEARCHNULL));
1942#endif
1943
1944 attno_skip++;
1945 break;
1946 }
1947
1948 cmp_proc = get_opcode(eq_op);
1949 if (!RegProcedureIsValid(cmp_proc))
1950 elog(ERROR, "missing oprcode for skipping equals operator %u", eq_op);
1951
1953 SK_SEARCHARRAY | SK_BT_SKIP, /* flags */
1954 attno_skip, /* skipped att number */
1955 BTEqualStrategyNumber, /* equality strategy */
1956 InvalidOid, /* opclass input subtype */
1957 collation, /* index column's collation */
1958 cmp_proc, /* equality operator's proc */
1959 (Datum) 0); /* constant */
1960
1961 /* Initialize generic BTArrayKeyInfo fields */
1962 so->arrayKeys[numArrayKeys].scan_key = numArrayKeyData;
1963 so->arrayKeys[numArrayKeys].num_elems = -1;
1964
1965 /* Initialize skip array specific BTArrayKeyInfo fields */
1966 attr = TupleDescCompactAttr(RelationGetDescr(rel), attno_skip - 1);
1967 reverse = (indoption[attno_skip - 1] & INDOPTION_DESC) != 0;
1968 so->arrayKeys[numArrayKeys].attlen = attr->attlen;
1969 so->arrayKeys[numArrayKeys].attbyval = attr->attbyval;
1970 so->arrayKeys[numArrayKeys].null_elem = true; /* for now */
1971 so->arrayKeys[numArrayKeys].sksup =
1972 PrepareSkipSupportFromOpclass(opfamily, opcintype, reverse);
1973 so->arrayKeys[numArrayKeys].low_compare = NULL; /* for now */
1974 so->arrayKeys[numArrayKeys].high_compare = NULL; /* for now */
1975
1976 /*
1977 * We'll need a 3-way ORDER proc. Set that up now.
1978 */
1979 _bt_setup_array_cmp(scan, cur, opcintype,
1980 &so->orderProcs[numArrayKeyData], NULL);
1981
1982 numArrayKeys++;
1983 numArrayKeyData++; /* keep this scan key/array */
1984
1985 /* set up next output scan key */
1986 cur = &arrayKeyData[numArrayKeyData];
1987
1988 /* remember having output this skip array and scan key */
1989 numSkipArrayKeys--;
1990 attno_skip++;
1991 }
1992
1993 /*
1994 * Provisionally copy scan key into arrayKeyData[] array we'll return
1995 * to _bt_preprocess_keys caller
1996 */
1997 *cur = *inkey;
1998
1999 if (!(cur->sk_flags & SK_SEARCHARRAY))
2000 {
2001 numArrayKeyData++; /* keep this non-array scan key */
2002 continue;
2003 }
2004
2005 /*
2006 * Process SAOP array scan key
2007 */
2009
2010 /* If array is null as a whole, the scan qual is unsatisfiable */
2011 if (cur->sk_flags & SK_ISNULL)
2012 {
2013 so->qual_ok = false;
2014 break;
2015 }
2016
2017 /*
2018 * Deconstruct the array into elements
2019 */
2020 arrayval = DatumGetArrayTypeP(cur->sk_argument);
2021 /* We could cache this data, but not clear it's worth it */
2023 &elmlen, &elmbyval, &elmalign);
2024 deconstruct_array(arrayval,
2025 ARR_ELEMTYPE(arrayval),
2026 elmlen, elmbyval, elmalign,
2027 &elem_values, &elem_nulls, &num_elems);
2028
2029 /*
2030 * Compress out any null elements. We can ignore them since we assume
2031 * all btree operators are strict.
2032 */
2033 num_nonnulls = 0;
2034 for (int j = 0; j < num_elems; j++)
2035 {
2036 if (!elem_nulls[j])
2037 elem_values[num_nonnulls++] = elem_values[j];
2038 }
2039
2040 /* We could pfree(elem_nulls) now, but not worth the cycles */
2041
2042 /* If there's no non-nulls, the scan qual is unsatisfiable */
2043 if (num_nonnulls == 0)
2044 {
2045 so->qual_ok = false;
2046 break;
2047 }
2048
2049 /*
2050 * Determine the nominal datatype of the array elements. We have to
2051 * support the convention that sk_subtype == InvalidOid means the
2052 * opclass input type; this is a hack to simplify life for
2053 * ScanKeyInit().
2054 */
2055 elemtype = cur->sk_subtype;
2056 if (elemtype == InvalidOid)
2057 elemtype = rel->rd_opcintype[cur->sk_attno - 1];
2058
2059 /*
2060 * If the comparison operator is not equality, then the array qual
2061 * degenerates to a simple comparison against the smallest or largest
2062 * non-null array element, as appropriate.
2063 */
2064 switch (cur->sk_strategy)
2065 {
2068 cur->sk_argument =
2069 _bt_find_extreme_element(scan, cur, elemtype,
2071 elem_values, num_nonnulls);
2072 numArrayKeyData++; /* keep this transformed scan key */
2073 continue;
2075 /* proceed with rest of loop */
2076 break;
2079 cur->sk_argument =
2080 _bt_find_extreme_element(scan, cur, elemtype,
2082 elem_values, num_nonnulls);
2083 numArrayKeyData++; /* keep this transformed scan key */
2084 continue;
2085 default:
2086 elog(ERROR, "unrecognized StrategyNumber: %d",
2087 (int) cur->sk_strategy);
2088 break;
2089 }
2090
2091 /*
2092 * We'll need a 3-way ORDER proc to perform binary searches for the
2093 * next matching array element. Set that up now.
2094 *
2095 * Array scan keys with cross-type equality operators will require a
2096 * separate same-type ORDER proc for sorting their array. Otherwise,
2097 * sortproc just points to the same proc used during binary searches.
2098 */
2099 _bt_setup_array_cmp(scan, cur, elemtype,
2100 &so->orderProcs[numArrayKeyData], &sortprocp);
2101
2102 /*
2103 * Sort the non-null elements and eliminate any duplicates. We must
2104 * sort in the same ordering used by the index column, so that the
2105 * arrays can be advanced in lockstep with the scan's progress through
2106 * the index's key space.
2107 */
2108 reverse = (indoption[cur->sk_attno - 1] & INDOPTION_DESC) != 0;
2109 num_elems = _bt_sort_array_elements(cur, sortprocp, reverse,
2110 elem_values, num_nonnulls);
2111
2112 if (origarrayatt == cur->sk_attno)
2113 {
2114 BTArrayKeyInfo *orig = &so->arrayKeys[origarraykey];
2115
2116 /*
2117 * This array scan key is redundant with a previous equality
2118 * operator array scan key. Merge the two arrays together to
2119 * eliminate contradictory non-intersecting elements (or try to).
2120 *
2121 * We merge this next array back into attribute's original array.
2122 */
2123 Assert(arrayKeyData[orig->scan_key].sk_attno == cur->sk_attno);
2124 Assert(arrayKeyData[orig->scan_key].sk_collation ==
2125 cur->sk_collation);
2126 if (_bt_merge_arrays(scan, cur, sortprocp, reverse,
2127 origelemtype, elemtype,
2128 orig->elem_values, &orig->num_elems,
2129 elem_values, num_elems))
2130 {
2131 /* Successfully eliminated this array */
2132 pfree(elem_values);
2133
2134 /*
2135 * If no intersecting elements remain in the original array,
2136 * the scan qual is unsatisfiable
2137 */
2138 if (orig->num_elems == 0)
2139 {
2140 so->qual_ok = false;
2141 break;
2142 }
2143
2144 /* Throw away this scan key/array */
2145 continue;
2146 }
2147
2148 /*
2149 * Unable to merge this array with previous array due to a lack of
2150 * suitable cross-type opfamily support. Will need to keep both
2151 * scan keys/arrays.
2152 */
2153 }
2154 else
2155 {
2156 /*
2157 * This array is the first for current index attribute.
2158 *
2159 * If it turns out to not be the last array (that is, if the next
2160 * array is redundantly applied to this same index attribute),
2161 * we'll then treat this array as the attribute's "original" array
2162 * when merging.
2163 */
2164 origarrayatt = cur->sk_attno;
2165 origarraykey = numArrayKeys;
2166 origelemtype = elemtype;
2167 }
2168
2169 /* Initialize generic BTArrayKeyInfo fields */
2170 so->arrayKeys[numArrayKeys].scan_key = numArrayKeyData;
2171 so->arrayKeys[numArrayKeys].num_elems = num_elems;
2172
2173 /* Initialize SAOP array specific BTArrayKeyInfo fields */
2174 so->arrayKeys[numArrayKeys].elem_values = elem_values;
2175 so->arrayKeys[numArrayKeys].cur_elem = -1; /* i.e. invalid */
2176
2177 numArrayKeys++;
2178 numArrayKeyData++; /* keep this scan key/array */
2179 }
2180
2181 Assert(numSkipArrayKeys == 0 || !so->qual_ok);
2182
2183 /* Set final number of equality-type array keys */
2184 so->numArrayKeys = numArrayKeys;
2185 /* Set number of scan keys in arrayKeyData[] */
2186 *new_numberOfKeys = numArrayKeyData;
2187
2188 MemoryContextSwitchTo(oldContext);
2189
2190 return arrayKeyData;
2191}
#define DatumGetArrayTypeP(X)
Definition: array.h:261
#define ARR_ELEMTYPE(a)
Definition: array.h:292
void deconstruct_array(ArrayType *array, Oid elmtype, int elmlen, bool elmbyval, char elmalign, Datum **elemsp, bool **nullsp, int *nelemsp)
Definition: arrayfuncs.c:3632
#define InvalidAttrNumber
Definition: attnum.h:23
int16_t int16
Definition: c.h:533
struct cursor * cur
Definition: ecpg.c:29
void get_typlenbyvalalign(Oid typid, int16 *typlen, bool *typbyval, char *typalign)
Definition: lsyscache.c:2438
void MemoryContextReset(MemoryContext context)
Definition: mcxt.c:400
void pfree(void *pointer)
Definition: mcxt.c:1594
void * palloc(Size size)
Definition: mcxt.c:1365
MemoryContext CurrentMemoryContext
Definition: mcxt.c:160
#define AllocSetContextCreate
Definition: memutils.h:129
#define ALLOCSET_SMALL_SIZES
Definition: memutils.h:170
static bool _bt_merge_arrays(IndexScanDesc scan, ScanKey skey, FmgrInfo *sortproc, bool reverse, Oid origelemtype, Oid nextelemtype, Datum *elems_orig, int *nelems_orig, Datum *elems_next, int nelems_next)
static int _bt_num_array_keys(IndexScanDesc scan, Oid *skip_eq_ops_out, int *numSkipArrayKeys_out)
static Datum _bt_find_extreme_element(IndexScanDesc scan, ScanKey skey, Oid elemtype, StrategyNumber strat, Datum *elems, int nelems)
static void _bt_setup_array_cmp(IndexScanDesc scan, ScanKey skey, Oid elemtype, FmgrInfo *orderproc, FmgrInfo **sortprocp)
static int _bt_sort_array_elements(ScanKey skey, FmgrInfo *sortproc, bool reverse, Datum *elems, int nelems)
static MemoryContext MemoryContextSwitchTo(MemoryContext context)
Definition: palloc.h:124
#define INDEX_MAX_KEYS
#define RelationGetDescr(relation)
Definition: rel.h:540
void ScanKeyEntryInitialize(ScanKey entry, int flags, AttrNumber attributeNumber, StrategyNumber strategy, Oid subtype, Oid collation, RegProcedure procedure, Datum argument)
Definition: scankey.c:32
SkipSupport PrepareSkipSupportFromOpclass(Oid opfamily, Oid opcintype, bool reverse)
Definition: skipsupport.c:30
Definition: array.h:93
bool attbyval
Definition: nbtree.h:1046
Datum * elem_values
Definition: nbtree.h:1041
ScanKey high_compare
Definition: nbtree.h:1050
ScanKey low_compare
Definition: nbtree.h:1049
int scan_key
Definition: nbtree.h:1037
SkipSupport sksup
Definition: nbtree.h:1048
int16 attlen
Definition: nbtree.h:1045
int cur_elem
Definition: nbtree.h:1042
bool qual_ok
Definition: nbtree.h:1056
BTArrayKeyInfo * arrayKeys
Definition: nbtree.h:1066
int numArrayKeys
Definition: nbtree.h:1061
FmgrInfo * orderProcs
Definition: nbtree.h:1067
bool skipScan
Definition: nbtree.h:1062
bool attbyval
Definition: tupdesc.h:73
int16 attlen
Definition: tupdesc.h:71
int16 * rd_indoption
Definition: rel.h:211
static CompactAttribute * TupleDescCompactAttr(TupleDesc tupdesc, int i)
Definition: tupdesc.h:175

References _bt_find_extreme_element(), _bt_merge_arrays(), _bt_num_array_keys(), _bt_setup_array_cmp(), _bt_sort_array_elements(), ALLOCSET_SMALL_SIZES, AllocSetContextCreate, ARR_ELEMTYPE, BTScanOpaqueData::arrayContext, BTScanOpaqueData::arrayKeys, Assert(), BTArrayKeyInfo::attbyval, CompactAttribute::attbyval, BTArrayKeyInfo::attlen, CompactAttribute::attlen, BTEqualStrategyNumber, BTGreaterEqualStrategyNumber, BTGreaterStrategyNumber, BTLessEqualStrategyNumber, BTLessStrategyNumber, cur, BTArrayKeyInfo::cur_elem, CurrentMemoryContext, DatumGetArrayTypeP, deconstruct_array(), BTArrayKeyInfo::elem_values, elog, ERROR, get_opcode(), get_typlenbyvalalign(), BTArrayKeyInfo::high_compare, INDEX_MAX_KEYS, IndexScanDescData::indexRelation, InvalidAttrNumber, InvalidOid, j, IndexScanDescData::keyData, BTArrayKeyInfo::low_compare, MemoryContextReset(), MemoryContextSwitchTo(), BTArrayKeyInfo::null_elem, BTArrayKeyInfo::num_elems, BTScanOpaqueData::numArrayKeys, IndexScanDescData::numberOfKeys, OidIsValid, IndexScanDescData::opaque, BTScanOpaqueData::orderProcs, palloc(), pfree(), PrepareSkipSupportFromOpclass(), BTScanOpaqueData::qual_ok, RelationData::rd_indoption, RegProcedureIsValid, RelationGetDescr, BTArrayKeyInfo::scan_key, ScanKeyEntryInitialize(), ScanKeyData::sk_attno, SK_BT_SKIP, ScanKeyData::sk_flags, SK_ISNULL, SK_ROW_HEADER, SK_SEARCHARRAY, SK_SEARCHNOTNULL, SK_SEARCHNULL, ScanKeyData::sk_strategy, BTScanOpaqueData::skipScan, BTArrayKeyInfo::sksup, and TupleDescCompactAttr().

Referenced by _bt_preprocess_keys().

◆ _bt_preprocess_array_keys_final()

static void _bt_preprocess_array_keys_final ( IndexScanDesc  scan,
int *  keyDataMap 
)
static

Definition at line 2216 of file nbtpreprocesskeys.c.

2217{
2218 BTScanOpaque so = (BTScanOpaque) scan->opaque;
2219 Relation rel = scan->indexRelation;
2220 int arrayidx = 0;
2221 int last_equal_output_ikey PG_USED_FOR_ASSERTS_ONLY = -1;
2222
2223 Assert(so->qual_ok);
2224
2225 /*
2226 * Nothing for us to do when _bt_preprocess_array_keys only had to deal
2227 * with array inequalities
2228 */
2229 if (so->numArrayKeys == 0)
2230 return;
2231
2232 for (int output_ikey = 0; output_ikey < so->numberOfKeys; output_ikey++)
2233 {
2234 ScanKey outkey = so->keyData + output_ikey;
2235 int input_ikey;
2236 bool found PG_USED_FOR_ASSERTS_ONLY = false;
2237
2239
2240 if (outkey->sk_strategy != BTEqualStrategyNumber)
2241 continue;
2242
2243 input_ikey = keyDataMap[output_ikey];
2244
2245 Assert(last_equal_output_ikey < output_ikey);
2246 Assert(last_equal_output_ikey < input_ikey);
2247 last_equal_output_ikey = output_ikey;
2248
2249 /*
2250 * We're lazy about looking up ORDER procs for non-array keys, since
2251 * not all input keys become output keys. Take care of it now.
2252 */
2253 if (!(outkey->sk_flags & SK_SEARCHARRAY))
2254 {
2255 Oid elemtype;
2256
2257 /* No need for an ORDER proc given an IS NULL scan key */
2258 if (outkey->sk_flags & SK_SEARCHNULL)
2259 continue;
2260
2261 /*
2262 * A non-required scan key doesn't need an ORDER proc, either
2263 * (unless it's associated with an array, which this one isn't)
2264 */
2265 if (!(outkey->sk_flags & SK_BT_REQFWD))
2266 continue;
2267
2268 elemtype = outkey->sk_subtype;
2269 if (elemtype == InvalidOid)
2270 elemtype = rel->rd_opcintype[outkey->sk_attno - 1];
2271
2272 _bt_setup_array_cmp(scan, outkey, elemtype,
2273 &so->orderProcs[output_ikey], NULL);
2274 continue;
2275 }
2276
2277 /*
2278 * Reorder existing array scan key so->orderProcs[] entries.
2279 *
2280 * Doing this in-place is safe because preprocessing is required to
2281 * output all equality strategy scan keys in original input order
2282 * (among each group of entries against the same index attribute).
2283 * This is also the order that the arrays themselves appear in.
2284 */
2285 so->orderProcs[output_ikey] = so->orderProcs[input_ikey];
2286
2287 /* Fix-up array->scan_key references for arrays */
2288 for (; arrayidx < so->numArrayKeys; arrayidx++)
2289 {
2290 BTArrayKeyInfo *array = &so->arrayKeys[arrayidx];
2291
2292 /*
2293 * All skip arrays must be marked required, and final column can
2294 * never have a skip array
2295 */
2296 Assert(array->num_elems > 0 || array->num_elems == -1);
2297 Assert(array->num_elems != -1 || outkey->sk_flags & SK_BT_REQFWD);
2298 Assert(array->num_elems != -1 ||
2300
2301 if (array->scan_key == input_ikey)
2302 {
2303 /* found it */
2304 array->scan_key = output_ikey;
2305 found = true;
2306
2307 /*
2308 * Transform array scan keys that have exactly 1 element
2309 * remaining (following all prior preprocessing) into
2310 * equivalent non-array scan keys.
2311 */
2312 if (array->num_elems == 1)
2313 {
2314 outkey->sk_flags &= ~SK_SEARCHARRAY;
2315 outkey->sk_argument = array->elem_values[0];
2316 so->numArrayKeys--;
2317
2318 /* If we're out of array keys, we can quit right away */
2319 if (so->numArrayKeys == 0)
2320 return;
2321
2322 /* Shift other arrays forward */
2323 memmove(array, array + 1,
2324 sizeof(BTArrayKeyInfo) *
2325 (so->numArrayKeys - arrayidx));
2326
2327 /*
2328 * Don't increment arrayidx (there was an entry that was
2329 * just shifted forward to the offset at arrayidx, which
2330 * will still need to be matched)
2331 */
2332 }
2333 else
2334 {
2335 /*
2336 * Any skip array low_compare and high_compare scan keys
2337 * are now final. Transform the array's > low_compare key
2338 * into a >= key (and < high_compare keys into a <= key).
2339 */
2340 if (array->num_elems == -1 && array->sksup &&
2341 !array->null_elem)
2342 _bt_skiparray_strat_adjust(scan, outkey, array);
2343
2344 /* Match found, so done with this array */
2345 arrayidx++;
2346 }
2347
2348 break;
2349 }
2350 }
2351
2352 Assert(found);
2353 }
2354
2355 /*
2356 * Parallel index scans require space in shared memory to store the
2357 * current array elements (for arrays kept by preprocessing) to schedule
2358 * the next primitive index scan. The underlying structure is protected
2359 * using an LWLock, so defensively limit its size. In practice this can
2360 * only affect parallel scans that use an incomplete opfamily.
2361 */
2362 if (scan->parallel_scan && so->numArrayKeys > INDEX_MAX_KEYS)
2363 ereport(ERROR,
2364 (errcode(ERRCODE_PROGRAM_LIMIT_EXCEEDED),
2365 errmsg_internal("number of array scan keys left by preprocessing (%d) exceeds the maximum allowed by parallel btree index scans (%d)",
2367}
#define PG_USED_FOR_ASSERTS_ONLY
Definition: c.h:223
int errmsg_internal(const char *fmt,...)
Definition: elog.c:1161
int errcode(int sqlerrcode)
Definition: elog.c:854
#define ereport(elevel,...)
Definition: elog.h:150
static void _bt_skiparray_strat_adjust(IndexScanDesc scan, ScanKey arraysk, BTArrayKeyInfo *array)
#define IndexRelationGetNumberOfKeyAttributes(relation)
Definition: rel.h:533
#define InvalidStrategy
Definition: stratnum.h:24
int numberOfKeys
Definition: nbtree.h:1057
ScanKey keyData
Definition: nbtree.h:1058
struct ParallelIndexScanDescData * parallel_scan
Definition: relscan.h:191

References _bt_setup_array_cmp(), _bt_skiparray_strat_adjust(), BTScanOpaqueData::arrayKeys, Assert(), BTEqualStrategyNumber, BTArrayKeyInfo::elem_values, ereport, errcode(), errmsg_internal(), ERROR, INDEX_MAX_KEYS, IndexScanDescData::indexRelation, IndexRelationGetNumberOfKeyAttributes, InvalidOid, InvalidStrategy, BTScanOpaqueData::keyData, BTArrayKeyInfo::null_elem, BTArrayKeyInfo::num_elems, BTScanOpaqueData::numArrayKeys, BTScanOpaqueData::numberOfKeys, IndexScanDescData::opaque, BTScanOpaqueData::orderProcs, IndexScanDescData::parallel_scan, PG_USED_FOR_ASSERTS_ONLY, BTScanOpaqueData::qual_ok, BTArrayKeyInfo::scan_key, ScanKeyData::sk_argument, ScanKeyData::sk_attno, SK_BT_REQFWD, ScanKeyData::sk_flags, SK_SEARCHARRAY, SK_SEARCHNULL, ScanKeyData::sk_strategy, ScanKeyData::sk_subtype, and BTArrayKeyInfo::sksup.

Referenced by _bt_preprocess_keys().

◆ _bt_preprocess_keys()

void _bt_preprocess_keys ( IndexScanDesc  scan )

Definition at line 194 of file nbtpreprocesskeys.c.

195{
196 BTScanOpaque so = (BTScanOpaque) scan->opaque;
197 int numberOfKeys = scan->numberOfKeys;
198 int16 *indoption = scan->indexRelation->rd_indoption;
199 int new_numberOfKeys;
200 int numberOfEqualCols;
201 ScanKey inkeys;
203 bool test_result,
204 redundant_key_kept = false;
205 AttrNumber attno;
206 ScanKey arrayKeyData;
207 int *keyDataMap = NULL;
208 int arrayidx = 0;
209
210 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 return;
217 }
218
219 /* initialize result variables */
220 so->qual_ok = true;
221 so->numberOfKeys = 0;
222
223 if (numberOfKeys < 1)
224 return; /* done if qual-less scan */
225
226 /* If any keys are SK_SEARCHARRAY type, set up array-key info */
227 arrayKeyData = _bt_preprocess_array_keys(scan, &numberOfKeys);
228 if (!so->qual_ok)
229 {
230 /* unmatchable array, so give up */
231 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 if (arrayKeyData)
240 {
241 inkeys = arrayKeyData;
242
243 /* Also maintain keyDataMap for remapping so->orderProcs[] later */
244 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 if (numberOfKeys > scan->numberOfKeys)
252 so->keyData = repalloc(so->keyData,
253 numberOfKeys * sizeof(ScanKeyData));
254 }
255 else
256 inkeys = scan->keyData;
257
258 /* we check that input keys are correctly ordered */
259 if (inkeys[0].sk_attno < 1)
260 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 if (numberOfKeys == 1)
264 {
265 /* Apply indoption to scankey (might change sk_strategy!) */
266 if (!_bt_fix_scankey_strategy(&inkeys[0], indoption))
267 so->qual_ok = false;
268 memcpy(&so->keyData[0], &inkeys[0], sizeof(ScanKeyData));
269 so->numberOfKeys = 1;
270 /* We can mark the qual as required if it's for first index col */
271 if (inkeys[0].sk_attno == 1)
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 */
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 return;
288 }
289
290 /*
291 * Otherwise, do the full set of pushups.
292 */
293 new_numberOfKeys = 0;
294 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 attno = 1;
303 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 for (int i = 0;; i++)
311 {
312 ScanKey inkey = inkeys + i;
313 int j;
314
315 if (i < numberOfKeys)
316 {
317 /* Apply indoption to scankey (might change sk_strategy!) */
318 if (!_bt_fix_scankey_strategy(inkey, indoption))
319 {
320 /* NULL can't be matched, so give up */
321 so->qual_ok = false;
322 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 if (i == numberOfKeys || inkey->sk_attno != attno)
331 {
332 int priorNumberOfEqualCols = numberOfEqualCols;
333
334 /* check input keys are correctly ordered */
335 if (i < numberOfKeys && inkey->sk_attno < attno)
336 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 if (xform[BTEqualStrategyNumber - 1].inkey)
357 {
358 ScanKey eq = xform[BTEqualStrategyNumber - 1].inkey;
359 BTArrayKeyInfo *array = NULL;
360 FmgrInfo *orderproc = NULL;
361
362 if (arrayKeyData && (eq->sk_flags & SK_SEARCHARRAY))
363 {
364 int eq_in_ikey,
365 eq_arrayidx;
366
367 eq_in_ikey = xform[BTEqualStrategyNumber - 1].inkeyi;
368 eq_arrayidx = xform[BTEqualStrategyNumber - 1].arrayidx;
369 array = &so->arrayKeys[eq_arrayidx - 1];
370 orderproc = so->orderProcs + eq_in_ikey;
371
372 Assert(array->scan_key == eq_in_ikey);
373 Assert(OidIsValid(orderproc->fn_oid));
374 }
375
376 for (j = BTMaxStrategyNumber; --j >= 0;)
377 {
378 ScanKey chk = xform[j].inkey;
379
380 if (!chk || j == (BTEqualStrategyNumber - 1))
381 continue;
382
383 if (eq->sk_flags & SK_SEARCHNULL)
384 {
385 /* IS NULL is contradictory to anything else */
386 so->qual_ok = false;
387 return;
388 }
389
390 if (_bt_compare_scankey_args(scan, chk, eq, chk,
391 array, orderproc,
392 &test_result))
393 {
394 if (!test_result)
395 {
396 /* keys proven mutually contradictory */
397 so->qual_ok = false;
398 return;
399 }
400 /* else discard the redundant non-equality key */
401 xform[j].inkey = NULL;
402 xform[j].inkeyi = -1;
403 }
404 else
405 redundant_key_kept = true;
406 }
407 /* track number of attrs for which we have "=" keys */
408 numberOfEqualCols++;
409 }
410
411 /* try to keep only one of <, <= */
412 if (xform[BTLessStrategyNumber - 1].inkey &&
413 xform[BTLessEqualStrategyNumber - 1].inkey)
414 {
415 ScanKey lt = xform[BTLessStrategyNumber - 1].inkey;
416 ScanKey le = xform[BTLessEqualStrategyNumber - 1].inkey;
417
418 if (_bt_compare_scankey_args(scan, le, lt, le, NULL, NULL,
419 &test_result))
420 {
421 if (test_result)
422 xform[BTLessEqualStrategyNumber - 1].inkey = NULL;
423 else
424 xform[BTLessStrategyNumber - 1].inkey = NULL;
425 }
426 else
427 redundant_key_kept = true;
428 }
429
430 /* try to keep only one of >, >= */
431 if (xform[BTGreaterStrategyNumber - 1].inkey &&
432 xform[BTGreaterEqualStrategyNumber - 1].inkey)
433 {
434 ScanKey gt = xform[BTGreaterStrategyNumber - 1].inkey;
435 ScanKey ge = xform[BTGreaterEqualStrategyNumber - 1].inkey;
436
437 if (_bt_compare_scankey_args(scan, ge, gt, ge, NULL, NULL,
438 &test_result))
439 {
440 if (test_result)
441 xform[BTGreaterEqualStrategyNumber - 1].inkey = NULL;
442 else
443 xform[BTGreaterStrategyNumber - 1].inkey = NULL;
444 }
445 else
446 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 for (j = BTMaxStrategyNumber; --j >= 0;)
460 {
461 if (xform[j].inkey)
462 {
463 ScanKey outkey = &so->keyData[new_numberOfKeys++];
464
465 memcpy(outkey, xform[j].inkey, sizeof(ScanKeyData));
466 if (arrayKeyData)
467 keyDataMap[new_numberOfKeys - 1] = xform[j].inkeyi;
468 if (priorNumberOfEqualCols == attno - 1)
470 }
471 }
472
473 /*
474 * Exit loop here if done.
475 */
476 if (i == numberOfKeys)
477 break;
478
479 /* Re-initialize for new attno */
480 attno = inkey->sk_attno;
481 memset(xform, 0, sizeof(xform));
482 }
483
484 /* check strategy this key's operator corresponds to */
485 j = inkey->sk_strategy - 1;
486
487 if (inkey->sk_strategy == BTEqualStrategyNumber &&
488 (inkey->sk_flags & SK_SEARCHARRAY))
489 {
490 /* must track how input scan keys map to arrays */
491 Assert(arrayKeyData);
492 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 if (xform[j].inkey == NULL)
500 {
501 /* nope, so this scan key wins by default (at least for now) */
502 xform[j].inkey = inkey;
503 xform[j].inkeyi = i;
504 xform[j].arrayidx = arrayidx;
505 }
506 else
507 {
508 FmgrInfo *orderproc = NULL;
509 BTArrayKeyInfo *array = NULL;
510
511 /*
512 * Seen one of these before, so keep only the more restrictive key
513 * if possible
514 */
515 if (j == (BTEqualStrategyNumber - 1) && arrayKeyData)
516 {
517 /*
518 * Have to set up array keys
519 */
520 if (inkey->sk_flags & SK_SEARCHARRAY)
521 {
522 array = &so->arrayKeys[arrayidx - 1];
523 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 else if (xform[j].inkey->sk_flags & SK_SEARCHARRAY)
530 {
531 array = &so->arrayKeys[xform[j].arrayidx - 1];
532 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 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 if (test_result)
555 {
556 /*
557 * New key is more restrictive, and so replaces old key...
558 */
559 if (j != (BTEqualStrategyNumber - 1) ||
560 !(xform[j].inkey->sk_flags & SK_SEARCHARRAY))
561 {
562 xform[j].inkey = inkey;
563 xform[j].inkeyi = i;
564 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 else if (j == (BTEqualStrategyNumber - 1))
580 {
581 /* key == a && key == b, but a != b */
582 so->qual_ok = false;
583 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 ScanKey outkey = &so->keyData[new_numberOfKeys++];
599
600 memcpy(outkey, xform[j].inkey, sizeof(ScanKeyData));
601 if (arrayKeyData)
602 keyDataMap[new_numberOfKeys - 1] = xform[j].inkeyi;
603 if (numberOfEqualCols == attno - 1)
605 xform[j].inkey = inkey;
606 xform[j].inkeyi = i;
607 xform[j].arrayidx = arrayidx;
608 redundant_key_kept = true;
609 }
610 }
611 }
612
613 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 if (arrayKeyData)
622 _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 if (unlikely(redundant_key_kept) && so->qual_ok)
631 _bt_unmark_keys(scan, keyDataMap);
632
633 /* Could pfree arrayKeyData/keyDataMap now, but not worth the cycles */
634}
#define unlikely(x)
Definition: c.h:402
if(TABLE==NULL||TABLE_index==NULL)
Definition: isn.c:81
void * MemoryContextAlloc(MemoryContext context, Size size)
Definition: mcxt.c:1229
void * repalloc(void *pointer, Size size)
Definition: mcxt.c:1610
static bool _bt_fix_scankey_strategy(ScanKey skey, int16 *indoption)
static void _bt_unmark_keys(IndexScanDesc scan, int *keyDataMap)
static void _bt_mark_scankey_required(ScanKey skey)
static ScanKey _bt_preprocess_array_keys(IndexScanDesc scan, int *new_numberOfKeys)
static void _bt_preprocess_array_keys_final(IndexScanDesc scan, int *keyDataMap)
static bool _bt_compare_scankey_args(IndexScanDesc scan, ScanKey op, ScanKey leftarg, ScanKey rightarg, BTArrayKeyInfo *array, FmgrInfo *orderproc, bool *result)
#define BTMaxStrategyNumber
Definition: stratnum.h:35
Oid fn_oid
Definition: fmgr.h:59

References _bt_compare_scankey_args(), _bt_fix_scankey_strategy(), _bt_mark_scankey_required(), _bt_preprocess_array_keys(), _bt_preprocess_array_keys_final(), _bt_unmark_keys(), BTScanOpaqueData::arrayContext, BTScanOpaqueData::arrayKeys, Assert(), BTEqualStrategyNumber, BTGreaterEqualStrategyNumber, BTGreaterStrategyNumber, BTLessEqualStrategyNumber, BTLessStrategyNumber, BTMaxStrategyNumber, elog, ERROR, FmgrInfo::fn_oid, i, if(), IndexScanDescData::indexRelation, j, BTScanOpaqueData::keyData, IndexScanDescData::keyData, MemoryContextAlloc(), BTScanOpaqueData::numberOfKeys, IndexScanDescData::numberOfKeys, OidIsValid, IndexScanDescData::opaque, BTScanOpaqueData::orderProcs, BTScanOpaqueData::qual_ok, RelationData::rd_indoption, repalloc(), BTArrayKeyInfo::scan_key, ScanKeyData::sk_attno, SK_BT_SKIP, ScanKeyData::sk_flags, SK_SEARCHARRAY, SK_SEARCHNULL, ScanKeyData::sk_strategy, and unlikely.

Referenced by _bt_first().

◆ _bt_reorder_array_cmp()

static int _bt_reorder_array_cmp ( const void *  a,
const void *  b 
)
static

Definition at line 1784 of file nbtpreprocesskeys.c.

1785{
1786 BTArrayKeyInfo *arraya = (BTArrayKeyInfo *) a;
1787 BTArrayKeyInfo *arrayb = (BTArrayKeyInfo *) b;
1788
1789 return pg_cmp_s32(arraya->scan_key, arrayb->scan_key);
1790}
static int pg_cmp_s32(int32 a, int32 b)
Definition: int.h:646

References a, b, pg_cmp_s32(), and BTArrayKeyInfo::scan_key.

Referenced by _bt_unmark_keys().

◆ _bt_saoparray_shrink()

static bool _bt_saoparray_shrink ( IndexScanDesc  scan,
ScanKey  arraysk,
ScanKey  skey,
FmgrInfo *  orderproc,
BTArrayKeyInfo *  array,
bool *  qual_ok 
)
static

Definition at line 1126 of file nbtpreprocesskeys.c.

1128{
1129 Relation rel = scan->indexRelation;
1130 Oid opcintype = rel->rd_opcintype[arraysk->sk_attno - 1];
1131 int cmpresult = 0,
1132 cmpexact = 0,
1133 matchelem,
1134 new_nelems = 0;
1135 FmgrInfo crosstypeproc;
1136 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 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 arraysk_elemtype = arraysk->sk_subtype;
1166 if (arraysk_elemtype == InvalidOid)
1167 arraysk_elemtype = rel->rd_opcintype[arraysk->sk_attno - 1];
1168 cmp_proc = get_opfamily_proc(rel->rd_opfamily[arraysk->sk_attno - 1],
1169 skey->sk_subtype, arraysk_elemtype,
1170 BTORDER_PROC);
1171 if (!RegProcedureIsValid(cmp_proc))
1172 {
1173 /* Can't make the comparison */
1174 *qual_ok = false; /* suppress compiler warnings */
1175 return false;
1176 }
1177
1178 /* We have all we need to determine redundancy/contradictoriness */
1179 orderprocp = &crosstypeproc;
1180 fmgr_info(cmp_proc, orderprocp);
1181 }
1182
1183 matchelem = _bt_binsrch_array_skey(orderprocp, false,
1185 skey->sk_argument, false, array,
1186 arraysk, &cmpresult);
1187
1188 switch (skey->sk_strategy)
1189 {
1191 cmpexact = 1; /* exclude exact match, if any */
1192 /* FALL THRU */
1194 if (cmpresult >= cmpexact)
1195 matchelem++;
1196 /* Resize, keeping elements from the start of the array */
1197 new_nelems = matchelem;
1198 break;
1200 if (cmpresult != 0)
1201 {
1202 /* qual is unsatisfiable */
1203 new_nelems = 0;
1204 }
1205 else
1206 {
1207 /* Shift matching element to the start of the array, resize */
1208 array->elem_values[0] = array->elem_values[matchelem];
1209 new_nelems = 1;
1210 }
1211 break;
1213 cmpexact = 1; /* include exact match, if any */
1214 /* FALL THRU */
1216 if (cmpresult >= cmpexact)
1217 matchelem++;
1218 /* Shift matching elements to the start of the array, resize */
1219 new_nelems = array->num_elems - matchelem;
1220 memmove(array->elem_values, array->elem_values + matchelem,
1221 sizeof(Datum) * new_nelems);
1222 break;
1223 default:
1224 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 array->num_elems = new_nelems;
1233 *qual_ok = new_nelems > 0;
1234
1235 return true;
1236}
int _bt_binsrch_array_skey(FmgrInfo *orderproc, bool cur_elem_trig, ScanDirection dir, Datum tupdatum, bool tupnull, BTArrayKeyInfo *array, ScanKey cur, int32 *set_elem_result)
Definition: nbtutils.c:289
@ NoMovementScanDirection
Definition: sdir.h:27

References _bt_binsrch_array_skey(), Assert(), BTEqualStrategyNumber, BTGreaterEqualStrategyNumber, BTGreaterStrategyNumber, BTLessEqualStrategyNumber, BTLessStrategyNumber, BTORDER_PROC, BTArrayKeyInfo::elem_values, elog, ERROR, fmgr_info(), get_opfamily_proc(), IndexScanDescData::indexRelation, InvalidOid, NoMovementScanDirection, BTArrayKeyInfo::num_elems, RelationData::rd_opcintype, RelationData::rd_opfamily, RegProcedureIsValid, ScanKeyData::sk_argument, ScanKeyData::sk_attno, SK_BT_SKIP, ScanKeyData::sk_flags, ScanKeyData::sk_strategy, and ScanKeyData::sk_subtype.

Referenced by _bt_compare_array_scankey_args().

◆ _bt_setup_array_cmp()

static void _bt_setup_array_cmp ( IndexScanDesc  scan,
ScanKey  skey,
Oid  elemtype,
FmgrInfo *  orderproc,
FmgrInfo **  sortprocp 
)
static

Definition at line 2643 of file nbtpreprocesskeys.c.

2645{
2646 BTScanOpaque so = (BTScanOpaque) scan->opaque;
2647 Relation rel = scan->indexRelation;
2648 RegProcedure cmp_proc;
2649 Oid opcintype = rel->rd_opcintype[skey->sk_attno - 1];
2650
2652 Assert(OidIsValid(elemtype));
2653
2654 /*
2655 * If scankey operator is not a cross-type comparison, we can use the
2656 * cached comparison function; otherwise gotta look it up in the catalogs
2657 */
2658 if (elemtype == opcintype)
2659 {
2660 /* Set same-type ORDER procs for caller */
2661 *orderproc = *index_getprocinfo(rel, skey->sk_attno, BTORDER_PROC);
2662 if (sortprocp)
2663 *sortprocp = orderproc;
2664
2665 return;
2666 }
2667
2668 /*
2669 * Look up the appropriate cross-type comparison function in the opfamily.
2670 *
2671 * Use the opclass input type as the left hand arg type, and the array
2672 * element type as the right hand arg type (since binary searches use an
2673 * index tuple's attribute value to search for a matching array element).
2674 *
2675 * Note: it's possible that this would fail, if the opfamily is
2676 * incomplete, but only in cases where it's quite likely that _bt_first
2677 * would fail in just the same way (had we not failed before it could).
2678 */
2679 cmp_proc = get_opfamily_proc(rel->rd_opfamily[skey->sk_attno - 1],
2680 opcintype, elemtype, BTORDER_PROC);
2681 if (!RegProcedureIsValid(cmp_proc))
2682 elog(ERROR, "missing support function %d(%u,%u) for attribute %d of index \"%s\"",
2683 BTORDER_PROC, opcintype, elemtype, skey->sk_attno,
2685
2686 /* Set cross-type ORDER proc for caller */
2687 fmgr_info_cxt(cmp_proc, orderproc, so->arrayContext);
2688
2689 /* Done if caller doesn't actually have an array they'll need to sort */
2690 if (!sortprocp)
2691 return;
2692
2693 /*
2694 * Look up the appropriate same-type comparison function in the opfamily.
2695 *
2696 * Note: it's possible that this would fail, if the opfamily is
2697 * incomplete, but it seems quite unlikely that an opfamily would omit
2698 * non-cross-type comparison procs for any datatype that it supports at
2699 * all.
2700 */
2701 cmp_proc = get_opfamily_proc(rel->rd_opfamily[skey->sk_attno - 1],
2702 elemtype, elemtype, BTORDER_PROC);
2703 if (!RegProcedureIsValid(cmp_proc))
2704 elog(ERROR, "missing support function %d(%u,%u) for attribute %d of index \"%s\"",
2705 BTORDER_PROC, elemtype, elemtype,
2706 skey->sk_attno, RelationGetRelationName(rel));
2707
2708 /* Set same-type ORDER proc for caller */
2709 fmgr_info_cxt(cmp_proc, *sortprocp, so->arrayContext);
2710}
FmgrInfo * index_getprocinfo(Relation irel, AttrNumber attnum, uint16 procnum)
Definition: indexam.c:917
#define RelationGetRelationName(relation)
Definition: rel.h:548

References BTScanOpaqueData::arrayContext, Assert(), BTEqualStrategyNumber, BTORDER_PROC, elog, ERROR, fmgr_info_cxt(), get_opfamily_proc(), index_getprocinfo(), IndexScanDescData::indexRelation, OidIsValid, IndexScanDescData::opaque, RelationData::rd_opcintype, RegProcedureIsValid, RelationGetRelationName, ScanKeyData::sk_attno, and ScanKeyData::sk_strategy.

Referenced by _bt_preprocess_array_keys(), and _bt_preprocess_array_keys_final().

◆ _bt_skiparray_shrink()

static bool _bt_skiparray_shrink ( IndexScanDesc  scan,
ScanKey  skey,
BTArrayKeyInfo *  array,
bool *  qual_ok 
)
static

Definition at line 1251 of file nbtpreprocesskeys.c.

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 array->null_elem = false;
1264 *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 switch (skey->sk_strategy)
1289 {
1292 if (array->high_compare)
1293 {
1294 /* replace existing high_compare with caller's key? */
1295 if (!_bt_compare_scankey_args(scan, array->high_compare, skey,
1296 array->high_compare, NULL, NULL,
1297 &test_result))
1298 return false; /* can't determine more restrictive key */
1299
1300 if (!test_result)
1301 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 array->high_compare = skey;
1308 break;
1311 if (array->low_compare)
1312 {
1313 /* replace existing low_compare with caller's key? */
1314 if (!_bt_compare_scankey_args(scan, array->low_compare, skey,
1315 array->low_compare, NULL, NULL,
1316 &test_result))
1317 return false; /* can't determine more restrictive key */
1318
1319 if (!test_result)
1320 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 array->low_compare = skey;
1327 break;
1329 default:
1330 elog(ERROR, "unrecognized StrategyNumber: %d",
1331 (int) skey->sk_strategy);
1332 break;
1333 }
1334
1335 return true;
1336}

References _bt_compare_scankey_args(), Assert(), BTEqualStrategyNumber, BTGreaterEqualStrategyNumber, BTGreaterStrategyNumber, BTLessEqualStrategyNumber, BTLessStrategyNumber, elog, ERROR, BTArrayKeyInfo::high_compare, BTArrayKeyInfo::low_compare, BTArrayKeyInfo::null_elem, BTArrayKeyInfo::num_elems, and ScanKeyData::sk_strategy.

Referenced by _bt_compare_array_scankey_args().

◆ _bt_skiparray_strat_adjust()

static void _bt_skiparray_strat_adjust ( IndexScanDesc  scan,
ScanKey  arraysk,
BTArrayKeyInfo *  array 
)
static

Definition at line 1373 of file nbtpreprocesskeys.c.

1375{
1376 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 oldContext = MemoryContextSwitchTo(so->arrayContext);
1387
1388 if (array->high_compare &&
1390 _bt_skiparray_strat_decrement(scan, arraysk, array);
1391
1392 if (array->low_compare &&
1394 _bt_skiparray_strat_increment(scan, arraysk, array);
1395
1396 MemoryContextSwitchTo(oldContext);
1397}
static void _bt_skiparray_strat_increment(IndexScanDesc scan, ScanKey arraysk, BTArrayKeyInfo *array)
static void _bt_skiparray_strat_decrement(IndexScanDesc scan, ScanKey arraysk, BTArrayKeyInfo *array)

References _bt_skiparray_strat_decrement(), _bt_skiparray_strat_increment(), BTScanOpaqueData::arrayContext, Assert(), BTGreaterStrategyNumber, BTLessStrategyNumber, BTArrayKeyInfo::high_compare, BTArrayKeyInfo::low_compare, MemoryContextSwitchTo(), BTArrayKeyInfo::null_elem, BTArrayKeyInfo::num_elems, IndexScanDescData::opaque, SK_BT_SKIP, ScanKeyData::sk_flags, ScanKeyData::sk_strategy, and BTArrayKeyInfo::sksup.

Referenced by _bt_preprocess_array_keys_final().

◆ _bt_skiparray_strat_decrement()

static void _bt_skiparray_strat_decrement ( IndexScanDesc  scan,
ScanKey  arraysk,
BTArrayKeyInfo *  array 
)
static

Definition at line 1403 of file nbtpreprocesskeys.c.

1405{
1406 Relation rel = scan->indexRelation;
1407 Oid opfamily = rel->rd_opfamily[arraysk->sk_attno - 1],
1408 opcintype = rel->rd_opcintype[arraysk->sk_attno - 1],
1409 leop;
1410 RegProcedure cmp_proc;
1411 ScanKey high_compare = array->high_compare;
1412 Datum orig_sk_argument = high_compare->sk_argument,
1413 new_sk_argument;
1414 bool uflow;
1415 int16 lookupstrat;
1416
1417 Assert(high_compare->sk_strategy == BTLessStrategyNumber);
1418
1419 /*
1420 * Only perform the transformation when the operator type matches the
1421 * index attribute's input opclass type
1422 */
1423 if (high_compare->sk_subtype != opcintype &&
1424 high_compare->sk_subtype != InvalidOid)
1425 return;
1426
1427 /* Decrement, handling underflow by marking the qual unsatisfiable */
1428 new_sk_argument = array->sksup->decrement(rel, orig_sk_argument, &uflow);
1429 if (uflow)
1430 {
1431 BTScanOpaque so = (BTScanOpaque) scan->opaque;
1432
1433 so->qual_ok = false;
1434 return;
1435 }
1436
1437 /*
1438 * Look up <= operator (might fail), accounting for the fact that a
1439 * high_compare on a DESC column already had its strategy commuted
1440 */
1441 lookupstrat = BTLessEqualStrategyNumber;
1442 if (high_compare->sk_flags & SK_BT_DESC)
1443 lookupstrat = BTGreaterEqualStrategyNumber; /* commute this too */
1444 leop = get_opfamily_member(opfamily, opcintype, opcintype, lookupstrat);
1445 if (!OidIsValid(leop))
1446 return;
1447 cmp_proc = get_opcode(leop);
1448 if (RegProcedureIsValid(cmp_proc))
1449 {
1450 /* Transform < high_compare key into <= key */
1451 fmgr_info(cmp_proc, &high_compare->sk_func);
1452 high_compare->sk_argument = new_sk_argument;
1453 high_compare->sk_strategy = BTLessEqualStrategyNumber;
1454 }
1455}
SkipSupportIncDec decrement
Definition: skipsupport.h:91

References Assert(), BTGreaterEqualStrategyNumber, BTLessEqualStrategyNumber, BTLessStrategyNumber, SkipSupportData::decrement, fmgr_info(), get_opcode(), get_opfamily_member(), BTArrayKeyInfo::high_compare, IndexScanDescData::indexRelation, InvalidOid, OidIsValid, IndexScanDescData::opaque, BTScanOpaqueData::qual_ok, RelationData::rd_opcintype, RelationData::rd_opfamily, RegProcedureIsValid, ScanKeyData::sk_argument, ScanKeyData::sk_attno, SK_BT_DESC, ScanKeyData::sk_flags, ScanKeyData::sk_func, ScanKeyData::sk_strategy, ScanKeyData::sk_subtype, and BTArrayKeyInfo::sksup.

Referenced by _bt_skiparray_strat_adjust().

◆ _bt_skiparray_strat_increment()

static void _bt_skiparray_strat_increment ( IndexScanDesc  scan,
ScanKey  arraysk,
BTArrayKeyInfo *  array 
)
static

Definition at line 1461 of file nbtpreprocesskeys.c.

1463{
1464 Relation rel = scan->indexRelation;
1465 Oid opfamily = rel->rd_opfamily[arraysk->sk_attno - 1],
1466 opcintype = rel->rd_opcintype[arraysk->sk_attno - 1],
1467 geop;
1468 RegProcedure cmp_proc;
1469 ScanKey low_compare = array->low_compare;
1470 Datum orig_sk_argument = low_compare->sk_argument,
1471 new_sk_argument;
1472 bool oflow;
1473 int16 lookupstrat;
1474
1476
1477 /*
1478 * Only perform the transformation when the operator type matches the
1479 * index attribute's input opclass type
1480 */
1481 if (low_compare->sk_subtype != opcintype &&
1482 low_compare->sk_subtype != InvalidOid)
1483 return;
1484
1485 /* Increment, handling overflow by marking the qual unsatisfiable */
1486 new_sk_argument = array->sksup->increment(rel, orig_sk_argument, &oflow);
1487 if (oflow)
1488 {
1489 BTScanOpaque so = (BTScanOpaque) scan->opaque;
1490
1491 so->qual_ok = false;
1492 return;
1493 }
1494
1495 /*
1496 * Look up >= operator (might fail), accounting for the fact that a
1497 * low_compare on a DESC column already had its strategy commuted
1498 */
1499 lookupstrat = BTGreaterEqualStrategyNumber;
1500 if (low_compare->sk_flags & SK_BT_DESC)
1501 lookupstrat = BTLessEqualStrategyNumber; /* commute this too */
1502 geop = get_opfamily_member(opfamily, opcintype, opcintype, lookupstrat);
1503 if (!OidIsValid(geop))
1504 return;
1505 cmp_proc = get_opcode(geop);
1506 if (RegProcedureIsValid(cmp_proc))
1507 {
1508 /* Transform > low_compare key into >= key */
1509 fmgr_info(cmp_proc, &low_compare->sk_func);
1510 low_compare->sk_argument = new_sk_argument;
1512 }
1513}
SkipSupportIncDec increment
Definition: skipsupport.h:92

References Assert(), BTGreaterEqualStrategyNumber, BTGreaterStrategyNumber, BTLessEqualStrategyNumber, fmgr_info(), get_opcode(), get_opfamily_member(), SkipSupportData::increment, IndexScanDescData::indexRelation, InvalidOid, BTArrayKeyInfo::low_compare, OidIsValid, IndexScanDescData::opaque, BTScanOpaqueData::qual_ok, RelationData::rd_opcintype, RelationData::rd_opfamily, RegProcedureIsValid, ScanKeyData::sk_argument, ScanKeyData::sk_attno, SK_BT_DESC, ScanKeyData::sk_flags, ScanKeyData::sk_func, ScanKeyData::sk_strategy, ScanKeyData::sk_subtype, and BTArrayKeyInfo::sksup.

Referenced by _bt_skiparray_strat_adjust().

◆ _bt_sort_array_elements()

static int _bt_sort_array_elements ( ScanKey  skey,
FmgrInfo *  sortproc,
bool  reverse,
Datum *  elems,
int  nelems 
)
static

Definition at line 2723 of file nbtpreprocesskeys.c.

2725{
2727
2728 if (nelems <= 1)
2729 return nelems; /* no work to do */
2730
2731 /* Sort the array elements */
2732 cxt.sortproc = sortproc;
2733 cxt.collation = skey->sk_collation;
2734 cxt.reverse = reverse;
2735 qsort_arg(elems, nelems, sizeof(Datum),
2737
2738 /* Now scan the sorted elements and remove duplicates */
2739 return qunique_arg(elems, nelems, sizeof(Datum),
2741}
void qsort_arg(void *base, size_t nel, size_t elsize, qsort_arg_comparator cmp, void *arg)
static size_t qunique_arg(void *array, size_t elements, size_t width, int(*compare)(const void *, const void *, void *), void *arg)
Definition: qunique.h:46

References _bt_compare_array_elements(), BTSortArrayContext::collation, qsort_arg(), qunique_arg(), BTSortArrayContext::reverse, ScanKeyData::sk_collation, and BTSortArrayContext::sortproc.

Referenced by _bt_preprocess_array_keys().

◆ _bt_unmark_keys()

static void _bt_unmark_keys ( IndexScanDesc  scan,
int *  keyDataMap 
)
static

Definition at line 1534 of file nbtpreprocesskeys.c.

1535{
1536 BTScanOpaque so = (BTScanOpaque) scan->opaque;
1537 AttrNumber attno;
1538 bool *unmarkikey;
1539 int nunmark,
1540 nunmarked,
1541 nkept,
1542 firsti;
1543 ScanKey keepKeys,
1544 unmarkKeys;
1545 FmgrInfo *keepOrderProcs = NULL,
1546 *unmarkOrderProcs = NULL;
1547 bool haveReqEquals,
1548 haveReqForward,
1549 haveReqBackward;
1550
1551 /*
1552 * Do an initial pass over so->keyData[] that determines which keys to
1553 * keep as required. We expect so->keyData[] to still be in attribute
1554 * order when we're called (though we don't expect any particular order
1555 * among each attribute's keys).
1556 *
1557 * When both equality and inequality keys remain on a single attribute, we
1558 * *must* make sure that exactly one of the equalities remains required.
1559 * Any requiredness markings that we might leave on later keys/attributes
1560 * are predicated on there being required = keys on all prior columns.
1561 */
1562 unmarkikey = palloc0(so->numberOfKeys * sizeof(bool));
1563 nunmark = 0;
1564
1565 /* Set things up for first key's attribute */
1566 attno = so->keyData[0].sk_attno;
1567 firsti = 0;
1568 haveReqEquals = false;
1569 haveReqForward = false;
1570 haveReqBackward = false;
1571 for (int i = 0; i < so->numberOfKeys; i++)
1572 {
1573 ScanKey origkey = &so->keyData[i];
1574
1575 if (origkey->sk_attno != attno)
1576 {
1577 /* Reset for next attribute */
1578 attno = origkey->sk_attno;
1579 firsti = i;
1580
1581 haveReqEquals = false;
1582 haveReqForward = false;
1583 haveReqBackward = false;
1584 }
1585
1586 /* Equalities get priority over inequalities */
1587 if (haveReqEquals)
1588 {
1589 /*
1590 * We already found the first "=" key for this attribute. We've
1591 * already decided that all its other keys will be unmarked.
1592 */
1593 Assert(!(origkey->sk_flags & SK_SEARCHNULL));
1594 unmarkikey[i] = true;
1595 nunmark++;
1596 continue;
1597 }
1598 else if ((origkey->sk_flags & SK_BT_REQFWD) &&
1599 (origkey->sk_flags & SK_BT_REQBKWD))
1600 {
1601 /*
1602 * Found the first "=" key for attno. All other attno keys will
1603 * be unmarked.
1604 */
1606
1607 haveReqEquals = true;
1608 for (int j = firsti; j < i; j++)
1609 {
1610 /* Unmark any prior inequality keys on attno after all */
1611 if (!unmarkikey[j])
1612 {
1613 unmarkikey[j] = true;
1614 nunmark++;
1615 }
1616 }
1617 continue;
1618 }
1619
1620 /* Deal with inequalities next */
1621 if ((origkey->sk_flags & SK_BT_REQFWD) && !haveReqForward)
1622 {
1623 haveReqForward = true;
1624 continue;
1625 }
1626 else if ((origkey->sk_flags & SK_BT_REQBKWD) && !haveReqBackward)
1627 {
1628 haveReqBackward = true;
1629 continue;
1630 }
1631
1632 /*
1633 * We have either a redundant inequality key that will be unmarked, or
1634 * we have a key that wasn't marked required in the first place
1635 */
1636 unmarkikey[i] = true;
1637 nunmark++;
1638 }
1639
1640 /* Should only be called when _bt_compare_scankey_args reported failure */
1641 Assert(nunmark > 0);
1642
1643 /*
1644 * Next, allocate temp arrays: one for required keys that'll remain
1645 * required, the other for all remaining keys
1646 */
1647 unmarkKeys = palloc(nunmark * sizeof(ScanKeyData));
1648 keepKeys = palloc((so->numberOfKeys - nunmark) * sizeof(ScanKeyData));
1649 nunmarked = 0;
1650 nkept = 0;
1651 if (so->numArrayKeys)
1652 {
1653 unmarkOrderProcs = palloc(nunmark * sizeof(FmgrInfo));
1654 keepOrderProcs = palloc((so->numberOfKeys - nunmark) * sizeof(FmgrInfo));
1655 }
1656
1657 /*
1658 * Next, copy the contents of so->keyData[] into the appropriate temp
1659 * array.
1660 *
1661 * Scans with = array keys need us to maintain invariants around the order
1662 * of so->orderProcs[] and so->arrayKeys[] relative to so->keyData[]. See
1663 * _bt_preprocess_array_keys_final for a full explanation.
1664 */
1665 for (int i = 0; i < so->numberOfKeys; i++)
1666 {
1667 ScanKey origkey = &so->keyData[i];
1668 ScanKey unmark;
1669
1670 if (!unmarkikey[i])
1671 {
1672 /*
1673 * Key gets to keep its original requiredness markings.
1674 *
1675 * Key will stay in its original position, unless we're going to
1676 * unmark an earlier key (in which case this key gets moved back).
1677 */
1678 memcpy(keepKeys + nkept, origkey, sizeof(ScanKeyData));
1679
1680 if (so->numArrayKeys)
1681 {
1682 keyDataMap[i] = nkept;
1683 memcpy(keepOrderProcs + nkept, &so->orderProcs[i],
1684 sizeof(FmgrInfo));
1685 }
1686
1687 nkept++;
1688 continue;
1689 }
1690
1691 /*
1692 * Key will be unmarked as needed, and moved to the end of the array,
1693 * next to other keys that will become (or always were) nonrequired
1694 */
1695 unmark = unmarkKeys + nunmarked;
1696 memcpy(unmark, origkey, sizeof(ScanKeyData));
1697
1698 if (so->numArrayKeys)
1699 {
1700 keyDataMap[i] = (so->numberOfKeys - nunmark) + nunmarked;
1701 memcpy(&unmarkOrderProcs[nunmarked], &so->orderProcs[i],
1702 sizeof(FmgrInfo));
1703 }
1704
1705 /*
1706 * Preprocessing only generates skip arrays when it knows that they'll
1707 * be the only required = key on the attr. We'll never unmark them.
1708 */
1709 Assert(!(unmark->sk_flags & SK_BT_SKIP));
1710
1711 /*
1712 * Also shouldn't have to unmark an IS NULL or an IS NOT NULL key.
1713 * They aren't cross-type, so an incomplete opfamily can't matter.
1714 */
1715 Assert(!(unmark->sk_flags & SK_ISNULL) ||
1716 !(unmark->sk_flags & (SK_BT_REQFWD | SK_BT_REQBKWD)));
1717
1718 /* Clear requiredness flags on redundant key (and on any subkeys) */
1719 unmark->sk_flags &= ~(SK_BT_REQFWD | SK_BT_REQBKWD);
1720 if (unmark->sk_flags & SK_ROW_HEADER)
1721 {
1722 ScanKey subkey = (ScanKey) DatumGetPointer(unmark->sk_argument);
1723
1724 Assert(subkey->sk_strategy == unmark->sk_strategy);
1725 for (;;)
1726 {
1727 Assert(subkey->sk_flags & SK_ROW_MEMBER);
1728 subkey->sk_flags &= ~(SK_BT_REQFWD | SK_BT_REQBKWD);
1729 if (subkey->sk_flags & SK_ROW_END)
1730 break;
1731 subkey++;
1732 }
1733 }
1734
1735 nunmarked++;
1736 }
1737
1738 /* Copy both temp arrays back into so->keyData[] to reorder */
1739 Assert(nkept == so->numberOfKeys - nunmark);
1740 Assert(nunmarked == nunmark);
1741 memcpy(so->keyData, keepKeys, sizeof(ScanKeyData) * nkept);
1742 memcpy(so->keyData + nkept, unmarkKeys, sizeof(ScanKeyData) * nunmarked);
1743
1744 /* Done with temp arrays */
1745 pfree(unmarkikey);
1746 pfree(keepKeys);
1747 pfree(unmarkKeys);
1748
1749 /*
1750 * Now copy so->orderProcs[] temp entries needed by scans with = array
1751 * keys back (just like with the so->keyData[] temp arrays)
1752 */
1753 if (so->numArrayKeys)
1754 {
1755 memcpy(so->orderProcs, keepOrderProcs, sizeof(FmgrInfo) * nkept);
1756 memcpy(so->orderProcs + nkept, unmarkOrderProcs,
1757 sizeof(FmgrInfo) * nunmarked);
1758
1759 /* Also fix-up array->scan_key references */
1760 for (int arridx = 0; arridx < so->numArrayKeys; arridx++)
1761 {
1762 BTArrayKeyInfo *array = &so->arrayKeys[arridx];
1763
1764 array->scan_key = keyDataMap[array->scan_key];
1765 }
1766
1767 /*
1768 * Sort so->arrayKeys[] based on its new BTArrayKeyInfo.scan_key
1769 * offsets, so that its order matches so->keyData[] order as expected
1770 */
1771 qsort(so->arrayKeys, so->numArrayKeys, sizeof(BTArrayKeyInfo),
1773
1774 /* Done with temp arrays */
1775 pfree(unmarkOrderProcs);
1776 pfree(keepOrderProcs);
1777 }
1778}
void * palloc0(Size size)
Definition: mcxt.c:1395
static int _bt_reorder_array_cmp(const void *a, const void *b)
#define qsort(a, b, c, d)
Definition: port.h:479

References _bt_reorder_array_cmp(), BTScanOpaqueData::arrayKeys, Assert(), BTEqualStrategyNumber, DatumGetPointer(), i, j, BTScanOpaqueData::keyData, BTScanOpaqueData::numArrayKeys, BTScanOpaqueData::numberOfKeys, IndexScanDescData::opaque, BTScanOpaqueData::orderProcs, palloc(), palloc0(), pfree(), qsort, BTArrayKeyInfo::scan_key, ScanKeyData::sk_argument, ScanKeyData::sk_attno, SK_BT_REQBKWD, SK_BT_REQFWD, SK_BT_SKIP, ScanKeyData::sk_flags, SK_ISNULL, SK_ROW_END, SK_ROW_HEADER, SK_ROW_MEMBER, SK_SEARCHNULL, and ScanKeyData::sk_strategy.

Referenced by _bt_preprocess_keys().

AltStyle によって変換されたページ (->オリジナル) /