Space-partitioning Trees in PostgreSQL Realization and Performance.pdf

hardware

12页

0次

2021-07-27

免费下载

Space-partitioning Trees in PostgreSQL: Realization and Performance

∗

Mohamed Y. Eltabakh Ramy Eltarras Walid G. Aref

Computer Science Department, Purdue University

{meltabak, rhassan, aref}@cs.purdue.edu

Abstract

Many evolving database applications warrant the use

of non-traditional indexing mechanisms beyond B+-trees

and hash tables. SP-GiST is an extensible indexing frame-

work 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 imple-

menting and realizing SP-GiST-based indexes inside Post-

greSQL. Several index types are realized inside PostgreSQL

facilitated by rapid SP-GiST instantiations. Challenges, ex-

periences, and performance issues are addressed in the pa-

per. 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 string, point, and line segment data sets. Interesting re-

sults that highlight the potential performance gains of SP-

GiST-based indexes are presented in the paper.

1 Introduction

Many emerging database applications warrant the use of

non-traditional indexing mechanisms beyond B+-trees and

hash tables. Database vendors have realized this need and

have initiated efforts to support several non-traditional in-

dexes, e.g., (Oracle [37], and IBM DB2 [1]).

One of the major hurdles in implementing non-

traditional indexes inside a database engine is the very wide

variety of such indexes. Moreover, there is tremendous

overhead associated with realizing and integrating any of

these indexes inside the engine. Generalized search trees

(e.g., GiST [21] and SP-GiST [3, 4]) are designed to ad-

dress this problem.

Generalized search trees (GiST [21]) and Space-

partitioning Generalized search trees (SP-GiST [3, 4]) are

software engineering frameworks for rapid prototyping of

indexes inside a database engine. GiST supports the class of

∗

This work was supported in part by the National Science Foundation

under Grants IIS-0093116, IIS-0209120, and 0010044-CCR.

balanced trees (B+-tree-like trees), e.g., R-trees [7, 20, 34],

SR-trees [25], and RD-trees [22], while SP-GiST supports

the class of space-partitioning trees, e.g., tries [10, 16],

quadtrees [15, 18, 26, 30], and kd-trees [8]. Both frame-

works have internal methods that furnish general database

functionalities, e.g., generalized search and insert algo-

rithms, as well as user-deﬁned external methods and pa-

rameters that tailor the generalized index into one instance

index from the corresponding index class. GiST has been

tested in prototype systems, e.g., in Predator [36] and in

PostgreSQL [39], and is not the focus of this study.

The purpose of this study is to demonstrate feasibility

and performance issues of SP-GiST-based indexes. Us-

ing SP-GiST instantiations, several index types are realized

rapidly inside PostgreSQL that index string, point, and line

segment data types. In addition, several advanced search

operations are developed inside the SP-GiST framework.

In particular, in addition to the standard index maintenance

and search mechanisms, we realized the nearest-neighbor

(NN) search algorithm proposed in [23] to support NN

search over space partitioning trees. Performance compar-

isons are conducted from within PostgreSQL to compare

update and search performances of (1) a disk-based trie

variant against the B+-tree for a variety of string dataset

collections, (2) a disk-based kd-tree variant against the

R-tree for two-dimensional point dataset collections, and

(3) a disk-based quadtree variant (the PMR-quadtree [30])

against the R-tree for line segment datasets. In addition to

the performance gains and the advanced search functionali-

ties provided by SP-GiST indexes, it is the ability to rapidly

prototype these indexes inside a DBMS that is most attrac-

tive.

The contributions of this paper are as follows:

1. We realized SP-GiST inside PostgreSQL to extend

the available access methods to include the class of

space-partitioning trees, e.g., quadtrees, tries, kd-trees

and sufﬁx trees. Our implementation methodology

makes SP-GiST portable, i.e., SP-GiST is realized in-

side PostgreSQL without recompiling PostgreSQL.

2. We extended the index operations in SP-GiST to in-

clude preﬁx and regular expression match, and a

generic incremental NN search for SP-GiST-based in-

dexes.

3. We conducted extensive experiments from within Post-

greSQL to compare the performance of SP-GiST in-

dexes against the B+-tree and R-tree. Our results show

that a disk-based SP-GiST trie performs more than 2

orders of magnitude better than the B+-tree for a regu-

lar expression match search, and that a disk-based SP-

GiST kd-tree performs more than 300% better than an

R-tree for a point match search.

4. We realized a disk-bsed sufﬁx tree index using SP-

GiST to support substring match searching. Our exper-

iments demonstrate that the sufﬁx tree performs more

than 3 orders of magnitude better than existing tech-

niques.

5. We made the PostgreSQL version of SP-GiST

available for public access and download at:

www.cs.purdue.edu/spgist.

The rest of this paper proceeds as follows. In Section 2, we

highlight related work. In Section 3, we overview space-

partitioning trees, the challenges they have from database

indexing point of view, and how these challenges are ad-

dressed in SP-GiST. Section 4 describes the implementation

of SP-GiST inside PostgreSQL. Section 5 presents a new

nearest-neighbor search functionality for SP-GiST. In Sec-

tion 6, we present the performance results of a disk-based

SP-GiST trie vs. the B+-tree for string data sets, and a disk-

based SP-GiST kd-tree and PMR quadtree vs. the R-tree

for two-dimensional point and line segment data sets, re-

spectively. Section 7 contains concluding remarks.

2 Related Work

Multidimensional searching is a fundamental operation

for many database applications. Several index structures

beyond B-trees [6, 11] and hash tables [14, 31] have been

proposed for multidimensional data, e.g., [17, 29, 33, 35].

These index structures include the R-tree and its variants,

e.g., [7, 20, 34], the quadtree and its variants, e.g., [15,

18, 26, 41], the kd-tree [8] and its disk-based variants,

e.g., [9, 32], and the trie and its variants [2, 10, 16]. Ex-

tensions to the B-tree have been proposed to index multidi-

mensional data, e.g., [5, 13]. Extensible indexing frame-

works have been proposed to instantiate a variety of in-

dex structures in an efﬁcient way and without modifying

the database engine. Extensible indexing frameworks are

ﬁrst proposed in [38]. GiST (Generalized Search Trees) is

an extensible framework for B-tree-like indexes [21]. SP-

GiST (Space Partitioning Generalized Search Trees) is an

extensible framework for the family of space-partitioning

trees [3, 4, 19]. Extensible indexing structures are impor-

tant in the context of object-relational database management

systems to support new data types. The implementation of

GiST in Informix Dynamic Server with Universal Data Op-

tion (IDS/UDO) is presented in [27]. Commercial databases

have supported extensible indexing frameworks, e.g., IBM

DB2 [1], and Oracle [37]. The performance of various in-

dex structures have been studied extensively. For example,

a model for the R-tree performance is proposed in [40]. R-

tree and quadtree variants are compared in [24] and from

within Oracle Spatial in [28].

3 Space-partitioning Trees: Overview, Chal-

lenges, and SP-GiST

The main characteristic of space-partitioning trees is

that they partition the multi-dimensional space into disjoint

(non-overlapping) regions. Refer to Figures 1, 2, and 3, for

a few examples of space-partitioning trees. Partitioning can

be either (1) space-driven (e.g., Figure 2), where we decom-

pose the space into equal-sized partitions regardless of the

data distribution, or (2) data-driven (e.g., Figure 3), where

we split the data set into equal portions based on some cri-

teria, e.g., based on one of the dimensions.

There are many types of trees in the class of space-

partitioning trees that differ from each other in various

ways. Without loss of generality, and for the simplicity of

this discussion, we highlight below some of the important

variations in the context of the trie data structure.

• Path Shrinking (refer to Figure 1) - The problem is

that we may want to avoid lengthy and skinny paths

from a root to a leaf. Paths of one child can be col-

lapsed into one node. For example, the Patricia trie

allows for leaf-shrinking (Shrinking single child nodes

at the leaf level nodes, e.g., Figure 1(b)), while it is

also possible to allow for path-shrinking (Shrinking

single child nodes at the non-leaf level nodes, e.g., Fig-

ure 1(c)), or even no shrinking at all (Figure 1(a)).

• Node Shrinking (refer to Figure 2) - The problem is

that with space-driven partitions, some partitions may

end up being empty. So, the question is: Do we al-

low that empty partitions be omitted? For example,

the difference between the standard trie (Figure 2(a))

and the forest trie (Figure 2(b)) is that the latter allows

for empty partitions to be eliminated.

• Clustering - This is one of the most serious issues

when addressing disk-based space-partitioning trees.

The problem is that tree nodes do not map directly to

disk pages. In fact, tree nodes are usually much smaller

than disk pages. So, the question is: How do we pack

of 12

免费下载

postgresql

关注

评论