gserialized_gist_picksplit()

Datum gserialized_gist_picksplit

(

PG_FUNCTION_ARGS

)

Definition at line 1579 of file gserialized_gist_nd.c.

{
 
        GistEntryVector *entryvec = (GistEntryVector *)PG_GETARG_POINTER(0);
 
        GIST_SPLITVEC *v = (GIST_SPLITVEC *)PG_GETARG_POINTER(1);
        OffsetNumber i;
        /* One union box for each half of the space. */
        GIDX **box_union;
        /* One offset number list for each half of the space. */
        OffsetNumber **list;
        /* One position index for each half of the space. */
        int *pos;
        GIDX *box_pageunion;
        GIDX *box_current;
        int direction = -1;
        bool all_entries_equal = true;
        OffsetNumber max_offset;
        int nbytes, ndims_pageunion, d;
        int posmin = entryvec->n;
 
        POSTGIS_DEBUG(4, "[GIST] 'picksplit' function called");
 
        /*
        ** First calculate the bounding box and maximum number of dimensions in this page.
        */
 
        max_offset = entryvec->n - 1;
        box_current = (GIDX *)DatumGetPointer(entryvec->vector[FirstOffsetNumber].key);
        box_pageunion = gidx_copy(box_current);
 
        /* Calculate the containing box (box_pageunion) for the whole page we are going to split. */
        for (i = OffsetNumberNext(FirstOffsetNumber); i <= max_offset; i = OffsetNumberNext(i))
        {
                box_current = (GIDX *)DatumGetPointer(entryvec->vector[i].key);
 
                if (all_entries_equal && !gidx_equals(box_pageunion, box_current))
                        all_entries_equal = false;
 
                gidx_merge(&box_pageunion, box_current);
        }
 
        POSTGIS_DEBUGF(3, "[GIST] box_pageunion: %s", gidx_to_string(box_pageunion));
 
        /* Every box in the page is the same! So, we split and just put half the boxes in each child. */
        if (all_entries_equal)
        {
                POSTGIS_DEBUG(4, "[GIST] picksplit finds all entries equal!");
                gserialized_gist_picksplit_fallback(entryvec, v);
                PG_RETURN_POINTER(v);
        }
 
        /* Initialize memory structures. */
        nbytes = (max_offset + 2) * sizeof(OffsetNumber);
        ndims_pageunion = GIDX_NDIMS(box_pageunion);
        POSTGIS_DEBUGF(4, "[GIST] ndims_pageunion == %d", ndims_pageunion);
        pos = palloc(2 * ndims_pageunion * sizeof(int));
        list = palloc(2 * ndims_pageunion * sizeof(OffsetNumber *));
        box_union = palloc(2 * ndims_pageunion * sizeof(GIDX *));
        for (d = 0; d < ndims_pageunion; d++)
        {
                list[BELOW(d)] = (OffsetNumber *)palloc(nbytes);
                list[ABOVE(d)] = (OffsetNumber *)palloc(nbytes);
                box_union[BELOW(d)] = gidx_new(ndims_pageunion);
                box_union[ABOVE(d)] = gidx_new(ndims_pageunion);
                pos[BELOW(d)] = 0;
                pos[ABOVE(d)] = 0;
        }
 
        /*
        ** Assign each entry in the node to the volume partitions it belongs to,
        ** such as "above the x/y plane, left of the y/z plane, below the x/z plane".
        ** Each entry thereby ends up in three of the six partitions.
        */
        POSTGIS_DEBUG(4, "[GIST] 'picksplit' calculating best split axis");
        for (i = FirstOffsetNumber; i <= max_offset; i = OffsetNumberNext(i))
        {
                box_current = (GIDX *)DatumGetPointer(entryvec->vector[i].key);
 
                for (d = 0; d < ndims_pageunion; d++)
                {
                        if (GIDX_GET_MIN(box_current, d) - GIDX_GET_MIN(box_pageunion, d) <
                            GIDX_GET_MAX(box_pageunion, d) - GIDX_GET_MAX(box_current, d))
                                gserialized_gist_picksplit_addlist(
                                    list[BELOW(d)], &(box_union[BELOW(d)]), box_current, &(pos[BELOW(d)]), i);
                        else
                                gserialized_gist_picksplit_addlist(
                                    list[ABOVE(d)], &(box_union[ABOVE(d)]), box_current, &(pos[ABOVE(d)]), i);
                }
        }
 
        /*
        ** "Bad disposition", too many entries fell into one octant of the space, so no matter which
        ** plane we choose to split on, we're going to end up with a mostly full node. Where the
        ** data is pretty homogeneous (lots of duplicates) entries that are equidistant from the
        ** sides of the page union box can occasionally all end up in one place, leading
        ** to this condition.
        */
        if (gserialized_gist_picksplit_badratios(pos, ndims_pageunion))
        {
                /*
                ** Instead we split on center points and see if we do better.
                ** First calculate the average center point for each axis.
                */
                double *avgCenter = palloc(ndims_pageunion * sizeof(double));
 
                for (d = 0; d < ndims_pageunion; d++)
                        avgCenter[d] = 0.0;
 
                POSTGIS_DEBUG(4, "[GIST] picksplit can't find good split axis, trying center point method");
 
                for (i = FirstOffsetNumber; i <= max_offset; i = OffsetNumberNext(i))
                {
                        box_current = (GIDX *)DatumGetPointer(entryvec->vector[i].key);
                        for (d = 0; d < ndims_pageunion; d++)
                                avgCenter[d] += (GIDX_GET_MAX(box_current, d) + GIDX_GET_MIN(box_current, d)) / 2.0;
                }
                for (d = 0; d < ndims_pageunion; d++)
                {
                        avgCenter[d] /= max_offset;
                        pos[BELOW(d)] = pos[ABOVE(d)] = 0; /* Re-initialize our counters. */
                        POSTGIS_DEBUGF(4, "[GIST] picksplit average center point[%d] = %.12g", d, avgCenter[d]);
                }
 
                /* For each of our entries... */
                for (i = FirstOffsetNumber; i <= max_offset; i = OffsetNumberNext(i))
                {
                        double center;
                        box_current = (GIDX *)DatumGetPointer(entryvec->vector[i].key);
 
                        for (d = 0; d < ndims_pageunion; d++)
                        {
                                center = (GIDX_GET_MIN(box_current, d) + GIDX_GET_MAX(box_current, d)) / 2.0;
                                if (center < avgCenter[d])
                                        gserialized_gist_picksplit_addlist(
                                            list[BELOW(d)], &(box_union[BELOW(d)]), box_current, &(pos[BELOW(d)]), i);
                                else if (FPeq(center, avgCenter[d]))
                                        if (pos[BELOW(d)] > pos[ABOVE(d)])
                                                gserialized_gist_picksplit_addlist(list[ABOVE(d)],
                                                                                   &(box_union[ABOVE(d)]),
                                                                                   box_current,
                                                                                   &(pos[ABOVE(d)]),
                                                                                   i);
                                        else
                                                gserialized_gist_picksplit_addlist(list[BELOW(d)],
                                                                                   &(box_union[BELOW(d)]),
                                                                                   box_current,
                                                                                   &(pos[BELOW(d)]),
                                                                                   i);
                                else
                                        gserialized_gist_picksplit_addlist(
                                            list[ABOVE(d)], &(box_union[ABOVE(d)]), box_current, &(pos[ABOVE(d)]), i);
                        }
                }
 
                /* Do we have a good disposition now? If not, screw it, just cut the node in half. */
                if (gserialized_gist_picksplit_badratios(pos, ndims_pageunion))
                {
                        POSTGIS_DEBUG(4,
                                      "[GIST] picksplit still cannot find a good split! just cutting the node in half");
                        gserialized_gist_picksplit_fallback(entryvec, v);
                        PG_RETURN_POINTER(v);
                }
        }
 
        /*
        ** Now, what splitting plane gives us the most even ratio of
        ** entries in our child pages? Since each split region has been apportioned entries
        ** against the same number of total entries, the axis that has the smallest maximum
        ** number of entries in its regions is the most evenly distributed.
        ** TODO: what if the distributions are equal in two or more axes?
        */
        for (d = 0; d < ndims_pageunion; d++)
        {
                int posd = Max(pos[ABOVE(d)], pos[BELOW(d)]);
                if (posd < posmin)
                {
                        direction = d;
                        posmin = posd;
                }
        }
        if (direction == -1 || posmin == entryvec->n)
                elog(ERROR, "Error in building split, unable to determine split direction.");
 
        POSTGIS_DEBUGF(3, "[GIST] 'picksplit' splitting on axis %d", direction);
 
        gserialized_gist_picksplit_constructsplit(v,
                                                  list[BELOW(direction)],
                                                  pos[BELOW(direction)],
                                                  &(box_union[BELOW(direction)]),
                                                  list[ABOVE(direction)],
                                                  pos[ABOVE(direction)],
                                                  &(box_union[ABOVE(direction)]));
 
        POSTGIS_DEBUGF(4, "[GIST] spl_ldatum: %s", gidx_to_string((GIDX *)v->spl_ldatum));
        POSTGIS_DEBUGF(4, "[GIST] spl_rdatum: %s", gidx_to_string((GIDX *)v->spl_rdatum));
 
        POSTGIS_DEBUGF(
            4,
            "[GIST] axis %d: parent range (%.12g, %.12g) left range (%.12g, %.12g), right range (%.12g, %.12g)",
            direction,
            GIDX_GET_MIN(box_pageunion, direction),
            GIDX_GET_MAX(box_pageunion, direction),
            GIDX_GET_MIN((GIDX *)v->spl_ldatum, direction),
            GIDX_GET_MAX((GIDX *)v->spl_ldatum, direction),
            GIDX_GET_MIN((GIDX *)v->spl_rdatum, direction),
            GIDX_GET_MAX((GIDX *)v->spl_rdatum, direction));
 
        PG_RETURN_POINTER(v);
}

References ABOVE, BELOW, gidx_copy(), gidx_equals(), gidx_merge(), gserialized_gist_picksplit_addlist(), gserialized_gist_picksplit_badratios(), gserialized_gist_picksplit_constructsplit(), and gserialized_gist_picksplit_fallback().

Here is the call graph for this function: