spgquadtreeproc.c

Go to the documentation of this file.

/*-------------------------------------------------------------------------
 *
 * spgquadtreeproc.c
 *    implementation of quad tree over points for SP-GiST
 *
 *
 * Portions Copyright (c) 1996-2021, PostgreSQL Global Development Group
 * Portions Copyright (c) 1994, Regents of the University of California
 *
 * IDENTIFICATION
 *          src/backend/access/spgist/spgquadtreeproc.c
 *
 *-------------------------------------------------------------------------
 */

#include "postgres.h"

#include "access/spgist.h"
#include "access/spgist_private.h"
#include "access/stratnum.h"
#include "catalog/pg_type.h"
#include "utils/builtins.h"
#include "utils/float.h"
#include "utils/geo_decls.h"

Datum
spg_quad_config(PG_FUNCTION_ARGS)
{
    /* spgConfigIn *cfgin = (spgConfigIn *) PG_GETARG_POINTER(0); */
    spgConfigOut *cfg = (spgConfigOut *) PG_GETARG_POINTER(1);

    cfg->prefixType = POINTOID;
    cfg->labelType = VOIDOID;   /* we don't need node labels */
    cfg->canReturnData = true;
    cfg->longValuesOK = false;
    PG_RETURN_VOID();
}

#define SPTEST(f, x, y) \
    DatumGetBool(DirectFunctionCall2(f, PointPGetDatum(x), PointPGetDatum(y)))

/*
 * Determine which quadrant a point falls into, relative to the centroid.
 *
 * Quadrants are identified like this:
 *
 *   4  |  1
 *  ----+-----
 *   3  |  2
 *
 * Points on one of the axes are taken to lie in the lowest-numbered
 * adjacent quadrant.
 */
static int16
getQuadrant(Point *centroid, Point *tst)
{
    if ((SPTEST(point_above, tst, centroid) ||
         SPTEST(point_horiz, tst, centroid)) &&
        (SPTEST(point_right, tst, centroid) ||
         SPTEST(point_vert, tst, centroid)))
        return 1;

    if (SPTEST(point_below, tst, centroid) &&
        (SPTEST(point_right, tst, centroid) ||
         SPTEST(point_vert, tst, centroid)))
        return 2;

    if ((SPTEST(point_below, tst, centroid) ||
         SPTEST(point_horiz, tst, centroid)) &&
        SPTEST(point_left, tst, centroid))
        return 3;

    if (SPTEST(point_above, tst, centroid) &&
        SPTEST(point_left, tst, centroid))
        return 4;

    elog(ERROR, "getQuadrant: impossible case");
    return 0;
}

/* Returns bounding box of a given quadrant inside given bounding box */
static BOX *
getQuadrantArea(BOX *bbox, Point *centroid, int quadrant)
{
    BOX        *result = (BOX *) palloc(sizeof(BOX));

    switch (quadrant)
    {
        case 1:
            result->high = bbox->high;
            result->low = *centroid;
            break;
        case 2:
            result->high.x = bbox->high.x;
            result->high.y = centroid->y;
            result->low.x = centroid->x;
            result->low.y = bbox->low.y;
            break;
        case 3:
            result->high = *centroid;
            result->low = bbox->low;
            break;
        case 4:
            result->high.x = centroid->x;
            result->high.y = bbox->high.y;
            result->low.x = bbox->low.x;
            result->low.y = centroid->y;
            break;
    }

    return result;
}

Datum
spg_quad_choose(PG_FUNCTION_ARGS)
{
    spgChooseIn *in = (spgChooseIn *) PG_GETARG_POINTER(0);
    spgChooseOut *out = (spgChooseOut *) PG_GETARG_POINTER(1);
    Point      *inPoint = DatumGetPointP(in->datum),
               *centroid;

    if (in->allTheSame)
    {
        out->resultType = spgMatchNode;
        /* nodeN will be set by core */
        out->result.matchNode.levelAdd = 0;
        out->result.matchNode.restDatum = PointPGetDatum(inPoint);
        PG_RETURN_VOID();
    }

    Assert(in->hasPrefix);
    centroid = DatumGetPointP(in->prefixDatum);

    Assert(in->nNodes == 4);

    out->resultType = spgMatchNode;
    out->result.matchNode.nodeN = getQuadrant(centroid, inPoint) - 1;
    out->result.matchNode.levelAdd = 0;
    out->result.matchNode.restDatum = PointPGetDatum(inPoint);

    PG_RETURN_VOID();
}

#ifdef USE_MEDIAN
static int
x_cmp(const void *a, const void *b, void *arg)
{
    Point      *pa = *(Point **) a;
    Point      *pb = *(Point **) b;

    if (pa->x == pb->x)
        return 0;
    return (pa->x > pb->x) ? 1 : -1;
}

static int
y_cmp(const void *a, const void *b, void *arg)
{
    Point      *pa = *(Point **) a;
    Point      *pb = *(Point **) b;

    if (pa->y == pb->y)
        return 0;
    return (pa->y > pb->y) ? 1 : -1;
}
#endif

Datum
spg_quad_picksplit(PG_FUNCTION_ARGS)
{
    spgPickSplitIn *in = (spgPickSplitIn *) PG_GETARG_POINTER(0);
    spgPickSplitOut *out = (spgPickSplitOut *) PG_GETARG_POINTER(1);
    int         i;
    Point      *centroid;

#ifdef USE_MEDIAN
    /* Use the median values of x and y as the centroid point */
    Point     **sorted;

    sorted = palloc(sizeof(*sorted) * in->nTuples);
    for (i = 0; i < in->nTuples; i++)
        sorted[i] = DatumGetPointP(in->datums[i]);

    centroid = palloc(sizeof(*centroid));

    qsort(sorted, in->nTuples, sizeof(*sorted), x_cmp);
    centroid->x = sorted[in->nTuples >> 1]->x;
    qsort(sorted, in->nTuples, sizeof(*sorted), y_cmp);
    centroid->y = sorted[in->nTuples >> 1]->y;
#else
    /* Use the average values of x and y as the centroid point */
    centroid = palloc0(sizeof(*centroid));

    for (i = 0; i < in->nTuples; i++)
    {
        centroid->x += DatumGetPointP(in->datums[i])->x;
        centroid->y += DatumGetPointP(in->datums[i])->y;
    }

    centroid->x /= in->nTuples;
    centroid->y /= in->nTuples;
#endif

    out->hasPrefix = true;
    out->prefixDatum = PointPGetDatum(centroid);

    out->nNodes = 4;
    out->nodeLabels = NULL;     /* we don't need node labels */

    out->mapTuplesToNodes = palloc(sizeof(int) * in->nTuples);
    out->leafTupleDatums = palloc(sizeof(Datum) * in->nTuples);

    for (i = 0; i < in->nTuples; i++)
    {
        Point      *p = DatumGetPointP(in->datums[i]);
        int         quadrant = getQuadrant(centroid, p) - 1;

        out->leafTupleDatums[i] = PointPGetDatum(p);
        out->mapTuplesToNodes[i] = quadrant;
    }

    PG_RETURN_VOID();
}


Datum
spg_quad_inner_consistent(PG_FUNCTION_ARGS)
{
    spgInnerConsistentIn *in = (spgInnerConsistentIn *) PG_GETARG_POINTER(0);
    spgInnerConsistentOut *out = (spgInnerConsistentOut *) PG_GETARG_POINTER(1);
    Point      *centroid;
    BOX         infbbox;
    BOX        *bbox = NULL;
    int         which;
    int         i;

    Assert(in->hasPrefix);
    centroid = DatumGetPointP(in->prefixDatum);

    /*
     * When ordering scan keys are specified, we've to calculate distance for
     * them.  In order to do that, we need calculate bounding boxes for all
     * children nodes.  Calculation of those bounding boxes on non-zero level
     * require knowledge of bounding box of upper node.  So, we save bounding
     * boxes to traversalValues.
     */
    if (in->norderbys > 0)
    {
        out->distances = (double **) palloc(sizeof(double *) * in->nNodes);
        out->traversalValues = (void **) palloc(sizeof(void *) * in->nNodes);

        if (in->level == 0)
        {
            double      inf = get_float8_infinity();

            infbbox.high.x = inf;
            infbbox.high.y = inf;
            infbbox.low.x = -inf;
            infbbox.low.y = -inf;
            bbox = &infbbox;
        }
        else
        {
            bbox = in->traversalValue;
            Assert(bbox);
        }
    }

    if (in->allTheSame)
    {
        /* Report that all nodes should be visited */
        out->nNodes = in->nNodes;
        out->nodeNumbers = (int *) palloc(sizeof(int) * in->nNodes);
        for (i = 0; i < in->nNodes; i++)
        {
            out->nodeNumbers[i] = i;

            if (in->norderbys > 0)
            {
                MemoryContext oldCtx = MemoryContextSwitchTo(in->traversalMemoryContext);

                /* Use parent quadrant box as traversalValue */
                BOX        *quadrant = box_copy(bbox);

                MemoryContextSwitchTo(oldCtx);

                out->traversalValues[i] = quadrant;
                out->distances[i] = spg_key_orderbys_distances(BoxPGetDatum(quadrant), false,
                                                               in->orderbys, in->norderbys);
            }
        }
        PG_RETURN_VOID();
    }

    Assert(in->nNodes == 4);

    /* "which" is a bitmask of quadrants that satisfy all constraints */
    which = (1 << 1) | (1 << 2) | (1 << 3) | (1 << 4);

    for (i = 0; i < in->nkeys; i++)
    {
        Point      *query = DatumGetPointP(in->scankeys[i].sk_argument);
        BOX        *boxQuery;

        switch (in->scankeys[i].sk_strategy)
        {
            case RTLeftStrategyNumber:
                if (SPTEST(point_right, centroid, query))
                    which &= (1 << 3) | (1 << 4);
                break;
            case RTRightStrategyNumber:
                if (SPTEST(point_left, centroid, query))
                    which &= (1 << 1) | (1 << 2);
                break;
            case RTSameStrategyNumber:
                which &= (1 << getQuadrant(centroid, query));
                break;
            case RTBelowStrategyNumber:
            case RTOldBelowStrategyNumber:
                if (SPTEST(point_above, centroid, query))
                    which &= (1 << 2) | (1 << 3);
                break;
            case RTAboveStrategyNumber:
            case RTOldAboveStrategyNumber:
                if (SPTEST(point_below, centroid, query))
                    which &= (1 << 1) | (1 << 4);
                break;
            case RTContainedByStrategyNumber:

                /*
                 * For this operator, the query is a box not a point.  We
                 * cheat to the extent of assuming that DatumGetPointP won't
                 * do anything that would be bad for a pointer-to-box.
                 */
                boxQuery = DatumGetBoxP(in->scankeys[i].sk_argument);

                if (DatumGetBool(DirectFunctionCall2(box_contain_pt,
                                                     PointerGetDatum(boxQuery),
                                                     PointerGetDatum(centroid))))
                {
                    /* centroid is in box, so all quadrants are OK */
                }
                else
                {
                    /* identify quadrant(s) containing all corners of box */
                    Point       p;
                    int         r = 0;

                    p = boxQuery->low;
                    r |= 1 << getQuadrant(centroid, &p);
                    p.y = boxQuery->high.y;
                    r |= 1 << getQuadrant(centroid, &p);
                    p = boxQuery->high;
                    r |= 1 << getQuadrant(centroid, &p);
                    p.x = boxQuery->low.x;
                    r |= 1 << getQuadrant(centroid, &p);

                    which &= r;
                }
                break;
            default:
                elog(ERROR, "unrecognized strategy number: %d",
                     in->scankeys[i].sk_strategy);
                break;
        }

        if (which == 0)
            break;              /* no need to consider remaining conditions */
    }

    out->levelAdds = palloc(sizeof(int) * 4);
    for (i = 0; i < 4; ++i)
        out->levelAdds[i] = 1;

    /* We must descend into the quadrant(s) identified by which */
    out->nodeNumbers = (int *) palloc(sizeof(int) * 4);
    out->nNodes = 0;

    for (i = 1; i <= 4; i++)
    {
        if (which & (1 << i))
        {
            out->nodeNumbers[out->nNodes] = i - 1;

            if (in->norderbys > 0)
            {
                MemoryContext oldCtx = MemoryContextSwitchTo(in->traversalMemoryContext);
                BOX        *quadrant = getQuadrantArea(bbox, centroid, i);

                MemoryContextSwitchTo(oldCtx);

                out->traversalValues[out->nNodes] = quadrant;

                out->distances[out->nNodes] = spg_key_orderbys_distances(BoxPGetDatum(quadrant), false,
                                                                         in->orderbys, in->norderbys);
            }

            out->nNodes++;
        }
    }

    PG_RETURN_VOID();
}


Datum
spg_quad_leaf_consistent(PG_FUNCTION_ARGS)
{
    spgLeafConsistentIn *in = (spgLeafConsistentIn *) PG_GETARG_POINTER(0);
    spgLeafConsistentOut *out = (spgLeafConsistentOut *) PG_GETARG_POINTER(1);
    Point      *datum = DatumGetPointP(in->leafDatum);
    bool        res;
    int         i;

    /* all tests are exact */
    out->recheck = false;

    /* leafDatum is what it is... */
    out->leafValue = in->leafDatum;

    /* Perform the required comparison(s) */
    res = true;
    for (i = 0; i < in->nkeys; i++)
    {
        Point      *query = DatumGetPointP(in->scankeys[i].sk_argument);

        switch (in->scankeys[i].sk_strategy)
        {
            case RTLeftStrategyNumber:
                res = SPTEST(point_left, datum, query);
                break;
            case RTRightStrategyNumber:
                res = SPTEST(point_right, datum, query);
                break;
            case RTSameStrategyNumber:
                res = SPTEST(point_eq, datum, query);
                break;
            case RTBelowStrategyNumber:
            case RTOldBelowStrategyNumber:
                res = SPTEST(point_below, datum, query);
                break;
            case RTAboveStrategyNumber:
            case RTOldAboveStrategyNumber:
                res = SPTEST(point_above, datum, query);
                break;
            case RTContainedByStrategyNumber:

                /*
                 * For this operator, the query is a box not a point.  We
                 * cheat to the extent of assuming that DatumGetPointP won't
                 * do anything that would be bad for a pointer-to-box.
                 */
                res = SPTEST(box_contain_pt, query, datum);
                break;
            default:
                elog(ERROR, "unrecognized strategy number: %d",
                     in->scankeys[i].sk_strategy);
                break;
        }

        if (!res)
            break;
    }

    if (res && in->norderbys > 0)
        /* ok, it passes -> let's compute the distances */
        out->distances = spg_key_orderbys_distances(in->leafDatum, true,
                                                    in->orderbys, in->norderbys);

    PG_RETURN_BOOL(res);
}