| 1 |
/*------------------------------------------------------------------------- |
| 2 |
* |
| 3 |
* nbtutils.c |
| 4 |
* Utility code for Postgres btree implementation. |
| 5 |
* |
| 6 |
* Portions Copyright (c) 1996-2025, PostgreSQL Global Development Group |
| 7 |
* Portions Copyright (c) 1994, Regents of the University of California |
| 8 |
* |
| 9 |
* |
| 10 |
* IDENTIFICATION |
| 11 |
* src/backend/access/nbtree/nbtutils.c |
| 12 |
* |
| 13 |
*------------------------------------------------------------------------- |
| 14 |
*/ |
| 15 |
|
| 16 |
#include "postgres.h" |
| 17 |
|
| 18 |
#include <time.h> |
| 19 |
|
| 20 |
#include "access/nbtree.h" |
| 21 |
#include "access/reloptions.h" |
| 22 |
#include "commands/progress.h" |
| 23 |
#include "miscadmin.h" |
| 24 |
#include "utils/datum.h" |
| 25 |
#include "utils/lsyscache.h" |
| 26 |
|
| 27 |
#define LOOK_AHEAD_REQUIRED_RECHECKS 3 |
| 28 |
#define LOOK_AHEAD_DEFAULT_DISTANCE 5 |
| 29 |
#define NSKIPADVANCES_THRESHOLD 3 |
| 30 |
|
| 31 |
static inline int32 _bt_compare_array_skey(FmgrInfo *orderproc, |
| 32 |
Datum tupdatum, bool tupnull, |
| 33 |
Datum arrdatum, ScanKey cur); |
| 34 |
static void _bt_binsrch_skiparray_skey(bool cur_elem_trig, ScanDirection dir, |
| 35 |
Datum tupdatum, bool tupnull, |
| 36 |
BTArrayKeyInfo *array, ScanKey cur, |
| 37 |
int32 *set_elem_result); |
| 38 |
static void _bt_skiparray_set_element(Relation rel, ScanKey skey, BTArrayKeyInfo *array, |
| 39 |
int32 set_elem_result, Datum tupdatum, bool tupnull); |
| 40 |
static void _bt_skiparray_set_isnull(Relation rel, ScanKey skey, BTArrayKeyInfo *array); |
| 41 |
static void _bt_array_set_low_or_high(Relation rel, ScanKey skey, |
| 42 |
BTArrayKeyInfo *array, bool low_not_high); |
| 43 |
static bool _bt_array_decrement(Relation rel, ScanKey skey, BTArrayKeyInfo *array); |
| 44 |
static bool _bt_array_increment(Relation rel, ScanKey skey, BTArrayKeyInfo *array); |
| 45 |
static bool _bt_advance_array_keys_increment(IndexScanDesc scan, ScanDirection dir, |
| 46 |
bool *skip_array_set); |
| 47 |
static bool _bt_tuple_before_array_skeys(IndexScanDesc scan, ScanDirection dir, |
| 48 |
IndexTuple tuple, TupleDesc tupdesc, int tupnatts, |
| 49 |
bool readpagetup, int sktrig, bool *scanBehind); |
| 50 |
static bool _bt_advance_array_keys(IndexScanDesc scan, BTReadPageState *pstate, |
| 51 |
IndexTuple tuple, int tupnatts, TupleDesc tupdesc, |
| 52 |
int sktrig, bool sktrig_required); |
| 53 |
#ifdef USE_ASSERT_CHECKING |
| 54 |
static bool _bt_verify_keys_with_arraykeys(IndexScanDesc scan); |
| 55 |
#endif |
| 56 |
static bool _bt_oppodir_checkkeys(IndexScanDesc scan, ScanDirection dir, |
| 57 |
IndexTuple finaltup); |
| 58 |
static bool _bt_check_compare(IndexScanDesc scan, ScanDirection dir, |
| 59 |
IndexTuple tuple, int tupnatts, TupleDesc tupdesc, |
| 60 |
bool advancenonrequired, bool forcenonrequired, |
| 61 |
bool *continuescan, int *ikey); |
| 62 |
static bool _bt_check_rowcompare(ScanKey header, |
| 63 |
IndexTuple tuple, int tupnatts, TupleDesc tupdesc, |
| 64 |
ScanDirection dir, bool forcenonrequired, bool *continuescan); |
| 65 |
static void _bt_checkkeys_look_ahead(IndexScanDesc scan, BTReadPageState *pstate, |
| 66 |
int tupnatts, TupleDesc tupdesc); |
| 67 |
static int _bt_keep_natts(Relation rel, IndexTuple lastleft, |
| 68 |
IndexTuple firstright, BTScanInsert itup_key); |
| 69 |
|
| 70 |
|
| 71 |
/* |
| 72 |
* _bt_mkscankey |
| 73 |
* Build an insertion scan key that contains comparison data from itup |
| 74 |
* as well as comparator routines appropriate to the key datatypes. |
| 75 |
* |
| 76 |
* The result is intended for use with _bt_compare() and _bt_truncate(). |
| 77 |
* Callers that don't need to fill out the insertion scankey arguments |
| 78 |
* (e.g. they use an ad-hoc comparison routine, or only need a scankey |
| 79 |
* for _bt_truncate()) can pass a NULL index tuple. The scankey will |
| 80 |
* be initialized as if an "all truncated" pivot tuple was passed |
| 81 |
* instead. |
| 82 |
* |
| 83 |
* Note that we may occasionally have to share lock the metapage to |
| 84 |
* determine whether or not the keys in the index are expected to be |
| 85 |
* unique (i.e. if this is a "heapkeyspace" index). We assume a |
| 86 |
* heapkeyspace index when caller passes a NULL tuple, allowing index |
| 87 |
* build callers to avoid accessing the non-existent metapage. We |
| 88 |
* also assume that the index is _not_ allequalimage when a NULL tuple |
| 89 |
* is passed; CREATE INDEX callers call _bt_allequalimage() to set the |
| 90 |
* field themselves. |
| 91 |
*/ |
| 92 |
BTScanInsert |
| 93 |
_bt_mkscankey(Relation rel, IndexTuple itup) |
| 94 |
{ |
| 95 |
BTScanInsert key; |
| 96 |
ScanKey skey; |
| 97 |
TupleDesc itupdesc; |
| 98 |
int indnkeyatts; |
| 99 |
int16 *indoption; |
| 100 |
int tupnatts; |
| 101 |
int i; |
| 102 |
|
| 103 |
itupdesc = RelationGetDescr(rel); |
| 104 |
indnkeyatts = IndexRelationGetNumberOfKeyAttributes(rel); |
| 105 |
indoption = rel->rd_indoption; |
| 106 |
tupnatts = itup ? BTreeTupleGetNAtts(itup, rel) : 0; |
| 107 |
|
| 108 |
Assert(tupnatts <= IndexRelationGetNumberOfAttributes(rel)); |
| 109 |
|
| 110 |
/* |
| 111 |
* We'll execute search using scan key constructed on key columns. |
| 112 |
* Truncated attributes and non-key attributes are omitted from the final |
| 113 |
* scan key. |
| 114 |
*/ |
| 115 |
key = palloc(offsetof(BTScanInsertData, scankeys) + |
| 116 |
sizeof(ScanKeyData) * indnkeyatts); |
| 117 |
if (itup) |
| 118 |
_bt_metaversion(rel, &key->heapkeyspace, &key->allequalimage); |
| 119 |
else |
| 120 |
{ |
| 121 |
/* Utility statement callers can set these fields themselves */ |
| 122 |
key->heapkeyspace = true; |
| 123 |
key->allequalimage = false; |
| 124 |
} |
| 125 |
key->anynullkeys = false; /* initial assumption */ |
| 126 |
key->nextkey = false; /* usual case, required by btinsert */ |
| 127 |
key->backward = false; /* usual case, required by btinsert */ |
| 128 |
key->keysz = Min(indnkeyatts, tupnatts); |
| 129 |
key->scantid = key->heapkeyspace && itup ? |
| 130 |
BTreeTupleGetHeapTID(itup) : NULL; |
| 131 |
skey = key->scankeys; |
| 132 |
for (i = 0; i < indnkeyatts; i++) |
| 133 |
{ |
| 134 |
FmgrInfo *procinfo; |
| 135 |
Datum arg; |
| 136 |
bool null; |
| 137 |
int flags; |
| 138 |
|
| 139 |
/* |
| 140 |
* We can use the cached (default) support procs since no cross-type |
| 141 |
* comparison can be needed. |
| 142 |
*/ |
| 143 |
procinfo = index_getprocinfo(rel, i + 1, BTORDER_PROC); |
| 144 |
|
| 145 |
/* |
| 146 |
* Key arguments built from truncated attributes (or when caller |
| 147 |
* provides no tuple) are defensively represented as NULL values. They |
| 148 |
* should never be used. |
| 149 |
*/ |
| 150 |
if (i < tupnatts) |
| 151 |
arg = index_getattr(itup, i + 1, itupdesc, &null); |
| 152 |
else |
| 153 |
{ |
| 154 |
arg = (Datum) 0; |
| 155 |
null = true; |
| 156 |
} |
| 157 |
flags = (null ? SK_ISNULL : 0) | (indoption[i] << SK_BT_INDOPTION_SHIFT); |
| 158 |
ScanKeyEntryInitializeWithInfo(&skey[i], |
| 159 |
flags, |
| 160 |
(AttrNumber) (i + 1), |
| 161 |
InvalidStrategy, |
| 162 |
InvalidOid, |
| 163 |
rel->rd_indcollation[i], |
| 164 |
procinfo, |
| 165 |
arg); |
| 166 |
/* Record if any key attribute is NULL (or truncated) */ |
| 167 |
if (null) |
| 168 |
key->anynullkeys = true; |
| 169 |
} |
| 170 |
|
| 171 |
/* |
| 172 |
* In NULLS NOT DISTINCT mode, we pretend that there are no null keys, so |
| 173 |
* that full uniqueness check is done. |
| 174 |
*/ |
| 175 |
if (rel->rd_index->indnullsnotdistinct) |
| 176 |
key->anynullkeys = false; |
| 177 |
|
| 178 |
return key; |
| 179 |
} |
| 180 |
|
| 181 |
/* |
| 182 |
* free a retracement stack made by _bt_search. |
| 183 |
*/ |
| 184 |
void |
| 185 |
_bt_freestack(BTStack stack) |
| 186 |
{ |
| 187 |
BTStack ostack; |
| 188 |
|
| 189 |
while (stack != NULL) |
| 190 |
{ |
| 191 |
ostack = stack; |
| 192 |
stack = stack->bts_parent; |
| 193 |
pfree(ostack); |
| 194 |
} |
| 195 |
} |
| 196 |
|
| 197 |
/* |
| 198 |
* _bt_compare_array_skey() -- apply array comparison function |
| 199 |
* |
| 200 |
* Compares caller's tuple attribute value to a scan key/array element. |
| 201 |
* Helper function used during binary searches of SK_SEARCHARRAY arrays. |
| 202 |
* |
| 203 |
* This routine returns: |
| 204 |
* <0 if tupdatum < arrdatum; |
| 205 |
* 0 if tupdatum == arrdatum; |
| 206 |
* >0 if tupdatum > arrdatum. |
| 207 |
* |
| 208 |
* This is essentially the same interface as _bt_compare: both functions |
| 209 |
* compare the value that they're searching for to a binary search pivot. |
| 210 |
* However, unlike _bt_compare, this function's "tuple argument" comes first, |
| 211 |
* while its "array/scankey argument" comes second. |
| 212 |
*/ |
| 213 |
static inline int32 |
| 214 |
_bt_compare_array_skey(FmgrInfo *orderproc, |
| 215 |
Datum tupdatum, bool tupnull, |
| 216 |
Datum arrdatum, ScanKey cur) |
| 217 |
{ |
| 218 |
int32 result = 0; |
| 219 |
|
| 220 |
Assert(cur->sk_strategy == BTEqualStrategyNumber); |
| 221 |
Assert(!(cur->sk_flags & (SK_BT_MINVAL | SK_BT_MAXVAL))); |
| 222 |
|
| 223 |
if (tupnull) /* NULL tupdatum */ |
| 224 |
{ |
| 225 |
if (cur->sk_flags & SK_ISNULL) |
| 226 |
result = 0; /* NULL "=" NULL */ |
| 227 |
else if (cur->sk_flags & SK_BT_NULLS_FIRST) |
| 228 |
result = -1; /* NULL "<" NOT_NULL */ |
| 229 |
else |
| 230 |
result = 1; /* NULL ">" NOT_NULL */ |
| 231 |
} |
| 232 |
else if (cur->sk_flags & SK_ISNULL) /* NOT_NULL tupdatum, NULL arrdatum */ |
| 233 |
{ |
| 234 |
if (cur->sk_flags & SK_BT_NULLS_FIRST) |
| 235 |
result = 1; /* NOT_NULL ">" NULL */ |
| 236 |
else |
| 237 |
result = -1; /* NOT_NULL "<" NULL */ |
| 238 |
} |
| 239 |
else |
| 240 |
{ |
| 241 |
/* |
| 242 |
* Like _bt_compare, we need to be careful of cross-type comparisons, |
| 243 |
* so the left value has to be the value that came from an index tuple |
| 244 |
*/ |
| 245 |
result = DatumGetInt32(FunctionCall2Coll(orderproc, cur->sk_collation, |
| 246 |
tupdatum, arrdatum)); |
| 247 |
|
| 248 |
/* |
| 249 |
* We flip the sign by following the obvious rule: flip whenever the |
| 250 |
* column is a DESC column. |
| 251 |
* |
| 252 |
* _bt_compare does it the wrong way around (flip when *ASC*) in order |
| 253 |
* to compensate for passing its orderproc arguments backwards. We |
| 254 |
* don't need to play these games because we find it natural to pass |
| 255 |
* tupdatum as the left value (and arrdatum as the right value). |
| 256 |
*/ |
| 257 |
if (cur->sk_flags & SK_BT_DESC) |
| 258 |
INVERT_COMPARE_RESULT(result); |
| 259 |
} |
| 260 |
|
| 261 |
return result; |
| 262 |
} |
| 263 |
|
| 264 |
/* |
| 265 |
* _bt_binsrch_array_skey() -- Binary search for next matching array key |
| 266 |
* |
| 267 |
* Returns an index to the first array element >= caller's tupdatum argument. |
| 268 |
* This convention is more natural for forwards scan callers, but that can't |
| 269 |
* really matter to backwards scan callers. Both callers require handling for |
| 270 |
* the case where the match we return is < tupdatum, and symmetric handling |
| 271 |
* for the case where our best match is > tupdatum. |
| 272 |
* |
| 273 |
* Also sets *set_elem_result to the result _bt_compare_array_skey returned |
| 274 |
* when we used it to compare the matching array element to tupdatum/tupnull. |
| 275 |
* |
| 276 |
* cur_elem_trig indicates if array advancement was triggered by this array's |
| 277 |
* scan key, and that the array is for a required scan key. We can apply this |
| 278 |
* information to find the next matching array element in the current scan |
| 279 |
* direction using far fewer comparisons (fewer on average, compared to naive |
| 280 |
* binary search). This scheme takes advantage of an important property of |
| 281 |
* required arrays: required arrays always advance in lockstep with the index |
| 282 |
* scan's progress through the index's key space. |
| 283 |
*/ |
| 284 |
int |
| 285 |
_bt_binsrch_array_skey(FmgrInfo *orderproc, |
| 286 |
bool cur_elem_trig, ScanDirection dir, |
| 287 |
Datum tupdatum, bool tupnull, |
| 288 |
BTArrayKeyInfo *array, ScanKey cur, |
| 289 |
int32 *set_elem_result) |
| 290 |
{ |
| 291 |
int low_elem = 0, |
| 292 |
mid_elem = -1, |
| 293 |
high_elem = array->num_elems - 1, |
| 294 |
result = 0; |
| 295 |
Datum arrdatum; |
| 296 |
|
| 297 |
Assert(cur->sk_flags & SK_SEARCHARRAY); |
| 298 |
Assert(!(cur->sk_flags & SK_BT_SKIP)); |
| 299 |
Assert(!(cur->sk_flags & SK_ISNULL)); /* SAOP arrays never have NULLs */ |
| 300 |
Assert(cur->sk_strategy == BTEqualStrategyNumber); |
| 301 |
|
| 302 |
if (cur_elem_trig) |
| 303 |
{ |
| 304 |
Assert(!ScanDirectionIsNoMovement(dir)); |
| 305 |
Assert(cur->sk_flags & SK_BT_REQFWD); |
| 306 |
|
| 307 |
/* |
| 308 |
* When the scan key that triggered array advancement is a required |
| 309 |
* array scan key, it is now certain that the current array element |
| 310 |
* (plus all prior elements relative to the current scan direction) |
| 311 |
* cannot possibly be at or ahead of the corresponding tuple value. |
| 312 |
* (_bt_checkkeys must have called _bt_tuple_before_array_skeys, which |
| 313 |
* makes sure this is true as a condition of advancing the arrays.) |
| 314 |
* |
| 315 |
* This makes it safe to exclude array elements up to and including |
| 316 |
* the former-current array element from our search. |
| 317 |
* |
| 318 |
* Separately, when array advancement was triggered by a required scan |
| 319 |
* key, the array element immediately after the former-current element |
| 320 |
* is often either an exact tupdatum match, or a "close by" near-match |
| 321 |
* (a near-match tupdatum is one whose key space falls _between_ the |
| 322 |
* former-current and new-current array elements). We'll detect both |
| 323 |
* cases via an optimistic comparison of the new search lower bound |
| 324 |
* (or new search upper bound in the case of backwards scans). |
| 325 |
*/ |
| 326 |
if (ScanDirectionIsForward(dir)) |
| 327 |
{ |
| 328 |
low_elem = array->cur_elem + 1; /* old cur_elem exhausted */ |
| 329 |
|
| 330 |
/* Compare prospective new cur_elem (also the new lower bound) */ |
| 331 |
if (high_elem >= low_elem) |
| 332 |
{ |
| 333 |
arrdatum = array->elem_values[low_elem]; |
| 334 |
result = _bt_compare_array_skey(orderproc, tupdatum, tupnull, |
| 335 |
arrdatum, cur); |
| 336 |
|
| 337 |
if (result <= 0) |
| 338 |
{ |
| 339 |
/* Optimistic comparison optimization worked out */ |
| 340 |
*set_elem_result = result; |
| 341 |
return low_elem; |
| 342 |
} |
| 343 |
mid_elem = low_elem; |
| 344 |
low_elem++; /* this cur_elem exhausted, too */ |
| 345 |
} |
| 346 |
|
| 347 |
if (high_elem < low_elem) |
| 348 |
{ |
| 349 |
/* Caller needs to perform "beyond end" array advancement */ |
| 350 |
*set_elem_result = 1; |
| 351 |
return high_elem; |
| 352 |
} |
| 353 |
} |
| 354 |
else |
| 355 |
{ |
| 356 |
high_elem = array->cur_elem - 1; /* old cur_elem exhausted */ |
| 357 |
|
| 358 |
/* Compare prospective new cur_elem (also the new upper bound) */ |
| 359 |
if (high_elem >= low_elem) |
| 360 |
{ |
| 361 |
arrdatum = array->elem_values[high_elem]; |
| 362 |
result = _bt_compare_array_skey(orderproc, tupdatum, tupnull, |
| 363 |
arrdatum, cur); |
| 364 |
|
| 365 |
if (result >= 0) |
| 366 |
{ |
| 367 |
/* Optimistic comparison optimization worked out */ |
| 368 |
*set_elem_result = result; |
| 369 |
return high_elem; |
| 370 |
} |
| 371 |
mid_elem = high_elem; |
| 372 |
high_elem--; /* this cur_elem exhausted, too */ |
| 373 |
} |
| 374 |
|
| 375 |
if (high_elem < low_elem) |
| 376 |
{ |
| 377 |
/* Caller needs to perform "beyond end" array advancement */ |
| 378 |
*set_elem_result = -1; |
| 379 |
return low_elem; |
| 380 |
} |
| 381 |
} |
| 382 |
} |
| 383 |
|
| 384 |
while (high_elem > low_elem) |
| 385 |
{ |
| 386 |
mid_elem = low_elem + ((high_elem - low_elem) / 2); |
| 387 |
arrdatum = array->elem_values[mid_elem]; |
| 388 |
|
| 389 |
result = _bt_compare_array_skey(orderproc, tupdatum, tupnull, |
| 390 |
arrdatum, cur); |
| 391 |
|
| 392 |
if (result == 0) |
| 393 |
{ |
| 394 |
/* |
| 395 |
* It's safe to quit as soon as we see an equal array element. |
| 396 |
* This often saves an extra comparison or two... |
| 397 |
*/ |
| 398 |
low_elem = mid_elem; |
| 399 |
break; |
| 400 |
} |
| 401 |
|
| 402 |
if (result > 0) |
| 403 |
low_elem = mid_elem + 1; |
| 404 |
else |
| 405 |
high_elem = mid_elem; |
| 406 |
} |
| 407 |
|
| 408 |
/* |
| 409 |
* ...but our caller also cares about how its searched-for tuple datum |
| 410 |
* compares to the low_elem datum. Must always set *set_elem_result with |
| 411 |
* the result of that comparison specifically. |
| 412 |
*/ |
| 413 |
if (low_elem != mid_elem) |
| 414 |
result = _bt_compare_array_skey(orderproc, tupdatum, tupnull, |
| 415 |
array->elem_values[low_elem], cur); |
| 416 |
|
| 417 |
*set_elem_result = result; |
| 418 |
|
| 419 |
return low_elem; |
| 420 |
} |
| 421 |
|
| 422 |
/* |
| 423 |
* _bt_binsrch_skiparray_skey() -- "Binary search" within a skip array |
| 424 |
* |
| 425 |
* Does not return an index into the array, since skip arrays don't really |
| 426 |
* contain elements (they generate their array elements procedurally instead). |
| 427 |
* Our interface matches that of _bt_binsrch_array_skey in every other way. |
| 428 |
* |
| 429 |
* Sets *set_elem_result just like _bt_binsrch_array_skey would with a true |
| 430 |
* array. The value 0 indicates that tupdatum/tupnull is within the range of |
| 431 |
* the skip array. We return -1 when tupdatum/tupnull is lower that any value |
| 432 |
* within the range of the array, and 1 when it is higher than every value. |
| 433 |
* Caller should pass *set_elem_result to _bt_skiparray_set_element to advance |
| 434 |
* the array. |
| 435 |
* |
| 436 |
* cur_elem_trig indicates if array advancement was triggered by this array's |
| 437 |
* scan key. We use this to optimize-away comparisons that are known by our |
| 438 |
* caller to be unnecessary from context, just like _bt_binsrch_array_skey. |
| 439 |
*/ |
| 440 |
static void |
| 441 |
_bt_binsrch_skiparray_skey(bool cur_elem_trig, ScanDirection dir, |
| 442 |
Datum tupdatum, bool tupnull, |
| 443 |
BTArrayKeyInfo *array, ScanKey cur, |
| 444 |
int32 *set_elem_result) |
| 445 |
{ |
| 446 |
Assert(cur->sk_flags & SK_BT_SKIP); |
| 447 |
Assert(cur->sk_flags & SK_SEARCHARRAY); |
| 448 |
Assert(cur->sk_flags & SK_BT_REQFWD); |
| 449 |
Assert(array->num_elems == -1); |
| 450 |
Assert(!ScanDirectionIsNoMovement(dir)); |
| 451 |
|
| 452 |
if (array->null_elem) |
| 453 |
{ |
| 454 |
Assert(!array->low_compare && !array->high_compare); |
| 455 |
|
| 456 |
*set_elem_result = 0; |
| 457 |
return; |
| 458 |
} |
| 459 |
|
| 460 |
if (tupnull) /* NULL tupdatum */ |
| 461 |
{ |
| 462 |
if (cur->sk_flags & SK_BT_NULLS_FIRST) |
| 463 |
*set_elem_result = -1; /* NULL "<" NOT_NULL */ |
| 464 |
else |
| 465 |
*set_elem_result = 1; /* NULL ">" NOT_NULL */ |
| 466 |
return; |
| 467 |
} |
| 468 |
|
| 469 |
/* |
| 470 |
* Array inequalities determine whether tupdatum is within the range of |
| 471 |
* caller's skip array |
| 472 |
*/ |
| 473 |
*set_elem_result = 0; |
| 474 |
if (ScanDirectionIsForward(dir)) |
| 475 |
{ |
| 476 |
/* |
| 477 |
* Evaluate low_compare first (unless cur_elem_trig tells us that it |
| 478 |
* cannot possibly fail to be satisfied), then evaluate high_compare |
| 479 |
*/ |
| 480 |
if (!cur_elem_trig && array->low_compare && |
| 481 |
!DatumGetBool(FunctionCall2Coll(&array->low_compare->sk_func, |
| 482 |
array->low_compare->sk_collation, |
| 483 |
tupdatum, |
| 484 |
array->low_compare->sk_argument))) |
| 485 |
*set_elem_result = -1; |
| 486 |
else if (array->high_compare && |
| 487 |
!DatumGetBool(FunctionCall2Coll(&array->high_compare->sk_func, |
| 488 |
array->high_compare->sk_collation, |
| 489 |
tupdatum, |
| 490 |
array->high_compare->sk_argument))) |
| 491 |
*set_elem_result = 1; |
| 492 |
} |
| 493 |
else |
| 494 |
{ |
| 495 |
/* |
| 496 |
* Evaluate high_compare first (unless cur_elem_trig tells us that it |
| 497 |
* cannot possibly fail to be satisfied), then evaluate low_compare |
| 498 |
*/ |
| 499 |
if (!cur_elem_trig && array->high_compare && |
| 500 |
!DatumGetBool(FunctionCall2Coll(&array->high_compare->sk_func, |
| 501 |
array->high_compare->sk_collation, |
| 502 |
tupdatum, |
| 503 |
array->high_compare->sk_argument))) |
| 504 |
*set_elem_result = 1; |
| 505 |
else if (array->low_compare && |
| 506 |
!DatumGetBool(FunctionCall2Coll(&array->low_compare->sk_func, |
| 507 |
array->low_compare->sk_collation, |
| 508 |
tupdatum, |
| 509 |
array->low_compare->sk_argument))) |
| 510 |
*set_elem_result = -1; |
| 511 |
} |
| 512 |
|
| 513 |
/* |
| 514 |
* Assert that any keys that were assumed to be satisfied already (due to |
| 515 |
* caller passing cur_elem_trig=true) really are satisfied as expected |
| 516 |
*/ |
| 517 |
#ifdef USE_ASSERT_CHECKING |
| 518 |
if (cur_elem_trig) |
| 519 |
{ |
| 520 |
if (ScanDirectionIsForward(dir) && array->low_compare) |
| 521 |
Assert(DatumGetBool(FunctionCall2Coll(&array->low_compare->sk_func, |
| 522 |
array->low_compare->sk_collation, |
| 523 |
tupdatum, |
| 524 |
array->low_compare->sk_argument))); |
| 525 |
|
| 526 |
if (ScanDirectionIsBackward(dir) && array->high_compare) |
| 527 |
Assert(DatumGetBool(FunctionCall2Coll(&array->high_compare->sk_func, |
| 528 |
array->high_compare->sk_collation, |
| 529 |
tupdatum, |
| 530 |
array->high_compare->sk_argument))); |
| 531 |
} |
| 532 |
#endif |
| 533 |
} |
| 534 |
|
| 535 |
/* |
| 536 |
* _bt_skiparray_set_element() -- Set skip array scan key's sk_argument |
| 537 |
* |
| 538 |
* Caller passes set_elem_result returned by _bt_binsrch_skiparray_skey for |
| 539 |
* caller's tupdatum/tupnull. |
| 540 |
* |
| 541 |
* We copy tupdatum/tupnull into skey's sk_argument iff set_elem_result == 0. |
| 542 |
* Otherwise, we set skey to either the lowest or highest value that's within |
| 543 |
* the range of caller's skip array (whichever is the best available match to |
| 544 |
* tupdatum/tupnull that is still within the range of the skip array according |
| 545 |
* to _bt_binsrch_skiparray_skey/set_elem_result). |
| 546 |
*/ |
| 547 |
static void |
| 548 |
_bt_skiparray_set_element(Relation rel, ScanKey skey, BTArrayKeyInfo *array, |
| 549 |
int32 set_elem_result, Datum tupdatum, bool tupnull) |
| 550 |
{ |
| 551 |
Assert(skey->sk_flags & SK_BT_SKIP); |
| 552 |
Assert(skey->sk_flags & SK_SEARCHARRAY); |
| 553 |
|
| 554 |
if (set_elem_result) |
| 555 |
{ |
| 556 |
/* tupdatum/tupnull is out of the range of the skip array */ |
| 557 |
Assert(!array->null_elem); |
| 558 |
|
| 559 |
_bt_array_set_low_or_high(rel, skey, array, set_elem_result < 0); |
| 560 |
return; |
| 561 |
} |
| 562 |
|
| 563 |
/* Advance skip array to tupdatum (or tupnull) value */ |
| 564 |
if (unlikely(tupnull)) |
| 565 |
{ |
| 566 |
_bt_skiparray_set_isnull(rel, skey, array); |
| 567 |
return; |
| 568 |
} |
| 569 |
|
| 570 |
/* Free memory previously allocated for sk_argument if needed */ |
| 571 |
if (!array->attbyval && skey->sk_argument) |
| 572 |
pfree(DatumGetPointer(skey->sk_argument)); |
| 573 |
|
| 574 |
/* tupdatum becomes new sk_argument/new current element */ |
| 575 |
skey->sk_flags &= ~(SK_SEARCHNULL | SK_ISNULL | |
| 576 |
SK_BT_MINVAL | SK_BT_MAXVAL | |
| 577 |
SK_BT_NEXT | SK_BT_PRIOR); |
| 578 |
skey->sk_argument = datumCopy(tupdatum, array->attbyval, array->attlen); |
| 579 |
} |
| 580 |
|
| 581 |
/* |
| 582 |
* _bt_skiparray_set_isnull() -- set skip array scan key to NULL |
| 583 |
*/ |
| 584 |
static void |
| 585 |
_bt_skiparray_set_isnull(Relation rel, ScanKey skey, BTArrayKeyInfo *array) |
| 586 |
{ |
| 587 |
Assert(skey->sk_flags & SK_BT_SKIP); |
| 588 |
Assert(skey->sk_flags & SK_SEARCHARRAY); |
| 589 |
Assert(array->null_elem && !array->low_compare && !array->high_compare); |
| 590 |
|
| 591 |
/* Free memory previously allocated for sk_argument if needed */ |
| 592 |
if (!array->attbyval && skey->sk_argument) |
| 593 |
pfree(DatumGetPointer(skey->sk_argument)); |
| 594 |
|
| 595 |
/* NULL becomes new sk_argument/new current element */ |
| 596 |
skey->sk_argument = (Datum) 0; |
| 597 |
skey->sk_flags &= ~(SK_BT_MINVAL | SK_BT_MAXVAL | |
| 598 |
SK_BT_NEXT | SK_BT_PRIOR); |
| 599 |
skey->sk_flags |= (SK_SEARCHNULL | SK_ISNULL); |
| 600 |
} |
| 601 |
|
| 602 |
/* |
| 603 |
* _bt_start_array_keys() -- Initialize array keys at start of a scan |
| 604 |
* |
| 605 |
* Set up the cur_elem counters and fill in the first sk_argument value for |
| 606 |
* each array scankey. |
| 607 |
*/ |
| 608 |
void |
| 609 |
_bt_start_array_keys(IndexScanDesc scan, ScanDirection dir) |
| 610 |
{ |
| 611 |
Relation rel = scan->indexRelation; |
| 612 |
BTScanOpaque so = (BTScanOpaque) scan->opaque; |
| 613 |
|
| 614 |
Assert(so->numArrayKeys); |
| 615 |
Assert(so->qual_ok); |
| 616 |
|
| 617 |
for (int i = 0; i < so->numArrayKeys; i++) |
| 618 |
{ |
| 619 |
BTArrayKeyInfo *array = &so->arrayKeys[i]; |
| 620 |
ScanKey skey = &so->keyData[array->scan_key]; |
| 621 |
|
| 622 |
Assert(skey->sk_flags & SK_SEARCHARRAY); |
| 623 |
|
| 624 |
_bt_array_set_low_or_high(rel, skey, array, |
| 625 |
ScanDirectionIsForward(dir)); |
| 626 |
} |
| 627 |
so->scanBehind = so->oppositeDirCheck = false; /* reset */ |
| 628 |
} |
| 629 |
|
| 630 |
/* |
| 631 |
* _bt_array_set_low_or_high() -- Set array scan key to lowest/highest element |
| 632 |
* |
| 633 |
* Caller also passes associated scan key, which will have its argument set to |
| 634 |
* the lowest/highest array value in passing. |
| 635 |
*/ |
| 636 |
static void |
| 637 |
_bt_array_set_low_or_high(Relation rel, ScanKey skey, BTArrayKeyInfo *array, |
| 638 |
bool low_not_high) |
| 639 |
{ |
| 640 |
Assert(skey->sk_flags & SK_SEARCHARRAY); |
| 641 |
|
| 642 |
if (array->num_elems != -1) |
| 643 |
{ |
| 644 |
/* set low or high element for SAOP array */ |
| 645 |
int set_elem = 0; |
| 646 |
|
| 647 |
Assert(!(skey->sk_flags & SK_BT_SKIP)); |
| 648 |
|
| 649 |
if (!low_not_high) |
| 650 |
set_elem = array->num_elems - 1; |
| 651 |
|
| 652 |
/* |
| 653 |
* Just copy over array datum (only skip arrays require freeing and |
| 654 |
* allocating memory for sk_argument) |
| 655 |
*/ |
| 656 |
array->cur_elem = set_elem; |
| 657 |
skey->sk_argument = array->elem_values[set_elem]; |
| 658 |
|
| 659 |
return; |
| 660 |
} |
| 661 |
|
| 662 |
/* set low or high element for skip array */ |
| 663 |
Assert(skey->sk_flags & SK_BT_SKIP); |
| 664 |
Assert(array->num_elems == -1); |
| 665 |
|
| 666 |
/* Free memory previously allocated for sk_argument if needed */ |
| 667 |
if (!array->attbyval && skey->sk_argument) |
| 668 |
pfree(DatumGetPointer(skey->sk_argument)); |
| 669 |
|
| 670 |
/* Reset flags */ |
| 671 |
skey->sk_argument = (Datum) 0; |
| 672 |
skey->sk_flags &= ~(SK_SEARCHNULL | SK_ISNULL | |
| 673 |
SK_BT_MINVAL | SK_BT_MAXVAL | |
| 674 |
SK_BT_NEXT | SK_BT_PRIOR); |
| 675 |
|
| 676 |
if (array->null_elem && |
| 677 |
(low_not_high == ((skey->sk_flags & SK_BT_NULLS_FIRST) != 0))) |
| 678 |
{ |
| 679 |
/* Requested element (either lowest or highest) has the value NULL */ |
| 680 |
skey->sk_flags |= (SK_SEARCHNULL | SK_ISNULL); |
| 681 |
} |
| 682 |
else if (low_not_high) |
| 683 |
{ |
| 684 |
/* Setting array to lowest element (according to low_compare) */ |
| 685 |
skey->sk_flags |= SK_BT_MINVAL; |
| 686 |
} |
| 687 |
else |
| 688 |
{ |
| 689 |
/* Setting array to highest element (according to high_compare) */ |
| 690 |
skey->sk_flags |= SK_BT_MAXVAL; |
| 691 |
} |
| 692 |
} |
| 693 |
|
| 694 |
/* |
| 695 |
* _bt_array_decrement() -- decrement array scan key's sk_argument |
| 696 |
* |
| 697 |
* Return value indicates whether caller's array was successfully decremented. |
| 698 |
* Cannot decrement an array whose current element is already the first one. |
| 699 |
*/ |
| 700 |
static bool |
| 701 |
_bt_array_decrement(Relation rel, ScanKey skey, BTArrayKeyInfo *array) |
| 702 |
{ |
| 703 |
bool uflow = false; |
| 704 |
Datum dec_sk_argument; |
| 705 |
|
| 706 |
Assert(skey->sk_flags & SK_SEARCHARRAY); |
| 707 |
Assert(!(skey->sk_flags & (SK_BT_MAXVAL | SK_BT_NEXT | SK_BT_PRIOR))); |
| 708 |
|
| 709 |
/* SAOP array? */ |
| 710 |
if (array->num_elems != -1) |
| 711 |
{ |
| 712 |
Assert(!(skey->sk_flags & (SK_BT_SKIP | SK_BT_MINVAL | SK_BT_MAXVAL))); |
| 713 |
if (array->cur_elem > 0) |
| 714 |
{ |
| 715 |
/* |
| 716 |
* Just decrement current element, and assign its datum to skey |
| 717 |
* (only skip arrays need us to free existing sk_argument memory) |
| 718 |
*/ |
| 719 |
array->cur_elem--; |
| 720 |
skey->sk_argument = array->elem_values[array->cur_elem]; |
| 721 |
|
| 722 |
/* Successfully decremented array */ |
| 723 |
return true; |
| 724 |
} |
| 725 |
|
| 726 |
/* Cannot decrement to before first array element */ |
| 727 |
return false; |
| 728 |
} |
| 729 |
|
| 730 |
/* Nope, this is a skip array */ |
| 731 |
Assert(skey->sk_flags & SK_BT_SKIP); |
| 732 |
|
| 733 |
/* |
| 734 |
* The sentinel value that represents the minimum value within the range |
| 735 |
* of a skip array (often just -inf) is never decrementable |
| 736 |
*/ |
| 737 |
if (skey->sk_flags & SK_BT_MINVAL) |
| 738 |
return false; |
| 739 |
|
| 740 |
/* |
| 741 |
* When the current array element is NULL, and the lowest sorting value in |
| 742 |
* the index is also NULL, we cannot decrement before first array element |
| 743 |
*/ |
| 744 |
if ((skey->sk_flags & SK_ISNULL) && (skey->sk_flags & SK_BT_NULLS_FIRST)) |
| 745 |
return false; |
| 746 |
|
| 747 |
/* |
| 748 |
* Opclasses without skip support "decrement" the scan key's current |
| 749 |
* element by setting the PRIOR flag. The true prior value is determined |
| 750 |
* by repositioning to the last index tuple < existing sk_argument/current |
| 751 |
* array element. Note that this works in the usual way when the scan key |
| 752 |
* is already marked ISNULL (i.e. when the current element is NULL). |
| 753 |
*/ |
| 754 |
if (!array->sksup) |
| 755 |
{ |
| 756 |
/* Successfully "decremented" array */ |
| 757 |
skey->sk_flags |= SK_BT_PRIOR; |
| 758 |
return true; |
| 759 |
} |
| 760 |
|
| 761 |
/* |
| 762 |
* Opclasses with skip support directly decrement sk_argument |
| 763 |
*/ |
| 764 |
if (skey->sk_flags & SK_ISNULL) |
| 765 |
{ |
| 766 |
Assert(!(skey->sk_flags & SK_BT_NULLS_FIRST)); |
| 767 |
|
| 768 |
/* |
| 769 |
* Existing sk_argument/array element is NULL (for an IS NULL qual). |
| 770 |
* |
| 771 |
* "Decrement" from NULL to the high_elem value provided by opclass |
| 772 |
* skip support routine. |
| 773 |
*/ |
| 774 |
skey->sk_flags &= ~(SK_SEARCHNULL | SK_ISNULL); |
| 775 |
skey->sk_argument = datumCopy(array->sksup->high_elem, |
| 776 |
array->attbyval, array->attlen); |
| 777 |
return true; |
| 778 |
} |
| 779 |
|
| 780 |
/* |
| 781 |
* Ask opclass support routine to provide decremented copy of existing |
| 782 |
* non-NULL sk_argument |
| 783 |
*/ |
| 784 |
dec_sk_argument = array->sksup->decrement(rel, skey->sk_argument, &uflow); |
| 785 |
if (unlikely(uflow)) |
| 786 |
{ |
| 787 |
/* dec_sk_argument has undefined value (so no pfree) */ |
| 788 |
if (array->null_elem && (skey->sk_flags & SK_BT_NULLS_FIRST)) |
| 789 |
{ |
| 790 |
_bt_skiparray_set_isnull(rel, skey, array); |
| 791 |
|
| 792 |
/* Successfully "decremented" array to NULL */ |
| 793 |
return true; |
| 794 |
} |
| 795 |
|
| 796 |
/* Cannot decrement to before first array element */ |
| 797 |
return false; |
| 798 |
} |
| 799 |
|
| 800 |
/* |
| 801 |
* Successfully decremented sk_argument to a non-NULL value. Make sure |
| 802 |
* that the decremented value is still within the range of the array. |
| 803 |
*/ |
| 804 |
if (array->low_compare && |
| 805 |
!DatumGetBool(FunctionCall2Coll(&array->low_compare->sk_func, |
| 806 |
array->low_compare->sk_collation, |
| 807 |
dec_sk_argument, |
| 808 |
array->low_compare->sk_argument))) |
| 809 |
{ |
| 810 |
/* Keep existing sk_argument after all */ |
| 811 |
if (!array->attbyval) |
| 812 |
pfree(DatumGetPointer(dec_sk_argument)); |
| 813 |
|
| 814 |
/* Cannot decrement to before first array element */ |
| 815 |
return false; |
| 816 |
} |
| 817 |
|
| 818 |
/* Accept value returned by opclass decrement callback */ |
| 819 |
if (!array->attbyval && skey->sk_argument) |
| 820 |
pfree(DatumGetPointer(skey->sk_argument)); |
| 821 |
skey->sk_argument = dec_sk_argument; |
| 822 |
|
| 823 |
/* Successfully decremented array */ |
| 824 |
return true; |
| 825 |
} |
| 826 |
|
| 827 |
/* |
| 828 |
* _bt_array_increment() -- increment array scan key's sk_argument |
| 829 |
* |
| 830 |
* Return value indicates whether caller's array was successfully incremented. |
| 831 |
* Cannot increment an array whose current element is already the final one. |
| 832 |
*/ |
| 833 |
static bool |
| 834 |
_bt_array_increment(Relation rel, ScanKey skey, BTArrayKeyInfo *array) |
| 835 |
{ |
| 836 |
bool oflow = false; |
| 837 |
Datum inc_sk_argument; |
| 838 |
|
| 839 |
Assert(skey->sk_flags & SK_SEARCHARRAY); |
| 840 |
Assert(!(skey->sk_flags & (SK_BT_MINVAL | SK_BT_NEXT | SK_BT_PRIOR))); |
| 841 |
|
| 842 |
/* SAOP array? */ |
| 843 |
if (array->num_elems != -1) |
| 844 |
{ |
| 845 |
Assert(!(skey->sk_flags & (SK_BT_SKIP | SK_BT_MINVAL | SK_BT_MAXVAL))); |
| 846 |
if (array->cur_elem < array->num_elems - 1) |
| 847 |
{ |
| 848 |
/* |
| 849 |
* Just increment current element, and assign its datum to skey |
| 850 |
* (only skip arrays need us to free existing sk_argument memory) |
| 851 |
*/ |
| 852 |
array->cur_elem++; |
| 853 |
skey->sk_argument = array->elem_values[array->cur_elem]; |
| 854 |
|
| 855 |
/* Successfully incremented array */ |
| 856 |
return true; |
| 857 |
} |
| 858 |
|
| 859 |
/* Cannot increment past final array element */ |
| 860 |
return false; |
| 861 |
} |
| 862 |
|
| 863 |
/* Nope, this is a skip array */ |
| 864 |
Assert(skey->sk_flags & SK_BT_SKIP); |
| 865 |
|
| 866 |
/* |
| 867 |
* The sentinel value that represents the maximum value within the range |
| 868 |
* of a skip array (often just +inf) is never incrementable |
| 869 |
*/ |
| 870 |
if (skey->sk_flags & SK_BT_MAXVAL) |
| 871 |
return false; |
| 872 |
|
| 873 |
/* |
| 874 |
* When the current array element is NULL, and the highest sorting value |
| 875 |
* in the index is also NULL, we cannot increment past the final element |
| 876 |
*/ |
| 877 |
if ((skey->sk_flags & SK_ISNULL) && !(skey->sk_flags & SK_BT_NULLS_FIRST)) |
| 878 |
return false; |
| 879 |
|
| 880 |
/* |
| 881 |
* Opclasses without skip support "increment" the scan key's current |
| 882 |
* element by setting the NEXT flag. The true next value is determined by |
| 883 |
* repositioning to the first index tuple > existing sk_argument/current |
| 884 |
* array element. Note that this works in the usual way when the scan key |
| 885 |
* is already marked ISNULL (i.e. when the current element is NULL). |
| 886 |
*/ |
| 887 |
if (!array->sksup) |
| 888 |
{ |
| 889 |
/* Successfully "incremented" array */ |
| 890 |
skey->sk_flags |= SK_BT_NEXT; |
| 891 |
return true; |
| 892 |
} |
| 893 |
|
| 894 |
/* |
| 895 |
* Opclasses with skip support directly increment sk_argument |
| 896 |
*/ |
| 897 |
if (skey->sk_flags & SK_ISNULL) |
| 898 |
{ |
| 899 |
Assert(skey->sk_flags & SK_BT_NULLS_FIRST); |
| 900 |
|
| 901 |
/* |
| 902 |
* Existing sk_argument/array element is NULL (for an IS NULL qual). |
| 903 |
* |
| 904 |
* "Increment" from NULL to the low_elem value provided by opclass |
| 905 |
* skip support routine. |
| 906 |
*/ |
| 907 |
skey->sk_flags &= ~(SK_SEARCHNULL | SK_ISNULL); |
| 908 |
skey->sk_argument = datumCopy(array->sksup->low_elem, |
| 909 |
array->attbyval, array->attlen); |
| 910 |
return true; |
| 911 |
} |
| 912 |
|
| 913 |
/* |
| 914 |
* Ask opclass support routine to provide incremented copy of existing |
| 915 |
* non-NULL sk_argument |
| 916 |
*/ |
| 917 |
inc_sk_argument = array->sksup->increment(rel, skey->sk_argument, &oflow); |
| 918 |
if (unlikely(oflow)) |
| 919 |
{ |
| 920 |
/* inc_sk_argument has undefined value (so no pfree) */ |
| 921 |
if (array->null_elem && !(skey->sk_flags & SK_BT_NULLS_FIRST)) |
| 922 |
{ |
| 923 |
_bt_skiparray_set_isnull(rel, skey, array); |
| 924 |
|
| 925 |
/* Successfully "incremented" array to NULL */ |
| 926 |
return true; |
| 927 |
} |
| 928 |
|
| 929 |
/* Cannot increment past final array element */ |
| 930 |
return false; |
| 931 |
} |
| 932 |
|
| 933 |
/* |
| 934 |
* Successfully incremented sk_argument to a non-NULL value. Make sure |
| 935 |
* that the incremented value is still within the range of the array. |
| 936 |
*/ |
| 937 |
if (array->high_compare && |
| 938 |
!DatumGetBool(FunctionCall2Coll(&array->high_compare->sk_func, |
| 939 |
array->high_compare->sk_collation, |
| 940 |
inc_sk_argument, |
| 941 |
array->high_compare->sk_argument))) |
| 942 |
{ |
| 943 |
/* Keep existing sk_argument after all */ |
| 944 |
if (!array->attbyval) |
| 945 |
pfree(DatumGetPointer(inc_sk_argument)); |
| 946 |
|
| 947 |
/* Cannot increment past final array element */ |
| 948 |
return false; |
| 949 |
} |
| 950 |
|
| 951 |
/* Accept value returned by opclass increment callback */ |
| 952 |
if (!array->attbyval && skey->sk_argument) |
| 953 |
pfree(DatumGetPointer(skey->sk_argument)); |
| 954 |
skey->sk_argument = inc_sk_argument; |
| 955 |
|
| 956 |
/* Successfully incremented array */ |
| 957 |
return true; |
| 958 |
} |
| 959 |
|
| 960 |
/* |
| 961 |
* _bt_advance_array_keys_increment() -- Advance to next set of array elements |
| 962 |
* |
| 963 |
* Advances the array keys by a single increment in the current scan |
| 964 |
* direction. When there are multiple array keys this can roll over from the |
| 965 |
* lowest order array to higher order arrays. |
| 966 |
* |
| 967 |
* Returns true if there is another set of values to consider, false if not. |
| 968 |
* On true result, the scankeys are initialized with the next set of values. |
| 969 |
* On false result, the scankeys stay the same, and the array keys are not |
| 970 |
* advanced (every array remains at its final element for scan direction). |
| 971 |
*/ |
| 972 |
static bool |
| 973 |
_bt_advance_array_keys_increment(IndexScanDesc scan, ScanDirection dir, |
| 974 |
bool *skip_array_set) |
| 975 |
{ |
| 976 |
Relation rel = scan->indexRelation; |
| 977 |
BTScanOpaque so = (BTScanOpaque) scan->opaque; |
| 978 |
|
| 979 |
/* |
| 980 |
* We must advance the last array key most quickly, since it will |
| 981 |
* correspond to the lowest-order index column among the available |
| 982 |
* qualifications |
| 983 |
*/ |
| 984 |
for (int i = so->numArrayKeys - 1; i >= 0; i--) |
| 985 |
{ |
| 986 |
BTArrayKeyInfo *array = &so->arrayKeys[i]; |
| 987 |
ScanKey skey = &so->keyData[array->scan_key]; |
| 988 |
|
| 989 |
if (array->num_elems == -1) |
| 990 |
*skip_array_set = true; |
| 991 |
|
| 992 |
if (ScanDirectionIsForward(dir)) |
| 993 |
{ |
| 994 |
if (_bt_array_increment(rel, skey, array)) |
| 995 |
return true; |
| 996 |
} |
| 997 |
else |
| 998 |
{ |
| 999 |
if (_bt_array_decrement(rel, skey, array)) |
| 1000 |
return true; |
| 1001 |
} |
| 1002 |
|
| 1003 |
/* |
| 1004 |
* Couldn't increment (or decrement) array. Handle array roll over. |
| 1005 |
* |
| 1006 |
* Start over at the array's lowest sorting value (or its highest |
| 1007 |
* value, for backward scans)... |
| 1008 |
*/ |
| 1009 |
_bt_array_set_low_or_high(rel, skey, array, |
| 1010 |
ScanDirectionIsForward(dir)); |
| 1011 |
|
| 1012 |
/* ...then increment (or decrement) next most significant array */ |
| 1013 |
} |
| 1014 |
|
| 1015 |
/* |
| 1016 |
* The array keys are now exhausted. |
| 1017 |
* |
| 1018 |
* Restore the array keys to the state they were in immediately before we |
| 1019 |
* were called. This ensures that the arrays only ever ratchet in the |
| 1020 |
* current scan direction. |
| 1021 |
* |
| 1022 |
* Without this, scans could overlook matching tuples when the scan |
| 1023 |
* direction gets reversed just before btgettuple runs out of items to |
| 1024 |
* return, but just after _bt_readpage prepares all the items from the |
| 1025 |
* scan's final page in so->currPos. When we're on the final page it is |
| 1026 |
* typical for so->currPos to get invalidated once btgettuple finally |
| 1027 |
* returns false, which'll effectively invalidate the scan's array keys. |
| 1028 |
* That hasn't happened yet, though -- and in general it may never happen. |
| 1029 |
*/ |
| 1030 |
_bt_start_array_keys(scan, -dir); |
| 1031 |
|
| 1032 |
return false; |
| 1033 |
} |
| 1034 |
|
| 1035 |
/* |
| 1036 |
* _bt_tuple_before_array_skeys() -- too early to advance required arrays? |
| 1037 |
* |
| 1038 |
* We always compare the tuple using the current array keys (which we assume |
| 1039 |
* are already set in so->keyData[]). readpagetup indicates if tuple is the |
| 1040 |
* scan's current _bt_readpage-wise tuple. |
| 1041 |
* |
| 1042 |
* readpagetup callers must only call here when _bt_check_compare already set |
| 1043 |
* continuescan=false. We help these callers deal with _bt_check_compare's |
| 1044 |
* inability to distinguish between the < and > cases (it uses equality |
| 1045 |
* operator scan keys, whereas we use 3-way ORDER procs). These callers pass |
| 1046 |
* a _bt_check_compare-set sktrig value that indicates which scan key |
| 1047 |
* triggered the call (!readpagetup callers just pass us sktrig=0 instead). |
| 1048 |
* This information allows us to avoid wastefully checking earlier scan keys |
| 1049 |
* that were already deemed to have been satisfied inside _bt_check_compare. |
| 1050 |
* |
| 1051 |
* Returns false when caller's tuple is >= the current required equality scan |
| 1052 |
* keys (or <=, in the case of backwards scans). This happens to readpagetup |
| 1053 |
* callers when the scan has reached the point of needing its array keys |
| 1054 |
* advanced; caller will need to advance required and non-required arrays at |
| 1055 |
* scan key offsets >= sktrig, plus scan keys < sktrig iff sktrig rolls over. |
| 1056 |
* (When we return false to readpagetup callers, tuple can only be == current |
| 1057 |
* required equality scan keys when caller's sktrig indicates that the arrays |
| 1058 |
* need to be advanced due to an unsatisfied required inequality key trigger.) |
| 1059 |
* |
| 1060 |
* Returns true when caller passes a tuple that is < the current set of |
| 1061 |
* equality keys for the most significant non-equal required scan key/column |
| 1062 |
* (or > the keys, during backwards scans). This happens to readpagetup |
| 1063 |
* callers when tuple is still before the start of matches for the scan's |
| 1064 |
* required equality strategy scan keys. (sktrig can't have indicated that an |
| 1065 |
* inequality strategy scan key wasn't satisfied in _bt_check_compare when we |
| 1066 |
* return true. In fact, we automatically return false when passed such an |
| 1067 |
* inequality sktrig by readpagetup callers -- _bt_check_compare's initial |
| 1068 |
* continuescan=false doesn't really need to be confirmed here by us.) |
| 1069 |
* |
| 1070 |
* !readpagetup callers optionally pass us *scanBehind, which tracks whether |
| 1071 |
* any missing truncated attributes might have affected array advancement |
| 1072 |
* (compared to what would happen if it was shown the first non-pivot tuple on |
| 1073 |
* the page to the right of caller's finaltup/high key tuple instead). It's |
| 1074 |
* only possible that we'll set *scanBehind to true when caller passes us a |
| 1075 |
* pivot tuple (with truncated -inf attributes) that we return false for. |
| 1076 |
*/ |
| 1077 |
static bool |
| 1078 |
_bt_tuple_before_array_skeys(IndexScanDesc scan, ScanDirection dir, |
| 1079 |
IndexTuple tuple, TupleDesc tupdesc, int tupnatts, |
| 1080 |
bool readpagetup, int sktrig, bool *scanBehind) |
| 1081 |
{ |
| 1082 |
BTScanOpaque so = (BTScanOpaque) scan->opaque; |
| 1083 |
|
| 1084 |
Assert(so->numArrayKeys); |
| 1085 |
Assert(so->numberOfKeys); |
| 1086 |
Assert(sktrig == 0 || readpagetup); |
| 1087 |
Assert(!readpagetup || scanBehind == NULL); |
| 1088 |
|
| 1089 |
if (scanBehind) |
| 1090 |
*scanBehind = false; |
| 1091 |
|
| 1092 |
for (int ikey = sktrig; ikey < so->numberOfKeys; ikey++) |
| 1093 |
{ |
| 1094 |
ScanKey cur = so->keyData + ikey; |
| 1095 |
Datum tupdatum; |
| 1096 |
bool tupnull; |
| 1097 |
int32 result; |
| 1098 |
|
| 1099 |
/* readpagetup calls require one ORDER proc comparison (at most) */ |
| 1100 |
Assert(!readpagetup || ikey == sktrig); |
| 1101 |
|
| 1102 |
/* |
| 1103 |
* Once we reach a non-required scan key, we're completely done. |
| 1104 |
* |
| 1105 |
* Note: we deliberately don't consider the scan direction here. |
| 1106 |
* _bt_advance_array_keys caller requires that we track *scanBehind |
| 1107 |
* without concern for scan direction. |
| 1108 |
*/ |
| 1109 |
if ((cur->sk_flags & (SK_BT_REQFWD | SK_BT_REQBKWD)) == 0) |
| 1110 |
{ |
| 1111 |
Assert(!readpagetup); |
| 1112 |
Assert(ikey > sktrig || ikey == 0); |
| 1113 |
return false; |
| 1114 |
} |
| 1115 |
|
| 1116 |
if (cur->sk_attno > tupnatts) |
| 1117 |
{ |
| 1118 |
Assert(!readpagetup); |
| 1119 |
|
| 1120 |
/* |
| 1121 |
* When we reach a high key's truncated attribute, assume that the |
| 1122 |
* tuple attribute's value is >= the scan's equality constraint |
| 1123 |
* scan keys (but set *scanBehind to let interested callers know |
| 1124 |
* that a truncated attribute might have affected our answer). |
| 1125 |
*/ |
| 1126 |
if (scanBehind) |
| 1127 |
*scanBehind = true; |
| 1128 |
|
| 1129 |
return false; |
| 1130 |
} |
| 1131 |
|
| 1132 |
/* |
| 1133 |
* Deal with inequality strategy scan keys that _bt_check_compare set |
| 1134 |
* continuescan=false for |
| 1135 |
*/ |
| 1136 |
if (cur->sk_strategy != BTEqualStrategyNumber) |
| 1137 |
{ |
| 1138 |
/* |
| 1139 |
* When _bt_check_compare indicated that a required inequality |
| 1140 |
* scan key wasn't satisfied, there's no need to verify anything; |
| 1141 |
* caller always calls _bt_advance_array_keys with this sktrig. |
| 1142 |
*/ |
| 1143 |
if (readpagetup) |
| 1144 |
return false; |
| 1145 |
|
| 1146 |
/* |
| 1147 |
* Otherwise we can't give up, since we must check all required |
| 1148 |
* scan keys (required in either direction) in order to correctly |
| 1149 |
* track *scanBehind for caller |
| 1150 |
*/ |
| 1151 |
continue; |
| 1152 |
} |
| 1153 |
|
| 1154 |
tupdatum = index_getattr(tuple, cur->sk_attno, tupdesc, &tupnull); |
| 1155 |
|
| 1156 |
if (likely(!(cur->sk_flags & (SK_BT_MINVAL | SK_BT_MAXVAL)))) |
| 1157 |
{ |
| 1158 |
/* Scankey has a valid/comparable sk_argument value */ |
| 1159 |
result = _bt_compare_array_skey(&so->orderProcs[ikey], |
| 1160 |
tupdatum, tupnull, |
| 1161 |
cur->sk_argument, cur); |
| 1162 |
|
| 1163 |
if (result == 0) |
| 1164 |
{ |
| 1165 |
/* |
| 1166 |
* Interpret result in a way that takes NEXT/PRIOR into |
| 1167 |
* account |
| 1168 |
*/ |
| 1169 |
if (cur->sk_flags & SK_BT_NEXT) |
| 1170 |
result = -1; |
| 1171 |
else if (cur->sk_flags & SK_BT_PRIOR) |
| 1172 |
result = 1; |
| 1173 |
|
| 1174 |
Assert(result == 0 || (cur->sk_flags & SK_BT_SKIP)); |
| 1175 |
} |
| 1176 |
} |
| 1177 |
else |
| 1178 |
{ |
| 1179 |
BTArrayKeyInfo *array = NULL; |
| 1180 |
|
| 1181 |
/* |
| 1182 |
* Current array element/array = scan key value is a sentinel |
| 1183 |
* value that represents the lowest (or highest) possible value |
| 1184 |
* that's still within the range of the array. |
| 1185 |
* |
| 1186 |
* Like _bt_first, we only see MINVAL keys during forwards scans |
| 1187 |
* (and similarly only see MAXVAL keys during backwards scans). |
| 1188 |
* Even if the scan's direction changes, we'll stop at some higher |
| 1189 |
* order key before we can ever reach any MAXVAL (or MINVAL) keys. |
| 1190 |
* (However, unlike _bt_first we _can_ get to keys marked either |
| 1191 |
* NEXT or PRIOR, regardless of the scan's current direction.) |
| 1192 |
*/ |
| 1193 |
Assert(ScanDirectionIsForward(dir) ? |
| 1194 |
!(cur->sk_flags & SK_BT_MAXVAL) : |
| 1195 |
!(cur->sk_flags & SK_BT_MINVAL)); |
| 1196 |
|
| 1197 |
/* |
| 1198 |
* There are no valid sk_argument values in MINVAL/MAXVAL keys. |
| 1199 |
* Check if tupdatum is within the range of skip array instead. |
| 1200 |
*/ |
| 1201 |
for (int arrayidx = 0; arrayidx < so->numArrayKeys; arrayidx++) |
| 1202 |
{ |
| 1203 |
array = &so->arrayKeys[arrayidx]; |
| 1204 |
if (array->scan_key == ikey) |
| 1205 |
break; |
| 1206 |
} |
| 1207 |
|
| 1208 |
_bt_binsrch_skiparray_skey(false, dir, tupdatum, tupnull, |
| 1209 |
array, cur, &result); |
| 1210 |
|
| 1211 |
if (result == 0) |
| 1212 |
{ |
| 1213 |
/* |
| 1214 |
* tupdatum satisfies both low_compare and high_compare, so |
| 1215 |
* it's time to advance the array keys. |
| 1216 |
* |
| 1217 |
* Note: It's possible that the skip array will "advance" from |
| 1218 |
* its MINVAL (or MAXVAL) representation to an alternative, |
| 1219 |
* logically equivalent representation of the same value: a |
| 1220 |
* representation where the = key gets a valid datum in its |
| 1221 |
* sk_argument. This is only possible when low_compare uses |
| 1222 |
* the >= strategy (or high_compare uses the <= strategy). |
| 1223 |
*/ |
| 1224 |
return false; |
| 1225 |
} |
| 1226 |
} |
| 1227 |
|
| 1228 |
/* |
| 1229 |
* Does this comparison indicate that caller must _not_ advance the |
| 1230 |
* scan's arrays just yet? |
| 1231 |
*/ |
| 1232 |
if ((ScanDirectionIsForward(dir) && result < 0) || |
| 1233 |
(ScanDirectionIsBackward(dir) && result > 0)) |
| 1234 |
return true; |
| 1235 |
|
| 1236 |
/* |
| 1237 |
* Does this comparison indicate that caller should now advance the |
| 1238 |
* scan's arrays? (Must be if we get here during a readpagetup call.) |
| 1239 |
*/ |
| 1240 |
if (readpagetup || result != 0) |
| 1241 |
{ |
| 1242 |
Assert(result != 0); |
| 1243 |
return false; |
| 1244 |
} |
| 1245 |
|
| 1246 |
/* |
| 1247 |
* Inconclusive -- need to check later scan keys, too. |
| 1248 |
* |
| 1249 |
* This must be a finaltup precheck, or a call made from an assertion. |
| 1250 |
*/ |
| 1251 |
Assert(result == 0); |
| 1252 |
} |
| 1253 |
|
| 1254 |
Assert(!readpagetup); |
| 1255 |
|
| 1256 |
return false; |
| 1257 |
} |
| 1258 |
|
| 1259 |
/* |
| 1260 |
* _bt_start_prim_scan() -- start scheduled primitive index scan? |
| 1261 |
* |
| 1262 |
* Returns true if _bt_checkkeys scheduled another primitive index scan, just |
| 1263 |
* as the last one ended. Otherwise returns false, indicating that the array |
| 1264 |
* keys are now fully exhausted. |
| 1265 |
* |
| 1266 |
* Only call here during scans with one or more equality type array scan keys, |
| 1267 |
* after _bt_first or _bt_next return false. |
| 1268 |
*/ |
| 1269 |
bool |
| 1270 |
_bt_start_prim_scan(IndexScanDesc scan, ScanDirection dir) |
| 1271 |
{ |
| 1272 |
BTScanOpaque so = (BTScanOpaque) scan->opaque; |
| 1273 |
|
| 1274 |
Assert(so->numArrayKeys); |
| 1275 |
|
| 1276 |
so->scanBehind = so->oppositeDirCheck = false; /* reset */ |
| 1277 |
|
| 1278 |
/* |
| 1279 |
* Array keys are advanced within _bt_checkkeys when the scan reaches the |
| 1280 |
* leaf level (more precisely, they're advanced when the scan reaches the |
| 1281 |
* end of each distinct set of array elements). This process avoids |
| 1282 |
* repeat access to leaf pages (across multiple primitive index scans) by |
| 1283 |
* advancing the scan's array keys when it allows the primitive index scan |
| 1284 |
* to find nearby matching tuples (or when it eliminates ranges of array |
| 1285 |
* key space that can't possibly be satisfied by any index tuple). |
| 1286 |
* |
| 1287 |
* _bt_checkkeys sets a simple flag variable to schedule another primitive |
| 1288 |
* index scan. The flag tells us what to do. |
| 1289 |
* |
| 1290 |
* We cannot rely on _bt_first always reaching _bt_checkkeys. There are |
| 1291 |
* various cases where that won't happen. For example, if the index is |
| 1292 |
* completely empty, then _bt_first won't call _bt_readpage/_bt_checkkeys. |
| 1293 |
* We also don't expect a call to _bt_checkkeys during searches for a |
| 1294 |
* non-existent value that happens to be lower/higher than any existing |
| 1295 |
* value in the index. |
| 1296 |
* |
| 1297 |
* We don't require special handling for these cases -- we don't need to |
| 1298 |
* be explicitly instructed to _not_ perform another primitive index scan. |
| 1299 |
* It's up to code under the control of _bt_first to always set the flag |
| 1300 |
* when another primitive index scan will be required. |
| 1301 |
* |
| 1302 |
* This works correctly, even with the tricky cases listed above, which |
| 1303 |
* all involve access to leaf pages "near the boundaries of the key space" |
| 1304 |
* (whether it's from a leftmost/rightmost page, or an imaginary empty |
| 1305 |
* leaf root page). If _bt_checkkeys cannot be reached by a primitive |
| 1306 |
* index scan for one set of array keys, then it also won't be reached for |
| 1307 |
* any later set ("later" in terms of the direction that we scan the index |
| 1308 |
* and advance the arrays). The array keys won't have advanced in these |
| 1309 |
* cases, but that's the correct behavior (even _bt_advance_array_keys |
| 1310 |
* won't always advance the arrays at the point they become "exhausted"). |
| 1311 |
*/ |
| 1312 |
if (so->needPrimScan) |
| 1313 |
{ |
| 1314 |
/* |
| 1315 |
* Flag was set -- must call _bt_first again, which will reset the |
| 1316 |
* scan's needPrimScan flag |
| 1317 |
*/ |
| 1318 |
return true; |
| 1319 |
} |
| 1320 |
|
| 1321 |
/* The top-level index scan ran out of tuples in this scan direction */ |
| 1322 |
if (scan->parallel_scan != NULL) |
| 1323 |
_bt_parallel_done(scan); |
| 1324 |
|
| 1325 |
return false; |
| 1326 |
} |
| 1327 |
|
| 1328 |
/* |
| 1329 |
* _bt_advance_array_keys() -- Advance array elements using a tuple |
| 1330 |
* |
| 1331 |
* The scan always gets a new qual as a consequence of calling here (except |
| 1332 |
* when we determine that the top-level scan has run out of matching tuples). |
| 1333 |
* All later _bt_check_compare calls also use the same new qual that was first |
| 1334 |
* used here (at least until the next call here advances the keys once again). |
| 1335 |
* It's convenient to structure _bt_check_compare rechecks of caller's tuple |
| 1336 |
* (using the new qual) as one the steps of advancing the scan's array keys, |
| 1337 |
* so this function works as a wrapper around _bt_check_compare. |
| 1338 |
* |
| 1339 |
* Like _bt_check_compare, we'll set pstate.continuescan on behalf of the |
| 1340 |
* caller, and return a boolean indicating if caller's tuple satisfies the |
| 1341 |
* scan's new qual. But unlike _bt_check_compare, we set so->needPrimScan |
| 1342 |
* when we set continuescan=false, indicating if a new primitive index scan |
| 1343 |
* has been scheduled (otherwise, the top-level scan has run out of tuples in |
| 1344 |
* the current scan direction). |
| 1345 |
* |
| 1346 |
* Caller must use _bt_tuple_before_array_skeys to determine if the current |
| 1347 |
* place in the scan is >= the current array keys _before_ calling here. |
| 1348 |
* We're responsible for ensuring that caller's tuple is <= the newly advanced |
| 1349 |
* required array keys once we return. We try to find an exact match, but |
| 1350 |
* failing that we'll advance the array keys to whatever set of array elements |
| 1351 |
* comes next in the key space for the current scan direction. Required array |
| 1352 |
* keys "ratchet forwards" (or backwards). They can only advance as the scan |
| 1353 |
* itself advances through the index/key space. |
| 1354 |
* |
| 1355 |
* (The rules are the same for backwards scans, except that the operators are |
| 1356 |
* flipped: just replace the precondition's >= operator with a <=, and the |
| 1357 |
* postcondition's <= operator with a >=. In other words, just swap the |
| 1358 |
* precondition with the postcondition.) |
| 1359 |
* |
| 1360 |
* We also deal with "advancing" non-required arrays here (or arrays that are |
| 1361 |
* treated as non-required for the duration of a _bt_readpage call). Callers |
| 1362 |
* whose sktrig scan key is non-required specify sktrig_required=false. These |
| 1363 |
* calls are the only exception to the general rule about always advancing the |
| 1364 |
* required array keys (the scan may not even have a required array). These |
| 1365 |
* callers should just pass a NULL pstate (since there is never any question |
| 1366 |
* of stopping the scan). No call to _bt_tuple_before_array_skeys is required |
| 1367 |
* ahead of these calls (it's already clear that any required scan keys must |
| 1368 |
* be satisfied by caller's tuple). |
| 1369 |
* |
| 1370 |
* Note that we deal with non-array required equality strategy scan keys as |
| 1371 |
* degenerate single element arrays here. Obviously, they can never really |
| 1372 |
* advance in the way that real arrays can, but they must still affect how we |
| 1373 |
* advance real array scan keys (exactly like true array equality scan keys). |
| 1374 |
* We have to keep around a 3-way ORDER proc for these (using the "=" operator |
| 1375 |
* won't do), since in general whether the tuple is < or > _any_ unsatisfied |
| 1376 |
* required equality key influences how the scan's real arrays must advance. |
| 1377 |
* |
| 1378 |
* Note also that we may sometimes need to advance the array keys when the |
| 1379 |
* existing required array keys (and other required equality keys) are already |
| 1380 |
* an exact match for every corresponding value from caller's tuple. We must |
| 1381 |
* do this for inequalities that _bt_check_compare set continuescan=false for. |
| 1382 |
* They'll advance the array keys here, just like any other scan key that |
| 1383 |
* _bt_check_compare stops on. (This can even happen _after_ we advance the |
| 1384 |
* array keys, in which case we'll advance the array keys a second time. That |
| 1385 |
* way _bt_checkkeys caller always has its required arrays advance to the |
| 1386 |
* maximum possible extent that its tuple will allow.) |
| 1387 |
*/ |
| 1388 |
static bool |
| 1389 |
_bt_advance_array_keys(IndexScanDesc scan, BTReadPageState *pstate, |
| 1390 |
IndexTuple tuple, int tupnatts, TupleDesc tupdesc, |
| 1391 |
int sktrig, bool sktrig_required) |
| 1392 |
{ |
| 1393 |
BTScanOpaque so = (BTScanOpaque) scan->opaque; |
| 1394 |
Relation rel = scan->indexRelation; |
| 1395 |
ScanDirection dir = so->currPos.dir; |
| 1396 |
int arrayidx = 0; |
| 1397 |
bool beyond_end_advance = false, |
| 1398 |
skip_array_advanced = false, |
| 1399 |
has_required_opposite_direction_only = false, |
| 1400 |
all_required_satisfied = true, |
| 1401 |
all_satisfied = true; |
| 1402 |
|
| 1403 |
Assert(!so->needPrimScan && !so->scanBehind && !so->oppositeDirCheck); |
| 1404 |
Assert(_bt_verify_keys_with_arraykeys(scan)); |
| 1405 |
|
| 1406 |
if (sktrig_required) |
| 1407 |
{ |
| 1408 |
/* |
| 1409 |
* Precondition array state assertion |
| 1410 |
*/ |
| 1411 |
Assert(!_bt_tuple_before_array_skeys(scan, dir, tuple, tupdesc, |
| 1412 |
tupnatts, false, 0, NULL)); |
| 1413 |
|
| 1414 |
/* |
| 1415 |
* Once we return we'll have a new set of required array keys, so |
| 1416 |
* reset state used by "look ahead" optimization |
| 1417 |
*/ |
| 1418 |
pstate->rechecks = 0; |
| 1419 |
pstate->targetdistance = 0; |
| 1420 |
} |
| 1421 |
else if (sktrig < so->numberOfKeys - 1 && |
| 1422 |
!(so->keyData[so->numberOfKeys - 1].sk_flags & SK_SEARCHARRAY)) |
| 1423 |
{ |
| 1424 |
int least_sign_ikey = so->numberOfKeys - 1; |
| 1425 |
bool continuescan; |
| 1426 |
|
| 1427 |
/* |
| 1428 |
* Optimization: perform a precheck of the least significant key |
| 1429 |
* during !sktrig_required calls when it isn't already our sktrig |
| 1430 |
* (provided the precheck key is not itself an array). |
| 1431 |
* |
| 1432 |
* When the precheck works out we'll avoid an expensive binary search |
| 1433 |
* of sktrig's array (plus any other arrays before least_sign_ikey). |
| 1434 |
*/ |
| 1435 |
Assert(so->keyData[sktrig].sk_flags & SK_SEARCHARRAY); |
| 1436 |
if (!_bt_check_compare(scan, dir, tuple, tupnatts, tupdesc, false, |
| 1437 |
false, &continuescan, |
| 1438 |
&least_sign_ikey)) |
| 1439 |
return false; |
| 1440 |
} |
| 1441 |
|
| 1442 |
for (int ikey = 0; ikey < so->numberOfKeys; ikey++) |
| 1443 |
{ |
| 1444 |
ScanKey cur = so->keyData + ikey; |
| 1445 |
BTArrayKeyInfo *array = NULL; |
| 1446 |
Datum tupdatum; |
| 1447 |
bool required = false, |
| 1448 |
tupnull; |
| 1449 |
int32 result; |
| 1450 |
int set_elem = 0; |
| 1451 |
|
| 1452 |
if (cur->sk_strategy == BTEqualStrategyNumber) |
| 1453 |
{ |
| 1454 |
/* Manage array state */ |
| 1455 |
if (cur->sk_flags & SK_SEARCHARRAY) |
| 1456 |
{ |
| 1457 |
array = &so->arrayKeys[arrayidx++]; |
| 1458 |
Assert(array->scan_key == ikey); |
| 1459 |
} |
| 1460 |
} |
| 1461 |
else |
| 1462 |
{ |
| 1463 |
/* |
| 1464 |
* Are any inequalities required in the opposite direction only |
| 1465 |
* present here? |
| 1466 |
*/ |
| 1467 |
if (((ScanDirectionIsForward(dir) && |
| 1468 |
(cur->sk_flags & (SK_BT_REQBKWD))) || |
| 1469 |
(ScanDirectionIsBackward(dir) && |
| 1470 |
(cur->sk_flags & (SK_BT_REQFWD))))) |
| 1471 |
has_required_opposite_direction_only = true; |
| 1472 |
} |
| 1473 |
|
| 1474 |
/* Optimization: skip over known-satisfied scan keys */ |
| 1475 |
if (ikey < sktrig) |
| 1476 |
continue; |
| 1477 |
|
| 1478 |
if (cur->sk_flags & (SK_BT_REQFWD | SK_BT_REQBKWD)) |
| 1479 |
{ |
| 1480 |
required = true; |
| 1481 |
|
| 1482 |
if (cur->sk_attno > tupnatts) |
| 1483 |
{ |
| 1484 |
/* Set this just like _bt_tuple_before_array_skeys */ |
| 1485 |
Assert(sktrig < ikey); |
| 1486 |
so->scanBehind = true; |
| 1487 |
} |
| 1488 |
} |
| 1489 |
|
| 1490 |
/* |
| 1491 |
* Handle a required non-array scan key that the initial call to |
| 1492 |
* _bt_check_compare indicated triggered array advancement, if any. |
| 1493 |
* |
| 1494 |
* The non-array scan key's strategy will be <, <=, or = during a |
| 1495 |
* forwards scan (or any one of =, >=, or > during a backwards scan). |
| 1496 |
* It follows that the corresponding tuple attribute's value must now |
| 1497 |
* be either > or >= the scan key value (for backwards scans it must |
| 1498 |
* be either < or <= that value). |
| 1499 |
* |
| 1500 |
* If this is a required equality strategy scan key, this is just an |
| 1501 |
* optimization; _bt_tuple_before_array_skeys already confirmed that |
| 1502 |
* this scan key places us ahead of caller's tuple. There's no need |
| 1503 |
* to repeat that work now. (The same underlying principle also gets |
| 1504 |
* applied by the cur_elem_trig optimization used to speed up searches |
| 1505 |
* for the next array element.) |
| 1506 |
* |
| 1507 |
* If this is a required inequality strategy scan key, we _must_ rely |
| 1508 |
* on _bt_check_compare like this; we aren't capable of directly |
| 1509 |
* evaluating required inequality strategy scan keys here, on our own. |
| 1510 |
*/ |
| 1511 |
if (ikey == sktrig && !array) |
| 1512 |
{ |
| 1513 |
Assert(sktrig_required && required && all_required_satisfied); |
| 1514 |
|
| 1515 |
/* Use "beyond end" advancement. See below for an explanation. */ |
| 1516 |
beyond_end_advance = true; |
| 1517 |
all_satisfied = all_required_satisfied = false; |
| 1518 |
|
| 1519 |
continue; |
| 1520 |
} |
| 1521 |
|
| 1522 |
/* |
| 1523 |
* Nothing more for us to do with an inequality strategy scan key that |
| 1524 |
* wasn't the one that _bt_check_compare stopped on, though. |
| 1525 |
* |
| 1526 |
* Note: if our later call to _bt_check_compare (to recheck caller's |
| 1527 |
* tuple) sets continuescan=false due to finding this same inequality |
| 1528 |
* unsatisfied (possible when it's required in the scan direction), |
| 1529 |
* we'll deal with it via a recursive "second pass" call. |
| 1530 |
*/ |
| 1531 |
else if (cur->sk_strategy != BTEqualStrategyNumber) |
| 1532 |
continue; |
| 1533 |
|
| 1534 |
/* |
| 1535 |
* Nothing for us to do with an equality strategy scan key that isn't |
| 1536 |
* marked required, either -- unless it's a non-required array |
| 1537 |
*/ |
| 1538 |
else if (!required && !array) |
| 1539 |
continue; |
| 1540 |
|
| 1541 |
/* |
| 1542 |
* Here we perform steps for all array scan keys after a required |
| 1543 |
* array scan key whose binary search triggered "beyond end of array |
| 1544 |
* element" array advancement due to encountering a tuple attribute |
| 1545 |
* value > the closest matching array key (or < for backwards scans). |
| 1546 |
*/ |
| 1547 |
if (beyond_end_advance) |
| 1548 |
{ |
| 1549 |
if (array) |
| 1550 |
_bt_array_set_low_or_high(rel, cur, array, |
| 1551 |
ScanDirectionIsBackward(dir)); |
| 1552 |
|
| 1553 |
continue; |
| 1554 |
} |
| 1555 |
|
| 1556 |
/* |
| 1557 |
* Here we perform steps for all array scan keys after a required |
| 1558 |
* array scan key whose tuple attribute was < the closest matching |
| 1559 |
* array key when we dealt with it (or > for backwards scans). |
| 1560 |
* |
| 1561 |
* This earlier required array key already puts us ahead of caller's |
| 1562 |
* tuple in the key space (for the current scan direction). We must |
| 1563 |
* make sure that subsequent lower-order array keys do not put us too |
| 1564 |
* far ahead (ahead of tuples that have yet to be seen by our caller). |
| 1565 |
* For example, when a tuple "(a, b) = (42, 5)" advances the array |
| 1566 |
* keys on "a" from 40 to 45, we must also set "b" to whatever the |
| 1567 |
* first array element for "b" is. It would be wrong to allow "b" to |
| 1568 |
* be set based on the tuple value. |
| 1569 |
* |
| 1570 |
* Perform the same steps with truncated high key attributes. You can |
| 1571 |
* think of this as a "binary search" for the element closest to the |
| 1572 |
* value -inf. Again, the arrays must never get ahead of the scan. |
| 1573 |
*/ |
| 1574 |
if (!all_required_satisfied || cur->sk_attno > tupnatts) |
| 1575 |
{ |
| 1576 |
if (array) |
| 1577 |
_bt_array_set_low_or_high(rel, cur, array, |
| 1578 |
ScanDirectionIsForward(dir)); |
| 1579 |
|
| 1580 |
continue; |
| 1581 |
} |
| 1582 |
|
| 1583 |
/* |
| 1584 |
* Search in scankey's array for the corresponding tuple attribute |
| 1585 |
* value from caller's tuple |
| 1586 |
*/ |
| 1587 |
tupdatum = index_getattr(tuple, cur->sk_attno, tupdesc, &tupnull); |
| 1588 |
|
| 1589 |
if (array) |
| 1590 |
{ |
| 1591 |
bool cur_elem_trig = (sktrig_required && ikey == sktrig); |
| 1592 |
|
| 1593 |
/* |
| 1594 |
* "Binary search" by checking if tupdatum/tupnull are within the |
| 1595 |
* range of the skip array |
| 1596 |
*/ |
| 1597 |
if (array->num_elems == -1) |
| 1598 |
_bt_binsrch_skiparray_skey(cur_elem_trig, dir, |
| 1599 |
tupdatum, tupnull, array, cur, |
| 1600 |
&result); |
| 1601 |
|
| 1602 |
/* |
| 1603 |
* Binary search for the closest match from the SAOP array |
| 1604 |
*/ |
| 1605 |
else |
| 1606 |
set_elem = _bt_binsrch_array_skey(&so->orderProcs[ikey], |
| 1607 |
cur_elem_trig, dir, |
| 1608 |
tupdatum, tupnull, array, cur, |
| 1609 |
&result); |
| 1610 |
} |
| 1611 |
else |
| 1612 |
{ |
| 1613 |
Assert(required); |
| 1614 |
|
| 1615 |
/* |
| 1616 |
* This is a required non-array equality strategy scan key, which |
| 1617 |
* we'll treat as a degenerate single element array. |
| 1618 |
* |
| 1619 |
* This scan key's imaginary "array" can't really advance, but it |
| 1620 |
* can still roll over like any other array. (Actually, this is |
| 1621 |
* no different to real single value arrays, which never advance |
| 1622 |
* without rolling over -- they can never truly advance, either.) |
| 1623 |
*/ |
| 1624 |
result = _bt_compare_array_skey(&so->orderProcs[ikey], |
| 1625 |
tupdatum, tupnull, |
| 1626 |
cur->sk_argument, cur); |
| 1627 |
} |
| 1628 |
|
| 1629 |
/* |
| 1630 |
* Consider "beyond end of array element" array advancement. |
| 1631 |
* |
| 1632 |
* When the tuple attribute value is > the closest matching array key |
| 1633 |
* (or < in the backwards scan case), we need to ratchet this array |
| 1634 |
* forward (backward) by one increment, so that caller's tuple ends up |
| 1635 |
* being < final array value instead (or > final array value instead). |
| 1636 |
* This process has to work for all of the arrays, not just this one: |
| 1637 |
* it must "carry" to higher-order arrays when the set_elem that we |
| 1638 |
* just found happens to be the final one for the scan's direction. |
| 1639 |
* Incrementing (decrementing) set_elem itself isn't good enough. |
| 1640 |
* |
| 1641 |
* Our approach is to provisionally use set_elem as if it was an exact |
| 1642 |
* match now, then set each later/less significant array to whatever |
| 1643 |
* its final element is. Once outside the loop we'll then "increment |
| 1644 |
* this array's set_elem" by calling _bt_advance_array_keys_increment. |
| 1645 |
* That way the process rolls over to higher order arrays as needed. |
| 1646 |
* |
| 1647 |
* Under this scheme any required arrays only ever ratchet forwards |
| 1648 |
* (or backwards), and always do so to the maximum possible extent |
| 1649 |
* that we can know will be safe without seeing the scan's next tuple. |
| 1650 |
* We don't need any special handling for required scan keys that lack |
| 1651 |
* a real array to advance, nor for redundant scan keys that couldn't |
| 1652 |
* be eliminated by _bt_preprocess_keys. It won't matter if some of |
| 1653 |
* our "true" array scan keys (or even all of them) are non-required. |
| 1654 |
*/ |
| 1655 |
if (sktrig_required && required && |
| 1656 |
((ScanDirectionIsForward(dir) && result > 0) || |
| 1657 |
(ScanDirectionIsBackward(dir) && result < 0))) |
| 1658 |
beyond_end_advance = true; |
| 1659 |
|
| 1660 |
Assert(all_required_satisfied && all_satisfied); |
| 1661 |
if (result != 0) |
| 1662 |
{ |
| 1663 |
/* |
| 1664 |
* Track whether caller's tuple satisfies our new post-advancement |
| 1665 |
* qual, for required scan keys, as well as for the entire set of |
| 1666 |
* interesting scan keys (all required scan keys plus non-required |
| 1667 |
* array scan keys are considered interesting.) |
| 1668 |
*/ |
| 1669 |
all_satisfied = false; |
| 1670 |
if (sktrig_required && required) |
| 1671 |
all_required_satisfied = false; |
| 1672 |
else |
| 1673 |
{ |
| 1674 |
/* |
| 1675 |
* There's no need to advance the arrays using the best |
| 1676 |
* available match for a non-required array. Give up now. |
| 1677 |
* (Though note that sktrig_required calls still have to do |
| 1678 |
* all the usual post-advancement steps, including the recheck |
| 1679 |
* call to _bt_check_compare.) |
| 1680 |
*/ |
| 1681 |
break; |
| 1682 |
} |
| 1683 |
} |
| 1684 |
|
| 1685 |
/* Advance array keys, even when we don't have an exact match */ |
| 1686 |
if (array) |
| 1687 |
{ |
| 1688 |
if (array->num_elems == -1) |
| 1689 |
{ |
| 1690 |
/* Skip array's new element is tupdatum (or MINVAL/MAXVAL) */ |
| 1691 |
_bt_skiparray_set_element(rel, cur, array, result, |
| 1692 |
tupdatum, tupnull); |
| 1693 |
skip_array_advanced = true; |
| 1694 |
} |
| 1695 |
else if (array->cur_elem != set_elem) |
| 1696 |
{ |
| 1697 |
/* SAOP array's new element is set_elem datum */ |
| 1698 |
array->cur_elem = set_elem; |
| 1699 |
cur->sk_argument = array->elem_values[set_elem]; |
| 1700 |
} |
| 1701 |
} |
| 1702 |
} |
| 1703 |
|
| 1704 |
/* |
| 1705 |
* Advance the array keys incrementally whenever "beyond end of array |
| 1706 |
* element" array advancement happens, so that advancement will carry to |
| 1707 |
* higher-order arrays (might exhaust all the scan's arrays instead, which |
| 1708 |
* ends the top-level scan). |
| 1709 |
*/ |
| 1710 |
if (beyond_end_advance && |
| 1711 |
!_bt_advance_array_keys_increment(scan, dir, &skip_array_advanced)) |
| 1712 |
goto end_toplevel_scan; |
| 1713 |
|
| 1714 |
Assert(_bt_verify_keys_with_arraykeys(scan)); |
| 1715 |
|
| 1716 |
/* |
| 1717 |
* Maintain a page-level count of the number of times the scan's array |
| 1718 |
* keys advanced in a way that affected at least one skip array |
| 1719 |
*/ |
| 1720 |
if (sktrig_required && skip_array_advanced) |
| 1721 |
pstate->nskipadvances++; |
| 1722 |
|
| 1723 |
/* |
| 1724 |
* Does tuple now satisfy our new qual? Recheck with _bt_check_compare. |
| 1725 |
* |
| 1726 |
* Calls triggered by an unsatisfied required scan key, whose tuple now |
| 1727 |
* satisfies all required scan keys, but not all nonrequired array keys, |
| 1728 |
* will still require a recheck call to _bt_check_compare. They'll still |
| 1729 |
* need its "second pass" handling of required inequality scan keys. |
| 1730 |
* (Might have missed a still-unsatisfied required inequality scan key |
| 1731 |
* that caller didn't detect as the sktrig scan key during its initial |
| 1732 |
* _bt_check_compare call that used the old/original qual.) |
| 1733 |
* |
| 1734 |
* Calls triggered by an unsatisfied nonrequired array scan key never need |
| 1735 |
* "second pass" handling of required inequalities (nor any other handling |
| 1736 |
* of any required scan key). All that matters is whether caller's tuple |
| 1737 |
* satisfies the new qual, so it's safe to just skip the _bt_check_compare |
| 1738 |
* recheck when we've already determined that it can only return 'false'. |
| 1739 |
* |
| 1740 |
* Note: In practice most scan keys are marked required by preprocessing, |
| 1741 |
* if necessary by generating a preceding skip array. We nevertheless |
| 1742 |
* often handle array keys marked required as if they were nonrequired. |
| 1743 |
* This behavior is requested by our _bt_check_compare caller, though only |
| 1744 |
* when it is passed "forcenonrequired=true" by _bt_checkkeys. |
| 1745 |
*/ |
| 1746 |
if ((sktrig_required && all_required_satisfied) || |
| 1747 |
(!sktrig_required && all_satisfied)) |
| 1748 |
{ |
| 1749 |
int nsktrig = sktrig + 1; |
| 1750 |
bool continuescan; |
| 1751 |
|
| 1752 |
Assert(all_required_satisfied); |
| 1753 |
|
| 1754 |
/* Recheck _bt_check_compare on behalf of caller */ |
| 1755 |
if (_bt_check_compare(scan, dir, tuple, tupnatts, tupdesc, false, |
| 1756 |
!sktrig_required, &continuescan, |
| 1757 |
&nsktrig) && |
| 1758 |
!so->scanBehind) |
| 1759 |
{ |
| 1760 |
/* This tuple satisfies the new qual */ |
| 1761 |
Assert(all_satisfied && continuescan); |
| 1762 |
|
| 1763 |
if (pstate) |
| 1764 |
pstate->continuescan = true; |
| 1765 |
|
| 1766 |
return true; |
| 1767 |
} |
| 1768 |
|
| 1769 |
/* |
| 1770 |
* Consider "second pass" handling of required inequalities. |
| 1771 |
* |
| 1772 |
* It's possible that our _bt_check_compare call indicated that the |
| 1773 |
* scan should end due to some unsatisfied inequality that wasn't |
| 1774 |
* initially recognized as such by us. Handle this by calling |
| 1775 |
* ourselves recursively, this time indicating that the trigger is the |
| 1776 |
* inequality that we missed first time around (and using a set of |
| 1777 |
* required array/equality keys that are now exact matches for tuple). |
| 1778 |
* |
| 1779 |
* We make a strong, general guarantee that every _bt_checkkeys call |
| 1780 |
* here will advance the array keys to the maximum possible extent |
| 1781 |
* that we can know to be safe based on caller's tuple alone. If we |
| 1782 |
* didn't perform this step, then that guarantee wouldn't quite hold. |
| 1783 |
*/ |
| 1784 |
if (unlikely(!continuescan)) |
| 1785 |
{ |
| 1786 |
bool satisfied PG_USED_FOR_ASSERTS_ONLY; |
| 1787 |
|
| 1788 |
Assert(sktrig_required); |
| 1789 |
Assert(so->keyData[nsktrig].sk_strategy != BTEqualStrategyNumber); |
| 1790 |
|
| 1791 |
/* |
| 1792 |
* The tuple must use "beyond end" advancement during the |
| 1793 |
* recursive call, so we cannot possibly end up back here when |
| 1794 |
* recursing. We'll consume a small, fixed amount of stack space. |
| 1795 |
*/ |
| 1796 |
Assert(!beyond_end_advance); |
| 1797 |
|
| 1798 |
/* Advance the array keys a second time using same tuple */ |
| 1799 |
satisfied = _bt_advance_array_keys(scan, pstate, tuple, tupnatts, |
| 1800 |
tupdesc, nsktrig, true); |
| 1801 |
|
| 1802 |
/* This tuple doesn't satisfy the inequality */ |
| 1803 |
Assert(!satisfied); |
| 1804 |
return false; |
| 1805 |
} |
| 1806 |
|
| 1807 |
/* |
| 1808 |
* Some non-required scan key (from new qual) still not satisfied. |
| 1809 |
* |
| 1810 |
* All scan keys required in the current scan direction must still be |
| 1811 |
* satisfied, though, so we can trust all_required_satisfied below. |
| 1812 |
*/ |
| 1813 |
} |
| 1814 |
|
| 1815 |
/* |
| 1816 |
* When we were called just to deal with "advancing" non-required arrays, |
| 1817 |
* this is as far as we can go (cannot stop the scan for these callers) |
| 1818 |
*/ |
| 1819 |
if (!sktrig_required) |
| 1820 |
{ |
| 1821 |
/* Caller's tuple doesn't match any qual */ |
| 1822 |
return false; |
| 1823 |
} |
| 1824 |
|
| 1825 |
/* |
| 1826 |
* Postcondition array state assertion (for still-unsatisfied tuples). |
| 1827 |
* |
| 1828 |
* By here we have established that the scan's required arrays (scan must |
| 1829 |
* have at least one required array) advanced, without becoming exhausted. |
| 1830 |
* |
| 1831 |
* Caller's tuple is now < the newly advanced array keys (or > when this |
| 1832 |
* is a backwards scan), except in the case where we only got this far due |
| 1833 |
* to an unsatisfied non-required scan key. Verify that with an assert. |
| 1834 |
* |
| 1835 |
* Note: we don't just quit at this point when all required scan keys were |
| 1836 |
* found to be satisfied because we need to consider edge-cases involving |
| 1837 |
* scan keys required in the opposite direction only; those aren't tracked |
| 1838 |
* by all_required_satisfied. |
| 1839 |
*/ |
| 1840 |
Assert(_bt_tuple_before_array_skeys(scan, dir, tuple, tupdesc, tupnatts, |
| 1841 |
false, 0, NULL) == |
| 1842 |
!all_required_satisfied); |
| 1843 |
|
| 1844 |
/* |
| 1845 |
* We generally permit primitive index scans to continue onto the next |
| 1846 |
* sibling page when the page's finaltup satisfies all required scan keys |
| 1847 |
* at the point where we're between pages. |
| 1848 |
* |
| 1849 |
* If caller's tuple is also the page's finaltup, and we see that required |
| 1850 |
* scan keys still aren't satisfied, start a new primitive index scan. |
| 1851 |
*/ |
| 1852 |
if (!all_required_satisfied && pstate->finaltup == tuple) |
| 1853 |
goto new_prim_scan; |
| 1854 |
|
| 1855 |
/* |
| 1856 |
* Proactively check finaltup (don't wait until finaltup is reached by the |
| 1857 |
* scan) when it might well turn out to not be satisfied later on. |
| 1858 |
* |
| 1859 |
* Note: if so->scanBehind hasn't already been set for finaltup by us, |
| 1860 |
* it'll be set during this call to _bt_tuple_before_array_skeys. Either |
| 1861 |
* way, it'll be set correctly (for the whole page) after this point. |
| 1862 |
*/ |
| 1863 |
if (!all_required_satisfied && pstate->finaltup && |
| 1864 |
_bt_tuple_before_array_skeys(scan, dir, pstate->finaltup, tupdesc, |
| 1865 |
BTreeTupleGetNAtts(pstate->finaltup, rel), |
| 1866 |
false, 0, &so->scanBehind)) |
| 1867 |
goto new_prim_scan; |
| 1868 |
|
| 1869 |
/* |
| 1870 |
* When we encounter a truncated finaltup high key attribute, we're |
| 1871 |
* optimistic about the chances of its corresponding required scan key |
| 1872 |
* being satisfied when we go on to recheck it against tuples from this |
| 1873 |
* page's right sibling leaf page. We consider truncated attributes to be |
| 1874 |
* satisfied by required scan keys, which allows the primitive index scan |
| 1875 |
* to continue to the next leaf page. We must set so->scanBehind to true |
| 1876 |
* to remember that the last page's finaltup had "satisfied" required scan |
| 1877 |
* keys for one or more truncated attribute values (scan keys required in |
| 1878 |
* _either_ scan direction). |
| 1879 |
* |
| 1880 |
* There is a chance that _bt_readpage (which checks so->scanBehind) will |
| 1881 |
* find that even the sibling leaf page's finaltup is < the new array |
| 1882 |
* keys. When that happens, our optimistic policy will have incurred a |
| 1883 |
* single extra leaf page access that could have been avoided. |
| 1884 |
* |
| 1885 |
* A pessimistic policy would give backward scans a gratuitous advantage |
| 1886 |
* over forward scans. We'd punish forward scans for applying more |
| 1887 |
* accurate information from the high key, rather than just using the |
| 1888 |
* final non-pivot tuple as finaltup, in the style of backward scans. |
| 1889 |
* Being pessimistic would also give some scans with non-required arrays a |
| 1890 |
* perverse advantage over similar scans that use required arrays instead. |
| 1891 |
* |
| 1892 |
* This is similar to our scan-level heuristics, below. They also set |
| 1893 |
* scanBehind to speculatively continue the primscan onto the next page. |
| 1894 |
*/ |
| 1895 |
if (so->scanBehind) |
| 1896 |
{ |
| 1897 |
/* Truncated high key -- _bt_scanbehind_checkkeys recheck scheduled */ |
| 1898 |
} |
| 1899 |
|
| 1900 |
/* |
| 1901 |
* Handle inequalities marked required in the opposite scan direction. |
| 1902 |
* They can also signal that we should start a new primitive index scan. |
| 1903 |
* |
| 1904 |
* It's possible that the scan is now positioned where "matching" tuples |
| 1905 |
* begin, and that caller's tuple satisfies all scan keys required in the |
| 1906 |
* current scan direction. But if caller's tuple still doesn't satisfy |
| 1907 |
* other scan keys that are required in the opposite scan direction only |
| 1908 |
* (e.g., a required >= strategy scan key when scan direction is forward), |
| 1909 |
* it's still possible that there are many leaf pages before the page that |
| 1910 |
* _bt_first could skip straight to. Groveling through all those pages |
| 1911 |
* will always give correct answers, but it can be very inefficient. We |
| 1912 |
* must avoid needlessly scanning extra pages. |
| 1913 |
* |
| 1914 |
* Separately, it's possible that _bt_check_compare set continuescan=false |
| 1915 |
* for a scan key that's required in the opposite direction only. This is |
| 1916 |
* a special case, that happens only when _bt_check_compare sees that the |
| 1917 |
* inequality encountered a NULL value. This signals the end of non-NULL |
| 1918 |
* values in the current scan direction, which is reason enough to end the |
| 1919 |
* (primitive) scan. If this happens at the start of a large group of |
| 1920 |
* NULL values, then we shouldn't expect to be called again until after |
| 1921 |
* the scan has already read indefinitely-many leaf pages full of tuples |
| 1922 |
* with NULL suffix values. (_bt_first is expected to skip over the group |
| 1923 |
* of NULLs by applying a similar "deduce NOT NULL" rule of its own, which |
| 1924 |
* involves consing up an explicit SK_SEARCHNOTNULL key.) |
| 1925 |
* |
| 1926 |
* Apply a test against finaltup to detect and recover from the problem: |
| 1927 |
* if even finaltup doesn't satisfy such an inequality, we just skip by |
| 1928 |
* starting a new primitive index scan. When we skip, we know for sure |
| 1929 |
* that all of the tuples on the current page following caller's tuple are |
| 1930 |
* also before the _bt_first-wise start of tuples for our new qual. That |
| 1931 |
* at least suggests many more skippable pages beyond the current page. |
| 1932 |
* (when so->scanBehind and so->oppositeDirCheck are set, this'll happen |
| 1933 |
* when we test the next page's finaltup/high key instead.) |
| 1934 |
*/ |
| 1935 |
else if (has_required_opposite_direction_only && pstate->finaltup && |
| 1936 |
unlikely(!_bt_oppodir_checkkeys(scan, dir, pstate->finaltup))) |
| 1937 |
goto new_prim_scan; |
| 1938 |
|
| 1939 |
continue_scan: |
| 1940 |
|
| 1941 |
/* |
| 1942 |
* Stick with the ongoing primitive index scan for now. |
| 1943 |
* |
| 1944 |
* It's possible that later tuples will also turn out to have values that |
| 1945 |
* are still < the now-current array keys (or > the current array keys). |
| 1946 |
* Our caller will handle this by performing what amounts to a linear |
| 1947 |
* search of the page, implemented by calling _bt_check_compare and then |
| 1948 |
* _bt_tuple_before_array_skeys for each tuple. |
| 1949 |
* |
| 1950 |
* This approach has various advantages over a binary search of the page. |
| 1951 |
* Repeated binary searches of the page (one binary search for every array |
| 1952 |
* advancement) won't outperform a continuous linear search. While there |
| 1953 |
* are workloads that a naive linear search won't handle well, our caller |
| 1954 |
* has a "look ahead" fallback mechanism to deal with that problem. |
| 1955 |
*/ |
| 1956 |
pstate->continuescan = true; /* Override _bt_check_compare */ |
| 1957 |
so->needPrimScan = false; /* _bt_readpage has more tuples to check */ |
| 1958 |
|
| 1959 |
if (so->scanBehind) |
| 1960 |
{ |
| 1961 |
/* |
| 1962 |
* Remember if recheck needs to call _bt_oppodir_checkkeys for next |
| 1963 |
* page's finaltup (see above comments about "Handle inequalities |
| 1964 |
* marked required in the opposite scan direction" for why). |
| 1965 |
*/ |
| 1966 |
so->oppositeDirCheck = has_required_opposite_direction_only; |
| 1967 |
|
| 1968 |
/* |
| 1969 |
* skip by setting "look ahead" mechanism's offnum for forwards scans |
| 1970 |
* (backwards scans check scanBehind flag directly instead) |
| 1971 |
*/ |
| 1972 |
if (ScanDirectionIsForward(dir)) |
| 1973 |
pstate->skip = pstate->maxoff + 1; |
| 1974 |
} |
| 1975 |
|
| 1976 |
/* Caller's tuple doesn't match the new qual */ |
| 1977 |
return false; |
| 1978 |
|
| 1979 |
new_prim_scan: |
| 1980 |
|
| 1981 |
Assert(pstate->finaltup); /* not on rightmost/leftmost page */ |
| 1982 |
|
| 1983 |
/* |
| 1984 |
* Looks like another primitive index scan is required. But consider |
| 1985 |
* continuing the current primscan based on scan-level heuristics. |
| 1986 |
* |
| 1987 |
* Continue the ongoing primitive scan (and schedule a recheck for when |
| 1988 |
* the scan arrives on the next sibling leaf page) when it has already |
| 1989 |
* read at least one leaf page before the one we're reading now. This |
| 1990 |
* makes primscan scheduling more efficient when scanning subsets of an |
| 1991 |
* index with many distinct attribute values matching many array elements. |
| 1992 |
* It encourages fewer, larger primitive scans where that makes sense. |
| 1993 |
* This will in turn encourage _bt_readpage to apply the pstate.startikey |
| 1994 |
* optimization more often. |
| 1995 |
* |
| 1996 |
* Also continue the ongoing primitive index scan when it is still on the |
| 1997 |
* first page if there have been more than NSKIPADVANCES_THRESHOLD calls |
| 1998 |
* here that each advanced at least one of the scan's skip arrays |
| 1999 |
* (deliberately ignore advancements that only affected SAOP arrays here). |
| 2000 |
* A page that cycles through this many skip array elements is quite |
| 2001 |
* likely to neighbor similar pages, that we'll also need to read. |
| 2002 |
* |
| 2003 |
* Note: These heuristics aren't as aggressive as you might think. We're |
| 2004 |
* conservative about allowing a primitive scan to step from the first |
| 2005 |
* leaf page it reads to the page's sibling page (we only allow it on |
| 2006 |
* first pages whose finaltup strongly suggests that it'll work out, as |
| 2007 |
* well as first pages that have a large number of skip array advances). |
| 2008 |
* Clearing this first page finaltup hurdle is a strong signal in itself. |
| 2009 |
* |
| 2010 |
* Note: The NSKIPADVANCES_THRESHOLD heuristic exists only to avoid |
| 2011 |
* pathological cases. Specifically, cases where a skip scan should just |
| 2012 |
* behave like a traditional full index scan, but ends up "skipping" again |
| 2013 |
* and again, descending to the prior leaf page's direct sibling leaf page |
| 2014 |
* each time. This misbehavior would otherwise be possible during scans |
| 2015 |
* that never quite manage to "clear the first page finaltup hurdle". |
| 2016 |
*/ |
| 2017 |
if (!pstate->firstpage || pstate->nskipadvances > NSKIPADVANCES_THRESHOLD) |
| 2018 |
{ |
| 2019 |
/* Schedule a recheck once on the next (or previous) page */ |
| 2020 |
so->scanBehind = true; |
| 2021 |
|
| 2022 |
/* Continue the current primitive scan after all */ |
| 2023 |
goto continue_scan; |
| 2024 |
} |
| 2025 |
|
| 2026 |
/* |
| 2027 |
* End this primitive index scan, but schedule another. |
| 2028 |
* |
| 2029 |
* Note: We make a soft assumption that the current scan direction will |
| 2030 |
* also be used within _bt_next, when it is asked to step off this page. |
| 2031 |
* It is up to _bt_next to cancel this scheduled primitive index scan |
| 2032 |
* whenever it steps to a page in the direction opposite currPos.dir. |
| 2033 |
*/ |
| 2034 |
pstate->continuescan = false; /* Tell _bt_readpage we're done... */ |
| 2035 |
so->needPrimScan = true; /* ...but call _bt_first again */ |
| 2036 |
|
| 2037 |
if (scan->parallel_scan) |
| 2038 |
_bt_parallel_primscan_schedule(scan, so->currPos.currPage); |
| 2039 |
|
| 2040 |
/* Caller's tuple doesn't match the new qual */ |
| 2041 |
return false; |
| 2042 |
|
| 2043 |
end_toplevel_scan: |
| 2044 |
|
| 2045 |
/* |
| 2046 |
* End the current primitive index scan, but don't schedule another. |
| 2047 |
* |
| 2048 |
* This ends the entire top-level scan in the current scan direction. |
| 2049 |
* |
| 2050 |
* Note: The scan's arrays (including any non-required arrays) are now in |
| 2051 |
* their final positions for the current scan direction. If the scan |
| 2052 |
* direction happens to change, then the arrays will already be in their |
| 2053 |
* first positions for what will then be the current scan direction. |
| 2054 |
*/ |
| 2055 |
pstate->continuescan = false; /* Tell _bt_readpage we're done... */ |
| 2056 |
so->needPrimScan = false; /* ...and don't call _bt_first again */ |
| 2057 |
|
| 2058 |
/* Caller's tuple doesn't match any qual */ |
| 2059 |
return false; |
| 2060 |
} |
| 2061 |
|
| 2062 |
#ifdef USE_ASSERT_CHECKING |
| 2063 |
/* |
| 2064 |
* Verify that the scan's "so->keyData[]" scan keys are in agreement with |
| 2065 |
* its array key state |
| 2066 |
*/ |
| 2067 |
static bool |
| 2068 |
_bt_verify_keys_with_arraykeys(IndexScanDesc scan) |
| 2069 |
{ |
| 2070 |
BTScanOpaque so = (BTScanOpaque) scan->opaque; |
| 2071 |
int last_sk_attno = InvalidAttrNumber, |
| 2072 |
arrayidx = 0; |
| 2073 |
bool nonrequiredseen = false; |
| 2074 |
|
| 2075 |
if (!so->qual_ok) |
| 2076 |
return false; |
| 2077 |
|
| 2078 |
for (int ikey = 0; ikey < so->numberOfKeys; ikey++) |
| 2079 |
{ |
| 2080 |
ScanKey cur = so->keyData + ikey; |
| 2081 |
BTArrayKeyInfo *array; |
| 2082 |
|
| 2083 |
if (cur->sk_strategy != BTEqualStrategyNumber || |
| 2084 |
!(cur->sk_flags & SK_SEARCHARRAY)) |
| 2085 |
continue; |
| 2086 |
|
| 2087 |
array = &so->arrayKeys[arrayidx++]; |
| 2088 |
if (array->scan_key != ikey) |
| 2089 |
return false; |
| 2090 |
|
| 2091 |
if (array->num_elems == 0 || array->num_elems < -1) |
| 2092 |
return false; |
| 2093 |
|
| 2094 |
if (array->num_elems != -1 && |
| 2095 |
cur->sk_argument != array->elem_values[array->cur_elem]) |
| 2096 |
return false; |
| 2097 |
if (cur->sk_flags & (SK_BT_REQFWD | SK_BT_REQBKWD)) |
| 2098 |
{ |
| 2099 |
if (last_sk_attno > cur->sk_attno) |
| 2100 |
return false; |
| 2101 |
if (nonrequiredseen) |
| 2102 |
return false; |
| 2103 |
} |
| 2104 |
else |
| 2105 |
nonrequiredseen = true; |
| 2106 |
|
| 2107 |
last_sk_attno = cur->sk_attno; |
| 2108 |
} |
| 2109 |
|
| 2110 |
if (arrayidx != so->numArrayKeys) |
| 2111 |
return false; |
| 2112 |
|
| 2113 |
return true; |
| 2114 |
} |
| 2115 |
#endif |
| 2116 |
|
| 2117 |
/* |
| 2118 |
* Test whether an indextuple satisfies all the scankey conditions. |
| 2119 |
* |
| 2120 |
* Return true if so, false if not. If the tuple fails to pass the qual, |
| 2121 |
* we also determine whether there's any need to continue the scan beyond |
| 2122 |
* this tuple, and set pstate.continuescan accordingly. See comments for |
| 2123 |
* _bt_preprocess_keys() about how this is done. |
| 2124 |
* |
| 2125 |
* Forward scan callers can pass a high key tuple in the hopes of having |
| 2126 |
* us set *continuescan to false, and avoiding an unnecessary visit to |
| 2127 |
* the page to the right. |
| 2128 |
* |
| 2129 |
* Advances the scan's array keys when necessary for arrayKeys=true callers. |
| 2130 |
* Scans without any array keys must always pass arrayKeys=false. |
| 2131 |
* |
| 2132 |
* Also stops and starts primitive index scans for arrayKeys=true callers. |
| 2133 |
* Scans with array keys are required to set up page state that helps us with |
| 2134 |
* this. The page's finaltup tuple (the page high key for a forward scan, or |
| 2135 |
* the page's first non-pivot tuple for a backward scan) must be set in |
| 2136 |
* pstate.finaltup ahead of the first call here for the page. Set this to |
| 2137 |
* NULL for rightmost page (or the leftmost page for backwards scans). |
| 2138 |
* |
| 2139 |
* scan: index scan descriptor (containing a search-type scankey) |
| 2140 |
* pstate: page level input and output parameters |
| 2141 |
* arrayKeys: should we advance the scan's array keys if necessary? |
| 2142 |
* tuple: index tuple to test |
| 2143 |
* tupnatts: number of attributes in tupnatts (high key may be truncated) |
| 2144 |
*/ |
| 2145 |
bool |
| 2146 |
_bt_checkkeys(IndexScanDesc scan, BTReadPageState *pstate, bool arrayKeys, |
| 2147 |
IndexTuple tuple, int tupnatts) |
| 2148 |
{ |
| 2149 |
TupleDesc tupdesc = RelationGetDescr(scan->indexRelation); |
| 2150 |
BTScanOpaque so = (BTScanOpaque) scan->opaque; |
| 2151 |
ScanDirection dir = so->currPos.dir; |
| 2152 |
int ikey = pstate->startikey; |
| 2153 |
bool res; |
| 2154 |
|
| 2155 |
Assert(BTreeTupleGetNAtts(tuple, scan->indexRelation) == tupnatts); |
| 2156 |
Assert(!so->needPrimScan && !so->scanBehind && !so->oppositeDirCheck); |
| 2157 |
Assert(arrayKeys || so->numArrayKeys == 0); |
| 2158 |
|
| 2159 |
res = _bt_check_compare(scan, dir, tuple, tupnatts, tupdesc, arrayKeys, |
| 2160 |
pstate->forcenonrequired, &pstate->continuescan, |
| 2161 |
&ikey); |
| 2162 |
|
| 2163 |
/* |
| 2164 |
* If _bt_check_compare relied on the pstate.startikey optimization, call |
| 2165 |
* again (in assert-enabled builds) to verify it didn't affect our answer. |
| 2166 |
* |
| 2167 |
* Note: we can't do this when !pstate.forcenonrequired, since any arrays |
| 2168 |
* before pstate.startikey won't have advanced on this page at all. |
| 2169 |
*/ |
| 2170 |
Assert(!pstate->forcenonrequired || arrayKeys); |
| 2171 |
#ifdef USE_ASSERT_CHECKING |
| 2172 |
if (pstate->startikey > 0 && !pstate->forcenonrequired) |
| 2173 |
{ |
| 2174 |
bool dres, |
| 2175 |
dcontinuescan; |
| 2176 |
int dikey = 0; |
| 2177 |
|
| 2178 |
/* Pass arrayKeys=false to avoid array side-effects */ |
| 2179 |
dres = _bt_check_compare(scan, dir, tuple, tupnatts, tupdesc, false, |
| 2180 |
pstate->forcenonrequired, &dcontinuescan, |
| 2181 |
&dikey); |
| 2182 |
Assert(res == dres); |
| 2183 |
Assert(pstate->continuescan == dcontinuescan); |
| 2184 |
|
| 2185 |
/* |
| 2186 |
* Should also get the same ikey result. We need a slightly weaker |
| 2187 |
* assertion during arrayKeys calls, since they might be using an |
| 2188 |
* array that couldn't be marked required during preprocessing. |
| 2189 |
*/ |
| 2190 |
Assert(arrayKeys || ikey == dikey); |
| 2191 |
Assert(ikey <= dikey); |
| 2192 |
} |
| 2193 |
#endif |
| 2194 |
|
| 2195 |
/* |
| 2196 |
* Only one _bt_check_compare call is required in the common case where |
| 2197 |
* there are no equality strategy array scan keys. Otherwise we can only |
| 2198 |
* accept _bt_check_compare's answer unreservedly when it didn't set |
| 2199 |
* pstate.continuescan=false. |
| 2200 |
*/ |
| 2201 |
if (!arrayKeys || pstate->continuescan) |
| 2202 |
return res; |
| 2203 |
|
| 2204 |
/* |
| 2205 |
* _bt_check_compare call set continuescan=false in the presence of |
| 2206 |
* equality type array keys. This could mean that the tuple is just past |
| 2207 |
* the end of matches for the current array keys. |
| 2208 |
* |
| 2209 |
* It's also possible that the scan is still _before_ the _start_ of |
| 2210 |
* tuples matching the current set of array keys. Check for that first. |
| 2211 |
*/ |
| 2212 |
Assert(!pstate->forcenonrequired); |
| 2213 |
if (_bt_tuple_before_array_skeys(scan, dir, tuple, tupdesc, tupnatts, true, |
| 2214 |
ikey, NULL)) |
| 2215 |
{ |
| 2216 |
/* Override _bt_check_compare, continue primitive scan */ |
| 2217 |
pstate->continuescan = true; |
| 2218 |
|
| 2219 |
/* |
| 2220 |
* We will end up here repeatedly given a group of tuples > the |
| 2221 |
* previous array keys and < the now-current keys (for a backwards |
| 2222 |
* scan it's just the same, though the operators swap positions). |
| 2223 |
* |
| 2224 |
* We must avoid allowing this linear search process to scan very many |
| 2225 |
* tuples from well before the start of tuples matching the current |
| 2226 |
* array keys (or from well before the point where we'll once again |
| 2227 |
* have to advance the scan's array keys). |
| 2228 |
* |
| 2229 |
* We keep the overhead under control by speculatively "looking ahead" |
| 2230 |
* to later still-unscanned items from this same leaf page. We'll |
| 2231 |
* only attempt this once the number of tuples that the linear search |
| 2232 |
* process has examined starts to get out of hand. |
| 2233 |
*/ |
| 2234 |
pstate->rechecks++; |
| 2235 |
if (pstate->rechecks >= LOOK_AHEAD_REQUIRED_RECHECKS) |
| 2236 |
{ |
| 2237 |
/* See if we should skip ahead within the current leaf page */ |
| 2238 |
_bt_checkkeys_look_ahead(scan, pstate, tupnatts, tupdesc); |
| 2239 |
|
| 2240 |
/* |
| 2241 |
* Might have set pstate.skip to a later page offset. When that |
| 2242 |
* happens then _bt_readpage caller will inexpensively skip ahead |
| 2243 |
* to a later tuple from the same page (the one just after the |
| 2244 |
* tuple we successfully "looked ahead" to). |
| 2245 |
*/ |
| 2246 |
} |
| 2247 |
|
| 2248 |
/* This indextuple doesn't match the current qual, in any case */ |
| 2249 |
return false; |
| 2250 |
} |
| 2251 |
|
| 2252 |
/* |
| 2253 |
* Caller's tuple is >= the current set of array keys and other equality |
| 2254 |
* constraint scan keys (or <= if this is a backwards scan). It's now |
| 2255 |
* clear that we _must_ advance any required array keys in lockstep with |
| 2256 |
* the scan. |
| 2257 |
*/ |
| 2258 |
return _bt_advance_array_keys(scan, pstate, tuple, tupnatts, tupdesc, |
| 2259 |
ikey, true); |
| 2260 |
} |
| 2261 |
|
| 2262 |
/* |
| 2263 |
* Test whether caller's finaltup tuple is still before the start of matches |
| 2264 |
* for the current array keys. |
| 2265 |
* |
| 2266 |
* Called at the start of reading a page during a scan with array keys, though |
| 2267 |
* only when the so->scanBehind flag was set on the scan's prior page. |
| 2268 |
* |
| 2269 |
* Returns false if the tuple is still before the start of matches. When that |
| 2270 |
* happens, caller should cut its losses and start a new primitive index scan. |
| 2271 |
* Otherwise returns true. |
| 2272 |
*/ |
| 2273 |
bool |
| 2274 |
_bt_scanbehind_checkkeys(IndexScanDesc scan, ScanDirection dir, |
| 2275 |
IndexTuple finaltup) |
| 2276 |
{ |
| 2277 |
Relation rel = scan->indexRelation; |
| 2278 |
TupleDesc tupdesc = RelationGetDescr(rel); |
| 2279 |
BTScanOpaque so = (BTScanOpaque) scan->opaque; |
| 2280 |
int nfinaltupatts = BTreeTupleGetNAtts(finaltup, rel); |
| 2281 |
bool scanBehind; |
| 2282 |
|
| 2283 |
Assert(so->numArrayKeys); |
| 2284 |
|
| 2285 |
if (_bt_tuple_before_array_skeys(scan, dir, finaltup, tupdesc, |
| 2286 |
nfinaltupatts, false, 0, &scanBehind)) |
| 2287 |
return false; |
| 2288 |
|
| 2289 |
/* |
| 2290 |
* If scanBehind was set, all of the untruncated attribute values from |
| 2291 |
* finaltup that correspond to an array match the array's current element, |
| 2292 |
* but there are other keys associated with truncated suffix attributes. |
| 2293 |
* Array advancement must have incremented the scan's arrays on the |
| 2294 |
* previous page, resulting in a set of array keys that happen to be an |
| 2295 |
* exact match for the current page high key's untruncated prefix values. |
| 2296 |
* |
| 2297 |
* This page definitely doesn't contain tuples that the scan will need to |
| 2298 |
* return. The next page may or may not contain relevant tuples. Handle |
| 2299 |
* this by cutting our losses and starting a new primscan. |
| 2300 |
*/ |
| 2301 |
if (scanBehind) |
| 2302 |
return false; |
| 2303 |
|
| 2304 |
if (!so->oppositeDirCheck) |
| 2305 |
return true; |
| 2306 |
|
| 2307 |
return _bt_oppodir_checkkeys(scan, dir, finaltup); |
| 2308 |
} |
| 2309 |
|
| 2310 |
/* |
| 2311 |
* Test whether an indextuple fails to satisfy an inequality required in the |
| 2312 |
* opposite direction only. |
| 2313 |
* |
| 2314 |
* Caller's finaltup tuple is the page high key (for forwards scans), or the |
| 2315 |
* first non-pivot tuple (for backwards scans). Called during scans with |
| 2316 |
* required array keys and required opposite-direction inequalities. |
| 2317 |
* |
| 2318 |
* Returns false if an inequality scan key required in the opposite direction |
| 2319 |
* only isn't satisfied (and any earlier required scan keys are satisfied). |
| 2320 |
* Otherwise returns true. |
| 2321 |
* |
| 2322 |
* An unsatisfied inequality required in the opposite direction only might |
| 2323 |
* well enable skipping over many leaf pages, provided another _bt_first call |
| 2324 |
* takes place. This type of unsatisfied inequality won't usually cause |
| 2325 |
* _bt_checkkeys to stop the scan to consider array advancement/starting a new |
| 2326 |
* primitive index scan. |
| 2327 |
*/ |
| 2328 |
static bool |
| 2329 |
_bt_oppodir_checkkeys(IndexScanDesc scan, ScanDirection dir, |
| 2330 |
IndexTuple finaltup) |
| 2331 |
{ |
| 2332 |
Relation rel = scan->indexRelation; |
| 2333 |
TupleDesc tupdesc = RelationGetDescr(rel); |
| 2334 |
BTScanOpaque so = (BTScanOpaque) scan->opaque; |
| 2335 |
int nfinaltupatts = BTreeTupleGetNAtts(finaltup, rel); |
| 2336 |
bool continuescan; |
| 2337 |
ScanDirection flipped = -dir; |
| 2338 |
int ikey = 0; |
| 2339 |
|
| 2340 |
Assert(so->numArrayKeys); |
| 2341 |
|
| 2342 |
_bt_check_compare(scan, flipped, finaltup, nfinaltupatts, tupdesc, false, |
| 2343 |
false, &continuescan, |
| 2344 |
&ikey); |
| 2345 |
|
| 2346 |
if (!continuescan && so->keyData[ikey].sk_strategy != BTEqualStrategyNumber) |
| 2347 |
return false; |
| 2348 |
|
| 2349 |
return true; |
| 2350 |
} |
| 2351 |
|
| 2352 |
/* |
| 2353 |
* Determines an offset to the first scan key (an so->keyData[]-wise offset) |
| 2354 |
* that is _not_ guaranteed to be satisfied by every tuple from pstate.page, |
| 2355 |
* which is set in pstate.startikey for _bt_checkkeys calls for the page. |
| 2356 |
* This allows caller to save cycles on comparisons of a prefix of keys while |
| 2357 |
* reading pstate.page. |
| 2358 |
* |
| 2359 |
* Also determines if later calls to _bt_checkkeys (for pstate.page) should be |
| 2360 |
* forced to treat all required scan keys >= pstate.startikey as nonrequired |
| 2361 |
* (that is, if they're to be treated as if any SK_BT_REQFWD/SK_BT_REQBKWD |
| 2362 |
* markings that were set by preprocessing were not set at all, for the |
| 2363 |
* duration of _bt_checkkeys calls prior to the call for pstate.finaltup). |
| 2364 |
* This is indicated to caller by setting pstate.forcenonrequired. |
| 2365 |
* |
| 2366 |
* Call here at the start of reading a leaf page beyond the first one for the |
| 2367 |
* primitive index scan. We consider all non-pivot tuples, so it doesn't make |
| 2368 |
* sense to call here when only a subset of those tuples can ever be read. |
| 2369 |
* This is also a good idea on performance grounds; not calling here when on |
| 2370 |
* the first page (first for the current primitive scan) avoids wasting cycles |
| 2371 |
* during selective point queries. They typically don't stand to gain as much |
| 2372 |
* when we can set pstate.startikey, and are likely to notice the overhead of |
| 2373 |
* calling here. (Also, allowing pstate.forcenonrequired to be set on a |
| 2374 |
* primscan's first page would mislead _bt_advance_array_keys, which expects |
| 2375 |
* pstate.nskipadvances to be representative of every first page's key space.) |
| 2376 |
* |
| 2377 |
* Caller must call _bt_start_array_keys and reset startikey/forcenonrequired |
| 2378 |
* ahead of the finaltup _bt_checkkeys call when we set forcenonrequired=true. |
| 2379 |
* This will give _bt_checkkeys the opportunity to call _bt_advance_array_keys |
| 2380 |
* with sktrig_required=true, restoring the invariant that the scan's required |
| 2381 |
* arrays always track the scan's progress through the index's key space. |
| 2382 |
* Caller won't need to do this on the rightmost/leftmost page in the index |
| 2383 |
* (where pstate.finaltup isn't ever set), since forcenonrequired will never |
| 2384 |
* be set here in the first place. |
| 2385 |
*/ |
| 2386 |
void |
| 2387 |
_bt_set_startikey(IndexScanDesc scan, BTReadPageState *pstate) |
| 2388 |
{ |
| 2389 |
BTScanOpaque so = (BTScanOpaque) scan->opaque; |
| 2390 |
Relation rel = scan->indexRelation; |
| 2391 |
TupleDesc tupdesc = RelationGetDescr(rel); |
| 2392 |
ItemId iid; |
| 2393 |
IndexTuple firsttup, |
| 2394 |
lasttup; |
| 2395 |
int startikey = 0, |
| 2396 |
arrayidx = 0, |
| 2397 |
firstchangingattnum; |
| 2398 |
bool start_past_saop_eq = false; |
| 2399 |
|
| 2400 |
Assert(!so->scanBehind); |
| 2401 |
Assert(pstate->minoff < pstate->maxoff); |
| 2402 |
Assert(!pstate->firstpage); |
| 2403 |
Assert(pstate->startikey == 0); |
| 2404 |
Assert(!so->numArrayKeys || pstate->finaltup || |
| 2405 |
P_RIGHTMOST(BTPageGetOpaque(pstate->page)) || |
| 2406 |
P_LEFTMOST(BTPageGetOpaque(pstate->page))); |
| 2407 |
|
| 2408 |
if (so->numberOfKeys == 0) |
| 2409 |
return; |
| 2410 |
|
| 2411 |
/* minoff is an offset to the lowest non-pivot tuple on the page */ |
| 2412 |
iid = PageGetItemId(pstate->page, pstate->minoff); |
| 2413 |
firsttup = (IndexTuple) PageGetItem(pstate->page, iid); |
| 2414 |
|
| 2415 |
/* maxoff is an offset to the highest non-pivot tuple on the page */ |
| 2416 |
iid = PageGetItemId(pstate->page, pstate->maxoff); |
| 2417 |
lasttup = (IndexTuple) PageGetItem(pstate->page, iid); |
| 2418 |
|
| 2419 |
/* Determine the first attribute whose values change on caller's page */ |
| 2420 |
firstchangingattnum = _bt_keep_natts_fast(rel, firsttup, lasttup); |
| 2421 |
|
| 2422 |
for (; startikey < so->numberOfKeys; startikey++) |
| 2423 |
{ |
| 2424 |
ScanKey key = so->keyData + startikey; |
| 2425 |
BTArrayKeyInfo *array; |
| 2426 |
Datum firstdatum, |
| 2427 |
lastdatum; |
| 2428 |
bool firstnull, |
| 2429 |
lastnull; |
| 2430 |
int32 result; |
| 2431 |
|
| 2432 |
/* |
| 2433 |
* Determine if it's safe to set pstate.startikey to an offset to a |
| 2434 |
* key that comes after this key, by examining this key |
| 2435 |
*/ |
| 2436 |
if (!(key->sk_flags & (SK_BT_REQFWD | SK_BT_REQBKWD))) |
| 2437 |
{ |
| 2438 |
/* Scan key isn't marked required (corner case) */ |
| 2439 |
break; /* unsafe */ |
| 2440 |
} |
| 2441 |
if (key->sk_flags & SK_ROW_HEADER) |
| 2442 |
{ |
| 2443 |
/* RowCompare inequalities currently aren't supported */ |
| 2444 |
break; /* "unsafe" */ |
| 2445 |
} |
| 2446 |
if (key->sk_strategy != BTEqualStrategyNumber) |
| 2447 |
{ |
| 2448 |
/* |
| 2449 |
* Scalar inequality key. |
| 2450 |
* |
| 2451 |
* It's definitely safe for _bt_checkkeys to avoid assessing this |
| 2452 |
* inequality when the page's first and last non-pivot tuples both |
| 2453 |
* satisfy the inequality (since the same must also be true of all |
| 2454 |
* the tuples in between these two). |
| 2455 |
* |
| 2456 |
* Unlike the "=" case, it doesn't matter if this attribute has |
| 2457 |
* more than one distinct value (though it _is_ necessary for any |
| 2458 |
* and all _prior_ attributes to contain no more than one distinct |
| 2459 |
* value amongst all of the tuples from pstate.page). |
| 2460 |
*/ |
| 2461 |
if (key->sk_attno > firstchangingattnum) /* >, not >= */ |
| 2462 |
break; /* unsafe, preceding attr has multiple |
| 2463 |
* distinct values */ |
| 2464 |
|
| 2465 |
firstdatum = index_getattr(firsttup, key->sk_attno, tupdesc, &firstnull); |
| 2466 |
lastdatum = index_getattr(lasttup, key->sk_attno, tupdesc, &lastnull); |
| 2467 |
|
| 2468 |
if (key->sk_flags & SK_ISNULL) |
| 2469 |
{ |
| 2470 |
/* IS NOT NULL key */ |
| 2471 |
Assert(key->sk_flags & SK_SEARCHNOTNULL); |
| 2472 |
|
| 2473 |
if (firstnull || lastnull) |
| 2474 |
break; /* unsafe */ |
| 2475 |
|
| 2476 |
/* Safe, IS NOT NULL key satisfied by every tuple */ |
| 2477 |
continue; |
| 2478 |
} |
| 2479 |
|
| 2480 |
/* Test firsttup */ |
| 2481 |
if (firstnull || |
| 2482 |
!DatumGetBool(FunctionCall2Coll(&key->sk_func, |
| 2483 |
key->sk_collation, firstdatum, |
| 2484 |
key->sk_argument))) |
| 2485 |
break; /* unsafe */ |
| 2486 |
|
| 2487 |
/* Test lasttup */ |
| 2488 |
if (lastnull || |
| 2489 |
!DatumGetBool(FunctionCall2Coll(&key->sk_func, |
| 2490 |
key->sk_collation, lastdatum, |
| 2491 |
key->sk_argument))) |
| 2492 |
break; /* unsafe */ |
| 2493 |
|
| 2494 |
/* Safe, scalar inequality satisfied by every tuple */ |
| 2495 |
continue; |
| 2496 |
} |
| 2497 |
|
| 2498 |
/* Some = key (could be a scalar = key, could be an array = key) */ |
| 2499 |
Assert(key->sk_strategy == BTEqualStrategyNumber); |
| 2500 |
|
| 2501 |
if (!(key->sk_flags & SK_SEARCHARRAY)) |
| 2502 |
{ |
| 2503 |
/* |
| 2504 |
* Scalar = key (possibly an IS NULL key). |
| 2505 |
* |
| 2506 |
* It is unsafe to set pstate.startikey to an ikey beyond this |
| 2507 |
* key, unless the = key is satisfied by every possible tuple on |
| 2508 |
* the page (possible only when attribute has just one distinct |
| 2509 |
* value among all tuples on the page). |
| 2510 |
*/ |
| 2511 |
if (key->sk_attno >= firstchangingattnum) |
| 2512 |
break; /* unsafe, multiple distinct attr values */ |
| 2513 |
|
| 2514 |
firstdatum = index_getattr(firsttup, key->sk_attno, tupdesc, |
| 2515 |
&firstnull); |
| 2516 |
if (key->sk_flags & SK_ISNULL) |
| 2517 |
{ |
| 2518 |
/* IS NULL key */ |
| 2519 |
Assert(key->sk_flags & SK_SEARCHNULL); |
| 2520 |
|
| 2521 |
if (!firstnull) |
| 2522 |
break; /* unsafe */ |
| 2523 |
|
| 2524 |
/* Safe, IS NULL key satisfied by every tuple */ |
| 2525 |
continue; |
| 2526 |
} |
| 2527 |
if (firstnull || |
| 2528 |
!DatumGetBool(FunctionCall2Coll(&key->sk_func, |
| 2529 |
key->sk_collation, firstdatum, |
| 2530 |
key->sk_argument))) |
| 2531 |
break; /* unsafe */ |
| 2532 |
|
| 2533 |
/* Safe, scalar = key satisfied by every tuple */ |
| 2534 |
continue; |
| 2535 |
} |
| 2536 |
|
| 2537 |
/* = array key (could be a SAOP array, could be a skip array) */ |
| 2538 |
array = &so->arrayKeys[arrayidx++]; |
| 2539 |
Assert(array->scan_key == startikey); |
| 2540 |
if (array->num_elems != -1) |
| 2541 |
{ |
| 2542 |
/* |
| 2543 |
* SAOP array = key. |
| 2544 |
* |
| 2545 |
* Handle this like we handle scalar = keys (though binary search |
| 2546 |
* for a matching element, to avoid relying on key's sk_argument). |
| 2547 |
*/ |
| 2548 |
if (key->sk_attno >= firstchangingattnum) |
| 2549 |
break; /* unsafe, multiple distinct attr values */ |
| 2550 |
|
| 2551 |
firstdatum = index_getattr(firsttup, key->sk_attno, tupdesc, |
| 2552 |
&firstnull); |
| 2553 |
_bt_binsrch_array_skey(&so->orderProcs[startikey], |
| 2554 |
false, NoMovementScanDirection, |
| 2555 |
firstdatum, firstnull, array, key, |
| 2556 |
&result); |
| 2557 |
if (result != 0) |
| 2558 |
break; /* unsafe */ |
| 2559 |
|
| 2560 |
/* Safe, SAOP = key satisfied by every tuple */ |
| 2561 |
start_past_saop_eq = true; |
| 2562 |
continue; |
| 2563 |
} |
| 2564 |
|
| 2565 |
/* |
| 2566 |
* Skip array = key |
| 2567 |
*/ |
| 2568 |
Assert(key->sk_flags & SK_BT_SKIP); |
| 2569 |
if (array->null_elem) |
| 2570 |
{ |
| 2571 |
/* |
| 2572 |
* Non-range skip array = key. |
| 2573 |
* |
| 2574 |
* Safe, non-range skip array "satisfied" by every tuple on page |
| 2575 |
* (safe even when "key->sk_attno > firstchangingattnum"). |
| 2576 |
*/ |
| 2577 |
continue; |
| 2578 |
} |
| 2579 |
|
| 2580 |
/* |
| 2581 |
* Range skip array = key. |
| 2582 |
* |
| 2583 |
* Handle this like we handle scalar inequality keys (but avoid using |
| 2584 |
* key's sk_argument directly, as in the SAOP array case). |
| 2585 |
*/ |
| 2586 |
if (key->sk_attno > firstchangingattnum) /* >, not >= */ |
| 2587 |
break; /* unsafe, preceding attr has multiple |
| 2588 |
* distinct values */ |
| 2589 |
|
| 2590 |
firstdatum = index_getattr(firsttup, key->sk_attno, tupdesc, &firstnull); |
| 2591 |
lastdatum = index_getattr(lasttup, key->sk_attno, tupdesc, &lastnull); |
| 2592 |
|
| 2593 |
/* Test firsttup */ |
| 2594 |
_bt_binsrch_skiparray_skey(false, ForwardScanDirection, |
| 2595 |
firstdatum, firstnull, array, key, |
| 2596 |
&result); |
| 2597 |
if (result != 0) |
| 2598 |
break; /* unsafe */ |
| 2599 |
|
| 2600 |
/* Test lasttup */ |
| 2601 |
_bt_binsrch_skiparray_skey(false, ForwardScanDirection, |
| 2602 |
lastdatum, lastnull, array, key, |
| 2603 |
&result); |
| 2604 |
if (result != 0) |
| 2605 |
break; /* unsafe */ |
| 2606 |
|
| 2607 |
/* Safe, range skip array satisfied by every tuple on page */ |
| 2608 |
} |
| 2609 |
|
| 2610 |
/* |
| 2611 |
* Use of forcenonrequired is typically undesirable, since it'll force |
| 2612 |
* _bt_readpage caller to read every tuple on the page -- even though, in |
| 2613 |
* general, it might well be possible to end the scan on an earlier tuple. |
| 2614 |
* However, caller must use forcenonrequired when start_past_saop_eq=true, |
| 2615 |
* since the usual required array behavior might fail to roll over to the |
| 2616 |
* SAOP array. |
| 2617 |
* |
| 2618 |
* We always prefer forcenonrequired=true during scans with skip arrays |
| 2619 |
* (except on the first page of each primitive index scan), though -- even |
| 2620 |
* when "startikey == 0". That way, _bt_advance_array_keys's low-order |
| 2621 |
* key precheck optimization can always be used (unless on the first page |
| 2622 |
* of the scan). It seems slightly preferable to check more tuples when |
| 2623 |
* that allows us to do significantly less skip array maintenance. |
| 2624 |
*/ |
| 2625 |
pstate->forcenonrequired = (start_past_saop_eq || so->skipScan); |
| 2626 |
pstate->startikey = startikey; |
| 2627 |
|
| 2628 |
/* |
| 2629 |
* _bt_readpage caller is required to call _bt_checkkeys against page's |
| 2630 |
* finaltup with forcenonrequired=false whenever we initially set |
| 2631 |
* forcenonrequired=true. That way the scan's arrays will reliably track |
| 2632 |
* its progress through the index's key space. |
| 2633 |
* |
| 2634 |
* We don't expect this when _bt_readpage caller has no finaltup due to |
| 2635 |
* its page being the rightmost (or the leftmost, during backwards scans). |
| 2636 |
* When we see that _bt_readpage has no finaltup, back out of everything. |
| 2637 |
*/ |
| 2638 |
Assert(!pstate->forcenonrequired || so->numArrayKeys); |
| 2639 |
if (pstate->forcenonrequired && !pstate->finaltup) |
| 2640 |
{ |
| 2641 |
pstate->forcenonrequired = false; |
| 2642 |
pstate->startikey = 0; |
| 2643 |
} |
| 2644 |
} |
| 2645 |
|
| 2646 |
/* |
| 2647 |
* Test whether an indextuple satisfies current scan condition. |
| 2648 |
* |
| 2649 |
* Return true if so, false if not. If not, also sets *continuescan to false |
| 2650 |
* when it's also not possible for any later tuples to pass the current qual |
| 2651 |
* (with the scan's current set of array keys, in the current scan direction), |
| 2652 |
* in addition to setting *ikey to the so->keyData[] subscript/offset for the |
| 2653 |
* unsatisfied scan key (needed when caller must consider advancing the scan's |
| 2654 |
* array keys). |
| 2655 |
* |
| 2656 |
* This is a subroutine for _bt_checkkeys. We provisionally assume that |
| 2657 |
* reaching the end of the current set of required keys (in particular the |
| 2658 |
* current required array keys) ends the ongoing (primitive) index scan. |
| 2659 |
* Callers without array keys should just end the scan right away when they |
| 2660 |
* find that continuescan has been set to false here by us. Things are more |
| 2661 |
* complicated for callers with array keys. |
| 2662 |
* |
| 2663 |
* Callers with array keys must first consider advancing the arrays when |
| 2664 |
* continuescan has been set to false here by us. They must then consider if |
| 2665 |
* it really does make sense to end the current (primitive) index scan, in |
| 2666 |
* light of everything that is known at that point. (In general when we set |
| 2667 |
* continuescan=false for these callers it must be treated as provisional.) |
| 2668 |
* |
| 2669 |
* We deal with advancing unsatisfied non-required arrays directly, though. |
| 2670 |
* This is safe, since by definition non-required keys can't end the scan. |
| 2671 |
* This is just how we determine if non-required arrays are just unsatisfied |
| 2672 |
* by the current array key, or if they're truly unsatisfied (that is, if |
| 2673 |
* they're unsatisfied by every possible array key). |
| 2674 |
* |
| 2675 |
* Pass advancenonrequired=false to avoid all array related side effects. |
| 2676 |
* This allows _bt_advance_array_keys caller to avoid infinite recursion. |
| 2677 |
* |
| 2678 |
* Pass forcenonrequired=true to instruct us to treat all keys as nonrequired. |
| 2679 |
* This is used to make it safe to temporarily stop properly maintaining the |
| 2680 |
* scan's required arrays. _bt_checkkeys caller (_bt_readpage, actually) |
| 2681 |
* determines a prefix of keys that must satisfy every possible corresponding |
| 2682 |
* index attribute value from its page, which is passed to us via *ikey arg |
| 2683 |
* (this is the first key that might be unsatisfied by tuples on the page). |
| 2684 |
* Obviously, we won't maintain any array keys from before *ikey, so it's |
| 2685 |
* quite possible for such arrays to "fall behind" the index's keyspace. |
| 2686 |
* Caller will need to "catch up" by passing forcenonrequired=true (alongside |
| 2687 |
* an *ikey=0) once the page's finaltup is reached. |
| 2688 |
* |
| 2689 |
* Note: it's safe to pass an *ikey > 0 with forcenonrequired=false, but only |
| 2690 |
* when caller determines that it won't affect array maintenance. |
| 2691 |
*/ |
| 2692 |
static bool |
| 2693 |
_bt_check_compare(IndexScanDesc scan, ScanDirection dir, |
| 2694 |
IndexTuple tuple, int tupnatts, TupleDesc tupdesc, |
| 2695 |
bool advancenonrequired, bool forcenonrequired, |
| 2696 |
bool *continuescan, int *ikey) |
| 2697 |
{ |
| 2698 |
BTScanOpaque so = (BTScanOpaque) scan->opaque; |
| 2699 |
|
| 2700 |
*continuescan = true; /* default assumption */ |
| 2701 |
|
| 2702 |
for (; *ikey < so->numberOfKeys; (*ikey)++) |
| 2703 |
{ |
| 2704 |
ScanKey key = so->keyData + *ikey; |
| 2705 |
Datum datum; |
| 2706 |
bool isNull; |
| 2707 |
bool requiredSameDir = false, |
| 2708 |
requiredOppositeDirOnly = false; |
| 2709 |
|
| 2710 |
/* |
| 2711 |
* Check if the key is required in the current scan direction, in the |
| 2712 |
* opposite scan direction _only_, or in neither direction (except |
| 2713 |
* when we're forced to treat all scan keys as nonrequired) |
| 2714 |
*/ |
| 2715 |
if (forcenonrequired) |
| 2716 |
{ |
| 2717 |
/* treating scan's keys as non-required */ |
| 2718 |
} |
| 2719 |
else if (((key->sk_flags & SK_BT_REQFWD) && ScanDirectionIsForward(dir)) || |
| 2720 |
((key->sk_flags & SK_BT_REQBKWD) && ScanDirectionIsBackward(dir))) |
| 2721 |
requiredSameDir = true; |
| 2722 |
else if (((key->sk_flags & SK_BT_REQFWD) && ScanDirectionIsBackward(dir)) || |
| 2723 |
((key->sk_flags & SK_BT_REQBKWD) && ScanDirectionIsForward(dir))) |
| 2724 |
requiredOppositeDirOnly = true; |
| 2725 |
|
| 2726 |
if (key->sk_attno > tupnatts) |
| 2727 |
{ |
| 2728 |
/* |
| 2729 |
* This attribute is truncated (must be high key). The value for |
| 2730 |
* this attribute in the first non-pivot tuple on the page to the |
| 2731 |
* right could be any possible value. Assume that truncated |
| 2732 |
* attribute passes the qual. |
| 2733 |
*/ |
| 2734 |
Assert(BTreeTupleIsPivot(tuple)); |
| 2735 |
continue; |
| 2736 |
} |
| 2737 |
|
| 2738 |
/* |
| 2739 |
* A skip array scan key uses one of several sentinel values. We just |
| 2740 |
* fall back on _bt_tuple_before_array_skeys when we see such a value. |
| 2741 |
*/ |
| 2742 |
if (key->sk_flags & (SK_BT_MINVAL | SK_BT_MAXVAL | |
| 2743 |
SK_BT_NEXT | SK_BT_PRIOR)) |
| 2744 |
{ |
| 2745 |
Assert(key->sk_flags & SK_SEARCHARRAY); |
| 2746 |
Assert(key->sk_flags & SK_BT_SKIP); |
| 2747 |
Assert(requiredSameDir || forcenonrequired); |
| 2748 |
|
| 2749 |
/* |
| 2750 |
* Cannot fall back on _bt_tuple_before_array_skeys when we're |
| 2751 |
* treating the scan's keys as nonrequired, though. Just handle |
| 2752 |
* this like any other non-required equality-type array key. |
| 2753 |
*/ |
| 2754 |
if (forcenonrequired) |
| 2755 |
return _bt_advance_array_keys(scan, NULL, tuple, tupnatts, |
| 2756 |
tupdesc, *ikey, false); |
| 2757 |
|
| 2758 |
*continuescan = false; |
| 2759 |
return false; |
| 2760 |
} |
| 2761 |
|
| 2762 |
/* row-comparison keys need special processing */ |
| 2763 |
if (key->sk_flags & SK_ROW_HEADER) |
| 2764 |
{ |
| 2765 |
if (_bt_check_rowcompare(key, tuple, tupnatts, tupdesc, dir, |
| 2766 |
forcenonrequired, continuescan)) |
| 2767 |
continue; |
| 2768 |
return false; |
| 2769 |
} |
| 2770 |
|
| 2771 |
datum = index_getattr(tuple, |
| 2772 |
key->sk_attno, |
| 2773 |
tupdesc, |
| 2774 |
&isNull); |
| 2775 |
|
| 2776 |
if (key->sk_flags & SK_ISNULL) |
| 2777 |
{ |
| 2778 |
/* Handle IS NULL/NOT NULL tests */ |
| 2779 |
if (key->sk_flags & SK_SEARCHNULL) |
| 2780 |
{ |
| 2781 |
if (isNull) |
| 2782 |
continue; /* tuple satisfies this qual */ |
| 2783 |
} |
| 2784 |
else |
| 2785 |
{ |
| 2786 |
Assert(key->sk_flags & SK_SEARCHNOTNULL); |
| 2787 |
Assert(!(key->sk_flags & SK_BT_SKIP)); |
| 2788 |
if (!isNull) |
| 2789 |
continue; /* tuple satisfies this qual */ |
| 2790 |
} |
| 2791 |
|
| 2792 |
/* |
| 2793 |
* Tuple fails this qual. If it's a required qual for the current |
| 2794 |
* scan direction, then we can conclude no further tuples will |
| 2795 |
* pass, either. |
| 2796 |
*/ |
| 2797 |
if (requiredSameDir) |
| 2798 |
*continuescan = false; |
| 2799 |
else if (unlikely(key->sk_flags & SK_BT_SKIP)) |
| 2800 |
{ |
| 2801 |
/* |
| 2802 |
* If we're treating scan keys as nonrequired, and encounter a |
| 2803 |
* skip array scan key whose current element is NULL, then it |
| 2804 |
* must be a non-range skip array. It must be satisfied, so |
| 2805 |
* there's no need to call _bt_advance_array_keys to check. |
| 2806 |
*/ |
| 2807 |
Assert(forcenonrequired && *ikey > 0); |
| 2808 |
continue; |
| 2809 |
} |
| 2810 |
|
| 2811 |
/* |
| 2812 |
* This indextuple doesn't match the qual. |
| 2813 |
*/ |
| 2814 |
return false; |
| 2815 |
} |
| 2816 |
|
| 2817 |
if (isNull) |
| 2818 |
{ |
| 2819 |
/* |
| 2820 |
* Scalar scan key isn't satisfied by NULL tuple value. |
| 2821 |
* |
| 2822 |
* If we're treating scan keys as nonrequired, and key is for a |
| 2823 |
* skip array, then we must attempt to advance the array to NULL |
| 2824 |
* (if we're successful then the tuple might match the qual). |
| 2825 |
*/ |
| 2826 |
if (unlikely(forcenonrequired && key->sk_flags & SK_BT_SKIP)) |
| 2827 |
return _bt_advance_array_keys(scan, NULL, tuple, tupnatts, |
| 2828 |
tupdesc, *ikey, false); |
| 2829 |
|
| 2830 |
if (key->sk_flags & SK_BT_NULLS_FIRST) |
| 2831 |
{ |
| 2832 |
/* |
| 2833 |
* Since NULLs are sorted before non-NULLs, we know we have |
| 2834 |
* reached the lower limit of the range of values for this |
| 2835 |
* index attr. On a backward scan, we can stop if this qual |
| 2836 |
* is one of the "must match" subset. We can stop regardless |
| 2837 |
* of whether the qual is > or <, so long as it's required, |
| 2838 |
* because it's not possible for any future tuples to pass. On |
| 2839 |
* a forward scan, however, we must keep going, because we may |
| 2840 |
* have initially positioned to the start of the index. |
| 2841 |
* (_bt_advance_array_keys also relies on this behavior during |
| 2842 |
* forward scans.) |
| 2843 |
*/ |
| 2844 |
if ((requiredSameDir || requiredOppositeDirOnly) && |
| 2845 |
ScanDirectionIsBackward(dir)) |
| 2846 |
*continuescan = false; |
| 2847 |
} |
| 2848 |
else |
| 2849 |
{ |
| 2850 |
/* |
| 2851 |
* Since NULLs are sorted after non-NULLs, we know we have |
| 2852 |
* reached the upper limit of the range of values for this |
| 2853 |
* index attr. On a forward scan, we can stop if this qual is |
| 2854 |
* one of the "must match" subset. We can stop regardless of |
| 2855 |
* whether the qual is > or <, so long as it's required, |
| 2856 |
* because it's not possible for any future tuples to pass. On |
| 2857 |
* a backward scan, however, we must keep going, because we |
| 2858 |
* may have initially positioned to the end of the index. |
| 2859 |
* (_bt_advance_array_keys also relies on this behavior during |
| 2860 |
* backward scans.) |
| 2861 |
*/ |
| 2862 |
if ((requiredSameDir || requiredOppositeDirOnly) && |
| 2863 |
ScanDirectionIsForward(dir)) |
| 2864 |
*continuescan = false; |
| 2865 |
} |
| 2866 |
|
| 2867 |
/* |
| 2868 |
* This indextuple doesn't match the qual. |
| 2869 |
*/ |
| 2870 |
return false; |
| 2871 |
} |
| 2872 |
|
| 2873 |
if (!DatumGetBool(FunctionCall2Coll(&key->sk_func, key->sk_collation, |
| 2874 |
datum, key->sk_argument))) |
| 2875 |
{ |
| 2876 |
/* |
| 2877 |
* Tuple fails this qual. If it's a required qual for the current |
| 2878 |
* scan direction, then we can conclude no further tuples will |
| 2879 |
* pass, either. |
| 2880 |
*/ |
| 2881 |
if (requiredSameDir) |
| 2882 |
*continuescan = false; |
| 2883 |
|
| 2884 |
/* |
| 2885 |
* If this is a non-required equality-type array key, the tuple |
| 2886 |
* needs to be checked against every possible array key. Handle |
| 2887 |
* this by "advancing" the scan key's array to a matching value |
| 2888 |
* (if we're successful then the tuple might match the qual). |
| 2889 |
*/ |
| 2890 |
else if (advancenonrequired && |
| 2891 |
key->sk_strategy == BTEqualStrategyNumber && |
| 2892 |
(key->sk_flags & SK_SEARCHARRAY)) |
| 2893 |
return _bt_advance_array_keys(scan, NULL, tuple, tupnatts, |
| 2894 |
tupdesc, *ikey, false); |
| 2895 |
|
| 2896 |
/* |
| 2897 |
* This indextuple doesn't match the qual. |
| 2898 |
*/ |
| 2899 |
return false; |
| 2900 |
} |
| 2901 |
} |
| 2902 |
|
| 2903 |
/* If we get here, the tuple passes all index quals. */ |
| 2904 |
return true; |
| 2905 |
} |
| 2906 |
|
| 2907 |
/* |
| 2908 |
* Test whether an indextuple satisfies a row-comparison scan condition. |
| 2909 |
* |
| 2910 |
* Return true if so, false if not. If not, also clear *continuescan if |
| 2911 |
* it's not possible for any future tuples in the current scan direction |
| 2912 |
* to pass the qual. |
| 2913 |
* |
| 2914 |
* This is a subroutine for _bt_checkkeys/_bt_check_compare. Caller passes us |
| 2915 |
* a row compare header key taken from so->keyData[]. |
| 2916 |
* |
| 2917 |
* Row value comparisons can be described in terms of logical expansions that |
| 2918 |
* use only scalar operators. Consider the following example row comparison: |
| 2919 |
* |
| 2920 |
* "(a, b, c) > (7, 'bar', 62)" |
| 2921 |
* |
| 2922 |
* This can be evaluated as: |
| 2923 |
* |
| 2924 |
* "(a = 7 AND b = 'bar' AND c > 62) OR (a = 7 AND b > 'bar') OR (a > 7)". |
| 2925 |
* |
| 2926 |
* Notice that this condition is satisfied by _all_ rows that satisfy "a > 7", |
| 2927 |
* and by a subset of all rows that satisfy "a >= 7" (possibly all such rows). |
| 2928 |
* It _can't_ be satisfied by other rows (where "a < 7" or where "a IS NULL"). |
| 2929 |
* A row comparison header key can therefore often be treated as if it was a |
| 2930 |
* simple scalar inequality on the row compare's most significant column. |
| 2931 |
* (For example, _bt_advance_array_keys and most preprocessing routines treat |
| 2932 |
* row compares like any other same-strategy inequality on the same column.) |
| 2933 |
* |
| 2934 |
* Things get more complicated for our row compare given a row where "a = 7". |
| 2935 |
* Note that a row compare isn't necessarily satisfied by _every_ tuple that |
| 2936 |
* appears between the first and last satisfied tuple returned by the scan, |
| 2937 |
* due to the way that its lower-order subkeys are only conditionally applied. |
| 2938 |
* A forwards scan that uses our example qual might initially return a tuple |
| 2939 |
* "(a, b, c) = (7, 'zebra', 54)". But it won't subsequently return a tuple |
| 2940 |
* "(a, b, c) = (7, NULL, 1)" located to the right of the first matching tuple |
| 2941 |
* (assume that "b" was declared NULLS LAST here). The scan will only return |
| 2942 |
* additional matches upon reaching tuples where "a > 7". If you rereview our |
| 2943 |
* example row comparison's logical expansion, you'll understand why this is. |
| 2944 |
* (Here we assume that all subkeys could be marked required, guaranteeing |
| 2945 |
* that row comparison order matches index order. This is the common case.) |
| 2946 |
* |
| 2947 |
* Note that a row comparison header key behaves _exactly_ the same as a |
| 2948 |
* similar scalar inequality key on the row's most significant column once the |
| 2949 |
* scan reaches the point where it no longer needs to evaluate lower-order |
| 2950 |
* subkeys (or before the point where it starts needing to evaluate them). |
| 2951 |
* For example, once a forwards scan that uses our example qual reaches the |
| 2952 |
* first tuple "a > 7", we'll behave in just the same way as our caller would |
| 2953 |
* behave with a similar scalar inequality "a > 7" for the remainder of the |
| 2954 |
* scan (assuming that the scan never changes direction/never goes backwards). |
| 2955 |
* We'll even set continuescan=false according to exactly the same rules as |
| 2956 |
* the ones our caller applies with simple scalar inequalities, including the |
| 2957 |
* rules it applies when NULL tuple values don't satisfy an inequality qual. |
| 2958 |
*/ |
| 2959 |
static bool |
| 2960 |
_bt_check_rowcompare(ScanKey header, IndexTuple tuple, int tupnatts, |
| 2961 |
TupleDesc tupdesc, ScanDirection dir, |
| 2962 |
bool forcenonrequired, bool *continuescan) |
| 2963 |
{ |
| 2964 |
ScanKey subkey = (ScanKey) DatumGetPointer(header->sk_argument); |
| 2965 |
int32 cmpresult = 0; |
| 2966 |
bool result; |
| 2967 |
|
| 2968 |
/* First subkey should be same as the header says */ |
| 2969 |
Assert(header->sk_flags & SK_ROW_HEADER); |
| 2970 |
Assert(subkey->sk_attno == header->sk_attno); |
| 2971 |
Assert(subkey->sk_strategy == header->sk_strategy); |
| 2972 |
|
| 2973 |
/* Loop over columns of the row condition */ |
| 2974 |
for (;;) |
| 2975 |
{ |
| 2976 |
Datum datum; |
| 2977 |
bool isNull; |
| 2978 |
|
| 2979 |
Assert(subkey->sk_flags & SK_ROW_MEMBER); |
| 2980 |
|
| 2981 |
/* When a NULL row member is compared, the row never matches */ |
| 2982 |
if (subkey->sk_flags & SK_ISNULL) |
| 2983 |
{ |
| 2984 |
/* |
| 2985 |
* Unlike the simple-scankey case, this isn't a disallowed case |
| 2986 |
* (except when it's the first row element that has the NULL arg). |
| 2987 |
* But it can never match. If all the earlier row comparison |
| 2988 |
* columns are required for the scan direction, we can stop the |
| 2989 |
* scan, because there can't be another tuple that will succeed. |
| 2990 |
*/ |
| 2991 |
Assert(subkey != (ScanKey) DatumGetPointer(header->sk_argument)); |
| 2992 |
subkey--; |
| 2993 |
if (forcenonrequired) |
| 2994 |
{ |
| 2995 |
/* treating scan's keys as non-required */ |
| 2996 |
} |
| 2997 |
else if ((subkey->sk_flags & SK_BT_REQFWD) && |
| 2998 |
ScanDirectionIsForward(dir)) |
| 2999 |
*continuescan = false; |
| 3000 |
else if ((subkey->sk_flags & SK_BT_REQBKWD) && |
| 3001 |
ScanDirectionIsBackward(dir)) |
| 3002 |
*continuescan = false; |
| 3003 |
return false; |
| 3004 |
} |
| 3005 |
|
| 3006 |
if (subkey->sk_attno > tupnatts) |
| 3007 |
{ |
| 3008 |
/* |
| 3009 |
* This attribute is truncated (must be high key). The value for |
| 3010 |
* this attribute in the first non-pivot tuple on the page to the |
| 3011 |
* right could be any possible value. Assume that truncated |
| 3012 |
* attribute passes the qual. |
| 3013 |
*/ |
| 3014 |
Assert(BTreeTupleIsPivot(tuple)); |
| 3015 |
return true; |
| 3016 |
} |
| 3017 |
|
| 3018 |
datum = index_getattr(tuple, |
| 3019 |
subkey->sk_attno, |
| 3020 |
tupdesc, |
| 3021 |
&isNull); |
| 3022 |
|
| 3023 |
if (isNull) |
| 3024 |
{ |
| 3025 |
int reqflags; |
| 3026 |
|
| 3027 |
if (forcenonrequired) |
| 3028 |
{ |
| 3029 |
/* treating scan's keys as non-required */ |
| 3030 |
} |
| 3031 |
else if (subkey->sk_flags & SK_BT_NULLS_FIRST) |
| 3032 |
{ |
| 3033 |
/* |
| 3034 |
* Since NULLs are sorted before non-NULLs, we know we have |
| 3035 |
* reached the lower limit of the range of values for this |
| 3036 |
* index attr. On a backward scan, we can stop if this qual |
| 3037 |
* is one of the "must match" subset. However, on a forwards |
| 3038 |
* scan, we must keep going, because we may have initially |
| 3039 |
* positioned to the start of the index. |
| 3040 |
* |
| 3041 |
* All required NULLS FIRST > row members can use NULL tuple |
| 3042 |
* values to end backwards scans, just like with other values. |
| 3043 |
* A qual "WHERE (a, b, c) > (9, 42, 'foo')" can terminate a |
| 3044 |
* backwards scan upon reaching the index's rightmost "a = 9" |
| 3045 |
* tuple whose "b" column contains a NULL (if not sooner). |
| 3046 |
* Since "b" is NULLS FIRST, we can treat its NULLs as "<" 42. |
| 3047 |
*/ |
| 3048 |
reqflags = SK_BT_REQBKWD; |
| 3049 |
|
| 3050 |
/* |
| 3051 |
* When a most significant required NULLS FIRST < row compare |
| 3052 |
* member sees NULL tuple values during a backwards scan, it |
| 3053 |
* signals the end of matches for the whole row compare/scan. |
| 3054 |
* A qual "WHERE (a, b, c) < (9, 42, 'foo')" will terminate a |
| 3055 |
* backwards scan upon reaching the rightmost tuple whose "a" |
| 3056 |
* column has a NULL. The "a" NULL value is "<" 9, and yet |
| 3057 |
* our < row compare will still end the scan. (This isn't |
| 3058 |
* safe with later/lower-order row members. Notice that it |
| 3059 |
* can only happen with an "a" NULL some time after the scan |
| 3060 |
* completely stops needing to use its "b" and "c" members.) |
| 3061 |
*/ |
| 3062 |
if (subkey == (ScanKey) DatumGetPointer(header->sk_argument)) |
| 3063 |
reqflags |= SK_BT_REQFWD; /* safe, first row member */ |
| 3064 |
|
| 3065 |
if ((subkey->sk_flags & reqflags) && |
| 3066 |
ScanDirectionIsBackward(dir)) |
| 3067 |
*continuescan = false; |
| 3068 |
} |
| 3069 |
else |
| 3070 |
{ |
| 3071 |
/* |
| 3072 |
* Since NULLs are sorted after non-NULLs, we know we have |
| 3073 |
* reached the upper limit of the range of values for this |
| 3074 |
* index attr. On a forward scan, we can stop if this qual is |
| 3075 |
* one of the "must match" subset. However, on a backward |
| 3076 |
* scan, we must keep going, because we may have initially |
| 3077 |
* positioned to the end of the index. |
| 3078 |
* |
| 3079 |
* All required NULLS LAST < row members can use NULL tuple |
| 3080 |
* values to end forwards scans, just like with other values. |
| 3081 |
* A qual "WHERE (a, b, c) < (9, 42, 'foo')" can terminate a |
| 3082 |
* forwards scan upon reaching the index's leftmost "a = 9" |
| 3083 |
* tuple whose "b" column contains a NULL (if not sooner). |
| 3084 |
* Since "b" is NULLS LAST, we can treat its NULLs as ">" 42. |
| 3085 |
*/ |
| 3086 |
reqflags = SK_BT_REQFWD; |
| 3087 |
|
| 3088 |
/* |
| 3089 |
* When a most significant required NULLS LAST > row compare |
| 3090 |
* member sees NULL tuple values during a forwards scan, it |
| 3091 |
* signals the end of matches for the whole row compare/scan. |
| 3092 |
* A qual "WHERE (a, b, c) > (9, 42, 'foo')" will terminate a |
| 3093 |
* forwards scan upon reaching the leftmost tuple whose "a" |
| 3094 |
* column has a NULL. The "a" NULL value is ">" 9, and yet |
| 3095 |
* our > row compare will end the scan. (This isn't safe with |
| 3096 |
* later/lower-order row members. Notice that it can only |
| 3097 |
* happen with an "a" NULL some time after the scan completely |
| 3098 |
* stops needing to use its "b" and "c" members.) |
| 3099 |
*/ |
| 3100 |
if (subkey == (ScanKey) DatumGetPointer(header->sk_argument)) |
| 3101 |
reqflags |= SK_BT_REQBKWD; /* safe, first row member */ |
| 3102 |
|
| 3103 |
if ((subkey->sk_flags & reqflags) && |
| 3104 |
ScanDirectionIsForward(dir)) |
| 3105 |
*continuescan = false; |
| 3106 |
} |
| 3107 |
|
| 3108 |
/* |
| 3109 |
* In any case, this indextuple doesn't match the qual. |
| 3110 |
*/ |
| 3111 |
return false; |
| 3112 |
} |
| 3113 |
|
| 3114 |
/* Perform the test --- three-way comparison not bool operator */ |
| 3115 |
cmpresult = DatumGetInt32(FunctionCall2Coll(&subkey->sk_func, |
| 3116 |
subkey->sk_collation, |
| 3117 |
datum, |
| 3118 |
subkey->sk_argument)); |
| 3119 |
|
| 3120 |
if (subkey->sk_flags & SK_BT_DESC) |
| 3121 |
INVERT_COMPARE_RESULT(cmpresult); |
| 3122 |
|
| 3123 |
/* Done comparing if unequal, else advance to next column */ |
| 3124 |
if (cmpresult != 0) |
| 3125 |
break; |
| 3126 |
|
| 3127 |
if (subkey->sk_flags & SK_ROW_END) |
| 3128 |
break; |
| 3129 |
subkey++; |
| 3130 |
} |
| 3131 |
|
| 3132 |
/* |
| 3133 |
* At this point cmpresult indicates the overall result of the row |
| 3134 |
* comparison, and subkey points to the deciding column (or the last |
| 3135 |
* column if the result is "="). |
| 3136 |
*/ |
| 3137 |
switch (subkey->sk_strategy) |
| 3138 |
{ |
| 3139 |
/* EQ and NE cases aren't allowed here */ |
| 3140 |
case BTLessStrategyNumber: |
| 3141 |
result = (cmpresult < 0); |
| 3142 |
break; |
| 3143 |
case BTLessEqualStrategyNumber: |
| 3144 |
result = (cmpresult <= 0); |
| 3145 |
break; |
| 3146 |
case BTGreaterEqualStrategyNumber: |
| 3147 |
result = (cmpresult >= 0); |
| 3148 |
break; |
| 3149 |
case BTGreaterStrategyNumber: |
| 3150 |
result = (cmpresult > 0); |
| 3151 |
break; |
| 3152 |
default: |
| 3153 |
elog(ERROR, "unexpected strategy number %d", subkey->sk_strategy); |
| 3154 |
result = 0; /* keep compiler quiet */ |
| 3155 |
break; |
| 3156 |
} |
| 3157 |
|
| 3158 |
if (!result && !forcenonrequired) |
| 3159 |
{ |
| 3160 |
/* |
| 3161 |
* Tuple fails this qual. If it's a required qual for the current |
| 3162 |
* scan direction, then we can conclude no further tuples will pass, |
| 3163 |
* either. Note we have to look at the deciding column, not |
| 3164 |
* necessarily the first or last column of the row condition. |
| 3165 |
*/ |
| 3166 |
if ((subkey->sk_flags & SK_BT_REQFWD) && |
| 3167 |
ScanDirectionIsForward(dir)) |
| 3168 |
*continuescan = false; |
| 3169 |
else if ((subkey->sk_flags & SK_BT_REQBKWD) && |
| 3170 |
ScanDirectionIsBackward(dir)) |
| 3171 |
*continuescan = false; |
| 3172 |
} |
| 3173 |
|
| 3174 |
return result; |
| 3175 |
} |
| 3176 |
|
| 3177 |
/* |
| 3178 |
* Determine if a scan with array keys should skip over uninteresting tuples. |
| 3179 |
* |
| 3180 |
* This is a subroutine for _bt_checkkeys. Called when _bt_readpage's linear |
| 3181 |
* search process (started after it finishes reading an initial group of |
| 3182 |
* matching tuples, used to locate the start of the next group of tuples |
| 3183 |
* matching the next set of required array keys) has already scanned an |
| 3184 |
* excessive number of tuples whose key space is "between arrays". |
| 3185 |
* |
| 3186 |
* When we perform look ahead successfully, we'll sets pstate.skip, which |
| 3187 |
* instructs _bt_readpage to skip ahead to that tuple next (could be past the |
| 3188 |
* end of the scan's leaf page). Pages where the optimization is effective |
| 3189 |
* will generally still need to skip several times. Each call here performs |
| 3190 |
* only a single "look ahead" comparison of a later tuple, whose distance from |
| 3191 |
* the current tuple's offset number is determined by applying heuristics. |
| 3192 |
*/ |
| 3193 |
static void |
| 3194 |
_bt_checkkeys_look_ahead(IndexScanDesc scan, BTReadPageState *pstate, |
| 3195 |
int tupnatts, TupleDesc tupdesc) |
| 3196 |
{ |
| 3197 |
BTScanOpaque so = (BTScanOpaque) scan->opaque; |
| 3198 |
ScanDirection dir = so->currPos.dir; |
| 3199 |
OffsetNumber aheadoffnum; |
| 3200 |
IndexTuple ahead; |
| 3201 |
|
| 3202 |
Assert(!pstate->forcenonrequired); |
| 3203 |
|
| 3204 |
/* Avoid looking ahead when comparing the page high key */ |
| 3205 |
if (pstate->offnum < pstate->minoff) |
| 3206 |
return; |
| 3207 |
|
| 3208 |
/* |
| 3209 |
* Don't look ahead when there aren't enough tuples remaining on the page |
| 3210 |
* (in the current scan direction) for it to be worth our while |
| 3211 |
*/ |
| 3212 |
if (ScanDirectionIsForward(dir) && |
| 3213 |
pstate->offnum >= pstate->maxoff - LOOK_AHEAD_DEFAULT_DISTANCE) |
| 3214 |
return; |
| 3215 |
else if (ScanDirectionIsBackward(dir) && |
| 3216 |
pstate->offnum <= pstate->minoff + LOOK_AHEAD_DEFAULT_DISTANCE) |
| 3217 |
return; |
| 3218 |
|
| 3219 |
/* |
| 3220 |
* The look ahead distance starts small, and ramps up as each call here |
| 3221 |
* allows _bt_readpage to skip over more tuples |
| 3222 |
*/ |
| 3223 |
if (!pstate->targetdistance) |
| 3224 |
pstate->targetdistance = LOOK_AHEAD_DEFAULT_DISTANCE; |
| 3225 |
else if (pstate->targetdistance < MaxIndexTuplesPerPage / 2) |
| 3226 |
pstate->targetdistance *= 2; |
| 3227 |
|
| 3228 |
/* Don't read past the end (or before the start) of the page, though */ |
| 3229 |
if (ScanDirectionIsForward(dir)) |
| 3230 |
aheadoffnum = Min((int) pstate->maxoff, |
| 3231 |
(int) pstate->offnum + pstate->targetdistance); |
| 3232 |
else |
| 3233 |
aheadoffnum = Max((int) pstate->minoff, |
| 3234 |
(int) pstate->offnum - pstate->targetdistance); |
| 3235 |
|
| 3236 |
ahead = (IndexTuple) PageGetItem(pstate->page, |
| 3237 |
PageGetItemId(pstate->page, aheadoffnum)); |
| 3238 |
if (_bt_tuple_before_array_skeys(scan, dir, ahead, tupdesc, tupnatts, |
| 3239 |
false, 0, NULL)) |
| 3240 |
{ |
| 3241 |
/* |
| 3242 |
* Success -- instruct _bt_readpage to skip ahead to very next tuple |
| 3243 |
* after the one we determined was still before the current array keys |
| 3244 |
*/ |
| 3245 |
if (ScanDirectionIsForward(dir)) |
| 3246 |
pstate->skip = aheadoffnum + 1; |
| 3247 |
else |
| 3248 |
pstate->skip = aheadoffnum - 1; |
| 3249 |
} |
| 3250 |
else |
| 3251 |
{ |
| 3252 |
/* |
| 3253 |
* Failure -- "ahead" tuple is too far ahead (we were too aggressive). |
| 3254 |
* |
| 3255 |
* Reset the number of rechecks, and aggressively reduce the target |
| 3256 |
* distance (we're much more aggressive here than we were when the |
| 3257 |
* distance was initially ramped up). |
| 3258 |
*/ |
| 3259 |
pstate->rechecks = 0; |
| 3260 |
pstate->targetdistance = Max(pstate->targetdistance / 8, 1); |
| 3261 |
} |
| 3262 |
} |
| 3263 |
|
| 3264 |
/* |
| 3265 |
* _bt_killitems - set LP_DEAD state for items an indexscan caller has |
| 3266 |
* told us were killed |
| 3267 |
* |
| 3268 |
* scan->opaque, referenced locally through so, contains information about the |
| 3269 |
* current page and killed tuples thereon (generally, this should only be |
| 3270 |
* called if so->numKilled > 0). |
| 3271 |
* |
| 3272 |
* Caller should not have a lock on the so->currPos page, but must hold a |
| 3273 |
* buffer pin when !so->dropPin. When we return, it still won't be locked. |
| 3274 |
* It'll continue to hold whatever pins were held before calling here. |
| 3275 |
* |
| 3276 |
* We match items by heap TID before assuming they are the right ones to set |
| 3277 |
* LP_DEAD. If the scan is one that holds a buffer pin on the target page |
| 3278 |
* continuously from initially reading the items until applying this function |
| 3279 |
* (if it is a !so->dropPin scan), VACUUM cannot have deleted any items on the |
| 3280 |
* page, so the page's TIDs can't have been recycled by now. There's no risk |
| 3281 |
* that we'll confuse a new index tuple that happens to use a recycled TID |
| 3282 |
* with a now-removed tuple with the same TID (that used to be on this same |
| 3283 |
* page). We can't rely on that during scans that drop buffer pins eagerly |
| 3284 |
* (so->dropPin scans), though, so we must condition setting LP_DEAD bits on |
| 3285 |
* the page LSN having not changed since back when _bt_readpage saw the page. |
| 3286 |
* We totally give up on setting LP_DEAD bits when the page LSN changed. |
| 3287 |
* |
| 3288 |
* We give up much less often during !so->dropPin scans, but it still happens. |
| 3289 |
* We cope with cases where items have moved right due to insertions. If an |
| 3290 |
* item has moved off the current page due to a split, we'll fail to find it |
| 3291 |
* and just give up on it. |
| 3292 |
*/ |
| 3293 |
void |
| 3294 |
_bt_killitems(IndexScanDesc scan) |
| 3295 |
{ |
| 3296 |
Relation rel = scan->indexRelation; |
| 3297 |
BTScanOpaque so = (BTScanOpaque) scan->opaque; |
| 3298 |
Page page; |
| 3299 |
BTPageOpaque opaque; |
| 3300 |
OffsetNumber minoff; |
| 3301 |
OffsetNumber maxoff; |
| 3302 |
int numKilled = so->numKilled; |
| 3303 |
bool killedsomething = false; |
| 3304 |
Buffer buf; |
| 3305 |
|
| 3306 |
Assert(numKilled > 0); |
| 3307 |
Assert(BTScanPosIsValid(so->currPos)); |
| 3308 |
Assert(scan->heapRelation != NULL); /* can't be a bitmap index scan */ |
| 3309 |
|
| 3310 |
/* Always invalidate so->killedItems[] before leaving so->currPos */ |
| 3311 |
so->numKilled = 0; |
| 3312 |
|
| 3313 |
if (!so->dropPin) |
| 3314 |
{ |
| 3315 |
/* |
| 3316 |
* We have held the pin on this page since we read the index tuples, |
| 3317 |
* so all we need to do is lock it. The pin will have prevented |
| 3318 |
* concurrent VACUUMs from recycling any of the TIDs on the page. |
| 3319 |
*/ |
| 3320 |
Assert(BTScanPosIsPinned(so->currPos)); |
| 3321 |
buf = so->currPos.buf; |
| 3322 |
_bt_lockbuf(rel, buf, BT_READ); |
| 3323 |
} |
| 3324 |
else |
| 3325 |
{ |
| 3326 |
XLogRecPtr latestlsn; |
| 3327 |
|
| 3328 |
Assert(!BTScanPosIsPinned(so->currPos)); |
| 3329 |
Assert(RelationNeedsWAL(rel)); |
| 3330 |
buf = _bt_getbuf(rel, so->currPos.currPage, BT_READ); |
| 3331 |
|
| 3332 |
latestlsn = BufferGetLSNAtomic(buf); |
| 3333 |
Assert(so->currPos.lsn <= latestlsn); |
| 3334 |
if (so->currPos.lsn != latestlsn) |
| 3335 |
{ |
| 3336 |
/* Modified, give up on hinting */ |
| 3337 |
_bt_relbuf(rel, buf); |
| 3338 |
return; |
| 3339 |
} |
| 3340 |
|
| 3341 |
/* Unmodified, hinting is safe */ |
| 3342 |
} |
| 3343 |
|
| 3344 |
page = BufferGetPage(buf); |
| 3345 |
opaque = BTPageGetOpaque(page); |
| 3346 |
minoff = P_FIRSTDATAKEY(opaque); |
| 3347 |
maxoff = PageGetMaxOffsetNumber(page); |
| 3348 |
|
| 3349 |
for (int i = 0; i < numKilled; i++) |
| 3350 |
{ |
| 3351 |
int itemIndex = so->killedItems[i]; |
| 3352 |
BTScanPosItem *kitem = &so->currPos.items[itemIndex]; |
| 3353 |
OffsetNumber offnum = kitem->indexOffset; |
| 3354 |
|
| 3355 |
Assert(itemIndex >= so->currPos.firstItem && |
| 3356 |
itemIndex <= so->currPos.lastItem); |
| 3357 |
if (offnum < minoff) |
| 3358 |
continue; /* pure paranoia */ |
| 3359 |
while (offnum <= maxoff) |
| 3360 |
{ |
| 3361 |
ItemId iid = PageGetItemId(page, offnum); |
| 3362 |
IndexTuple ituple = (IndexTuple) PageGetItem(page, iid); |
| 3363 |
bool killtuple = false; |
| 3364 |
|
| 3365 |
if (BTreeTupleIsPosting(ituple)) |
| 3366 |
{ |
| 3367 |
int pi = i + 1; |
| 3368 |
int nposting = BTreeTupleGetNPosting(ituple); |
| 3369 |
int j; |
| 3370 |
|
| 3371 |
/* |
| 3372 |
* We rely on the convention that heap TIDs in the scanpos |
| 3373 |
* items array are stored in ascending heap TID order for a |
| 3374 |
* group of TIDs that originally came from a posting list |
| 3375 |
* tuple. This convention even applies during backwards |
| 3376 |
* scans, where returning the TIDs in descending order might |
| 3377 |
* seem more natural. This is about effectiveness, not |
| 3378 |
* correctness. |
| 3379 |
* |
| 3380 |
* Note that the page may have been modified in almost any way |
| 3381 |
* since we first read it (in the !so->dropPin case), so it's |
| 3382 |
* possible that this posting list tuple wasn't a posting list |
| 3383 |
* tuple when we first encountered its heap TIDs. |
| 3384 |
*/ |
| 3385 |
for (j = 0; j < nposting; j++) |
| 3386 |
{ |
| 3387 |
ItemPointer item = BTreeTupleGetPostingN(ituple, j); |
| 3388 |
|
| 3389 |
if (!ItemPointerEquals(item, &kitem->heapTid)) |
| 3390 |
break; /* out of posting list loop */ |
| 3391 |
|
| 3392 |
/* |
| 3393 |
* kitem must have matching offnum when heap TIDs match, |
| 3394 |
* though only in the common case where the page can't |
| 3395 |
* have been concurrently modified |
| 3396 |
*/ |
| 3397 |
Assert(kitem->indexOffset == offnum || !so->dropPin); |
| 3398 |
|
| 3399 |
/* |
| 3400 |
* Read-ahead to later kitems here. |
| 3401 |
* |
| 3402 |
* We rely on the assumption that not advancing kitem here |
| 3403 |
* will prevent us from considering the posting list tuple |
| 3404 |
* fully dead by not matching its next heap TID in next |
| 3405 |
* loop iteration. |
| 3406 |
* |
| 3407 |
* If, on the other hand, this is the final heap TID in |
| 3408 |
* the posting list tuple, then tuple gets killed |
| 3409 |
* regardless (i.e. we handle the case where the last |
| 3410 |
* kitem is also the last heap TID in the last index tuple |
| 3411 |
* correctly -- posting tuple still gets killed). |
| 3412 |
*/ |
| 3413 |
if (pi < numKilled) |
| 3414 |
kitem = &so->currPos.items[so->killedItems[pi++]]; |
| 3415 |
} |
| 3416 |
|
| 3417 |
/* |
| 3418 |
* Don't bother advancing the outermost loop's int iterator to |
| 3419 |
* avoid processing killed items that relate to the same |
| 3420 |
* offnum/posting list tuple. This micro-optimization hardly |
| 3421 |
* seems worth it. (Further iterations of the outermost loop |
| 3422 |
* will fail to match on this same posting list's first heap |
| 3423 |
* TID instead, so we'll advance to the next offnum/index |
| 3424 |
* tuple pretty quickly.) |
| 3425 |
*/ |
| 3426 |
if (j == nposting) |
| 3427 |
killtuple = true; |
| 3428 |
} |
| 3429 |
else if (ItemPointerEquals(&ituple->t_tid, &kitem->heapTid)) |
| 3430 |
killtuple = true; |
| 3431 |
|
| 3432 |
/* |
| 3433 |
* Mark index item as dead, if it isn't already. Since this |
| 3434 |
* happens while holding a buffer lock possibly in shared mode, |
| 3435 |
* it's possible that multiple processes attempt to do this |
| 3436 |
* simultaneously, leading to multiple full-page images being sent |
| 3437 |
* to WAL (if wal_log_hints or data checksums are enabled), which |
| 3438 |
* is undesirable. |
| 3439 |
*/ |
| 3440 |
if (killtuple && !ItemIdIsDead(iid)) |
| 3441 |
{ |
| 3442 |
/* found the item/all posting list items */ |
| 3443 |
ItemIdMarkDead(iid); |
| 3444 |
killedsomething = true; |
| 3445 |
break; /* out of inner search loop */ |
| 3446 |
} |
| 3447 |
offnum = OffsetNumberNext(offnum); |
| 3448 |
} |
| 3449 |
} |
| 3450 |
|
| 3451 |
/* |
| 3452 |
* Since this can be redone later if needed, mark as dirty hint. |
| 3453 |
* |
| 3454 |
* Whenever we mark anything LP_DEAD, we also set the page's |
| 3455 |
* BTP_HAS_GARBAGE flag, which is likewise just a hint. (Note that we |
| 3456 |
* only rely on the page-level flag in !heapkeyspace indexes.) |
| 3457 |
*/ |
| 3458 |
if (killedsomething) |
| 3459 |
{ |
| 3460 |
opaque->btpo_flags |= BTP_HAS_GARBAGE; |
| 3461 |
MarkBufferDirtyHint(buf, true); |
| 3462 |
} |
| 3463 |
|
| 3464 |
if (!so->dropPin) |
| 3465 |
_bt_unlockbuf(rel, buf); |
| 3466 |
else |
| 3467 |
_bt_relbuf(rel, buf); |
| 3468 |
} |
| 3469 |
|
| 3470 |
|
| 3471 |
/* |
| 3472 |
* The following routines manage a shared-memory area in which we track |
| 3473 |
* assignment of "vacuum cycle IDs" to currently-active btree vacuuming |
| 3474 |
* operations. There is a single counter which increments each time we |
| 3475 |
* start a vacuum to assign it a cycle ID. Since multiple vacuums could |
| 3476 |
* be active concurrently, we have to track the cycle ID for each active |
| 3477 |
* vacuum; this requires at most MaxBackends entries (usually far fewer). |
| 3478 |
* We assume at most one vacuum can be active for a given index. |
| 3479 |
* |
| 3480 |
* Access to the shared memory area is controlled by BtreeVacuumLock. |
| 3481 |
* In principle we could use a separate lmgr locktag for each index, |
| 3482 |
* but a single LWLock is much cheaper, and given the short time that |
| 3483 |
* the lock is ever held, the concurrency hit should be minimal. |
| 3484 |
*/ |
| 3485 |
|
| 3486 |
typedef struct BTOneVacInfo |
| 3487 |
{ |
| 3488 |
LockRelId relid; /* global identifier of an index */ |
| 3489 |
BTCycleId cycleid; /* cycle ID for its active VACUUM */ |
| 3490 |
} BTOneVacInfo; |
| 3491 |
|
| 3492 |
typedef struct BTVacInfo |
| 3493 |
{ |
| 3494 |
BTCycleId cycle_ctr; /* cycle ID most recently assigned */ |
| 3495 |
int num_vacuums; /* number of currently active VACUUMs */ |
| 3496 |
int max_vacuums; /* allocated length of vacuums[] array */ |
| 3497 |
BTOneVacInfo vacuums[FLEXIBLE_ARRAY_MEMBER]; |
| 3498 |
} BTVacInfo; |
| 3499 |
|
| 3500 |
static BTVacInfo *btvacinfo; |
| 3501 |
|
| 3502 |
|
| 3503 |
/* |
| 3504 |
* _bt_vacuum_cycleid --- get the active vacuum cycle ID for an index, |
| 3505 |
* or zero if there is no active VACUUM |
| 3506 |
* |
| 3507 |
* Note: for correct interlocking, the caller must already hold pin and |
| 3508 |
* exclusive lock on each buffer it will store the cycle ID into. This |
| 3509 |
* ensures that even if a VACUUM starts immediately afterwards, it cannot |
| 3510 |
* process those pages until the page split is complete. |
| 3511 |
*/ |
| 3512 |
BTCycleId |
| 3513 |
_bt_vacuum_cycleid(Relation rel) |
| 3514 |
{ |
| 3515 |
BTCycleId result = 0; |
| 3516 |
int i; |
| 3517 |
|
| 3518 |
/* Share lock is enough since this is a read-only operation */ |
| 3519 |
LWLockAcquire(BtreeVacuumLock, LW_SHARED); |
| 3520 |
|
| 3521 |
for (i = 0; i < btvacinfo->num_vacuums; i++) |
| 3522 |
{ |
| 3523 |
BTOneVacInfo *vac = &btvacinfo->vacuums[i]; |
| 3524 |
|
| 3525 |
if (vac->relid.relId == rel->rd_lockInfo.lockRelId.relId && |
| 3526 |
vac->relid.dbId == rel->rd_lockInfo.lockRelId.dbId) |
| 3527 |
{ |
| 3528 |
result = vac->cycleid; |
| 3529 |
break; |
| 3530 |
} |
| 3531 |
} |
| 3532 |
|
| 3533 |
LWLockRelease(BtreeVacuumLock); |
| 3534 |
return result; |
| 3535 |
} |
| 3536 |
|
| 3537 |
/* |
| 3538 |
* _bt_start_vacuum --- assign a cycle ID to a just-starting VACUUM operation |
| 3539 |
* |
| 3540 |
* Note: the caller must guarantee that it will eventually call |
| 3541 |
* _bt_end_vacuum, else we'll permanently leak an array slot. To ensure |
| 3542 |
* that this happens even in elog(FATAL) scenarios, the appropriate coding |
| 3543 |
* is not just a PG_TRY, but |
| 3544 |
* PG_ENSURE_ERROR_CLEANUP(_bt_end_vacuum_callback, PointerGetDatum(rel)) |
| 3545 |
*/ |
| 3546 |
BTCycleId |
| 3547 |
_bt_start_vacuum(Relation rel) |
| 3548 |
{ |
| 3549 |
BTCycleId result; |
| 3550 |
int i; |
| 3551 |
BTOneVacInfo *vac; |
| 3552 |
|
| 3553 |
LWLockAcquire(BtreeVacuumLock, LW_EXCLUSIVE); |
| 3554 |
|
| 3555 |
/* |
| 3556 |
* Assign the next cycle ID, being careful to avoid zero as well as the |
| 3557 |
* reserved high values. |
| 3558 |
*/ |
| 3559 |
result = ++(btvacinfo->cycle_ctr); |
| 3560 |
if (result == 0 || result > MAX_BT_CYCLE_ID) |
| 3561 |
result = btvacinfo->cycle_ctr = 1; |
| 3562 |
|
| 3563 |
/* Let's just make sure there's no entry already for this index */ |
| 3564 |
for (i = 0; i < btvacinfo->num_vacuums; i++) |
| 3565 |
{ |
| 3566 |
vac = &btvacinfo->vacuums[i]; |
| 3567 |
if (vac->relid.relId == rel->rd_lockInfo.lockRelId.relId && |
| 3568 |
vac->relid.dbId == rel->rd_lockInfo.lockRelId.dbId) |
| 3569 |
{ |
| 3570 |
/* |
| 3571 |
* Unlike most places in the backend, we have to explicitly |
| 3572 |
* release our LWLock before throwing an error. This is because |
| 3573 |
* we expect _bt_end_vacuum() to be called before transaction |
| 3574 |
* abort cleanup can run to release LWLocks. |
| 3575 |
*/ |
| 3576 |
LWLockRelease(BtreeVacuumLock); |
| 3577 |
elog(ERROR, "multiple active vacuums for index \"%s\"", |
| 3578 |
RelationGetRelationName(rel)); |
| 3579 |
} |
| 3580 |
} |
| 3581 |
|
| 3582 |
/* OK, add an entry */ |
| 3583 |
if (btvacinfo->num_vacuums >= btvacinfo->max_vacuums) |
| 3584 |
{ |
| 3585 |
LWLockRelease(BtreeVacuumLock); |
| 3586 |
elog(ERROR, "out of btvacinfo slots"); |
| 3587 |
} |
| 3588 |
vac = &btvacinfo->vacuums[btvacinfo->num_vacuums]; |
| 3589 |
vac->relid = rel->rd_lockInfo.lockRelId; |
| 3590 |
vac->cycleid = result; |
| 3591 |
btvacinfo->num_vacuums++; |
| 3592 |
|
| 3593 |
LWLockRelease(BtreeVacuumLock); |
| 3594 |
return result; |
| 3595 |
} |
| 3596 |
|
| 3597 |
/* |
| 3598 |
* _bt_end_vacuum --- mark a btree VACUUM operation as done |
| 3599 |
* |
| 3600 |
* Note: this is deliberately coded not to complain if no entry is found; |
| 3601 |
* this allows the caller to put PG_TRY around the start_vacuum operation. |
| 3602 |
*/ |
| 3603 |
void |
| 3604 |
_bt_end_vacuum(Relation rel) |
| 3605 |
{ |
| 3606 |
int i; |
| 3607 |
|
| 3608 |
LWLockAcquire(BtreeVacuumLock, LW_EXCLUSIVE); |
| 3609 |
|
| 3610 |
/* Find the array entry */ |
| 3611 |
for (i = 0; i < btvacinfo->num_vacuums; i++) |
| 3612 |
{ |
| 3613 |
BTOneVacInfo *vac = &btvacinfo->vacuums[i]; |
| 3614 |
|
| 3615 |
if (vac->relid.relId == rel->rd_lockInfo.lockRelId.relId && |
| 3616 |
vac->relid.dbId == rel->rd_lockInfo.lockRelId.dbId) |
| 3617 |
{ |
| 3618 |
/* Remove it by shifting down the last entry */ |
| 3619 |
*vac = btvacinfo->vacuums[btvacinfo->num_vacuums - 1]; |
| 3620 |
btvacinfo->num_vacuums--; |
| 3621 |
break; |
| 3622 |
} |
| 3623 |
} |
| 3624 |
|
| 3625 |
LWLockRelease(BtreeVacuumLock); |
| 3626 |
} |
| 3627 |
|
| 3628 |
/* |
| 3629 |
* _bt_end_vacuum wrapped as an on_shmem_exit callback function |
| 3630 |
*/ |
| 3631 |
void |
| 3632 |
_bt_end_vacuum_callback(int code, Datum arg) |
| 3633 |
{ |
| 3634 |
_bt_end_vacuum((Relation) DatumGetPointer(arg)); |
| 3635 |
} |
| 3636 |
|
| 3637 |
/* |
| 3638 |
* BTreeShmemSize --- report amount of shared memory space needed |
| 3639 |
*/ |
| 3640 |
Size |
| 3641 |
BTreeShmemSize(void) |
| 3642 |
{ |
| 3643 |
Size size; |
| 3644 |
|
| 3645 |
size = offsetof(BTVacInfo, vacuums); |
| 3646 |
size = add_size(size, mul_size(MaxBackends, sizeof(BTOneVacInfo))); |
| 3647 |
return size; |
| 3648 |
} |
| 3649 |
|
| 3650 |
/* |
| 3651 |
* BTreeShmemInit --- initialize this module's shared memory |
| 3652 |
*/ |
| 3653 |
void |
| 3654 |
BTreeShmemInit(void) |
| 3655 |
{ |
| 3656 |
bool found; |
| 3657 |
|
| 3658 |
btvacinfo = (BTVacInfo *) ShmemInitStruct("BTree Vacuum State", |
| 3659 |
BTreeShmemSize(), |
| 3660 |
&found); |
| 3661 |
|
| 3662 |
if (!IsUnderPostmaster) |
| 3663 |
{ |
| 3664 |
/* Initialize shared memory area */ |
| 3665 |
Assert(!found); |
| 3666 |
|
| 3667 |
/* |
| 3668 |
* It doesn't really matter what the cycle counter starts at, but |
| 3669 |
* having it always start the same doesn't seem good. Seed with |
| 3670 |
* low-order bits of time() instead. |
| 3671 |
*/ |
| 3672 |
btvacinfo->cycle_ctr = (BTCycleId) time(NULL); |
| 3673 |
|
| 3674 |
btvacinfo->num_vacuums = 0; |
| 3675 |
btvacinfo->max_vacuums = MaxBackends; |
| 3676 |
} |
| 3677 |
else |
| 3678 |
Assert(found); |
| 3679 |
} |
| 3680 |
|
| 3681 |
bytea * |
| 3682 |
btoptions(Datum reloptions, bool validate) |
| 3683 |
{ |
| 3684 |
static const relopt_parse_elt tab[] = { |
| 3685 |
{"fillfactor", RELOPT_TYPE_INT, offsetof(BTOptions, fillfactor)}, |
| 3686 |
{"vacuum_cleanup_index_scale_factor", RELOPT_TYPE_REAL, |
| 3687 |
offsetof(BTOptions, vacuum_cleanup_index_scale_factor)}, |
| 3688 |
{"deduplicate_items", RELOPT_TYPE_BOOL, |
| 3689 |
offsetof(BTOptions, deduplicate_items)} |
| 3690 |
}; |
| 3691 |
|
| 3692 |
return (bytea *) build_reloptions(reloptions, validate, |
| 3693 |
RELOPT_KIND_BTREE, |
| 3694 |
sizeof(BTOptions), |
| 3695 |
tab, lengthof(tab)); |
| 3696 |
} |
| 3697 |
|
| 3698 |
/* |
| 3699 |
* btproperty() -- Check boolean properties of indexes. |
| 3700 |
* |
| 3701 |
* This is optional, but handling AMPROP_RETURNABLE here saves opening the rel |
| 3702 |
* to call btcanreturn. |
| 3703 |
*/ |
| 3704 |
bool |
| 3705 |
btproperty(Oid index_oid, int attno, |
| 3706 |
IndexAMProperty prop, const char *propname, |
| 3707 |
bool *res, bool *isnull) |
| 3708 |
{ |
| 3709 |
switch (prop) |
| 3710 |
{ |
| 3711 |
case AMPROP_RETURNABLE: |
| 3712 |
/* answer only for columns, not AM or whole index */ |
| 3713 |
if (attno == 0) |
| 3714 |
return false; |
| 3715 |
/* otherwise, btree can always return data */ |
| 3716 |
*res = true; |
| 3717 |
return true; |
| 3718 |
|
| 3719 |
default: |
| 3720 |
return false; /* punt to generic code */ |
| 3721 |
} |
| 3722 |
} |
| 3723 |
|
| 3724 |
/* |
| 3725 |
* btbuildphasename() -- Return name of index build phase. |
| 3726 |
*/ |
| 3727 |
char * |
| 3728 |
btbuildphasename(int64 phasenum) |
| 3729 |
{ |
| 3730 |
switch (phasenum) |
| 3731 |
{ |
| 3732 |
case PROGRESS_CREATEIDX_SUBPHASE_INITIALIZE: |
| 3733 |
return "initializing"; |
| 3734 |
case PROGRESS_BTREE_PHASE_INDEXBUILD_TABLESCAN: |
| 3735 |
return "scanning table"; |
| 3736 |
case PROGRESS_BTREE_PHASE_PERFORMSORT_1: |
| 3737 |
return "sorting live tuples"; |
| 3738 |
case PROGRESS_BTREE_PHASE_PERFORMSORT_2: |
| 3739 |
return "sorting dead tuples"; |
| 3740 |
case PROGRESS_BTREE_PHASE_LEAF_LOAD: |
| 3741 |
return "loading tuples in tree"; |
| 3742 |
default: |
| 3743 |
return NULL; |
| 3744 |
} |
| 3745 |
} |
| 3746 |
|
| 3747 |
/* |
| 3748 |
* _bt_truncate() -- create tuple without unneeded suffix attributes. |
| 3749 |
* |
| 3750 |
* Returns truncated pivot index tuple allocated in caller's memory context, |
| 3751 |
* with key attributes copied from caller's firstright argument. If rel is |
| 3752 |
* an INCLUDE index, non-key attributes will definitely be truncated away, |
| 3753 |
* since they're not part of the key space. More aggressive suffix |
| 3754 |
* truncation can take place when it's clear that the returned tuple does not |
| 3755 |
* need one or more suffix key attributes. We only need to keep firstright |
| 3756 |
* attributes up to and including the first non-lastleft-equal attribute. |
| 3757 |
* Caller's insertion scankey is used to compare the tuples; the scankey's |
| 3758 |
* argument values are not considered here. |
| 3759 |
* |
| 3760 |
* Note that returned tuple's t_tid offset will hold the number of attributes |
| 3761 |
* present, so the original item pointer offset is not represented. Caller |
| 3762 |
* should only change truncated tuple's downlink. Note also that truncated |
| 3763 |
* key attributes are treated as containing "minus infinity" values by |
| 3764 |
* _bt_compare(). |
| 3765 |
* |
| 3766 |
* In the worst case (when a heap TID must be appended to distinguish lastleft |
| 3767 |
* from firstright), the size of the returned tuple is the size of firstright |
| 3768 |
* plus the size of an additional MAXALIGN()'d item pointer. This guarantee |
| 3769 |
* is important, since callers need to stay under the 1/3 of a page |
| 3770 |
* restriction on tuple size. If this routine is ever taught to truncate |
| 3771 |
* within an attribute/datum, it will need to avoid returning an enlarged |
| 3772 |
* tuple to caller when truncation + TOAST compression ends up enlarging the |
| 3773 |
* final datum. |
| 3774 |
*/ |
| 3775 |
IndexTuple |
| 3776 |
_bt_truncate(Relation rel, IndexTuple lastleft, IndexTuple firstright, |
| 3777 |
BTScanInsert itup_key) |
| 3778 |
{ |
| 3779 |
TupleDesc itupdesc = RelationGetDescr(rel); |
| 3780 |
int16 nkeyatts = IndexRelationGetNumberOfKeyAttributes(rel); |
| 3781 |
int keepnatts; |
| 3782 |
IndexTuple pivot; |
| 3783 |
IndexTuple tidpivot; |
| 3784 |
ItemPointer pivotheaptid; |
| 3785 |
Size newsize; |
| 3786 |
|
| 3787 |
/* |
| 3788 |
* We should only ever truncate non-pivot tuples from leaf pages. It's |
| 3789 |
* never okay to truncate when splitting an internal page. |
| 3790 |
*/ |
| 3791 |
Assert(!BTreeTupleIsPivot(lastleft) && !BTreeTupleIsPivot(firstright)); |
| 3792 |
|
| 3793 |
/* Determine how many attributes must be kept in truncated tuple */ |
| 3794 |
keepnatts = _bt_keep_natts(rel, lastleft, firstright, itup_key); |
| 3795 |
|
| 3796 |
#ifdef DEBUG_NO_TRUNCATE |
| 3797 |
/* Force truncation to be ineffective for testing purposes */ |
| 3798 |
keepnatts = nkeyatts + 1; |
| 3799 |
#endif |
| 3800 |
|
| 3801 |
pivot = index_truncate_tuple(itupdesc, firstright, |
| 3802 |
Min(keepnatts, nkeyatts)); |
| 3803 |
|
| 3804 |
if (BTreeTupleIsPosting(pivot)) |
| 3805 |
{ |
| 3806 |
/* |
| 3807 |
* index_truncate_tuple() just returns a straight copy of firstright |
| 3808 |
* when it has no attributes to truncate. When that happens, we may |
| 3809 |
* need to truncate away a posting list here instead. |
| 3810 |
*/ |
| 3811 |
Assert(keepnatts == nkeyatts || keepnatts == nkeyatts + 1); |
| 3812 |
Assert(IndexRelationGetNumberOfAttributes(rel) == nkeyatts); |
| 3813 |
pivot->t_info &= ~INDEX_SIZE_MASK; |
| 3814 |
pivot->t_info |= MAXALIGN(BTreeTupleGetPostingOffset(firstright)); |
| 3815 |
} |
| 3816 |
|
| 3817 |
/* |
| 3818 |
* If there is a distinguishing key attribute within pivot tuple, we're |
| 3819 |
* done |
| 3820 |
*/ |
| 3821 |
if (keepnatts <= nkeyatts) |
| 3822 |
{ |
| 3823 |
BTreeTupleSetNAtts(pivot, keepnatts, false); |
| 3824 |
return pivot; |
| 3825 |
} |
| 3826 |
|
| 3827 |
/* |
| 3828 |
* We have to store a heap TID in the new pivot tuple, since no non-TID |
| 3829 |
* key attribute value in firstright distinguishes the right side of the |
| 3830 |
* split from the left side. nbtree conceptualizes this case as an |
| 3831 |
* inability to truncate away any key attributes, since heap TID is |
| 3832 |
* treated as just another key attribute (despite lacking a pg_attribute |
| 3833 |
* entry). |
| 3834 |
* |
| 3835 |
* Use enlarged space that holds a copy of pivot. We need the extra space |
| 3836 |
* to store a heap TID at the end (using the special pivot tuple |
| 3837 |
* representation). Note that the original pivot already has firstright's |
| 3838 |
* possible posting list/non-key attribute values removed at this point. |
| 3839 |
*/ |
| 3840 |
newsize = MAXALIGN(IndexTupleSize(pivot)) + MAXALIGN(sizeof(ItemPointerData)); |
| 3841 |
tidpivot = palloc0(newsize); |
| 3842 |
memcpy(tidpivot, pivot, MAXALIGN(IndexTupleSize(pivot))); |
| 3843 |
/* Cannot leak memory here */ |
| 3844 |
pfree(pivot); |
| 3845 |
|
| 3846 |
/* |
| 3847 |
* Store all of firstright's key attribute values plus a tiebreaker heap |
| 3848 |
* TID value in enlarged pivot tuple |
| 3849 |
*/ |
| 3850 |
tidpivot->t_info &= ~INDEX_SIZE_MASK; |
| 3851 |
tidpivot->t_info |= newsize; |
| 3852 |
BTreeTupleSetNAtts(tidpivot, nkeyatts, true); |
| 3853 |
pivotheaptid = BTreeTupleGetHeapTID(tidpivot); |
| 3854 |
|
| 3855 |
/* |
| 3856 |
* Lehman & Yao use lastleft as the leaf high key in all cases, but don't |
| 3857 |
* consider suffix truncation. It seems like a good idea to follow that |
| 3858 |
* example in cases where no truncation takes place -- use lastleft's heap |
| 3859 |
* TID. (This is also the closest value to negative infinity that's |
| 3860 |
* legally usable.) |
| 3861 |
*/ |
| 3862 |
ItemPointerCopy(BTreeTupleGetMaxHeapTID(lastleft), pivotheaptid); |
| 3863 |
|
| 3864 |
/* |
| 3865 |
* We're done. Assert() that heap TID invariants hold before returning. |
| 3866 |
* |
| 3867 |
* Lehman and Yao require that the downlink to the right page, which is to |
| 3868 |
* be inserted into the parent page in the second phase of a page split be |
| 3869 |
* a strict lower bound on items on the right page, and a non-strict upper |
| 3870 |
* bound for items on the left page. Assert that heap TIDs follow these |
| 3871 |
* invariants, since a heap TID value is apparently needed as a |
| 3872 |
* tiebreaker. |
| 3873 |
*/ |
| 3874 |
#ifndef DEBUG_NO_TRUNCATE |
| 3875 |
Assert(ItemPointerCompare(BTreeTupleGetMaxHeapTID(lastleft), |
| 3876 |
BTreeTupleGetHeapTID(firstright)) < 0); |
| 3877 |
Assert(ItemPointerCompare(pivotheaptid, |
| 3878 |
BTreeTupleGetHeapTID(lastleft)) >= 0); |
| 3879 |
Assert(ItemPointerCompare(pivotheaptid, |
| 3880 |
BTreeTupleGetHeapTID(firstright)) < 0); |
| 3881 |
#else |
| 3882 |
|
| 3883 |
/* |
| 3884 |
* Those invariants aren't guaranteed to hold for lastleft + firstright |
| 3885 |
* heap TID attribute values when they're considered here only because |
| 3886 |
* DEBUG_NO_TRUNCATE is defined (a heap TID is probably not actually |
| 3887 |
* needed as a tiebreaker). DEBUG_NO_TRUNCATE must therefore use a heap |
| 3888 |
* TID value that always works as a strict lower bound for items to the |
| 3889 |
* right. In particular, it must avoid using firstright's leading key |
| 3890 |
* attribute values along with lastleft's heap TID value when lastleft's |
| 3891 |
* TID happens to be greater than firstright's TID. |
| 3892 |
*/ |
| 3893 |
ItemPointerCopy(BTreeTupleGetHeapTID(firstright), pivotheaptid); |
| 3894 |
|
| 3895 |
/* |
| 3896 |
* Pivot heap TID should never be fully equal to firstright. Note that |
| 3897 |
* the pivot heap TID will still end up equal to lastleft's heap TID when |
| 3898 |
* that's the only usable value. |
| 3899 |
*/ |
| 3900 |
ItemPointerSetOffsetNumber(pivotheaptid, |
| 3901 |
OffsetNumberPrev(ItemPointerGetOffsetNumber(pivotheaptid))); |
| 3902 |
Assert(ItemPointerCompare(pivotheaptid, |
| 3903 |
BTreeTupleGetHeapTID(firstright)) < 0); |
| 3904 |
#endif |
| 3905 |
|
| 3906 |
return tidpivot; |
| 3907 |
} |
| 3908 |
|
| 3909 |
/* |
| 3910 |
* _bt_keep_natts - how many key attributes to keep when truncating. |
| 3911 |
* |
| 3912 |
* Caller provides two tuples that enclose a split point. Caller's insertion |
| 3913 |
* scankey is used to compare the tuples; the scankey's argument values are |
| 3914 |
* not considered here. |
| 3915 |
* |
| 3916 |
* This can return a number of attributes that is one greater than the |
| 3917 |
* number of key attributes for the index relation. This indicates that the |
| 3918 |
* caller must use a heap TID as a unique-ifier in new pivot tuple. |
| 3919 |
*/ |
| 3920 |
static int |
| 3921 |
_bt_keep_natts(Relation rel, IndexTuple lastleft, IndexTuple firstright, |
| 3922 |
BTScanInsert itup_key) |
| 3923 |
{ |
| 3924 |
int nkeyatts = IndexRelationGetNumberOfKeyAttributes(rel); |
| 3925 |
TupleDesc itupdesc = RelationGetDescr(rel); |
| 3926 |
int keepnatts; |
| 3927 |
ScanKey scankey; |
| 3928 |
|
| 3929 |
/* |
| 3930 |
* _bt_compare() treats truncated key attributes as having the value minus |
| 3931 |
* infinity, which would break searches within !heapkeyspace indexes. We |
| 3932 |
* must still truncate away non-key attribute values, though. |
| 3933 |
*/ |
| 3934 |
if (!itup_key->heapkeyspace) |
| 3935 |
return nkeyatts; |
| 3936 |
|
| 3937 |
scankey = itup_key->scankeys; |
| 3938 |
keepnatts = 1; |
| 3939 |
for (int attnum = 1; attnum <= nkeyatts; attnum++, scankey++) |
| 3940 |
{ |
| 3941 |
Datum datum1, |
| 3942 |
datum2; |
| 3943 |
bool isNull1, |
| 3944 |
isNull2; |
| 3945 |
|
| 3946 |
datum1 = index_getattr(lastleft, attnum, itupdesc, &isNull1); |
| 3947 |
datum2 = index_getattr(firstright, attnum, itupdesc, &isNull2); |
| 3948 |
|
| 3949 |
if (isNull1 != isNull2) |
| 3950 |
break; |
| 3951 |
|
| 3952 |
if (!isNull1 && |
| 3953 |
DatumGetInt32(FunctionCall2Coll(&scankey->sk_func, |
| 3954 |
scankey->sk_collation, |
| 3955 |
datum1, |
| 3956 |
datum2)) != 0) |
| 3957 |
break; |
| 3958 |
|
| 3959 |
keepnatts++; |
| 3960 |
} |
| 3961 |
|
| 3962 |
/* |
| 3963 |
* Assert that _bt_keep_natts_fast() agrees with us in passing. This is |
| 3964 |
* expected in an allequalimage index. |
| 3965 |
*/ |
| 3966 |
Assert(!itup_key->allequalimage || |
| 3967 |
keepnatts == _bt_keep_natts_fast(rel, lastleft, firstright)); |
| 3968 |
|
| 3969 |
return keepnatts; |
| 3970 |
} |
| 3971 |
|
| 3972 |
/* |
| 3973 |
* _bt_keep_natts_fast - fast bitwise variant of _bt_keep_natts. |
| 3974 |
* |
| 3975 |
* This is exported so that a candidate split point can have its effect on |
| 3976 |
* suffix truncation inexpensively evaluated ahead of time when finding a |
| 3977 |
* split location. A naive bitwise approach to datum comparisons is used to |
| 3978 |
* save cycles. |
| 3979 |
* |
| 3980 |
* The approach taken here usually provides the same answer as _bt_keep_natts |
| 3981 |
* will (for the same pair of tuples from a heapkeyspace index), since the |
| 3982 |
* majority of btree opclasses can never indicate that two datums are equal |
| 3983 |
* unless they're bitwise equal after detoasting. When an index only has |
| 3984 |
* "equal image" columns, routine is guaranteed to give the same result as |
| 3985 |
* _bt_keep_natts would. |
| 3986 |
* |
| 3987 |
* Callers can rely on the fact that attributes considered equal here are |
| 3988 |
* definitely also equal according to _bt_keep_natts, even when the index uses |
| 3989 |
* an opclass or collation that is not "allequalimage"/deduplication-safe. |
| 3990 |
* This weaker guarantee is good enough for nbtsplitloc.c caller, since false |
| 3991 |
* negatives generally only have the effect of making leaf page splits use a |
| 3992 |
* more balanced split point. |
| 3993 |
*/ |
| 3994 |
int |
| 3995 |
_bt_keep_natts_fast(Relation rel, IndexTuple lastleft, IndexTuple firstright) |
| 3996 |
{ |
| 3997 |
TupleDesc itupdesc = RelationGetDescr(rel); |
| 3998 |
int keysz = IndexRelationGetNumberOfKeyAttributes(rel); |
| 3999 |
int keepnatts; |
| 4000 |
|
| 4001 |
keepnatts = 1; |
| 4002 |
for (int attnum = 1; attnum <= keysz; attnum++) |
| 4003 |
{ |
| 4004 |
Datum datum1, |
| 4005 |
datum2; |
| 4006 |
bool isNull1, |
| 4007 |
isNull2; |
| 4008 |
CompactAttribute *att; |
| 4009 |
|
| 4010 |
datum1 = index_getattr(lastleft, attnum, itupdesc, &isNull1); |
| 4011 |
datum2 = index_getattr(firstright, attnum, itupdesc, &isNull2); |
| 4012 |
att = TupleDescCompactAttr(itupdesc, attnum - 1); |
| 4013 |
|
| 4014 |
if (isNull1 != isNull2) |
| 4015 |
break; |
| 4016 |
|
| 4017 |
if (!isNull1 && |
| 4018 |
!datum_image_eq(datum1, datum2, att->attbyval, att->attlen)) |
| 4019 |
break; |
| 4020 |
|
| 4021 |
keepnatts++; |
| 4022 |
} |
| 4023 |
|
| 4024 |
return keepnatts; |
| 4025 |
} |
| 4026 |
|
| 4027 |
/* |
| 4028 |
* _bt_check_natts() -- Verify tuple has expected number of attributes. |
| 4029 |
* |
| 4030 |
* Returns value indicating if the expected number of attributes were found |
| 4031 |
* for a particular offset on page. This can be used as a general purpose |
| 4032 |
* sanity check. |
| 4033 |
* |
| 4034 |
* Testing a tuple directly with BTreeTupleGetNAtts() should generally be |
| 4035 |
* preferred to calling here. That's usually more convenient, and is always |
| 4036 |
* more explicit. Call here instead when offnum's tuple may be a negative |
| 4037 |
* infinity tuple that uses the pre-v11 on-disk representation, or when a low |
| 4038 |
* context check is appropriate. This routine is as strict as possible about |
| 4039 |
* what is expected on each version of btree. |
| 4040 |
*/ |
| 4041 |
bool |
| 4042 |
_bt_check_natts(Relation rel, bool heapkeyspace, Page page, OffsetNumber offnum) |
| 4043 |
{ |
| 4044 |
int16 natts = IndexRelationGetNumberOfAttributes(rel); |
| 4045 |
int16 nkeyatts = IndexRelationGetNumberOfKeyAttributes(rel); |
| 4046 |
BTPageOpaque opaque = BTPageGetOpaque(page); |
| 4047 |
IndexTuple itup; |
| 4048 |
int tupnatts; |
| 4049 |
|
| 4050 |
/* |
| 4051 |
* We cannot reliably test a deleted or half-dead page, since they have |
| 4052 |
* dummy high keys |
| 4053 |
*/ |
| 4054 |
if (P_IGNORE(opaque)) |
| 4055 |
return true; |
| 4056 |
|
| 4057 |
Assert(offnum >= FirstOffsetNumber && |
| 4058 |
offnum <= PageGetMaxOffsetNumber(page)); |
| 4059 |
|
| 4060 |
itup = (IndexTuple) PageGetItem(page, PageGetItemId(page, offnum)); |
| 4061 |
tupnatts = BTreeTupleGetNAtts(itup, rel); |
| 4062 |
|
| 4063 |
/* !heapkeyspace indexes do not support deduplication */ |
| 4064 |
if (!heapkeyspace && BTreeTupleIsPosting(itup)) |
| 4065 |
return false; |
| 4066 |
|
| 4067 |
/* Posting list tuples should never have "pivot heap TID" bit set */ |
| 4068 |
if (BTreeTupleIsPosting(itup) && |
| 4069 |
(ItemPointerGetOffsetNumberNoCheck(&itup->t_tid) & |
| 4070 |
BT_PIVOT_HEAP_TID_ATTR) != 0) |
| 4071 |
return false; |
| 4072 |
|
| 4073 |
/* INCLUDE indexes do not support deduplication */ |
| 4074 |
if (natts != nkeyatts && BTreeTupleIsPosting(itup)) |
| 4075 |
return false; |
| 4076 |
|
| 4077 |
if (P_ISLEAF(opaque)) |
| 4078 |
{ |
| 4079 |
if (offnum >= P_FIRSTDATAKEY(opaque)) |
| 4080 |
{ |
| 4081 |
/* |
| 4082 |
* Non-pivot tuple should never be explicitly marked as a pivot |
| 4083 |
* tuple |
| 4084 |
*/ |
| 4085 |
if (BTreeTupleIsPivot(itup)) |
| 4086 |
return false; |
| 4087 |
|
| 4088 |
/* |
| 4089 |
* Leaf tuples that are not the page high key (non-pivot tuples) |
| 4090 |
* should never be truncated. (Note that tupnatts must have been |
| 4091 |
* inferred, even with a posting list tuple, because only pivot |
| 4092 |
* tuples store tupnatts directly.) |
| 4093 |
*/ |
| 4094 |
return tupnatts == natts; |
| 4095 |
} |
| 4096 |
else |
| 4097 |
{ |
| 4098 |
/* |
| 4099 |
* Rightmost page doesn't contain a page high key, so tuple was |
| 4100 |
* checked above as ordinary leaf tuple |
| 4101 |
*/ |
| 4102 |
Assert(!P_RIGHTMOST(opaque)); |
| 4103 |
|
| 4104 |
/* |
| 4105 |
* !heapkeyspace high key tuple contains only key attributes. Note |
| 4106 |
* that tupnatts will only have been explicitly represented in |
| 4107 |
* !heapkeyspace indexes that happen to have non-key attributes. |
| 4108 |
*/ |
| 4109 |
if (!heapkeyspace) |
| 4110 |
return tupnatts == nkeyatts; |
| 4111 |
|
| 4112 |
/* Use generic heapkeyspace pivot tuple handling */ |
| 4113 |
} |
| 4114 |
} |
| 4115 |
else /* !P_ISLEAF(opaque) */ |
| 4116 |
{ |
| 4117 |
if (offnum == P_FIRSTDATAKEY(opaque)) |
| 4118 |
{ |
| 4119 |
/* |
| 4120 |
* The first tuple on any internal page (possibly the first after |
| 4121 |
* its high key) is its negative infinity tuple. Negative |
| 4122 |
* infinity tuples are always truncated to zero attributes. They |
| 4123 |
* are a particular kind of pivot tuple. |
| 4124 |
*/ |
| 4125 |
if (heapkeyspace) |
| 4126 |
return tupnatts == 0; |
| 4127 |
|
| 4128 |
/* |
| 4129 |
* The number of attributes won't be explicitly represented if the |
| 4130 |
* negative infinity tuple was generated during a page split that |
| 4131 |
* occurred with a version of Postgres before v11. There must be |
| 4132 |
* a problem when there is an explicit representation that is |
| 4133 |
* non-zero, or when there is no explicit representation and the |
| 4134 |
* tuple is evidently not a pre-pg_upgrade tuple. |
| 4135 |
* |
| 4136 |
* Prior to v11, downlinks always had P_HIKEY as their offset. |
| 4137 |
* Accept that as an alternative indication of a valid |
| 4138 |
* !heapkeyspace negative infinity tuple. |
| 4139 |
*/ |
| 4140 |
return tupnatts == 0 || |
| 4141 |
ItemPointerGetOffsetNumber(&(itup->t_tid)) == P_HIKEY; |
| 4142 |
} |
| 4143 |
else |
| 4144 |
{ |
| 4145 |
/* |
| 4146 |
* !heapkeyspace downlink tuple with separator key contains only |
| 4147 |
* key attributes. Note that tupnatts will only have been |
| 4148 |
* explicitly represented in !heapkeyspace indexes that happen to |
| 4149 |
* have non-key attributes. |
| 4150 |
*/ |
| 4151 |
if (!heapkeyspace) |
| 4152 |
return tupnatts == nkeyatts; |
| 4153 |
|
| 4154 |
/* Use generic heapkeyspace pivot tuple handling */ |
| 4155 |
} |
| 4156 |
} |
| 4157 |
|
| 4158 |
/* Handle heapkeyspace pivot tuples (excluding minus infinity items) */ |
| 4159 |
Assert(heapkeyspace); |
| 4160 |
|
| 4161 |
/* |
| 4162 |
* Explicit representation of the number of attributes is mandatory with |
| 4163 |
* heapkeyspace index pivot tuples, regardless of whether or not there are |
| 4164 |
* non-key attributes. |
| 4165 |
*/ |
| 4166 |
if (!BTreeTupleIsPivot(itup)) |
| 4167 |
return false; |
| 4168 |
|
| 4169 |
/* Pivot tuple should not use posting list representation (redundant) */ |
| 4170 |
if (BTreeTupleIsPosting(itup)) |
| 4171 |
return false; |
| 4172 |
|
| 4173 |
/* |
| 4174 |
* Heap TID is a tiebreaker key attribute, so it cannot be untruncated |
| 4175 |
* when any other key attribute is truncated |
| 4176 |
*/ |
| 4177 |
if (BTreeTupleGetHeapTID(itup) != NULL && tupnatts != nkeyatts) |
| 4178 |
return false; |
| 4179 |
|
| 4180 |
/* |
| 4181 |
* Pivot tuple must have at least one untruncated key attribute (minus |
| 4182 |
* infinity pivot tuples are the only exception). Pivot tuples can never |
| 4183 |
* represent that there is a value present for a key attribute that |
| 4184 |
* exceeds pg_index.indnkeyatts for the index. |
| 4185 |
*/ |
| 4186 |
return tupnatts > 0 && tupnatts <= nkeyatts; |
| 4187 |
} |
| 4188 |
|
| 4189 |
/* |
| 4190 |
* |
| 4191 |
* _bt_check_third_page() -- check whether tuple fits on a btree page at all. |
| 4192 |
* |
| 4193 |
* We actually need to be able to fit three items on every page, so restrict |
| 4194 |
* any one item to 1/3 the per-page available space. Note that itemsz should |
| 4195 |
* not include the ItemId overhead. |
| 4196 |
* |
| 4197 |
* It might be useful to apply TOAST methods rather than throw an error here. |
| 4198 |
* Using out of line storage would break assumptions made by suffix truncation |
| 4199 |
* and by contrib/amcheck, though. |
| 4200 |
*/ |
| 4201 |
void |
| 4202 |
_bt_check_third_page(Relation rel, Relation heap, bool needheaptidspace, |
| 4203 |
Page page, IndexTuple newtup) |
| 4204 |
{ |
| 4205 |
Size itemsz; |
| 4206 |
BTPageOpaque opaque; |
| 4207 |
|
| 4208 |
itemsz = MAXALIGN(IndexTupleSize(newtup)); |
| 4209 |
|
| 4210 |
/* Double check item size against limit */ |
| 4211 |
if (itemsz <= BTMaxItemSize) |
| 4212 |
return; |
| 4213 |
|
| 4214 |
/* |
| 4215 |
* Tuple is probably too large to fit on page, but it's possible that the |
| 4216 |
* index uses version 2 or version 3, or that page is an internal page, in |
| 4217 |
* which case a slightly higher limit applies. |
| 4218 |
*/ |
| 4219 |
if (!needheaptidspace && itemsz <= BTMaxItemSizeNoHeapTid) |
| 4220 |
return; |
| 4221 |
|
| 4222 |
/* |
| 4223 |
* Internal page insertions cannot fail here, because that would mean that |
| 4224 |
* an earlier leaf level insertion that should have failed didn't |
| 4225 |
*/ |
| 4226 |
opaque = BTPageGetOpaque(page); |
| 4227 |
if (!P_ISLEAF(opaque)) |
| 4228 |
elog(ERROR, "cannot insert oversized tuple of size %zu on internal page of index \"%s\"", |
| 4229 |
itemsz, RelationGetRelationName(rel)); |
| 4230 |
|
| 4231 |
ereport(ERROR, |
| 4232 |
(errcode(ERRCODE_PROGRAM_LIMIT_EXCEEDED), |
| 4233 |
errmsg("index row size %zu exceeds btree version %u maximum %zu for index \"%s\"", |
| 4234 |
itemsz, |
| 4235 |
needheaptidspace ? BTREE_VERSION : BTREE_NOVAC_VERSION, |
| 4236 |
needheaptidspace ? BTMaxItemSize : BTMaxItemSizeNoHeapTid, |
| 4237 |
RelationGetRelationName(rel)), |
| 4238 |
errdetail("Index row references tuple (%u,%u) in relation \"%s\".", |
| 4239 |
ItemPointerGetBlockNumber(BTreeTupleGetHeapTID(newtup)), |
| 4240 |
ItemPointerGetOffsetNumber(BTreeTupleGetHeapTID(newtup)), |
| 4241 |
RelationGetRelationName(heap)), |
| 4242 |
errhint("Values larger than 1/3 of a buffer page cannot be indexed.\n" |
| 4243 |
"Consider a function index of an MD5 hash of the value, " |
| 4244 |
"or use full text indexing."), |
| 4245 |
errtableconstraint(heap, RelationGetRelationName(rel)))); |
| 4246 |
} |
| 4247 |
|
| 4248 |
/* |
| 4249 |
* Are all attributes in rel "equality is image equality" attributes? |
| 4250 |
* |
| 4251 |
* We use each attribute's BTEQUALIMAGE_PROC opclass procedure. If any |
| 4252 |
* opclass either lacks a BTEQUALIMAGE_PROC procedure or returns false, we |
| 4253 |
* return false; otherwise we return true. |
| 4254 |
* |
| 4255 |
* Returned boolean value is stored in index metapage during index builds. |
| 4256 |
* Deduplication can only be used when we return true. |
| 4257 |
*/ |
| 4258 |
bool |
| 4259 |
_bt_allequalimage(Relation rel, bool debugmessage) |
| 4260 |
{ |
| 4261 |
bool allequalimage = true; |
| 4262 |
|
| 4263 |
/* INCLUDE indexes can never support deduplication */ |
| 4264 |
if (IndexRelationGetNumberOfAttributes(rel) != |
| 4265 |
IndexRelationGetNumberOfKeyAttributes(rel)) |
| 4266 |
return false; |
| 4267 |
|
| 4268 |
for (int i = 0; i < IndexRelationGetNumberOfKeyAttributes(rel); i++) |
| 4269 |
{ |
| 4270 |
Oid opfamily = rel->rd_opfamily[i]; |
| 4271 |
Oid opcintype = rel->rd_opcintype[i]; |
| 4272 |
Oid collation = rel->rd_indcollation[i]; |
| 4273 |
Oid equalimageproc; |
| 4274 |
|
| 4275 |
equalimageproc = get_opfamily_proc(opfamily, opcintype, opcintype, |
| 4276 |
BTEQUALIMAGE_PROC); |
| 4277 |
|
| 4278 |
/* |
| 4279 |
* If there is no BTEQUALIMAGE_PROC then deduplication is assumed to |
| 4280 |
* be unsafe. Otherwise, actually call proc and see what it says. |
| 4281 |
*/ |
| 4282 |
if (!OidIsValid(equalimageproc) || |
| 4283 |
!DatumGetBool(OidFunctionCall1Coll(equalimageproc, collation, |
| 4284 |
ObjectIdGetDatum(opcintype)))) |
| 4285 |
{ |
| 4286 |
allequalimage = false; |
| 4287 |
break; |
| 4288 |
} |
| 4289 |
} |
| 4290 |
|
| 4291 |
if (debugmessage) |
| 4292 |
{ |
| 4293 |
if (allequalimage) |
| 4294 |
elog(DEBUG1, "index \"%s\" can safely use deduplication", |
| 4295 |
RelationGetRelationName(rel)); |
| 4296 |
else |
| 4297 |
elog(DEBUG1, "index \"%s\" cannot use deduplication", |
| 4298 |
RelationGetRelationName(rel)); |
| 4299 |
} |
| 4300 |
|
| 4301 |
return allequalimage; |
| 4302 |
} |