estimate_selectivity()

static float8 estimate_selectivity ( const GBOX *  box, const ND_STATS *  nd_stats, int  mode  )

static

This function returns an estimate of the selectivity of a search GBOX by looking at data in the ND_STATS structure.

The selectivity is a float from 0-1, that estimates the proportion of the rows in the table that will be returned as a result of the search box.

To get our estimate, we need "only" sum up the values * the proportion of each cell in the histogram that falls within the search box, then divide by the number of features that generated the histogram.

Definition at line 1959 of file gserialized_estimate.c.

{
        int d; /* counter */
        float8 selectivity;
        ND_BOX nd_box;
        ND_IBOX nd_ibox;
        int at[ND_DIMS];
        double cell_size[ND_DIMS];
        double min[ND_DIMS];
        double max[ND_DIMS];
        double total_count = 0.0;
        int ndims_max;
 
        /* Calculate the overlap of the box on the histogram */
        if ( ! nd_stats )
        {
                elog(NOTICE, " estimate_selectivity called with null input");
                return FALLBACK_ND_SEL;
        }
 
        ndims_max = Max(nd_stats->ndims, gbox_ndims(box));
 
        /* Initialize nd_box. */
        nd_box_from_gbox(box, &nd_box);
 
        /*
         * To return 2D stats on an ND sample, we need to make the
         * 2D box cover the full range of the other dimensions in the
         * histogram.
         */
        POSTGIS_DEBUGF(3, " mode: %d", mode);
        if ( mode == 2 )
        {
                POSTGIS_DEBUG(3, " in 2d mode, stripping the computation down to 2d");
                ndims_max = 2;
        }
 
        POSTGIS_DEBUGF(3, " nd_stats->extent: %s", nd_box_to_json(&(nd_stats->extent), nd_stats->ndims));
        POSTGIS_DEBUGF(3, " nd_box: %s", nd_box_to_json(&(nd_box), gbox_ndims(box)));
 
        /*
         * Search box completely misses histogram extent?
         * We have to intersect in all N dimensions or else we have
         * zero interaction under the &&& operator. It's important
         * to short circuit in this case, as some of the tests below
         * will return junk results when run on non-intersecting inputs.
         */
        if ( ! nd_box_intersects(&nd_box, &(nd_stats->extent), ndims_max) )
        {
                POSTGIS_DEBUG(3, " search box does not overlap histogram, returning 0");
                return 0.0;
        }
 
        /* Search box completely contains histogram extent! */
        if ( nd_box_contains(&nd_box, &(nd_stats->extent), ndims_max) )
        {
                POSTGIS_DEBUG(3, " search box contains histogram, returning 1");
                return 1.0;
        }
 
        /* Calculate the overlap of the box on the histogram */
        if ( ! nd_box_overlap(nd_stats, &nd_box, &nd_ibox) )
        {
                POSTGIS_DEBUG(3, " search box overlap with stats histogram failed");
                return FALLBACK_ND_SEL;
        }
 
        /* Work out some measurements of the histogram */
        for ( d = 0; d < nd_stats->ndims; d++ )
        {
                /* Cell size in each dim */
                min[d] = nd_stats->extent.min[d];
                max[d] = nd_stats->extent.max[d];
                cell_size[d] = (max[d] - min[d]) / nd_stats->size[d];
                POSTGIS_DEBUGF(3, " cell_size[%d] : %.9g", d, cell_size[d]);
 
                /* Initialize the counter */
                at[d] = nd_ibox.min[d];
        }
 
        /* Move through all the overlap values and sum them */
        do
        {
                float cell_count, ratio;
                ND_BOX nd_cell = { {0.0, 0.0, 0.0, 0.0}, {0.0, 0.0, 0.0, 0.0} };
 
                /* We have to pro-rate partially overlapped cells. */
                for ( d = 0; d < nd_stats->ndims; d++ )
                {
                        nd_cell.min[d] = min[d] + (at[d]+0) * cell_size[d];
                        nd_cell.max[d] = min[d] + (at[d]+1) * cell_size[d];
                }
 
                ratio = nd_box_ratio(&nd_box, &nd_cell, nd_stats->ndims);
                cell_count = nd_stats->value[nd_stats_value_index(nd_stats, at)];
 
                /* Add the pro-rated count for this cell to the overall total */
                total_count += cell_count * ratio;
                POSTGIS_DEBUGF(4, " cell (%d,%d), cell value %.6f, ratio %.6f", at[0], at[1], cell_count, ratio);
        }
        while ( nd_increment(&nd_ibox, nd_stats->ndims, at) );
 
        /* Scale by the number of features in our histogram to get the proportion */
        selectivity = total_count / nd_stats->histogram_features;
 
        POSTGIS_DEBUGF(3, " nd_stats->histogram_features = %f", nd_stats->histogram_features);
        POSTGIS_DEBUGF(3, " nd_stats->histogram_cells = %f", nd_stats->histogram_cells);
        POSTGIS_DEBUGF(3, " sum(overlapped histogram cells) = %f", total_count);
        POSTGIS_DEBUGF(3, " selectivity = %f", selectivity);
 
        /* Prevent rounding overflows */
        if (selectivity > 1.0) selectivity = 1.0;
        else if (selectivity < 0.0) selectivity = 0.0;
 
        return selectivity;
}

References ND_STATS_T::extent, FALLBACK_ND_SEL, gbox_ndims(), ND_STATS_T::histogram_cells, ND_STATS_T::histogram_features, ND_BOX_T::max, ND_BOX_T::min, ND_IBOX_T::min, nd_box_contains(), nd_box_from_gbox(), nd_box_intersects(), nd_box_overlap(), nd_box_ratio(), nd_box_to_json(), ND_DIMS, nd_increment(), nd_stats_value_index(), ND_STATS_T::ndims, ND_STATS_T::size, and ND_STATS_T::value.

Referenced by _postgis_gserialized_sel(), and gserialized_sel_internal().

Here is the call graph for this function:

Here is the caller graph for this function: