gserialized_gist_picksplit()

Datum gserialized_gist_picksplit

(

PG_FUNCTION_ARGS

)

Definition at line 1796 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 == true && ! 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) == true )
        {
                /*
                ** 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) == true )
                {
                        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 )
        {
                /* ERROR OUT HERE */
                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: