Dissertation: Advanced Query Processing

Complex queries such as correlated queries are common in decision support systems. Traditional nested iteration evaluation method is time-consuming and query rewriting technique does not always apply. I have designed and implemented a new ``invariant'' technique that can evaluate arbitrary correlated queries efficiently. The technique recognizes the part of the subquery that is uncorrelated and tries to cache and reuse the invariant result. The method can be integrated smoothly into a conventional cost-based optimizer.

As random access memory gets cheaper, it becomes possible to keep database tables memory resident. An important factor in main memory query processing is cache behavior. Cache miss penalty is high given the current speed gap between cache access and main memory access. I propose two cache conscious main memory indexing structures: Cache Sensitive Search (CSS) Trees and Cache Sensitive B+(CSB+) Trees. By better utilizing each cache line, both indexes are faster in searching than existing indexing structures such as B+-Trees and T-Trees. While CSS-Trees are designed for OLAP environment where updates are batched and infrequent, CSB+-Trees support incremental updates in a fashion similar to B+-Trees and can be used for a more general purpose.