Thesis Presentation

Recent analysis of concurrent decision-support systems suggests that DSS workloads exhibit several recurring data access and computation patterns. Multiple clients in the system simultaneously submit queries which access the same disk pages, compute similar aggregates, produce intermediate results which are subsets of other intermediate results, etc. Harizopoulos et al proposed staged database systems to identify and take advantage of instruction and data commonality across concurrent queries by providing the execution engine with more control over how data and instructions are accessed.

Although a staged database management system (DBMS) may improve DSS workload performance, it must address several issues which do not arise in a conventional query-centric DBMS. Many of these issues stem from the staged system's use of producer-consumer networks of worker threads to process each query. The system must allocate worker threads so that at least one query always makes forward progress. The system must also deal with the bounded buffer deadlocks which arise in non-tree producer-consumer networks in which producers are forced to wait for full buffers to drain.

In this thesis, we show that imposing a total ordering on the packet types and pessimistically reserving worker threads before query dispatch eliminates the worker thread allocation problem with a small performance penalty. Our measurements show speedups between 0.967 and 1.132 with an average speedup of 1.022. We also show that selectively flushing shared intermediate buffers to disk files is an effective solution to the bounded buffer deadlock problem. This selective materialization approach is much easier to implement than the avoidance algorithms previously analyzed. Our materialization implementation shows speedups between 0.748 and 1.301 with an average speedup of 0.966. We have indications that the remaining penalties can be reduced by using more scan-friendly cache replacement policies.

Thesis Committee:
Anastasia Ailamaki, Chair
David R. O’Hallaron