LCOV - code coverage report
Current view: top level - src/backend/access/gist - gistutil.c (source / functions) Hit Total Coverage
Test: PostgreSQL 13devel Lines: 259 294 88.1 %
Date: 2019-11-13 22:07:24 Functions: 24 25 96.0 %
Legend: Lines: hit not hit

          Line data    Source code
       1             : /*-------------------------------------------------------------------------
       2             :  *
       3             :  * gistutil.c
       4             :  *    utilities routines for the postgres GiST index access method.
       5             :  *
       6             :  *
       7             :  * Portions Copyright (c) 1996-2019, PostgreSQL Global Development Group
       8             :  * Portions Copyright (c) 1994, Regents of the University of California
       9             :  *
      10             :  * IDENTIFICATION
      11             :  *          src/backend/access/gist/gistutil.c
      12             :  *-------------------------------------------------------------------------
      13             :  */
      14             : #include "postgres.h"
      15             : 
      16             : #include <math.h>
      17             : 
      18             : #include "access/gist_private.h"
      19             : #include "access/htup_details.h"
      20             : #include "access/reloptions.h"
      21             : #include "catalog/pg_opclass.h"
      22             : #include "storage/indexfsm.h"
      23             : #include "storage/lmgr.h"
      24             : #include "utils/float.h"
      25             : #include "utils/lsyscache.h"
      26             : #include "utils/snapmgr.h"
      27             : #include "utils/syscache.h"
      28             : 
      29             : /*
      30             :  * Write itup vector to page, has no control of free space.
      31             :  */
      32             : void
      33      668366 : gistfillbuffer(Page page, IndexTuple *itup, int len, OffsetNumber off)
      34             : {
      35      668366 :     OffsetNumber l = InvalidOffsetNumber;
      36             :     int         i;
      37             : 
      38      668366 :     if (off == InvalidOffsetNumber)
      39     1336428 :         off = (PageIsEmpty(page)) ? FirstOffsetNumber :
      40      668062 :             OffsetNumberNext(PageGetMaxOffsetNumber(page));
      41             : 
      42     1346106 :     for (i = 0; i < len; i++)
      43             :     {
      44      677740 :         Size        sz = IndexTupleSize(itup[i]);
      45             : 
      46      677740 :         l = PageAddItem(page, (Item) itup[i], sz, off, false, false);
      47      677740 :         if (l == InvalidOffsetNumber)
      48           0 :             elog(ERROR, "failed to add item to GiST index page, item %d out of %d, size %d bytes",
      49             :                  i, len, (int) sz);
      50      677740 :         off++;
      51             :     }
      52      668366 : }
      53             : 
      54             : /*
      55             :  * Check space for itup vector on page
      56             :  */
      57             : bool
      58     1109906 : gistnospace(Page page, IndexTuple *itvec, int len, OffsetNumber todelete, Size freespace)
      59             : {
      60     1109906 :     unsigned int size = freespace,
      61     1109906 :                 deleted = 0;
      62             :     int         i;
      63             : 
      64     2229308 :     for (i = 0; i < len; i++)
      65     1119402 :         size += IndexTupleSize(itvec[i]) + sizeof(ItemIdData);
      66             : 
      67     1109906 :     if (todelete != InvalidOffsetNumber)
      68             :     {
      69      441306 :         IndexTuple  itup = (IndexTuple) PageGetItem(page, PageGetItemId(page, todelete));
      70             : 
      71      441306 :         deleted = IndexTupleSize(itup) + sizeof(ItemIdData);
      72             :     }
      73             : 
      74     1109906 :     return (PageGetFreeSpace(page) + deleted < size);
      75             : }
      76             : 
      77             : bool
      78       19480 : gistfitpage(IndexTuple *itvec, int len)
      79             : {
      80             :     int         i;
      81       19480 :     Size        size = 0;
      82             : 
      83     1290514 :     for (i = 0; i < len; i++)
      84     1271034 :         size += IndexTupleSize(itvec[i]) + sizeof(ItemIdData);
      85             : 
      86             :     /* TODO: Consider fillfactor */
      87       19480 :     return (size <= GiSTPageSize);
      88             : }
      89             : 
      90             : /*
      91             :  * Read buffer into itup vector
      92             :  */
      93             : IndexTuple *
      94        9740 : gistextractpage(Page page, int *len /* out */ )
      95             : {
      96             :     OffsetNumber i,
      97             :                 maxoff;
      98             :     IndexTuple *itvec;
      99             : 
     100        9740 :     maxoff = PageGetMaxOffsetNumber(page);
     101        9740 :     *len = maxoff;
     102        9740 :     itvec = palloc(sizeof(IndexTuple) * maxoff);
     103     1271044 :     for (i = FirstOffsetNumber; i <= maxoff; i = OffsetNumberNext(i))
     104     1261304 :         itvec[i - FirstOffsetNumber] = (IndexTuple) PageGetItem(page, PageGetItemId(page, i));
     105             : 
     106        9740 :     return itvec;
     107             : }
     108             : 
     109             : /*
     110             :  * join two vectors into one
     111             :  */
     112             : IndexTuple *
     113        9740 : gistjoinvector(IndexTuple *itvec, int *len, IndexTuple *additvec, int addlen)
     114             : {
     115        9740 :     itvec = (IndexTuple *) repalloc((void *) itvec, sizeof(IndexTuple) * ((*len) + addlen));
     116        9740 :     memmove(&itvec[*len], additvec, sizeof(IndexTuple) * addlen);
     117        9740 :     *len += addlen;
     118        9740 :     return itvec;
     119             : }
     120             : 
     121             : /*
     122             :  * make plain IndexTuple vector
     123             :  */
     124             : 
     125             : IndexTupleData *
     126       19724 : gistfillitupvec(IndexTuple *vec, int veclen, int *memlen)
     127             : {
     128             :     char       *ptr,
     129             :                *ret;
     130             :     int         i;
     131             : 
     132       19724 :     *memlen = 0;
     133             : 
     134     1291246 :     for (i = 0; i < veclen; i++)
     135     1271522 :         *memlen += IndexTupleSize(vec[i]);
     136             : 
     137       19724 :     ptr = ret = palloc(*memlen);
     138             : 
     139     1291246 :     for (i = 0; i < veclen; i++)
     140             :     {
     141     1271522 :         memcpy(ptr, vec[i], IndexTupleSize(vec[i]));
     142     1271522 :         ptr += IndexTupleSize(vec[i]);
     143             :     }
     144             : 
     145       19724 :     return (IndexTupleData *) ret;
     146             : }
     147             : 
     148             : /*
     149             :  * Make unions of keys in IndexTuple vector (one union datum per index column).
     150             :  * Union Datums are returned into the attr/isnull arrays.
     151             :  * Resulting Datums aren't compressed.
     152             :  */
     153             : void
     154        1932 : gistMakeUnionItVec(GISTSTATE *giststate, IndexTuple *itvec, int len,
     155             :                    Datum *attr, bool *isnull)
     156             : {
     157             :     int         i;
     158             :     GistEntryVector *evec;
     159             :     int         attrsize;
     160             : 
     161        1932 :     evec = (GistEntryVector *) palloc((len + 2) * sizeof(GISTENTRY) + GEVHDRSZ);
     162             : 
     163        5640 :     for (i = 0; i < giststate->nonLeafTupdesc->natts; i++)
     164             :     {
     165             :         int         j;
     166             : 
     167             :         /* Collect non-null datums for this column */
     168        3708 :         evec->n = 0;
     169      200624 :         for (j = 0; j < len; j++)
     170             :         {
     171             :             Datum       datum;
     172             :             bool        IsNull;
     173             : 
     174      196916 :             datum = index_getattr(itvec[j], i + 1, giststate->leafTupdesc,
     175             :                                   &IsNull);
     176      196916 :             if (IsNull)
     177        1414 :                 continue;
     178             : 
     179      391004 :             gistdentryinit(giststate, i,
     180      195502 :                            evec->vector + evec->n,
     181             :                            datum,
     182             :                            NULL, NULL, (OffsetNumber) 0,
     183             :                            false, IsNull);
     184      195502 :             evec->n++;
     185             :         }
     186             : 
     187             :         /* If this column was all NULLs, the union is NULL */
     188        3708 :         if (evec->n == 0)
     189             :         {
     190          82 :             attr[i] = (Datum) 0;
     191          82 :             isnull[i] = true;
     192             :         }
     193             :         else
     194             :         {
     195        3626 :             if (evec->n == 1)
     196             :             {
     197             :                 /* unionFn may expect at least two inputs */
     198           8 :                 evec->n = 2;
     199           8 :                 evec->vector[1] = evec->vector[0];
     200             :             }
     201             : 
     202             :             /* Make union and store in attr array */
     203        3626 :             attr[i] = FunctionCall2Coll(&giststate->unionFn[i],
     204             :                                         giststate->supportCollation[i],
     205             :                                         PointerGetDatum(evec),
     206             :                                         PointerGetDatum(&attrsize));
     207             : 
     208        3626 :             isnull[i] = false;
     209             :         }
     210             :     }
     211        1932 : }
     212             : 
     213             : /*
     214             :  * Return an IndexTuple containing the result of applying the "union"
     215             :  * method to the specified IndexTuple vector.
     216             :  */
     217             : IndexTuple
     218           0 : gistunion(Relation r, IndexTuple *itvec, int len, GISTSTATE *giststate)
     219             : {
     220             :     Datum       attr[INDEX_MAX_KEYS];
     221             :     bool        isnull[INDEX_MAX_KEYS];
     222             : 
     223           0 :     gistMakeUnionItVec(giststate, itvec, len, attr, isnull);
     224             : 
     225           0 :     return gistFormTuple(giststate, r, attr, isnull, false);
     226             : }
     227             : 
     228             : /*
     229             :  * makes union of two key
     230             :  */
     231             : void
     232      828392 : gistMakeUnionKey(GISTSTATE *giststate, int attno,
     233             :                  GISTENTRY *entry1, bool isnull1,
     234             :                  GISTENTRY *entry2, bool isnull2,
     235             :                  Datum *dst, bool *dstisnull)
     236             : {
     237             :     /* we need a GistEntryVector with room for exactly 2 elements */
     238             :     union
     239             :     {
     240             :         GistEntryVector gev;
     241             :         char        padding[2 * sizeof(GISTENTRY) + GEVHDRSZ];
     242             :     }           storage;
     243      828392 :     GistEntryVector *evec = &storage.gev;
     244             :     int         dstsize;
     245             : 
     246      828392 :     evec->n = 2;
     247             : 
     248      828392 :     if (isnull1 && isnull2)
     249             :     {
     250        7314 :         *dstisnull = true;
     251        7314 :         *dst = (Datum) 0;
     252             :     }
     253             :     else
     254             :     {
     255      821078 :         if (isnull1 == false && isnull2 == false)
     256             :         {
     257      820828 :             evec->vector[0] = *entry1;
     258      820828 :             evec->vector[1] = *entry2;
     259             :         }
     260         250 :         else if (isnull1 == false)
     261             :         {
     262         250 :             evec->vector[0] = *entry1;
     263         250 :             evec->vector[1] = *entry1;
     264             :         }
     265             :         else
     266             :         {
     267           0 :             evec->vector[0] = *entry2;
     268           0 :             evec->vector[1] = *entry2;
     269             :         }
     270             : 
     271      821078 :         *dstisnull = false;
     272      821078 :         *dst = FunctionCall2Coll(&giststate->unionFn[attno],
     273             :                                  giststate->supportCollation[attno],
     274             :                                  PointerGetDatum(evec),
     275             :                                  PointerGetDatum(&dstsize));
     276             :     }
     277      828392 : }
     278             : 
     279             : bool
     280      760704 : gistKeyIsEQ(GISTSTATE *giststate, int attno, Datum a, Datum b)
     281             : {
     282             :     bool        result;
     283             : 
     284      760704 :     FunctionCall3Coll(&giststate->equalFn[attno],
     285             :                       giststate->supportCollation[attno],
     286             :                       a, b,
     287             :                       PointerGetDatum(&result));
     288      760704 :     return result;
     289             : }
     290             : 
     291             : /*
     292             :  * Decompress all keys in tuple
     293             :  */
     294             : void
     295     2288526 : gistDeCompressAtt(GISTSTATE *giststate, Relation r, IndexTuple tuple, Page p,
     296             :                   OffsetNumber o, GISTENTRY *attdata, bool *isnull)
     297             : {
     298             :     int         i;
     299             : 
     300     4773690 :     for (i = 0; i < IndexRelationGetNumberOfKeyAttributes(r); i++)
     301             :     {
     302             :         Datum       datum;
     303             : 
     304     2485164 :         datum = index_getattr(tuple, i + 1, giststate->leafTupdesc, &isnull[i]);
     305     2485164 :         gistdentryinit(giststate, i, &attdata[i],
     306             :                        datum, r, p, o,
     307     2485164 :                        false, isnull[i]);
     308             :     }
     309     2288526 : }
     310             : 
     311             : /*
     312             :  * Forms union of oldtup and addtup, if union == oldtup then return NULL
     313             :  */
     314             : IndexTuple
     315      762842 : gistgetadjusted(Relation r, IndexTuple oldtup, IndexTuple addtup, GISTSTATE *giststate)
     316             : {
     317      762842 :     bool        neednew = false;
     318             :     GISTENTRY   oldentries[INDEX_MAX_KEYS],
     319             :                 addentries[INDEX_MAX_KEYS];
     320             :     bool        oldisnull[INDEX_MAX_KEYS],
     321             :                 addisnull[INDEX_MAX_KEYS];
     322             :     Datum       attr[INDEX_MAX_KEYS];
     323             :     bool        isnull[INDEX_MAX_KEYS];
     324      762842 :     IndexTuple  newtup = NULL;
     325             :     int         i;
     326             : 
     327      762842 :     gistDeCompressAtt(giststate, r, oldtup, NULL,
     328             :                       (OffsetNumber) 0, oldentries, oldisnull);
     329             : 
     330      762842 :     gistDeCompressAtt(giststate, r, addtup, NULL,
     331             :                       (OffsetNumber) 0, addentries, addisnull);
     332             : 
     333     1591230 :     for (i = 0; i < IndexRelationGetNumberOfKeyAttributes(r); i++)
     334             :     {
     335     4970328 :         gistMakeUnionKey(giststate, i,
     336     1656776 :                          oldentries + i, oldisnull[i],
     337     1656776 :                          addentries + i, addisnull[i],
     338      828388 :                          attr + i, isnull + i);
     339             : 
     340      828388 :         if (neednew)
     341             :             /* we already need new key, so we can skip check */
     342       61004 :             continue;
     343             : 
     344      767384 :         if (isnull[i])
     345             :             /* union of key may be NULL if and only if both keys are NULL */
     346        7314 :             continue;
     347             : 
     348      760070 :         if (!addisnull[i])
     349             :         {
     350     1519640 :             if (oldisnull[i] ||
     351      759820 :                 !gistKeyIsEQ(giststate, i, oldentries[i].key, attr[i]))
     352      431810 :                 neednew = true;
     353             :         }
     354             :     }
     355             : 
     356      762842 :     if (neednew)
     357             :     {
     358             :         /* need to update key */
     359      431810 :         newtup = gistFormTuple(giststate, r, attr, isnull, false);
     360      431810 :         newtup->t_tid = oldtup->t_tid;
     361             :     }
     362             : 
     363      762842 :     return newtup;
     364             : }
     365             : 
     366             : /*
     367             :  * Search an upper index page for the entry with lowest penalty for insertion
     368             :  * of the new index key contained in "it".
     369             :  *
     370             :  * Returns the index of the page entry to insert into.
     371             :  */
     372             : OffsetNumber
     373      762842 : gistchoose(Relation r, Page p, IndexTuple it,   /* it has compressed entry */
     374             :            GISTSTATE *giststate)
     375             : {
     376             :     OffsetNumber result;
     377             :     OffsetNumber maxoff;
     378             :     OffsetNumber i;
     379             :     float       best_penalty[INDEX_MAX_KEYS];
     380             :     GISTENTRY   entry,
     381             :                 identry[INDEX_MAX_KEYS];
     382             :     bool        isnull[INDEX_MAX_KEYS];
     383             :     int         keep_current_best;
     384             : 
     385             :     Assert(!GistPageIsLeaf(p));
     386             : 
     387      762842 :     gistDeCompressAtt(giststate, r,
     388             :                       it, NULL, (OffsetNumber) 0,
     389             :                       identry, isnull);
     390             : 
     391             :     /* we'll return FirstOffsetNumber if page is empty (shouldn't happen) */
     392      762842 :     result = FirstOffsetNumber;
     393             : 
     394             :     /*
     395             :      * The index may have multiple columns, and there's a penalty value for
     396             :      * each column.  The penalty associated with a column that appears earlier
     397             :      * in the index definition is strictly more important than the penalty of
     398             :      * a column that appears later in the index definition.
     399             :      *
     400             :      * best_penalty[j] is the best penalty we have seen so far for column j,
     401             :      * or -1 when we haven't yet examined column j.  Array entries to the
     402             :      * right of the first -1 are undefined.
     403             :      */
     404      762842 :     best_penalty[0] = -1;
     405             : 
     406             :     /*
     407             :      * If we find a tuple that's exactly as good as the currently best one, we
     408             :      * could use either one.  When inserting a lot of tuples with the same or
     409             :      * similar keys, it's preferable to descend down the same path when
     410             :      * possible, as that's more cache-friendly.  On the other hand, if all
     411             :      * inserts land on the same leaf page after a split, we're never going to
     412             :      * insert anything to the other half of the split, and will end up using
     413             :      * only 50% of the available space.  Distributing the inserts evenly would
     414             :      * lead to better space usage, but that hurts cache-locality during
     415             :      * insertion.  To get the best of both worlds, when we find a tuple that's
     416             :      * exactly as good as the previous best, choose randomly whether to stick
     417             :      * to the old best, or use the new one.  Once we decide to stick to the
     418             :      * old best, we keep sticking to it for any subsequent equally good tuples
     419             :      * we might find.  This favors tuples with low offsets, but still allows
     420             :      * some inserts to go to other equally-good subtrees.
     421             :      *
     422             :      * keep_current_best is -1 if we haven't yet had to make a random choice
     423             :      * whether to keep the current best tuple.  If we have done so, and
     424             :      * decided to keep it, keep_current_best is 1; if we've decided to
     425             :      * replace, keep_current_best is 0.  (This state will be reset to -1 as
     426             :      * soon as we've made the replacement, but sometimes we make the choice in
     427             :      * advance of actually finding a replacement best tuple.)
     428             :      */
     429      762842 :     keep_current_best = -1;
     430             : 
     431             :     /*
     432             :      * Loop over tuples on page.
     433             :      */
     434      762842 :     maxoff = PageGetMaxOffsetNumber(p);
     435             :     Assert(maxoff >= FirstOffsetNumber);
     436             : 
     437    27007860 :     for (i = FirstOffsetNumber; i <= maxoff; i = OffsetNumberNext(i))
     438             :     {
     439    26434730 :         IndexTuple  itup = (IndexTuple) PageGetItem(p, PageGetItemId(p, i));
     440             :         bool        zero_penalty;
     441             :         int         j;
     442             : 
     443    26434730 :         zero_penalty = true;
     444             : 
     445             :         /* Loop over index attributes. */
     446    50094660 :         for (j = 0; j < IndexRelationGetNumberOfKeyAttributes(r); j++)
     447             :         {
     448             :             Datum       datum;
     449             :             float       usize;
     450             :             bool        IsNull;
     451             : 
     452             :             /* Compute penalty for this column. */
     453    28897448 :             datum = index_getattr(itup, j + 1, giststate->leafTupdesc,
     454             :                                   &IsNull);
     455    28897448 :             gistdentryinit(giststate, j, &entry, datum, r, p, i,
     456             :                            false, IsNull);
     457    28897448 :             usize = gistpenalty(giststate, j, &entry, IsNull,
     458    28897448 :                                 &identry[j], isnull[j]);
     459    28897448 :             if (usize > 0)
     460    28509392 :                 zero_penalty = false;
     461             : 
     462    28897448 :             if (best_penalty[j] < 0 || usize < best_penalty[j])
     463             :             {
     464             :                 /*
     465             :                  * New best penalty for column.  Tentatively select this tuple
     466             :                  * as the target, and record the best penalty.  Then reset the
     467             :                  * next column's penalty to "unknown" (and indirectly, the
     468             :                  * same for all the ones to its right).  This will force us to
     469             :                  * adopt this tuple's penalty values as the best for all the
     470             :                  * remaining columns during subsequent loop iterations.
     471             :                  */
     472    21434132 :                 result = i;
     473    21434132 :                 best_penalty[j] = usize;
     474             : 
     475    21434132 :                 if (j < IndexRelationGetNumberOfKeyAttributes(r) - 1)
     476     2459288 :                     best_penalty[j + 1] = -1;
     477             : 
     478             :                 /* we have new best, so reset keep-it decision */
     479    21434132 :                 keep_current_best = -1;
     480             :             }
     481     7463316 :             else if (best_penalty[j] == usize)
     482             :             {
     483             :                 /*
     484             :                  * The current tuple is exactly as good for this column as the
     485             :                  * best tuple seen so far.  The next iteration of this loop
     486             :                  * will compare the next column.
     487             :                  */
     488             :             }
     489             :             else
     490             :             {
     491             :                 /*
     492             :                  * The current tuple is worse for this column than the best
     493             :                  * tuple seen so far.  Skip the remaining columns and move on
     494             :                  * to the next tuple, if any.
     495             :                  */
     496     5237518 :                 zero_penalty = false;   /* so outer loop won't exit */
     497     5237518 :                 break;
     498             :             }
     499             :         }
     500             : 
     501             :         /*
     502             :          * If we looped past the last column, and did not update "result",
     503             :          * then this tuple is exactly as good as the prior best tuple.
     504             :          */
     505    26434730 :         if (j == IndexRelationGetNumberOfKeyAttributes(r) && result != i)
     506             :         {
     507     2222368 :             if (keep_current_best == -1)
     508             :             {
     509             :                 /* we didn't make the random choice yet for this old best */
     510      173620 :                 keep_current_best = (random() <= (MAX_RANDOM_VALUE / 2)) ? 1 : 0;
     511             :             }
     512     2222368 :             if (keep_current_best == 0)
     513             :             {
     514             :                 /* we choose to use the new tuple */
     515      165248 :                 result = i;
     516             :                 /* choose again if there are even more exactly-as-good ones */
     517      165248 :                 keep_current_best = -1;
     518             :             }
     519             :         }
     520             : 
     521             :         /*
     522             :          * If we find a tuple with zero penalty for all columns, and we've
     523             :          * decided we don't want to search for another tuple with equal
     524             :          * penalty, there's no need to examine remaining tuples; just break
     525             :          * out of the loop and return it.
     526             :          */
     527    26434730 :         if (zero_penalty)
     528             :         {
     529      380100 :             if (keep_current_best == -1)
     530             :             {
     531             :                 /* we didn't make the random choice yet for this old best */
     532      380100 :                 keep_current_best = (random() <= (MAX_RANDOM_VALUE / 2)) ? 1 : 0;
     533             :             }
     534      380100 :             if (keep_current_best == 1)
     535      189712 :                 break;
     536             :         }
     537             :     }
     538             : 
     539      762842 :     return result;
     540             : }
     541             : 
     542             : /*
     543             :  * initialize a GiST entry with a decompressed version of key
     544             :  */
     545             : void
     546    33640560 : gistdentryinit(GISTSTATE *giststate, int nkey, GISTENTRY *e,
     547             :                Datum k, Relation r, Page pg, OffsetNumber o,
     548             :                bool l, bool isNull)
     549             : {
     550    33640560 :     if (!isNull)
     551             :     {
     552             :         GISTENTRY  *dep;
     553             : 
     554    33516650 :         gistentryinit(*e, k, r, pg, o, l);
     555             : 
     556             :         /* there may not be a decompress function in opclass */
     557    33516650 :         if (!OidIsValid(giststate->decompressFn[nkey].fn_oid))
     558    29465488 :             return;
     559             : 
     560     4051162 :         dep = (GISTENTRY *)
     561     4051162 :             DatumGetPointer(FunctionCall1Coll(&giststate->decompressFn[nkey],
     562             :                                               giststate->supportCollation[nkey],
     563             :                                               PointerGetDatum(e)));
     564             :         /* decompressFn may just return the given pointer */
     565     4051162 :         if (dep != e)
     566      346270 :             gistentryinit(*e, dep->key, dep->rel, dep->page, dep->offset,
     567             :                           dep->leafkey);
     568             :     }
     569             :     else
     570      123910 :         gistentryinit(*e, (Datum) 0, r, pg, o, l);
     571             : }
     572             : 
     573             : IndexTuple
     574     1119902 : gistFormTuple(GISTSTATE *giststate, Relation r,
     575             :               Datum attdata[], bool isnull[], bool isleaf)
     576             : {
     577             :     Datum       compatt[INDEX_MAX_KEYS];
     578             :     int         i;
     579             :     IndexTuple  res;
     580             : 
     581             :     /*
     582             :      * Call the compress method on each attribute.
     583             :      */
     584     2348030 :     for (i = 0; i < IndexRelationGetNumberOfKeyAttributes(r); i++)
     585             :     {
     586     1228128 :         if (isnull[i])
     587        8284 :             compatt[i] = (Datum) 0;
     588             :         else
     589             :         {
     590             :             GISTENTRY   centry;
     591             :             GISTENTRY  *cep;
     592             : 
     593     1219844 :             gistentryinit(centry, attdata[i], r, NULL, (OffsetNumber) 0,
     594             :                           isleaf);
     595             :             /* there may not be a compress function in opclass */
     596     1219844 :             if (OidIsValid(giststate->compressFn[i].fn_oid))
     597      889778 :                 cep = (GISTENTRY *)
     598      889778 :                     DatumGetPointer(FunctionCall1Coll(&giststate->compressFn[i],
     599             :                                                       giststate->supportCollation[i],
     600             :                                                       PointerGetDatum(&centry)));
     601             :             else
     602      330066 :                 cep = &centry;
     603     1219844 :             compatt[i] = cep->key;
     604             :         }
     605             :     }
     606             : 
     607     1119902 :     if (isleaf)
     608             :     {
     609             :         /*
     610             :          * Emplace each included attribute if any.
     611             :          */
     612      861372 :         for (; i < r->rd_att->natts; i++)
     613             :         {
     614      192760 :             if (isnull[i])
     615           0 :                 compatt[i] = (Datum) 0;
     616             :             else
     617      192760 :                 compatt[i] = attdata[i];
     618             :         }
     619             :     }
     620             : 
     621     1119902 :     res = index_form_tuple(isleaf ? giststate->leafTupdesc :
     622             :                            giststate->nonLeafTupdesc,
     623             :                            compatt, isnull);
     624             : 
     625             :     /*
     626             :      * The offset number on tuples on internal pages is unused. For historical
     627             :      * reasons, it is set to 0xffff.
     628             :      */
     629     1119902 :     ItemPointerSetOffsetNumber(&(res->t_tid), 0xffff);
     630     1119902 :     return res;
     631             : }
     632             : 
     633             : /*
     634             :  * initialize a GiST entry with fetched value in key field
     635             :  */
     636             : static Datum
     637       45170 : gistFetchAtt(GISTSTATE *giststate, int nkey, Datum k, Relation r)
     638             : {
     639             :     GISTENTRY   fentry;
     640             :     GISTENTRY  *fep;
     641             : 
     642       45170 :     gistentryinit(fentry, k, r, NULL, (OffsetNumber) 0, false);
     643             : 
     644       45170 :     fep = (GISTENTRY *)
     645       45170 :         DatumGetPointer(FunctionCall1Coll(&giststate->fetchFn[nkey],
     646             :                                           giststate->supportCollation[nkey],
     647             :                                           PointerGetDatum(&fentry)));
     648             : 
     649             :     /* fetchFn set 'key', return it to the caller */
     650       45170 :     return fep->key;
     651             : }
     652             : 
     653             : /*
     654             :  * Fetch all keys in tuple.
     655             :  * Returns a new HeapTuple containing the originally-indexed data.
     656             :  */
     657             : HeapTuple
     658      193320 : gistFetchTuple(GISTSTATE *giststate, Relation r, IndexTuple tuple)
     659             : {
     660      193320 :     MemoryContext oldcxt = MemoryContextSwitchTo(giststate->tempCxt);
     661             :     Datum       fetchatt[INDEX_MAX_KEYS];
     662             :     bool        isnull[INDEX_MAX_KEYS];
     663             :     int         i;
     664             : 
     665      386640 :     for (i = 0; i < IndexRelationGetNumberOfKeyAttributes(r); i++)
     666             :     {
     667             :         Datum       datum;
     668             : 
     669      193320 :         datum = index_getattr(tuple, i + 1, giststate->leafTupdesc, &isnull[i]);
     670             : 
     671      193320 :         if (giststate->fetchFn[i].fn_oid != InvalidOid)
     672             :         {
     673       45178 :             if (!isnull[i])
     674       45170 :                 fetchatt[i] = gistFetchAtt(giststate, i, datum, r);
     675             :             else
     676           8 :                 fetchatt[i] = (Datum) 0;
     677             :         }
     678      148142 :         else if (giststate->compressFn[i].fn_oid == InvalidOid)
     679             :         {
     680             :             /*
     681             :              * If opclass does not provide compress method that could change
     682             :              * original value, att is necessarily stored in original form.
     683             :              */
     684      148142 :             if (!isnull[i])
     685      145918 :                 fetchatt[i] = datum;
     686             :             else
     687        2224 :                 fetchatt[i] = (Datum) 0;
     688             :         }
     689             :         else
     690             :         {
     691             :             /*
     692             :              * Index-only scans not supported for this column. Since the
     693             :              * planner chose an index-only scan anyway, it is not interested
     694             :              * in this column, and we can replace it with a NULL.
     695             :              */
     696           0 :             isnull[i] = true;
     697           0 :             fetchatt[i] = (Datum) 0;
     698             :         }
     699             :     }
     700             : 
     701             :     /*
     702             :      * Get each included attribute.
     703             :      */
     704      193320 :     for (; i < r->rd_att->natts; i++)
     705             :     {
     706           0 :         fetchatt[i] = index_getattr(tuple, i + 1, giststate->leafTupdesc,
     707             :                                     &isnull[i]);
     708             :     }
     709      193320 :     MemoryContextSwitchTo(oldcxt);
     710             : 
     711      193320 :     return heap_form_tuple(giststate->fetchTupdesc, fetchatt, isnull);
     712             : }
     713             : 
     714             : float
     715    28981276 : gistpenalty(GISTSTATE *giststate, int attno,
     716             :             GISTENTRY *orig, bool isNullOrig,
     717             :             GISTENTRY *add, bool isNullAdd)
     718             : {
     719    28981276 :     float       penalty = 0.0;
     720             : 
     721    57962552 :     if (giststate->penaltyFn[attno].fn_strict == false ||
     722    57862454 :         (isNullOrig == false && isNullAdd == false))
     723             :     {
     724    28841674 :         FunctionCall3Coll(&giststate->penaltyFn[attno],
     725             :                           giststate->supportCollation[attno],
     726             :                           PointerGetDatum(orig),
     727             :                           PointerGetDatum(add),
     728             :                           PointerGetDatum(&penalty));
     729             :         /* disallow negative or NaN penalty */
     730    57683348 :         if (isnan(penalty) || penalty < 0.0)
     731        4758 :             penalty = 0.0;
     732             :     }
     733      139602 :     else if (isNullOrig && isNullAdd)
     734        7314 :         penalty = 0.0;
     735             :     else
     736             :     {
     737             :         /* try to prevent mixing null and non-null values */
     738      132288 :         penalty = get_float4_infinity();
     739             :     }
     740             : 
     741    28981276 :     return penalty;
     742             : }
     743             : 
     744             : /*
     745             :  * Initialize a new index page
     746             :  */
     747             : void
     748       10328 : GISTInitBuffer(Buffer b, uint32 f)
     749             : {
     750             :     GISTPageOpaque opaque;
     751             :     Page        page;
     752             :     Size        pageSize;
     753             : 
     754       10328 :     pageSize = BufferGetPageSize(b);
     755       10328 :     page = BufferGetPage(b);
     756       10328 :     PageInit(page, pageSize, sizeof(GISTPageOpaqueData));
     757             : 
     758       10328 :     opaque = GistPageGetOpaque(page);
     759             :     /* page was already zeroed by PageInit, so this is not needed: */
     760             :     /* memset(&(opaque->nsn), 0, sizeof(GistNSN)); */
     761       10328 :     opaque->rightlink = InvalidBlockNumber;
     762       10328 :     opaque->flags = f;
     763       10328 :     opaque->gist_page_id = GIST_PAGE_ID;
     764       10328 : }
     765             : 
     766             : /*
     767             :  * Verify that a freshly-read page looks sane.
     768             :  */
     769             : void
     770     1454010 : gistcheckpage(Relation rel, Buffer buf)
     771             : {
     772     1454010 :     Page        page = BufferGetPage(buf);
     773             : 
     774             :     /*
     775             :      * ReadBuffer verifies that every newly-read page passes
     776             :      * PageHeaderIsValid, which means it either contains a reasonably sane
     777             :      * page header or is all-zero.  We have to defend against the all-zero
     778             :      * case, however.
     779             :      */
     780     1454010 :     if (PageIsNew(page))
     781           0 :         ereport(ERROR,
     782             :                 (errcode(ERRCODE_INDEX_CORRUPTED),
     783             :                  errmsg("index \"%s\" contains unexpected zero page at block %u",
     784             :                         RelationGetRelationName(rel),
     785             :                         BufferGetBlockNumber(buf)),
     786             :                  errhint("Please REINDEX it.")));
     787             : 
     788             :     /*
     789             :      * Additionally check that the special area looks sane.
     790             :      */
     791     1454010 :     if (PageGetSpecialSize(page) != MAXALIGN(sizeof(GISTPageOpaqueData)))
     792           0 :         ereport(ERROR,
     793             :                 (errcode(ERRCODE_INDEX_CORRUPTED),
     794             :                  errmsg("index \"%s\" contains corrupted page at block %u",
     795             :                         RelationGetRelationName(rel),
     796             :                         BufferGetBlockNumber(buf)),
     797             :                  errhint("Please REINDEX it.")));
     798     1454010 : }
     799             : 
     800             : 
     801             : /*
     802             :  * Allocate a new page (either by recycling, or by extending the index file)
     803             :  *
     804             :  * The returned buffer is already pinned and exclusive-locked
     805             :  *
     806             :  * Caller is responsible for initializing the page by calling GISTInitBuffer
     807             :  */
     808             : Buffer
     809       10328 : gistNewBuffer(Relation r)
     810             : {
     811             :     Buffer      buffer;
     812             :     bool        needLock;
     813             : 
     814             :     /* First, try to get a page from FSM */
     815             :     for (;;)
     816           0 :     {
     817       10328 :         BlockNumber blkno = GetFreeIndexPage(r);
     818             : 
     819       10328 :         if (blkno == InvalidBlockNumber)
     820       10328 :             break;              /* nothing left in FSM */
     821             : 
     822           0 :         buffer = ReadBuffer(r, blkno);
     823             : 
     824             :         /*
     825             :          * We have to guard against the possibility that someone else already
     826             :          * recycled this page; the buffer may be locked if so.
     827             :          */
     828           0 :         if (ConditionalLockBuffer(buffer))
     829             :         {
     830           0 :             Page        page = BufferGetPage(buffer);
     831             : 
     832             :             /*
     833             :              * If the page was never initialized, it's OK to use.
     834             :              */
     835           0 :             if (PageIsNew(page))
     836           0 :                 return buffer;
     837             : 
     838           0 :             gistcheckpage(r, buffer);
     839             : 
     840             :             /*
     841             :              * Otherwise, recycle it if deleted, and too old to have any
     842             :              * processes interested in it.
     843             :              */
     844           0 :             if (gistPageRecyclable(page))
     845             :             {
     846             :                 /*
     847             :                  * If we are generating WAL for Hot Standby then create a WAL
     848             :                  * record that will allow us to conflict with queries running
     849             :                  * on standby, in case they have snapshots older than the
     850             :                  * page's deleteXid.
     851             :                  */
     852           0 :                 if (XLogStandbyInfoActive() && RelationNeedsWAL(r))
     853           0 :                     gistXLogPageReuse(r, blkno, GistPageGetDeleteXid(page));
     854             : 
     855           0 :                 return buffer;
     856             :             }
     857             : 
     858           0 :             LockBuffer(buffer, GIST_UNLOCK);
     859             :         }
     860             : 
     861             :         /* Can't use it, so release buffer and try again */
     862           0 :         ReleaseBuffer(buffer);
     863             :     }
     864             : 
     865             :     /* Must extend the file */
     866       10328 :     needLock = !RELATION_IS_LOCAL(r);
     867             : 
     868       10328 :     if (needLock)
     869        4046 :         LockRelationForExtension(r, ExclusiveLock);
     870             : 
     871       10328 :     buffer = ReadBuffer(r, P_NEW);
     872       10328 :     LockBuffer(buffer, GIST_EXCLUSIVE);
     873             : 
     874       10328 :     if (needLock)
     875        4046 :         UnlockRelationForExtension(r, ExclusiveLock);
     876             : 
     877       10328 :     return buffer;
     878             : }
     879             : 
     880             : /* Can this page be recycled yet? */
     881             : bool
     882        3388 : gistPageRecyclable(Page page)
     883             : {
     884        3388 :     if (PageIsNew(page))
     885           0 :         return true;
     886        3388 :     if (GistPageIsDeleted(page))
     887             :     {
     888             :         /*
     889             :          * The page was deleted, but when? If it was just deleted, a scan
     890             :          * might have seen the downlink to it, and will read the page later.
     891             :          * As long as that can happen, we must keep the deleted page around as
     892             :          * a tombstone.
     893             :          *
     894             :          * Compare the deletion XID with RecentGlobalXmin. If deleteXid <
     895             :          * RecentGlobalXmin, then no scan that's still in progress could have
     896             :          * seen its downlink, and we can recycle it.
     897             :          */
     898           0 :         FullTransactionId deletexid_full = GistPageGetDeleteXid(page);
     899           0 :         FullTransactionId recentxmin_full = GetFullRecentGlobalXmin();
     900             : 
     901           0 :         if (FullTransactionIdPrecedes(deletexid_full, recentxmin_full))
     902           0 :             return true;
     903             :     }
     904        3388 :     return false;
     905             : }
     906             : 
     907             : bytea *
     908         100 : gistoptions(Datum reloptions, bool validate)
     909             : {
     910             :     static const relopt_parse_elt tab[] = {
     911             :         {"fillfactor", RELOPT_TYPE_INT, offsetof(GiSTOptions, fillfactor)},
     912             :         {"buffering", RELOPT_TYPE_ENUM, offsetof(GiSTOptions, buffering_mode)}
     913             :     };
     914             : 
     915         100 :     return (bytea *) build_reloptions(reloptions, validate,
     916             :                                       RELOPT_KIND_GIST,
     917             :                                       sizeof(GiSTOptions),
     918             :                                       tab, lengthof(tab));
     919             : }
     920             : 
     921             : /*
     922             :  *  gistproperty() -- Check boolean properties of indexes.
     923             :  *
     924             :  * This is optional for most AMs, but is required for GiST because the core
     925             :  * property code doesn't support AMPROP_DISTANCE_ORDERABLE.  We also handle
     926             :  * AMPROP_RETURNABLE here to save opening the rel to call gistcanreturn.
     927             :  */
     928             : bool
     929         312 : gistproperty(Oid index_oid, int attno,
     930             :              IndexAMProperty prop, const char *propname,
     931             :              bool *res, bool *isnull)
     932             : {
     933             :     Oid         opclass,
     934             :                 opfamily,
     935             :                 opcintype;
     936             :     int16       procno;
     937             : 
     938             :     /* Only answer column-level inquiries */
     939         312 :     if (attno == 0)
     940         196 :         return false;
     941             : 
     942             :     /*
     943             :      * Currently, GiST distance-ordered scans require that there be a distance
     944             :      * function in the opclass with the default types (i.e. the one loaded
     945             :      * into the relcache entry, see initGISTstate).  So we assume that if such
     946             :      * a function exists, then there's a reason for it (rather than grubbing
     947             :      * through all the opfamily's operators to find an ordered one).
     948             :      *
     949             :      * Essentially the same code can test whether we support returning the
     950             :      * column data, since that's true if the opclass provides a fetch proc.
     951             :      */
     952             : 
     953         116 :     switch (prop)
     954             :     {
     955             :         case AMPROP_DISTANCE_ORDERABLE:
     956           8 :             procno = GIST_DISTANCE_PROC;
     957           8 :             break;
     958             :         case AMPROP_RETURNABLE:
     959           8 :             procno = GIST_FETCH_PROC;
     960           8 :             break;
     961             :         default:
     962         100 :             return false;
     963             :     }
     964             : 
     965             :     /* First we need to know the column's opclass. */
     966          16 :     opclass = get_index_column_opclass(index_oid, attno);
     967          16 :     if (!OidIsValid(opclass))
     968             :     {
     969           0 :         *isnull = true;
     970           0 :         return true;
     971             :     }
     972             : 
     973             :     /* Now look up the opclass family and input datatype. */
     974          16 :     if (!get_opclass_opfamily_and_input_type(opclass, &opfamily, &opcintype))
     975             :     {
     976           0 :         *isnull = true;
     977           0 :         return true;
     978             :     }
     979             : 
     980             :     /* And now we can check whether the function is provided. */
     981             : 
     982          16 :     *res = SearchSysCacheExists4(AMPROCNUM,
     983             :                                  ObjectIdGetDatum(opfamily),
     984             :                                  ObjectIdGetDatum(opcintype),
     985             :                                  ObjectIdGetDatum(opcintype),
     986             :                                  Int16GetDatum(procno));
     987             : 
     988             :     /*
     989             :      * Special case: even without a fetch function, AMPROP_RETURNABLE is true
     990             :      * if the opclass has no compress function.
     991             :      */
     992          16 :     if (prop == AMPROP_RETURNABLE && !*res)
     993             :     {
     994           8 :         *res = !SearchSysCacheExists4(AMPROCNUM,
     995             :                                       ObjectIdGetDatum(opfamily),
     996             :                                       ObjectIdGetDatum(opcintype),
     997             :                                       ObjectIdGetDatum(opcintype),
     998             :                                       Int16GetDatum(GIST_COMPRESS_PROC));
     999             :     }
    1000             : 
    1001          16 :     *isnull = false;
    1002             : 
    1003          16 :     return true;
    1004             : }
    1005             : 
    1006             : /*
    1007             :  * Temporary and unlogged GiST indexes are not WAL-logged, but we need LSNs
    1008             :  * to detect concurrent page splits anyway. This function provides a fake
    1009             :  * sequence of LSNs for that purpose.
    1010             :  */
    1011             : XLogRecPtr
    1012           8 : gistGetFakeLSN(Relation rel)
    1013             : {
    1014             :     static XLogRecPtr counter = FirstNormalUnloggedLSN;
    1015             : 
    1016           8 :     if (rel->rd_rel->relpersistence == RELPERSISTENCE_TEMP)
    1017             :     {
    1018             :         /*
    1019             :          * Temporary relations are only accessible in our session, so a simple
    1020             :          * backend-local counter will do.
    1021             :          */
    1022           8 :         return counter++;
    1023             :     }
    1024             :     else
    1025             :     {
    1026             :         /*
    1027             :          * Unlogged relations are accessible from other backends, and survive
    1028             :          * (clean) restarts. GetFakeLSNForUnloggedRel() handles that for us.
    1029             :          */
    1030             :         Assert(rel->rd_rel->relpersistence == RELPERSISTENCE_UNLOGGED);
    1031           0 :         return GetFakeLSNForUnloggedRel();
    1032             :     }
    1033             : }

Generated by: LCOV version 1.13