Skip site navigation (1) Skip section navigation (2)

Re: SP-GiST for ranges based on 2d-mapping and quad-tree

From: Jeff Davis <pgsql(at)j-davis(dot)com>
To: Alexander Korotkov <aekorotkov(at)gmail(dot)com>
Cc: pgsql-hackers <pgsql-hackers(at)postgresql(dot)org>
Subject: Re: SP-GiST for ranges based on 2d-mapping and quad-tree
Date: 2012-07-03 06:47:58
Message-ID: 1341298078.6857.14.camel@jdavis (view raw or flat)
Thread:
Lists: pgsql-hackers
On Thu, 2012-06-14 at 02:56 +0400, Alexander Korotkov wrote:
> Hackers,
> 
> 
> attached patch implements quad-tree on ranges. Some performance
> results in comparison with current GiST indexing.
> Index creation is slightly slower. Probably, it need some
> investigation. Search queries on SP-GiST use much more pages. However
> this comparison can be not really correct, because SP-GiST can pin
> same buffer several times during one scan. In CPU search queries on
> SP-GiST seems to be slightly faster. Dramatical difference in "column
> <@ const" query is thanks to 2d-mapping.
> 

More comments:

* Minor rebase is required (simple int2 -> int16).

* Perhaps I'm mistaken, but the following code in getQuadrant() looks
wrong to me, shouldn't the 1 and 2 be reversed?

        if (range_cmp_bounds(typcache, &upper, &centroidUpper) >= 0)
            return 1;
        else
            return 2;

* in the "choose" method, why does in->allTheSame unconditionally match?
Why not split? Similarly, why does inner_consistent always match when
the nodes are allTheSame?

* It's a little confusing having empty prefixes mean that empty range go
to node0, and non-empty ranges meaning that empty ranges go to node4
(quadrant 5). Why can't there just always be 5 nodes, and iff all the
ranges are empty, then the prefix is NULL?

And for that matter, let's let the quadrant equal the node number, and
have the empty ranges in node0. I don't see much point in always
subtracting 1 from the quadrant number.

Regards,
	Jeff Davis


In response to

Responses

pgsql-hackers by date

Next:From: Jeff DavisDate: 2012-07-03 06:51:08
Subject: Re: SP-GiST for ranges based on 2d-mapping and quad-tree
Previous:From: Tatsuo IshiiDate: 2012-07-03 06:17:47
Subject: Re: Patch: add conversion from pg_wchar to multibyte

Privacy Policy | About PostgreSQL
Copyright © 1996-2014 The PostgreSQL Global Development Group