gistsplit.c File Reference

#include "postgres.h"
#include "access/gist_private.h"
#include "utils/rel.h"

Include dependency graph for gistsplit.c:

Go to the source code of this file.

Data Structures
struct	GistSplitUnion

Macros
#define	SWAPVAR(s, d, t)

Functions
static void	gistunionsubkeyvec (GISTSTATE *giststate, IndexTuple *itvec, GistSplitUnion *gsvp)
static void	gistunionsubkey (GISTSTATE *giststate, IndexTuple *itvec, GistSplitVector *spl)
static int	findDontCares (Relation r, GISTSTATE *giststate, GISTENTRY *valvec, GistSplitVector *spl, int attno)
static void	removeDontCares (OffsetNumber *a, int *len, const bool *dontcare)
static void	placeOne (Relation r, GISTSTATE *giststate, GistSplitVector *v, IndexTuple itup, OffsetNumber off, int attno)
static void	supportSecondarySplit (Relation r, GISTSTATE *giststate, int attno, GIST_SPLITVEC *sv, Datum oldL, Datum oldR)
static void	genericPickSplit (GISTSTATE *giststate, GistEntryVector *entryvec, GIST_SPLITVEC *v, int attno)
static bool	gistUserPicksplit (Relation r, GistEntryVector *entryvec, int attno, GistSplitVector *v, IndexTuple *itup, int len, GISTSTATE *giststate)
static void	gistSplitHalf (GIST_SPLITVEC *v, int len)
void	gistSplitByKey (Relation r, Page page, IndexTuple *itup, int len, GISTSTATE *giststate, GistSplitVector *v, int attno)

Macro Definition Documentation

SWAPVAR

#define SWAPVAR	(		s,
			d,
			t
	)

Value:

do {    \
    (t) = (s); \
    (s) = (d); \
    (d) = (t); \
} while(0)

Definition at line 237 of file gistsplit.c.

Function Documentation

findDontCares()

static int findDontCares ( Relation  r, GISTSTATE *  giststate, GISTENTRY *  valvec, GistSplitVector *  spl, int  attno  )

static

Definition at line 113 of file gistsplit.c.

{
    int         i;
    GISTENTRY   entry;
    int         NumDontCare = 0;
 
    /*
     * First, search the left-side tuples to see if any have zero penalty to
     * be added to the right-side union key.
     *
     * attno column is known all-not-null (see gistSplitByKey), so we need not
     * check for nulls
     */
    gistentryinit(entry, spl->splitVector.spl_rdatum, r, NULL,
                  (OffsetNumber) 0, false);
    for (i = 0; i < spl->splitVector.spl_nleft; i++)
    {
        int         j = spl->splitVector.spl_left[i];
        float       penalty = gistpenalty(giststate, attno, &entry, false,
                                          &valvec[j], false);
 
        if (penalty == 0.0)
        {
            spl->spl_dontcare[j] = true;
            NumDontCare++;
        }
    }
 
    /* And conversely for the right-side tuples */
    gistentryinit(entry, spl->splitVector.spl_ldatum, r, NULL,
                  (OffsetNumber) 0, false);
    for (i = 0; i < spl->splitVector.spl_nright; i++)
    {
        int         j = spl->splitVector.spl_right[i];
        float       penalty = gistpenalty(giststate, attno, &entry, false,
                                          &valvec[j], false);
 
        if (penalty == 0.0)
        {
            spl->spl_dontcare[j] = true;
            NumDontCare++;
        }
    }
 
    return NumDontCare;
}

References gistentryinit, gistpenalty(), i, j, GistSplitVector::spl_dontcare, GIST_SPLITVEC::spl_ldatum, GIST_SPLITVEC::spl_left, GIST_SPLITVEC::spl_nleft, GIST_SPLITVEC::spl_nright, GIST_SPLITVEC::spl_rdatum, GIST_SPLITVEC::spl_right, and GistSplitVector::splitVector.

Referenced by gistUserPicksplit().

genericPickSplit()

static void genericPickSplit ( GISTSTATE *  giststate, GistEntryVector *  entryvec, GIST_SPLITVEC *  v, int  attno  )

static

Definition at line 344 of file gistsplit.c.

{
    OffsetNumber i,
                maxoff;
    int         nbytes;
    GistEntryVector *evec;
 
    maxoff = entryvec->n - 1;
 
    nbytes = (maxoff + 2) * sizeof(OffsetNumber);
 
    v->spl_left = (OffsetNumber *) palloc(nbytes);
    v->spl_right = (OffsetNumber *) palloc(nbytes);
    v->spl_nleft = v->spl_nright = 0;
 
    for (i = FirstOffsetNumber; i <= maxoff; i = OffsetNumberNext(i))
    {
        if (i <= (maxoff - FirstOffsetNumber + 1) / 2)
        {
            v->spl_left[v->spl_nleft] = i;
            v->spl_nleft++;
        }
        else
        {
            v->spl_right[v->spl_nright] = i;
            v->spl_nright++;
        }
    }
 
    /*
     * Form union datums for each side
     */
    evec = palloc(sizeof(GISTENTRY) * entryvec->n + GEVHDRSZ);
 
    evec->n = v->spl_nleft;
    memcpy(evec->vector, entryvec->vector + FirstOffsetNumber,
           sizeof(GISTENTRY) * evec->n);
    v->spl_ldatum = FunctionCall2Coll(&giststate->unionFn[attno],
                                      giststate->supportCollation[attno],
                                      PointerGetDatum(evec),
                                      PointerGetDatum(&nbytes));
 
    evec->n = v->spl_nright;
    memcpy(evec->vector, entryvec->vector + FirstOffsetNumber + v->spl_nleft,
           sizeof(GISTENTRY) * evec->n);
    v->spl_rdatum = FunctionCall2Coll(&giststate->unionFn[attno],
                                      giststate->supportCollation[attno],
                                      PointerGetDatum(evec),
                                      PointerGetDatum(&nbytes));
}

References FirstOffsetNumber, FunctionCall2Coll(), GEVHDRSZ, i, GistEntryVector::n, OffsetNumberNext, palloc(), PointerGetDatum(), GIST_SPLITVEC::spl_ldatum, GIST_SPLITVEC::spl_left, GIST_SPLITVEC::spl_nleft, GIST_SPLITVEC::spl_nright, GIST_SPLITVEC::spl_rdatum, GIST_SPLITVEC::spl_right, GISTSTATE::supportCollation, GISTSTATE::unionFn, and GistEntryVector::vector.

Referenced by gistUserPicksplit().

gistSplitByKey()

void gistSplitByKey	(	Relation	r,
		Page	page,
		IndexTuple *	itup,
		int	len,
		GISTSTATE *	giststate,
		GistSplitVector *	v,
		int	attno
	)

Definition at line 623 of file gistsplit.c.

{
    GistEntryVector *entryvec;
    OffsetNumber *offNullTuples;
    int         nOffNullTuples = 0;
    int         i;
 
    /* generate the item array, and identify tuples with null keys */
    /* note that entryvec->vector[0] goes unused in this code */
    entryvec = palloc(GEVHDRSZ + (len + 1) * sizeof(GISTENTRY));
    entryvec->n = len + 1;
    offNullTuples = (OffsetNumber *) palloc(len * sizeof(OffsetNumber));
 
    for (i = 1; i <= len; i++)
    {
        Datum       datum;
        bool        IsNull;
 
        datum = index_getattr(itup[i - 1], attno + 1, giststate->leafTupdesc,
                              &IsNull);
        gistdentryinit(giststate, attno, &(entryvec->vector[i]),
                       datum, r, page, i,
                       false, IsNull);
        if (IsNull)
            offNullTuples[nOffNullTuples++] = i;
    }
 
    if (nOffNullTuples == len)
    {
        /*
         * Corner case: All keys in attno column are null, so just transfer
         * our attention to the next column.  If there's no next column, just
         * split page in half.
         */
        v->spl_risnull[attno] = v->spl_lisnull[attno] = true;
 
        if (attno + 1 < giststate->nonLeafTupdesc->natts)
            gistSplitByKey(r, page, itup, len, giststate, v, attno + 1);
        else
            gistSplitHalf(&v->splitVector, len);
    }
    else if (nOffNullTuples > 0)
    {
        int         j = 0;
 
        /*
         * We don't want to mix NULL and not-NULL keys on one page, so split
         * nulls to right page and not-nulls to left.
         */
        v->splitVector.spl_right = offNullTuples;
        v->splitVector.spl_nright = nOffNullTuples;
        v->spl_risnull[attno] = true;
 
        v->splitVector.spl_left = (OffsetNumber *) palloc(len * sizeof(OffsetNumber));
        v->splitVector.spl_nleft = 0;
        for (i = 1; i <= len; i++)
            if (j < v->splitVector.spl_nright && offNullTuples[j] == i)
                j++;
            else
                v->splitVector.spl_left[v->splitVector.spl_nleft++] = i;
 
        /* Compute union keys, unless outer recursion level will handle it */
        if (attno == 0 && giststate->nonLeafTupdesc->natts == 1)
        {
            v->spl_dontcare = NULL;
            gistunionsubkey(giststate, itup, v);
        }
    }
    else
    {
        /*
         * All keys are not-null, so apply user-defined PickSplit method
         */
        if (gistUserPicksplit(r, entryvec, attno, v, itup, len, giststate))
        {
            /*
             * Splitting on attno column is not optimal, so consider
             * redistributing don't-care tuples according to the next column
             */
            Assert(attno + 1 < giststate->nonLeafTupdesc->natts);
 
            if (v->spl_dontcare == NULL)
            {
                /*
                 * This split was actually degenerate, so ignore it altogether
                 * and just split according to the next column.
                 */
                gistSplitByKey(r, page, itup, len, giststate, v, attno + 1);
            }
            else
            {
                /*
                 * Form an array of just the don't-care tuples to pass to a
                 * recursive invocation of this function for the next column.
                 */
                IndexTuple *newitup = (IndexTuple *) palloc(len * sizeof(IndexTuple));
                OffsetNumber *map = (OffsetNumber *) palloc(len * sizeof(OffsetNumber));
                int         newlen = 0;
                GIST_SPLITVEC backupSplit;
 
                for (i = 0; i < len; i++)
                {
                    if (v->spl_dontcare[i + 1])
                    {
                        newitup[newlen] = itup[i];
                        map[newlen] = i + 1;
                        newlen++;
                    }
                }
 
                Assert(newlen > 0);
 
                /*
                 * Make a backup copy of v->splitVector, since the recursive
                 * call will overwrite that with its own result.
                 */
                backupSplit = v->splitVector;
                backupSplit.spl_left = (OffsetNumber *) palloc(sizeof(OffsetNumber) * len);
                memcpy(backupSplit.spl_left, v->splitVector.spl_left, sizeof(OffsetNumber) * v->splitVector.spl_nleft);
                backupSplit.spl_right = (OffsetNumber *) palloc(sizeof(OffsetNumber) * len);
                memcpy(backupSplit.spl_right, v->splitVector.spl_right, sizeof(OffsetNumber) * v->splitVector.spl_nright);
 
                /* Recursively decide how to split the don't-care tuples */
                gistSplitByKey(r, page, newitup, newlen, giststate, v, attno + 1);
 
                /* Merge result of subsplit with non-don't-care tuples */
                for (i = 0; i < v->splitVector.spl_nleft; i++)
                    backupSplit.spl_left[backupSplit.spl_nleft++] = map[v->splitVector.spl_left[i] - 1];
                for (i = 0; i < v->splitVector.spl_nright; i++)
                    backupSplit.spl_right[backupSplit.spl_nright++] = map[v->splitVector.spl_right[i] - 1];
 
                v->splitVector = backupSplit;
            }
        }
    }
 
    /*
     * If we're handling a multicolumn index, at the end of the recursion
     * recompute the left and right union datums for all index columns.  This
     * makes sure we hand back correct union datums in all corner cases,
     * including when we haven't processed all columns to start with, or when
     * a secondary split moved "don't care" tuples from one side to the other
     * (we really shouldn't assume that that didn't change the union datums).
     *
     * Note: when we're in an internal recursion (attno > 0), we do not worry
     * about whether the union datums we return with are sensible, since
     * calling levels won't care.  Also, in a single-column index, we expect
     * that PickSplit (or the special cases above) produced correct union
     * datums.
     */
    if (attno == 0 && giststate->nonLeafTupdesc->natts > 1)
    {
        v->spl_dontcare = NULL;
        gistunionsubkey(giststate, itup, v);
    }
}

References Assert, for(), GEVHDRSZ, gistdentryinit(), gistSplitHalf(), gistunionsubkey(), gistUserPicksplit(), i, index_getattr(), j, GISTSTATE::leafTupdesc, len, GistEntryVector::n, TupleDescData::natts, GISTSTATE::nonLeafTupdesc, palloc(), GistSplitVector::spl_dontcare, GIST_SPLITVEC::spl_left, GistSplitVector::spl_lisnull, GIST_SPLITVEC::spl_nleft, GIST_SPLITVEC::spl_nright, GIST_SPLITVEC::spl_right, GistSplitVector::spl_risnull, GistSplitVector::splitVector, and GistEntryVector::vector.

Referenced by gistSplit().

gistSplitHalf()

static void gistSplitHalf ( GIST_SPLITVEC *  v, int  len  )

static

Definition at line 585 of file gistsplit.c.

{
    int         i;
 
    v->spl_nright = v->spl_nleft = 0;
    v->spl_left = (OffsetNumber *) palloc(len * sizeof(OffsetNumber));
    v->spl_right = (OffsetNumber *) palloc(len * sizeof(OffsetNumber));
    for (i = 1; i <= len; i++)
        if (i < len / 2)
            v->spl_right[v->spl_nright++] = i;
        else
            v->spl_left[v->spl_nleft++] = i;
 
    /* we need not compute union keys, caller took care of it */
}

References i, len, palloc(), GIST_SPLITVEC::spl_left, GIST_SPLITVEC::spl_nleft, GIST_SPLITVEC::spl_nright, and GIST_SPLITVEC::spl_right.

Referenced by gistSplitByKey().

gistunionsubkey()

static void gistunionsubkey ( GISTSTATE *  giststate, IndexTuple *  itvec, GistSplitVector *  spl  )

static

Definition at line 80 of file gistsplit.c.

{
    GistSplitUnion gsvp;
 
    gsvp.dontcare = spl->spl_dontcare;
 
    gsvp.entries = spl->splitVector.spl_left;
    gsvp.len = spl->splitVector.spl_nleft;
    gsvp.attr = spl->spl_lattr;
    gsvp.isnull = spl->spl_lisnull;
 
    gistunionsubkeyvec(giststate, itvec, &gsvp);
 
    gsvp.entries = spl->splitVector.spl_right;
    gsvp.len = spl->splitVector.spl_nright;
    gsvp.attr = spl->spl_rattr;
    gsvp.isnull = spl->spl_risnull;
 
    gistunionsubkeyvec(giststate, itvec, &gsvp);
}

References GistSplitUnion::attr, GistSplitUnion::dontcare, GistSplitUnion::entries, gistunionsubkeyvec(), GistSplitUnion::isnull, GistSplitUnion::len, GistSplitVector::spl_dontcare, GistSplitVector::spl_lattr, GIST_SPLITVEC::spl_left, GistSplitVector::spl_lisnull, GIST_SPLITVEC::spl_nleft, GIST_SPLITVEC::spl_nright, GistSplitVector::spl_rattr, GIST_SPLITVEC::spl_right, GistSplitVector::spl_risnull, and GistSplitVector::splitVector.

Referenced by gistSplitByKey(), and gistUserPicksplit().

gistunionsubkeyvec()

static void gistunionsubkeyvec ( GISTSTATE *  giststate, IndexTuple *  itvec, GistSplitUnion *  gsvp  )

static

Definition at line 47 of file gistsplit.c.

{
    IndexTuple *cleanedItVec;
    int         i,
                cleanedLen = 0;
 
    cleanedItVec = (IndexTuple *) palloc(sizeof(IndexTuple) * gsvp->len);
 
    for (i = 0; i < gsvp->len; i++)
    {
        if (gsvp->dontcare && gsvp->dontcare[gsvp->entries[i]])
            continue;
 
        cleanedItVec[cleanedLen++] = itvec[gsvp->entries[i] - 1];
    }
 
    gistMakeUnionItVec(giststate, cleanedItVec, cleanedLen,
                       gsvp->attr, gsvp->isnull);
 
    pfree(cleanedItVec);
}

References GistSplitUnion::attr, GistSplitUnion::dontcare, GistSplitUnion::entries, gistMakeUnionItVec(), i, GistSplitUnion::isnull, GistSplitUnion::len, palloc(), and pfree().

Referenced by gistunionsubkey().

gistUserPicksplit()

static bool gistUserPicksplit ( Relation  r, GistEntryVector *  entryvec, int  attno, GistSplitVector *  v, IndexTuple *  itup, int  len, GISTSTATE *  giststate  )

static

Definition at line 415 of file gistsplit.c.

{
    GIST_SPLITVEC *sv = &v->splitVector;
 
    /*
     * Prepare spl_ldatum/spl_rdatum/spl_ldatum_exists/spl_rdatum_exists in
     * case we are doing a secondary split (see comments in gist.h).
     */
    sv->spl_ldatum_exists = !(v->spl_lisnull[attno]);
    sv->spl_rdatum_exists = !(v->spl_risnull[attno]);
    sv->spl_ldatum = v->spl_lattr[attno];
    sv->spl_rdatum = v->spl_rattr[attno];
 
    /*
     * Let the opclass-specific PickSplit method do its thing.  Note that at
     * this point we know there are no null keys in the entryvec.
     */
    FunctionCall2Coll(&giststate->picksplitFn[attno],
                      giststate->supportCollation[attno],
                      PointerGetDatum(entryvec),
                      PointerGetDatum(sv));
 
    if (sv->spl_nleft == 0 || sv->spl_nright == 0)
    {
        /*
         * User-defined picksplit failed to create an actual split, ie it put
         * everything on the same side.  Complain but cope.
         */
        ereport(DEBUG1,
                (errcode(ERRCODE_INTERNAL_ERROR),
                 errmsg("picksplit method for column %d of index \"%s\" failed",
                        attno + 1, RelationGetRelationName(r)),
                 errhint("The index is not optimal. To optimize it, contact a developer, or try to use the column as the second one in the CREATE INDEX command.")));
 
        /*
         * Reinit GIST_SPLITVEC. Although these fields are not used by
         * genericPickSplit(), set them up for further processing
         */
        sv->spl_ldatum_exists = !(v->spl_lisnull[attno]);
        sv->spl_rdatum_exists = !(v->spl_risnull[attno]);
        sv->spl_ldatum = v->spl_lattr[attno];
        sv->spl_rdatum = v->spl_rattr[attno];
 
        /* Do a generic split */
        genericPickSplit(giststate, entryvec, sv, attno);
    }
    else
    {
        /* hack for compatibility with old picksplit API */
        if (sv->spl_left[sv->spl_nleft - 1] == InvalidOffsetNumber)
            sv->spl_left[sv->spl_nleft - 1] = (OffsetNumber) (entryvec->n - 1);
        if (sv->spl_right[sv->spl_nright - 1] == InvalidOffsetNumber)
            sv->spl_right[sv->spl_nright - 1] = (OffsetNumber) (entryvec->n - 1);
    }
 
    /* Clean up if PickSplit didn't take care of a secondary split */
    if (sv->spl_ldatum_exists || sv->spl_rdatum_exists)
        supportSecondarySplit(r, giststate, attno, sv,
                              v->spl_lattr[attno], v->spl_rattr[attno]);
 
    /* emit union datums computed by PickSplit back to v arrays */
    v->spl_lattr[attno] = sv->spl_ldatum;
    v->spl_rattr[attno] = sv->spl_rdatum;
    v->spl_lisnull[attno] = false;
    v->spl_risnull[attno] = false;
 
    /*
     * If index columns remain, then consider whether we can improve the split
     * by using them.
     */
    v->spl_dontcare = NULL;
 
    if (attno + 1 < giststate->nonLeafTupdesc->natts)
    {
        int         NumDontCare;
 
        /*
         * Make a quick check to see if left and right union keys are equal;
         * if so, the split is certainly degenerate, so tell caller to
         * re-split with the next column.
         */
        if (gistKeyIsEQ(giststate, attno, sv->spl_ldatum, sv->spl_rdatum))
            return true;
 
        /*
         * Locate don't-care tuples, if any.  If there are none, the split is
         * optimal, so just fall out and return false.
         */
        v->spl_dontcare = (bool *) palloc0(sizeof(bool) * (entryvec->n + 1));
 
        NumDontCare = findDontCares(r, giststate, entryvec->vector, v, attno);
 
        if (NumDontCare > 0)
        {
            /*
             * Remove don't-cares from spl_left[] and spl_right[].
             */
            removeDontCares(sv->spl_left, &sv->spl_nleft, v->spl_dontcare);
            removeDontCares(sv->spl_right, &sv->spl_nright, v->spl_dontcare);
 
            /*
             * If all tuples on either side were don't-cares, the split is
             * degenerate, and we're best off to ignore it and split on the
             * next column.  (We used to try to press on with a secondary
             * split by forcing a random tuple on each side to be treated as
             * non-don't-care, but it seems unlikely that that technique
             * really gives a better result.  Note that we don't want to try a
             * secondary split with empty left or right primary split sides,
             * because then there is no union key on that side for the
             * PickSplit function to try to expand, so it can have no good
             * figure of merit for what it's doing.  Also note that this check
             * ensures we can't produce a bogus one-side-only split in the
             * NumDontCare == 1 special case below.)
             */
            if (sv->spl_nleft == 0 || sv->spl_nright == 0)
            {
                v->spl_dontcare = NULL;
                return true;
            }
 
            /*
             * Recompute union keys, considering only non-don't-care tuples.
             * NOTE: this will set union keys for remaining index columns,
             * which will cause later calls of gistUserPicksplit to pass those
             * values down to user-defined PickSplit methods with
             * spl_ldatum_exists/spl_rdatum_exists set true.
             */
            gistunionsubkey(giststate, itup, v);
 
            if (NumDontCare == 1)
            {
                /*
                 * If there's only one don't-care tuple then we can't do a
                 * PickSplit on it, so just choose whether to send it left or
                 * right by comparing penalties.  We needed the
                 * gistunionsubkey step anyway so that we have appropriate
                 * union keys for figuring the penalties.
                 */
                OffsetNumber toMove;
 
                /* find it ... */
                for (toMove = FirstOffsetNumber; toMove < entryvec->n; toMove++)
                {
                    if (v->spl_dontcare[toMove])
                        break;
                }
                Assert(toMove < entryvec->n);
 
                /* ... and assign it to cheaper side */
                placeOne(r, giststate, v, itup[toMove - 1], toMove, attno + 1);
 
                /*
                 * At this point the union keys are wrong, but we don't care
                 * because we're done splitting.  The outermost recursion
                 * level of gistSplitByKey will fix things before returning.
                 */
            }
            else
                return true;
        }
    }
 
    return false;
}

References Assert, DEBUG1, ereport, errcode(), errhint(), errmsg(), findDontCares(), FirstOffsetNumber, FunctionCall2Coll(), genericPickSplit(), gistKeyIsEQ(), gistunionsubkey(), InvalidOffsetNumber, GistEntryVector::n, TupleDescData::natts, GISTSTATE::nonLeafTupdesc, palloc0(), GISTSTATE::picksplitFn, placeOne(), PointerGetDatum(), RelationGetRelationName, removeDontCares(), GistSplitVector::spl_dontcare, GistSplitVector::spl_lattr, GIST_SPLITVEC::spl_ldatum, GIST_SPLITVEC::spl_ldatum_exists, GIST_SPLITVEC::spl_left, GistSplitVector::spl_lisnull, GIST_SPLITVEC::spl_nleft, GIST_SPLITVEC::spl_nright, GistSplitVector::spl_rattr, GIST_SPLITVEC::spl_rdatum, GIST_SPLITVEC::spl_rdatum_exists, GIST_SPLITVEC::spl_right, GistSplitVector::spl_risnull, GistSplitVector::splitVector, GISTSTATE::supportCollation, supportSecondarySplit(), and GistEntryVector::vector.

Referenced by gistSplitByKey().

placeOne()

static void placeOne ( Relation  r, GISTSTATE *  giststate, GistSplitVector *  v, IndexTuple  itup, OffsetNumber  off, int  attno  )

static

Definition at line 200 of file gistsplit.c.

{
    GISTENTRY   identry[INDEX_MAX_KEYS];
    bool        isnull[INDEX_MAX_KEYS];
    bool        toLeft = true;
 
    gistDeCompressAtt(giststate, r, itup, NULL, (OffsetNumber) 0,
                      identry, isnull);
 
    for (; attno < giststate->nonLeafTupdesc->natts; attno++)
    {
        float       lpenalty,
                    rpenalty;
        GISTENTRY   entry;
 
        gistentryinit(entry, v->spl_lattr[attno], r, NULL, 0, false);
        lpenalty = gistpenalty(giststate, attno, &entry, v->spl_lisnull[attno],
                               identry + attno, isnull[attno]);
        gistentryinit(entry, v->spl_rattr[attno], r, NULL, 0, false);
        rpenalty = gistpenalty(giststate, attno, &entry, v->spl_risnull[attno],
                               identry + attno, isnull[attno]);
 
        if (lpenalty != rpenalty)
        {
            if (lpenalty > rpenalty)
                toLeft = false;
            break;
        }
    }
 
    if (toLeft)
        v->splitVector.spl_left[v->splitVector.spl_nleft++] = off;
    else
        v->splitVector.spl_right[v->splitVector.spl_nright++] = off;
}

References gistDeCompressAtt(), gistentryinit, gistpenalty(), INDEX_MAX_KEYS, TupleDescData::natts, GISTSTATE::nonLeafTupdesc, GistSplitVector::spl_lattr, GIST_SPLITVEC::spl_left, GistSplitVector::spl_lisnull, GIST_SPLITVEC::spl_nleft, GIST_SPLITVEC::spl_nright, GistSplitVector::spl_rattr, GIST_SPLITVEC::spl_right, GistSplitVector::spl_risnull, and GistSplitVector::splitVector.

Referenced by gistUserPicksplit().

removeDontCares()

static void removeDontCares ( OffsetNumber *  a, int *  len, const bool *  dontcare  )

static

Definition at line 167 of file gistsplit.c.

{
    int         origlen,
                newlen,
                i;
    OffsetNumber *curwpos;
 
    origlen = newlen = *len;
    curwpos = a;
    for (i = 0; i < origlen; i++)
    {
        OffsetNumber ai = a[i];
 
        if (dontcare[ai] == false)
        {
            /* re-emit item into a[] */
            *curwpos = ai;
            curwpos++;
        }
        else
            newlen--;
    }
 
    *len = newlen;
}

References a, i, and len.

Referenced by gistUserPicksplit().

supportSecondarySplit()

static void supportSecondarySplit ( Relation  r, GISTSTATE *  giststate, int  attno, GIST_SPLITVEC *  sv, Datum  oldL, Datum  oldR  )

static

Definition at line 258 of file gistsplit.c.

{
    bool        leaveOnLeft = true,
                tmpBool;
    GISTENTRY   entryL,
                entryR,
                entrySL,
                entrySR;
 
    gistentryinit(entryL, oldL, r, NULL, 0, false);
    gistentryinit(entryR, oldR, r, NULL, 0, false);
    gistentryinit(entrySL, sv->spl_ldatum, r, NULL, 0, false);
    gistentryinit(entrySR, sv->spl_rdatum, r, NULL, 0, false);
 
    if (sv->spl_ldatum_exists && sv->spl_rdatum_exists)
    {
        float       penalty1,
                    penalty2;
 
        penalty1 = gistpenalty(giststate, attno, &entryL, false, &entrySL, false) +
            gistpenalty(giststate, attno, &entryR, false, &entrySR, false);
        penalty2 = gistpenalty(giststate, attno, &entryL, false, &entrySR, false) +
            gistpenalty(giststate, attno, &entryR, false, &entrySL, false);
 
        if (penalty1 > penalty2)
            leaveOnLeft = false;
    }
    else
    {
        GISTENTRY  *entry1 = (sv->spl_ldatum_exists) ? &entryL : &entryR;
        float       penalty1,
                    penalty2;
 
        /*
         * There is only one previously defined union, so we just choose swap
         * or not by lowest penalty for that side.  We can only get here if a
         * secondary split happened to have all NULLs in its column in the
         * tuples that the outer recursion level had assigned to one side.
         * (Note that the null checks in gistSplitByKey don't prevent the
         * case, because they'll only be checking tuples that were considered
         * don't-cares at the outer recursion level, not the tuples that went
         * into determining the passed-down left and right union keys.)
         */
        penalty1 = gistpenalty(giststate, attno, entry1, false, &entrySL, false);
        penalty2 = gistpenalty(giststate, attno, entry1, false, &entrySR, false);
 
        if (penalty1 < penalty2)
            leaveOnLeft = sv->spl_ldatum_exists;
        else
            leaveOnLeft = sv->spl_rdatum_exists;
    }
 
    if (leaveOnLeft == false)
    {
        /*
         * swap left and right
         */
        OffsetNumber *off,
                    noff;
        Datum       datum;
 
        SWAPVAR(sv->spl_left, sv->spl_right, off);
        SWAPVAR(sv->spl_nleft, sv->spl_nright, noff);
        SWAPVAR(sv->spl_ldatum, sv->spl_rdatum, datum);
        gistentryinit(entrySL, sv->spl_ldatum, r, NULL, 0, false);
        gistentryinit(entrySR, sv->spl_rdatum, r, NULL, 0, false);
    }
 
    if (sv->spl_ldatum_exists)
        gistMakeUnionKey(giststate, attno, &entryL, false, &entrySL, false,
                         &sv->spl_ldatum, &tmpBool);
 
    if (sv->spl_rdatum_exists)
        gistMakeUnionKey(giststate, attno, &entryR, false, &entrySR, false,
                         &sv->spl_rdatum, &tmpBool);
 
    sv->spl_ldatum_exists = sv->spl_rdatum_exists = false;
}

References gistentryinit, gistMakeUnionKey(), gistpenalty(), GIST_SPLITVEC::spl_ldatum, GIST_SPLITVEC::spl_ldatum_exists, GIST_SPLITVEC::spl_left, GIST_SPLITVEC::spl_nleft, GIST_SPLITVEC::spl_nright, GIST_SPLITVEC::spl_rdatum, GIST_SPLITVEC::spl_rdatum_exists, GIST_SPLITVEC::spl_right, and SWAPVAR.

Referenced by gistUserPicksplit().