To trie or not to trie? realizing space-partitioning trees inside postgresql: Challenges, experiences and performance

Many evolving database applications warrant the use of non-traditional indexing mechanisms beyond B+-trees and hash tables. SP-GiST is an extensible indexing framework that broadens the class of supported indexes to include disk-based versions of a wide variety of space-partitioning trees: e.g. disk-based trie variants, quadtree variants. and kd-trees. This paper presents a serious attempt at implementing and realizing SP-GiST-based indexes inside PostgreSQL. Several index types are realized inside PostgreSQL facilitated by rapid SP-GiST instantiations. Challenges, experiences. and performance issues are addressed in the paper. Performance comparisons are conducted from within PostgreSQL to compare update and search performances of SP-GiST-based indexes against the B+-tree and the R-tree for text string and point data sets. Interesting performance results are presented in the paper. Results highlight the potential performance gains of SP-GiST-based indexes as well as several strengths and weaknesses of SP-GiST-based indexes that need to be addressed in future research