III: Small: Bringing database query optimization to data intensive applications

现代数据库管理系统(DBMS)采用复杂的查询优化技术，能够针对非常大的数据集生成高效的查询执行计划。各种其他应用程序也处理大型数据集，但不能对其代码利用数据库风格的查询优化。在这个项目中，一个开源编程语言编译器将得到增强，具有数据库式的查询优化能力。普通程序的数据密集型部分将使用不同的执行计划分块执行。根据之前组块的反馈，可能会对后面的组块使用替代计划。现有的用于内存处理的查询优化技术在几个方面受到限制：(A)它们在关系数据库管理系统之外没有被广泛使用；(B)它们仅限于少数几个关系运算符，并且不包括在其他数据分析场景中发现的访问模式或动态定义的函数；(C)它们将底层编译器视为黑匣子，具有不可预测的性能，这取决于哪个编译器与哪个编译器设置一起使用；(D)它们经常烘焙可能适合在特定数据库管理系统中使用的设计选择，但不适用于更一般的情况。该项目通过优化在传统命令式编程语言中表示为紧密循环的数据分析风格的查询，直接解决了这些挑战。该项目将使用已知和新颖的优化技术扩展开源编译器(GraalVM/Truffle)，只要编译器发现循环很耗时，就会自动应用这些技术。集成到编译器中允许许多应用程序高效地处理大型数据集。该系统将支持涉及用户定义函数和任意访问模式的动态查询。数据库风格的优化和编译器优化将在一个系统中共存，消除了当编译器被DBMS用作黑匣子时发生的一些不匹配。该系统将自动调整各种运行时执行参数，只需程序员提供最少的指导。扩展的编译器将通过开发交互式数据探索应用程序进行验证，该应用程序将允许用户动态指定和分析各种大型内存数据集。该奖项反映了NSF的法定使命，并通过使用基金会的智力优势和更广泛的影响审查标准进行评估，被认为值得支持。

Modern database management systems (DBMSs) employ sophisticated query optimization techniques that enable the generation of efficient execution plans for queries over very large data sets. A variety of other applications also process large data sets, but cannot leverage database-style query optimization for their code. In this project, an open-source programming language compiler will be enhanced with database-style query optimization capabilities. Data-intensive parts of ordinary programs will be executed in chunks using different execution plans. Based on feedback from earlier chunks, alternative plans might be used for later chunks. The compiler could be used for a variety of data-intensive applications, allowing all of them to benefit from this class of performance optimizations.Existing query optimization techniques for in-memory processing are limited in several ways: (a) they are not extensively used outside relational database management systems; (b) they are limited to a handful of relational operators, and do not cover access patterns or dynamically-defined functions found in other data-analysis scenarios; (c) they treat the underlying compiler as a black-box, with unpredictable performance depending on which compiler is used with which compiler settings; (d) they often bake-in design choices that may be appropriate for usage within a particular DBMS, but not for more general cases. This project directly addresses these challenges by optimizing data-analysis style queries expressed as tight loops in a conventional imperative programming language. This project will extend an open-source compiler (GraalVM/Truffle) with both known and novel optimization techniques that will automatically be applied whenever the compiler identifies that a loop is time-consuming. Integration into the compiler allows many applications to efficiently process large data sets. The system will support dynamic queries involving user-defined functions and arbitrary access patterns. Database-style and compiler optimizations will co-exist in one system, eliminating some of the mismatches that happen when the compiler is used as a black-box by a DBMS. The system will tune a variety of run-time execution parameters automatically, with minimal guidance from the programmer. The extended compiler will be validated by developing an interactive data exploration application that will allow users to dynamically specify and analyze a variety of large in-memory datasets.This award reflects NSF's statutory mission and has been deemed worthy of support through evaluation using the Foundation's intellectual merit and broader impacts review criteria.