Database management systems will continue to manage large data volumes. Thus, efficient
algorithms for accessing and manipulating large sets and sequences will be required to provide
acceptable performance. The advent of object-oriented and extensible database systems will not
solve this problem. On the contrary, modern data models exacerbate it: In order to manipulate
large sets of complex objects as efficiently as today’s database systems manipulate simple
records, query processing algorithms and software will become more complex, and a solid
understanding of algorithm and architectural issues is essential for the designer of database
management software.
This survey pro vides a foundation for the design and implementation of query execution facilities
in new database management systems. It describes a wide array of practical query evaluation
techniques for both relational and post-relational database systems, including iterative execution
of complex query evaluation plans, the duality of sort- and hash-based set matching algorithms,
types of parallel query execution and their implementation, and special operators for emerging
database application domains.