From edff2142fd8239bbc9cef31a885a55344e20a649 Mon Sep 17 00:00:00 2001 From: Nikita Glukhov Date: Tue, 10 Sep 2019 17:26:26 +0300 Subject: [PATCH 1/4] Fix GiST and SP-GiST ordering by distance for NULLs --- src/backend/access/gist/gistget.c | 68 ++++------- src/backend/access/gist/gistscan.c | 18 ++- src/backend/access/index/indexam.c | 22 ++-- 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 | 136 +++++++++++++++++----- src/backend/utils/adt/geo_spgist.c | 18 +-- src/include/access/genam.h | 10 +- src/include/access/gist_private.h | 27 +---- src/include/access/spgist.h | 4 +- src/include/access/spgist_private.h | 22 ++-- src/test/regress/expected/create_index_spgist.out | 10 ++ src/test/regress/sql/create_index_spgist.sql | 5 + src/tools/pgindent/typedefs.list | 1 + 15 files changed, 212 insertions(+), 142 deletions(-) diff --git a/src/backend/access/gist/gistget.c b/src/backend/access/gist/gistget.c index db633a9..22d790d 100644 --- a/src/backend/access/gist/gistget.c +++ b/src/backend/access/gist/gistget.c @@ -112,9 +112,8 @@ gistkillitems(IndexScanDesc scan) * Similarly, *recheck_distances_p is set to indicate whether the distances * need to be rechecked, and it is also ignored for non-leaf entries. * - * If we are doing an ordered scan, so->distancesValues[] and - * so->distancesNulls[] is filled with distance data from the distance() - * functions before returning success. + * If we are doing an ordered scan, so->distances[] is filled with distance + * data from the distance() functions before returning success. * * We must decompress the key in the IndexTuple before passing it to the * sk_funcs (which actually are the opclass Consistent or Distance methods). @@ -135,8 +134,7 @@ gistindex_keytest(IndexScanDesc scan, GISTSTATE *giststate = so->giststate; ScanKey key = scan->keyData; int keySize = scan->numberOfKeys; - double *distance_value_p; - bool *distance_null_p; + IndexOrderByDistance *distance_p; Relation r = scan->indexRelation; *recheck_p = false; @@ -155,8 +153,8 @@ gistindex_keytest(IndexScanDesc scan, elog(ERROR, "invalid GiST tuple found on leaf page"); for (i = 0; i < scan->numberOfOrderBys; i++) { - so->distanceValues[i] = -get_float8_infinity(); - so->distanceNulls[i] = false; + so->distances[i].value = -get_float8_infinity(); + so->distances[i].isnull = false; } return true; } @@ -240,8 +238,7 @@ gistindex_keytest(IndexScanDesc scan, /* OK, it passes --- now let's compute the distances */ key = scan->orderByData; - distance_value_p = so->distanceValues; - distance_null_p = so->distanceNulls; + distance_p = so->distances; keySize = scan->numberOfOrderBys; while (keySize > 0) { @@ -256,8 +253,8 @@ gistindex_keytest(IndexScanDesc scan, if ((key->sk_flags & SK_ISNULL) || isNull) { /* Assume distance computes as null */ - *distance_value_p = 0.0; - *distance_null_p = true; + distance_p->value = 0.0; + distance_p->isnull = true; } else { @@ -294,13 +291,12 @@ gistindex_keytest(IndexScanDesc scan, ObjectIdGetDatum(key->sk_subtype), PointerGetDatum(&recheck)); *recheck_distances_p |= recheck; - *distance_value_p = DatumGetFloat8(dist); - *distance_null_p = false; + distance_p->value = DatumGetFloat8(dist); + distance_p->isnull = false; } key++; - distance_value_p++; - distance_null_p++; + distance_p++; keySize--; } @@ -313,8 +309,7 @@ gistindex_keytest(IndexScanDesc scan, * * scan: index scan we are executing * pageItem: search queue item identifying an index page to scan - * myDistanceValues: distances array associated with pageItem, or NULL at the root - * myDistanceNulls: null flags for myDistanceValues array, or NULL at the root + * myDistances: distances array associated with pageItem, or NULL at the root * tbm: if not NULL, gistgetbitmap's output bitmap * ntids: if not NULL, gistgetbitmap's output tuple counter * @@ -332,8 +327,7 @@ gistindex_keytest(IndexScanDesc scan, */ static void gistScanPage(IndexScanDesc scan, GISTSearchItem *pageItem, - double *myDistanceValues, bool *myDistanceNulls, - TIDBitmap *tbm, int64 *ntids) + IndexOrderByDistance *myDistances, TIDBitmap *tbm, int64 *ntids) { GISTScanOpaque so = (GISTScanOpaque) scan->opaque; GISTSTATE *giststate = so->giststate; @@ -370,7 +364,7 @@ gistScanPage(IndexScanDesc scan, GISTSearchItem *pageItem, GISTSearchItem *item; /* This can't happen when starting at the root */ - Assert(myDistanceValues != NULL && myDistanceNulls != NULL); + Assert(myDistances != NULL); oldcxt = MemoryContextSwitchTo(so->queueCxt); @@ -380,10 +374,8 @@ gistScanPage(IndexScanDesc scan, GISTSearchItem *pageItem, item->data.parentlsn = pageItem->data.parentlsn; /* Insert it into the queue using same distances as for this page */ - memcpy(GISTSearchItemDistanceValues(item, scan->numberOfOrderBys), - myDistanceValues, sizeof(double) * scan->numberOfOrderBys); - memcpy(GISTSearchItemDistanceNulls(item, scan->numberOfOrderBys), - myDistanceNulls, sizeof(bool) * scan->numberOfOrderBys); + memcpy(item->distances, myDistances, + sizeof(item->distances[0]) * scan->numberOfOrderBys); pairingheap_add(so->queue, &item->phNode); @@ -527,10 +519,8 @@ gistScanPage(IndexScanDesc scan, GISTSearchItem *pageItem, } /* Insert it into the queue using new distance data */ - memcpy(GISTSearchItemDistanceValues(item, nOrderBys), - so->distanceValues, sizeof(double) * nOrderBys); - memcpy(GISTSearchItemDistanceNulls(item, nOrderBys), - so->distanceNulls, sizeof(bool) * nOrderBys); + memcpy(item->distances, so->distances, + sizeof(item->distances[0]) * nOrderBys); pairingheap_add(so->queue, &item->phNode); @@ -595,8 +585,7 @@ getNextNearest(IndexScanDesc scan) scan->xs_recheck = item->data.heap.recheck; index_store_float8_orderby_distances(scan, so->orderByTypes, - GISTSearchItemDistanceValues(item, scan->numberOfOrderBys), - GISTSearchItemDistanceNulls(item, scan->numberOfOrderBys), + item->distances, item->data.heap.recheckDistances); /* in an index-only scan, also return the reconstructed tuple. */ @@ -609,10 +598,7 @@ getNextNearest(IndexScanDesc scan) /* visit an index page, extract its items into queue */ CHECK_FOR_INTERRUPTS(); - gistScanPage(scan, item, - GISTSearchItemDistanceValues(item, scan->numberOfOrderBys), - GISTSearchItemDistanceNulls(item, scan->numberOfOrderBys), - NULL, NULL); + gistScanPage(scan, item, item->distances, NULL, NULL); } pfree(item); @@ -650,7 +636,7 @@ gistgettuple(IndexScanDesc scan, ScanDirection dir) fakeItem.blkno = GIST_ROOT_BLKNO; memset(&fakeItem.data.parentlsn, 0, sizeof(GistNSN)); - gistScanPage(scan, &fakeItem, NULL, NULL, NULL, NULL); + gistScanPage(scan, &fakeItem, NULL, NULL, NULL); } if (scan->numberOfOrderBys > 0) @@ -744,10 +730,7 @@ gistgettuple(IndexScanDesc scan, ScanDirection dir) * this page, we fall out of the inner "do" and loop around to * return them. */ - gistScanPage(scan, item, - GISTSearchItemDistanceValues(item, scan->numberOfOrderBys), - GISTSearchItemDistanceNulls(item, scan->numberOfOrderBys), - NULL, NULL); + gistScanPage(scan, item, item->distances, NULL, NULL); pfree(item); } while (so->nPageData == 0); @@ -778,7 +761,7 @@ gistgetbitmap(IndexScanDesc scan, TIDBitmap *tbm) fakeItem.blkno = GIST_ROOT_BLKNO; memset(&fakeItem.data.parentlsn, 0, sizeof(GistNSN)); - gistScanPage(scan, &fakeItem, NULL, NULL, tbm, &ntids); + gistScanPage(scan, &fakeItem, NULL, tbm, &ntids); /* * While scanning a leaf page, ItemPointers of matching heap tuples will @@ -793,10 +776,7 @@ gistgetbitmap(IndexScanDesc scan, TIDBitmap *tbm) CHECK_FOR_INTERRUPTS(); - gistScanPage(scan, item, - GISTSearchItemDistanceValues(item, scan->numberOfOrderBys), - GISTSearchItemDistanceNulls(item, scan->numberOfOrderBys), - tbm, &ntids); + gistScanPage(scan, item, item->distances, tbm, &ntids); pfree(item); } diff --git a/src/backend/access/gist/gistscan.c b/src/backend/access/gist/gistscan.c index e72bf08..323a19d 100644 --- a/src/backend/access/gist/gistscan.c +++ b/src/backend/access/gist/gistscan.c @@ -14,6 +14,8 @@ */ #include "postgres.h" +#include + #include "access/gist_private.h" #include "access/gistscan.h" #include "access/relscan.h" @@ -33,26 +35,23 @@ pairingheap_GISTSearchItem_cmp(const pairingheap_node *a, const pairingheap_node const GISTSearchItem *sb = (const GISTSearchItem *) b; IndexScanDesc scan = (IndexScanDesc) arg; int i; - double *da = GISTSearchItemDistanceValues(sa, scan->numberOfOrderBys), - *db = GISTSearchItemDistanceValues(sb, scan->numberOfOrderBys); - bool *na = GISTSearchItemDistanceNulls(sa, scan->numberOfOrderBys), - *nb = GISTSearchItemDistanceNulls(sb, scan->numberOfOrderBys); /* Order according to distance comparison */ for (i = 0; i < scan->numberOfOrderBys; i++) { - if (na[i]) + if (sa->distances[i].isnull) { - if (!nb[i]) + if (!sb->distances[i].isnull) return -1; } - else if (nb[i]) + else if (sb->distances[i].isnull) { return 1; } else { - int cmp = -float8_cmp_internal(da[i], db[i]); + int cmp = -float8_cmp_internal(sa->distances[i].value, + sb->distances[i].value); if (cmp != 0) return cmp; @@ -100,8 +99,7 @@ gistbeginscan(Relation r, int nkeys, int norderbys) so->queueCxt = giststate->scanCxt; /* see gistrescan */ /* workspaces with size dependent on numberOfOrderBys: */ - so->distanceValues = palloc(sizeof(double) * scan->numberOfOrderBys); - so->distanceNulls = palloc(sizeof(bool) * scan->numberOfOrderBys); + so->distances = palloc(sizeof(so->distances[0]) * scan->numberOfOrderBys); so->qual_ok = true; /* in case there are zero keys */ if (scan->numberOfOrderBys > 0) { diff --git a/src/backend/access/index/indexam.c b/src/backend/access/index/indexam.c index 2e8f53a..442f414 100644 --- a/src/backend/access/index/indexam.c +++ b/src/backend/access/index/indexam.c @@ -847,14 +847,14 @@ index_getprocinfo(Relation irel, */ void index_store_float8_orderby_distances(IndexScanDesc scan, Oid *orderByTypes, - double *distanceValues, - bool *distanceNulls, bool recheckOrderBy) + IndexOrderByDistance *distances, + bool recheckOrderBy) { int i; scan->xs_recheckorderby = recheckOrderBy; - if (!distanceValues) + if (!distances) { Assert(!scan->xs_recheckorderby); @@ -869,11 +869,11 @@ index_store_float8_orderby_distances(IndexScanDesc scan, Oid *orderByTypes, for (i = 0; i < scan->numberOfOrderBys; i++) { - if (distanceNulls && distanceNulls[i]) - { + scan->xs_orderbynulls[i] = distances[i].isnull; + + if (scan->xs_orderbynulls[i]) scan->xs_orderbyvals[i] = (Datum) 0; - scan->xs_orderbynulls[i] = true; - } + if (orderByTypes[i] == FLOAT8OID) { #ifndef USE_FLOAT8_BYVAL @@ -881,8 +881,8 @@ index_store_float8_orderby_distances(IndexScanDesc scan, Oid *orderByTypes, if (!scan->xs_orderbynulls[i]) pfree(DatumGetPointer(scan->xs_orderbyvals[i])); #endif - scan->xs_orderbyvals[i] = Float8GetDatum(distanceValues[i]); - scan->xs_orderbynulls[i] = false; + if (!scan->xs_orderbynulls[i]) + scan->xs_orderbyvals[i] = Float8GetDatum(distances[i].value); } else if (orderByTypes[i] == FLOAT4OID) { @@ -892,8 +892,8 @@ index_store_float8_orderby_distances(IndexScanDesc scan, Oid *orderByTypes, if (!scan->xs_orderbynulls[i]) pfree(DatumGetPointer(scan->xs_orderbyvals[i])); #endif - scan->xs_orderbyvals[i] = Float4GetDatum((float4) distanceValues[i]); - scan->xs_orderbynulls[i] = false; + if (!scan->xs_orderbynulls[i]) + scan->xs_orderbyvals[i] = Float4GetDatum((float4) distances[i].value); } else { 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 2bd4037..41354d8e 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,17 +113,18 @@ 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 = - palloc(SizeOfSpGistSearchItem(isnull ? 0 : so->numberOfOrderBys)); + palloc(SizeOfSpGistSearchItem(isnull ? 0 : so->numberOfNonNullOrderBys)); item->isNull = isnull; - if (!isnull && so->numberOfOrderBys > 0) + if (!isnull && so->numberOfNonNullOrderBys > 0) memcpy(item->distances, distances, - so->numberOfOrderBys * sizeof(double)); + sizeof(item->distances[0]) * so->numberOfNonNullOrderBys); return item; } @@ -208,6 +219,34 @@ spgPrepareScanKeys(IndexScanDesc scan) so->numberOfOrderBys = scan->numberOfOrderBys; so->orderByData = scan->orderByData; + if (so->numberOfOrderBys <= 0) + so->numberOfNonNullOrderBys = 0; + else + { + int j = 0; + + /* + * Remove all NULL keys, but remember their offsets in the original + * array. + */ + for (i = 0; i < scan->numberOfOrderBys; i++) + { + ScanKey skey = &so->orderByData[i]; + + if (skey->sk_flags & SK_ISNULL) + so->nonNullOrderByOffsets[i] = -1; + else + { + if (i != j) + so->orderByData[j] = *skey; + + so->nonNullOrderByOffsets[i] = j++; + } + } + + so->numberOfNonNullOrderBys = j; + } + if (scan->numberOfKeys <= 0) { /* If no quals, whole-index scan is required */ @@ -295,17 +334,21 @@ spgbeginscan(Relation rel, int keysz, int orderbysz) /* This will be filled in spgrescan, but allocate the space here */ so->orderByTypes = (Oid *) palloc(sizeof(Oid) * scan->numberOfOrderBys); + so->nonNullOrderByOffsets = (int *) + 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 *) @@ -394,6 +437,7 @@ spgendscan(IndexScanDesc scan) if (scan->numberOfOrderBys > 0) { pfree(so->orderByTypes); + pfree(so->nonNullOrderByOffsets); pfree(so->zeroDistances); pfree(so->infDistances); pfree(scan->xs_orderbyvals); @@ -409,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); @@ -439,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; @@ -465,7 +509,7 @@ spgLeafTest(SpGistScanOpaque so, SpGistSearchItem *item, in.scankeys = so->keyData; in.nkeys = so->numberOfKeys; in.orderbys = so->orderByData; - in.norderbys = so->numberOfOrderBys; + in.norderbys = so->numberOfNonNullOrderBys; in.reconstructedValue = item->value; in.traversalValue = item->traversalValue; in.level = item->level; @@ -492,7 +536,7 @@ spgLeafTest(SpGistScanOpaque so, SpGistSearchItem *item, if (result) { /* item passes the scankeys */ - if (so->numberOfOrderBys > 0) + if (so->numberOfNonNullOrderBys > 0) { /* the scan is ordered -> add the item to the queue */ MemoryContext oldCxt = MemoryContextSwitchTo(so->traversalCxt); @@ -531,7 +575,7 @@ spgInitInnerConsistentIn(spgInnerConsistentIn *in, in->scankeys = so->keyData; in->orderbys = so->orderByData; in->nkeys = so->numberOfKeys; - in->norderbys = so->numberOfOrderBys; + in->norderbys = so->numberOfNonNullOrderBys; in->reconstructedValue = item->value; in->traversalMemoryContext = so->traversalCxt; in->traversalValue = item->traversalValue; @@ -549,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); @@ -633,7 +677,7 @@ spgInnerTest(SpGistScanOpaque so, SpGistSearchItem *item, { int nodeN = out.nodeNumbers[i]; SpGistSearchItem *innerItem; - double *distances; + IndexOrderByDistance *distances; Assert(nodeN >= 0 && nodeN < nNodes); @@ -751,7 +795,7 @@ redirect: if (item->isLeaf) { /* We store heap items in the queue only in case of ordered search */ - Assert(so->numberOfOrderBys > 0); + Assert(so->numberOfNonNullOrderBys > 0); storeRes(so, &item->heapPtr, item->value, item->isNull, item->recheck, item->recheckDistances, item->distances); reportedSome = true; @@ -847,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); @@ -874,7 +918,7 @@ spggetbitmap(IndexScanDesc scan, TIDBitmap *tbm) static void storeGettuple(SpGistScanOpaque so, ItemPointer heapPtr, Datum leafValue, bool isnull, bool recheck, bool recheckDistances, - double *distances) + IndexOrderByDistance *nonNullDistances) { Assert(so->nPtrs < MaxIndexTuplesPerPage); so->heapPtrs[so->nPtrs] = *heapPtr; @@ -883,13 +927,44 @@ storeGettuple(SpGistScanOpaque so, ItemPointer heapPtr, if (so->numberOfOrderBys > 0) { - if (isnull) + if (isnull || so->numberOfNonNullOrderBys <= 0) so->distances[so->nPtrs] = NULL; else { - Size size = sizeof(double) * so->numberOfOrderBys; + Size size = sizeof(nonNullDistances[0]) * so->numberOfOrderBys; + IndexOrderByDistance *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 i; + + for (i = 0; i < so->numberOfOrderBys; i++) + { + 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; + } + } + } - so->distances[so->nPtrs] = memcpy(palloc(size), distances, size); + so->distances[so->nPtrs] = distances; } } @@ -929,7 +1004,6 @@ spggettuple(IndexScanDesc scan, ScanDirection dir) if (so->numberOfOrderBys > 0) index_store_float8_orderby_distances(scan, so->orderByTypes, so->distances[so->iPtr], - NULL, so->recheckDistances[so->iPtr]); so->iPtr++; return 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/genam.h b/src/include/access/genam.h index 6c56717..aaa56ae 100644 --- a/src/include/access/genam.h +++ b/src/include/access/genam.h @@ -118,6 +118,13 @@ typedef enum IndexUniqueCheck } IndexUniqueCheck; +/* Nullable ORDER BY distance */ +typedef struct IndexOrderByDistance +{ + double value; + bool isnull; +} IndexOrderByDistance; + /* * generalized index_ interface routines (in indexam.c) */ @@ -179,8 +186,7 @@ extern FmgrInfo *index_getprocinfo(Relation irel, AttrNumber attnum, uint16 procnum); extern void index_store_float8_orderby_distances(IndexScanDesc scan, Oid *orderByTypes, - double *distanceValues, - bool *distanceNulls, + IndexOrderByDistance *distances, bool recheckOrderBy); /* diff --git a/src/include/access/gist_private.h b/src/include/access/gist_private.h index ed5b643..ab134c1 100644 --- a/src/include/access/gist_private.h +++ b/src/include/access/gist_private.h @@ -138,29 +138,15 @@ typedef struct GISTSearchItem GISTSearchHeapItem heap; /* heap info, if heap tuple */ } data; - /* - * This data structure is followed by arrays of distance values and - * distance null flags. Size of both arrays is - * IndexScanDesc->numberOfOrderBys. See macros below for accessing those - * arrays. - */ + /* numberOfOrderBys entries */ + IndexOrderByDistance distances[FLEXIBLE_ARRAY_MEMBER]; } GISTSearchItem; #define GISTSearchItemIsHeap(item) ((item).blkno == InvalidBlockNumber) -#define SizeOfGISTSearchItem(n_distances) (DOUBLEALIGN(sizeof(GISTSearchItem)) + \ - (sizeof(double) + sizeof(bool)) * (n_distances)) - -/* - * We actually don't need n_distances compute pointer to distance values. - * Nevertheless take n_distances as argument to have same arguments list for - * GISTSearchItemDistanceValues() and GISTSearchItemDistanceNulls(). - */ -#define GISTSearchItemDistanceValues(item, n_distances) \ - ((double *) ((Pointer) (item) + DOUBLEALIGN(sizeof(GISTSearchItem)))) - -#define GISTSearchItemDistanceNulls(item, n_distances) \ - ((bool *) ((Pointer) (item) + DOUBLEALIGN(sizeof(GISTSearchItem)) + sizeof(double) * (n_distances))) +#define SizeOfGISTSearchItem(n_distances) \ + (offsetof(GISTSearchItem, distances) + \ + sizeof(IndexOrderByDistance) * (n_distances)) /* * GISTScanOpaqueData: private state for a scan of a GiST index @@ -176,8 +162,7 @@ typedef struct GISTScanOpaqueData bool firstCall; /* true until first gistgettuple call */ /* pre-allocated workspace arrays */ - double *distanceValues; /* output area for gistindex_keytest */ - bool *distanceNulls; + IndexOrderByDistance *distances; /* output area for gistindex_keytest */ /* info about killed items if any (killedItems is NULL if never used) */ OffsetNumber *killedItems; /* offset numbers of killed items */ 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 e0d1178..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 @@ -169,8 +170,12 @@ typedef struct SpGistScanOpaqueData int numberOfKeys; /* number of index qualifier conditions */ ScanKey keyData; /* array of index qualifier descriptors */ int numberOfOrderBys; /* number of ordering operators */ + int numberOfNonNullOrderBys; /* number of ordering operators + * with non-NULL arguments */ ScanKey orderByData; /* array of ordering op descriptors */ Oid *orderByTypes; /* array of ordering op return types */ + int *nonNullOrderByOffsets; /* array of offset of non-NULL ordering + * keys in the original array */ Oid indexCollation; /* collation of index column */ /* Opclass defined functions: */ @@ -178,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 */ @@ -195,7 +200,9 @@ typedef struct SpGistScanOpaqueData bool recheckDistances[MaxIndexTuplesPerPage]; /* distance recheck * flags */ HeapTuple reconTups[MaxIndexTuplesPerPage]; /* reconstructed tuples */ - double *distances[MaxIndexTuplesPerPage]; /* distances (for recheck) */ + + /* distances (for recheck) */ + IndexOrderByDistance *distances[MaxIndexTuplesPerPage]; /* * Note: using MaxIndexTuplesPerPage above is a bit hokey since @@ -459,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 */ diff --git a/src/test/regress/expected/create_index_spgist.out b/src/test/regress/expected/create_index_spgist.out index 81b4a67..5ccea91 100644 --- a/src/test/regress/expected/create_index_spgist.out +++ b/src/test/regress/expected/create_index_spgist.out @@ -555,6 +555,16 @@ WHERE seq.dist IS DISTINCT FROM idx.dist; ---+------+---+---+------+--- (0 rows) +-- check ORDER BY distance to NULL +SELECT (SELECT p FROM kd_point_tbl ORDER BY p <-> pt LIMIT 1) +FROM (VALUES (point '1,2'), (NULL), ('1234,5678')) pts(pt); + p +------------- + (59,21) + (9853,112) + (1239,5647) +(3 rows) + EXPLAIN (COSTS OFF) SELECT count(*) FROM radix_text_tbl WHERE t = 'P0123456789abcdef'; QUERY PLAN diff --git a/src/test/regress/sql/create_index_spgist.sql b/src/test/regress/sql/create_index_spgist.sql index 8e6c453..629936f 100644 --- a/src/test/regress/sql/create_index_spgist.sql +++ b/src/test/regress/sql/create_index_spgist.sql @@ -225,6 +225,11 @@ SELECT * FROM quad_point_tbl_ord_seq3 seq FULL JOIN kd_point_tbl_ord_idx3 idx ON seq.n = idx.n WHERE seq.dist IS DISTINCT FROM idx.dist; +-- check ORDER BY distance to NULL +SELECT (SELECT p FROM kd_point_tbl ORDER BY p <-> pt LIMIT 1) +FROM (VALUES (point '1,2'), (NULL), ('1234,5678')) pts(pt); + + EXPLAIN (COSTS OFF) SELECT count(*) FROM radix_text_tbl WHERE t = 'P0123456789abcdef'; SELECT count(*) FROM radix_text_tbl WHERE t = 'P0123456789abcdef'; diff --git a/src/tools/pgindent/typedefs.list b/src/tools/pgindent/typedefs.list index f3cdfa8..fb65265 100644 --- a/src/tools/pgindent/typedefs.list +++ b/src/tools/pgindent/typedefs.list @@ -1043,6 +1043,7 @@ IndexList IndexOnlyScan IndexOnlyScanState IndexOptInfo +IndexOrderByDistance IndexPath IndexRuntimeKeyInfo IndexScan -- 2.7.4