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

   1 /*-------------------------------------------------------------------------
   2  *
   3  * btutils.c
   4  *        Utility code for Postgres btree implementation.
   5  *
   6  * Portions Copyright (c) 1996-2002, 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.53 2003/07/28 00:09:14 tgl Exp $
  12  *
  13  *-------------------------------------------------------------------------
  14  */
  15
  16 #include "postgres.h"
  17
  18 #include "access/genam.h"
  19 #include "access/istrat.h"
  20 #include "access/nbtree.h"
  21 #include "catalog/catalog.h"
  22 #include "executor/execdebug.h"
  23
  24
  25 static int      _bt_getstrategynumber(RegProcedure sk_procedure, StrategyMap map);
  26
  27
  28 /*
  29  * _bt_mkscankey
  30  *              Build a scan key that contains comparison data from itup
  31  *              as well as comparator routines appropriate to the key datatypes.
  32  *
  33  *              The result is intended for use with _bt_compare().
  34  */
  35 ScanKey
  36 _bt_mkscankey(Relation rel, IndexTuple itup)
  37 {
  38         ScanKey         skey;
  39         TupleDesc       itupdesc;
  40         int                     natts;
  41         int                     i;
  42         FmgrInfo   *procinfo;
  43         Datum           arg;
  44         bool            null;
  45         bits16          flag;
  46
  47         itupdesc = RelationGetDescr(rel);
  48         natts = RelationGetNumberOfAttributes(rel);
  49
  50         skey = (ScanKey) palloc(natts * sizeof(ScanKeyData));
  51
  52         for (i = 0; i < natts; i++)
  53         {
  54                 procinfo = index_getprocinfo(rel, i + 1, BTORDER_PROC);
  55                 arg = index_getattr(itup, i + 1, itupdesc, &null);
  56                 flag = null ? SK_ISNULL : 0x0;
  57                 ScanKeyEntryInitializeWithInfo(&skey[i],
  58                                                                            flag,
  59                                                                            (AttrNumber) (i + 1),
  60                                                                            procinfo,
  61                                                                            CurrentMemoryContext,
  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.
  72  *
  73  *              The result cannot be used with _bt_compare().  Currently this
  74  *              routine is only called by utils/sort/tuplesort.c, which has its
  75  *              own comparison routine.
  76  */
  77 ScanKey
  78 _bt_mkscankey_nodata(Relation rel)
  79 {
  80         ScanKey         skey;
  81         int                     natts;
  82         int                     i;
  83         FmgrInfo   *procinfo;
  84
  85         natts = RelationGetNumberOfAttributes(rel);
  86
  87         skey = (ScanKey) palloc(natts * sizeof(ScanKeyData));
  88
  89         for (i = 0; i < natts; i++)
  90         {
  91                 procinfo = index_getprocinfo(rel, i + 1, BTORDER_PROC);
  92                 ScanKeyEntryInitializeWithInfo(&skey[i],
  93                                                                            SK_ISNULL,
  94                                                                            (AttrNumber) (i + 1),
  95                                                                            procinfo,
  96                                                                            CurrentMemoryContext,
  97                                                                            (Datum) 0);
  98         }
  99
 100         return skey;
 101 }
 102
 103 /*
 104  * free a scan key made by either _bt_mkscankey or _bt_mkscankey_nodata.
 105  */
 106 void
 107 _bt_freeskey(ScanKey skey)
 108 {
 109         pfree(skey);
 110 }
 111
 112 /*
 113  * free a retracement stack made by _bt_search.
 114  */
 115 void
 116 _bt_freestack(BTStack stack)
 117 {
 118         BTStack         ostack;
 119
 120         while (stack != (BTStack) NULL)
 121         {
 122                 ostack = stack;
 123                 stack = stack->bts_parent;
 124                 pfree(ostack);
 125         }
 126 }
 127
 128 /*
 129  * Construct a BTItem from a plain IndexTuple.
 130  *
 131  * This is now useless code, since a BTItem *is* an index tuple with
 132  * no extra stuff.      We hang onto it for the moment to preserve the
 133  * notational distinction, in case we want to add some extra stuff
 134  * again someday.
 135  */
 136 BTItem
 137 _bt_formitem(IndexTuple itup)
 138 {
 139         int                     nbytes_btitem;
 140         BTItem          btitem;
 141         Size            tuplen;
 142
 143         /* make a copy of the index tuple with room for extra stuff */
 144         tuplen = IndexTupleSize(itup);
 145         nbytes_btitem = tuplen + (sizeof(BTItemData) - sizeof(IndexTupleData));
 146
 147         btitem = (BTItem) palloc(nbytes_btitem);
 148         memcpy((char *) &(btitem->bti_itup), (char *) itup, tuplen);
 149
 150         return btitem;
 151 }
 152
 153 /*----------
 154  *      _bt_orderkeys() -- Put keys in a sensible order for conjunctive quals.
 155  *
 156  * After this routine runs, the scan keys are ordered by index attribute
 157  * (all quals for attr 1, then all for attr 2, etc) and within each attr
 158  * the keys are ordered by constraint type: ">", ">=", "=", "<=", "<".
 159  * Furthermore, redundant keys are eliminated: we keep only the tightest
 160  * >/>= bound and the tightest </<= bound, and if there's an = key then
 161  * that's the only one returned.  (So, we return either a single = key,
 162  * or one or two boundary-condition keys for each attr.)
 163  *
 164  * As a byproduct of this work, we can detect contradictory quals such
 165  * as "x = 1 AND x > 2".  If we see that, we return so->quals_ok = FALSE,
 166  * indicating the scan need not be run at all since no tuples can match.
 167  *
 168  * Another byproduct is to determine how many quals must be satisfied to
 169  * continue the scan.  _bt_checkkeys uses this.  For example, if the quals
 170  * are "x = 1 AND y < 4 AND z < 5", then _bt_checkkeys will reject a tuple
 171  * (1,2,7), but we must continue the scan in case there are tuples (1,3,z).
 172  * But once we reach tuples like (1,4,z) we can stop scanning because no
 173  * later tuples could match.  This is reflected by setting
 174  * so->numberOfRequiredKeys to the number of leading keys that must be
 175  * matched to continue the scan.  numberOfRequiredKeys is equal to the
 176  * number of leading "=" keys plus the key(s) for the first non "="
 177  * attribute, which can be seen to be correct by considering the above
 178  * example.
 179  *
 180  * Furthermore, we detect the case where the index is unique and we have
 181  * equality quals for all columns.      In this case there can be at most one
 182  * (visible) matching tuple.  index_getnext uses this to avoid uselessly
 183  * continuing the scan after finding one match.
 184  *
 185  * The initial ordering of the keys is expected to be by attribute already
 186  * (see group_clauses_by_indexkey() in indxpath.c).  The task here is to
 187  * standardize the appearance of multiple keys for the same attribute.
 188  *
 189  * XXX this routine is one of many places that fail to handle SK_COMMUTE
 190  * scankeys properly.  Currently, the planner is careful never to generate
 191  * any indexquals that would require SK_COMMUTE to be set.      Someday we ought
 192  * to try to fix this, though it's not real critical as long as indexable
 193  * operators all have commutators...
 194  *
 195  * Note: this routine invokes comparison operators via OidFunctionCallN,
 196  * ie, without caching function lookups.  No point in trying to be smarter,
 197  * since these comparisons are executed only when the user expresses a
 198  * hokey qualification, and happen only once per scan anyway.
 199  *----------
 200  */
 201 void
 202 _bt_orderkeys(IndexScanDesc scan)
 203 {
 204         Relation        relation = scan->indexRelation;
 205         BTScanOpaque so = (BTScanOpaque) scan->opaque;
 206         ScanKeyData xform[BTMaxStrategyNumber];
 207         bool            init[BTMaxStrategyNumber];
 208         int                     numberOfKeys = so->numberOfKeys;
 209         ScanKey         key;
 210         ScanKey         cur;
 211         StrategyMap map;
 212         Datum           test;
 213         int                     i,
 214                                 j;
 215         AttrNumber      attno;
 216         int                     new_numberOfKeys;
 217         bool            allEqualSoFar;
 218
 219         so->qual_ok = true;
 220         so->numberOfRequiredKeys = 0;
 221         scan->keys_are_unique = false;
 222
 223         if (numberOfKeys < 1)
 224                 return;                                 /* done if qual-less scan */
 225
 226         key = so->keyData;
 227         cur = &key[0];
 228         /* check input keys are correctly ordered */
 229         if (cur->sk_attno != 1)
 230                 elog(ERROR, "key(s) for attribute 1 missed");
 231
 232         /* We can short-circuit most of the work if there's just one key */
 233         if (numberOfKeys == 1)
 234         {
 235                 /*
 236                  * We don't use indices for 'A is null' and 'A is not null'
 237                  * currently and 'A < = > <> NULL' will always fail - so qual is
 238                  * not Ok if comparison value is NULL.          - vadim 03/21/97
 239                  */
 240                 if (cur->sk_flags & SK_ISNULL)
 241                         so->qual_ok = false;
 242                 else if (relation->rd_index->indisunique &&
 243                                  relation->rd_rel->relnatts == 1)
 244                 {
 245                         /* it's a unique index, do we have an equality qual? */
 246                         map = IndexStrategyGetStrategyMap(RelationGetIndexStrategy(relation),
 247                                                                                           BTMaxStrategyNumber,
 248                                                                                           1);
 249                         j = _bt_getstrategynumber(cur->sk_procedure, map);
 250                         if (j == (BTEqualStrategyNumber - 1))
 251                                 scan->keys_are_unique = true;
 252                 }
 253                 so->numberOfRequiredKeys = 1;
 254                 return;
 255         }
 256
 257         /*
 258          * Otherwise, do the full set of pushups.
 259          */
 260         new_numberOfKeys = 0;
 261         allEqualSoFar = true;
 262
 263         /*
 264          * Initialize for processing of keys for attr 1.
 265          *
 266          * xform[i] holds a copy of the current scan key of strategy type i+1, if
 267          * any; init[i] is TRUE if we have found such a key for this attr.
 268          */
 269         attno = 1;
 270         map = IndexStrategyGetStrategyMap(RelationGetIndexStrategy(relation),
 271                                                                           BTMaxStrategyNumber,
 272                                                                           attno);
 273         MemSet(xform, 0, sizeof(xform));        /* not really necessary */
 274         MemSet(init, 0, sizeof(init));
 275
 276         /*
 277          * Loop iterates from 0 to numberOfKeys inclusive; we use the last
 278          * pass to handle after-last-key processing.  Actual exit from the
 279          * loop is at the "break" statement below.
 280          */
 281         for (i = 0;; cur++, i++)
 282         {
 283                 if (i < numberOfKeys)
 284                 {
 285                         /* See comments above: any NULL implies cannot match qual */
 286                         if (cur->sk_flags & SK_ISNULL)
 287                         {
 288                                 so->qual_ok = false;
 289
 290                                 /*
 291                                  * Quit processing so we don't try to invoke comparison
 292                                  * routines on NULLs.
 293                                  */
 294                                 return;
 295                         }
 296                 }
 297
 298                 /*
 299                  * If we are at the end of the keys for a particular attr, finish
 300                  * up processing and emit the cleaned-up keys.
 301                  */
 302                 if (i == numberOfKeys || cur->sk_attno != attno)
 303                 {
 304                         bool            priorAllEqualSoFar = allEqualSoFar;
 305
 306                         /* check input keys are correctly ordered */
 307                         if (i < numberOfKeys && cur->sk_attno != attno + 1)
 308                                 elog(ERROR, "key(s) for attribute %d missed", attno + 1);
 309
 310                         /*
 311                          * If = has been specified, no other key will be used. In case
 312                          * of key > 2 && key == 1 and so on we have to set qual_ok to
 313                          * false before discarding the other keys.
 314                          */
 315                         if (init[BTEqualStrategyNumber - 1])
 316                         {
 317                                 ScanKeyData *eq,
 318                                                    *chk;
 319
 320                                 eq = &xform[BTEqualStrategyNumber - 1];
 321                                 for (j = BTMaxStrategyNumber; --j >= 0;)
 322                                 {
 323                                         if (!init[j] ||
 324                                                 j == (BTEqualStrategyNumber - 1))
 325                                                 continue;
 326                                         chk = &xform[j];
 327                                         test = OidFunctionCall2(chk->sk_procedure,
 328                                                                                         eq->sk_argument,
 329                                                                                         chk->sk_argument);
 330                                         if (!DatumGetBool(test))
 331                                                 so->qual_ok = false;
 332                                 }
 333                                 init[BTLessStrategyNumber - 1] = false;
 334                                 init[BTLessEqualStrategyNumber - 1] = false;
 335                                 init[BTGreaterEqualStrategyNumber - 1] = false;
 336                                 init[BTGreaterStrategyNumber - 1] = false;
 337                         }
 338                         else
 339                         {
 340                                 /*
 341                                  * No "=" for this key, so we're done with required keys
 342                                  */
 343                                 allEqualSoFar = false;
 344                         }
 345
 346                         /* keep only one of <, <= */
 347                         if (init[BTLessStrategyNumber - 1]
 348                                 && init[BTLessEqualStrategyNumber - 1])
 349                         {
 350                                 ScanKeyData *lt = &xform[BTLessStrategyNumber - 1];
 351                                 ScanKeyData *le = &xform[BTLessEqualStrategyNumber - 1];
 352
 353                                 test = OidFunctionCall2(le->sk_procedure,
 354                                                                                 lt->sk_argument,
 355                                                                                 le->sk_argument);
 356                                 if (DatumGetBool(test))
 357                                         init[BTLessEqualStrategyNumber - 1] = false;
 358                                 else
 359                                         init[BTLessStrategyNumber - 1] = false;
 360                         }
 361
 362                         /* keep only one of >, >= */
 363                         if (init[BTGreaterStrategyNumber - 1]
 364                                 && init[BTGreaterEqualStrategyNumber - 1])
 365                         {
 366                                 ScanKeyData *gt = &xform[BTGreaterStrategyNumber - 1];
 367                                 ScanKeyData *ge = &xform[BTGreaterEqualStrategyNumber - 1];
 368
 369                                 test = OidFunctionCall2(ge->sk_procedure,
 370                                                                                 gt->sk_argument,
 371                                                                                 ge->sk_argument);
 372                                 if (DatumGetBool(test))
 373                                         init[BTGreaterEqualStrategyNumber - 1] = false;
 374                                 else
 375                                         init[BTGreaterStrategyNumber - 1] = false;
 376                         }
 377
 378                         /*
 379                          * Emit the cleaned-up keys back into the key[] array in the
 380                          * correct order.  Note we are overwriting our input here!
 381                          * It's OK because (a) xform[] is a physical copy of the keys
 382                          * we want, (b) we cannot emit more keys than we input, so we
 383                          * won't overwrite as-yet-unprocessed keys.
 384                          */
 385                         for (j = BTMaxStrategyNumber; --j >= 0;)
 386                         {
 387                                 if (init[j])
 388                                         memcpy(&key[new_numberOfKeys++], &xform[j],
 389                                                    sizeof(ScanKeyData));
 390                         }
 391
 392                         /*
 393                          * If all attrs before this one had "=", include these keys
 394                          * into the required-keys count.
 395                          */
 396                         if (priorAllEqualSoFar)
 397                                 so->numberOfRequiredKeys = new_numberOfKeys;
 398
 399                         /*
 400                          * Exit loop here if done.
 401                          */
 402                         if (i == numberOfKeys)
 403                                 break;
 404
 405                         /* Re-initialize for new attno */
 406                         attno = cur->sk_attno;
 407                         map = IndexStrategyGetStrategyMap(RelationGetIndexStrategy(relation),
 408                                                                                           BTMaxStrategyNumber,
 409                                                                                           attno);
 410                         MemSet(xform, 0, sizeof(xform));        /* not really necessary */
 411                         MemSet(init, 0, sizeof(init));
 412                 }
 413
 414                 /* figure out which strategy this key's operator corresponds to */
 415                 j = _bt_getstrategynumber(cur->sk_procedure, map);
 416
 417                 /* have we seen one of these before? */
 418                 if (init[j])
 419                 {
 420                         /* yup, keep the more restrictive value */
 421                         test = FunctionCall2(&cur->sk_func,
 422                                                                  cur->sk_argument,
 423                                                                  xform[j].sk_argument);
 424                         if (DatumGetBool(test))
 425                                 xform[j].sk_argument = cur->sk_argument;
 426                         else if (j == (BTEqualStrategyNumber - 1))
 427                                 so->qual_ok = false;
 428                         /* key == a && key == b, but a != b */
 429                 }
 430                 else
 431                 {
 432                         /* nope, so remember this scankey */
 433                         memcpy(&xform[j], cur, sizeof(ScanKeyData));
 434                         init[j] = true;
 435                 }
 436         }
 437
 438         so->numberOfKeys = new_numberOfKeys;
 439
 440         /*
 441          * If unique index and we have equality keys for all columns, set
 442          * keys_are_unique flag for higher levels.
 443          */
 444         if (allEqualSoFar && relation->rd_index->indisunique &&
 445                 relation->rd_rel->relnatts == new_numberOfKeys)
 446                 scan->keys_are_unique = true;
 447 }
 448
 449 /*
 450  * Determine which btree strategy an operator procedure matches.
 451  *
 452  * Result is strategy number minus 1.
 453  */
 454 static int
 455 _bt_getstrategynumber(RegProcedure sk_procedure, StrategyMap map)
 456 {
 457         int                     j;
 458
 459         for (j = BTMaxStrategyNumber; --j >= 0;)
 460         {
 461                 if (sk_procedure == map->entry[j].sk_procedure)
 462                         return j;
 463         }
 464         elog(ERROR, "could not identify operator %u", sk_procedure);
 465         return -1;                                      /* keep compiler quiet */
 466 }
 467
 468 /*
 469  * Test whether an indextuple satisfies all the scankey conditions.
 470  *
 471  * If the tuple fails to pass the qual, we also determine whether there's
 472  * any need to continue the scan beyond this tuple, and set *continuescan
 473  * accordingly.  See comments for _bt_orderkeys(), above, about how this is
 474  * done.
 475  */
 476 bool
 477 _bt_checkkeys(IndexScanDesc scan, IndexTuple tuple,
 478                           ScanDirection dir, bool *continuescan)
 479 {
 480         BTScanOpaque so = (BTScanOpaque) scan->opaque;
 481         int                     keysz = so->numberOfKeys;
 482         int                     keysok;
 483         TupleDesc       tupdesc;
 484         ScanKey         key;
 485
 486         *continuescan = true;
 487
 488         /* If no keys, always scan the whole index */
 489         if (keysz == 0)
 490                 return true;
 491
 492         tupdesc = RelationGetDescr(scan->indexRelation);
 493         key = so->keyData;
 494         keysok = 0;
 495
 496         IncrIndexProcessed();
 497
 498         while (keysz > 0)
 499         {
 500                 Datum           datum;
 501                 bool            isNull;
 502                 Datum           test;
 503
 504                 datum = index_getattr(tuple,
 505                                                           key->sk_attno,
 506                                                           tupdesc,
 507                                                           &isNull);
 508
 509                 /* btree doesn't support 'A is null' clauses, yet */
 510                 if (key->sk_flags & SK_ISNULL)
 511                 {
 512                         /* we shouldn't get here, really; see _bt_orderkeys() */
 513                         *continuescan = false;
 514                         return false;
 515                 }
 516
 517                 if (isNull)
 518                 {
 519                         /*
 520                          * Since NULLs are sorted after non-NULLs, we know we have
 521                          * reached the upper limit of the range of values for this
 522                          * index attr.  On a forward scan, we can stop if this qual is
 523                          * one of the "must match" subset.      On a backward scan,
 524                          * however, we should keep going.
 525                          */
 526                         if (keysok < so->numberOfRequiredKeys &&
 527                                 ScanDirectionIsForward(dir))
 528                                 *continuescan = false;
 529
 530                         /*
 531                          * In any case, this indextuple doesn't match the qual.
 532                          */
 533                         return false;
 534                 }
 535
 536                 if (key->sk_flags & SK_COMMUTE)
 537                         test = FunctionCall2(&key->sk_func,
 538                                                                  key->sk_argument, datum);
 539                 else
 540                         test = FunctionCall2(&key->sk_func,
 541                                                                  datum, key->sk_argument);
 542
 543                 if (DatumGetBool(test) == !!(key->sk_flags & SK_NEGATE))
 544                 {
 545                         /*
 546                          * Tuple fails this qual.  If it's a required qual, then we
 547                          * can conclude no further tuples will pass, either.
 548                          */
 549                         if (keysok < so->numberOfRequiredKeys)
 550                                 *continuescan = false;
 551                         return false;
 552                 }
 553
 554                 keysok++;
 555                 key++;
 556                 keysz--;
 557         }
 558
 559         /* If we get here, the tuple passes all quals. */
 560         return true;
 561 }