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

现代数据库管理系统（DBMS）采用复杂的查询优化技术，这些技术使得能够为在非常大的数据集上的查询生成高效的执行计划。许多其他应用程序也处理大型数据集，但不能为它们的代码利用数据库风格的查询优化。在这个项目中，一个开源编程语言编译器将增强数据库风格的查询优化能力。普通程序的数据密集型部分将使用不同的执行计划分块执行。基于来自较早的块的反馈，替代计划可以用于较晚的块。编译器可以用于各种数据密集型应用程序，允许所有这些应用程序都从这类性能优化中受益。现有的内存处理查询优化技术在几个方面受到限制：（a）它们没有广泛地在关系数据库管理系统之外使用;（B）它们仅限于少数关系运算符，并且不包括在其他数据分析场景中发现的访问模式或动态定义的函数;（c）他们把底层编译器当作一个黑盒子，其不可预测的性能取决于使用哪种编译器和哪种编译器设置;（d）他们经常烘烤可能适合在特定DBMS中使用的设计选择，但不适合更一般的情况。该项目通过优化在传统命令式编程语言中表示为紧循环的数据分析风格查询来直接解决这些挑战。该项目将扩展一个开源编译器（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.