granicus.if.org Git - postgresql/blob - src/backend/access/nbtree/nbtutils.c

   1 /*-------------------------------------------------------------------------
   2  *
   3  * nbtutils.c
   4  *        Utility code for Postgres btree implementation.
   5  *
   6  * Portions Copyright (c) 1996-2003, PostgreSQL Global Development Group
   7  * Portions Copyright (c) 1994, Regents of the University of California
   8  *
   9  *
  10  * IDENTIFICATION
  11  *        $Header: /cvsroot/pgsql/src/backend/access/nbtree/nbtutils.c,v 1.56 2003/11/12 21:15:47 tgl Exp $
  12  *
  13  *-------------------------------------------------------------------------
  14  */
  15
  16 #include "postgres.h"
  17
  18 #include "access/genam.h"
  19 #include "access/nbtree.h"
  20 #include "catalog/catalog.h"
  21 #include "executor/execdebug.h"
  22
  23
  24 /*
  25  * _bt_mkscankey
  26  *              Build a scan key that contains comparison data from itup
  27  *              as well as comparator routines appropriate to the key datatypes.
  28  *
  29  *              The result is intended for use with _bt_compare().
  30  */
  31 ScanKey
  32 _bt_mkscankey(Relation rel, IndexTuple itup)
  33 {
  34         ScanKey         skey;
  35         TupleDesc       itupdesc;
  36         int                     natts;
  37         int                     i;
  38
  39         itupdesc = RelationGetDescr(rel);
  40         natts = RelationGetNumberOfAttributes(rel);
  41
  42         skey = (ScanKey) palloc(natts * sizeof(ScanKeyData));
  43
  44         for (i = 0; i < natts; i++)
  45         {
  46                 FmgrInfo   *procinfo;
  47                 Datum           arg;
  48                 bool            null;
  49
  50                 /*
  51                  * We can use the cached (default) support procs since no cross-type
  52                  * comparison can be needed.
  53                  */
  54                 procinfo = index_getprocinfo(rel, i + 1, BTORDER_PROC);
  55                 arg = index_getattr(itup, i + 1, itupdesc, &null);
  56                 ScanKeyEntryInitializeWithInfo(&skey[i],
  57                                                                            null ? SK_ISNULL : 0,
  58                                                                            (AttrNumber) (i + 1),
  59                                                                            InvalidStrategy,
  60                                                                            InvalidOid,
  61                                                                            procinfo,
  62                                                                            arg);
  63         }
  64
  65         return skey;
  66 }
  67
  68 /*
  69  * _bt_mkscankey_nodata
  70  *              Build a scan key that contains comparator routines appropriate to
  71  *              the key datatypes, but no comparison data.  The comparison data
  72  *              ultimately used must match the key datatypes.
  73  *
  74  *              The result cannot be used with _bt_compare().  Currently this
  75  *              routine is only called by nbtsort.c and tuplesort.c, which have
  76  *              their own comparison routines.
  77  */
  78 ScanKey
  79 _bt_mkscankey_nodata(Relation rel)
  80 {
  81         ScanKey         skey;
  82         TupleDesc       itupdesc;
  83         int                     natts;
  84         int                     i;
  85
  86         itupdesc = RelationGetDescr(rel);
  87         natts = RelationGetNumberOfAttributes(rel);
  88
  89         skey = (ScanKey) palloc(natts * sizeof(ScanKeyData));
  90
  91         for (i = 0; i < natts; i++)
  92         {
  93                 FmgrInfo   *procinfo;
  94
  95                 /*
  96                  * We can use the cached (default) support procs since no cross-type
  97                  * comparison can be needed.
  98                  */
  99                 procinfo = index_getprocinfo(rel, i + 1, BTORDER_PROC);
 100                 ScanKeyEntryInitializeWithInfo(&skey[i],
 101                                                                            SK_ISNULL,
 102                                                                            (AttrNumber) (i + 1),
 103                                                                            InvalidStrategy,
 104                                                                            InvalidOid,
 105                                                                            procinfo,
 106                                                                            (Datum) 0);
 107         }
 108
 109         return skey;
 110 }
 111
 112 /*
 113  * free a scan key made by either _bt_mkscankey or _bt_mkscankey_nodata.
 114  */
 115 void
 116 _bt_freeskey(ScanKey skey)
 117 {
 118         pfree(skey);
 119 }
 120
 121 /*
 122  * free a retracement stack made by _bt_search.
 123  */
 124 void
 125 _bt_freestack(BTStack stack)
 126 {
 127         BTStack         ostack;
 128
 129         while (stack != (BTStack) NULL)
 130         {
 131                 ostack = stack;
 132                 stack = stack->bts_parent;
 133                 pfree(ostack);
 134         }
 135 }
 136
 137 /*
 138  * Construct a BTItem from a plain IndexTuple.
 139  *
 140  * This is now useless code, since a BTItem *is* an index tuple with
 141  * no extra stuff.      We hang onto it for the moment to preserve the
 142  * notational distinction, in case we want to add some extra stuff
 143  * again someday.
 144  */
 145 BTItem
 146 _bt_formitem(IndexTuple itup)
 147 {
 148         int                     nbytes_btitem;
 149         BTItem          btitem;
 150         Size            tuplen;
 151
 152         /* make a copy of the index tuple with room for extra stuff */
 153         tuplen = IndexTupleSize(itup);
 154         nbytes_btitem = tuplen + (sizeof(BTItemData) - sizeof(IndexTupleData));
 155
 156         btitem = (BTItem) palloc(nbytes_btitem);
 157         memcpy((char *) &(btitem->bti_itup), (char *) itup, tuplen);
 158
 159         return btitem;
 160 }
 161
 162 /*----------
 163  *      _bt_preprocess_keys() -- Preprocess scan keys
 164  *
 165  * The caller-supplied keys (in scan->keyData[]) are copied to
 166  * so->keyData[] with possible transformation.  scan->numberOfKeys is
 167  * the number of input keys, so->numberOfKeys gets the number of output
 168  * keys (possibly less, never greater).
 169  *
 170  * The primary purpose of this routine is to discover how many scan keys
 171  * must be satisfied to continue the scan.  It also attempts to eliminate
 172  * redundant keys and detect contradictory keys.  At present, redundant and
 173  * contradictory keys can only be detected for same-data-type comparisons,
 174  * but that's the usual case so it seems worth doing.
 175  *
 176  * The output keys must be sorted by index attribute.  Presently we expect
 177  * (but verify) that the input keys are already so sorted --- this is done
 178  * by group_clauses_by_indexkey() in indxpath.c.  Some reordering of the keys
 179  * within each attribute may be done as a byproduct of the processing here,
 180  * but no other code depends on that.
 181  *
 182  * Aside from preparing so->keyData[], this routine sets
 183  * so->numberOfRequiredKeys to the number of quals that must be satisfied to
 184  * continue the scan.  _bt_checkkeys uses this.  For example, if the quals
 185  * are "x = 1 AND y < 4 AND z < 5", then _bt_checkkeys will reject a tuple
 186  * (1,2,7), but we must continue the scan in case there are tuples (1,3,z).
 187  * But once we reach tuples like (1,4,z) we can stop scanning because no
 188  * later tuples could match.  This is reflected by setting
 189  * so->numberOfRequiredKeys to 2, the number of leading keys that must be
 190  * matched to continue the scan.  In general, numberOfRequiredKeys is equal
 191  * to the number of keys for leading attributes with "=" keys, plus the
 192  * key(s) for the first non "=" attribute, which can be seen to be correct
 193  * by considering the above example.
 194  *
 195  * If possible, redundant keys are eliminated: we keep only the tightest
 196  * >/>= bound and the tightest </<= bound, and if there's an = key then
 197  * that's the only one returned.  (So, we return either a single = key,
 198  * or one or two boundary-condition keys for each attr.)  However, we can
 199  * only detect redundant keys when the right-hand datatypes are all equal
 200  * to the index datatype, because we do not know suitable operators for
 201  * comparing right-hand values of two different datatypes.  (In theory
 202  * we could handle comparison of a RHS of the index datatype with a RHS of
 203  * another type, but that seems too much pain for too little gain.)  So,
 204  * keys whose operator has a nondefault subtype (ie, its RHS is not of the
 205  * index datatype) are ignored here, except for noting whether they impose
 206  * an "=" condition or not.
 207  *
 208  * As a byproduct of this work, we can detect contradictory quals such
 209  * as "x = 1 AND x > 2".  If we see that, we return so->quals_ok = FALSE,
 210  * indicating the scan need not be run at all since no tuples can match.
 211  * Again though, only keys with RHS datatype equal to the index datatype
 212  * can be checked for contradictions.
 213  *
 214  * Furthermore, we detect the case where the index is unique and we have
 215  * equality quals for all columns.      In this case there can be at most one
 216  * (visible) matching tuple.  index_getnext uses this to avoid uselessly
 217  * continuing the scan after finding one match.
 218  *----------
 219  */
 220 void
 221 _bt_preprocess_keys(IndexScanDesc scan)
 222 {
 223         Relation        relation = scan->indexRelation;
 224         BTScanOpaque so = (BTScanOpaque) scan->opaque;
 225         int                     numberOfKeys = scan->numberOfKeys;
 226         int                     new_numberOfKeys;
 227         ScanKey         inkeys;
 228         ScanKey         outkeys;
 229         ScanKey         cur;
 230         ScanKey         xform[BTMaxStrategyNumber];
 231         bool            allEqualSoFar;
 232         bool            hasOtherTypeEqual;
 233         Datum           test;
 234         int                     i,
 235                                 j;
 236         AttrNumber      attno;
 237
 238         /* initialize result variables */
 239         so->qual_ok = true;
 240         so->numberOfKeys = 0;
 241         so->numberOfRequiredKeys = 0;
 242         scan->keys_are_unique = false;
 243
 244         if (numberOfKeys < 1)
 245                 return;                                 /* done if qual-less scan */
 246
 247         inkeys = scan->keyData;
 248         outkeys = so->keyData;
 249         cur = &inkeys[0];
 250         /* we check that input keys are correctly ordered */
 251         if (cur->sk_attno != 1)
 252                 elog(ERROR, "key(s) for attribute 1 missed");
 253
 254         /* We can short-circuit most of the work if there's just one key */
 255         if (numberOfKeys == 1)
 256         {
 257                 /*
 258                  * We don't use indices for 'A is null' and 'A is not null'
 259                  * currently and 'A < = > <> NULL' will always fail - so qual is
 260                  * not OK if comparison value is NULL.          - vadim 03/21/97
 261                  */
 262                 if (cur->sk_flags & SK_ISNULL)
 263                         so->qual_ok = false;
 264                 else if (relation->rd_index->indisunique &&
 265                                  relation->rd_rel->relnatts == 1)
 266                 {
 267                         /* it's a unique index, do we have an equality qual? */
 268                         if (cur->sk_strategy == BTEqualStrategyNumber)
 269                                 scan->keys_are_unique = true;
 270                 }
 271                 memcpy(outkeys, inkeys, sizeof(ScanKeyData));
 272                 so->numberOfKeys = 1;
 273                 so->numberOfRequiredKeys = 1;
 274                 return;
 275         }
 276
 277         /*
 278          * Otherwise, do the full set of pushups.
 279          */
 280         new_numberOfKeys = 0;
 281         allEqualSoFar = true;
 282
 283         /*
 284          * Initialize for processing of keys for attr 1.
 285          *
 286          * xform[i] points to the currently best scan key of strategy type i+1,
 287          * if any is found with a default operator subtype; it is NULL if we
 288          * haven't yet found such a key for this attr.  Scan keys of nondefault
 289          * subtypes are transferred to the output with no processing except for
 290          * noting if they are of "=" type.
 291          */
 292         attno = 1;
 293         memset(xform, 0, sizeof(xform));
 294         hasOtherTypeEqual = false;
 295
 296         /*
 297          * Loop iterates from 0 to numberOfKeys inclusive; we use the last
 298          * pass to handle after-last-key processing.  Actual exit from the
 299          * loop is at the "break" statement below.
 300          */
 301         for (i = 0;; cur++, i++)
 302         {
 303                 if (i < numberOfKeys)
 304                 {
 305                         /* See comments above: any NULL implies cannot match qual */
 306                         if (cur->sk_flags & SK_ISNULL)
 307                         {
 308                                 so->qual_ok = false;
 309
 310                                 /*
 311                                  * Quit processing so we don't try to invoke comparison
 312                                  * routines on NULLs.
 313                                  */
 314                                 return;
 315                         }
 316                 }
 317
 318                 /*
 319                  * If we are at the end of the keys for a particular attr, finish
 320                  * up processing and emit the cleaned-up keys.
 321                  */
 322                 if (i == numberOfKeys || cur->sk_attno != attno)
 323                 {
 324                         bool            priorAllEqualSoFar = allEqualSoFar;
 325
 326                         /* check input keys are correctly ordered */
 327                         if (i < numberOfKeys && cur->sk_attno != attno + 1)
 328                                 elog(ERROR, "key(s) for attribute %d missed", attno + 1);
 329
 330                         /*
 331                          * If = has been specified, no other key will be used. In case
 332                          * of key > 2 && key == 1 and so on we have to set qual_ok to
 333                          * false before discarding the other keys.
 334                          */
 335                         if (xform[BTEqualStrategyNumber - 1])
 336                         {
 337                                 ScanKey         eq = xform[BTEqualStrategyNumber - 1];
 338
 339                                 for (j = BTMaxStrategyNumber; --j >= 0;)
 340                                 {
 341                                         ScanKey         chk = xform[j];
 342
 343                                         if (!chk || j == (BTEqualStrategyNumber - 1))
 344                                                 continue;
 345                                         test = FunctionCall2(&chk->sk_func,
 346                                                                                  eq->sk_argument,
 347                                                                                  chk->sk_argument);
 348                                         if (!DatumGetBool(test))
 349                                         {
 350                                                 so->qual_ok = false;
 351                                                 break;
 352                                         }
 353                                 }
 354                                 xform[BTLessStrategyNumber - 1] = NULL;
 355                                 xform[BTLessEqualStrategyNumber - 1] = NULL;
 356                                 xform[BTGreaterEqualStrategyNumber - 1] = NULL;
 357                                 xform[BTGreaterStrategyNumber - 1] = NULL;
 358                         }
 359                         else
 360                         {
 361                                 /*
 362                                  * If no "=" for this key, we're done with required keys
 363                                  */
 364                                 if (! hasOtherTypeEqual)
 365                                         allEqualSoFar = false;
 366                         }
 367
 368                         /* keep only one of <, <= */
 369                         if (xform[BTLessStrategyNumber - 1]
 370                                 && xform[BTLessEqualStrategyNumber - 1])
 371                         {
 372                                 ScanKey lt = xform[BTLessStrategyNumber - 1];
 373                                 ScanKey le = xform[BTLessEqualStrategyNumber - 1];
 374
 375                                 test = FunctionCall2(&le->sk_func,
 376                                                                          lt->sk_argument,
 377                                                                          le->sk_argument);
 378                                 if (DatumGetBool(test))
 379                                         xform[BTLessEqualStrategyNumber - 1] = NULL;
 380                                 else
 381                                         xform[BTLessStrategyNumber - 1] = NULL;
 382                         }
 383
 384                         /* keep only one of >, >= */
 385                         if (xform[BTGreaterStrategyNumber - 1]
 386                                 && xform[BTGreaterEqualStrategyNumber - 1])
 387                         {
 388                                 ScanKey gt = xform[BTGreaterStrategyNumber - 1];
 389                                 ScanKey ge = xform[BTGreaterEqualStrategyNumber - 1];
 390
 391                                 test = FunctionCall2(&ge->sk_func,
 392                                                                          gt->sk_argument,
 393                                                                          ge->sk_argument);
 394                                 if (DatumGetBool(test))
 395                                         xform[BTGreaterEqualStrategyNumber - 1] = NULL;
 396                                 else
 397                                         xform[BTGreaterStrategyNumber - 1] = NULL;
 398                         }
 399
 400                         /*
 401                          * Emit the cleaned-up keys into the outkeys[] array.
 402                          */
 403                         for (j = BTMaxStrategyNumber; --j >= 0;)
 404                         {
 405                                 if (xform[j])
 406                                         memcpy(&outkeys[new_numberOfKeys++], xform[j],
 407                                                    sizeof(ScanKeyData));
 408                         }
 409
 410                         /*
 411                          * If all attrs before this one had "=", include these keys
 412                          * into the required-keys count.
 413                          */
 414                         if (priorAllEqualSoFar)
 415                                 so->numberOfRequiredKeys = new_numberOfKeys;
 416
 417                         /*
 418                          * Exit loop here if done.
 419                          */
 420                         if (i == numberOfKeys)
 421                                 break;
 422
 423                         /* Re-initialize for new attno */
 424                         attno = cur->sk_attno;
 425                         memset(xform, 0, sizeof(xform));
 426                         hasOtherTypeEqual = false;
 427                 }
 428
 429                 /* check strategy this key's operator corresponds to */
 430                 j = cur->sk_strategy - 1;
 431
 432                 /* if wrong RHS data type, punt */
 433                 if (cur->sk_subtype != InvalidOid)
 434                 {
 435                         memcpy(&outkeys[new_numberOfKeys++], cur,
 436                                    sizeof(ScanKeyData));
 437                         if (j == (BTEqualStrategyNumber - 1))
 438                                 hasOtherTypeEqual = true;
 439                         continue;
 440                 }
 441
 442                 /* have we seen one of these before? */
 443                 if (xform[j])
 444                 {
 445                         /* yup, keep the more restrictive key */
 446                         test = FunctionCall2(&cur->sk_func,
 447                                                                  cur->sk_argument,
 448                                                                  xform[j]->sk_argument);
 449                         if (DatumGetBool(test))
 450                                 xform[j] = cur;
 451                         else if (j == (BTEqualStrategyNumber - 1))
 452                         {
 453                                 /* key == a && key == b, but a != b */
 454                                 so->qual_ok = false;
 455                                 return;
 456                         }
 457                 }
 458                 else
 459                 {
 460                         /* nope, so remember this scankey */
 461                         xform[j] = cur;
 462                 }
 463         }
 464
 465         so->numberOfKeys = new_numberOfKeys;
 466
 467         /*
 468          * If unique index and we have equality keys for all columns, set
 469          * keys_are_unique flag for higher levels.
 470          */
 471         if (allEqualSoFar && relation->rd_index->indisunique &&
 472                 relation->rd_rel->relnatts == new_numberOfKeys)
 473                 scan->keys_are_unique = true;
 474 }
 475
 476 /*
 477  * Test whether an indextuple satisfies all the scankey conditions.
 478  *
 479  * If the tuple fails to pass the qual, we also determine whether there's
 480  * any need to continue the scan beyond this tuple, and set *continuescan
 481  * accordingly.  See comments for _bt_preprocess_keys(), above, about how
 482  * this is done.
 483  */
 484 bool
 485 _bt_checkkeys(IndexScanDesc scan, IndexTuple tuple,
 486                           ScanDirection dir, bool *continuescan)
 487 {
 488         BTScanOpaque so = (BTScanOpaque) scan->opaque;
 489         int                     keysz = so->numberOfKeys;
 490         int                     ikey;
 491         TupleDesc       tupdesc;
 492         ScanKey         key;
 493
 494         *continuescan = true;
 495
 496         /* If no keys, always scan the whole index */
 497         if (keysz == 0)
 498                 return true;
 499
 500         IncrIndexProcessed();
 501
 502         tupdesc = RelationGetDescr(scan->indexRelation);
 503
 504         for (key = so->keyData, ikey = 0; ikey < keysz; key++, ikey++)
 505         {
 506                 Datum           datum;
 507                 bool            isNull;
 508                 Datum           test;
 509
 510                 datum = index_getattr(tuple,
 511                                                           key->sk_attno,
 512                                                           tupdesc,
 513                                                           &isNull);
 514
 515                 /* btree doesn't support 'A is null' clauses, yet */
 516                 if (key->sk_flags & SK_ISNULL)
 517                 {
 518                         /* we shouldn't get here, really; see _bt_preprocess_keys() */
 519                         *continuescan = false;
 520                         return false;
 521                 }
 522
 523                 if (isNull)
 524                 {
 525                         /*
 526                          * Since NULLs are sorted after non-NULLs, we know we have
 527                          * reached the upper limit of the range of values for this
 528                          * index attr.  On a forward scan, we can stop if this qual is
 529                          * one of the "must match" subset.      On a backward scan,
 530                          * however, we should keep going.
 531                          */
 532                         if (ikey < so->numberOfRequiredKeys &&
 533                                 ScanDirectionIsForward(dir))
 534                                 *continuescan = false;
 535
 536                         /*
 537                          * In any case, this indextuple doesn't match the qual.
 538                          */
 539                         return false;
 540                 }
 541
 542                 test = FunctionCall2(&key->sk_func, datum, key->sk_argument);
 543
 544                 if (!DatumGetBool(test))
 545                 {
 546                         /*
 547                          * Tuple fails this qual.  If it's a required qual, then we
 548                          * may be able to conclude no further tuples will pass, either.
 549                          * We have to look at the scan direction and the qual type.
 550                          *
 551                          * Note: the only case in which we would keep going after failing
 552                          * a required qual is if there are partially-redundant quals that
 553                          * _bt_preprocess_keys() was unable to eliminate.  For example,
 554                          * given "x > 4 AND x > 10" where both are cross-type comparisons
 555                          * and so not removable, we might start the scan at the x = 4
 556                          * boundary point.  The "x > 10" condition will fail until we
 557                          * pass x = 10, but we must not stop the scan on its account.
 558                          *
 559                          * Note: because we stop the scan as soon as any required equality
 560                          * qual fails, it is critical that equality quals be used for the
 561                          * initial positioning in _bt_first() when they are available.
 562                          * See comments in _bt_first().
 563                          */
 564                         if (ikey < so->numberOfRequiredKeys)
 565                         {
 566                                 switch (key->sk_strategy)
 567                                 {
 568                                         case BTLessStrategyNumber:
 569                                         case BTLessEqualStrategyNumber:
 570                                                 if (ScanDirectionIsForward(dir))
 571                                                         *continuescan = false;
 572                                                 break;
 573                                         case BTEqualStrategyNumber:
 574                                                 *continuescan = false;
 575                                                 break;
 576                                         case BTGreaterEqualStrategyNumber:
 577                                         case BTGreaterStrategyNumber:
 578                                                 if (ScanDirectionIsBackward(dir))
 579                                                         *continuescan = false;
 580                                                 break;
 581                                         default:
 582                                                 elog(ERROR, "unrecognized StrategyNumber: %d",
 583                                                          key->sk_strategy);
 584                                 }
 585                         }
 586
 587                         /*
 588                          * In any case, this indextuple doesn't match the qual.
 589                          */
 590                         return false;
 591                 }
 592         }
 593
 594         /* If we get here, the tuple passes all quals. */
 595         return true;
 596 }