$PostgreSQL: pgsql/src/backend/access/gist/README,v 1.1 2005/09/1516:39:15 teodor Exp $

$PostgreSQL: pgsql/src/backend/access/gist/README,v 1.2 2005/09/1517:44:27 neilc Exp $

This directory contains an implementation of GiST indexing for Postgres.

GiST is stands for Generalized Search Tree. It was introduced in seminal paper

"Generalized Search Trees for Database Systems", 1995,Joseph M. Hellerstein,

Jeffrey F. Naughton,Avi Pfeffer (http://www.sai.msu.su/~megera/postgres/gist/papers/gist.ps) and implemented by J. Hellerstein and P.Aoki in early version of

PostgreSQL ( more details is available from The GiST Indexing Project at

Berkeley at http://gist.cs.berkeley.edu/). As an "university" project it had a

limited number of features and was in rare use.

GiST stands for Generalized Search Tree. It was introduced in the seminal paper

"Generalized Search Trees for Database Systems", 1995, Joseph M. Hellerstein,

Jeffrey F. Naughton, Avi Pfeffer:

Current implementation of GiST supports:

http://www.sai.msu.su/~megera/postgres/gist/papers/gist.ps

and implemented by J. Hellerstein and P. Aoki in an early version of

PostgreSQL (more details are available from The GiST Indexing Project

at Berkeley at http://gist.cs.berkeley.edu/). As a "university"

project it had a limited number of features and was in rare use.

The current implementation of GiST supports:

* Variable length keys

* Composite keys (multi-key)

* provides NULL-safe interface to GiST core

* Concurrency

* Recovery support via WAL logging

Concurrence algoritms implemented in PostgreSQL were developed following paper

"Access Methods for Next-Generation Database Systems" by Marcel Kornaker (http://www.sai.msu.su/~megera/postgres/gist/papers/concurrency/access-methods-for-next-generation.pdf.gz).

The support for concurrency implemented in PostgreSQL was developed based on the paper "Access Methods for Next-Generation Database Systems" by Marcel Kornaker:

* They should be adapted to PostgreSQL conventions. For example, SEARCH

The original algorithms were modified in several ways:

* They should be adapted to PostgreSQL conventions. For example, the SEARCH

algorithm was considerably changed, because in PostgreSQL function search

should return one tuple (next), not all tuples at once. Also, it should

release page locks between calls.

*since we added supportof variable length keys, it's not possible to guarantee

*Since we added supportfor variable length keys, it's not possible to guarantee

enough free space for all keys on pages after splitting. User defined function

picksplit doesn't have information about size of tuples (each tuple may

contain several keys as in multicolumn index while picksplit could work with

only one key) and pages.

* We modified original INSERT algorithm forperfomance reason. Inparticularly,

it's single-pass algorithm.

* Since thepaper were theoretical, some details wereomited and we have to find

out ourself how to solve some specific problems.

only one key) and pages.

* We modified original INSERT algorithm forperformance reason. Inparticular,

it is now a single-pass algorithm.

* Since thepapers were theoretical, some details wereomitted and we

have to findout ourself how to solve some specific problems.

Because of above reasons, we have to revised interaction of GiST core and

PostgreSQL WAL system. Moreover, we encountered (and solved) a problem of

uncompleted insertions when recovering after crash, which was not touched in

the paper.

Because oftheabove reasons, we have to revised interaction of GiST

core andPostgreSQL WAL system. Moreover, we encountered (and solved)

a problem ofuncompleted insertions when recovering after crash, which

was not touched inthe paper.

SEARCH ALGORITHM

Function gettuple finds tuple, which satisfy search predicate. It store their

state and returns next tuple under subsequent calls. Stack contains page,

its LSN and LSN of parent page and currentposition is saved between calls.

Function gettuple finds a tuple which satisfies the search

predicate. It store their state and returns next tuple under

subsequent calls. Stack contains page, its LSN and LSN of parent page

and currentposition is saved between calls.

gettuple(search-pred)

if ( firsttime )

the node splitting algorithm; method Union is used for propagating changes

upward to maintain the tree properties.

NOTICE: We modified original INSERT algorithm forperfomance reason. In

particularly, it's single-pass algorithm.

NOTICE: We modified original INSERT algorithm forperformance reason. In

particularly, it is now a single-pass algorithm.

Function findLeaf is used to identify subtree for insertion. Page, in which

insertion is proceeded, is locked as well as its parent page. Functions