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