This Small Business Innovation Research (SBIR) Phase I project will investigate adaptive techniques to speed up key database operations dramatically. Specifically, the project will investigate adaptive algorithms and idle-time re-balancers which can respond to bursts of insertions and to changing insertion and query patterns. Many applications insert millions of indexed records per second into storage systems. The proposed research is based on new algorithms for transactional databases that improve insertion speeds by two orders of magnitude, achieving about 2% of disk bandwidth for worst-case insertion patterns of 100-byte records, as compared to 0.01% for traditional B-tree-based databases, a 200-fold speedup. Although impressive, there remains another factor of 50 before disk bandwidth is fully utilized. The specific research objective is to obtain another order-of-magnitude speedup for insertions, allowing databases to insert millions of indexed records per second on a modestly sized disk array. The anticipated outcome of the research is an algorithm with a theoretical performance analysis, along with a design document for incorporating the design into a proposed database product. The market for databases and file systems is over $15 billion per year and growing. Furthermore, there are many application areas which do not employ database because their performance is too slow. Orders-of-magnitude speedup for databases can help grow the market by additional billions of dollars per year. Societal impact: Applications in finance, retail, homeland security, telecommunications, and scientific computing will benefit from high-performance databases. Enhanced scientific and technological understanding: The proposed research will further understanding of how to organize data on disk, which is a core problem for computation on large persistent data
