Generation of low-level LLVM code from Query Plans
The project focuses on transforming range-restricted queries (with nested loops joins, concatenations, projections, and simple negations) to LLVM code structured as an open-first-next-close style iterator. The input to the code generator is a range-restricted FOL query representing a query plan and a list of iterator interfaces to access paths that implement atomic predicates in the plan. The focus of the project is on efficient code generation, in particular, on issues related to inlining simple access paths, such as field extraction, in the generated code. The project should also provide the implementations of basic MM access paths, such as arrays, lists, and records/pointers, including a way to create and bulk load a sample initial instance of these to test the generated code.
Tree (or other deadlock and abort-free) Locking Techniques for MM Systems
The goal of the project is to develop a lock manager based on deadlock and abort-free concurrency control protocols that can be used as an utility by the remainder of a MM DBMS: the utility should provide an API that the rest of the system must call in order to obtain locks before accessing data items in MM. The project's focus is twofold: first, given a lock tree how to efficiently acquire/release locks (with minimal overhead), and second, given a workload (in terms of reads and updates of main memory structures, such as linked lists), how to define an appropriate lock-tree for such a situation (this is much more ambitious).
Analysis of the Halloween Problem
The goal of this project is to consider what the appropriate semantics ought to be in this setting, how one can detect the problem happening, and what can one do to prevent it. (coming up with partial answers/solutions is perfectly good for a project).
Bi-cameral MM layout and other of objects (records)
The goal is to modify the bidirectional layout of objects described in
Joseph Gil, William Pugh, Grant E. Weddell, Yoav Zibin: Two-dimensional bidirectional object layout. ACM Trans. Program. Lang. Syst. 30(5) (2008)
to a bi-cameral layout (in which the two directions are represented by separate MM records) using double pointers to account for the layout modification. The project's goal is to develop the formalism and (optionally) to compare the performance with the original 2D layout.
Bi-cameral MM layout and other of objects (records)
The goal of this project is to consider object layout in secondary storage and the implications of the existence of secondary storage on queries and updates.
The goal of this project is to figure out how to check whether a user's transaction satisfies integrity constraints: the main question is what is the minimal (but sufficient) amount of checking needed and (optionally) how to generate efficient code for it
Cost Estimation for (Main Memory) Queries
The goal of the project is to develop cost estimation model for MM queries based on the performance characteristics of MM access paths and on physical characteristics of memory, such as the sizes and organizations of various caches. The project can range from adopting and modifying existing cost estimation techniques to developing analytic results pertinent to cost estimation in MM. On another dimension, the results can range from analytic/statistical guarantees to experimental verification of the efficacy of the proposed cost model.
Survey of Physical Design Patterns in Main Memory Database and Information Systems
The goal of this project is to assemble a comprehensive (as feasible) survey of ways in which data is typically stored in various M/IMDB information systems. The survey should provide
Survey of Physical Design Specification Languages
The goal of this project is to survey the state of art in how physical design decisions are communicated to database and information systems, ranging from system build/configuration options to extensions of the DDL/DML languages.
Survey of Concurrency Control in MMDB and Operating systems
The goal of the project is to survey the literature on Concurrency Control in MMDBs and operating systems. The survey should not only list the techniques, but also contrast the differences between DB and OS approaches.
Survey of Durability Guarantees and Implementations for MMDB Systems
The goal of the project is to investigate what durability guarantees are provided by MMDB systems and how durability is implemented in these systems.
(more to come)