|
|
|
 |
|
 |
|
Processing Operations with Restrictions in RDBMS without External Sorting: The Tetris Algorithm
|
V. Markl,
M. Zirkel,, and
R. Bayer
View Paper (PDF)
Return to Session 17: Query Processing & Reconciliation
Most operations of the relational algebra or SQL require a sorted stream of tuples for efficient processing. Therefore, processing complex relational queries relies on efficient access to a table in some sort order. In principle, indexes could be used, but they are superior to a full table scan only, if the result set is sufficiently restricted in the index attribute. In this paper we present the Tetris algorithm, which utilizes restrictions to process a table in sort order of any attribute without the need of external sorting. The algorithm relies on the space partitioning of a multidimensional access method. A sweep line technique is used to read data in sort order of any attribute, while accessing each disk page of a table only once. Results are produced earlier than with traditional sorting techniques, allowing better response times for interactive applications and pipelined processing of the result set. We describe a prototype implementation of the Tetris algorithm using UB-Trees on top of Oracle 8, define a cost model and present performance measurements for some queries of the TPC-D benchmark.
Keywords: query processing, relational database management systems, performance measurements, data warehousing, OLAP, TPC-D benchmark, access methods, UB-Tree
Copyright(C) 2000 ACM
|
|
|
|
|
|
|
