src/backend/optimizer/util/plancat.c

   1 /*-------------------------------------------------------------------------
   2  *
   3  * plancat.c
   4  *         routines for accessing the system catalogs
   5  *
   6  *
   7  * Copyright (c) 1994, Regents of the University of California
   8  *
   9  *
  10  * IDENTIFICATION
  11  *        $Header: /cvsroot/pgsql/src/backend/optimizer/util/plancat.c,v 1.29 1999/05/10 00:45:25 momjian Exp $
  12  *
  13  *-------------------------------------------------------------------------
  14  */
  15 #include <stdio.h>
  16 #include "postgres.h"
  17
  18 #include "access/heapam.h"
  19 #include "access/genam.h"
  20 #include "access/htup.h"
  21 #include "access/itup.h"
  22
  23 #include "catalog/catname.h"
  24 #include "catalog/pg_amop.h"
  25 #include "catalog/pg_index.h"
  26 #include "catalog/pg_inherits.h"
  27 #include "catalog/pg_version.h"
  28
  29 #include "parser/parsetree.h"   /* for getrelid() */
  30 #include "fmgr.h"
  31
  32 #include "optimizer/internal.h"
  33 #include "optimizer/plancat.h"
  34
  35 #include "utils/syscache.h"
  36 #ifndef HAVE_MEMMOVE
  37 #include <regex/utils.h>
  38 #else
  39 #include <string.h>
  40 #endif
  41
  42
  43 static void IndexSelectivity(Oid indexrelid, Oid indrelid, int32 nIndexKeys,
  44                                  Oid *AccessMethodOperatorClasses, Oid *operatorObjectIds,
  45            int32 *varAttributeNumbers, char **constValues, int32 *constFlags,
  46                                  float *idxPages, float *idxSelec);
  47
  48
  49 /*
  50  * relation_info -
  51  *        Retrieves catalog information for a given relation. Given the oid of
  52  *        the relation, return the following information:
  53  *                              whether the relation has secondary indices
  54  *                              number of pages
  55  *                              number of tuples
  56  */
  57 void
  58 relation_info(Query *root, Index relid,
  59                           bool *hasindex, int *pages, int *tuples)
  60 {
  61         HeapTuple       relationTuple;
  62         Form_pg_class relation;
  63         Oid                     relationObjectId;
  64
  65         relationObjectId = getrelid(relid, root->rtable);
  66         relationTuple = SearchSysCacheTuple(RELOID,
  67                                                                           ObjectIdGetDatum(relationObjectId),
  68                                                                                 0, 0, 0);
  69         if (HeapTupleIsValid(relationTuple))
  70         {
  71                 relation = (Form_pg_class) GETSTRUCT(relationTuple);
  72
  73                 *hasindex = (relation->relhasindex) ? TRUE : FALSE;
  74                 *pages = relation->relpages;
  75                 *tuples = relation->reltuples;
  76         }
  77         else
  78         {
  79                 elog(ERROR, "RelationCatalogInformation: Relation %u not found",
  80                          relationObjectId);
  81         }
  82
  83         return;
  84 }
  85
  86
  87 /*
  88  * index_info
  89  *        Retrieves catalog information on an index on a given relation.
  90  *
  91  *        The index relation is opened on the first invocation. The current
  92  *        retrieves the next index relation within the catalog that has not
  93  *        already been retrieved by a previous call.  The index catalog
  94  *        is closed when no more indices for 'relid' can be found.
  95  *
  96  * 'first' is 1 if this is the first call
  97  *
  98  * Returns true if successful and false otherwise. Index info is returned
  99  * via the transient data structure 'info'.
 100  *
 101  */
 102 bool
 103 index_info(Query *root, bool first, int relid, IdxInfoRetval *info)
 104 {
 105         int                     i;
 106         HeapTuple       indexTuple,
 107                                 amopTuple;
 108         Form_pg_index index;
 109         Relation        indexRelation;
 110         uint16          amstrategy;
 111         Oid                     relam;
 112         Oid                     indrelid;
 113
 114         static Relation relation = (Relation) NULL;
 115         static HeapScanDesc scan = (HeapScanDesc) NULL;
 116         static ScanKeyData indexKey;
 117
 118
 119         /* find the oid of the indexed relation */
 120         indrelid = getrelid(relid, root->rtable);
 121
 122         MemSet(info, 0, sizeof(IdxInfoRetval));
 123
 124         /*
 125          * the maximum number of elements in each of the following arrays is
 126          * 8. We allocate one more for a terminating 0 to indicate the end of
 127          * the array.
 128          */
 129         info->indexkeys = (int *) palloc(sizeof(int) * 9);
 130         MemSet(info->indexkeys, 0, sizeof(int) * 9);
 131         info->orderOprs = (Oid *) palloc(sizeof(Oid) * 9);
 132         MemSet(info->orderOprs, 0, sizeof(Oid) * 9);
 133         info->classlist = (Oid *) palloc(sizeof(Oid) * 9);
 134         MemSet(info->classlist, 0, sizeof(Oid) * 9);
 135
 136         /* Find an index on the given relation */
 137         if (first)
 138         {
 139                 if (RelationIsValid(relation))
 140                         heap_close(relation);
 141                 if (HeapScanIsValid(scan))
 142                         heap_endscan(scan);
 143
 144                 ScanKeyEntryInitialize(&indexKey, 0,
 145                                                            Anum_pg_index_indrelid,
 146                                                            F_OIDEQ,
 147                                                            ObjectIdGetDatum(indrelid));
 148
 149                 relation = heap_openr(IndexRelationName);
 150                 scan = heap_beginscan(relation, 0, SnapshotNow,
 151                                                           1, &indexKey);
 152         }
 153         if (!HeapScanIsValid(scan))
 154                 elog(ERROR, "index_info: scan not started");
 155         indexTuple = heap_getnext(scan, 0);
 156         if (!HeapTupleIsValid(indexTuple))
 157         {
 158                 heap_endscan(scan);
 159                 heap_close(relation);
 160                 scan = (HeapScanDesc) NULL;
 161                 relation = (Relation) NULL;
 162                 return 0;
 163         }
 164
 165         /* Extract info from the index tuple */
 166         index = (Form_pg_index) GETSTRUCT(indexTuple);
 167         info->relid = index->indexrelid;        /* index relation */
 168         for (i = 0; i < INDEX_MAX_KEYS; i++)
 169                 info->indexkeys[i] = index->indkey[i];
 170         for (i = 0; i < INDEX_MAX_KEYS; i++)
 171                 info->classlist[i] = index->indclass[i];
 172
 173         info->indproc = index->indproc;         /* functional index ?? */
 174
 175         /* partial index ?? */
 176         if (VARSIZE(&index->indpred) != 0)
 177         {
 178
 179                 /*
 180                  * The memory allocated here for the predicate (in lispReadString)
 181                  * only needs to stay around until it's used in find_index_paths,
 182                  * which is all within a command, so the automatic pfree at end of
 183                  * transaction should be ok.
 184                  */
 185                 char       *predString;
 186
 187                 predString = fmgr(F_TEXTOUT, &index->indpred);
 188                 info->indpred = (Node *) stringToNode(predString);
 189                 pfree(predString);
 190         }
 191
 192         /* Extract info from the relation descriptor for the index */
 193         indexRelation = index_open(index->indexrelid);
 194 #ifdef notdef
 195         /* XXX should iterate through strategies -- but how?  use #1 for now */
 196         amstrategy = indexRelation->rd_am->amstrategies;
 197 #endif   /* notdef */
 198         amstrategy = 1;
 199         relam = indexRelation->rd_rel->relam;
 200         info->relam = relam;
 201         info->pages = indexRelation->rd_rel->relpages;
 202         info->tuples = indexRelation->rd_rel->reltuples;
 203         heap_close(indexRelation);
 204
 205         /*
 206          * Find the index ordering keys
 207          *
 208          * Must use indclass to know when to stop looking since with functional
 209          * indices there could be several keys (args) for one opclass. -mer 27
 210          * Sept 1991
 211          */
 212         for (i = 0; i < 8 && index->indclass[i]; ++i)
 213         {
 214                 amopTuple = SearchSysCacheTuple(AMOPSTRATEGY,
 215                                                                                 ObjectIdGetDatum(relam),
 216                                                                         ObjectIdGetDatum(index->indclass[i]),
 217                                                                                 UInt16GetDatum(amstrategy),
 218                                                                                 0);
 219                 if (!HeapTupleIsValid(amopTuple))
 220                         elog(ERROR, "index_info: no amop %u %u %d",
 221                                  relam, index->indclass[i], amstrategy);
 222                 info->orderOprs[i] = ((Form_pg_amop) GETSTRUCT(amopTuple))->amopopr;
 223         }
 224         return TRUE;
 225 }
 226
 227 /*
 228  * index_selectivity
 229  *
 230  *        Call util/plancat.c:IndexSelectivity with the indicated arguments.
 231  *
 232  * 'indid' is the index OID
 233  * 'classes' is a list of index key classes
 234  * 'opnos' is a list of index key operator OIDs
 235  * 'relid' is the OID of the relation indexed
 236  * 'attnos' is a list of the relation attnos which the index keys over
 237  * 'values' is a list of the values of the clause's constants
 238  * 'flags' is a list of fixnums which describe the constants
 239  * 'nkeys' is the number of index keys
 240  *
 241  * Returns two floats: index pages and index selectivity in 'idxPages' and
 242  *              'idxSelec'.
 243  *
 244  */
 245 void
 246 index_selectivity(Oid indid,
 247                                   Oid *classes,
 248                                   List *opnos,
 249                                   Oid relid,
 250                                   List *attnos,
 251                                   List *values,
 252                                   List *flags,
 253                                   int32 nkeys,
 254                                   float *idxPages,
 255                                   float *idxSelec)
 256 {
 257         Oid                *opno_array;
 258         int                *attno_array,
 259                            *flag_array;
 260         char      **value_array;
 261         int                     i = 0;
 262         List       *xopno,
 263                            *xattno,
 264                            *value,
 265                            *flag;
 266
 267         if (length(opnos) != nkeys || length(attnos) != nkeys ||
 268                 length(values) != nkeys || length(flags) != nkeys)
 269         {
 270
 271                 *idxPages = 0.0;
 272                 *idxSelec = 1.0;
 273                 return;
 274         }
 275
 276         opno_array = (Oid *) palloc(nkeys * sizeof(Oid));
 277         attno_array = (int *) palloc(nkeys * sizeof(int32));
 278         value_array = (char **) palloc(nkeys * sizeof(char *));
 279         flag_array = (int *) palloc(nkeys * sizeof(int32));
 280
 281         i = 0;
 282         foreach(xopno, opnos)
 283                 opno_array[i++] = lfirsti(xopno);
 284
 285         i = 0;
 286         foreach(xattno, attnos)
 287                 attno_array[i++] = lfirsti(xattno);
 288
 289         i = 0;
 290         foreach(value, values)
 291                 value_array[i++] = (char *) lfirst(value);
 292
 293         i = 0;
 294         foreach(flag, flags)
 295                 flag_array[i++] = lfirsti(flag);
 296
 297         IndexSelectivity(indid,
 298                                          relid,
 299                                          nkeys,
 300                                          classes,       /* not used */
 301                                          opno_array,
 302                                          attno_array,
 303                                          value_array,
 304                                          flag_array,
 305                                          idxPages,
 306                                          idxSelec);
 307         return;
 308 }
 309
 310 /*
 311  * restriction_selectivity in lisp system.
 312  *
 313  *        NOTE: The routine is now merged with RestrictionClauseSelectivity
 314  *        as defined in plancat.c
 315  *
 316  * Returns the selectivity of a specified operator.
 317  * This code executes registered procedures stored in the
 318  * operator relation, by calling the function manager.
 319  *
 320  * XXX The assumption in the selectivity procedures is that if the
 321  *              relation OIDs or attribute numbers are -1, then the clause
 322  *              isn't of the form (op var const).
 323  */
 324 Cost
 325 restriction_selectivity(Oid functionObjectId,
 326                                                 Oid operatorObjectId,
 327                                                 Oid relationObjectId,
 328                                                 AttrNumber attributeNumber,
 329                                                 char *constValue,
 330                                                 int32 constFlag)
 331 {
 332         float64         result;
 333
 334         result = (float64) fmgr(functionObjectId,
 335                                                         (char *) operatorObjectId,
 336                                                         (char *) relationObjectId,
 337                                                         (char *) (int) attributeNumber,
 338                                                         (char *) constValue,
 339                                                         (char *) constFlag,
 340                                                         NULL);
 341         if (!PointerIsValid(result))
 342                 elog(ERROR, "RestrictionClauseSelectivity: bad pointer");
 343
 344         if (*result < 0.0 || *result > 1.0)
 345                 elog(ERROR, "RestrictionClauseSelectivity: bad value %lf",
 346                          *result);
 347
 348         return (Cost) *result;
 349 }
 350
 351 /*
 352  * join_selectivity
 353  *        Similarly, this routine is merged with JoinClauseSelectivity in
 354  *        plancat.c
 355  *
 356  *        Returns the selectivity of an operator, given the join clause
 357  *        information.
 358  *
 359  * XXX The assumption in the selectivity procedures is that if the
 360  *              relation OIDs or attribute numbers are -1, then the clause
 361  *              isn't of the form (op var var).
 362  */
 363 Cost
 364 join_selectivity(Oid functionObjectId,
 365                                  Oid operatorObjectId,
 366                                  Oid relationObjectId1,
 367                                  AttrNumber attributeNumber1,
 368                                  Oid relationObjectId2,
 369                                  AttrNumber attributeNumber2)
 370 {
 371         float64         result;
 372
 373         result = (float64) fmgr(functionObjectId,
 374                                                         (char *) operatorObjectId,
 375                                                         (char *) relationObjectId1,
 376                                                         (char *) (int) attributeNumber1,
 377                                                         (char *) relationObjectId2,
 378                                                         (char *) (int) attributeNumber2,
 379                                                         NULL);
 380         if (!PointerIsValid(result))
 381                 elog(ERROR, "JoinClauseSelectivity: bad pointer");
 382
 383         if (*result < 0.0 || *result > 1.0)
 384                 elog(ERROR, "JoinClauseSelectivity: bad value %lf",
 385                          *result);
 386
 387         return (Cost) *result;
 388 }
 389
 390 /*
 391  * find_all_inheritors
 392  *
 393  * Returns a LISP list containing the OIDs of all relations which
 394  * inherits from the relation with OID 'inhparent'.
 395  */
 396 List *
 397 find_inheritance_children(Oid inhparent)
 398 {
 399         static ScanKeyData key[1] = {
 400                 {0, Anum_pg_inherits_inhparent, F_OIDEQ}
 401         };
 402
 403         HeapTuple       inheritsTuple;
 404         Relation        relation;
 405         HeapScanDesc scan;
 406         List       *list = NIL;
 407         Oid                     inhrelid;
 408
 409         fmgr_info(F_OIDEQ, &key[0].sk_func);
 410         key[0].sk_nargs = key[0].sk_func.fn_nargs;
 411
 412         key[0].sk_argument = ObjectIdGetDatum((Oid) inhparent);
 413         relation = heap_openr(InheritsRelationName);
 414         scan = heap_beginscan(relation, 0, SnapshotNow, 1, key);
 415         while (HeapTupleIsValid(inheritsTuple = heap_getnext(scan, 0)))
 416         {
 417                 inhrelid = ((Form_pg_inherits) GETSTRUCT(inheritsTuple))->inhrel;
 418                 list = lappendi(list, inhrelid);
 419         }
 420         heap_endscan(scan);
 421         heap_close(relation);
 422         return list;
 423 }
 424
 425 #ifdef NOT_USED
 426 /*
 427  * VersionGetParents
 428  *
 429  * Returns a LISP list containing the OIDs of all relations which are
 430  * base relations of the relation with OID 'verrelid'.
 431  */
 432 List *
 433 VersionGetParents(Oid verrelid)
 434 {
 435         static ScanKeyData key[1] = {
 436                 {0, Anum_pg_version_verrelid, F_OIDEQ}
 437         };
 438
 439         HeapTuple       versionTuple;
 440         Relation        relation;
 441         HeapScanDesc scan;
 442         Oid                     verbaseid;
 443         List       *list = NIL;
 444
 445         fmgr_info(F_OIDEQ, &key[0].sk_func);
 446         key[0].sk_nargs = key[0].sk_func.fn_nargs;
 447         relation = heap_openr(VersionRelationName);
 448         key[0].sk_argument = ObjectIdGetDatum(verrelid);
 449         scan = heap_beginscan(relation, 0, SnapshotNow, 1, key);
 450         while (HeapTupleIsValid(versionTuple = heap_getnext(scan, 0)))
 451         {
 452                 verbaseid = ((Form_pg_version)
 453                                          GETSTRUCT(versionTuple))->verbaseid;
 454
 455                 list = lconsi(verbaseid, list);
 456
 457                 key[0].sk_argument = ObjectIdGetDatum(verbaseid);
 458                 heap_rescan(scan, 0, key);
 459         }
 460         heap_endscan(scan);
 461         heap_close(relation);
 462         return list;
 463 }
 464 #endif
 465
 466
 467 /*****************************************************************************
 468  *
 469  *****************************************************************************/
 470
 471 /*
 472  * IdexSelectivity
 473  *
 474  *        Retrieves the 'amopnpages' and 'amopselect' parameters for each
 475  *        AM operator when a given index (specified by 'indexrelid') is used.
 476  *        These two parameters are returned by copying them to into an array of
 477  *        floats.
 478  *
 479  *        Assumption: the attribute numbers and operator ObjectIds are in order
 480  *        WRT to each other (otherwise, you have no way of knowing which
 481  *        AM operator class or attribute number corresponds to which operator.
 482  *
 483  * 'varAttributeNumbers' contains attribute numbers for variables
 484  * 'constValues' contains the constant values
 485  * 'constFlags' describes how to treat the constants in each clause
 486  * 'nIndexKeys' describes how many keys the index actually has
 487  *
 488  * Returns 'selectivityInfo' filled with the sum of all pages touched
 489  * and the product of each clause's selectivity.
 490  *
 491  */
 492 static void
 493 IndexSelectivity(Oid indexrelid,
 494                                  Oid indrelid,
 495                                  int32 nIndexKeys,
 496                                  Oid *AccessMethodOperatorClasses,              /* XXX not used? */
 497                                  Oid *operatorObjectIds,
 498                                  int32 *varAttributeNumbers,
 499                                  char **constValues,
 500                                  int32 *constFlags,
 501                                  float *idxPages,
 502                                  float *idxSelec)
 503 {
 504         int                     i,
 505                                 n;
 506         HeapTuple       indexTuple,
 507                                 amopTuple,
 508                                 indRel;
 509         Form_pg_index index;
 510         Form_pg_amop amop;
 511         Oid                     indclass;
 512         float64data npages,
 513                                 select;
 514         float64         amopnpages,
 515                                 amopselect;
 516         Oid                     relam;
 517         bool            nphack = false;
 518         float64data fattr_select = 1.0;
 519
 520         indRel = SearchSysCacheTuple(RELOID,
 521                                                                  ObjectIdGetDatum(indexrelid),
 522                                                                  0, 0, 0);
 523         if (!HeapTupleIsValid(indRel))
 524                 elog(ERROR, "IndexSelectivity: index %u not found",
 525                          indexrelid);
 526         relam = ((Form_pg_class) GETSTRUCT(indRel))->relam;
 527
 528         indexTuple = SearchSysCacheTuple(INDEXRELID,
 529                                                                          ObjectIdGetDatum(indexrelid),
 530                                                                          0, 0, 0);
 531         if (!HeapTupleIsValid(indexTuple))
 532                 elog(ERROR, "IndexSelectivity: index %u not found",
 533                          indexrelid);
 534         index = (Form_pg_index) GETSTRUCT(indexTuple);
 535
 536         /*
 537          * Hack for non-functional btree npages estimation: npages =
 538          * index_pages * selectivity_of_1st_attr_clause(s) - vadim 04/24/97
 539          */
 540         if (relam == BTREE_AM_OID &&
 541                 varAttributeNumbers[0] != InvalidAttrNumber)
 542                 nphack = true;
 543
 544         npages = 0.0;
 545         select = 1.0;
 546         for (n = 0; n < nIndexKeys; ++n)
 547         {
 548                 /*
 549                  * Find the AM class for this key.
 550                  *
 551                  * If the first attribute number is invalid then we have a functional
 552                  * index, and AM class is the first one defined since functional
 553                  * indices have exactly one key.
 554                  */
 555                 indclass = (varAttributeNumbers[0] == InvalidAttrNumber) ?
 556                         index->indclass[0] : InvalidOid;
 557                 i = 0;
 558                 while ((i < nIndexKeys) && (indclass == InvalidOid))
 559                 {
 560                         if (varAttributeNumbers[n] == index->indkey[i])
 561                         {
 562                                 indclass = index->indclass[i];
 563                                 break;
 564                         }
 565                         i++;
 566                 }
 567                 if (!OidIsValid(indclass))
 568                 {
 569
 570                         /*
 571                          * Presumably this means that we are using a functional index
 572                          * clause and so had no variable to match to the index key ...
 573                          * if not we are in trouble.
 574                          */
 575                         elog(NOTICE, "IndexSelectivity: no key %d in index %u",
 576                                  varAttributeNumbers[n], indexrelid);
 577                         continue;
 578                 }
 579
 580                 amopTuple = SearchSysCacheTuple(AMOPOPID,
 581                                                                                 ObjectIdGetDatum(indclass),
 582                                                                                 ObjectIdGetDatum(operatorObjectIds[n]),
 583                                                                                 ObjectIdGetDatum(relam),
 584                                                                                 0);
 585                 if (!HeapTupleIsValid(amopTuple))
 586                         elog(ERROR, "IndexSelectivity: no amop %u %u",
 587                                  indclass, operatorObjectIds[n]);
 588                 amop = (Form_pg_amop) GETSTRUCT(amopTuple);
 589
 590                 if (!nphack)
 591                 {
 592                         amopnpages = (float64) fmgr(amop->amopnpages,
 593                                                                                 (char *) operatorObjectIds[n],
 594                                                                                 (char *) indrelid,
 595                                                                                 (char *) varAttributeNumbers[n],
 596                                                                                 (char *) constValues[n],
 597                                                                                 (char *) constFlags[n],
 598                                                                                 (char *) nIndexKeys,
 599                                                                                 (char *) indexrelid);
 600 #ifdef NOT_USED
 601 /*
 602  * So cool guys! Npages for x > 10 and x < 20 is twice as
 603  * npages for x > 10!   - vadim 04/09/97
 604  */
 605                         npages += PointerIsValid(amopnpages) ? *amopnpages : 0.0;
 606                         if ((i = npages) < npages)      /* ceil(npages)? */
 607                                 npages += 1.0;
 608 #endif
 609                         npages += PointerIsValid(amopnpages) ? *amopnpages : 0.0;
 610                 }
 611
 612                 amopselect = (float64) fmgr(amop->amopselect,
 613                                                                         (char *) operatorObjectIds[n],
 614                                                                         (char *) indrelid,
 615                                                                         (char *) varAttributeNumbers[n],
 616                                                                         (char *) constValues[n],
 617                                                                         (char *) constFlags[n],
 618                                                                         (char *) nIndexKeys,
 619                                                                         (char *) indexrelid);
 620
 621                 if (nphack && varAttributeNumbers[n] == index->indkey[0])
 622                         fattr_select *= PointerIsValid(amopselect) ? *amopselect : 1.0;
 623
 624                 select *= PointerIsValid(amopselect) ? *amopselect : 1.0;
 625         }
 626
 627         /*
 628          * Estimation of npages below is hack of course, but it's better than
 629          * it was before.               - vadim 04/09/97
 630          */
 631         if (nphack)
 632         {
 633                 npages = fattr_select * ((Form_pg_class) GETSTRUCT(indRel))->relpages;
 634                 *idxPages = ceil((double) npages);
 635         }
 636         else
 637         {
 638                 if (nIndexKeys > 1)
 639                         npages = npages / (1.0 + nIndexKeys);
 640                 *idxPages = ceil((double) (npages / nIndexKeys));
 641         }
 642         *idxSelec = select;
 643 }