Context Navigation

Homework 2: Implementing Near-Neighbor Search in GiST

In this assignment, you will rewrite the search algorithm used in PostgreSQL's Generalized Search Tree (GiST) index to use a priority queue technique, rather than the default depth-first search algorithm. By using a priority queue ordered by a "MinDistance" metric, your implementation will return query matches in order of spatial proximity. This will provide efficient k-nearest-neighbor search in addition to the traditional range-based searches currently offered by PostgreSQL.

You should do this assignment with the same team of two that you were on for Homework 1.

Background: The Default Stack-Based Traversal Algorithm

The native search algorithm for GiST visits the children of a tree node in the order they appear on the node, recursing depth-first. The interface to PostgreSQL's GiST search routines is the gistnext function in gistget.c. This function is "incremental": the first call to the function returns a single matching tuple, and subsequent calls "continue" where the preceding call left off, returning another matching tuple, until finally all matching tuples have been returned, indicated by a return value of 0. (Actually, each call to gistnext specifies a constant number of tuples to return -- the maxtid argument -- which may be larger than 1.) We will refer to this as an iterator interface later in the semester.

Depth-first search is achieved in Postgres via a simple stack-based implementation. To start, the block number of the root is pushed on the stack. Then recursively, the traversal algorithm pops an entry off the stack, loads the associated disk block into a buffer frame, and examines each entry on the page, inserting the block numbers of the "consistent" children nodes onto the stack. Note that the children of a leaf node are data entries, not index blocks. Whenever a data entry is popped off the stack, the associated data tuple can be returned to the caller. On the next call to gistnext, the stack is used to continue where things left off.

Go ahead: read through this code in gistget.c.

Your Task: Priority Queue Traversal Based on MinDist

Your main task is to replace the Postgres depth-first search with a priority-based search. This scheme centers on a priority queue ordered by the MinDistance metric, rather than a stack. To begin, the root's block number is inserted into a priority queue with a priority score corresponding to its MinDistance to the query object. Then, recursively, the traversal algorithm calls FindMin on the priority queue. If the minimum-distance item is the block number of a tree node, then the block is loaded into the buffer pool, and each entry on the block that is "consistent" with the query is inserted into the priority queue with priority corresponding to its MinDistance to the query object. If the minimum item is a data entry, the associated tuple can be returned to the caller. The next call to gistnext uses the priority queue to continue where things left off. You should be able to convince yourself that this algorithm returns data items in order of their distance from the query object.

In this assignment, we will focus on 2-dimensional box objects only: the query object is a box, the data attribute being indexes is of type box, and the internal index entries contain Minimum Bounding Rectangles (MBRs) of the collection of boxes at the leaves. You will need to implement the MinDistance function between a query box and an MBR. Note: By definition of being "minimum", each side of an MBR "touches" some object within. So the MinDist between a query box Q and an MBR M is the minimum distance between any point on the perimeter of Q and any point on the perimeter of M. Note also that a box of zero width and zero height (e.g. '(1,1,1,1)') is a valid object -- it's a point.

Details, Details

In order to implement things correctly, you will need to interact with a number of PostgreSQL subsystems, including the Buffer Pool Manager, the Lock Manager, and the Memory Manager. For the most part, you can follow patterns used in the pre-existing stack-based version of gistnext. Here are the issues that you have to stay aware of:

For reasons of concurrency control (the gistnext_checksplit routine), you need to maintain information about each page that is stored in the stack of the original implementation. A simple way to achieve this is to also maintain the current search stack during your priority queue implementation. In particular, for each node in the priority queue, you can copy the stack from that node back to the root (without any "siblings" along the way). Then when gistnext_checksplit is called, ensure that the so->stack variable is assigned to the stack that was copied with the current item from the priority queue. You must use the same stack data structure as the one in the default Postgres implementation. The routines gistfreestack and gistcopystack are available in src/backend/access/gist/gistscan.c to assist you with this.

For an example, take a look at the attachment at the end of this page. Here, we show a snapshot of the priority queue during a nearest neighbor traversal of the tree (the query point/box and the bounding boxes are not important, and hence not illustrated). The nodes in the priority queue are ordered according to their distance from the query point. Each node is associated with a stack, which corresponds to the path of nodes from the root that is leading to that node (in other words its ancestors).

Notice how the original code takes a block number from the stack and gets the page into the buffer pool. First it "reads" the page into the buffer pool, which pins the page. Then it calls LockBuffer to grab a "lightweight" lock (called a "latch" in many DBMSs) to ensure that no other process modifies the contents of the buffer. Eventually it unlocks the buffer and "releases" the pin on the page. You will need to bracket your code in a similar pair of buffer pin and LockBuffer? requests and releases.

Like many DBMSs, Postgres uses a Context-Based Memory Allocator. It is not OK to call malloc or free in your code. Instead, use the built-in palloc and pfree routines.

On a related note, in two places in your code you will call out to GiST extension code that can be user-defined functions (UDFs): once in the gistindex_keytest routine that calls the GiST consistent method (which is done in the pre-existing GiST code), and once in the gistindex_keydistance routine that calls the min_distance method you'll use for the priority queue. Such code is considered untrusted by the DBMS, and should not be allowed to allocate memory in the same "context" as the system internals. Observe how the call to gistindex_keytest is bracketed with MemoryContext calls that change the memory context used for palloc and pfree; you'll need to do the same for calls to gistindex_keydistance.

Strategy

You will have to modify a fair bit of code to get this working. Here's a suggestion for how to break the task down into manageable steps:

Follow instructions below ASAP to check out the homework. Read through the relevant code that is copied into Hw2/MyStuff. Pay particular attention to the pre-existing implementation of gistnext, and understand how it works. Run some queries and step through it with a debugger. For example, set a breakpoint in gistnext, and try the example below that loads up table cali (replace cs186-XX with your user name):
```
   % psql
   testdb=# create table test(id integer, the_box box);
   testdb=# copy test from '/home/cc/cs186/fa07/class/cs186-XX/Hw2/MyStuff/randomboxes' deli
miter ';' ;
   testdb=# create index ix1 on test using gist (the_box box_ops);
   testdb=# select * from test where the_box && '(.75,.75,1,1)';
```
(The && operator checks for overlap of two boxes.)

Implement your priority queue. We will not require that it be an O(log n) data structure; you can use a naive linked-list implementation. For getting priority values to test with, start by implementing a dummy version of index_keydistance that returns different values on different calls (e.g. random numbers.)

Without making any other modifications to gistnext, have it insert items in the priority queue whenever it puts them on the stack, and remove the minimum from the priority queue whenever gistnext pops the stack. Using either the debugger or the gist_pq_dump routine, ensure that your priority queue is working properly.

Implement ~~box_min_distance~~ box_mindist_internal in the file geo_ops.c ~~, and replace index_keytest with code that calls it.~~

UPDATE (10/1/07): The file gistget.c now includes an implementation of index_keydistance, and there's no need to change index_keytest. If you do not see the implementation of index_keydistance in your copy of the homework, read about svn update to learn how to get it.

Implement the one-node case. Try rewriting a simple version of gistnext that uses the priority queue rather than the stack, but only works when the root node is a leaf node (the only leaf node). (At this point in development, it's OK for your code to completely crash otherwise; you'll fix it soon.) Load test data into an empty table from randomboxes25, and build a gist index on it; this will be a one-page index:
```
   % psql
   testdb=# create table test25 (id integer, the_box box);
   testdb=# copy test25 from '/home/cc/cs186/fa07/class/cs186-XX/Hw2/MyStuff/randomboxes25' delimiter ';' ;
   testdb=# create index ix2 on test25 using gist (the_box box_ops);
   testdb=# select id, box_mindistance(the_box, '(1,1,1,1)') from test25 where the_box ~~ '(1,1,1,1)';
```

This is a near-neighbor query -- it will call your GiST code and should return all 25 items in order of distance. Make sure you get correct answers (a sorted output!) for this simple case.
(A detail: I have hacked Postgres so that the ~~ operator always returns "true", but the query optimizer chooses a GiST indexscan anyhow, passing the right-hand-side of the operator as an index search key.)

Now extend that implementation to deal with trees of more than one node. Test on the full randomboxes dataset as described below.

Check up and make sure you're getting each of the "Details" above right! You may have to insert tests in your code to check that the details are being observed, since many of them are tricky to test from the SQL interface.

Logistics: Setting up, testing, etc.

Here is a bare-bones guide to doing the homework.

Check out a skeleton of Postgres 8.2.4, and build it in your tmp space.
```
 % hw2quickinstall.sh
 [... lots of output ...]
```
- In ~/Hw2/postgresql-8.2.4 you will find a link to your private copy of the Postgres source
- In ~/Hw2/MyStuff you will find copies of the two files you need to edit
- In ~/pgsql you will find the PostgreSQL installation

set up a database

 % initdb
 [... bunch of output ...]
 % pg_ctl start -l ~/Hw2/pglog
 server starting
 % createdb
 CREATE DATABASE

populate the database with example box data and build a gist R-Tree on top (replace cs186-XX below with your account name):

 % psql
 cs186-XX=# create table cali (location box, name text);
 CREATE TABLE
 cs186-XX=#  copy cali from '/home/cc/cs186/fa07/class/cs186-XX/Hw2/MyStuff/cali.txt' delimiter '|' ;
 COPY 62556
 cs186-XX=# create index cali_ix on cali using gist (location box_ops);
 CREATE INDEX

let's try a query on the original (stack-based) implementation. first double-check that Postgres' optimizer chose an index scan:

  % psql
 cs186-XX=# explain select name, box_mindistance(location, '(-1930026,-531897,-1930026,-531897)') 
 cs186-XX=# from cali where location ~~ '(-1930026,-531897,-1930026,-531897)';
                                  QUERY PLAN 
 ----------------------------------------------------------------------------
  Index Scan using cali_ix on cali  (cost=0.00..8.29 rows=1 width=64)
    Index Cond: ("location" ~~ '(-1930026,-531897),(-1930026,-531897)'::box)
 (2 rows)

Now let's run the query limited to the first 10 rows. Until you implement near-neighbor search, it will be an arbitrary 10 rows in no particular order. (So you may get a different 10 rows than this!)

 cs186-XX=# select name, box_mindistance(location, '(-1930026,-531897,-1930026,-531897)') 
 cs186-XX=# from cali where location ~~ '(-1930026,-531897,-1930026,-531897)' limit 10;
          name          |   box_mindistance   
 -----------------------+------------------
    Amador Creek        | 135400.657908298
    American Ranch Hill | 174699.053348895
    Bayley House        | 152489.026808489
    Bear Creek          | 131678.532342975
    Big Springs Creek   | 136915.215403548
    Bisbee Peak         |  137570.67655936
    Bowman Canal        | 160874.116143648
    Box Canyon          | 132413.304376864
    Bugtown Mine        | 140146.412030419
    Cave Gulch          | 133496.017213998
 (10 rows)

When you have edited the files in ~/Hw2/MyStuff to your satisfaction, install them and recompile:

 % cd ~/Hw2/MyStuff
 % ./install.sh
 % cd ../postgresql-8.2.4/src
 % gmake
 [... lots of output ...]
 % gmake install
 [... lots of output ...]

When you have the homework complete, the results will look like this:

 cs186-XX=# select name, box_mindistance(location, '(-1930026,-531897,-1930026,-531897)') 
 cs186-XX=# from cali where location ~~ '(-1930026,-531897,-1930026,-531897)' limit 10;
              name              | box_mindistance  
 -------------------------------+------------------
    Berkeley                    |                0
    Berkeley High School        | 412.021844081112
    Whittier School             | 618.328391714306
    Garfield Junior High School | 1154.91471546604
    University Of California    | 1236.27707250438
    Jefferson School            | 1296.09336083478
    Burbank Junior High School  |  1355.6673633307
    McKinley School             |   1357.973858364
    Live Oak Park               | 1462.21270682483
    Longfellow School           | 1506.30840135744
 (10 rows)

And to be sure, you can compare against a simple sorted output:

 cs186-XX=# select name, box_mindistance(location, '(-1930026,-531897,-1930026,-531897)')  as dist
 cs186-XX=# from cali order by dist limit 10;
              name              |       dist       
 -------------------------------+------------------
    Berkeley                    |                0
    Berkeley High School        | 412.021844081112
    Whittier School             | 618.328391714306
    Garfield Junior High School | 1154.91471546604
    University Of California    | 1236.27707250438
    Jefferson School            | 1296.09336083478
    Burbank Junior High School  |  1355.6673633307
    McKinley School             |   1357.973858364
    Live Oak Park               | 1462.21270682483
    Longfellow School           | 1506.30840135744
 (10 rows)

More tests will appear here in the 2nd week of the assignment!

Resources

Spatial Operators and Functions in PostgreSQL: helpful syntax for composing example queries.
PostgreSQL GiST docs
Original GiST research webpages
R-Tree Portal
Research paper with the R-tree near-neighbor algorithm and many variants. The pseudocode of interest is on page 8. However, be warned: that pseudocode is generalized to trees that can store each object more than once (e.g. R+-trees), and may be more confusing than helpful unless the discussion is read carefully. The pseudcode in the class slides is a better guide.

How to submit

As usual, create a subdirectory called hw2 and copy inside the files geo_ops.c, gist_private.h and gistget.c. Then, from the parent directory type

      % submit hw2

Note that the submission deadline is Wednesday, 11pm.

Attachments

PriorityQueue.jpg (39.4 kB) - added by admin 4 years ago. Priority Queue Example

Download in other formats:

Plain Text