On 13.09.2019 20:17, Alexander Korotkov wrote:
On Fri, Sep 13, 2019 at 5:23 PM Nikita Glukhov <n.glu...@postgrespro.ru> wrote:
I have moved handling of NULL ordering keys from opclasses to the common
SP-GiST code, but really I don't like how it is implemented now. Maybe it's
worth to move handling of NULL order-by keys to the even more higher
level so,
that AM don't have to worry about NULLs?
Yes, optimizer could remove away "col op NULL" clauses from ORDER BY
if op is strict operator. And then such clauses wouldn't be passed to
AM. But I see this as future improvement. For backpatching we should
solve this at AM side.
Also I leaved usages of IndexOrderByDistance in opclasses. I think, that
may help to minimize opclass changes in the future.
Could you please extract this as a separate patch. We can consider
this for master, but we shouldn't backpatch this.
Propagation of IndexOrderByDistance in SP-GiST was extracted into a separate
patch #2.
--
Nikita Glukhov
Postgres Professional: http://www.postgrespro.com
The Russian Postgres Company
>From e651a985b832e8429c8bab69ec3a7f7c39cdf2dd Mon Sep 17 00:00:00 2001
From: Nikita Glukhov <n.glu...@postgrespro.ru>
Date: Tue, 10 Sep 2019 17:26:26 +0300
Subject: [PATCH 1/5] 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/spgscan.c | 74 +++++++++++++++++++----
src/include/access/genam.h | 10 ++-
src/include/access/gist_private.h | 27 ++-------
src/include/access/spgist_private.h | 8 ++-
src/test/regress/expected/create_index_spgist.out | 10 +++
src/test/regress/sql/create_index_spgist.sql | 5 ++
src/tools/pgindent/typedefs.list | 1 +
10 files changed, 142 insertions(+), 101 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 <math.h>
+
#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/spgscan.c b/src/backend/access/spgist/spgscan.c
index 2bd4037..053bf09 100644
--- a/src/backend/access/spgist/spgscan.c
+++ b/src/backend/access/spgist/spgscan.c
@@ -107,13 +107,13 @@ spgAllocSearchItem(SpGistScanOpaque so, bool isnull, double *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 +208,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,6 +323,8 @@ 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 *)
@@ -394,6 +424,7 @@ spgendscan(IndexScanDesc scan)
if (scan->numberOfOrderBys > 0)
{
pfree(so->orderByTypes);
+ pfree(so->nonNullOrderByOffsets);
pfree(so->zeroDistances);
pfree(so->infDistances);
pfree(scan->xs_orderbyvals);
@@ -465,7 +496,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 +523,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 +562,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;
@@ -751,7 +782,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;
@@ -874,7 +905,7 @@ spggetbitmap(IndexScanDesc scan, TIDBitmap *tbm)
static void
storeGettuple(SpGistScanOpaque so, ItemPointer heapPtr,
Datum leafValue, bool isnull, bool recheck, bool recheckDistances,
- double *distances)
+ double *nonNullDistances)
{
Assert(so->nPtrs < MaxIndexTuplesPerPage);
so->heapPtrs[so->nPtrs] = *heapPtr;
@@ -883,13 +914,33 @@ 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;
+ IndexOrderByDistance *distances =
+ palloc(sizeof(distances[0]) * so->numberOfOrderBys);
+ int i;
+
+ for (i = 0; i < so->numberOfOrderBys; i++)
+ {
+ int offset = so->nonNullOrderByOffsets[i];
+
+ if (offset >= 0)
+ {
+ /* 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;
+ }
+ }
- so->distances[so->nPtrs] = memcpy(palloc(size), distances, size);
+ so->distances[so->nPtrs] = distances;
}
}
@@ -929,7 +980,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/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_private.h b/src/include/access/spgist_private.h
index e0d1178..3d322c9 100644
--- a/src/include/access/spgist_private.h
+++ b/src/include/access/spgist_private.h
@@ -169,8 +169,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: */
@@ -195,7 +199,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
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
>From 510dcf4685a14d7be1d297969f94671045d02b3c Mon Sep 17 00:00:00 2001
From: Nikita Glukhov <n.glu...@postgrespro.ru>
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
