agora inbox for pgsql-hackers@postgresql.org
help / color / mirror / Atom feedFrom: Nikita Glukhov <n.gluhov@postgrespro.ru>
To: Alexander Korotkov <a.korotkov@postgrespro.ru>
Cc: pgsql-hackers <pgsql-hackers@postgresql.org>
Cc: Heikki Linnakangas <hlinnaka@iki.fi>
Subject: Re: Bug in GiST paring heap comparator
Date: Mon, 16 Sep 2019 15:44:07 +0300
Message-ID: <907ff6e7-001c-8e86-e05f-ffe5483c2634@postgrespro.ru> (raw)
In-Reply-To: <CAPpHfdtkvxXtxT7KADq+_Y894qM6ybAuF10rYp1bxfvYfW6dLw@mail.gmail.com>
References: <CAPpHfdsNvNdA0DBS+wMpFrgwT6C3-q50sFVGLSiuWnV3FqOJuQ@mail.gmail.com>
<7362fcac-3664-d960-f0fa-77c24e62a7b3@iki.fi>
<CAPpHfdtaQZLC_9Zyn9rFMoxVKPimDBce0SwKvT5+7XH=z_xYvA@mail.gmail.com>
<CAPpHfdvgx7hM4wJmeEeaiuYTTZjzsokJyhfL1h7Gt-sxKZidZQ@mail.gmail.com>
<826f57ee-afc7-8977-c44c-6111d18b02ec@postgrespro.ru>
<CAPpHfdskuYR5tN78u7Yk_H9SQdnjnYFZZ8aQ69jRbXrRVzV=9g@mail.gmail.com>
<e9547b97-ed11-8e0e-6f40-0777d2407207@postgrespro.ru>
<CAPpHfdvttSd3XsVp5dSgBKz=KxakWtBnbgCeJULJDRpVkB_K8A@mail.gmail.com>
<ebcee467-547e-ca63-1858-4a485c4b8261@postgrespro.ru>
<CAPpHfdtkvxXtxT7KADq+_Y894qM6ybAuF10rYp1bxfvYfW6dLw@mail.gmail.com>
On 13.09.2019 20:17, Alexander Korotkov wrote:
> On Fri, Sep 13, 2019 at 5:23 PM Nikita Glukhov <n.gluhov@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
Attachments:
[text/x-patch] 0001-Fix-GiST-and-SP-GiST-ordering-by-distance-for-NULLs-v3.patch (23.0K, ../907ff6e7-001c-8e86-e05f-ffe5483c2634@postgrespro.ru/3-0001-Fix-GiST-and-SP-GiST-ordering-by-distance-for-NULLs-v3.patch)
download | inline diff:
From e651a985b832e8429c8bab69ec3a7f7c39cdf2dd Mon Sep 17 00:00:00 2001
From: Nikita Glukhov <n.gluhov@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
[text/x-patch] 0002-Use-IndexOrderByDistance-in-SP-GiST-user-functions-v3.patch (13.8K, ../907ff6e7-001c-8e86-e05f-ffe5483c2634@postgrespro.ru/4-0002-Use-IndexOrderByDistance-in-SP-GiST-user-functions-v3.patch)
download | inline diff:
From 510dcf4685a14d7be1d297969f94671045d02b3c Mon Sep 17 00:00:00 2001
From: Nikita Glukhov <n.gluhov@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
view thread (17+ messages) latest in thread
Message-ID: <907ff6e7-001c-8e86-e05f-ffe5483c2634@postgrespro.ru>
Permalink: ../907ff6e7-001c-8e86-e05f-ffe5483c2634@postgrespro.ru/
Also on: postgresql.org/message-id/907ff6e7-001c-8e86-e05f-ffe5483c2634@postgrespro.ru
reply
Reply instructions:
You may reply publicly to this message via plain-text email
using any one of the following methods:
* Reply to all the recipients using the --to and --cc options:
reply via email
To: pgsql-hackers@postgresql.org
Cc: n.gluhov@postgrespro.ru, a.korotkov@postgrespro.ru, hlinnaka@iki.fi
Subject: Re: Bug in GiST paring heap comparator
In-Reply-To: <907ff6e7-001c-8e86-e05f-ffe5483c2634@postgrespro.ru>
* Save the following mbox file, import it into your mail client,
and reply-to-all from there: mbox
This inbox is served by agora; see mirroring instructions
for how to clone and mirror all data and code used for this inbox