Pipelined query processing in the DBGraph storage model

The DBGraph storage model, designed for main memory DBMS, ensures both data storage compactness and efficient processing for all database operations. By representing the entire database in a unique graph-based structure, called DBGraph, it fully exploits the direct-access capability of main memory systems. Complex database queries can be processed in either set-oriented or pipelined mode depending on the way the DBGraph is traversed. In this paper we concentrate on the pipelined mode. Its advantages are the ability to produce result tuples as early as possible (during query processing) and the low cost of memory utilization in managing temporary results. We analyze different strategies for translating a query into a pipelined program and compare their performance with the set-oriented mode. Based on these results, we propose a compiler/optimizer algorithm translating relational queries into an optimal pipelined program. 1