GSoC/GCI Archive
Google Summer of Code 2012 PostgreSQL Project

Better indexing for ranges

by Alexander Korotkov for PostgreSQL Project

Range types are singnificant new feature of PostgreSQL. Indexing of range types is necesary to provide efficient search of ranges. The currently implemented for 9.2 indexing approach for GiST holds ranges in both internal and leaf pages entries. This approach could be very inefficient in the case of highly overlapping ranges and "@>", "<@" operators, because cost of search is similar to cost of search using "&&" operator. Mapping ranges into 2d-space could handle such cases much more efficiently. This project is focused on implementation 2d-space mapping based GiST and SP-GiST operator classes for range types.