gserialized_gist_picksplit_2d()

Datum gserialized_gist_picksplit_2d

(

PG_FUNCTION_ARGS

)

Definition at line 1781 of file gserialized_gist_2d.c.

{
        GistEntryVector *entryvec = (GistEntryVector *) PG_GETARG_POINTER(0);
        GIST_SPLITVEC *v = (GIST_SPLITVEC *) PG_GETARG_POINTER(1);
        OffsetNumber i,
                                maxoff;
        ConsiderSplitContext context;
        BOX2DF *leftBox, *rightBox;
        int                     dim,
                                commonEntriesCount;
        SplitInterval *intervalsLower,
                           *intervalsUpper;
        CommonEntry *commonEntries;
        int                     nentries;
 
        POSTGIS_DEBUG(3, "[GIST] 'picksplit' entered");
 
        memset(&context, 0, sizeof(ConsiderSplitContext));
 
        maxoff = entryvec->n - 1;
        nentries = context.entriesCount = maxoff - FirstOffsetNumber + 1;
 
        /* Allocate arrays for intervals along axes */
        intervalsLower = (SplitInterval *) palloc(nentries * sizeof(SplitInterval));
        intervalsUpper = (SplitInterval *) palloc(nentries * sizeof(SplitInterval));
 
        /*
         * Calculate the overall minimum bounding box over all the entries.
         */
        for (i = FirstOffsetNumber; i <= maxoff; i = OffsetNumberNext(i))
        {
                BOX2DF *box = (BOX2DF *)DatumGetPointer(entryvec->vector[i].key);
                if (i == FirstOffsetNumber)
                        context.boundingBox = *box;
                else
                        adjustBox(&context.boundingBox, box);
        }
 
        POSTGIS_DEBUGF(4, "boundingBox is %s", box2df_to_string(
                                                                                                                &context.boundingBox));
 
        /*
         * Iterate over axes for optimal split searching.
         */
        context.first = true;           /* nothing selected yet */
        for (dim = 0; dim < 2; dim++)
        {
                float           leftUpper,
                                        rightLower;
                int                     i1,
                                        i2;
 
                /* Project each entry as an interval on the selected axis. */
                for (i = FirstOffsetNumber; i <= maxoff; i = OffsetNumberNext(i))
                {
                        BOX2DF *box = (BOX2DF *)DatumGetPointer(entryvec->vector[i].key);
                        if (dim == 0)
                        {
                                intervalsLower[i - FirstOffsetNumber].lower = box->xmin;
                                intervalsLower[i - FirstOffsetNumber].upper = box->xmax;
                        }
                        else
                        {
                                intervalsLower[i - FirstOffsetNumber].lower = box->ymin;
                                intervalsLower[i - FirstOffsetNumber].upper = box->ymax;
                        }
                }
 
                /*
                 * Make two arrays of intervals: one sorted by lower bound and another
                 * sorted by upper bound.
                 */
                memcpy(intervalsUpper, intervalsLower,
                           sizeof(SplitInterval) * nentries);
                qsort(intervalsLower, nentries, sizeof(SplitInterval),
                          interval_cmp_lower);
                qsort(intervalsUpper, nentries, sizeof(SplitInterval),
                          interval_cmp_upper);
 
                /*----
                 * The goal is to form a left and right interval, so that every entry
                 * interval is contained by either left or right interval (or both).
                 *
                 * For example, with the intervals (0,1), (1,3), (2,3), (2,4):
                 *
                 * 0 1 2 3 4
                 * +-+
                 *       +---+
                 *         +-+
                 *         +---+
                 *
                 * The left and right intervals are of the form (0,a) and (b,4).
                 * We first consider splits where b is the lower bound of an entry.
                 * We iterate through all entries, and for each b, calculate the
                 * smallest possible a. Then we consider splits where a is the
                 * upper bound of an entry, and for each a, calculate the greatest
                 * possible b.
                 *
                 * In the above example, the first loop would consider splits:
                 * b=0: (0,1)-(0,4)
                 * b=1: (0,1)-(1,4)
                 * b=2: (0,3)-(2,4)
                 *
                 * And the second loop:
                 * a=1: (0,1)-(1,4)
                 * a=3: (0,3)-(2,4)
                 * a=4: (0,4)-(2,4)
                 */
 
                /*
                 * Iterate over lower bound of right group, finding smallest possible
                 * upper bound of left group.
                 */
                i1 = 0;
                i2 = 0;
                rightLower = intervalsLower[i1].lower;
                leftUpper = intervalsUpper[i2].lower;
                while (true)
                {
                        /*
                         * Find next lower bound of right group.
                         */
                        while (i1 < nentries && (rightLower == intervalsLower[i1].lower ||
                                        isnan(intervalsLower[i1].lower)))
                        {
                                leftUpper = Max(leftUpper, intervalsLower[i1].upper);
                                i1++;
                        }
                        if (i1 >= nentries)
                                break;
                        rightLower = intervalsLower[i1].lower;
 
                        /*
                         * Find count of intervals which anyway should be placed to the
                         * left group.
                         */
                        while (i2 < nentries && intervalsUpper[i2].upper <= leftUpper)
                                i2++;
 
                        /*
                         * Consider found split.
                         */
                        g_box_consider_split(&context, dim, rightLower, i1, leftUpper, i2);
                }
 
                /*
                 * Iterate over upper bound of left group finding greatest possible
                 * lower bound of right group.
                 */
                i1 = nentries - 1;
                i2 = nentries - 1;
                rightLower = intervalsLower[i1].upper;
                leftUpper = intervalsUpper[i2].upper;
                while (true)
                {
                        /*
                         * Find next upper bound of left group.
                         */
                        while (i2 >= 0 && (leftUpper == intervalsUpper[i2].upper ||
                                        isnan(intervalsUpper[i2].upper)))
                        {
                                rightLower = Min(rightLower, intervalsUpper[i2].lower);
                                i2--;
                        }
                        if (i2 < 0)
                                break;
                        leftUpper = intervalsUpper[i2].upper;
 
                        /*
                         * Find count of intervals which anyway should be placed to the
                         * right group.
                         */
                        while (i1 >= 0 && intervalsLower[i1].lower >= rightLower)
                                i1--;
 
                        /*
                         * Consider found split.
                         */
                        g_box_consider_split(&context, dim,
                                                                 rightLower, i1 + 1, leftUpper, i2 + 1);
                }
        }
 
        /*
         * If we failed to find any acceptable splits, use trivial split.
         */
        if (context.first)
        {
                POSTGIS_DEBUG(4, "no acceptable splits,  trivial split");
                fallbackSplit(entryvec, v);
                PG_RETURN_POINTER(v);
        }
 
        /*
         * Ok, we have now selected the split across one axis.
         *
         * While considering the splits, we already determined that there will be
         * enough entries in both groups to reach the desired ratio, but we did
         * not memorize which entries go to which group. So determine that now.
         */
 
        POSTGIS_DEBUGF(4, "split direction: %d", context.dim);
 
        /* Allocate vectors for results */
        v->spl_left = (OffsetNumber *) palloc(nentries * sizeof(OffsetNumber));
        v->spl_right = (OffsetNumber *) palloc(nentries * sizeof(OffsetNumber));
        v->spl_nleft = 0;
        v->spl_nright = 0;
 
        /* Allocate bounding boxes of left and right groups */
        leftBox = palloc0(sizeof(BOX2DF));
        rightBox = palloc0(sizeof(BOX2DF));
 
        /*
         * Allocate an array for "common entries" - entries which can be placed to
         * either group without affecting overlap along selected axis.
         */
        commonEntriesCount = 0;
        commonEntries = (CommonEntry *) palloc(nentries * sizeof(CommonEntry));
 
        /* Helper macros to place an entry in the left or right group */
#define PLACE_LEFT(box, off)                                    \
        do {                                                                            \
                if (v->spl_nleft > 0)                                   \
                        adjustBox(leftBox, box);                        \
                else                                                                    \
                        *leftBox = *(box);                                      \
                v->spl_left[v->spl_nleft++] = off;              \
        } while(0)
 
#define PLACE_RIGHT(box, off)                                   \
        do {                                                                            \
                if (v->spl_nright > 0)                                  \
                        adjustBox(rightBox, box);                       \
                else                                                                    \
                        *rightBox = *(box);                                     \
                v->spl_right[v->spl_nright++] = off;    \
        } while(0)
 
        /*
         * Distribute entries which can be distributed unambiguously, and collect
         * common entries.
         */
        for (i = FirstOffsetNumber; i <= maxoff; i = OffsetNumberNext(i))
        {
                float           lower,
                                        upper;
 
                /*
                 * Get upper and lower bounds along selected axis.
                 */
                BOX2DF *box = (BOX2DF *)DatumGetPointer(entryvec->vector[i].key);
                if (context.dim == 0)
                {
                        lower = box->xmin;
                        upper = box->xmax;
                }
                else
                {
                        lower = box->ymin;
                        upper = box->ymax;
                }
 
                if (upper <= context.leftUpper || isnan(upper))
                {
                        /* Fits to the left group */
                        if (lower >= context.rightLower || isnan(lower))
                        {
                                /* Fits also to the right group, so "common entry" */
                                commonEntries[commonEntriesCount++].index = i;
                        }
                        else
                        {
                                /* Doesn't fit to the right group, so join to the left group */
                                PLACE_LEFT(box, i);
                        }
                }
                else
                {
                        /*
                         * Each entry should fit on either left or right group. Since this
                         * entry didn't fit on the left group, it better fit in the right
                         * group.
                         */
                        Assert(lower >= context.rightLower);
 
                        /* Doesn't fit to the left group, so join to the right group */
                        PLACE_RIGHT(box, i);
                }
        }
 
        POSTGIS_DEBUGF(4, "leftBox is %s", box2df_to_string(leftBox));
        POSTGIS_DEBUGF(4, "rightBox is %s", box2df_to_string(rightBox));
 
        /*
         * Distribute "common entries", if any.
         */
        if (commonEntriesCount > 0)
        {
                /* Calculate minimum number of entries that must be placed in both groups, to reach LIMIT_RATIO. */
                int m = ceil(LIMIT_RATIO * (double)nentries);
 
                /* Recursive picksplit called, this is going to be the last split, keep split into 2 parts */
                if (nentries > INDEX_TUPLES_PER_PAGE && nentries <= 2 * INDEX_TUPLES_PER_PAGE)
                        m = Max(m, nentries - INDEX_TUPLES_PER_PAGE);
 
                Assert(m >= 1);
 
                for (i = 0; i < (OffsetNumber)commonEntriesCount; i++)
                {
                        BOX2DF *box = (BOX2DF *)DatumGetPointer(entryvec->vector[commonEntries[i].index].key);
 
                        if (v->spl_nright > 0 && v->spl_nleft > 0)
                        {
                                /* Calculate delta between penalties of join "common entries" to different groups. */
                                commonEntries[i].delta =
                                    fabsf(box2df_penalty(leftBox, box) - box2df_penalty(rightBox, box));
                        }
                        else
                        {
                                /* One group became degenerate during split - distribute boxes by their size */
                                commonEntries[i].delta = -box2df_penalty_single(box);
                        }
                }
 
                /* Sort "common entries" to distribute the most ambiguous entries first. */
                qsort(commonEntries, commonEntriesCount, sizeof(CommonEntry), common_entry_cmp);
 
                /* Distribute "common entries" between groups. */
                for (i = 0; i < (OffsetNumber)commonEntriesCount; i++)
                {
                        bool place_right = true;
                        BOX2DF *box = (BOX2DF *)DatumGetPointer(entryvec->vector[commonEntries[i].index].key);
 
                        /* Recheck penalties. After we put undecided tuples to some side they're changed */
                        float left_penalty = box2df_penalty(leftBox, box);
                        float right_penalty = box2df_penalty(rightBox, box);
 
                        /* Guarantee at least one tuple on each side to make Postgres happy */
                        if (v->spl_nright == 0 && v->spl_nleft > 0)
                                place_right = true;
                        else if (v->spl_nleft == 0 && v->spl_nright > 0)
                                place_right = false;
                        /* Check if we have to place this entry in either group to achieve LIMIT_RATIO */
                        else if (v->spl_nleft + (commonEntriesCount - i) <= m)
                                place_right = false;
                        else if (v->spl_nright + (commonEntriesCount - i) <= m)
                                place_right = true;
                        /* Otherwise select the group by smaller penalty */
                        else if (left_penalty < right_penalty)
                                place_right = false;
                        else if (right_penalty < left_penalty)
                                place_right = true;
                        /* or just put tuple into smaller group */
                        else if (v->spl_nleft < v->spl_nright)
                                place_right = false;
                        else
                                place_right = true;
 
                        if (place_right)
                                PLACE_RIGHT(box, commonEntries[i].index);
                        else
                                PLACE_LEFT(box, commonEntries[i].index);
                }
        }
        v->spl_ldatum = PointerGetDatum(leftBox);
        v->spl_rdatum = PointerGetDatum(rightBox);
 
        POSTGIS_DEBUG(4, "[GIST] 'picksplit' completed");
 
        PG_RETURN_POINTER(v);
}

References adjustBox(), ConsiderSplitContext::boundingBox, box2df_penalty(), box2df_penalty_single(), box2df_to_string(), common_entry_cmp(), CommonEntry::delta, ConsiderSplitContext::dim, ConsiderSplitContext::entriesCount, fallbackSplit(), ConsiderSplitContext::first, g_box_consider_split(), CommonEntry::index, INDEX_TUPLES_PER_PAGE, interval_cmp_lower(), interval_cmp_upper(), ConsiderSplitContext::leftUpper, LIMIT_RATIO, SplitInterval::lower, PLACE_LEFT, PLACE_RIGHT, ConsiderSplitContext::rightLower, and SplitInterval::upper.

Here is the call graph for this function: