=== Applying patches on top of PostgreSQL commit ID 23d7562018b2c772aec26f4641de211d8a930b26 === /etc/rc.d/jail: WARNING: Per-jail configuration via jail_* variables is obsolete. Please consider migrating to /etc/jail.conf. Sun Jan 19 21:22:20 UTC 2025 On branch cf/5461 nothing to commit, working tree clean === applying patch ./arrayelemhdr.patch Applied patch to 'contrib/hstore/hstore_gin.c' cleanly. Applied patch to 'contrib/hstore/hstore_gist.c' cleanly. Applied patch to 'contrib/hstore/hstore_io.c' cleanly. Applied patch to 'contrib/hstore/hstore_op.c' cleanly. Applied patch to 'contrib/ltree/_ltree_gist.c' cleanly. Applied patch to 'contrib/ltree/_ltree_op.c' cleanly. Applied patch to 'contrib/ltree/lquery_op.c' cleanly. Applied patch to 'contrib/ltree/ltree.h' cleanly. Applied patch to 'contrib/ltree/ltree_gist.c' cleanly. Applied patch to 'src/backend/access/common/reloptions.c' cleanly. Applied patch to 'src/backend/access/gin/ginarrayproc.c' cleanly. Applied patch to 'src/backend/access/nbtree/nbtutils.c' with conflicts. Applied patch to 'src/backend/bootstrap/bootstrap.c' cleanly. Applied patch to 'src/backend/catalog/objectaddress.c' cleanly. Applied patch to 'src/backend/catalog/pg_attrdef.c' cleanly. Applied patch to 'src/backend/commands/analyze.c' cleanly. Applied patch to 'src/backend/commands/extension.c' cleanly. Applied patch to 'src/backend/commands/tablecmds.c' cleanly. Applied patch to 'src/backend/executor/execExpr.c' cleanly. Applied patch to 'src/backend/executor/execExprInterp.c' cleanly. Applied patch to 'src/backend/executor/nodeIndexscan.c' cleanly. Applied patch to 'src/backend/optimizer/path/indxpath.c' cleanly. Applied patch to 'src/backend/optimizer/util/predtest.c' cleanly. Applied patch to 'src/backend/partitioning/partbounds.c' cleanly. Applied patch to 'src/backend/partitioning/partprune.c' cleanly. Applied patch to 'src/backend/statistics/extended_stats.c' cleanly. Applied patch to 'src/backend/statistics/mcv.c' cleanly. Applied patch to 'src/backend/utils/adt/array_expanded.c' cleanly. Applied patch to 'src/backend/utils/adt/array_selfuncs.c' cleanly. Applied patch to 'src/backend/utils/adt/array_typanalyze.c' cleanly. Applied patch to 'src/backend/utils/adt/array_userfuncs.c' cleanly. Applied patch to 'src/backend/utils/adt/arrayfuncs.c' cleanly. Applied patch to 'src/backend/utils/adt/arraysubs.c' cleanly. Applied patch to 'src/backend/utils/adt/enum.c' cleanly. Applied patch to 'src/backend/utils/adt/json.c' cleanly. Applied patch to 'src/backend/utils/adt/jsonb.c' cleanly. Applied patch to 'src/backend/utils/adt/multirangetypes.c' cleanly. Applied patch to 'src/backend/utils/adt/orderedsetaggs.c' cleanly. Applied patch to 'src/backend/utils/adt/rangetypes.c' cleanly. Applied patch to 'src/backend/utils/adt/regexp.c' cleanly. Applied patch to 'src/backend/utils/adt/ruleutils.c' cleanly. Applied patch to 'src/backend/utils/adt/selfuncs.c' cleanly. Applied patch to 'src/backend/utils/adt/tsvector_op.c' cleanly. Applied patch to 'src/backend/utils/adt/varlena.c' cleanly. Applied patch to 'src/backend/utils/adt/xml.c' cleanly. Applied patch to 'src/backend/utils/cache/lsyscache.c' cleanly. Applied patch to 'src/backend/utils/cache/relcache.c' cleanly. Applied patch to 'src/backend/utils/fmgr/funcapi.c' cleanly. Applied patch to 'src/backend/utils/misc/guc.c' cleanly. Applied patch to 'src/include/access/tupmacs.h' cleanly. Applied patch to 'src/include/bootstrap/bootstrap.h' cleanly. Applied patch to 'src/include/catalog/pg_type.h' cleanly. Applied patch to 'src/include/commands/vacuum.h' cleanly. Applied patch to 'src/include/executor/execExpr.h' cleanly. Applied patch to 'src/include/utils/array.h' cleanly. Applied patch to 'src/include/utils/lsyscache.h' cleanly. Applied patch to 'src/include/utils/palloc.h' cleanly. Applied patch to 'src/pl/plperl/plperl.c' cleanly. Applied patch to 'src/pl/plpgsql/src/pl_exec.c' cleanly. Applied patch to 'src/test/modules/test_regex/test_regex.c' cleanly. U src/backend/access/nbtree/nbtutils.c diff --cc src/backend/access/nbtree/nbtutils.c index 693e43c674,c3aa979c57..0000000000 --- a/src/backend/access/nbtree/nbtutils.c +++ b/src/backend/access/nbtree/nbtutils.c @@@ -181,226 -230,309 +181,255 @@@ _bt_freestack(BTStack stack } } - /* - * _bt_preprocess_array_keys() -- Preprocess SK_SEARCHARRAY scan keys - * - * If there are any SK_SEARCHARRAY scan keys, deconstruct the array(s) and - * set up BTArrayKeyInfo info for each one that is an equality-type key. - * Returns modified scan keys as input for further, standard preprocessing. - * - * Currently we perform two kinds of preprocessing to deal with redundancies. - * For inequality array keys, it's sufficient to find the extreme element - * value and replace the whole array with that scalar value. This eliminates - * all but one array element as redundant. Similarly, we are capable of - * "merging together" multiple equality array keys (from two or more input - * scan keys) into a single output scan key containing only the intersecting - * array elements. This can eliminate many redundant array elements, as well - * as eliminating whole array scan keys as redundant. It can also allow us to - * detect contradictory quals. + * _bt_compare_array_skey() -- apply array comparison function * - * Caller must pass *new_numberOfKeys to give us a way to change the number of - * scan keys that caller treats as input to standard preprocessing steps. The - * returned array is smaller than scan->keyData[] when we could eliminate a - * redundant array scan key (redundant with another array scan key). It is - * convenient for _bt_preprocess_keys caller to have to deal with no more than - * one equality strategy array scan key per index attribute. We'll always be - * able to set things up that way when complete opfamilies are used. + * Compares caller's tuple attribute value to a scan key/array element. + * Helper function used during binary searches of SK_SEARCHARRAY arrays. * - * We set the scan key references from the scan's BTArrayKeyInfo info array to - * offsets into the temp modified input array returned to caller. Scans that - * have array keys should call _bt_preprocess_array_keys_final when standard - * preprocessing steps are complete. This will convert the scan key offset - * references into references to the scan's so->keyData[] output scan keys. + * This routine returns: + * <0 if tupdatum < arrdatum; + * 0 if tupdatum == arrdatum; + * >0 if tupdatum > arrdatum. * - * Note: the reason we need to return a temp scan key array, rather than just - * scribbling on scan->keyData, is that callers are permitted to call btrescan - * without supplying a new set of scankey data. - */ -static ScanKey -_bt_preprocess_array_keys(IndexScanDesc scan, int *new_numberOfKeys) + * This is essentially the same interface as _bt_compare: both functions + * compare the value that they're searching for to a binary search pivot. + * However, unlike _bt_compare, this function's "tuple argument" comes first, + * while its "array/scankey argument" comes second. +*/ +static inline int32 +_bt_compare_array_skey(FmgrInfo *orderproc, + Datum tupdatum, bool tupnull, + Datum arrdatum, ScanKey cur) { - BTScanOpaque so = (BTScanOpaque) scan->opaque; - Relation rel = scan->indexRelation; - int numberOfKeys = scan->numberOfKeys; - int16 *indoption = rel->rd_indoption; - int numArrayKeys, - output_ikey = 0; - int origarrayatt = InvalidAttrNumber, - origarraykey = -1; - Oid origelemtype = InvalidOid; - ScanKey cur; - MemoryContext oldContext; - ScanKey arrayKeyData; /* modified copy of scan->keyData */ - - Assert(numberOfKeys); - - /* Quick check to see if there are any array keys */ - numArrayKeys = 0; - for (int i = 0; i < numberOfKeys; i++) - { - cur = &scan->keyData[i]; - if (cur->sk_flags & SK_SEARCHARRAY) - { - numArrayKeys++; - Assert(!(cur->sk_flags & (SK_ROW_HEADER | SK_SEARCHNULL | SK_SEARCHNOTNULL))); - /* If any arrays are null as a whole, we can quit right now. */ - if (cur->sk_flags & SK_ISNULL) - { - so->qual_ok = false; - return NULL; - } - } - } + int32 result = 0; - /* Quit if nothing to do. */ - if (numArrayKeys == 0) - return NULL; + Assert(cur->sk_strategy == BTEqualStrategyNumber); - /* - * Make a scan-lifespan context to hold array-associated data, or reset it - * if we already have one from a previous rescan cycle. - */ - if (so->arrayContext == NULL) - so->arrayContext = AllocSetContextCreate(CurrentMemoryContext, - "BTree array context", - ALLOCSET_SMALL_SIZES); + if (tupnull) /* NULL tupdatum */ + { + if (cur->sk_flags & SK_ISNULL) + result = 0; /* NULL "=" NULL */ + else if (cur->sk_flags & SK_BT_NULLS_FIRST) + result = -1; /* NULL "<" NOT_NULL */ + else + result = 1; /* NULL ">" NOT_NULL */ + } + else if (cur->sk_flags & SK_ISNULL) /* NOT_NULL tupdatum, NULL arrdatum */ + { + if (cur->sk_flags & SK_BT_NULLS_FIRST) + result = 1; /* NOT_NULL ">" NULL */ + else + result = -1; /* NOT_NULL "<" NULL */ + } else - MemoryContextReset(so->arrayContext); - - oldContext = MemoryContextSwitchTo(so->arrayContext); - - /* Create output scan keys in the workspace context */ - arrayKeyData = (ScanKey) palloc(numberOfKeys * sizeof(ScanKeyData)); - - /* Allocate space for per-array data in the workspace context */ - so->arrayKeys = (BTArrayKeyInfo *) palloc(numArrayKeys * sizeof(BTArrayKeyInfo)); - - /* Allocate space for ORDER procs used to help _bt_checkkeys */ - so->orderProcs = (FmgrInfo *) palloc(numberOfKeys * sizeof(FmgrInfo)); - - /* Now process each array key */ - numArrayKeys = 0; - for (int input_ikey = 0; input_ikey < numberOfKeys; input_ikey++) { ++<<<<<<< ours ++======= + FmgrInfo sortproc; + FmgrInfo *sortprocp = &sortproc; + Oid elemtype; + bool reverse; + ArrayType *arrayval; + int16 elmlen; + bool elmbyval; + char elmalign; + char elmstor; + int num_elems; + Datum *elem_values; + bool *elem_nulls; + int num_nonnulls; + int j; + ++>>>>>>> theirs /* - * Provisionally copy scan key into arrayKeyData[] array we'll return - * to _bt_preprocess_keys caller + * Like _bt_compare, we need to be careful of cross-type comparisons, + * so the left value has to be the value that came from an index tuple */ - cur = &arrayKeyData[output_ikey]; - *cur = scan->keyData[input_ikey]; - - if (!(cur->sk_flags & SK_SEARCHARRAY)) - { - output_ikey++; /* keep this non-array scan key */ - continue; - } + result = DatumGetInt32(FunctionCall2Coll(orderproc, cur->sk_collation, + tupdatum, arrdatum)); /* - * Deconstruct the array into elements + * We flip the sign by following the obvious rule: flip whenever the + * column is a DESC column. + * + * _bt_compare does it the wrong way around (flip when *ASC*) in order + * to compensate for passing its orderproc arguments backwards. We + * don't need to play these games because we find it natural to pass + * tupdatum as the left value (and arrdatum as the right value). */ ++<<<<<<< ours + if (cur->sk_flags & SK_BT_DESC) + INVERT_COMPARE_RESULT(result); + } ++======= + arrayval = DatumGetArrayTypeP(cur->sk_argument); + /* We could cache this data, but not clear it's worth it */ + get_type_stores(ARR_ELEMTYPE(arrayval), + &elmlen, &elmbyval, &elmalign, &elmstor); + deconstruct_array(arrayval, + ARR_ELEMTYPE(arrayval), + elmlen, elmbyval, elmalign, elmstor, + &elem_values, &elem_nulls, &num_elems); ++>>>>>>> theirs - /* - * Compress out any null elements. We can ignore them since we assume - * all btree operators are strict. - */ - num_nonnulls = 0; - for (j = 0; j < num_elems; j++) - { - if (!elem_nulls[j]) - elem_values[num_nonnulls++] = elem_values[j]; - } + return result; +} - /* We could pfree(elem_nulls) now, but not worth the cycles */ +/* + * _bt_binsrch_array_skey() -- Binary search for next matching array key + * + * Returns an index to the first array element >= caller's tupdatum argument. + * This convention is more natural for forwards scan callers, but that can't + * really matter to backwards scan callers. Both callers require handling for + * the case where the match we return is < tupdatum, and symmetric handling + * for the case where our best match is > tupdatum. + * + * Also sets *set_elem_result to the result _bt_compare_array_skey returned + * when we used it to compare the matching array element to tupdatum/tupnull. + * + * cur_elem_trig indicates if array advancement was triggered by this array's + * scan key, and that the array is for a required scan key. We can apply this + * information to find the next matching array element in the current scan + * direction using far fewer comparisons (fewer on average, compared to naive + * binary search). This scheme takes advantage of an important property of + * required arrays: required arrays always advance in lockstep with the index + * scan's progress through the index's key space. + */ +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) +{ + int low_elem = 0, + mid_elem = -1, + high_elem = array->num_elems - 1, + result = 0; + Datum arrdatum; - /* If there's no non-nulls, the scan qual is unsatisfiable */ - if (num_nonnulls == 0) - { - so->qual_ok = false; - break; - } + Assert(cur->sk_flags & SK_SEARCHARRAY); + Assert(cur->sk_strategy == BTEqualStrategyNumber); - /* - * Determine the nominal datatype of the array elements. We have to - * support the convention that sk_subtype == InvalidOid means the - * opclass input type; this is a hack to simplify life for - * ScanKeyInit(). - */ - elemtype = cur->sk_subtype; - if (elemtype == InvalidOid) - elemtype = rel->rd_opcintype[cur->sk_attno - 1]; + if (cur_elem_trig) + { + Assert(!ScanDirectionIsNoMovement(dir)); + Assert(cur->sk_flags & SK_BT_REQFWD); /* - * If the comparison operator is not equality, then the array qual - * degenerates to a simple comparison against the smallest or largest - * non-null array element, as appropriate. + * When the scan key that triggered array advancement is a required + * array scan key, it is now certain that the current array element + * (plus all prior elements relative to the current scan direction) + * cannot possibly be at or ahead of the corresponding tuple value. + * (_bt_checkkeys must have called _bt_tuple_before_array_skeys, which + * makes sure this is true as a condition of advancing the arrays.) + * + * This makes it safe to exclude array elements up to and including + * the former-current array element from our search. + * + * Separately, when array advancement was triggered by a required scan + * key, the array element immediately after the former-current element + * is often either an exact tupdatum match, or a "close by" near-match + * (a near-match tupdatum is one whose key space falls _between_ the + * former-current and new-current array elements). We'll detect both + * cases via an optimistic comparison of the new search lower bound + * (or new search upper bound in the case of backwards scans). */ - switch (cur->sk_strategy) + if (ScanDirectionIsForward(dir)) { - case BTLessStrategyNumber: - case BTLessEqualStrategyNumber: - cur->sk_argument = - _bt_find_extreme_element(scan, cur, elemtype, - BTGreaterStrategyNumber, - elem_values, num_nonnulls); - output_ikey++; /* keep this transformed scan key */ - continue; - case BTEqualStrategyNumber: - /* proceed with rest of loop */ - break; - case BTGreaterEqualStrategyNumber: - case BTGreaterStrategyNumber: - cur->sk_argument = - _bt_find_extreme_element(scan, cur, elemtype, - BTLessStrategyNumber, - elem_values, num_nonnulls); - output_ikey++; /* keep this transformed scan key */ - continue; - default: - elog(ERROR, "unrecognized StrategyNumber: %d", - (int) cur->sk_strategy); - break; - } + low_elem = array->cur_elem + 1; /* old cur_elem exhausted */ - /* - * We'll need a 3-way ORDER proc to perform binary searches for the - * next matching array element. Set that up now. - * - * Array scan keys with cross-type equality operators will require a - * separate same-type ORDER proc for sorting their array. Otherwise, - * sortproc just points to the same proc used during binary searches. - */ - _bt_setup_array_cmp(scan, cur, elemtype, - &so->orderProcs[output_ikey], &sortprocp); + /* Compare prospective new cur_elem (also the new lower bound) */ + if (high_elem >= low_elem) + { + arrdatum = array->elem_values[low_elem]; + result = _bt_compare_array_skey(orderproc, tupdatum, tupnull, + arrdatum, cur); - /* - * Sort the non-null elements and eliminate any duplicates. We must - * sort in the same ordering used by the index column, so that the - * arrays can be advanced in lockstep with the scan's progress through - * the index's key space. - */ - reverse = (indoption[cur->sk_attno - 1] & INDOPTION_DESC) != 0; - num_elems = _bt_sort_array_elements(cur, sortprocp, reverse, - elem_values, num_nonnulls); + if (result <= 0) + { + /* Optimistic comparison optimization worked out */ + *set_elem_result = result; + return low_elem; + } + mid_elem = low_elem; + low_elem++; /* this cur_elem exhausted, too */ + } - if (origarrayatt == cur->sk_attno) + if (high_elem < low_elem) + { + /* Caller needs to perform "beyond end" array advancement */ + *set_elem_result = 1; + return high_elem; + } + } + else { - BTArrayKeyInfo *orig = &so->arrayKeys[origarraykey]; + high_elem = array->cur_elem - 1; /* old cur_elem exhausted */ - /* - * This array scan key is redundant with a previous equality - * operator array scan key. Merge the two arrays together to - * eliminate contradictory non-intersecting elements (or try to). - * - * We merge this next array back into attribute's original array. - */ - Assert(arrayKeyData[orig->scan_key].sk_attno == cur->sk_attno); - Assert(arrayKeyData[orig->scan_key].sk_collation == - cur->sk_collation); - if (_bt_merge_arrays(scan, cur, sortprocp, reverse, - origelemtype, elemtype, - orig->elem_values, &orig->num_elems, - elem_values, num_elems)) + /* Compare prospective new cur_elem (also the new upper bound) */ + if (high_elem >= low_elem) { - /* Successfully eliminated this array */ - pfree(elem_values); + arrdatum = array->elem_values[high_elem]; + result = _bt_compare_array_skey(orderproc, tupdatum, tupnull, + arrdatum, cur); - /* - * If no intersecting elements remain in the original array, - * the scan qual is unsatisfiable - */ - if (orig->num_elems == 0) + if (result >= 0) { - so->qual_ok = false; - break; + /* Optimistic comparison optimization worked out */ + *set_elem_result = result; + return high_elem; } - - /* Throw away this scan key/array */ - continue; + mid_elem = high_elem; + high_elem--; /* this cur_elem exhausted, too */ } - /* - * Unable to merge this array with previous array due to a lack of - * suitable cross-type opfamily support. Will need to keep both - * scan keys/arrays. - */ + if (high_elem < low_elem) + { + /* Caller needs to perform "beyond end" array advancement */ + *set_elem_result = -1; + return low_elem; + } } - else + } + + while (high_elem > low_elem) + { + mid_elem = low_elem + ((high_elem - low_elem) / 2); + arrdatum = array->elem_values[mid_elem]; + + result = _bt_compare_array_skey(orderproc, tupdatum, tupnull, + arrdatum, cur); + + if (result == 0) { /* - * This array is the first for current index attribute. - * - * If it turns out to not be the last array (that is, if the next - * array is redundantly applied to this same index attribute), - * we'll then treat this array as the attribute's "original" array - * when merging. + * It's safe to quit as soon as we see an equal array element. + * This often saves an extra comparison or two... */ - origarrayatt = cur->sk_attno; - origarraykey = numArrayKeys; - origelemtype = elemtype; + low_elem = mid_elem; + break; } - /* - * And set up the BTArrayKeyInfo data. - * - * Note: _bt_preprocess_array_keys_final will fix-up each array's - * scan_key field later on, after so->keyData[] has been finalized. - */ - so->arrayKeys[numArrayKeys].scan_key = output_ikey; - so->arrayKeys[numArrayKeys].num_elems = num_elems; - so->arrayKeys[numArrayKeys].elem_values = elem_values; - numArrayKeys++; - output_ikey++; /* keep this scan key/array */ + if (result > 0) + low_elem = mid_elem + 1; + else + high_elem = mid_elem; } - /* Set final number of equality-type array keys */ - so->numArrayKeys = numArrayKeys; - /* Set number of scan keys remaining in arrayKeyData[] */ - *new_numberOfKeys = output_ikey; + /* + * ...but our caller also cares about how its searched-for tuple datum + * compares to the low_elem datum. Must always set *set_elem_result with + * the result of that comparison specifically. + */ + if (low_elem != mid_elem) + result = _bt_compare_array_skey(orderproc, tupdatum, tupnull, + array->elem_values[low_elem], cur); - MemoryContextSwitchTo(oldContext); + *set_elem_result = result; - return arrayKeyData; + return low_elem; } /*