Access methods for next-generation database systems
Marcel Kornacker, Joseph M. Hellerstein · 2000
Today's extensible object-relational database management systems (ORDBMSs) are being deployed to support nontraditional applications such as dynamic web servers and geographic information systems. ORDBMSs distinguish themselves from purely relational DBMSs by providing an extensible architecture, built around a richer and user-extensible type system combined with object-oriented concepts such as type hierarchies. They retain standard features of relational databases such as declarative access, multiuser operation, transactional isolation and recoverability. One particular aspect of DBMS functionality that is critical to performance is their support for access methods (AMs). In traditional relational DBMSs, B+-trees [Com79] serve as the AM of choice to provide a very high level of performance for applications dealing with the standard SQL datatypes (numeric data, character strings, dates, etc.). In order to provide the same level of performance for non-traditional applications, B+-trees are not sufficient; instead, novel kinds of datatype-specific AMs are required. The most promising approach to supporting those novel AMs is an extensible architecture in which the core services of the ORDBMS can be complemented with externally-supplied AMs. In my dissertation, I investigate general issues that arise in the design and implementation of nontraditional AMs in an extensible ORDBMS. This research was undertaken in the context of the generalized search tree (GIST), a tree-structured template access method, which encapsulates standard AM search and update functions and is a suitable basis for AM extensibility in ORDBMSs. The dissertation contains three contributions. The first is an extension of the GIST API that makes it more flexible and at the same time improves performance when implemented in a typical commercial ORDBMS. The second comprises concurrency and recovery protocols that allow GiSTs to be useful in application scenarios where high concurrency and recoverability are required. With these protocols, GiSTs fully encapsulate physical concurrency, transactional isolation and recovery, and thereby relieve an external access method of the burden of dealing with these issues. The API extensions and the concurrency and recovery protocols together make GiSTs a high-performance alternative to custom AM development in commercial ORDBMS. The third contribution is an AM performance analysis framework, implemented in a corresponding tool, that gives the AM developer a detailed picture of an AM's performance deficiencies while still retaining the GIST framework's independence of the datatype and application.