agora inbox for pgsql-hackers@postgresql.org
help / color / mirror / Atom feedBug in GiST paring heap comparator
17+ messages / 4 participants
[nested] [flat]
* Bug in GiST paring heap comparator
@ 2019-09-02 04:54 Alexander Korotkov <a.korotkov@postgrespro.ru>
0 siblings, 2 replies; 17+ messages in thread
From: Alexander Korotkov @ 2019-09-02 04:54 UTC (permalink / raw)
To: pgsql-hackers
Hi!
Andrey Borodin noticed me that results of some KNN-GIST tests are
obviously wrong and don't match results of sort node.
SELECT * FROM point_tbl ORDER BY f1 <-> '0,1';
f1
-------------------
(10,10)
(NaN,NaN)
(0,0)
(1e-300,-1e-300)
(-3,4)
(-10,0)
(-5,-12)
(5.1,34.5)
(1e+300,Infinity)
(10 rows)
It appears to be related to implementation of comparison function in
pairing heap used as priority queue for KNN. It used plain float
comparison, which doesn't handle Inf and Nan values well. Attached
patch replaced it with float8_cmp_internal().
Also, note that with patch KNN results still don't fully match results
of sort node.
SELECT * FROM point_tbl ORDER BY f1 <-> '0,1';
f1
-------------------
(0,0)
(1e-300,-1e-300)
(-3,4)
(-10,0)
(10,10)
(-5,-12)
(5.1,34.5)
(1e+300,Infinity)
(NaN,NaN)
(10 rows)
NULL and '(NaN,NaN)' are swapped. It happens so, because we assume
distance to NULL to be Inf, while float8_cmp_internal() assumes NaN to
be greater than NULL. If even we would assume distance to NULL to be
Nan, it doesn't guarantee that NULLs would be last. It looks like we
can handle this only by introduction array of "distance is null" flags
to GISTSearchItem. But does it worth it?
------
Alexander Korotkov
Postgres Professional: http://www.postgrespro.com
The Russian Postgres Company
Attachments:
[application/octet-stream] gist-pairing-heap-cmp-fix-1.patch (2.1K, ../../CAPpHfdsNvNdA0DBS+wMpFrgwT6C3-q50sFVGLSiuWnV3FqOJuQ@mail.gmail.com/2-gist-pairing-heap-cmp-fix-1.patch)
download | inline diff:
commit 8caa5026ffe6d14abe92cf5c3c442865ac663a01
Author: Alexander Korotkov <akorotkov@postgresql.org>
Date: Mon Sep 2 07:36:35 2019 +0300
Fix handling Inf and Nan values in GiST pairing heap comparator
Reported-by:
Bug:
Discussion:
Author:
Reviewed-by:
Tested-by:
Backpatch-through:
diff --git a/src/backend/access/gist/gistscan.c b/src/backend/access/gist/gistscan.c
index 893d7765b6c..3bfeb18e2ed 100644
--- a/src/backend/access/gist/gistscan.c
+++ b/src/backend/access/gist/gistscan.c
@@ -17,6 +17,7 @@
#include "access/gist_private.h"
#include "access/gistscan.h"
#include "access/relscan.h"
+#include "utils/float.h"
#include "utils/lsyscache.h"
#include "utils/memutils.h"
#include "utils/rel.h"
@@ -36,8 +37,9 @@ pairingheap_GISTSearchItem_cmp(const pairingheap_node *a, const pairingheap_node
/* Order according to distance comparison */
for (i = 0; i < scan->numberOfOrderBys; i++)
{
- if (sa->distances[i] != sb->distances[i])
- return (sa->distances[i] < sb->distances[i]) ? 1 : -1;
+ int cmp = -float8_cmp_internal(sa->distances[i], sb->distances[i]);
+ if (cmp != 0)
+ return cmp;
}
/* Heap items go before inner pages, to ensure a depth-first search */
diff --git a/src/test/regress/expected/create_index.out b/src/test/regress/expected/create_index.out
index c6d575a2f99..117b11a1a63 100644
--- a/src/test/regress/expected/create_index.out
+++ b/src/test/regress/expected/create_index.out
@@ -523,16 +523,16 @@ SELECT * FROM point_tbl ORDER BY f1 <-> '0,1';
SELECT * FROM point_tbl ORDER BY f1 <-> '0,1';
f1
-------------------
- (10,10)
- (NaN,NaN)
(0,0)
(1e-300,-1e-300)
(-3,4)
(-10,0)
+ (10,10)
(-5,-12)
(5.1,34.5)
-
(1e+300,Infinity)
+
+ (NaN,NaN)
(10 rows)
EXPLAIN (COSTS OFF)
@@ -561,15 +561,15 @@ SELECT * FROM point_tbl WHERE f1 IS NOT NULL ORDER BY f1 <-> '0,1';
SELECT * FROM point_tbl WHERE f1 IS NOT NULL ORDER BY f1 <-> '0,1';
f1
-------------------
- (10,10)
- (NaN,NaN)
(0,0)
(1e-300,-1e-300)
(-3,4)
(-10,0)
+ (10,10)
(-5,-12)
(5.1,34.5)
(1e+300,Infinity)
+ (NaN,NaN)
(9 rows)
EXPLAIN (COSTS OFF)
^ permalink raw reply [nested|flat] 17+ messages in thread
* Re: Bug in GiST paring heap comparator
@ 2019-09-02 05:11 Andrey Borodin <x4mmm@yandex-team.ru>
parent: Alexander Korotkov <a.korotkov@postgrespro.ru>
1 sibling, 0 replies; 17+ messages in thread
From: Andrey Borodin @ 2019-09-02 05:11 UTC (permalink / raw)
To: Alexander Korotkov <a.korotkov@postgrespro.ru>; +Cc: pgsql-hackers
> 2 сент. 2019 г., в 9:54, Alexander Korotkov <a.korotkov@postgrespro.ru> написал(а):
>
> It appears to be related to implementation of comparison function in
> pairing heap used as priority queue for KNN. It used plain float
> comparison, which doesn't handle Inf and Nan values well. Attached
> patch replaced it with float8_cmp_internal().
Thanks! This patch fixes tests of my new GiST build :)
While patch looks good to me, I want to add that that there's a lot of <= and > comparisons in gistproc.c in function:
static float8
computeDistance(bool isLeaf, BOX *box, Point *point)
Should we fix this too? Or add comment why current code is safe.
Thanks!
Best regards, Andrey Borodin.
^ permalink raw reply [nested|flat] 17+ messages in thread
* Re: Bug in GiST paring heap comparator
@ 2019-09-02 06:28 Heikki Linnakangas <hlinnaka@iki.fi>
parent: Alexander Korotkov <a.korotkov@postgrespro.ru>
1 sibling, 1 reply; 17+ messages in thread
From: Heikki Linnakangas @ 2019-09-02 06:28 UTC (permalink / raw)
To: Alexander Korotkov <a.korotkov@postgrespro.ru>; pgsql-hackers
On 02/09/2019 07:54, Alexander Korotkov wrote:
> Andrey Borodin noticed me that results of some KNN-GIST tests are
> obviously wrong and don't match results of sort node.
>
> SELECT * FROM point_tbl ORDER BY f1 <-> '0,1';
> f1
> -------------------
> (10,10)
> (NaN,NaN)
> (0,0)
> (1e-300,-1e-300)
> (-3,4)
> (-10,0)
> (-5,-12)
> (5.1,34.5)
>
> (1e+300,Infinity)
> (10 rows)
So we've memorized incorrect results in the expected output. Ouch!
> It appears to be related to implementation of comparison function in
> pairing heap used as priority queue for KNN. It used plain float
> comparison, which doesn't handle Inf and Nan values well. Attached
> patch replaced it with float8_cmp_internal().
>
> Also, note that with patch KNN results still don't fully match results
> of sort node.
>
> SELECT * FROM point_tbl ORDER BY f1 <-> '0,1';
> f1
> -------------------
> (0,0)
> (1e-300,-1e-300)
> (-3,4)
> (-10,0)
> (10,10)
> (-5,-12)
> (5.1,34.5)
> (1e+300,Infinity)
>
> (NaN,NaN)
> (10 rows)
>
> NULL and '(NaN,NaN)' are swapped. It happens so, because we assume
> distance to NULL to be Inf, while float8_cmp_internal() assumes NaN to
> be greater than NULL. If even we would assume distance to NULL to be
> Nan, it doesn't guarantee that NULLs would be last. It looks like we
> can handle this only by introduction array of "distance is null" flags
> to GISTSearchItem. But does it worth it?
I don't think we have much choice, returning wrong results is not an
option. At first I thought we could set the "recheck" flag if we see
NULLs or NaNs, but that won't work because rechecking is not supported
with Index-Only Scans.
Looking at the corresponding SP-GiST code,
pairingheap_SpGistSearchItem_cmp() gets this right. I'd suggest
copy-pasting the implementation from there, so that they would be as
similar as possible. (SP-GiST gets away with just one isNull flag,
because it doesn't support multi-column indexes. In GiST, you need an
array, as you said.)
- Heikki
^ permalink raw reply [nested|flat] 17+ messages in thread
* Re: Bug in GiST paring heap comparator
@ 2019-09-06 14:44 Alexander Korotkov <a.korotkov@postgrespro.ru>
parent: Heikki Linnakangas <hlinnaka@iki.fi>
0 siblings, 1 reply; 17+ messages in thread
From: Alexander Korotkov @ 2019-09-06 14:44 UTC (permalink / raw)
To: Heikki Linnakangas <hlinnaka@iki.fi>; +Cc: pgsql-hackers
On Mon, Sep 2, 2019 at 9:28 AM Heikki Linnakangas <hlinnaka@iki.fi> wrote:
> On 02/09/2019 07:54, Alexander Korotkov wrote:
> > NULL and '(NaN,NaN)' are swapped. It happens so, because we assume
> > distance to NULL to be Inf, while float8_cmp_internal() assumes NaN to
> > be greater than NULL. If even we would assume distance to NULL to be
> > Nan, it doesn't guarantee that NULLs would be last. It looks like we
> > can handle this only by introduction array of "distance is null" flags
> > to GISTSearchItem. But does it worth it?
>
> I don't think we have much choice, returning wrong results is not an
> option. At first I thought we could set the "recheck" flag if we see
> NULLs or NaNs, but that won't work because rechecking is not supported
> with Index-Only Scans.
>
> Looking at the corresponding SP-GiST code,
> pairingheap_SpGistSearchItem_cmp() gets this right. I'd suggest
> copy-pasting the implementation from there, so that they would be as
> similar as possible. (SP-GiST gets away with just one isNull flag,
> because it doesn't support multi-column indexes. In GiST, you need an
> array, as you said.)
Thank you for clarifying my doubts.
Second of attached patches solves this problem. In this patch
GISTSearchItem have both array of distances and array of null flags at
the end. They are accessed by a bit cumbersome
GISTSearchItemDistanceValues() and GISTSearchItemDistanceNulls()
macros. I came up to this, because I didn't like to allocate null
flags or distances in separate chunk of memory. Also I had idea to
wrap distance and null flag into struct, but I didn't like to change
signature of index_store_float8_orderby_distances() that much.
I'm going to push both if no objections.
------
Alexander Korotkov
Postgres Professional: http://www.postgrespro.com
The Russian Postgres Company
Attachments:
[application/octet-stream] 0001-gist-pairing-heap-cmp-fix-2.patch (2.1K, ../../CAPpHfdtaQZLC_9Zyn9rFMoxVKPimDBce0SwKvT5+7XH=z_xYvA@mail.gmail.com/2-0001-gist-pairing-heap-cmp-fix-2.patch)
download | inline diff:
commit f44601ab0bb3d8767783e8f9530f974256ac62ae
Author: Alexander Korotkov <akorotkov@postgresql.org>
Date: Mon Sep 2 07:36:35 2019 +0300
Fix handling Inf and Nan values in GiST pairing heap comparator
Reported-by:
Bug:
Discussion:
Author:
Reviewed-by:
Tested-by:
Backpatch-through:
diff --git a/src/backend/access/gist/gistscan.c b/src/backend/access/gist/gistscan.c
index 893d7765b6c..3bfeb18e2ed 100644
--- a/src/backend/access/gist/gistscan.c
+++ b/src/backend/access/gist/gistscan.c
@@ -17,6 +17,7 @@
#include "access/gist_private.h"
#include "access/gistscan.h"
#include "access/relscan.h"
+#include "utils/float.h"
#include "utils/lsyscache.h"
#include "utils/memutils.h"
#include "utils/rel.h"
@@ -36,8 +37,9 @@ pairingheap_GISTSearchItem_cmp(const pairingheap_node *a, const pairingheap_node
/* Order according to distance comparison */
for (i = 0; i < scan->numberOfOrderBys; i++)
{
- if (sa->distances[i] != sb->distances[i])
- return (sa->distances[i] < sb->distances[i]) ? 1 : -1;
+ int cmp = -float8_cmp_internal(sa->distances[i], sb->distances[i]);
+ if (cmp != 0)
+ return cmp;
}
/* Heap items go before inner pages, to ensure a depth-first search */
diff --git a/src/test/regress/expected/create_index.out b/src/test/regress/expected/create_index.out
index c6d575a2f99..117b11a1a63 100644
--- a/src/test/regress/expected/create_index.out
+++ b/src/test/regress/expected/create_index.out
@@ -523,16 +523,16 @@ SELECT * FROM point_tbl ORDER BY f1 <-> '0,1';
SELECT * FROM point_tbl ORDER BY f1 <-> '0,1';
f1
-------------------
- (10,10)
- (NaN,NaN)
(0,0)
(1e-300,-1e-300)
(-3,4)
(-10,0)
+ (10,10)
(-5,-12)
(5.1,34.5)
-
(1e+300,Infinity)
+
+ (NaN,NaN)
(10 rows)
EXPLAIN (COSTS OFF)
@@ -561,15 +561,15 @@ SELECT * FROM point_tbl WHERE f1 IS NOT NULL ORDER BY f1 <-> '0,1';
SELECT * FROM point_tbl WHERE f1 IS NOT NULL ORDER BY f1 <-> '0,1';
f1
-------------------
- (10,10)
- (NaN,NaN)
(0,0)
(1e-300,-1e-300)
(-3,4)
(-10,0)
+ (10,10)
(-5,-12)
(5.1,34.5)
(1e+300,Infinity)
+ (NaN,NaN)
(9 rows)
EXPLAIN (COSTS OFF)
[application/octet-stream] 0002-knn-gist-fix-null-distances-2.patch (14.7K, ../../CAPpHfdtaQZLC_9Zyn9rFMoxVKPimDBce0SwKvT5+7XH=z_xYvA@mail.gmail.com/3-0002-knn-gist-fix-null-distances-2.patch)
download | inline diff:
commit 7b1de7aa3022154888ba2c2d89237e95e26d1e5c
Author: Alexander Korotkov <akorotkov@postgresql.org>
Date: Mon Sep 2 07:36:35 2019 +0300
Fix handling of NULL distances in KNN-GiST
In order to implement NULL LAST semantic GiST previously assumed distance to
the NULL value to be Inf. However, our distance functions can return Inf and
NaN for non-null values. In such cases, NULL LAST semantic appears to be
broken. This commit fixes that by introducing separate array of null flags for
distances.
Reported-by:
Bug:
Discussion:
Author:
Reviewed-by:
Tested-by:
Backpatch-through:
diff --git a/src/backend/access/gist/gistget.c b/src/backend/access/gist/gistget.c
index 95ac35e3bb3..a4fff975e7e 100644
--- a/src/backend/access/gist/gistget.c
+++ b/src/backend/access/gist/gistget.c
@@ -112,8 +112,9 @@ 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->distances[] is filled with distance
- * data from the distance() functions before returning success.
+ * If we are doing an ordered scan, so->distancesValues[] and
+ * so->distancesNulls[] 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).
@@ -134,7 +135,8 @@ gistindex_keytest(IndexScanDesc scan,
GISTSTATE *giststate = so->giststate;
ScanKey key = scan->keyData;
int keySize = scan->numberOfKeys;
- double *distance_p;
+ double *distance_value_p;
+ bool *distance_null_p;
Relation r = scan->indexRelation;
*recheck_p = false;
@@ -152,7 +154,10 @@ gistindex_keytest(IndexScanDesc scan,
if (GistPageIsLeaf(page)) /* shouldn't happen */
elog(ERROR, "invalid GiST tuple found on leaf page");
for (i = 0; i < scan->numberOfOrderBys; i++)
- so->distances[i] = -get_float8_infinity();
+ {
+ so->distanceValues[i] = -get_float8_infinity();
+ so->distanceNulls[i] = false;
+ }
return true;
}
@@ -235,7 +240,8 @@ gistindex_keytest(IndexScanDesc scan,
/* OK, it passes --- now let's compute the distances */
key = scan->orderByData;
- distance_p = so->distances;
+ distance_value_p = so->distanceValues;
+ distance_null_p = so->distanceNulls;
keySize = scan->numberOfOrderBys;
while (keySize > 0)
{
@@ -249,8 +255,9 @@ gistindex_keytest(IndexScanDesc scan,
if ((key->sk_flags & SK_ISNULL) || isNull)
{
- /* Assume distance computes as null and sorts to the end */
- *distance_p = get_float8_infinity();
+ /* Assume distance computes as null */
+ *distance_value_p = 0.0;
+ *distance_null_p = true;
}
else
{
@@ -287,11 +294,13 @@ gistindex_keytest(IndexScanDesc scan,
ObjectIdGetDatum(key->sk_subtype),
PointerGetDatum(&recheck));
*recheck_distances_p |= recheck;
- *distance_p = DatumGetFloat8(dist);
+ *distance_value_p = DatumGetFloat8(dist);
+ *distance_null_p = false;
}
key++;
- distance_p++;
+ distance_value_p++;
+ distance_null_p++;
keySize--;
}
@@ -304,7 +313,8 @@ gistindex_keytest(IndexScanDesc scan,
*
* scan: index scan we are executing
* pageItem: search queue item identifying an index page to scan
- * myDistances: distances array associated with pageItem, or NULL at the root
+ * myDistanceValues: distances array associated with pageItem, or NULL at the root
+ * myDistanceNulls: null flags for myDistanceValues array, or NULL at the root
* tbm: if not NULL, gistgetbitmap's output bitmap
* ntids: if not NULL, gistgetbitmap's output tuple counter
*
@@ -321,7 +331,8 @@ gistindex_keytest(IndexScanDesc scan,
* sibling will be processed next.
*/
static void
-gistScanPage(IndexScanDesc scan, GISTSearchItem *pageItem, double *myDistances,
+gistScanPage(IndexScanDesc scan, GISTSearchItem *pageItem,
+ double *myDistanceValues, bool *myDistanceNulls,
TIDBitmap *tbm, int64 *ntids)
{
GISTScanOpaque so = (GISTScanOpaque) scan->opaque;
@@ -359,7 +370,7 @@ gistScanPage(IndexScanDesc scan, GISTSearchItem *pageItem, double *myDistances,
GISTSearchItem *item;
/* This can't happen when starting at the root */
- Assert(myDistances != NULL);
+ Assert(myDistanceValues != NULL && myDistanceNulls != NULL);
oldcxt = MemoryContextSwitchTo(so->queueCxt);
@@ -369,8 +380,10 @@ gistScanPage(IndexScanDesc scan, GISTSearchItem *pageItem, double *myDistances,
item->data.parentlsn = pageItem->data.parentlsn;
/* Insert it into the queue using same distances as for this page */
- memcpy(item->distances, myDistances,
- sizeof(double) * scan->numberOfOrderBys);
+ memcpy(GISTSearchItemDistanceValues(item, scan->numberOfOrderBys),
+ myDistanceValues, sizeof(double) * scan->numberOfOrderBys);
+ memcpy(GISTSearchItemDistanceNulls(item, scan->numberOfOrderBys),
+ myDistanceNulls, sizeof(bool) * scan->numberOfOrderBys);
pairingheap_add(so->queue, &item->phNode);
@@ -479,6 +492,7 @@ gistScanPage(IndexScanDesc scan, GISTSearchItem *pageItem, double *myDistances,
* search.
*/
GISTSearchItem *item;
+ int nOrderBys = scan->numberOfOrderBys;
oldcxt = MemoryContextSwitchTo(so->queueCxt);
@@ -513,8 +527,10 @@ gistScanPage(IndexScanDesc scan, GISTSearchItem *pageItem, double *myDistances,
}
/* Insert it into the queue using new distance data */
- memcpy(item->distances, so->distances,
- sizeof(double) * scan->numberOfOrderBys);
+ memcpy(GISTSearchItemDistanceValues(item, nOrderBys),
+ so->distanceValues, sizeof(double) * nOrderBys);
+ memcpy(GISTSearchItemDistanceNulls(item, nOrderBys),
+ so->distanceNulls, sizeof(bool) * nOrderBys);
pairingheap_add(so->queue, &item->phNode);
@@ -579,7 +595,8 @@ getNextNearest(IndexScanDesc scan)
scan->xs_recheck = item->data.heap.recheck;
index_store_float8_orderby_distances(scan, so->orderByTypes,
- item->distances,
+ GISTSearchItemDistanceValues(item, scan->numberOfOrderBys),
+ GISTSearchItemDistanceNulls(item, scan->numberOfOrderBys),
item->data.heap.recheckDistances);
/* in an index-only scan, also return the reconstructed tuple. */
@@ -592,7 +609,10 @@ getNextNearest(IndexScanDesc scan)
/* visit an index page, extract its items into queue */
CHECK_FOR_INTERRUPTS();
- gistScanPage(scan, item, item->distances, NULL, NULL);
+ gistScanPage(scan, item,
+ GISTSearchItemDistanceValues(item, scan->numberOfOrderBys),
+ GISTSearchItemDistanceNulls(item, scan->numberOfOrderBys),
+ NULL, NULL);
}
pfree(item);
@@ -630,7 +650,7 @@ gistgettuple(IndexScanDesc scan, ScanDirection dir)
fakeItem.blkno = GIST_ROOT_BLKNO;
memset(&fakeItem.data.parentlsn, 0, sizeof(GistNSN));
- gistScanPage(scan, &fakeItem, NULL, NULL, NULL);
+ gistScanPage(scan, &fakeItem, NULL, NULL, NULL, NULL);
}
if (scan->numberOfOrderBys > 0)
@@ -724,7 +744,10 @@ gistgettuple(IndexScanDesc scan, ScanDirection dir)
* this page, we fall out of the inner "do" and loop around to
* return them.
*/
- gistScanPage(scan, item, item->distances, NULL, NULL);
+ gistScanPage(scan, item,
+ GISTSearchItemDistanceValues(item, scan->numberOfOrderBys),
+ GISTSearchItemDistanceNulls(item, scan->numberOfOrderBys),
+ NULL, NULL);
pfree(item);
} while (so->nPageData == 0);
@@ -755,7 +778,7 @@ gistgetbitmap(IndexScanDesc scan, TIDBitmap *tbm)
fakeItem.blkno = GIST_ROOT_BLKNO;
memset(&fakeItem.data.parentlsn, 0, sizeof(GistNSN));
- gistScanPage(scan, &fakeItem, NULL, tbm, &ntids);
+ gistScanPage(scan, &fakeItem, NULL, NULL, tbm, &ntids);
/*
* While scanning a leaf page, ItemPointers of matching heap tuples will
@@ -770,7 +793,10 @@ gistgetbitmap(IndexScanDesc scan, TIDBitmap *tbm)
CHECK_FOR_INTERRUPTS();
- gistScanPage(scan, item, item->distances, tbm, &ntids);
+ gistScanPage(scan, item,
+ GISTSearchItemDistanceValues(item, scan->numberOfOrderBys),
+ GISTSearchItemDistanceNulls(item, scan->numberOfOrderBys),
+ tbm, &ntids);
pfree(item);
}
diff --git a/src/backend/access/gist/gistscan.c b/src/backend/access/gist/gistscan.c
index 3bfeb18e2ed..344b9e96a20 100644
--- a/src/backend/access/gist/gistscan.c
+++ b/src/backend/access/gist/gistscan.c
@@ -33,13 +33,29 @@ 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++)
{
- int cmp = -float8_cmp_internal(sa->distances[i], sb->distances[i]);
- if (cmp != 0)
- return cmp;
+ if (na[i])
+ {
+ if (!nb[i])
+ return -1;
+ }
+ else if (nb[i])
+ {
+ return 1;
+ }
+ else
+ {
+ int cmp = -float8_cmp_internal(da[i], db[i]);
+ if (cmp != 0)
+ return cmp;
+ }
}
/* Heap items go before inner pages, to ensure a depth-first search */
@@ -83,7 +99,8 @@ gistbeginscan(Relation r, int nkeys, int norderbys)
so->queueCxt = giststate->scanCxt; /* see gistrescan */
/* workspaces with size dependent on numberOfOrderBys: */
- so->distances = palloc(sizeof(double) * scan->numberOfOrderBys);
+ so->distanceValues = palloc(sizeof(double) * scan->numberOfOrderBys);
+ so->distanceNulls = palloc(sizeof(bool) * 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 28edd4aca76..2e8f53a37c8 100644
--- a/src/backend/access/index/indexam.c
+++ b/src/backend/access/index/indexam.c
@@ -847,13 +847,14 @@ index_getprocinfo(Relation irel,
*/
void
index_store_float8_orderby_distances(IndexScanDesc scan, Oid *orderByTypes,
- double *distances, bool recheckOrderBy)
+ double *distanceValues,
+ bool *distanceNulls, bool recheckOrderBy)
{
int i;
scan->xs_recheckorderby = recheckOrderBy;
- if (!distances)
+ if (!distanceValues)
{
Assert(!scan->xs_recheckorderby);
@@ -868,6 +869,11 @@ index_store_float8_orderby_distances(IndexScanDesc scan, Oid *orderByTypes,
for (i = 0; i < scan->numberOfOrderBys; i++)
{
+ if (distanceNulls && distanceNulls[i])
+ {
+ scan->xs_orderbyvals[i] = (Datum) 0;
+ scan->xs_orderbynulls[i] = true;
+ }
if (orderByTypes[i] == FLOAT8OID)
{
#ifndef USE_FLOAT8_BYVAL
@@ -875,7 +881,7 @@ 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(distances[i]);
+ scan->xs_orderbyvals[i] = Float8GetDatum(distanceValues[i]);
scan->xs_orderbynulls[i] = false;
}
else if (orderByTypes[i] == FLOAT4OID)
@@ -886,7 +892,7 @@ 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) distances[i]);
+ scan->xs_orderbyvals[i] = Float4GetDatum((float4) distanceValues[i]);
scan->xs_orderbynulls[i] = false;
}
else
diff --git a/src/backend/access/spgist/spgscan.c b/src/backend/access/spgist/spgscan.c
index 1cf28ecf2fd..2bd4037af9e 100644
--- a/src/backend/access/spgist/spgscan.c
+++ b/src/backend/access/spgist/spgscan.c
@@ -929,6 +929,7 @@ 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 8c053be2caf..6c56717ba77 100644
--- a/src/include/access/genam.h
+++ b/src/include/access/genam.h
@@ -178,7 +178,9 @@ extern RegProcedure index_getprocid(Relation irel, AttrNumber attnum,
extern FmgrInfo *index_getprocinfo(Relation irel, AttrNumber attnum,
uint16 procnum);
extern void index_store_float8_orderby_distances(IndexScanDesc scan,
- Oid *orderByTypes, double *distances,
+ Oid *orderByTypes,
+ double *distanceValues,
+ bool *distanceNulls,
bool recheckOrderBy);
/*
diff --git a/src/include/access/gist_private.h b/src/include/access/gist_private.h
index fc1a3115565..1a192290be9 100644
--- a/src/include/access/gist_private.h
+++ b/src/include/access/gist_private.h
@@ -137,13 +137,18 @@ typedef struct GISTSearchItem
/* we must store parentlsn to detect whether a split occurred */
GISTSearchHeapItem heap; /* heap info, if heap tuple */
} data;
- double distances[FLEXIBLE_ARRAY_MEMBER]; /* numberOfOrderBys
- * entries */
} GISTSearchItem;
#define GISTSearchItemIsHeap(item) ((item).blkno == InvalidBlockNumber)
-#define SizeOfGISTSearchItem(n_distances) (offsetof(GISTSearchItem, distances) + sizeof(double) * (n_distances))
+#define SizeOfGISTSearchItem(n_distances) (DOUBLEALIGN(sizeof(GISTSearchItem)) + \
+ (sizeof(double) + sizeof(bool)) * (n_distances))
+
+#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)))
/*
* GISTScanOpaqueData: private state for a scan of a GiST index
@@ -159,7 +164,8 @@ typedef struct GISTScanOpaqueData
bool firstCall; /* true until first gistgettuple call */
/* pre-allocated workspace arrays */
- double *distances; /* output area for gistindex_keytest */
+ double *distanceValues; /* output area for gistindex_keytest */
+ bool *distanceNulls;
/* info about killed items if any (killedItems is NULL if never used) */
OffsetNumber *killedItems; /* offset numbers of killed items */
diff --git a/src/test/regress/expected/create_index.out b/src/test/regress/expected/create_index.out
index 117b11a1a63..324db1b6ae1 100644
--- a/src/test/regress/expected/create_index.out
+++ b/src/test/regress/expected/create_index.out
@@ -531,8 +531,8 @@ SELECT * FROM point_tbl ORDER BY f1 <-> '0,1';
(-5,-12)
(5.1,34.5)
(1e+300,Infinity)
-
(NaN,NaN)
+
(10 rows)
EXPLAIN (COSTS OFF)
^ permalink raw reply [nested|flat] 17+ messages in thread
* Re: Bug in GiST paring heap comparator
@ 2019-09-08 19:32 Alexander Korotkov <a.korotkov@postgrespro.ru>
parent: Alexander Korotkov <a.korotkov@postgrespro.ru>
0 siblings, 1 reply; 17+ messages in thread
From: Alexander Korotkov @ 2019-09-08 19:32 UTC (permalink / raw)
To: Heikki Linnakangas <hlinnaka@iki.fi>; +Cc: pgsql-hackers
On Fri, Sep 6, 2019 at 5:44 PM Alexander Korotkov
<a.korotkov@postgrespro.ru> wrote:
> I'm going to push both if no objections.
So, pushed!
------
Alexander Korotkov
Postgres Professional: http://www.postgrespro.com
The Russian Postgres Company
^ permalink raw reply [nested|flat] 17+ messages in thread
* Re: Bug in GiST paring heap comparator
@ 2019-09-09 17:30 Nikita Glukhov <n.gluhov@postgrespro.ru>
parent: Alexander Korotkov <a.korotkov@postgrespro.ru>
0 siblings, 1 reply; 17+ messages in thread
From: Nikita Glukhov @ 2019-09-09 17:30 UTC (permalink / raw)
To: Alexander Korotkov <a.korotkov@postgrespro.ru>; Heikki Linnakangas <hlinnaka@iki.fi>; +Cc: pgsql-hackers
On 08.09.2019 22:32, Alexander Korotkov wrote:
> On Fri, Sep 6, 2019 at 5:44 PM Alexander Korotkov
> <a.korotkov@postgrespro.ru> wrote:
>> I'm going to push both if no objections.
> So, pushed!
Two years ago there was a similar patch for this issue:
https://www.postgresql.org/message-id/1499c9d0-075a-3014-d2aa-ba59121b3728%40postgrespro.ru
Sorry that I looked at this thread too late.
--
Nikita Glukhov
Postgres Professional: http://www.postgrespro.com
The Russian Postgres Company
^ permalink raw reply [nested|flat] 17+ messages in thread
* Re: Bug in GiST paring heap comparator
@ 2019-09-09 19:47 Alexander Korotkov <a.korotkov@postgrespro.ru>
parent: Nikita Glukhov <n.gluhov@postgrespro.ru>
0 siblings, 1 reply; 17+ messages in thread
From: Alexander Korotkov @ 2019-09-09 19:47 UTC (permalink / raw)
To: Nikita Glukhov <n.gluhov@postgrespro.ru>; +Cc: Heikki Linnakangas <hlinnaka@iki.fi>; pgsql-hackers
On Mon, Sep 9, 2019 at 8:32 PM Nikita Glukhov <n.gluhov@postgrespro.ru> wrote:
> On 08.09.2019 22:32, Alexander Korotkov wrote:
>
> > On Fri, Sep 6, 2019 at 5:44 PM Alexander Korotkov
> > <a.korotkov@postgrespro.ru> wrote:
> >> I'm going to push both if no objections.
> > So, pushed!
>
> Two years ago there was a similar patch for this issue:
> https://www.postgresql.org/message-id/1499c9d0-075a-3014-d2aa-ba59121b3728%40postgrespro.ru
>
> Sorry that I looked at this thread too late.
I see, thanks.
You patch seems a bit less cumbersome thanks to using GISTDistance
struct. You don't have to introduce separate array with null flags.
But it's harder too keep index_store_float8_orderby_distances() used
by both GiST and SP-GiST.
What do you think? You can rebase your patch can propose that as refactoring.
------
Alexander Korotkov
Postgres Professional: http://www.postgrespro.com
The Russian Postgres Company
^ permalink raw reply [nested|flat] 17+ messages in thread
* Re: Bug in GiST paring heap comparator
@ 2019-09-11 00:31 Nikita Glukhov <n.gluhov@postgrespro.ru>
parent: Alexander Korotkov <a.korotkov@postgrespro.ru>
0 siblings, 1 reply; 17+ messages in thread
From: Nikita Glukhov @ 2019-09-11 00:31 UTC (permalink / raw)
To: Alexander Korotkov <a.korotkov@postgrespro.ru>; pgsql-hackers; +Cc: Heikki Linnakangas <hlinnaka@iki.fi>
On 09.09.2019 22:47, Alexander Korotkov wrote:
> On Mon, Sep 9, 2019 at 8:32 PM Nikita Glukhov <n.gluhov@postgrespro.ru> wrote:
>> On 08.09.2019 22:32, Alexander Korotkov wrote:
>>
>>> On Fri, Sep 6, 2019 at 5:44 PM Alexander Korotkov
>>> <a.korotkov@postgrespro.ru> wrote:
>>>> I'm going to push both if no objections.
>>> So, pushed!
>> Two years ago there was a similar patch for this issue:
>> https://www.postgresql.org/message-id/1499c9d0-075a-3014-d2aa-ba59121b3728%40postgrespro.ru
>>
>> Sorry that I looked at this thread too late.
> I see, thanks.
>
> You patch seems a bit less cumbersome thanks to using GISTDistance
> struct. You don't have to introduce separate array with null flags.
> But it's harder too keep index_store_float8_orderby_distances() used
> by both GiST and SP-GiST.
>
> What do you think? You can rebase your patch can propose that as refactoring.
Rebased patch with refactoring is attached.
During this rebase I found that SP-GiST code has similar problems with NULLs.
All SP-GiST functions do not check SK_ISNULL flag of ordering ScanKeys, and
that leads to segfaults. In the following test, index is searched with
non-NULL key first and then with NULL key, that leads to a crash:
CREATE TABLE t AS SELECT point(x, y) p
FROM generate_series(0, 100) x, generate_series(0, 100) y;
CREATE INDEX ON t USING spgist (p);
-- crash
SELECT (SELECT p FROM t ORDER BY p <-> pt LIMIT 1)
FROM (VALUES (point '1,2'), (NULL)) pts(pt);
After adding SK_ISNULL checks and starting to produce NULL distances, we need to
store NULL flags for distance somewhere. Existing singleton flag for the whole
SPGistSearchItem is not sufficient anymore.
So, I introduced structure IndexOrderByDistance and used it everywhere in the
GiST and SP-GiST code instead of raw double distances.
SP-GiST order-by-distance code can be further refactored so that user functions
do not have to worry about SK_ISNULL checks.
--
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.patch (30.1K, ../../e9547b97-ed11-8e0e-6f40-0777d2407207@postgrespro.ru/3-0001-Fix-GiST-and-SP-GiST-ordering-by-distance-for-NULLs.patch)
download | inline diff:
From 199887de4f970a0f831c0518e34bf3c70c3d1aad 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/4] Fix GiST and SP-GiST ordering by distance for NULLs and
NaNs
---
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 | 19 +++++--
src/backend/access/spgist/spgquadtreeproc.c | 2 +-
src/backend/access/spgist/spgscan.c | 60 ++++++++++++--------
src/backend/utils/adt/geo_spgist.c | 40 +++++++++----
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 | 18 +++---
src/test/regress/expected/create_index_spgist.out | 10 ++++
src/test/regress/sql/create_index_spgist.sql | 5 ++
14 files changed, 167 insertions(+), 138 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/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..1059456 100644
--- a/src/backend/access/spgist/spgproc.c
+++ b/src/backend/access/spgist/spgproc.c
@@ -59,20 +59,29 @@ 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);
+ if (orderbys->sk_flags & SK_ISNULL)
+ {
+ distance->isnull = true;
+ distance->value = 0;
+ }
+ else
+ {
+ 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..a837789 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.
@@ -58,14 +59,23 @@ pairingheap_SpGistSearchItem_cmp(const pairingheap_node *a,
/* Order according to distance comparison */
for (i = 0; i < so->numberOfOrderBys; 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 =
@@ -113,7 +124,7 @@ spgAllocSearchItem(SpGistScanOpaque so, bool isnull, double *distances)
if (!isnull && so->numberOfOrderBys > 0)
memcpy(item->distances, distances,
- so->numberOfOrderBys * sizeof(double));
+ sizeof(item->distances[0]) * so->numberOfOrderBys);
return item;
}
@@ -297,15 +308,17 @@ spgbeginscan(Relation rel, int keysz, int orderbysz)
palloc(sizeof(Oid) * 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 *)
@@ -409,7 +422,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 +452,7 @@ spgLeafTest(SpGistScanOpaque so, SpGistSearchItem *item,
bool *reportedSome, storeRes_func storeRes)
{
Datum leafValue;
- double *distances;
+ IndexOrderByDistance *distances;
bool result;
bool recheck;
bool recheckDistances;
@@ -549,7 +562,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 +646,7 @@ spgInnerTest(SpGistScanOpaque so, SpGistSearchItem *item,
{
int nodeN = out.nodeNumbers[i];
SpGistSearchItem *innerItem;
- double *distances;
+ IndexOrderByDistance *distances;
Assert(nodeN >= 0 && nodeN < nNodes);
@@ -847,7 +860,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 +887,7 @@ spggetbitmap(IndexScanDesc scan, TIDBitmap *tbm)
static void
storeGettuple(SpGistScanOpaque so, ItemPointer heapPtr,
Datum leafValue, bool isnull, bool recheck, bool recheckDistances,
- double *distances)
+ IndexOrderByDistance *distances)
{
Assert(so->nPtrs < MaxIndexTuplesPerPage);
so->heapPtrs[so->nPtrs] = *heapPtr;
@@ -887,9 +900,11 @@ storeGettuple(SpGistScanOpaque so, ItemPointer heapPtr,
so->distances[so->nPtrs] = NULL;
else
{
- Size size = sizeof(double) * so->numberOfOrderBys;
+ Size size = sizeof(distances[0]) * so->numberOfOrderBys;
+
+ so->distances[so->nPtrs] = palloc(size);
- so->distances[so->nPtrs] = memcpy(palloc(size), distances, size);
+ memcpy(so->distances[so->nPtrs], distances, size);
}
}
@@ -929,7 +944,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..cde6264 100644
--- a/src/backend/utils/adt/geo_spgist.c
+++ b/src/backend/utils/adt/geo_spgist.c
@@ -580,24 +580,33 @@ 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);
+ if (in->orderbys[j].sk_flags & SK_ISNULL)
+ {
+ distances[j].value = 0;
+ distances[j].isnull = true;
+ }
+ else
+ {
+ 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 +631,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,16 +712,25 @@ 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;
for (j = 0; j < in->norderbys; j++)
{
- Point *pt = DatumGetPointP(in->orderbys[j].sk_argument);
-
- distances[j] = pointToRectBoxDistance(pt, next_rect_box);
+ if (in->orderbys[j].sk_flags & SK_ISNULL)
+ {
+ distances[j].value = 0;
+ distances[j].isnull = true;
+ }
+ else
+ {
+ Point *pt = DatumGetPointP(in->orderbys[j].sk_argument);
+
+ 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..2875c1f 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
@@ -178,8 +179,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 +196,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 +462,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';
--
2.7.4
^ permalink raw reply [nested|flat] 17+ messages in thread
* Re: Bug in GiST paring heap comparator
@ 2019-09-12 13:45 Alexander Korotkov <a.korotkov@postgrespro.ru>
parent: Nikita Glukhov <n.gluhov@postgrespro.ru>
0 siblings, 1 reply; 17+ messages in thread
From: Alexander Korotkov @ 2019-09-12 13:45 UTC (permalink / raw)
To: Nikita Glukhov <n.gluhov@postgrespro.ru>; +Cc: pgsql-hackers; Heikki Linnakangas <hlinnaka@iki.fi>
On Wed, Sep 11, 2019 at 3:34 AM Nikita Glukhov <n.gluhov@postgrespro.ru> wrote:
> On 09.09.2019 22:47, Alexander Korotkov wrote:
>
> On Mon, Sep 9, 2019 at 8:32 PM Nikita Glukhov <n.gluhov@postgrespro.ru> wrote:
>
> On 08.09.2019 22:32, Alexander Korotkov wrote:
>
> On Fri, Sep 6, 2019 at 5:44 PM Alexander Korotkov
> <a.korotkov@postgrespro.ru> wrote:
>
> I'm going to push both if no objections.
>
> So, pushed!
>
> Two years ago there was a similar patch for this issue:
> https://www.postgresql.org/message-id/1499c9d0-075a-3014-d2aa-ba59121b3728%40postgrespro.ru
>
> Sorry that I looked at this thread too late.
>
> I see, thanks.
>
> You patch seems a bit less cumbersome thanks to using GISTDistance
> struct. You don't have to introduce separate array with null flags.
> But it's harder too keep index_store_float8_orderby_distances() used
> by both GiST and SP-GiST.
>
> What do you think? You can rebase your patch can propose that as refactoring.
>
> Rebased patch with refactoring is attached.
>
> During this rebase I found that SP-GiST code has similar problems with NULLs.
> All SP-GiST functions do not check SK_ISNULL flag of ordering ScanKeys, and
> that leads to segfaults. In the following test, index is searched with
> non-NULL key first and then with NULL key, that leads to a crash:
>
> CREATE TABLE t AS SELECT point(x, y) p
> FROM generate_series(0, 100) x, generate_series(0, 100) y;
>
> CREATE INDEX ON t USING spgist (p);
>
> -- crash
> SELECT (SELECT p FROM t ORDER BY p <-> pt LIMIT 1)
> FROM (VALUES (point '1,2'), (NULL)) pts(pt);
>
>
> After adding SK_ISNULL checks and starting to produce NULL distances, we need to
> store NULL flags for distance somewhere. Existing singleton flag for the whole
> SPGistSearchItem is not sufficient anymore.
>
>
> So, I introduced structure IndexOrderByDistance and used it everywhere in the
> GiST and SP-GiST code instead of raw double distances.
>
>
> SP-GiST order-by-distance code can be further refactored so that user functions
> do not have to worry about SK_ISNULL checks.
It doesn't seem SP-GiST inner_consistent and leaf_consistent functions
can handle NULL scan keys for now. So should we let them handle NULL
orderby keys? If we assume that NULL arguments produce NULL
distances, we can evade changing the code of opclasses.
Also, I've noticed IndexOrderByDistance is missed in typedefs.list.
------
Alexander Korotkov
Postgres Professional: http://www.postgrespro.com
The Russian Postgres Company
^ permalink raw reply [nested|flat] 17+ messages in thread
* Re: Bug in GiST paring heap comparator
@ 2019-09-13 14:20 Nikita Glukhov <n.gluhov@postgrespro.ru>
parent: Alexander Korotkov <a.korotkov@postgrespro.ru>
0 siblings, 1 reply; 17+ messages in thread
From: Nikita Glukhov @ 2019-09-13 14:20 UTC (permalink / raw)
To: Alexander Korotkov <a.korotkov@postgrespro.ru>; +Cc: pgsql-hackers; Heikki Linnakangas <hlinnaka@iki.fi>
On 12.09.2019 16:45, Alexander Korotkov wrote:
> On Wed, Sep 11, 2019 at 3:34 AM Nikita Glukhov <n.gluhov@postgrespro.ru> wrote:
>> On 09.09.2019 22:47, Alexander Korotkov wrote:
>>
>> On Mon, Sep 9, 2019 at 8:32 PM Nikita Glukhov <n.gluhov@postgrespro.ru> wrote:
>>
>> On 08.09.2019 22:32, Alexander Korotkov wrote:
>>
>> On Fri, Sep 6, 2019 at 5:44 PM Alexander Korotkov
>> <a.korotkov@postgrespro.ru> wrote:
>>
>> I'm going to push both if no objections.
>>
>> So, pushed!
>>
>> Two years ago there was a similar patch for this issue:
>> https://www.postgresql.org/message-id/1499c9d0-075a-3014-d2aa-ba59121b3728%40postgrespro.ru
>>
>> Sorry that I looked at this thread too late.
>>
>> I see, thanks.
>>
>> You patch seems a bit less cumbersome thanks to using GISTDistance
>> struct. You don't have to introduce separate array with null flags.
>> But it's harder too keep index_store_float8_orderby_distances() used
>> by both GiST and SP-GiST.
>>
>> What do you think? You can rebase your patch can propose that as refactoring.
>>
>> Rebased patch with refactoring is attached.
>>
>> During this rebase I found that SP-GiST code has similar problems with NULLs.
>> All SP-GiST functions do not check SK_ISNULL flag of ordering ScanKeys, and
>> that leads to segfaults. In the following test, index is searched with
>> non-NULL key first and then with NULL key, that leads to a crash:
>>
>> CREATE TABLE t AS SELECT point(x, y) p
>> FROM generate_series(0, 100) x, generate_series(0, 100) y;
>>
>> CREATE INDEX ON t USING spgist (p);
>>
>> -- crash
>> SELECT (SELECT p FROM t ORDER BY p <-> pt LIMIT 1)
>> FROM (VALUES (point '1,2'), (NULL)) pts(pt);
>>
>>
>> After adding SK_ISNULL checks and starting to produce NULL distances, we need to
>> store NULL flags for distance somewhere. Existing singleton flag for the whole
>> SPGistSearchItem is not sufficient anymore.
>>
>>
>> So, I introduced structure IndexOrderByDistance and used it everywhere in the
>> GiST and SP-GiST code instead of raw double distances.
>>
>>
>> SP-GiST order-by-distance code can be further refactored so that user functions
>> do not have to worry about SK_ISNULL checks.
> It doesn't seem SP-GiST inner_consistent and leaf_consistent functions
> can handle NULL scan keys for now. So should we let them handle NULL
> orderby keys? If we assume that NULL arguments produce NULL
> distances, we can evade changing the code of opclasses.
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?
Also I leaved usages of IndexOrderByDistance in opclasses. I think, that
may
help to minimize opclass changes in the future.
> Also, I've noticed IndexOrderByDistance is missed in typedefs.list.
Fixed.
--
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-v2.patch (34.1K, ../../ebcee467-547e-ca63-1858-4a485c4b8261@postgrespro.ru/2-0001-Fix-GiST-and-SP-GiST-ordering-by-distance-for-NULLs-v2.patch)
download | inline diff:
From edff2142fd8239bbc9cef31a885a55344e20a649 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/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 <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/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
^ permalink raw reply [nested|flat] 17+ messages in thread
* Re: Bug in GiST paring heap comparator
@ 2019-09-13 17:17 Alexander Korotkov <a.korotkov@postgrespro.ru>
parent: Nikita Glukhov <n.gluhov@postgrespro.ru>
0 siblings, 1 reply; 17+ messages in thread
From: Alexander Korotkov @ 2019-09-13 17:17 UTC (permalink / raw)
To: Nikita Glukhov <n.gluhov@postgrespro.ru>; +Cc: pgsql-hackers; Heikki Linnakangas <hlinnaka@iki.fi>
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.
------
Alexander Korotkov
Postgres Professional: http://www.postgrespro.com
The Russian Postgres Company
^ permalink raw reply [nested|flat] 17+ messages in thread
* Re: Bug in GiST paring heap comparator
@ 2019-09-16 12:44 Nikita Glukhov <n.gluhov@postgrespro.ru>
parent: Alexander Korotkov <a.korotkov@postgrespro.ru>
0 siblings, 1 reply; 17+ messages in thread
From: Nikita Glukhov @ 2019-09-16 12:44 UTC (permalink / raw)
To: Alexander Korotkov <a.korotkov@postgrespro.ru>; +Cc: pgsql-hackers; Heikki Linnakangas <hlinnaka@iki.fi>
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
^ permalink raw reply [nested|flat] 17+ messages in thread
* Re: Bug in GiST paring heap comparator
@ 2019-09-16 19:30 Alexander Korotkov <a.korotkov@postgrespro.ru>
parent: Nikita Glukhov <n.gluhov@postgrespro.ru>
0 siblings, 1 reply; 17+ messages in thread
From: Alexander Korotkov @ 2019-09-16 19:30 UTC (permalink / raw)
To: Nikita Glukhov <n.gluhov@postgrespro.ru>; +Cc: pgsql-hackers; Heikki Linnakangas <hlinnaka@iki.fi>
On Mon, Sep 16, 2019 at 3:47 PM Nikita Glukhov <n.gluhov@postgrespro.ru> wrote:
> 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.
First patch is minor editing from me and commit message is attached.
I'm going to push it if no objections.
------
Alexander Korotkov
Postgres Professional: http://www.postgrespro.com
The Russian Postgres Company
Attachments:
[application/octet-stream] 0001-Fix-GiST-and-SP-GiST-ordering-by-distance-for-NULLs-v4.patch (23.3K, ../../CAPpHfdsnNdryJ765=oqw16Nv4fKdHEJ+T5Tm07asOL6a4s3W9g@mail.gmail.com/2-0001-Fix-GiST-and-SP-GiST-ordering-by-distance-for-NULLs-v4.patch)
download | inline diff:
commit 6dbeb2ea7db71dc388397f3babf4e7be8c792696
Author: Alexander Korotkov <akorotkov@postgresql.org>
Date: Mon Sep 16 22:09:21 2019 +0300
Improve handling of NULLs in KNN-GiST and KNN-SP-GiST
This commit improves subject in two ways:
* It removes ugliness of 02f90879e7, which stores distance values and null
flags in two separate arrays after GISTSearchItem struct. Instead we pack
both distance value and null flag in IndexOrderByDistance struct. Alignment
overhead should be negligible, because we typically deal with at most few
"col op const" expressions in ORDER BY clause.
* It fixes handling of "col op NULL" expression in KNN-SP-GiST. Now, these
expression are not passed to support functions, which can't deal with them.
Instead, NULL result is implicitly assumed. It future we may decide to
teach support functions to deal with NULL arguments, but current solution is
bugfix suitable for backpatch.
Reported-by: Nikita Glukhov
Discussion: https://postgr.es/m/826f57ee-afc7-8977-c44c-6111d18b02ec%40postgrespro.ru
Author: Nikita Glukhov
Reviewed-by: Alexander Korotkov
Backpatch-through: 9.4
diff --git a/src/backend/access/gist/gistget.c b/src/backend/access/gist/gistget.c
index db633a94757..22d790d8221 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 e72bf08f952..323a19dcad1 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 2e8f53a37c8..442f41425d4 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 2bd4037af9e..cfba47067cc 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 6c56717ba77..a813b004be7 100644
--- a/src/include/access/genam.h
+++ b/src/include/access/genam.h
@@ -118,6 +118,13 @@ typedef enum IndexUniqueCheck
} IndexUniqueCheck;
+/* Nullable "ORDER BY col op const" 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 ed5b643885d..ab134c1a394 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 e0d1178f245..428e54bfbd2 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 81b4a67c390..5ccea915867 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 8e6c4533076..629936fd3d4 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 f3cdfa8a223..fb652651750 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
^ permalink raw reply [nested|flat] 17+ messages in thread
* Re: Bug in GiST paring heap comparator
@ 2019-09-19 19:14 Alexander Korotkov <a.korotkov@postgrespro.ru>
parent: Alexander Korotkov <a.korotkov@postgrespro.ru>
0 siblings, 1 reply; 17+ messages in thread
From: Alexander Korotkov @ 2019-09-19 19:14 UTC (permalink / raw)
To: Nikita Glukhov <n.gluhov@postgrespro.ru>; +Cc: pgsql-hackers; Heikki Linnakangas <hlinnaka@iki.fi>
On Mon, Sep 16, 2019 at 10:30 PM Alexander Korotkov <
a.korotkov@postgrespro.ru> wrote:
> On Mon, Sep 16, 2019 at 3:47 PM Nikita Glukhov <n.gluhov@postgrespro.ru>
> wrote:
> > 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.
>
> First patch is minor editing from me and commit message is attached.
> I'm going to push it if no objections.
>
Pushed.
------
Alexander Korotkov
Postgres Professional: http://www.postgrespro.com
The Russian Postgres Company
^ permalink raw reply [nested|flat] 17+ messages in thread
* Re: Bug in GiST paring heap comparator
@ 2019-09-19 21:15 Nikita Glukhov <n.gluhov@postgrespro.ru>
parent: Alexander Korotkov <a.korotkov@postgrespro.ru>
0 siblings, 1 reply; 17+ messages in thread
From: Nikita Glukhov @ 2019-09-19 21:15 UTC (permalink / raw)
To: Alexander Korotkov <a.korotkov@postgrespro.ru>; pgsql-hackers; +Cc: Heikki Linnakangas <hlinnaka@iki.fi>
On 19.09.2019 22:14, Alexander Korotkov wrote:
> Pushed.
Attached patch fixes premature xs_orderbynulls[] assignment. The old value of
NULL flag, not the new, should be checked before pfree()ing the old value.
--
Nikita Glukhov
Postgres Professional: http://www.postgrespro.com
The Russian Postgres Company
Attachments:
[text/x-patch] 0001-Fix-pfree-ing-of-index-order-by-distances.patch (2.1K, ../../426580d3-a668-b9d1-7b8e-f74d1a6524e0@postgrespro.ru/3-0001-Fix-pfree-ing-of-index-order-by-distances.patch)
download | inline diff:
From bf4ffb0c066dd55e027ed156790277c597f44e45 Mon Sep 17 00:00:00 2001
From: Nikita Glukhov <n.gluhov@postgrespro.ru>
Date: Fri, 20 Sep 2019 00:07:30 +0300
Subject: [PATCH] Fix pfree()ing of index order-by distances
---
src/backend/access/index/indexam.c | 18 +++++++++++-------
1 file changed, 11 insertions(+), 7 deletions(-)
diff --git a/src/backend/access/index/indexam.c b/src/backend/access/index/indexam.c
index 442f414..3a061e5 100644
--- a/src/backend/access/index/indexam.c
+++ b/src/backend/access/index/indexam.c
@@ -869,11 +869,6 @@ index_store_float8_orderby_distances(IndexScanDesc scan, Oid *orderByTypes,
for (i = 0; i < scan->numberOfOrderBys; i++)
{
- scan->xs_orderbynulls[i] = distances[i].isnull;
-
- if (scan->xs_orderbynulls[i])
- scan->xs_orderbyvals[i] = (Datum) 0;
-
if (orderByTypes[i] == FLOAT8OID)
{
#ifndef USE_FLOAT8_BYVAL
@@ -881,7 +876,11 @@ index_store_float8_orderby_distances(IndexScanDesc scan, Oid *orderByTypes,
if (!scan->xs_orderbynulls[i])
pfree(DatumGetPointer(scan->xs_orderbyvals[i]));
#endif
- if (!scan->xs_orderbynulls[i])
+ scan->xs_orderbynulls[i] = distances[i].isnull;
+
+ if (scan->xs_orderbynulls[i])
+ scan->xs_orderbyvals[i] = (Datum) 0;
+ else
scan->xs_orderbyvals[i] = Float8GetDatum(distances[i].value);
}
else if (orderByTypes[i] == FLOAT4OID)
@@ -892,7 +891,11 @@ index_store_float8_orderby_distances(IndexScanDesc scan, Oid *orderByTypes,
if (!scan->xs_orderbynulls[i])
pfree(DatumGetPointer(scan->xs_orderbyvals[i]));
#endif
- if (!scan->xs_orderbynulls[i])
+ scan->xs_orderbynulls[i] = distances[i].isnull;
+
+ if (scan->xs_orderbynulls[i])
+ scan->xs_orderbyvals[i] = (Datum) 0;
+ else
scan->xs_orderbyvals[i] = Float4GetDatum((float4) distances[i].value);
}
else
@@ -908,6 +911,7 @@ index_store_float8_orderby_distances(IndexScanDesc scan, Oid *orderByTypes,
if (scan->xs_recheckorderby)
elog(ERROR, "ORDER BY operator must return float8 or float4 if the distance function is lossy");
scan->xs_orderbynulls[i] = true;
+ scan->xs_orderbyvals[i] = (Datum) 0;
}
}
}
--
2.7.4
^ permalink raw reply [nested|flat] 17+ messages in thread
* Re: Bug in GiST paring heap comparator
@ 2019-09-24 22:19 Nikita Glukhov <n.gluhov@postgrespro.ru>
parent: Nikita Glukhov <n.gluhov@postgrespro.ru>
0 siblings, 1 reply; 17+ messages in thread
From: Nikita Glukhov @ 2019-09-24 22:19 UTC (permalink / raw)
To: Alexander Korotkov <a.korotkov@postgrespro.ru>; pgsql-hackers; +Cc: Heikki Linnakangas <hlinnaka@iki.fi>
On 20.09.2019 0:15, Nikita Glukhov wrote:
> On 19.09.2019 22:14, Alexander Korotkov wrote:
>> Pushed.
> Attached patch fixes premature xs_orderbynulls[] assignment. The old value
> of NULL flag, not the new, should be checked before pfree()ing the old value.
Attached another one-line patch that fixes incorrect number of distances used
in pairingheap_SpGistSearchItem_cmp():
- for (i = 0; i < so->numberOfOrderBys; i++)
+ for (i = 0; i < so->numberOfNonNullOrderBys; i++)
This change was present in my original commit, but it seems to have been
missed after the rebase. Sorry.
--
Nikita Glukhov
Postgres Professional: http://www.postgrespro.com
The Russian Postgres Company
Attachments:
[text/x-patch] 0001-Fix-number-of-distances-in-pairingheap_SpGistSearchI.patch (876B, ../../53536807-784c-e029-6e92-6da802ab8d60@postgrespro.ru/3-0001-Fix-number-of-distances-in-pairingheap_SpGistSearchI.patch)
download | inline diff:
From 2e58a94fd2f973257d1c8a3d9cd0b907c719a859 Mon Sep 17 00:00:00 2001
From: Nikita Glukhov <n.gluhov@postgrespro.ru>
Date: Tue, 24 Sep 2019 01:33:03 +0300
Subject: [PATCH] Fix number of distances in pairingheap_SpGistSearchItem_cmp()
---
src/backend/access/spgist/spgscan.c | 2 +-
1 file changed, 1 insertion(+), 1 deletion(-)
diff --git a/src/backend/access/spgist/spgscan.c b/src/backend/access/spgist/spgscan.c
index cfba470..6e940fd 100644
--- a/src/backend/access/spgist/spgscan.c
+++ b/src/backend/access/spgist/spgscan.c
@@ -56,7 +56,7 @@ 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]))
continue; /* NaN == NaN */
--
2.7.4
^ permalink raw reply [nested|flat] 17+ messages in thread
* Re: Bug in GiST paring heap comparator
@ 2019-09-24 22:57 Alexander Korotkov <a.korotkov@postgrespro.ru>
parent: Nikita Glukhov <n.gluhov@postgrespro.ru>
0 siblings, 0 replies; 17+ messages in thread
From: Alexander Korotkov @ 2019-09-24 22:57 UTC (permalink / raw)
To: Nikita Glukhov <n.gluhov@postgrespro.ru>; +Cc: pgsql-hackers; Heikki Linnakangas <hlinnaka@iki.fi>
On Wed, Sep 25, 2019 at 1:22 AM Nikita Glukhov <n.gluhov@postgrespro.ru> wrote:
> Attached another one-line patch that fixes incorrect number of distances used
> in pairingheap_SpGistSearchItem_cmp():
>
> - for (i = 0; i < so->numberOfOrderBys; i++)
> + for (i = 0; i < so->numberOfNonNullOrderBys; i++)
>
>
> This change was present in my original commit, but it seems to have been
> missed after the rebase. Sorry.
Pushed, thanks.
------
Alexander Korotkov
Postgres Professional: http://www.postgrespro.com
The Russian Postgres Company
^ permalink raw reply [nested|flat] 17+ messages in thread
end of thread, other threads:[~2019-09-24 22:57 UTC | newest]
Thread overview: 17+ messages (download: mbox mbox.gz follow: Atom feed)
-- links below jump to the message on this page --
2019-09-02 04:54 Bug in GiST paring heap comparator Alexander Korotkov <a.korotkov@postgrespro.ru>
2019-09-02 05:11 ` Andrey Borodin <x4mmm@yandex-team.ru>
2019-09-02 06:28 ` Heikki Linnakangas <hlinnaka@iki.fi>
2019-09-06 14:44 ` Alexander Korotkov <a.korotkov@postgrespro.ru>
2019-09-08 19:32 ` Alexander Korotkov <a.korotkov@postgrespro.ru>
2019-09-09 17:30 ` Nikita Glukhov <n.gluhov@postgrespro.ru>
2019-09-09 19:47 ` Alexander Korotkov <a.korotkov@postgrespro.ru>
2019-09-11 00:31 ` Nikita Glukhov <n.gluhov@postgrespro.ru>
2019-09-12 13:45 ` Alexander Korotkov <a.korotkov@postgrespro.ru>
2019-09-13 14:20 ` Nikita Glukhov <n.gluhov@postgrespro.ru>
2019-09-13 17:17 ` Alexander Korotkov <a.korotkov@postgrespro.ru>
2019-09-16 12:44 ` Nikita Glukhov <n.gluhov@postgrespro.ru>
2019-09-16 19:30 ` Alexander Korotkov <a.korotkov@postgrespro.ru>
2019-09-19 19:14 ` Alexander Korotkov <a.korotkov@postgrespro.ru>
2019-09-19 21:15 ` Nikita Glukhov <n.gluhov@postgrespro.ru>
2019-09-24 22:19 ` Nikita Glukhov <n.gluhov@postgrespro.ru>
2019-09-24 22:57 ` Alexander Korotkov <a.korotkov@postgrespro.ru>
This inbox is served by agora; see mirroring instructions
for how to clone and mirror all data and code used for this inbox