SBIR Phase I: A Storage Engine for High-Volume Data

该小型企业创新研究(SBIR)第一阶段项目将研究显著加快关键数据库操作的自适应技术。具体地说，该项目将研究自适应算法和空闲时间重新平衡器，它们可以响应插入的突发以及不断变化的插入和查询模式。许多应用程序每秒向存储系统中插入数百万条索引记录。建议的研究基于事务数据库的新算法，这些算法将插入速度提高了两个数量级，对于最糟糕的100字节记录插入模式，实现了约2%的磁盘带宽，而传统的基于B树的数据库为0.01%，速度提高了200倍。尽管令人印象深刻，但在充分利用磁盘带宽之前，还有另一个因素是50。具体的研究目标是获得另一个数量级的插入加速，允许数据库在中等大小的磁盘阵列上每秒插入数百万条索引记录。这项研究的预期结果是一种具有理论性能分析的算法，以及一份将设计整合到拟议的数据库产品中的设计文档。数据库和文件系统的市场每年超过150亿美元，而且还在增长。此外，还有许多应用领域因为性能太慢而没有使用数据库。数据库的数量级加速可以帮助市场每年额外增长数十亿美元。社会影响：金融、零售、国土安全、电信和科学计算领域的应用程序将受益于高性能数据库。增强了对科学和技术的理解：拟议的研究将进一步了解如何组织磁盘上的数据，这是对大型持久数据进行计算的核心问题。

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.