DOI: 10.17587/prin.9.22-28

Improving Penalty Function of R-tree over Generalized Index Search Tree as Possible Way to Advance Performance of PostgreSQL Cube Extension

S. V. Porshnev, s.v.porshnev@urfu.ru, O. A. Ponomareva, o.a.ponomareva@urfu.ru, Ural Federal University, 620002, Yekaterinburg, Russian Federation, A. M. Borodin, amborodin@urfu.ru, Yandex, 620014, Yekaterinburg, Russian Federation, S. G. Mirvoda, s.g.mirvoda@urfu.ru, Octonika, 620014, Yekaterinburg, Russian Federation

Corresponding author: Ponomareva Olga A., Lector, Ural Federal University, 620002, Yekaterinburg, Russian Federation, E-mail: o.a.ponomareva@urfu.ru

At present time databases solve many different technical challenges. They store data compactly, resolve data write conflicts and allow efficient data querying. The last challenge is undertaken by so called access methods (AM), i.e. algorithms and data structures enabling quick retrieval of the data by certain conditions. The paramount of AMs for modern relational databases is a B-tree allowing fast retrieval of data by the primary key and many other useful operations. Generalized index search tree (GiST) is an AM technique, which allows abstraction of significant parts of the data access methods, structured as a balanced tree. Use of the GiST allows AM developer to concentrate on their own case-specific details of AM and skip common work on the tree structure implementation within database engine, a query language integration, a query planner support, etc. Generalized index search tree (GiST) greatly simplifies data access methods development. Important parts like query processing, failure recovery, memory management are implemented in generic code, so access method developer has to implement only specifics of the desired algorithm. But this generality comes with a significant cost of fitting a method for GiST API. In this paper we present a number of tweaks to the R-tree implementation inside PostgreSQL GiST framework and analyze possible ways of GiST API advancements.

Keywords: generalized index search tree, multidimensional access method, PostgreSQL, R-tree

pp. 22–28

For citation:
Porshnev S. V., Ponomareva O. A., Borodin A. M., Mirvoda S. G. Improving Penalty Function of R-tree over Generalized Index Search Tree as Possible Way to Advance Performance of PostgreSQL Cube Extension, Programmnaya Ingeneria, 2018, vol. 9, no 1, pp. 22—28.