From 510dcf4685a14d7be1d297969f94671045d02b3c Mon Sep 17 00:00:00 2001 From: Nikita Glukhov Date: Mon, 16 Sep 2019 15:36:44 +0300 Subject: [PATCH 2/5] Use IndexOrderByDistance in SP-GiST user functions --- src/backend/access/spgist/spgkdtreeproc.c | 2 +- src/backend/access/spgist/spgproc.c | 9 +-- src/backend/access/spgist/spgquadtreeproc.c | 2 +- src/backend/access/spgist/spgscan.c | 96 ++++++++++++++++++----------- src/backend/utils/adt/geo_spgist.c | 18 +++--- src/include/access/spgist.h | 4 +- src/include/access/spgist_private.h | 14 +++-- 7 files changed, 88 insertions(+), 57 deletions(-) diff --git a/src/backend/access/spgist/spgkdtreeproc.c b/src/backend/access/spgist/spgkdtreeproc.c index 9d479fe..66ab1ac 100644 --- a/src/backend/access/spgist/spgkdtreeproc.c +++ b/src/backend/access/spgist/spgkdtreeproc.c @@ -271,7 +271,7 @@ spg_kd_inner_consistent(PG_FUNCTION_ARGS) BOX infArea; BOX *area; - out->distances = (double **) palloc(sizeof(double *) * in->nNodes); + out->distances = palloc(sizeof(out->distances[0]) * in->nNodes); out->traversalValues = (void **) palloc(sizeof(void *) * in->nNodes); if (in->level == 0) diff --git a/src/backend/access/spgist/spgproc.c b/src/backend/access/spgist/spgproc.c index 688638a..41203ed 100644 --- a/src/backend/access/spgist/spgproc.c +++ b/src/backend/access/spgist/spgproc.c @@ -59,20 +59,21 @@ point_box_distance(Point *point, BOX *box) * is expected to be point, non-leaf key is expected to be box. Scan key * arguments are expected to be points. */ -double * +IndexOrderByDistance * spg_key_orderbys_distances(Datum key, bool isLeaf, ScanKey orderbys, int norderbys) { int sk_num; - double *distances = (double *) palloc(norderbys * sizeof(double)), + IndexOrderByDistance *distances = palloc(sizeof(distances[0]) * norderbys), *distance = distances; for (sk_num = 0; sk_num < norderbys; ++sk_num, ++orderbys, ++distance) { Point *point = DatumGetPointP(orderbys->sk_argument); - *distance = isLeaf ? point_point_distance(point, DatumGetPointP(key)) - : point_box_distance(point, DatumGetBoxP(key)); + distance->isnull = false; + distance->value = isLeaf ? point_point_distance(point, DatumGetPointP(key)) + : point_box_distance(point, DatumGetBoxP(key)); } return distances; diff --git a/src/backend/access/spgist/spgquadtreeproc.c b/src/backend/access/spgist/spgquadtreeproc.c index e50108e..3f59bea 100644 --- a/src/backend/access/spgist/spgquadtreeproc.c +++ b/src/backend/access/spgist/spgquadtreeproc.c @@ -247,7 +247,7 @@ spg_quad_inner_consistent(PG_FUNCTION_ARGS) */ if (in->norderbys > 0) { - out->distances = (double **) palloc(sizeof(double *) * in->nNodes); + out->distances = palloc(sizeof(out->distances[0]) * in->nNodes); out->traversalValues = (void **) palloc(sizeof(void *) * in->nNodes); if (in->level == 0) diff --git a/src/backend/access/spgist/spgscan.c b/src/backend/access/spgist/spgscan.c index 053bf09..67d23f2 100644 --- a/src/backend/access/spgist/spgscan.c +++ b/src/backend/access/spgist/spgscan.c @@ -28,7 +28,8 @@ typedef void (*storeRes_func) (SpGistScanOpaque so, ItemPointer heapPtr, Datum leafValue, bool isNull, bool recheck, - bool recheckDistances, double *distances); + bool recheckDistances, + IndexOrderByDistance *distances); /* * Pairing heap comparison function for the SpGistSearchItem queue. @@ -56,16 +57,25 @@ pairingheap_SpGistSearchItem_cmp(const pairingheap_node *a, else { /* Order according to distance comparison */ - for (i = 0; i < so->numberOfOrderBys; i++) + for (i = 0; i < so->numberOfNonNullOrderBys; i++) { - if (isnan(sa->distances[i]) && isnan(sb->distances[i])) + if (sa->distances[i].isnull) + { + if (!sb->distances[i].isnull) + return -1; + continue; + } + else if (sb->distances[i].isnull) + return 1; + + if (isnan(sa->distances[i].value) && isnan(sb->distances[i].value)) continue; /* NaN == NaN */ - if (isnan(sa->distances[i])) + if (isnan(sa->distances[i].value)) return -1; /* NaN > number */ - if (isnan(sb->distances[i])) + if (isnan(sb->distances[i].value)) return 1; /* number < NaN */ - if (sa->distances[i] != sb->distances[i]) - return (sa->distances[i] < sb->distances[i]) ? 1 : -1; + if (sa->distances[i].value != sb->distances[i].value) + return (sa->distances[i].value < sb->distances[i].value) ? 1 : -1; } } @@ -103,7 +113,8 @@ spgAddSearchItemToQueue(SpGistScanOpaque so, SpGistSearchItem *item) } static SpGistSearchItem * -spgAllocSearchItem(SpGistScanOpaque so, bool isnull, double *distances) +spgAllocSearchItem(SpGistScanOpaque so, bool isnull, + IndexOrderByDistance *distances) { /* allocate distance array only for non-NULL items */ SpGistSearchItem *item = @@ -327,15 +338,17 @@ spgbeginscan(Relation rel, int keysz, int orderbysz) palloc(sizeof(int) * scan->numberOfOrderBys); /* These arrays have constant contents, so we can fill them now */ - so->zeroDistances = (double *) - palloc(sizeof(double) * scan->numberOfOrderBys); - so->infDistances = (double *) - palloc(sizeof(double) * scan->numberOfOrderBys); + so->zeroDistances = + palloc(sizeof(so->zeroDistances[0]) * scan->numberOfOrderBys); + so->infDistances = + palloc(sizeof(so->infDistances[0]) * scan->numberOfOrderBys); for (i = 0; i < scan->numberOfOrderBys; i++) { - so->zeroDistances[i] = 0.0; - so->infDistances[i] = get_float8_infinity(); + so->zeroDistances[i].value = 0.0; + so->zeroDistances[i].isnull = false; + so->infDistances[i].value = get_float8_infinity(); + so->infDistances[i].isnull = false; } scan->xs_orderbyvals = (Datum *) @@ -440,7 +453,7 @@ spgendscan(IndexScanDesc scan) static SpGistSearchItem * spgNewHeapItem(SpGistScanOpaque so, int level, ItemPointer heapPtr, Datum leafValue, bool recheck, bool recheckDistances, - bool isnull, double *distances) + bool isnull, IndexOrderByDistance *distances) { SpGistSearchItem *item = spgAllocSearchItem(so, isnull, distances); @@ -470,7 +483,7 @@ spgLeafTest(SpGistScanOpaque so, SpGistSearchItem *item, bool *reportedSome, storeRes_func storeRes) { Datum leafValue; - double *distances; + IndexOrderByDistance *distances; bool result; bool recheck; bool recheckDistances; @@ -580,7 +593,7 @@ spgMakeInnerItem(SpGistScanOpaque so, SpGistSearchItem *parentItem, SpGistNodeTuple tuple, spgInnerConsistentOut *out, int i, bool isnull, - double *distances) + IndexOrderByDistance *distances) { SpGistSearchItem *item = spgAllocSearchItem(so, isnull, distances); @@ -664,7 +677,7 @@ spgInnerTest(SpGistScanOpaque so, SpGistSearchItem *item, { int nodeN = out.nodeNumbers[i]; SpGistSearchItem *innerItem; - double *distances; + IndexOrderByDistance *distances; Assert(nodeN >= 0 && nodeN < nNodes); @@ -878,7 +891,7 @@ redirect: static void storeBitmap(SpGistScanOpaque so, ItemPointer heapPtr, Datum leafValue, bool isnull, bool recheck, bool recheckDistances, - double *distances) + IndexOrderByDistance *distances) { Assert(!recheckDistances && !distances); tbm_add_tuples(so->tbm, heapPtr, 1, recheck); @@ -905,7 +918,7 @@ spggetbitmap(IndexScanDesc scan, TIDBitmap *tbm) static void storeGettuple(SpGistScanOpaque so, ItemPointer heapPtr, Datum leafValue, bool isnull, bool recheck, bool recheckDistances, - double *nonNullDistances) + IndexOrderByDistance *nonNullDistances) { Assert(so->nPtrs < MaxIndexTuplesPerPage); so->heapPtrs[so->nPtrs] = *heapPtr; @@ -918,25 +931,38 @@ storeGettuple(SpGistScanOpaque so, ItemPointer heapPtr, so->distances[so->nPtrs] = NULL; else { - IndexOrderByDistance *distances = - palloc(sizeof(distances[0]) * so->numberOfOrderBys); - int i; + IndexOrderByDistance *distances; + Size size = sizeof(distances[0]) * so->numberOfOrderBys; - for (i = 0; i < so->numberOfOrderBys; i++) + distances = palloc(size); + + if (so->numberOfNonNullOrderBys >= so->numberOfOrderBys) + { + /* + * All distance keys are not NULL, so simply copy distance + * values. + */ + memcpy(distances, nonNullDistances, size); + } + else { - int offset = so->nonNullOrderByOffsets[i]; + int i; - if (offset >= 0) + for (i = 0; i < so->numberOfOrderBys; i++) { - /* Copy non-NULL distance value */ - distances[i].value = nonNullDistances[offset]; - distances[i].isnull = false; - } - else - { - /* Set distance's NULL flag. */ - distances[i].value = 0.0; - distances[i].isnull = true; + int offset = so->nonNullOrderByOffsets[i]; + + if (offset >= 0) + { + /* Copy non-NULL distance value */ + distances[i] = nonNullDistances[offset]; + } + else + { + /* Set distance's NULL flag. */ + distances[i].value = 0.0; + distances[i].isnull = true; + } } } diff --git a/src/backend/utils/adt/geo_spgist.c b/src/backend/utils/adt/geo_spgist.c index 8e29770..448b574 100644 --- a/src/backend/utils/adt/geo_spgist.c +++ b/src/backend/utils/adt/geo_spgist.c @@ -580,24 +580,25 @@ spg_box_quad_inner_consistent(PG_FUNCTION_ARGS) if (in->norderbys > 0 && in->nNodes > 0) { - double *distances = palloc(sizeof(double) * in->norderbys); + IndexOrderByDistance *distances = palloc(sizeof(distances[0]) * in->norderbys); int j; for (j = 0; j < in->norderbys; j++) { Point *pt = DatumGetPointP(in->orderbys[j].sk_argument); - distances[j] = pointToRectBoxDistance(pt, rect_box); + distances[j].value = pointToRectBoxDistance(pt, rect_box); + distances[j].isnull = false; } - out->distances = (double **) palloc(sizeof(double *) * in->nNodes); + out->distances = palloc(sizeof(out->distances[0]) * in->nNodes); out->distances[0] = distances; for (i = 1; i < in->nNodes; i++) { - out->distances[i] = palloc(sizeof(double) * in->norderbys); + out->distances[i] = palloc(sizeof(distances[0]) * in->norderbys); memcpy(out->distances[i], distances, - sizeof(double) * in->norderbys); + sizeof(distances[0]) * in->norderbys); } } @@ -622,7 +623,7 @@ spg_box_quad_inner_consistent(PG_FUNCTION_ARGS) out->nodeNumbers = (int *) palloc(sizeof(int) * in->nNodes); out->traversalValues = (void **) palloc(sizeof(void *) * in->nNodes); if (in->norderbys > 0) - out->distances = (double **) palloc(sizeof(double *) * in->nNodes); + out->distances = palloc(sizeof(out->distances[0]) * in->nNodes); /* * We switch memory context, because we want to allocate memory for new @@ -703,7 +704,7 @@ spg_box_quad_inner_consistent(PG_FUNCTION_ARGS) if (in->norderbys > 0) { - double *distances = palloc(sizeof(double) * in->norderbys); + IndexOrderByDistance *distances = palloc(sizeof(distances[0]) * in->norderbys); int j; out->distances[out->nNodes] = distances; @@ -712,7 +713,8 @@ spg_box_quad_inner_consistent(PG_FUNCTION_ARGS) { Point *pt = DatumGetPointP(in->orderbys[j].sk_argument); - distances[j] = pointToRectBoxDistance(pt, next_rect_box); + distances[j].value = pointToRectBoxDistance(pt, next_rect_box); + distances[j].isnull = false; } } diff --git a/src/include/access/spgist.h b/src/include/access/spgist.h index d787ab2..bcbcb1b 100644 --- a/src/include/access/spgist.h +++ b/src/include/access/spgist.h @@ -161,7 +161,7 @@ typedef struct spgInnerConsistentOut int *levelAdds; /* increment level by this much for each */ Datum *reconstructedValues; /* associated reconstructed values */ void **traversalValues; /* opclass-specific traverse values */ - double **distances; /* associated distances */ + IndexOrderByDistance **distances; /* associated distances */ } spgInnerConsistentOut; /* @@ -188,7 +188,7 @@ typedef struct spgLeafConsistentOut Datum leafValue; /* reconstructed original data, if any */ bool recheck; /* set true if operator must be rechecked */ bool recheckDistances; /* set true if distances must be rechecked */ - double *distances; /* associated distances */ + IndexOrderByDistance *distances; /* associated distances */ } spgLeafConsistentOut; diff --git a/src/include/access/spgist_private.h b/src/include/access/spgist_private.h index 3d322c9..1bfe7fa 100644 --- a/src/include/access/spgist_private.h +++ b/src/include/access/spgist_private.h @@ -145,11 +145,12 @@ typedef struct SpGistSearchItem bool recheckDistances; /* distance recheck is needed */ /* array with numberOfOrderBys entries */ - double distances[FLEXIBLE_ARRAY_MEMBER]; + IndexOrderByDistance distances[FLEXIBLE_ARRAY_MEMBER]; } SpGistSearchItem; #define SizeOfSpGistSearchItem(n_distances) \ - (offsetof(SpGistSearchItem, distances) + sizeof(double) * (n_distances)) + (offsetof(SpGistSearchItem, distances) + \ + sizeof(IndexOrderByDistance) * (n_distances)) /* * Private state of an index scan @@ -182,8 +183,8 @@ typedef struct SpGistScanOpaqueData FmgrInfo leafConsistentFn; /* Pre-allocated workspace arrays: */ - double *zeroDistances; - double *infDistances; + IndexOrderByDistance *zeroDistances; + IndexOrderByDistance *infDistances; /* These fields are only used in amgetbitmap scans: */ TIDBitmap *tbm; /* bitmap being filled */ @@ -465,8 +466,9 @@ extern bool spgdoinsert(Relation index, SpGistState *state, ItemPointer heapPtr, Datum datum, bool isnull); /* spgproc.c */ -extern double *spg_key_orderbys_distances(Datum key, bool isLeaf, - ScanKey orderbys, int norderbys); +extern IndexOrderByDistance *spg_key_orderbys_distances(Datum key, bool isLeaf, + ScanKey orderbys, + int norderbys); extern BOX *box_copy(BOX *orig); #endif /* SPGIST_PRIVATE_H */ -- 2.7.4