Thread: KNN-GiST with recheck

On 01/13/2014 07:17 PM, Alexander Korotkov wrote:
> Here goes a desription of this patch same as in original thread.
>
> KNN-GiST provides ability to get ordered results from index, but this order
> is based only on index information. For instance, GiST index contains
> bounding rectangles for polygons, and we can't get exact distance to
> polygon from index (similar situation is in PostGIS). In attached patch,
> GiST distance method can set recheck flag (similar to consistent method).
> This flag means that distance method returned lower bound of distance and
> we should recheck it from heap.
>
> See an example.
>
> create table test as (select id, polygon(3+(random()*10)::int,
> circle(point(random(), random()), 0.0003 + random()*0.001)) as p from
> generate_series(1,1000000) id);
> create index test_idx on test using gist (p);
>
> We can get results ordered by distance from polygon to point.
>
> postgres=# select id, p <-> point(0.5,0.5) from test order by p <->
> point(0.5,0.5) limit 10;
>     id   |       ?column?
> --------+----------------------
>   755611 | 0.000405855808916853
>   807562 | 0.000464123777564343
>   437778 | 0.000738524708741959
>   947860 |  0.00076250998760724
>   389843 | 0.000886362723569568
>    17586 | 0.000981960100555216
>   411329 |  0.00145338112316853
>   894191 |  0.00149399559703506
>   391907 |   0.0016647896049741
>   235381 |  0.00167554614889509
> (10 rows)
>
> It's fast using just index scan.
>
>                                                              QUERY PLAN
>
>
----------------------------------------------------------------------------------------------------------------------------------
>   Limit  (cost=0.29..1.86 rows=10 width=36) (actual time=0.180..0.230
> rows=10 loops=1)
>     ->  Index Scan using test_idx on test  (cost=0.29..157672.29
> rows=1000000 width=36) (actual time=0.179..0.228 rows=10 loops=1)
>           Order By: (p <-> '(0.5,0.5)'::point)
>   Total runtime: 0.305 ms
> (4 rows)

Nice! Some thoughts:

1. This patch introduces a new "polygon <-> point" operator. That seems 
useful on its own, with or without this patch.

2. I wonder how useful it really is to allow mixing exact and non-exact 
return values from the distance function. The distance function included 
in the patch always returns recheck=true. I have a feeling that all 
other distance function will also always return either true or false.

3. A binary heap would be a better data structure to buffer the 
rechecked values. A Red-Black tree allows random insertions and 
deletions, but in this case you need to insert arbitrary values but only 
remove the minimum item. That's exactly what a binary heap excels at. We 
have a nice binary heap implementation in the backend that you can use, 
see src/backend/lib/binaryheap.c.

4. (as you mentioned in the other thread: ) It's a modularity violation 
that you peek into the heap tuple from gist. I think the proper way to 
do this would be to extend the IndexScan executor node to perform the 
re-shuffling of tuples that come from the index in wrong order, or 
perhaps add a new node type for it.

Of course that's exactly what your partial sort patch does :-). I 
haven't looked at that in detail, but I don't think the approach the 
partial sort patch takes will work here as is. In the KNN-GiST case, the 
index is returning tuples roughly in the right order, but a tuple that 
it returns might in reality belong somewhere later in the ordering. In 
the partial sort patch, the "input stream" of tuples is divided into 
non-overlapping groups, so that the tuples within the group are not 
sorted, but the groups are. I think the partial sort case is a special 
case of the KNN-GiST case, if you consider the lower bound of each tuple 
to be the leading keys that you don't need to sort.

BTW, this capability might also be highly useful for the min/max indexes 
as well. A min/max index cannot return an exact ordering of tuples, but 
it can also give a lower bound for a group of tuples.

- Heikki

On 01/28/2014 04:12 PM, Alexander Korotkov wrote:
> On Tue, Jan 28, 2014 at 5:54 PM, Heikki Linnakangas <hlinnakangas@vmware.com
>> wrote:
>
>> 4. (as you mentioned in the other thread: ) It's a modularity violation
>> that you peek into the heap tuple from gist. I think the proper way to do
>> this would be to extend the IndexScan executor node to perform the
>> re-shuffling of tuples that come from the index in wrong order, or perhaps
>> add a new node type for it.
>>
>> Of course that's exactly what your partial sort patch does :-). I haven't
>> looked at that in detail, but I don't think the approach the partial sort
>> patch takes will work here as is. In the KNN-GiST case, the index is
>> returning tuples roughly in the right order, but a tuple that it returns
>> might in reality belong somewhere later in the ordering. In the partial
>> sort patch, the "input stream" of tuples is divided into non-overlapping
>> groups, so that the tuples within the group are not sorted, but the groups
>> are. I think the partial sort case is a special case of the KNN-GiST case,
>> if you consider the lower bound of each tuple to be the leading keys that
>> you don't need to sort.
>
> Yes. But, for instance btree accesses heap for unique checking. Is really
> it so crimilal? :-)

Well, it is generally considered an ugly hack in b-tree too. I'm not 
100% opposed to doing such a hack in GiST, but would very much prefer 
not to.

> This is not only question of a new node or extending existing node. We need
> to teach planner/executor access method can return value of some expression
> which is lower bound of another expression. AFICS now access method can
> return only original indexed datums and TIDs. So, I afraid that enormous
> infrastructure changes are required. And I can hardly imagine what they
> should look like.

Yeah, I'm not sure either. Maybe a new field in IndexScanDesc, along 
with xs_itup. Or as an attribute of xs_itup itself.

- Heikki

> > 1. This patch introduces a new "polygon <-> point" operator. That seems
> > useful on its own, with or without this patch.
>
> Yeah, but exact-knn cant come with no one implementation. But it would
> better come in a separate patch.

I tried to split them.  Separated patches are attached.  I changed
the order of the arguments as point <-> polygon, because point was
the first one on all the others.  Its commutator was required for
the index, so I added it on the second patch.  I also added tests
for the operator.  I think it is ready for committer as a separate
patch.  We can add it to the open CommitFest.

I have made some cosmetic changes on the patches.  I hope they are
useful.

I added support to point <-> circle operator with the same GiST
distance function you added for polygon.  I can change it, if it is not
the right way.

> > 2. I wonder how useful it really is to allow mixing exact and non-exact
> > return values from the distance function. The distance function included in
> > the patch always returns recheck=true. I have a feeling that all other
> > distance function will also always return either true or false.
>
> For geometrical datatypes recheck variations in consistent methods are also
> very rare (I can't remember any). But imagine opclass for arrays where keys
> have different representation depending on array length. For such opclass
> and knn on similarity recheck flag could be useful.

I also wonder how useful it is.  Your example is convincing, but maybe
setting it index-wide will make the decisions on the framework easier.
For example, how hard would it be to decide if further sorting is
required or not on the planner?

> > 4. (as you mentioned in the other thread: ) It's a modularity violation
> > that you peek into the heap tuple from gist. I think the proper way to do
> > this would be to extend the IndexScan executor node to perform the
> > re-shuffling of tuples that come from the index in wrong order, or perhaps
> > add a new node type for it.
> >
> > Of course that's exactly what your partial sort patch does :-). I haven't
> > looked at that in detail, but I don't think the approach the partial sort
> > patch takes will work here as is. In the KNN-GiST case, the index is
> > returning tuples roughly in the right order, but a tuple that it returns
> > might in reality belong somewhere later in the ordering. In the partial
> > sort patch, the "input stream" of tuples is divided into non-overlapping
> > groups, so that the tuples within the group are not sorted, but the groups
> > are. I think the partial sort case is a special case of the KNN-GiST case,
> > if you consider the lower bound of each tuple to be the leading keys that
> > you don't need to sort.
>
> Yes. But, for instance btree accesses heap for unique checking. Is really
> it so crimilal? :-)
> This is not only question of a new node or extending existing node. We need
> to teach planner/executor access method can return value of some expression
> which is lower bound of another expression. AFICS now access method can
> return only original indexed datums and TIDs. So, I afraid that enormous
> infrastructure changes are required. And I can hardly imagine what they
> should look like.

Unfortunately, I am not experienced enough to judge your implementation.
As far as I understand the problem is partially sorting rows on
the index scan node.  It can lead the planner to choose non-optimal
plans, because of not taking into account the cost of sorting.

I added the point to polygon distance operator patch to the open
CommitFest as ready for committer and added myself as reviewer to
both of the patches.

> I think that for most use cases just some operators require further sorting
> and some of them not. But it could appear one day that some index gives
> part of its knn answers exact and part of them inexact. Same happen to
> recheck of regular operators. Initially recheck flag was defined in
> opclass. But later recheck became runtime flag.

I cannot think of an use case, but it makes sense to add the flag to
the distance function just like the consistent function if we will go
with this implementation.

> Cost estimation of GiST is a big problem anyway. It doesn't care (and
> can't) about amount of recheck for regular operators. In this patch, same
> would be for knn recheck. The problem is that touching heap from access
> method breaks incapsulation. One idea about this is to do sorting in
> another nodes. However, I wonder if it would be an overengineering and
> overhead. In attached patch I propose a different approach: put code
> touching heap into separate index_get_heap_values function. Also new
> version of patch includes regression tests and some cleanup.

While looking it at I found a bug.  It returns the second column
in wrong order when both of the distance functions return recheck = true.
Test script attached to run on the regression database.  I tried to
fix but could not.  searchTreeItemDistanceRecheck function is not
very easy to follow.  I think it deserves more comments.

> > While looking it at I found a bug.  It returns the second column
> > in wrong order when both of the distance functions return recheck = true.
> > Test script attached to run on the regression database.  I tried to
> > fix but could not.  searchTreeItemDistanceRecheck function is not
> > very easy to follow.  I think it deserves more comments.
>
> Fixed, thanks. It was logical error in comparison function implementation.

I managed to break it again by ordering rows only by the second column
of the index.  Test script attached.

> I managed to break it again by ordering rows only by the second column
> of the index.  Test script attached.

I was confused.  It is undefined behavior.  Sorry for the noise.

<div dir="ltr"><div class="gmail_extra"><div class="gmail_quote">On Wed, Sep 17, 2014 at 12:30 PM, Emre Hasegeli <span
dir="ltr"><<ahref="mailto:emre@hasegeli.com" target="_blank">emre@hasegeli.com</a>></span> wrote:<br
/><blockquoteclass="gmail_quote" style="margin:0px 0px 0px
0.8ex;border-left-width:1px;border-left-color:rgb(204,204,204);border-left-style:solid;padding-left:1ex"><span
class="">>I managed to break it again by ordering rows only by the second column<br /> > of the index.  Test
scriptattached.<br /><br /></span>I was confused.  It is undefined behavior.  Sorry for the noise.<br
/></blockquote></div><br/></div><div class="gmail_extra">No problem. Thanks a lot for testing.</div><div
class="gmail_extra"><br/></div>------<br />With best regards,<br />Alexander Korotkov.</div> 

> Fixed, thanks.

Here are my questions and comments about the code.

doc/src/sgml/gist.sgml:812:
>        be rechecked from heap tuple before tuple is returned.  If
>        <literal>recheck</> flag isn't set then it's true by default for
>        compatibility reasons.  The <literal>recheck</> flag can be used only

Recheck flag is set to false on gistget.c so I think it should say
"false by default".  On the other hand, it is true by default on
the consistent function.  It is written as "the safest assumption"
on the code comments.  I don't know why the safest is chosen over
the backwards compatible for the consistent function.

src/backend/access/gist/gistget.c:505:
>             /* Recheck distance from heap tuple if needed */
>             if (GISTSearchItemIsHeap(*item) &&
>                 searchTreeItemNeedDistanceRecheck(scan, so->curTreeItem))
>             {
>                 searchTreeItemDistanceRecheck(scan, so->curTreeItem, item);
>                 continue;
>             }

Why so->curTreeItem is passed to these functions?  They can use
scan->opaque->curTreeItem.

src/backend/access/gist/gistscan.c:49:
>         /*
>          * When all distance values are the same, items without recheck
>          * can be immediately returned.  So they are placed first.
>          */
>         if (recheckCmp == 0 && distance_a.recheck != distance_b.recheck)
>             recheckCmp = distance_a.recheck ? 1 : -1;

I don't understand why items without recheck can be immediately
returned.  Do you think it will work correctly when there is
an operator class which will return recheck true and false for
the items under the same page?

src/backend/access/index/indexam.c:258:
>     /* Prepare data structures for getting original indexed values from heap */
>     scan->indexInfo = BuildIndexInfo(scan->indexRelation);
>     scan->estate = CreateExecutorState();
>     scan->slot = MakeSingleTupleTableSlot(RelationGetDescr(heapRelation));

With the changes in indexam.c, heap access become legal for all index
access methods.  I think it is better than the previous version but
I am leaving the judgement to someone experienced.  I will try to
summarize the pros and cons of sorting the rows in the GiST access
method, as far as I understand.

Pros:

* It does not require another queue.  It should be effective to sort the rows inside the queue the GiST access method
alreadyhas.
 
* It does not complicate index access method infrastructure.

Cons:

* It could be done without additional heap access.
* Other access methods could make use of the sorting infrastructure one day.
* It could be more transparent to the users.  Sorting information could be shown on the explain output.
* A more suitable data structure like binary heap could be used for the queue to sort the rows.

On Sun, Sep 14, 2014 at 11:34:26PM +0400, Alexander Korotkov wrote:
>     > Cost estimation of GiST is a big problem anyway. It doesn't care (and
>     > can't) about amount of recheck for regular operators. In this patch, same
>     > would be for knn recheck. The problem is that touching heap from access

This is very important work.  While our existing KNN-GiST index code
works fine for scalar values and point-to-point distance ordering, it
doesn't work well for 2-dimensional objects because they are only
indexed by their bounding boxes (a rectangle around the object).  The
indexed bounding box can't produce accurate distances to other objects. 

As an example, see this PostGIS blog post showing how to use LIMIT in a
CTE to filter results and then compute the closest object (search for
"LIMIT 50"):
http://shisaa.jp/postset/postgis-postgresqls-spatial-partner-part-3.html

This patch fixes our code for distances from a point to indexed 2-D
objects.

Does this also fix the identical PostGIS problem or is there something
PostGIS needs to do?

--  Bruce Momjian  <bruce@momjian.us>        http://momjian.us EnterpriseDB
http://enterprisedb.com
 + Everyone has their own god. +

On Fri, Sep 26, 2014 at 10:49:42AM +0400, Alexander Korotkov wrote:
>     Does this also fix the identical PostGIS problem or is there something
>     PostGIS needs to do?
> 
> 
> This patch provides general infrastructure for recheck in KNN-GiST. PostGIS
> need corresponding change in its GiST opclass. Since PostGIS already define <->
> and <#> operators as distance to bounding box border and bounding box center,
> it can't change their behaviour.
> it has to support new operator "exact distance" in opclass. 

Ah, OK, so they just need something that can be used for the recheck.  I
think they currently use ST_Distance() for that.  Does it have to be an
operator?  If they defined an operator for ST_Distance(), would
ST_Distance() work too for KNN-GiST?

In summary, you still create a normal GiST index on the column:
http://shisaa.jp/postset/postgis-postgresqls-spatial-partner-part-3.html
CREATE INDEX planet_osm_line_ref_index ON planet_osm_line(ref);

which indexes by the bounding box.  The new code will allow ordered
index hits to be filtered by something like ST_Distance(), rather than
having to a LIMIT 50 in a CTE, then call ST_Distance(), like this:
EXPLAIN ANALYZE WITH distance AS (    SELECT way AS road, ref AS route        FROM planet_osm_line        WHERE highway
='secondary'        ORDER BY ST_GeomFromText('POLYGON((14239931.42 3054117.72,14239990.49 3054224.25,14240230.15
3054091.38,14240171.083053984.84,14239931.42 3054117.72))', 900913) <#> way        LIMIT 50        )SELECT
ST_Distance(ST_GeomFromText('POLYGON((14239931.423054117.72,14239990.49 3054224.25,14240230.15 3054091.38,14240171.08
3053984.84,14239931.423054117.72))', 900913), road) AS true_distance, route    FROM distance    ORDER BY true_distance
 LIMIT 1;
 

Notice the CTE uses <#> (bounding box center), and then the outer query
uses ST_Distance and LIMIT 1 to find the closest item.

Excellent!

--  Bruce Momjian  <bruce@momjian.us>        http://momjian.us EnterpriseDB
http://enterprisedb.com
 + Everyone has their own god. +

> Thanks. The main question now is design of this patch. Currently, it does
> all the work inside access method. We already have some discussion of pro
> and cons of this method. I would like to clarify alternatives now. I can
> see following way:
> 
>    1. Implement new executor node which performs sorting by priority queue.
>    Let's call it "Priority queue". I think it should be separate node from
>    "Sort" node. Despite "Priority queue" and "Sort" are essentially similar
>    from user view, they would be completely different in implementation.
>    2. Implement some interface to transfer distance values from access
>    method to "Priority queue" node.

If we assume that all of them need recheck, maybe it can be done
without passing distance values.

>    3. Somehow tell the planner that it could use "Priority queue" in
>    corresponding cases. I see two ways of doing this:
>       - Add flag to operator in opclass indicating that index can only
>       order by lower bound of "col op value", not by "col op value" itself.
>       - Define new relation between operators. Value of one operator could
>       be lower bound for value of another operator. So, planner can
> put "Priority
>       queue" node when lower bound ordering is possible from index. Also "ALTER
>       OPERATOR" command would be reasonable, so extensions could upgrade.

I think, it would be better to make it a property of the operator
class.  We can add a column to pg_amop or define another value for
amoppurpose on pg_amop.  Syntax can be something like this:

CREATE OPERATOR CLASS circle_ops DEFAULT  FOR TYPE circle USING gist AS  OPERATOR 15  <->(circle, point) FOR ORDER BY
pg_catalog.float_opsLOWER BOUND;
 

While looking at it, I realize that current version of the patch does
not use the sort operator family defined with the operator class.  It
assumes that the distance function will return values compatible with
the operator.  Operator class definition makes me think that there is
not such an assumption.

> Besides overhead, this way makes significant infrastructural changes. So,
> it may be over-engineering. However, it's probably more clean and beautiful
> solution.
> I would like to get some feedback from people familiar with KNN-GiST like
> Heikki or Tom. What do you think about this? Any other ideas?

I would be happy to test and review the changes.  I think it is nice
to solve the problem in a generalized way improving the access method
infrastructure.  Definitely, we should have a consensus on the design
before working on the infrastructure changes.

On Mon, Jan 13, 2014 at 9:17 AM, Alexander Korotkov
<aekorotkov@gmail.com> wrote:
> This patch was split from thread:
> http://www.postgresql.org/message-id/CAPpHfdscOX5an71nHd8WSUH6GNOCf=V7wgDaTXdDd9=goN-gfA@mail.gmail.com
>
> I've split it to separate thead, because it's related to partial sort only
> conceptually not technically. Also I renamed it to "knn-gist-recheck" from
> "partial-knn" as more appropriate name. In the attached version docs are
> updated. Possible weak point of this patch design is that it fetches heap
> tuple from GiST scan. However, I didn't receive any notes about its design,
> so, I'm going to put it to commitfest.


The partial sort thing is not in the current 2014-10 commitfest
(although this patch is). Is that intentional?

-- 
Peter Geoghegan

On 01/28/2014 04:12 PM, Alexander Korotkov wrote:
>> >3. A binary heap would be a better data structure to buffer the rechecked
>> >values. A Red-Black tree allows random insertions and deletions, but in
>> >this case you need to insert arbitrary values but only remove the minimum
>> >item. That's exactly what a binary heap excels at. We have a nice binary
>> >heap implementation in the backend that you can use, see
>> >src/backend/lib/binaryheap.c.
>> >
> Hmm. For me binary heap would be a better data structure for KNN-GiST at
> all :-)

I decided to give this a shot, replacing the red-black tree in GiST with
the binary heap we have in lib/binaryheap.c. It made the GiST code
somewhat simpler, as the binaryheap interface is simpler than the
red-black tree one. Unfortunately, performance was somewhat worse. That
was quite surprising, as insertions and deletions are both O(log N) in
both data structures, but the red-black tree implementation is more
complicated.

I implemented another data structure called a Pairing Heap. It's also a
fairly simple data structure, but insertions are O(1) instead of O(log
N). It also performs fairly well in practice.

With that, I got a small but measurable improvement. To test, I created
a table like this:

create table gisttest (id integer, p point);
insert into gisttest select id, point(random(), random()) from
generate_series(1, 1000000) id;
create index i_gisttest on gisttest using gist (p);

And I ran this query with pgbench:

select id from gisttest order by p <-> '(0,0)' limit 1000;

With unpatched master, I got about 650 TPS, and with the patch 720 TPS.
That's a nice little improvement, but perhaps more importantly, the
pairing heap implementation consumes less memory. To measure that, I put
a MemoryContextStats(so->queueCtx) call into gistendscan. With the above
query, but without the "limit" clause, on master I got:

GiST scan context: 2109752 total in 10 blocks; 2088456 free (24998
chunks); 21296 used

And with the patch:

GiST scan context: 1061160 total in 9 blocks; 1040088 free (12502
chunks); 21072 used

That's 2MB vs 1MB. While that's not much in absolute terms, it'd be nice
to reduce that memory consumption, as there is no hard upper bound on
how much might be needed. If the GiST tree is really disorganized for
some reason, a query might need a lot more.


So all in all, I quite like this patch, even though it doesn't do
anything too phenomenal. It adds a some code, in the form of the new
pairing heap implementation, but it makes the GiST code a little bit
simpler. And it gives a small performance gain, and reduces memory usage
a bit.

- Heikki

<div dir="ltr"><div class="gmail_extra"><br /><div class="gmail_quote">On Wed, Dec 10, 2014 at 1:50 PM, Heikki
Linnakangas<span dir="ltr"><<a href="mailto:hlinnakangas@vmware.com"
target="_blank">hlinnakangas@vmware.com</a>></span>wrote:<br /><blockquote class="gmail_quote" style="margin:0 0 0
.8ex;border-left:1px#ccc solid;padding-left:1ex">On 01/28/2014 04:12 PM, Alexander Korotkov wrote:<br /><blockquote
class="gmail_quote"style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><blockquote
class="gmail_quote"style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"> >3. A binary heap would be
abetter data structure to buffer the rechecked<br /> >values. A Red-Black tree allows random insertions and
deletions,but in<br /> >this case you need to insert arbitrary values but only remove the minimum<br /> >item.
That'sexactly what a binary heap excels at. We have a nice binary<br /> >heap implementation in the backend that you
canuse, see<br /> >src/backend/lib/binaryheap.c.<br /> ><br /></blockquote> Hmm. For me binary heap would be a
betterdata structure for KNN-GiST at<br /> all :-)<br /></blockquote><br /> I decided to give this a shot, replacing
thered-black tree in GiST with the binary heap we have in lib/binaryheap.c. It made the GiST code somewhat simpler, as
thebinaryheap interface is simpler than the red-black tree one. Unfortunately, performance was somewhat worse. That was
quitesurprising, as insertions and deletions are both O(log N) in both data structures, but the red-black tree
implementationis more complicated.<br /><br /> I implemented another data structure called a Pairing Heap. It's also a
fairlysimple data structure, but insertions are O(1) instead of O(log N). It also performs fairly well in practice.<br
/><br/> With that, I got a small but measurable improvement. To test, I created a table like this:<br /><br /> create
tablegisttest (id integer, p point);<br /> insert into gisttest select id, point(random(), random()) from
generate_series(1,1000000) id;<br /> create index i_gisttest on gisttest using gist (p);<br /><br /> And I ran this
querywith pgbench:<br /><br /> select id from gisttest order by p <-> '(0,0)' limit 1000;<br /><br /> With
unpatchedmaster, I got about 650 TPS, and with the patch 720 TPS. That's a nice little improvement, but perhaps more
importantly,the pairing heap implementation consumes less memory. To measure that, I put a
MemoryContextStats(so-><u></u>queueCtx)call into gistendscan. With the above query, but without the "limit" clause,
onmaster I got:<br /><br /> GiST scan context: 2109752 total in 10 blocks; 2088456 free (24998 chunks); 21296 used<br
/><br/> And with the patch:<br /><br /> GiST scan context: 1061160 total in 9 blocks; 1040088 free (12502 chunks);
21072used<br /><br /> That's 2MB vs 1MB. While that's not much in absolute terms, it'd be nice to reduce that memory
consumption,as there is no hard upper bound on how much might be needed. If the GiST tree is really disorganized for
somereason, a query might need a lot more.<br /><br /><br /> So all in all, I quite like this patch, even though it
doesn'tdo anything too phenomenal. It adds a some code, in the form of the new pairing heap implementation, but it
makesthe GiST code a little bit simpler. And it gives a small performance gain, and reduces memory usage a
bit.<span><fontcolor="#888888"><br /><br /> - Heikki<br /><br /></font></span><br /><br /> --<br /> Sent via
pgsql-hackersmailing list (<a href="mailto:pgsql-hackers@postgresql.org"
target="_blank">pgsql-hackers@postgresql.org</a>)<br/> To make changes to your subscription:<br /><a
href="http://www.postgresql.org/mailpref/pgsql-hackers"
target="_blank">http://www.postgresql.org/mailpref/pgsql-hackers</a><br/><br /></blockquote></div><br /></div><div
class="gmail_extra">Itmay be better to replace the lib/binaryheap altogether as it offers comparable/better
performance.<br/></div></div> 

On 12/10/2014 10:59 PM, Arthur Silva wrote:
> It may be better to replace the lib/binaryheap altogether as it offers
> comparable/better performance.

It's not always better. A binary heap is more memory-efficient, for 
starters.

There are only two uses of lib/binaryheap: reorderbuffer.c and merge 
append. Reorderbuffer isn't that performance critical, although a binary 
heap may well be better there, because the comparison function is very 
cheap. For merge append, it might be a win, especially if the comparison 
function is expensive. (That's on the assumption that the overall number 
of comparisons needed with a pairing heap is smaller - I'm not sure how 
true that is). That would be worth testing.

I'd love to test some other heap implementation in in tuplesort.c. It 
has a custom binary heap implementation that's used in the final merge 
phase of an external sort, and also when doing a so-called bounded sort, 
i.e. "ORDER BY x LIMIT Y". But that would be difficult to replace, 
because tuplesort.c collects tuples in an array in memory, and then 
turns that into a heap. An array is efficient to turn into a binary 
heap, but to switch to another data structure, you'd suddenly need extra 
memory. And we do the switch when we run out of work_mem, so allocating 
more isn't really an option.

- Heikki

On Thu, Dec 11, 2014 at 12:50 AM, Heikki Linnakangas
<hlinnakangas@vmware.com> wrote:
> On 01/28/2014 04:12 PM, Alexander Korotkov wrote:
>>>
>>> >3. A binary heap would be a better data structure to buffer the
>>> > rechecked
>>> >values. A Red-Black tree allows random insertions and deletions, but in
>>> >this case you need to insert arbitrary values but only remove the
>>> > minimum
>>> >item. That's exactly what a binary heap excels at. We have a nice binary
>>> >heap implementation in the backend that you can use, see
>>> >src/backend/lib/binaryheap.c.
>>> >
>>
>> Hmm. For me binary heap would be a better data structure for KNN-GiST at
>> all :-)
>
>
> I decided to give this a shot, replacing the red-black tree in GiST with the
> binary heap we have in lib/binaryheap.c. It made the GiST code somewhat
> simpler, as the binaryheap interface is simpler than the red-black tree one.
> Unfortunately, performance was somewhat worse. That was quite surprising, as
> insertions and deletions are both O(log N) in both data structures, but the
> red-black tree implementation is more complicated.
>
> I implemented another data structure called a Pairing Heap. It's also a
> fairly simple data structure, but insertions are O(1) instead of O(log N).
> It also performs fairly well in practice.
>
> With that, I got a small but measurable improvement. To test, I created a
> table like this:
>
> create table gisttest (id integer, p point);
> insert into gisttest select id, point(random(), random()) from
> generate_series(1, 1000000) id;
> create index i_gisttest on gisttest using gist (p);
>
> And I ran this query with pgbench:
>
> select id from gisttest order by p <-> '(0,0)' limit 1000;
>
> With unpatched master, I got about 650 TPS, and with the patch 720 TPS.
> That's a nice little improvement, but perhaps more importantly, the pairing
> heap implementation consumes less memory. To measure that, I put a
> MemoryContextStats(so->queueCtx) call into gistendscan. With the above
> query, but without the "limit" clause, on master I got:
>
> GiST scan context: 2109752 total in 10 blocks; 2088456 free (24998 chunks);
> 21296 used
>
> And with the patch:
>
> GiST scan context: 1061160 total in 9 blocks; 1040088 free (12502 chunks);
> 21072 used
>
> That's 2MB vs 1MB. While that's not much in absolute terms, it'd be nice to
> reduce that memory consumption, as there is no hard upper bound on how much
> might be needed. If the GiST tree is really disorganized for some reason, a
> query might need a lot more.
>
>
> So all in all, I quite like this patch, even though it doesn't do anything
> too phenomenal. It adds a some code, in the form of the new pairing heap
> implementation, but it makes the GiST code a little bit simpler. And it
> gives a small performance gain, and reduces memory usage a bit.
Hum. It looks that this patch using binary heap is intended to be a
replacement red-black tree method. Any reason why it isn't added to
the CF to track it?
-- 
Michael

On Tue, Jan 28, 2014 at 10:54 PM, Heikki Linnakangas
<hlinnakangas@vmware.com> wrote:
> 1. This patch introduces a new "polygon <-> point" operator. That seems
> useful on its own, with or without this patch.
This patch is tracked with this entry in the commit fest app and is
marked as "Ready for committer". Hence I am moving this specific part
to 2014-12 to keep track of it:

> 3. A binary heap would be a better data structure to buffer the rechecked
> values. A Red-Black tree allows random insertions and deletions, but in this
> case you need to insert arbitrary values but only remove the minimum item.
> That's exactly what a binary heap excels at. We have a nice binary heap
> implementation in the backend that you can use, see
> src/backend/lib/binaryheap.c.
Based on those comments, I am marking this entry as returned with feedback:
https://commitfest.postgresql.org/action/patch_view?id=1367
Heikki has sent as well a new patch to use a binary heap method
instead of the red-black tree here:
http://www.postgresql.org/message-id/54886BB8.9040000@vmware.com
IMO this last patch should be added in the CF app, that's not the case now.
Regards,
-- 
Michael

On 12/15/2014 03:49 AM, Michael Paquier wrote:
> On Thu, Dec 11, 2014 at 12:50 AM, Heikki Linnakangas
> <hlinnakangas@vmware.com> wrote:
>> On 01/28/2014 04:12 PM, Alexander Korotkov wrote:
>>>>
>>>>> 3. A binary heap would be a better data structure to buffer the
>>>>> rechecked
>>>>> values. A Red-Black tree allows random insertions and deletions, but in
>>>>> this case you need to insert arbitrary values but only remove the
>>>>> minimum
>>>>> item. That's exactly what a binary heap excels at. We have a nice binary
>>>>> heap implementation in the backend that you can use, see
>>>>> src/backend/lib/binaryheap.c.
>>>>>
>>>
>>> Hmm. For me binary heap would be a better data structure for KNN-GiST at
>>> all :-)
>>
>>
>> I decided to give this a shot, replacing the red-black tree in GiST with the
>> binary heap we have in lib/binaryheap.c. It made the GiST code somewhat
>> simpler, as the binaryheap interface is simpler than the red-black tree one.
>> Unfortunately, performance was somewhat worse. That was quite surprising, as
>> insertions and deletions are both O(log N) in both data structures, but the
>> red-black tree implementation is more complicated.
>>
>> I implemented another data structure called a Pairing Heap. It's also a
>> fairly simple data structure, but insertions are O(1) instead of O(log N).
>> It also performs fairly well in practice.
>>
>> With that, I got a small but measurable improvement. To test, I created a
>> table like this:
>>
>> create table gisttest (id integer, p point);
>> insert into gisttest select id, point(random(), random()) from
>> generate_series(1, 1000000) id;
>> create index i_gisttest on gisttest using gist (p);
>>
>> And I ran this query with pgbench:
>>
>> select id from gisttest order by p <-> '(0,0)' limit 1000;
>>
>> With unpatched master, I got about 650 TPS, and with the patch 720 TPS.
>> That's a nice little improvement, but perhaps more importantly, the pairing
>> heap implementation consumes less memory. To measure that, I put a
>> MemoryContextStats(so->queueCtx) call into gistendscan. With the above
>> query, but without the "limit" clause, on master I got:
>>
>> GiST scan context: 2109752 total in 10 blocks; 2088456 free (24998 chunks);
>> 21296 used
>>
>> And with the patch:
>>
>> GiST scan context: 1061160 total in 9 blocks; 1040088 free (12502 chunks);
>> 21072 used
>>
>> That's 2MB vs 1MB. While that's not much in absolute terms, it'd be nice to
>> reduce that memory consumption, as there is no hard upper bound on how much
>> might be needed. If the GiST tree is really disorganized for some reason, a
>> query might need a lot more.
>>
>>
>> So all in all, I quite like this patch, even though it doesn't do anything
>> too phenomenal. It adds a some code, in the form of the new pairing heap
>> implementation, but it makes the GiST code a little bit simpler. And it
>> gives a small performance gain, and reduces memory usage a bit.
> Hum. It looks that this patch using binary heap is intended to be a
> replacement red-black tree method.

Right.

Here's a new version of the patch. It now uses the same pairing heap
code that I posted in the other thread ("advance local xmin more
aggressivley",
http://www.postgresql.org/message-id/5488ACF0.8050901@vmware.com). The
pairingheap_remove() function is unused in this patch, but it is needed
by that other patch.

> Any reason why it isn't added to the CF to track it?

No. Will add.

- Heikki

On 2014-12-15 15:08:28 +0200, Heikki Linnakangas wrote:
> +/*-------------------------------------------------------------------------
> + *
> + * pairingheap.c
> + *      A Pairing Heap implementation
> + *
> + * Portions Copyright (c) 2012-2014, PostgreSQL Global Development Group
> + *
> + * IDENTIFICATION
> + *      src/backend/lib/pairingheap.c
> + *
> + *-------------------------------------------------------------------------
> + */

> diff --git a/src/include/lib/pairingheap.h b/src/include/lib/pairingheap.h
> new file mode 100644
> index 0000000..e78196d
> --- /dev/null
> +++ b/src/include/lib/pairingheap.h
> @@ -0,0 +1,67 @@
> +/*
> + * pairingheap.h
> + *
> + * A Pairing Heap implementation
> + *
> + * Portions Copyright (c) 2012-2014, PostgreSQL Global Development Group
> + *
> + * src/include/lib/pairingheap.h
> + */
> +

If we add another heap implementation we probably should at least hint
at the different advantages somewhere.

Greetings,

Andres Freund

-- Andres Freund                       http://www.2ndQuadrant.com/PostgreSQL Development, 24x7 Support, Training &
Services

On 08/03/2014 04:48 PM, Emre Hasegeli wrote:
>>> 1. This patch introduces a new "polygon <-> point" operator. That seems
>>> useful on its own, with or without this patch.
>>
>> Yeah, but exact-knn cant come with no one implementation. But it would
>> better come in a separate patch.
>
> I tried to split them.  Separated patches are attached.  I changed
> the order of the arguments as point <-> polygon, because point was
> the first one on all the others.  Its commutator was required for
> the index, so I added it on the second patch.  I also added tests
> for the operator.  I think it is ready for committer as a separate
> patch.  We can add it to the open CommitFest.

Ok, committed this part now with minor changes. The implementation was 
copy-pasted from circle <-> polygon, so I put the common logic to a 
dist_ppoly_internal function, and called that in both dist_cpoly and 
dist_ppoly.

I was surprised that there were no documentation changes in the patch, 
but looking at the docs, we just list the geometric operators without 
explaining what the argument types are. That's not very comprehensive, 
might be good to expand the docs on that, but it's not this patch's fault.

- Heikki

On 12/15/2014 11:59 PM, Jeff Janes wrote:
> On Mon, Dec 15, 2014 at 5:08 AM, Heikki Linnakangas <hlinnakangas@vmware.com
>> wrote:
>
> Here's a new version of the patch. It now uses the same pairing heap code
>> that I posted in the other thread ("advance local xmin more aggressivley",
>> http://www.postgresql.org/message-id/5488ACF0.8050901@vmware.com). The
>> pairingheap_remove() function is unused in this patch, but it is needed by
>> that other patch.
>
> Under enable-cassert, this tries to call pairingheap_empty, but that
> function doesn't exist.
>
> I looked in the other patch and didn't find it defined there, either.

Ah, I renamed pairingheap_empty to pairingheap_is_empty at the last
minute, and missed the Asserts. Here's a corrected version.

- Heikki

On 10/06/2014 12:36 PM, Emre Hasegeli wrote:
>> Thanks. The main question now is design of this patch. Currently, it does
>> all the work inside access method. We already have some discussion of pro
>> and cons of this method. I would like to clarify alternatives now. I can
>> see following way:
>>
>>     1. Implement new executor node which performs sorting by priority queue.
>>     Let's call it "Priority queue". I think it should be separate node from
>>     "Sort" node. Despite "Priority queue" and "Sort" are essentially similar
>>     from user view, they would be completely different in implementation.
>>     2. Implement some interface to transfer distance values from access
>>     method to "Priority queue" node.
>
> If we assume that all of them need recheck, maybe it can be done
> without passing distance values.

No, the executor needs the lower-bound distance value, as calculated by
the indexam, so that it knows which tuples it can return from the queue
already. For example, imagine the following items coming from the index:

tuple #    lower bound    actual distance
1    1        1
2    2        10
3    30        30
4    40        40

After the executor has fetched tuple 2, and re-checked the distance, it
pushes the tuple to the queue. It then fetches tuple 3, with lower bound
30, and it can now immediately return tuple # 2 from the queue. Because
10 < 30, so there cannot be any more tuples coming from the index that
would need to go before tuple # 2.

The executor needs the lower bound as calculated by the index, as well
as the actual distance it calculates itself, to make those decisions.

>>     3. Somehow tell the planner that it could use "Priority queue" in
>>     corresponding cases. I see two ways of doing this:
>>        - Add flag to operator in opclass indicating that index can only
>>        order by lower bound of "col op value", not by "col op value" itself.
>>        - Define new relation between operators. Value of one operator could
>>        be lower bound for value of another operator. So, planner can
>> put "Priority
>>        queue" node when lower bound ordering is possible from index. Also "ALTER
>>        OPERATOR" command would be reasonable, so extensions could upgrade.
>
> I think, it would be better to make it a property of the operator
> class.  We can add a column to pg_amop or define another value for
> amoppurpose on pg_amop.  Syntax can be something like this:
>
> CREATE OPERATOR CLASS circle_ops DEFAULT
>     FOR TYPE circle USING gist AS
>     OPERATOR 15  <->(circle, point) FOR ORDER BY pg_catalog.float_ops LOWER BOUND;
>
> While looking at it, I realize that current version of the patch does
> not use the sort operator family defined with the operator class.  It
> assumes that the distance function will return values compatible with
> the operator.  Operator class definition makes me think that there is
> not such an assumption.

Yeah. I also noticed that the type of the argument passed to the
consistent function varies, and doesn't necessarily match that declared
in pg_proc. Looking at gist_point_consistent, the argument type can be a
point, a polygon, or a circle, depending on the "strategy group". But
it's declared as a point in pg_proc.

>> Besides overhead, this way makes significant infrastructural changes. So,
>> it may be over-engineering. However, it's probably more clean and beautiful
>> solution.
>> I would like to get some feedback from people familiar with KNN-GiST like
>> Heikki or Tom. What do you think about this? Any other ideas?
>
> I would be happy to test and review the changes.  I think it is nice
> to solve the problem in a generalized way improving the access method
> infrastructure.  Definitely, we should have a consensus on the design
> before working on the infrastructure changes.

I took a stab on this. I added the reorder queue directly to the Index
Scan node, rather than adding a whole new node type for it. It seems
reasonable, as Index Scan is responsible for rechecking the quals, too,
even though re-ordering the tuples is more complicated than rechecking
quals.

To recap, the idea is that the index can define an ordering op, even if
it cannot return the tuples in exactly the right order. It is enough
that for each tuple, it returns a lower bound of the expression that is
used for sorting. For example, for "ORDER BY key <-> column", it is
enough that it returns a lower bound of "key <-> column" for each tuple.
The index must return the tuples ordered by the lower bounds. The
executor re-checks the expressions, and re-orders the tuples to the
correct order.

Patch attached. It should be applied on top of my pairing heap patch at
http://www.postgresql.org/message-id/548FFA2C.7060000@vmware.com. Some
caveats:

* The signature of the distance function is unchanged, it doesn't get a
recheck argument. It is just assumed that if the consistent function
sets the recheck flag, then the distance needs to be rechecked as well.
We might want to add the recheck argument, like you Alexander did in
your patch, but it's not important right now.

* I used the "distance" term in the executor, although the ORDER BY expr
machinery is more general than that. The value returned by the ORDER BY
expression doesn't have to be a distance, although that's the only thing
supported by GiST and the built-in opclasses.

* I short-circuited the planner to assume that the ORDER BY expression
always returns a float. That's true today for knn-GiST, but is obviously
a bogus assumption in general.

This needs some work to get into a committable state, but from a
modularity point of view, this is much better than having the indexam to
peek into the heap.

- Heikki

On 12/15/2014 03:14 PM, Andres Freund wrote:
> If we add another heap implementation we probably should at least hint
> at the different advantages somewhere.

How about adding a src/backend/lib/README for that, per attached?

- Heikki

On Wed, Dec 17, 2014 at 6:07 AM, Heikki Linnakangas
<hlinnakangas@vmware.com> wrote:
> How about adding a src/backend/lib/README for that, per attached?

I took a quick look at this. Some observations:

* I like the idea of adding a .../lib README. However, the README
fails to note that ilist.c implements an *integrated* list, unlike the
much more prevalent cell-based List structure. It should note that,
since that's the whole point of ilist.c.

* pairingheap_remove() is technically dead code. It still makes sense
that you'd have it in this patch, but I think there's an argument for
not including it at all on the theory that if you need to use it you
should use a different data structure. After all, the actual
(non-amortized) complexity of that operation is O(n) [1], and if
remove operations are infrequent as we might expect, that might be the
more important consideration. As long as you are including
pairingheap_remove(), though, why is the local variable "prev_ptr" a
pointer to a pointer to a pairingheap_node, rather than just a pointer
to a pairingheap_node?

* Similarly, the function-like macro pairingheap_reset() doesn't seem
to pull its weight. Why does it exist alongside pairingheap_free()?
I'm not seeing a need to re-use a heap like that.

*  "Assert(!pairingheap_is_empty(heap))" appears in a few places.
You're basically asserting that a pointer isn't null, often
immediately before dereferencing the pointer. This seems to be of
questionable value.

* I think that the indentation of code could use some tweaking.

* More comments, please. In particular, comment the struct fields in
pairingheap_node. There are various blocks of code that could use at
least an additional terse comment, too.

* You talked about tuplesort.c integration. In order for that to
happen, I think the comparator logic should know less about min-heaps.
This should formally be a max-heap, with the ability to provide
customizations only encapsulated in the comparator (like inverting the
comparison logic to get a min-heap, or like custom NULLs first/last
behavior). So IMV this comment should be more generic/anticipatory:

+ /*
+  * For a max-heap, the comparator must return <0 iff a < b, 0 iff a == b,
+  * and >0 iff a > b.  For a min-heap, the conditions are reversed.
+  */
+ typedef int (*pairingheap_comparator) (const pairingheap_node *a,
const pairingheap_node *b, void *arg);

I think the functions should be called pairing_max_heap* for this
reason, too. Although that isn't consistent with binaryheap.c, so I
guess this whole argument is a non-starter.

* We should just move rbtree.c to .../lib. We're not using CVS anymore
-- the history will be magically preserved.

Anyway, to get to the heart of the matter: in general, I think the
argument for the patch is sound. It's not a stellar improvement, but
it's worthwhile. That's all I have for now...

[1] https://www.cise.ufl.edu/~sahni/dsaac/enrich/c13/pairing.htm
-- 
Peter Geoghegan

On 12/20/2014 10:50 PM, Peter Geoghegan wrote:
> On Wed, Dec 17, 2014 at 6:07 AM, Heikki Linnakangas
> <hlinnakangas@vmware.com> wrote:
>> How about adding a src/backend/lib/README for that, per attached?
>
> I took a quick look at this. Some observations:
>
> * I like the idea of adding a .../lib README. However, the README
> fails to note that ilist.c implements an *integrated* list, unlike the
> much more prevalent cell-based List structure. It should note that,
> since that's the whole point of ilist.c.

Added a sentence on that.

> * pairingheap_remove() is technically dead code. It still makes sense
> that you'd have it in this patch, but I think there's an argument for
> not including it at all on the theory that if you need to use it you
> should use a different data structure. After all, the actual
> (non-amortized) complexity of that operation is O(n) [1], and if
> remove operations are infrequent as we might expect, that might be the
> more important consideration. As long as you are including
> pairingheap_remove(), though, why is the local variable "prev_ptr" a
> pointer to a pointer to a pairingheap_node, rather than just a pointer
> to a pairingheap_node?
>
> * Similarly, the function-like macro pairingheap_reset() doesn't seem
> to pull its weight. Why does it exist alongside pairingheap_free()?
> I'm not seeing a need to re-use a heap like that.

pairingheap_remove and pairingheap_reset are both unused in this patch, 
but they were needed for the other use case, tracking snapshots to 
advance xmin more aggressively, discussed here: 
http://www.postgresql.org/message-id/5488ACF0.8050901@vmware.com. In 
fact, without the pairingheap_remove() operation, the prev_or_parent 
pointer wouldn't be necessarily at all. We could've added them as a 
separate patch, but that seems like unnecessary code churn.

The prev_ptr variable is used to set the parent's first_child pointer, 
or the previous sibling's next_sibling pointer, depending on whether the 
removed node is the parent's first child or not. I'll add more comments 
in pairingheap_remove to explain that.

> *  "Assert(!pairingheap_is_empty(heap))" appears in a few places.
> You're basically asserting that a pointer isn't null, often
> immediately before dereferencing the pointer. This seems to be of
> questionable value.

I copied that from binaryheap.c. It has some documentation value; they 
make it easy to see that the functions require the heap to not be empty. 
It's also explained in comments, but still.

> * I think that the indentation of code could use some tweaking.
>
> * More comments, please. In particular, comment the struct fields in
> pairingheap_node. There are various blocks of code that could use at
> least an additional terse comment, too.

Added some comments, hope it's better now.

> * You talked about tuplesort.c integration. In order for that to
> happen, I think the comparator logic should know less about min-heaps.
> This should formally be a max-heap, with the ability to provide
> customizations only encapsulated in the comparator (like inverting the
> comparison logic to get a min-heap, or like custom NULLs first/last
> behavior). So IMV this comment should be more generic/anticipatory:
>
> + /*
> +  * For a max-heap, the comparator must return <0 iff a < b, 0 iff a == b,
> +  * and >0 iff a > b.  For a min-heap, the conditions are reversed.
> +  */
> + typedef int (*pairingheap_comparator) (const pairingheap_node *a,
> const pairingheap_node *b, void *arg);
>
> I think the functions should be called pairing_max_heap* for this
> reason, too. Although that isn't consistent with binaryheap.c, so I
> guess this whole argument is a non-starter.

I don't see what the problem is. The pairingheap.c (and binaryheap.c) 
code works the same for min and max-heaps. The comments assume a 
max-heap in a few places, but that seems OK to me in the context.

> * We should just move rbtree.c to .../lib. We're not using CVS anymore
> -- the history will be magically preserved.

Yeah, I tend to agree. Tom Lane has not liked moving things, because it 
breaks back-patching. That's true in general, even though git has some 
smarts to follow renames. I think it would work in this case, though. 
Anyway, let's discuss and do that as a separate patch, so that we don't 
get stuck on that.

> Anyway, to get to the heart of the matter: in general, I think the
> argument for the patch is sound. It's not a stellar improvement, but
> it's worthwhile. That's all I have for now...

Ok, thanks for the review! I have committed this, with some cleanup and 
more comments added.

- Heikki

On 02/17/2015 02:56 PM, Alexander Korotkov wrote:
> Hi!
>
> On Mon, Dec 22, 2014 at 1:07 PM, Heikki Linnakangas <hlinnakangas@vmware.com
>> wrote:
>
>> Ok, thanks for the review! I have committed this, with some cleanup and
>> more comments added.
>
> ISTM that checks in pairingheap_GISTSearchItem_cmp is incorrect. This
> function should perform inverse comparison. Thus, if item a should be
> checked first function should return 1. Current behavior doesn't lead to
> incorrect query answers, but it could be slower than correct version.

Good catch. Fixed, thanks.

While testing this, I also noticed a bug in the pairing heap code 
itself. Fixed that too.

- Heikki

Hi,

On 17.2.2015 14:21, Alexander Korotkov wrote:
> On Sun, Feb 15, 2015 at 2:08 PM, Alexander Korotkov
> <aekorotkov@gmail.com <mailto:aekorotkov@gmail.com>> wrote:
> 
> Revised patch with reordering in GiST is attached
> (knn-gist-recheck-in-gist.patch) as well as testing script (test.py).

I meant to do a bit of testing on this (assuming it's still needed), but
the patches need rebasing - Heikki fixed a few issues, so they don't
apply cleanly.

regards

-- 
Tomas Vondra                http://www.2ndQuadrant.com/
PostgreSQL Development, 24x7 Support, Remote DBA, Training & Services

On 04/17/2015 12:05 PM, Alexander Korotkov wrote:
> On Wed, Feb 25, 2015 at 12:15 PM, Alexander Korotkov <aekorotkov@gmail.com>
> wrote:
>
>> Hi!
>>
>> On Tue, Feb 24, 2015 at 5:39 PM, Tomas Vondra <
>> tomas.vondra@2ndquadrant.com> wrote:
>>
>>> On 17.2.2015 14:21, Alexander Korotkov wrote:
>>>> On Sun, Feb 15, 2015 at 2:08 PM, Alexander Korotkov
>>>> <aekorotkov@gmail.com <mailto:aekorotkov@gmail.com>> wrote:
>>>>
>>>> Revised patch with reordering in GiST is attached
>>>> (knn-gist-recheck-in-gist.patch) as well as testing script (test.py).
>>>
>>> I meant to do a bit of testing on this (assuming it's still needed), but
>>> the patches need rebasing - Heikki fixed a few issues, so they don't
>>> apply cleanly.
>>>
>>
>> Both patches are revised.
>>
>
> Both patches are rebased against current master.

This looks pretty much ready. I'm going to spend some time on this on 
Friday, and if all looks good, commit. (Thursday's a public holiday here).

One quick comment:

It would be good to avoid the extra comparisons of the distances, when 
the index doesn't return any lossy items. As the patch stands, it adds 
one extra copyDistances() call and a cmp_distances() call for each tuple 
(in a knn-search), even if there are no lossy tuples.

- Heikki

On 05/14/2015 01:43 PM, Alexander Korotkov wrote:
> On Wed, May 13, 2015 at 10:17 PM, Alexander Korotkov <aekorotkov@gmail.com>
> wrote:
>
>> One quick comment:
>>>
>>> It would be good to avoid the extra comparisons of the distances, when
>>> the index doesn't return any lossy items. As the patch stands, it adds one
>>> extra copyDistances() call and a cmp_distances() call for each tuple (in a
>>> knn-search), even if there are no lossy tuples.
>>
>>
>> I will fix it until Friday.
>>
>
> Attached patch is rebased against current master. Extra extra
> copyDistances() call and a cmp_distances() call for each tuple are avoided
> in the case of no lossy tuples.

Thanks! I spent some time cleaning this up:

* fixed a memory leak

* fixed a silly bug in rechecking multi-column scans

* I restructured the changes to IndexNext. I actually created a whole 
separate copy of IndexNext, called IndexNextWithReorder, that is used 
when there are ORDER BY expressions that might need to be rechecked. 
There is now some duplicated code between them, but I think they are 
both easier to understand this way. The IndexNext function is now as 
simple as before, and the IndexNextWithReorder doesn't need so many 
if()-checks on whether the reorder queue exists at all.

* I renamed Distance to OrderByValues in the executor parts. We call the 
"ORDER BY x <-> y" construct an ORDER BY expression, so let's continue 
using that terminology.

I think this is now ready for committing, but I'm pretty tired now so 
I'll read through this one more time in the morning, so that I won't 
wake up to a red buildfarm.

- Heikki

On 05/15/2015 02:28 AM, Heikki Linnakangas wrote:
> I think this is now ready for committing, but I'm pretty tired now so
> I'll read through this one more time in the morning, so that I won't
> wake up to a red buildfarm.

Forgot to attach the latest patch, here you go.

- Heikki

On 05/15/2015 11:31 AM, Alexander Korotkov wrote:
> On Fri, May 15, 2015 at 2:30 AM, Heikki Linnakangas <hlinnaka@iki.fi> wrote:
>
>> On 05/15/2015 02:28 AM, Heikki Linnakangas wrote:
>>
>>> I think this is now ready for committing, but I'm pretty tired now so
>>> I'll read through this one more time in the morning, so that I won't
>>> wake up to a red buildfarm.
>>>
>>
>> Forgot to attach the latest patch, here you go.
>
>
> Looks good for me.

Ok, pushed after some further minor cleanup.

- Heikki

On Fri, May 15, 2015 at 02:48:29PM +0300, Heikki Linnakangas wrote:
> On 05/15/2015 11:31 AM, Alexander Korotkov wrote:
> >On Fri, May 15, 2015 at 2:30 AM, Heikki Linnakangas <hlinnaka@iki.fi> wrote:
> >
> >>On 05/15/2015 02:28 AM, Heikki Linnakangas wrote:
> >>
> >>>I think this is now ready for committing, but I'm pretty tired now so
> >>>I'll read through this one more time in the morning, so that I won't
> >>>wake up to a red buildfarm.
> >>>
> >>
> >>Forgot to attach the latest patch, here you go.
> >
> >
> >Looks good for me.
> 
> Ok, pushed after some further minor cleanup.

Great!  That PostGIS workaround they had to use for accurate distances
with CTEs and LIMIT 100 was an ugly hack.

--  Bruce Momjian  <bruce@momjian.us>        http://momjian.us EnterpriseDB
http://enterprisedb.com
 + Everyone has their own god. +

On 5/14/15 6:30 PM, Heikki Linnakangas wrote:
> On 05/15/2015 02:28 AM, Heikki Linnakangas wrote:
>> I think this is now ready for committing, but I'm pretty tired now so
>> I'll read through this one more time in the morning, so that I won't
>> wake up to a red buildfarm.

If anyone feels motivated to fix, there's a typo in the comment for 
IndexNextWithReorder (s/his/this/):
+ *        Like IndexNext, but his version can also re-check any


-- 
Jim Nasby, Data Architect, Blue Treble Consulting
Data in Trouble? Get it in Treble! http://BlueTreble.com

On 05/16/2015 12:42 AM, Jim Nasby wrote:
> On 5/14/15 6:30 PM, Heikki Linnakangas wrote:
>> On 05/15/2015 02:28 AM, Heikki Linnakangas wrote:
>>> I think this is now ready for committing, but I'm pretty tired now so
>>> I'll read through this one more time in the morning, so that I won't
>>> wake up to a red buildfarm.
>
> If anyone feels motivated to fix, there's a typo in the comment for
> IndexNextWithReorder (s/his/this/):
> + *        Like IndexNext, but his version can also re-check any

Fixed, thanks.

- Heikki