Re: [HACKERS] compress method for spgist - 2

[Nikita Glukhov]

On 21.09.2017 02:27, Alexander Korotkov wrote:

On Thu, Sep 21, 2017 at 2:06 AM, Darafei "Komяpa" Praliaskouski 
> 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
>From 52ab493cfe1ec6260578054b71f2c48e77d4850a Mon Sep 17 00:00:00 2001
From: Nikita Glukhov 
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.c
index 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

>From 066ad9104ec0e967e20e820977286f001e4055a4 Mon Sep 17 00:00:00 2001
From: Nikita Glukhov 
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.c
index 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 */

Re: [HACKERS] compress method for spgist - 2

[Alexander Korotkov]

On Thu, Sep 21, 2017 at 3:14 AM, Tom Lane  wrote:

> Alexander Korotkov  writes:
> > On Thu, Sep 21, 2017 at 2:06 AM, Darafei "Komяpa" Praliaskouski <
> >> 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.
>
> Hm, we can do better in at least some cases, eg for a box ((0,1),(1,inf))
> there's no reason to give up our knowledge of finite bounds for the
> other three boundaries.  But certainly for a NaN circle radius
> what you suggest seems the most sensible thing to do.
>

OK.  I'll try implement this for circles.

--
Alexander Korotkov
Postgres Professional: http://www.postgrespro.com
The Russian Postgres Company

Re: [HACKERS] compress method for spgist - 2

[Tom Lane]

Alexander Korotkov  writes:
> On Thu, Sep 21, 2017 at 2:06 AM, Darafei "Komяpa" Praliaskouski <
> m...@komzpa.net> wrote:
>> 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...

Yeah, that ship has sailed unfortunately.

>> 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.

Hm, we can do better in at least some cases, eg for a box ((0,1),(1,inf))
there's no reason to give up our knowledge of finite bounds for the
other three boundaries.  But certainly for a NaN circle radius
what you suggest seems the most sensible thing to do.

regards, tom lane


-- 
Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org)
To make changes to your subscription:
http://www.postgresql.org/mailpref/pgsql-hackers

Re: [HACKERS] compress method for spgist - 2

[Alexander Korotkov]

On Thu, Sep 21, 2017 at 2:06 AM, Darafei "Komяpa" Praliaskouski <
m...@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.

--
Alexander Korotkov
Postgres Professional: http://www.postgrespro.com
The Russian Postgres Company

Re: [HACKERS] compress method for spgist - 2

[Tom Lane]

=?UTF-8?Q?Darafei_=22Kom=D1=8Fpa=22_Praliaskouski?=  writes:
> If it happens because NaN > Infinity, then the check should be not for
> isnan, but for if (low>high){swap(high, low)}.

Yeah, the same idea had occurred to me.  It'd still need a comment, but
at least it's slightly more apparent what we're trying to ensure.

regards, tom lane


-- 
Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org)
To make changes to your subscription:
http://www.postgresql.org/mailpref/pgsql-hackers

Re: [HACKERS] compress method for spgist - 2

[Komяpa]

>
> 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?
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.

If it happens because NaN > Infinity, then the check should be not for
isnan, but for if (low>high){swap(high, low)}. It probably should be a part
of box, not a part of circle, maths.

Re: [HACKERS] compress method for spgist - 2

[Tom Lane]

Nikita Glukhov  writes:
> On 20.09.2017 23:19, Alexander Korotkov wrote:
>> On Wed, Sep 20, 2017 at 11:07 PM, Tom Lane > > wrote:
>>> Maybe I'm missing something, but it appears to me that it's
>>> impossible for bbox->low.x to be NaN unless circle->center.x and/or
>>> circle->radius is a NaN, in which case bbox->high.x would also have been 
>>> computed as a NaN,
>>> making the swap entirely useless.

> It is possible for bbox->low.x to be NaN when circle->center.x is and
> circle->radius are both +Infinity.  Without this float-order-preserving 
> swapping
> one regression test for KNN with ORDER BY index will be totally broken 
> (you can
> try it: https://github.com/glukhovn/postgres/tree/knn).

If that's the reasoning, not having a comment explaining it is
inexcusable.  Do you really think people will understand what
the code is doing?

regards, tom lane


-- 
Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org)
To make changes to your subscription:
http://www.postgresql.org/mailpref/pgsql-hackers

Re: [HACKERS] compress method for spgist - 2

[Nikita Glukhov]

On 20.09.2017 23:19, Alexander Korotkov wrote:

On Wed, Sep 20, 2017 at 11:07 PM, Tom Lane > wrote:


Darafei Praliaskouski > writes:
> I have some questions about the circles example though.

>  * What is the reason for isnan check and swap of box ordinates
for circle? It wasn't in the code previously.

I hadn't paid any attention to this patch previously, but this comment
excited my curiosity, so I went and looked:

+       bbox->high.x = circle->center.x + circle->radius;
+       bbox->low.x = circle->center.x - circle->radius;
+       bbox->high.y = circle->center.y + circle->radius;
+       bbox->low.y = circle->center.y - circle->radius;
+
+       if (isnan(bbox->low.x))
+       {
+               double tmp = bbox->low.x;
+               bbox->low.x = bbox->high.x;
+               bbox->high.x = tmp;
+       }

Maybe I'm missing something, but it appears to me that it's
impossible for
bbox->low.x to be NaN unless circle->center.x and/or
circle->radius is a
NaN, in which case bbox->high.x would also have been computed as a
NaN,
making the swap entirely useless.  Likewise for the Y case.  There
may be
something useful to do about NaNs here, but this doesn't seem like it.

Yeah, +1.



It is possible for bbox->low.x to be NaN when circle->center.x is and
circle->radius are both +Infinity.  Without this float-order-preserving 
swapping
one regression test for KNN with ORDER BY index will be totally broken 
(you can
try it: https://github.com/glukhovn/postgres/tree/knn). Unfortunately, I 
do not
remember exactly why, but most likely because of the incorrect index 
structure.


--
Nikita Glukhov
Postgres Professional: http://www.postgrespro.com
The Russian Postgres Company

Re: [HACKERS] compress method for spgist - 2

[Alexander Korotkov]

On Wed, Sep 20, 2017 at 11:07 PM, Tom Lane  wrote:

> Darafei Praliaskouski  writes:
> > I have some questions about the circles example though.
>
> >  * What is the reason for isnan check and swap of box ordinates for
> circle? It wasn't in the code previously.
>
> I hadn't paid any attention to this patch previously, but this comment
> excited my curiosity, so I went and looked:
>
> +   bbox->high.x = circle->center.x + circle->radius;
> +   bbox->low.x = circle->center.x - circle->radius;
> +   bbox->high.y = circle->center.y + circle->radius;
> +   bbox->low.y = circle->center.y - circle->radius;
> +
> +   if (isnan(bbox->low.x))
> +   {
> +   double tmp = bbox->low.x;
> +   bbox->low.x = bbox->high.x;
> +   bbox->high.x = tmp;
> +   }
>
> Maybe I'm missing something, but it appears to me that it's impossible for
> bbox->low.x to be NaN unless circle->center.x and/or circle->radius is a
> NaN, in which case bbox->high.x would also have been computed as a NaN,
> making the swap entirely useless.  Likewise for the Y case.  There may be
> something useful to do about NaNs here, but this doesn't seem like it.
>

Yeah, +1.

> How about removing circle from the scope of this patch, so it is smaller
> and cleaner?
>
> Neither of those patches would be particularly large, and since they'd need
> to touch adjacent code in some places, the diffs wouldn't be independent.
> I think splitting them is just make-work.
>

I've extracted polygon opclass into separate patch (attached).  I'll rework
and resubmit circle patch later.
I'm not particularly sure that polygon.sql is a good place for testing
sp-gist opclass for polygons...  But we've already done so for box.sql.

--
Alexander Korotkov
Postgres Professional: http://www.postgrespro.com
The Russian Postgres Company


0001-spgist-compress-method-7.patch
Description: Binary data


0002-spgist-polygon-7.patch
Description: Binary data

-- 
Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org)
To make changes to your subscription:
http://www.postgresql.org/mailpref/pgsql-hackers

Re: [HACKERS] compress method for spgist - 2

[Tom Lane]

Darafei Praliaskouski  writes:
> I have some questions about the circles example though.

>  * What is the reason for isnan check and swap of box ordinates for circle? 
> It wasn't in the code previously.

I hadn't paid any attention to this patch previously, but this comment
excited my curiosity, so I went and looked:

+   bbox->high.x = circle->center.x + circle->radius;
+   bbox->low.x = circle->center.x - circle->radius;
+   bbox->high.y = circle->center.y + circle->radius;
+   bbox->low.y = circle->center.y - circle->radius;
+ 
+   if (isnan(bbox->low.x))
+   {
+   double tmp = bbox->low.x;
+   bbox->low.x = bbox->high.x;
+   bbox->high.x = tmp;
+   }

Maybe I'm missing something, but it appears to me that it's impossible for
bbox->low.x to be NaN unless circle->center.x and/or circle->radius is a
NaN, in which case bbox->high.x would also have been computed as a NaN,
making the swap entirely useless.  Likewise for the Y case.  There may be
something useful to do about NaNs here, but this doesn't seem like it.

> How about removing circle from the scope of this patch, so it is smaller and 
> cleaner?

Neither of those patches would be particularly large, and since they'd need
to touch adjacent code in some places, the diffs wouldn't be independent.
I think splitting them is just make-work.

regards, tom lane


-- 
Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org)
To make changes to your subscription:
http://www.postgresql.org/mailpref/pgsql-hackers

Re: [HACKERS] compress method for spgist - 2

[Alexander Korotkov]

On Wed, Sep 20, 2017 at 10:00 PM, Darafei Praliaskouski 
wrote:

> The following review has been posted through the commitfest application:
> make installcheck-world:  not tested
> Implements feature:   not tested
> Spec compliant:   not tested
> Documentation:tested, passed
>
> Hi,
>
> I like the SP-GiST part of the patch. Looking forward to it, so PostGIS
> can benefit from SP-GiST infrastructure.
>
> I have some questions about the circles example though.
>
>  * What is the reason for isnan check and swap of box ordinates for
> circle? It wasn't in the code previously.
>
 * There are tests for infinities in circles, but checks are for NaNs.
>

This code was migrated from original patch by Nikita.  I can assume he
means that nan should be treated as greatest possible floating point value
(like float4_cmp_internal() does).  However, our current implementation of
geometrical datatypes don't correctly handles all the combinations of infs
as nans.  Most of code was written without taking infs and nans into
account.  Also, I'm not sure if this code fixes all possible issues with
infs and nans in SP-GiST opclass for circles.  This is why I'm going to
remove nans handling from this place.


>  * It seems to me that circle can be implemented without recheck, by
> making direct exact calculations.
>

Right.  Holding circles in the leafs instead of bounding boxes would both
allow exact calculations and take less space.


> How about removing circle from the scope of this patch, so it is smaller
> and cleaner?


Good point.  Polygons are enough for compress function example.  Opclass
for circles could be submitted as separate patch.

--
Alexander Korotkov
Postgres Professional: http://www.postgrespro.com
The Russian Postgres Company

Re: [HACKERS] compress method for spgist - 2

[Darafei Praliaskouski]

The following review has been posted through the commitfest application:
make installcheck-world:  not tested
Implements feature:   not tested
Spec compliant:   not tested
Documentation:tested, passed

Hi,

I like the SP-GiST part of the patch. Looking forward to it, so PostGIS can 
benefit from SP-GiST infrastructure.

I have some questions about the circles example though.

 * What is the reason for isnan check and swap of box ordinates for circle? It 
wasn't in the code previously.
 * There are tests for infinities in circles, but checks are for NaNs.
 * It seems to me that circle can be implemented without recheck, by making 
direct exact calculations.
How about removing circle from the scope of this patch, so it is smaller and 
cleaner?
-- 
Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org)
To make changes to your subscription:
http://www.postgresql.org/mailpref/pgsql-hackers

Re: [HACKERS] compress method for spgist - 2

[Alexander Korotkov]

On Mon, Sep 18, 2017 at 6:21 PM, Alexander Korotkov <
a.korot...@postgrespro.ru> wrote:

> On Tue, Aug 25, 2015 at 4:05 PM, Michael Paquier <
> michael.paqu...@gmail.com> wrote:
>
>> On Thu, Jul 23, 2015 at 6:18 PM, Teodor Sigaev  wrote:
>> >>> Poorly, by hanging boxes that straddled dividing lines off the parent
>> >>> node in a big linear list. The hope would be that the case was
>> >>
>> >> Ok, I see, but that's not really what I was wondering. My question is
>> >> this:
>> >> SP-GiST partitions the space into non-overlapping sections. How can you
>> >> store
>> >> polygons - which can overlap - in an SP-GiST index? And how does the
>> >> compress
>> >> method help with that?
>> >
>> >
>> > I believe if we found a way to index boxes then we will need a compress
>> > method to build index over polygons.
>> >
>> > BTW, we are working on investigation a index structure for box where
>> 2d-box
>> > is treated as 4d-point.
>>
>> There has been no activity on this patch for some time now, and a new
>> patch version has not been submitted, so I am marking it as return
>> with feedback.
>>
>
> There is interest to this patch from PostGIS users.  It would be nice to
> pickup this patch.
> AFAICS, the progress on this patch was suspended because we have no
> example for SP-GiST compress method in core/contrib.
> However, now we have acdf2a8b committed with 2d to 4d indexing of boxes
> using SP-GiST.  So, extending this 2d to 4d approach to polygons would be
> good example of SP-GiST compress method in core.  Would anyone be
> volunteering for writing such patch?
> If nobody, then I could do it
>

Nobody answered yet.  And I decided to nail down this long term issue.
Please, find following attached patches.

0001-spgist-compress-method-6.patch

Patch with SP-GiST compress method rebased on current master.  Index AM
interface was changed since that time.  I've added validation for compress
method: it validates input and output types of compress method.  That
required to call config method before.  That is controversial solution.  In
particular, no collation is provided in config method call.  It would be
weird if collation could affect data types in SP-GiST config method output,
but anyway...

0002-spgist-circle-polygon-6.patch

This patch provides example of SP-GiST compress method usage.  It adds
SP-GiST indexing for circles and polygons using mapping of their bounding
boxes to 4d.  This patch is based on prior work by Nikita Glukhov for
SP-GiST KNN.

--
Alexander Korotkov
Postgres Professional: http://www.postgrespro.com
The Russian Postgres Company


0001-spgist-compress-method-6.patch
Description: Binary data


0002-spgist-circle-polygon-6.patch
Description: Binary data

-- 
Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org)
To make changes to your subscription:
http://www.postgresql.org/mailpref/pgsql-hackers

Re: [HACKERS] compress method for spgist - 2

[Alexander Korotkov]

On Tue, Aug 25, 2015 at 4:05 PM, Michael Paquier 
wrote:

> On Thu, Jul 23, 2015 at 6:18 PM, Teodor Sigaev  wrote:
> >>> Poorly, by hanging boxes that straddled dividing lines off the parent
> >>> node in a big linear list. The hope would be that the case was
> >>
> >> Ok, I see, but that's not really what I was wondering. My question is
> >> this:
> >> SP-GiST partitions the space into non-overlapping sections. How can you
> >> store
> >> polygons - which can overlap - in an SP-GiST index? And how does the
> >> compress
> >> method help with that?
> >
> >
> > I believe if we found a way to index boxes then we will need a compress
> > method to build index over polygons.
> >
> > BTW, we are working on investigation a index structure for box where
> 2d-box
> > is treated as 4d-point.
>
> There has been no activity on this patch for some time now, and a new
> patch version has not been submitted, so I am marking it as return
> with feedback.
>

There is interest to this patch from PostGIS users.  It would be nice to
pickup this patch.
AFAICS, the progress on this patch was suspended because we have no example
for SP-GiST compress method in core/contrib.
However, now we have acdf2a8b committed with 2d to 4d indexing of boxes
using SP-GiST.  So, extending this 2d to 4d approach to polygons would be
good example of SP-GiST compress method in core.  Would anyone be
volunteering for writing such patch?
If nobody, then I could do it

--
Alexander Korotkov
Postgres Professional: http://www.postgrespro.com
The Russian Postgres Company

Re: [HACKERS] compress method for spgist - 2

[Michael Paquier]

On Thu, Jul 23, 2015 at 6:18 PM, Teodor Sigaev teo...@sigaev.ru wrote:
 Poorly, by hanging boxes that straddled dividing lines off the parent
 node in a big linear list. The hope would be that the case was

 Ok, I see, but that's not really what I was wondering. My question is
 this:
 SP-GiST partitions the space into non-overlapping sections. How can you
 store
 polygons - which can overlap - in an SP-GiST index? And how does the
 compress
 method help with that?


 I believe if we found a way to index boxes then we will need a compress
 method to build index over polygons.

 BTW, we are working on investigation a index structure for box where 2d-box
 is treated as 4d-point.

There has been no activity on this patch for some time now, and a new
patch version has not been submitted, so I am marking it as return
with feedback.
-- 
Michael


-- 
Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org)
To make changes to your subscription:
http://www.postgresql.org/mailpref/pgsql-hackers

Re: [HACKERS] compress method for spgist - 2

[Heikki Linnakangas]

On 03/04/2015 06:58 PM, Paul Ramsey wrote:

On Wed, Feb 25, 2015 at 6:13 AM, Heikki Linnakangas
hlinnakan...@vmware.com wrote:

In the original post on this, you mentioned that the PostGIS guys planned to
use this to store polygons, as bounding boxes
(http://www.postgresql.org/message-id/5447b3ff.2080...@sigaev.ru). Any idea
how would that work?


Poorly, by hanging boxes that straddled dividing lines off the parent
node in a big linear list. The hope would be that the case was
sufficiently rare compared to the overall volume of data, to not be an
issue. Oddly enough this big hammer has worked in other
implementations at least passable well
(https://github.com/mapserver/mapserver/blob/branch-7-0/maptree.c#L261)


Ok, I see, but that's not really what I was wondering. My question is 
this: SP-GiST partitions the space into non-overlapping sections. How 
can you store polygons - which can overlap - in an SP-GiST index? And 
how does the compress method help with that?


- Heikki



--
Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org)
To make changes to your subscription:
http://www.postgresql.org/mailpref/pgsql-hackers

Re: [HACKERS] compress method for spgist - 2

[Teodor Sigaev]

Poorly, by hanging boxes that straddled dividing lines off the parent
node in a big linear list. The hope would be that the case was

Ok, I see, but that's not really what I was wondering. My question is this:
SP-GiST partitions the space into non-overlapping sections. How can you store
polygons - which can overlap - in an SP-GiST index? And how does the compress
method help with that?


I believe if we found a way to index boxes then we will need a compress method 
to build index over polygons.


BTW, we are working on investigation a index structure for box where 2d-box is 
treated as 4d-point.



--
Teodor Sigaev   E-mail: teo...@sigaev.ru
   WWW: http://www.sigaev.ru/


--
Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org)
To make changes to your subscription:
http://www.postgresql.org/mailpref/pgsql-hackers

Re: [HACKERS] compress method for spgist - 2

[Paul Ramsey]

On Wed, Feb 25, 2015 at 6:13 AM, Heikki Linnakangas
hlinnakan...@vmware.com wrote:
 In the original post on this, you mentioned that the PostGIS guys planned to
 use this to store polygons, as bounding boxes
 (http://www.postgresql.org/message-id/5447b3ff.2080...@sigaev.ru). Any idea
 how would that work?

Poorly, by hanging boxes that straddled dividing lines off the parent
node in a big linear list. The hope would be that the case was
sufficiently rare compared to the overall volume of data, to not be an
issue. Oddly enough this big hammer has worked in other
implementations at least passable well
(https://github.com/mapserver/mapserver/blob/branch-7-0/maptree.c#L261)

P.


-- 
Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org)
To make changes to your subscription:
http://www.postgresql.org/mailpref/pgsql-hackers

Re: [HACKERS] compress method for spgist - 2

[Heikki Linnakangas]

On 02/13/2015 06:17 PM, Teodor Sigaev wrote:

Now that the input data type and leaf data type can be different, which one is
attType? It's the leaf data type, as the patch stands. I renamed that to
attLeafType, and went fixing all the references to it. In most places it's just
a matter of search  replace, but what about the reconstructed datum? In


Done. Now there is separate attType and attLeafType which describe input/output
and leaf types.


Thanks.

Did you try finding a use case for this patch in one of the built-in or 
contrib datatypes? That would allow writing a regression test for this.


In the original post on this, you mentioned that the PostGIS guys 
planned to use this to store polygons, as bounding boxes 
(http://www.postgresql.org/message-id/5447b3ff.2080...@sigaev.ru). Any 
idea how would that work?


- Heikki


--
Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org)
To make changes to your subscription:
http://www.postgresql.org/mailpref/pgsql-hackers

Re: [HACKERS] compress method for spgist - 2

[Teodor Sigaev]

Now that the input data type and leaf data type can be different, which one is
attType? It's the leaf data type, as the patch stands. I renamed that to
attLeafType, and went fixing all the references to it. In most places it's just
a matter of search  replace, but what about the reconstructed datum? In


Done. Now there is separate attType and attLeafType which describe input/output 
and leaf types.



--
Teodor Sigaev   E-mail: teo...@sigaev.ru
   WWW: http://www.sigaev.ru/


spgist_compress_method-5.patch.gz
Description: GNU Zip compressed data

-- 
Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org)
To make changes to your subscription:
http://www.postgresql.org/mailpref/pgsql-hackers

Re: [HACKERS] compress method for spgist - 2

[Heikki Linnakangas]

On 01/15/2015 09:28 AM, Michael Paquier wrote:

Marking this patch as returned with feedback because it is waiting for
input from the author for now a couple of weeks. Heikki, the
refactoring patch has some value, are you planning to push it?


I think you're mixing up with the other thread, btree_gin and ranges. 
I pushed the refactoring patch I posted to that thread 
(http://www.postgresql.org/message-id/54983cf2.80...@vmware.com) 
already. I haven't proposed any refactoring related to spgist.


- Heikki


--
Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org)
To make changes to your subscription:
http://www.postgresql.org/mailpref/pgsql-hackers

Re: [HACKERS] compress method for spgist - 2

[Michael Paquier]

Marking this patch as returned with feedback because it is waiting for
input from the author for now a couple of weeks. Heikki, the
refactoring patch has some value, are you planning to push it?
-- 
Michael


-- 
Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org)
To make changes to your subscription:
http://www.postgresql.org/mailpref/pgsql-hackers

Re: [HACKERS] compress method for spgist - 2

[Heikki Linnakangas]

On 12/23/2014 03:02 PM, Teodor Sigaev wrote:

I think we'll need a separate SpGistTypeDesc for the input type. Or perhaps a
separate SpGistTypeDesc for the reconstructed value and an optional decompress
method to turn the reconstructedValue back into an actual reconstructed input
datum. Or something like that.

I suppose that compress and reconstruct are mutual exclusive options.


I would rather not assume that. You might well want to store something 
in the leaf nodes that's different from the original Datum, but 
nevertheless contains enough information to reconstruct the original Datum.


- Heikki



--
Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org)
To make changes to your subscription:
http://www.postgresql.org/mailpref/pgsql-hackers

Re: [HACKERS] compress method for spgist - 2

[Heikki Linnakangas]

On 12/16/2014 07:48 PM, Teodor Sigaev wrote:

/*
 * This struct is what we actually keep in index-rd_amcache.  It includes
 * static configuration information as well as the lastUsedPages cache.
 */
typedef struct SpGistCache
{
spgConfigOut config;/* filled in by opclass config method */

SpGistTypeDesc attType; /* type of input data and leaf values */
SpGistTypeDesc attPrefixType;   /* type of inner-tuple prefix 
values */
SpGistTypeDesc attLabelType;/* type of node label values */

SpGistLUPCache lastUsedPages;   /* local storage of last-used 
info */
} SpGistCache;


Now that the input data type and leaf data type can be different, which 
one is attType? It's the leaf data type, as the patch stands. I 
renamed that to attLeafType, and went fixing all the references to it. 
In most places it's just a matter of search  replace, but what about 
the reconstructed datum? In freeScanStackEntry, we assume that 
att[Leaf]Type is the datatype for reconstructedValue, but I believe 
assume elsewhere that reconstructedValue is of the same data type as the 
input. At least if the opclass supports index-only scans.


I think we'll need a separate SpGistTypeDesc for the input type. Or 
perhaps a separate SpGistTypeDesc for the reconstructed value and an 
optional decompress method to turn the reconstructedValue back into an 
actual reconstructed input datum. Or something like that.


Attached is a patch with the kibitzing I did so far.

- Heikki

diff --git a/doc/src/sgml/spgist.sgml b/doc/src/sgml/spgist.sgml
index 56827e5..de158c3 100644
--- a/doc/src/sgml/spgist.sgml
+++ b/doc/src/sgml/spgist.sgml
@@ -201,20 +201,21 @@
 
  para
   There are five user-defined methods that an index operator class for
-  acronymSP-GiST/acronym must provide.  All five follow the convention
-  of accepting two typeinternal/ arguments, the first of which is a
-  pointer to a C struct containing input values for the support method,
-  while the second argument is a pointer to a C struct where output values
-  must be placed.  Four of the methods just return typevoid/, since
-  all their results appear in the output struct; but
+  acronymSP-GiST/acronym must provide and one optional. All five mandatory
+  methos follow the convention of accepting two typeinternal/ arguments,
+  the first of which is a pointer to a C struct containing input values for 
+  the support method, while the second argument is a pointer to a C struct 
+  where output values must be placed.  Four of the methods just return 
+  typevoid/, since all their results appear in the output struct; but
   functionleaf_consistent/ additionally returns a typeboolean/ result.
   The methods must not modify any fields of their input structs.  In all
   cases, the output struct is initialized to zeroes before calling the
-  user-defined method.
+  user-defined method. Optional method functioncompress/ accepts
+  datum to be indexed and returns values which actually will be indexed.  
  /para
 
  para
-  The five user-defined methods are:
+  The five mandatory user-defined methods are:
  /para
 
  variablelist
@@ -244,6 +245,7 @@ typedef struct spgConfigOut
 {
 Oid prefixType; /* Data type of inner-tuple prefixes */
 Oid labelType;  /* Data type of inner-tuple node labels */
+Oid leafType;   /* Data type of leaf */
 boolcanReturnData;  /* Opclass can reconstruct original data */
 boollongValuesOK;   /* Opclass can cope with values gt; 1 page */
 } spgConfigOut;
@@ -264,7 +266,15 @@ typedef struct spgConfigOut
   structfieldlongValuesOK/ should be set true only when the
   structfieldattType/ is of variable length and the operator
   class is capable of segmenting long values by repeated suffixing
-  (see xref linkend=spgist-limits).
+  (see xref linkend=spgist-limits). structfieldleafType/
+  usually has the same value as structfieldattType/ but if
+  it's different then optional method  functioncompress/
+  should be provided. Method  functioncompress/ is responsible
+  for transformation from structfieldattType/ to 
+  structfieldleafType/. In this case all other function should
+  accept structfieldleafType/ values. Note: both consistent
+  functions will get structfieldscankeys/ unchanged, without
+  functioncompress/ transformation.
  /para
  /listitem
 /varlistentry
@@ -690,6 +700,24 @@ typedef struct spgLeafConsistentOut
 /varlistentry
/variablelist
 
+ para
+  The optional user-defined method is:
+ /para
+
+ variablelist
+varlistentry
+ termfunctionDatum compress(Datum in)//term
+ listitem
+  para
+   Converts the data item into a format suitable for physical storage in 
+   an index page. It accepts structnamespgConfigIn/.structfieldattType/
+   value and return structnamespgConfigOut/.structfieldleafType/
+   value. 

Re: [HACKERS] compress method for spgist - 2

[Teodor Sigaev]

Now that the input data type and leaf data type can be different, which one is
attType? It's the leaf data type, as the patch stands. I renamed that to
attLeafType, and went fixing all the references to it. In most places it's just
a matter of search  replace, but what about the reconstructed datum? In
freeScanStackEntry, we assume that att[Leaf]Type is the datatype for
reconstructedValue, but I believe assume elsewhere that reconstructedValue is of
the same data type as the input. At least if the opclass supports index-only 
scans.



Agree with rename. I doubt that there is a real-world example of datatype which 
can be a) effectivly compressed and b) restored to original form. If so, why 
don't store it in compressed state in database? In GiST all compress methods 
uses one-way compress. In PostGIS example, polygons are compressed into 
bounding box, and, obviously, they cannot be restored.




I think we'll need a separate SpGistTypeDesc for the input type. Or perhaps a
separate SpGistTypeDesc for the reconstructed value and an optional decompress
method to turn the reconstructedValue back into an actual reconstructed input
datum. Or something like that.


I suppose that compress and reconstruct are mutual exclusive options.

--
Teodor Sigaev   E-mail: teo...@sigaev.ru
   WWW: http://www.sigaev.ru/


--
Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org)
To make changes to your subscription:
http://www.postgresql.org/mailpref/pgsql-hackers

Re: [HACKERS] compress method for spgist - 2

[Teodor Sigaev]

 For some datatypes, the compress method might be useful even if the leaf
 type is the same as the column type. For example, you could allow
 indexing text datums larger than the page size, with a compress function
 that just truncates the input.

Agree, and patch allows to use compress method in this case, see begining of 
spgdoinsert()



 Could you find some use for this in one of the built-in or contrib
 types? Just to have something that exercises it as part of the
 regression suite. How about creating an opclass for the built-in polygon
 type that stores the bounding box, like the PostGIS guys are doing?

Will try, but I don't have nice idea. Polygon opclass will have awful 
performance until PostGIS guys show the tree structure.


 The documentation needs to be updated.
Added.

--
Teodor Sigaev   E-mail: teo...@sigaev.ru
   WWW: http://www.sigaev.ru/


spgist_compress_method-3.patch.gz
Description: GNU Zip compressed data

-- 
Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org)
To make changes to your subscription:
http://www.postgresql.org/mailpref/pgsql-hackers

Re: [HACKERS] compress method for spgist - 2

[Heikki Linnakangas]

On 12/01/2014 02:44 PM, Teodor Sigaev wrote:


Initial message:
http://www.postgresql.org/message-id/5447b3ff.2080...@sigaev.ru

Second version fixes a forgotten changes in pg_am.



+   /* Get the information we need about each relevant datatypes */
+
+   if (OidIsValid(cache-config.leafType)  
cache-config.leafType != atttype)
+   {
+   if (!OidIsValid(index_getprocid(index, 1, 
SPGIST_COMPRESS_PROC)))
+   ereport(ERROR,
+   
(errcode(ERRCODE_INVALID_PARAMETER_VALUE),
+errmsg(compress method is not 
defined although input and leaf types are differ)));
+
+   fillTypeDesc(cache-attType, cache-config.leafType);
+   }
+   else
+   {
+   fillTypeDesc(cache-attType, atttype);
+   }
+


For some datatypes, the compress method might be useful even if the leaf 
type is the same as the column type. For example, you could allow 
indexing text datums larger than the page size, with a compress function 
that just truncates the input.


Could you find some use for this in one of the built-in or contrib 
types? Just to have something that exercises it as part of the 
regression suite. How about creating an opclass for the built-in polygon 
type that stores the bounding box, like the PostGIS guys are doing?


The documentation needs to be updated.

- Heikki



--
Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org)
To make changes to your subscription:
http://www.postgresql.org/mailpref/pgsql-hackers