From: Nikita Glukhov <n.gluhov@postgrespro.ru>
To: Alexander Korotkov <aekorotkov@gmail.com>
To: Darafei Komяpa Praliaskouski <me@komzpa.net>
Cc: Tom Lane <tgl@sss.pgh.pa.us>
Cc: pgsql-hackers <pgsql-hackers@postgresql.org>
Cc: Heikki Linnakangas <hlinnaka@iki.fi>
Cc: Fedor Sigaev <teodor@sigaev.ru>
Subject: Re: compress method for spgist - 2
Date: Fri, 22 Sep 2017 03:03:50 +0300
Message-ID: <1499c9d0-075a-3014-d2aa-ba59121b3728@postgrespro.ru> (raw)
In-Reply-To: <CAPpHfdsAruXqE80v_crv=du4GoUqWgx55gXR05ZAhyRp4kxGBA@mail.gmail.com>
References: <54907069.1030506@sigaev.ru>
<CAPpHfdsoy2bJMSTtvQySJ9zN2YJmzWJBLvdHV=ZvMOm6BR0UFg@mail.gmail.com>
<20170920190059.1354.29457.pgcf@coridan.postgresql.org>
<31999.1505938053@sss.pgh.pa.us>
<CAPpHfduv0XZ_k+D3NoFMr=wFVM22D=wFZCMMswoLwBe2jAbuJw@mail.gmail.com>
<60e048d3-aa29-8289-5438-3b0c4c1d8d84@postgrespro.ru>
<CAC8Q8tJ6jPJd_BJftq9CVrUNTNM__P-H4jbNO9qr5oV=bYJU0w@mail.gmail.com>
<CAPpHfdsAruXqE80v_crv=du4GoUqWgx55gXR05ZAhyRp4kxGBA@mail.gmail.com>
List-Unsubscribe: <mailto:majordomo@postgresql.org?body=unsub%20pgsql-hackers>
On 21.09.2017 02:27, Alexander Korotkov wrote:
> On Thu, Sep 21, 2017 at 2:06 AM, Darafei "Komяpa" Praliaskouski
> <me@komzpa.net <mailto:me@komzpa.net>> wrote:
>
> It is possible for bbox->low.x to be NaN when circle->center.x
> is and
> circle->radius are both +Infinity.
>
>
> What is rationale behind this circle?
>
>
> I would prefer to rather forbid any geometries with infs and nans.
> However, then upgrade process will suffer. User with such geometries
> would get errors during dump/restore, pg_upgraded instances would
> still contain invalid values...
>
> It seems to me that any circle with radius of any Infinity should
> become a [-Infinity .. Infinity, -Infinity .. Infinity] box.Then
> you won't have NaNs, and index structure shouldn't be broken.
>
>
> We probably should produce [-Infinity .. Infinity, -Infinity ..
> Infinity] box for any geometry containing inf or nan. That MBR would
> be founded for any query, saying: "index can't help you for this kind
> value, only recheck can deal with that". Therefore, we would at least
> guarantee that results of sequential scan and index scan are the same.
>
I have looked at the GiST KNN code and found the same errors for NaNs,
infinities and NULLs as in my SP-GiST KNN patch.
Attached two patches:
1. Fix NaN-inconsistencies in circle's bounding boxes computed in GiST
compress
method leading to the failed Assert(box->low.x <= box->high.x) in
computeDistance() from src/backend/access/gist/gistproc.c by
transforming NaNs
into infinities (corresponding test case provided in the second patch).
2. Fix ordering of NULL, NaN and infinite distances by GiST. This distance
values could be mixed because NULL distances were transformed into
infinities,
and there was no special processing for NaNs in KNN queue's comparison
function.
At first I tried just to set recheck flag for NULL distances, but it did not
work for index-only scans because they do not support rechecking. So I had
to add a special flag for NULL distances.
Should I start a separate thread for this issue and add patches to
commitfest?
--
Nikita Glukhov
Postgres Professional: http://www.postgrespro.com
The Russian Postgres Company
--
Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org)
To make changes to your subscription:
http://www.postgresql.org/mailpref/pgsql-hackersAttachments:download all (2 files, .tar.gz)0001-Fix-circle-bounding-box-inconsistency-in-GiST-compress-method-v01.patch (text/x-patch, 1.1K) download
From 52ab493cfe1ec6260578054b71f2c48e77d4850a Mon Sep 17 00:00:00 2001
From: Nikita Glukhov <n.gluhov@postgrespro.ru>
Date: Fri, 22 Sep 2017 02:06:48 +0300
Subject: [PATCH 1/2] Fix circle bounding box inconsistency in GiST compress
method
---
src/backend/access/gist/gistproc.c | 10 ++++++++++
1 file changed, 10 insertions(+)
diff --git a/src/backend/access/gist/gistproc.c b/src/backend/access/gist/gistproc.cindex 08990f5..2699304 100644--- a/src/backend/access/gist/gistproc.c+++ b/src/backend/access/gist/gistproc.c@@ -1149,6 +1149,16 @@ gist_circle_compress(PG_FUNCTION_ARGS)
r->high.y = in->center.y + in->radius;
r->low.y = in->center.y - in->radius;
+ /* avoid box inconsistency by transforming NaNs into infinities */+ if (isnan(r->high.x))+ r->high.x = get_float8_infinity();+ if (isnan(r->high.y))+ r->high.y = get_float8_infinity();+ if (isnan(r->low.x))+ r->low.x = -get_float8_infinity();+ if (isnan(r->low.y))+ r->low.y = -get_float8_infinity();+
retval = (GISTENTRY *) palloc(sizeof(GISTENTRY));
gistentryinit(*retval, PointerGetDatum(r),
entry->rel, entry->page,
--
2.7.4
0002-Fix-GiST-ordering-by-distance-for-NULLs-and-NaNs-v01.patch (text/x-patch, 12.0K) download
From 066ad9104ec0e967e20e820977286f001e4055a4 Mon Sep 17 00:00:00 2001
From: Nikita Glukhov <n.gluhov@postgrespro.ru>
Date: Thu, 21 Sep 2017 19:09:02 +0300
Subject: [PATCH 2/2] Fix GiST ordering by distance for NULLs and NaNs
---
src/backend/access/gist/gistget.c | 29 ++++++++++-------
src/backend/access/gist/gistscan.c | 36 +++++++++++++++++++--
src/include/access/gist_private.h | 13 ++++++--
src/test/regress/expected/gist.out | 64 ++++++++++++++++++++++++++++++++++++++
src/test/regress/sql/gist.sql | 60 +++++++++++++++++++++++++++++++++++
5 files changed, 184 insertions(+), 18 deletions(-)
diff --git a/src/backend/access/gist/gistget.c b/src/backend/access/gist/gistget.cindex 760ea0c..7fed700 100644--- a/src/backend/access/gist/gistget.c+++ b/src/backend/access/gist/gistget.c@@ -132,7 +132,7 @@ gistindex_keytest(IndexScanDesc scan,
GISTSTATE *giststate = so->giststate;
ScanKey key = scan->keyData;
int keySize = scan->numberOfKeys;
- double *distance_p;+ GISTDistance *distance_p;
Relation r = scan->indexRelation;
*recheck_p = false;
@@ -150,7 +150,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->distances[i].value = -get_float8_infinity();+ so->distances[i].isnull = false;+ }
return true;
}
@@ -248,7 +251,8 @@ 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();+ distance_p->value = get_float8_nan();+ distance_p->isnull = true;
}
else
{
@@ -285,7 +289,8 @@ gistindex_keytest(IndexScanDesc scan,
ObjectIdGetDatum(key->sk_subtype),
PointerGetDatum(&recheck));
*recheck_distances_p |= recheck;
- *distance_p = DatumGetFloat8(dist);+ distance_p->value = DatumGetFloat8(dist);+ distance_p->isnull = false;
}
key++;
@@ -319,8 +324,8 @@ gistindex_keytest(IndexScanDesc scan,
* sibling will be processed next.
*/
static void
-gistScanPage(IndexScanDesc scan, GISTSearchItem *pageItem, double *myDistances,- TIDBitmap *tbm, int64 *ntids)+gistScanPage(IndexScanDesc scan, GISTSearchItem *pageItem,+ GISTDistance *myDistances, TIDBitmap *tbm, int64 *ntids)
{
GISTScanOpaque so = (GISTScanOpaque) scan->opaque;
GISTSTATE *giststate = so->giststate;
@@ -367,7 +372,7 @@ gistScanPage(IndexScanDesc scan, GISTSearchItem *pageItem, double *myDistances,
/* Insert it into the queue using same distances as for this page */
memcpy(item->distances, myDistances,
- sizeof(double) * scan->numberOfOrderBys);+ sizeof(item->distances[0]) * scan->numberOfOrderBys);
pairingheap_add(so->queue, &item->phNode);
@@ -497,7 +502,7 @@ 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);+ sizeof(item->distances[0]) * scan->numberOfOrderBys);
pairingheap_add(so->queue, &item->phNode);
@@ -571,8 +576,8 @@ getNextNearest(IndexScanDesc scan)
if (!scan->xs_orderbynulls[i])
pfree(DatumGetPointer(scan->xs_orderbyvals[i]));
#endif
- scan->xs_orderbyvals[i] = Float8GetDatum(item->distances[i]);- scan->xs_orderbynulls[i] = false;+ scan->xs_orderbyvals[i] = Float8GetDatum(item->distances[i].value);+ scan->xs_orderbynulls[i] = item->distances[i].isnull;
}
else if (so->orderByTypes[i] == FLOAT4OID)
{
@@ -582,8 +587,8 @@ getNextNearest(IndexScanDesc scan)
if (!scan->xs_orderbynulls[i])
pfree(DatumGetPointer(scan->xs_orderbyvals[i]));
#endif
- scan->xs_orderbyvals[i] = Float4GetDatum((float4) item->distances[i]);- scan->xs_orderbynulls[i] = false;+ scan->xs_orderbyvals[i] = Float4GetDatum((float4) item->distances[i].value);+ scan->xs_orderbynulls[i] = item->distances[i].isnull;
}
else
{
diff --git a/src/backend/access/gist/gistscan.c b/src/backend/access/gist/gistscan.cindex 058544e..95cb554 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"
@@ -36,8 +38,36 @@ 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;+ double da;+ double db;++ if (sa->distances[i].isnull)+ {+ if (sb->distances[i].isnull)+ continue; /* NULL = NULL */++ return -1; /* NULL > non-NULL */+ }++ if (sb->distances[i].isnull)+ return 1; /* non-NULL < NULL */++ da = sa->distances[i].value;+ db = sb->distances[i].value;++ if (isnan(da))+ {+ if (isnan(db))+ continue; /* NaN = NaN */++ return -1; /* NaN > non-NaN */+ }++ if (isnan(db))+ return 1; /* non-NaN < NaN */++ if (da != db)+ return (da < db) ? 1 : -1;
}
/* Heap items go before inner pages, to ensure a depth-first search */
@@ -81,7 +111,7 @@ 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->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/include/access/gist_private.h b/src/include/access/gist_private.hindex bfef2df..2ae3162 100644--- a/src/include/access/gist_private.h+++ b/src/include/access/gist_private.h@@ -125,6 +125,13 @@ typedef struct GISTSearchHeapItem
* LP_DEAD */
} GISTSearchHeapItem;
+/* Nullable distance */+typedef struct GISTDistance+{+ double value;+ bool isnull;+} GISTDistance;+
/* Unvisited item, either index page or heap tuple */
typedef struct GISTSearchItem
{
@@ -136,13 +143,13 @@ 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+ GISTDistance 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) (offsetof(GISTSearchItem, distances) + sizeof(GISTDistance) * (n_distances))
/*
* GISTScanOpaqueData: private state for a scan of a GiST index
@@ -158,7 +165,7 @@ typedef struct GISTScanOpaqueData
bool firstCall; /* true until first gistgettuple call */
/* pre-allocated workspace arrays */
- double *distances; /* output area for gistindex_keytest */+ GISTDistance *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/test/regress/expected/gist.out b/src/test/regress/expected/gist.outindex 91f9998..6f165e6 100644--- a/src/test/regress/expected/gist.out+++ b/src/test/regress/expected/gist.out@@ -225,3 +225,67 @@ reset enable_seqscan;
reset enable_bitmapscan;
reset enable_indexonlyscan;
drop table gist_tbl;
+-- Test ORDER BY circle <-> point with Inifinities and NaNs+CREATE TABLE gist_circle_tbl (id int, c circle);+INSERT INTO gist_circle_tbl+ SELECT (x - 1) * 100 + y, circle(point(x * 10, y * 10), 1 + (x + y) % 10)+ FROM generate_series(1, 100) x,+ generate_series(1, 100) y;+INSERT INTO gist_circle_tbl+ SELECT i, '<(200, 300), 5>'+ FROM generate_series(10001, 11000) AS i;+INSERT INTO gist_circle_tbl+ VALUES+ (11001, NULL),+ (11002, NULL),+ (11003, '<(0,100), infinity>'),+ (11004, '<(-infinity,0),1000>'),+ (11005, '<(infinity,-infinity),infinity>');+CREATE INDEX gist_circle_tbl_idx ON gist_circle_tbl USING gist(c);+-- get ordering results from seq scan+SET enable_seqscan TO on;+SET enable_indexscan TO off;+EXPLAIN (COSTS OFF)+SELECT rank() OVER (ORDER BY c <-> point '123,456') n, c <-> point '123,456' dist, id+FROM gist_circle_tbl;+ QUERY PLAN +------------------------------------------------+ WindowAgg+ -> Sort+ Sort Key: ((c <-> '(123,456)'::point))+ -> Seq Scan on gist_circle_tbl+(4 rows)++CREATE TABLE gist_circle_tbl_ord_seq AS+ SELECT rank() OVER (ORDER BY c <-> point '123,456') n, c <-> point '123,456' dist, id+ FROM gist_circle_tbl;+-- get ordering results from index scan+SET enable_seqscan TO off;+SET enable_indexscan TO on;+EXPLAIN (COSTS OFF)+SELECT rank() OVER (ORDER BY c <-> point '123,456') n, c <-> point '123,456' dist, id+FROM gist_circle_tbl;+ QUERY PLAN +---------------------------------------------------------------+ WindowAgg+ -> Index Scan using gist_circle_tbl_idx on gist_circle_tbl+ Order By: (c <-> '(123,456)'::point)+(3 rows)++CREATE TABLE gist_circle_tbl_ord_idx AS+ SELECT rank() OVER (ORDER BY c <-> point '123,456') n, c <-> point '123,456' dist, id+ FROM gist_circle_tbl;+-- compare results+SELECT *+FROM gist_circle_tbl_ord_seq seq FULL JOIN gist_circle_tbl_ord_idx idx USING (n, id)+WHERE seq.id IS NULL OR idx.id IS NULL;+ n | id | dist | dist +---+----+------+------+(0 rows)++-- clean up+RESET enable_seqscan;+RESET enable_indexscan;+DROP TABLE gist_circle_tbl;+DROP TABLE gist_circle_tbl_ord_seq;+DROP TABLE gist_circle_tbl_ord_idx;diff --git a/src/test/regress/sql/gist.sql b/src/test/regress/sql/gist.sqlindex 49126fd..a603e72 100644--- a/src/test/regress/sql/gist.sql+++ b/src/test/regress/sql/gist.sql@@ -120,3 +120,63 @@ reset enable_bitmapscan;
reset enable_indexonlyscan;
drop table gist_tbl;
+++-- Test ORDER BY circle <-> point with Inifinities and NaNs+CREATE TABLE gist_circle_tbl (id int, c circle);++INSERT INTO gist_circle_tbl+ SELECT (x - 1) * 100 + y, circle(point(x * 10, y * 10), 1 + (x + y) % 10)+ FROM generate_series(1, 100) x,+ generate_series(1, 100) y;++INSERT INTO gist_circle_tbl+ SELECT i, '<(200, 300), 5>'+ FROM generate_series(10001, 11000) AS i;++INSERT INTO gist_circle_tbl+ VALUES+ (11001, NULL),+ (11002, NULL),+ (11003, '<(0,100), infinity>'),+ (11004, '<(-infinity,0),1000>'),+ (11005, '<(infinity,-infinity),infinity>');++CREATE INDEX gist_circle_tbl_idx ON gist_circle_tbl USING gist(c);++-- get ordering results from seq scan+SET enable_seqscan TO on;+SET enable_indexscan TO off;++EXPLAIN (COSTS OFF)+SELECT rank() OVER (ORDER BY c <-> point '123,456') n, c <-> point '123,456' dist, id+FROM gist_circle_tbl;++CREATE TABLE gist_circle_tbl_ord_seq AS+ SELECT rank() OVER (ORDER BY c <-> point '123,456') n, c <-> point '123,456' dist, id+ FROM gist_circle_tbl;++-- get ordering results from index scan+SET enable_seqscan TO off;+SET enable_indexscan TO on;++EXPLAIN (COSTS OFF)+SELECT rank() OVER (ORDER BY c <-> point '123,456') n, c <-> point '123,456' dist, id+FROM gist_circle_tbl;++CREATE TABLE gist_circle_tbl_ord_idx AS+ SELECT rank() OVER (ORDER BY c <-> point '123,456') n, c <-> point '123,456' dist, id+ FROM gist_circle_tbl;++-- compare results+SELECT *+FROM gist_circle_tbl_ord_seq seq FULL JOIN gist_circle_tbl_ord_idx idx USING (n, id)+WHERE seq.id IS NULL OR idx.id IS NULL;++-- clean up+RESET enable_seqscan;+RESET enable_indexscan;++DROP TABLE gist_circle_tbl;+DROP TABLE gist_circle_tbl_ord_seq;+DROP TABLE gist_circle_tbl_ord_idx;--
2.7.4
Reply instructions:
You may reply publicly to this message via plain-text email
using any one of the following methods:
* Reply to all the recipients using the --to and --cc options:
reply via email
To: pgsql-hackers@postgresql.org
Cc: n.gluhov@postgrespro.ru, aekorotkov@gmail.com, me@komzpa.net, tgl@sss.pgh.pa.us, hlinnaka@iki.fi, teodor@sigaev.ru
Subject: Re: compress method for spgist - 2
In-Reply-To: <1499c9d0-075a-3014-d2aa-ba59121b3728@postgrespro.ru>
* Save the following mbox file, import it into your mail client,
and reply-to-all from there: mbox
This inbox is served by DDX for PostgreSQL; see mirroring instructions
for how to clone and mirror all data and code used for this inbox