| PostgreSQL 8.4devel Documentation | ||||
|---|---|---|---|---|
| Prev | Fast Backward | Chapter 52. GIN Indexes | Fast Forward | Next |
Internally, a GIN index contains a B-tree index constructed over keys, where each key is an element of the indexed value (a member of an array, for example) and where each tuple in a leaf page is either a pointer to a B-tree over heap pointers (PT, posting tree), or a list of heap pointers (PL, posting list) if the list is small enough.
GIN can support "partial match" queries, in which the query
does not determine an exact match for one or more keys, but the possible
matches fall within a reasonably narrow range of key values (within the
key sorting order determined by the compare support method).
The extractQuery method, instead of returning a key value
to be matched exactly, returns a key value that is the lower bound of
the range to be searched, and sets the pmatch flag true.
The key range is then searched using the comparePartial
method. comparePartial must return zero for an actual
match, less than zero for a non-match that is still within the range
to be searched, or greater than zero if the index key is past the range
that could match.
During a partial-match scan, all itemPointers for matching keys are OR'ed into a TIDBitmap. The scan fails if the TIDBitmap becomes lossy. In this case an error message will be reported with advice to increase work_mem.