Flattening an Object Algebra to Provide Performance

Algebraic transformation and optimization techniques have been the method of choice in relational query execution, but applying them in OODBMS has been difficult due to the complexity of object-oriented query languages. This paper demonstrates that the problem can be simplified by mapping a complex storage model to the flat binary model implemented by Monet, a state-of-the-art database kernel. We present a generic mapping scheme to flatten data models and study the case of a straightforward object-oriented model. We show how flattening enabled us to implement a full-fledged query algebra on it, using only a very limited set of simple operations. The required primitives and query execution strategies are discussed, and their performance is evaluated on the 1GB TPC-D benchmark, showing that our divide-and-conquer approach yields excellent results.