Statistics on query expressions in relational database management systems
Statistics on query expressions in relational database management systems
复制标题
关系数据库管理系统中查询表达式的统计
DOI：
--
复制
发表时间：
2003
期刊：
影响因子：
--
通讯作者：
Nicolas Bruno
中科院分区：
文献类型：
--
作者：
L. Gravano;Nicolas Bruno
查询优化器是关系数据库系统中的组件，用于识别输入查询的有效执行计划。现代优化器通常以基于成本的方式探索许多替代查询计划。具体来说，估计每个候选计划的资源消耗和相关成本，并选择预期成本最低的计划来执行。计划的成本估算取决于多个因素，包括执行期间的资源可用性、组成计划的特定运算符以及计划执行期间生成的中间结果的大小。在这些因素中，中间结果大小（或基数）估计是优化期间不准确的主要来源：基数估计通常依赖于几个在实践中通常不成立的简化假设。优化器有时会根据不准确的信息做出决策，并产生低质量的执行计划。为了解决这个限制，在本文中我们引入了 SITS 的概念，它是基于查询表达式构建的统计信息。 SITS 直接准确地对查询执行计划中的中间结果进行建模，从而避免在基数估计期间容易出错的简化假设。如果优化器在优化期间有适当的 SITS 可用，则生成的查询计划可能会比其他情况好得多。尽管 SIT 是一个相当简单的概念，但在将 SIT 无缝集成到现代关系数据库系统中之前，需要解决具有挑战性的问题。在本文中，我们研究了与 SITS 相关的三个重要挑战。首先，我们展示如何修改查询优化器以利用 SIT 提供的附加统计信息，而不显着增加优化时间。其次，我们研究了创建 SIT 的一系列替代方案，这些方案平衡了构造效率和所得估算器的准确性。第三，我们提出了推荐一组小但非常有益的 SIT 的技术，以在数据库系统中针对给定的查询工作负载具体化。总之，我们解决了启用 SIT 进行优化的主要障碍，即构建哪些 SIT、如何构建它们以及如何在优化期间利用它们。总体而言，SIT 构成了一种处理复杂数据关联的基础良好的方法，并对关系数据库系统的效率产生积极影响。
The query optimizer is the component in a relational database system that identifies efficient execution plans for input queries. Modern optimizers generally explore many alternative query plans in a cost-based manner. Specifically, the resource consumption and associated cost of each candidate plan is estimated, and the plan with the least expected cost is chosen for execution. The cost estimation for a plan depends on several factors, including resource availability during execution, the specific operators that compose the plan, and the size of intermediate results that would be generated during the plan execution. Among these factors, the intermediate-result size (or cardinality) estimation is the main source of inaccuracies during optimization: cardinality estimation typically relies on several simplifying assumptions that often do not hold in practice. Optimizers then sometimes base their decisions on inaccurate information and produce low-quality execution plans. To address this limitation, in this thesis we introduce the concept of SITS, which are statistics built on query expressions. SITS directly and accurately model intermediate results in a query execution plan, and therefore avoid error-prone simplifying assumptions during cardinality estimation. If optimizers have appropriate SITS available during optimization, the resulting query plans can be dramatically better than otherwise. Although SITs are a fairly simple concept, challenging problems need to be addressed before SITs can be seamlessly integrated into modern relational database systems. In this thesis we study three important challenges associated with SITS. First, we show how to modify query optimizers to exploit the additional statistical information provided by SITs without significantly increasing optimization time. Second, we study a spectrum of alternatives to create SITs, which balance efficiency of construction and accuracy of the resulting estimators. Third, we present techniques to recommend a small but highly beneficial set of SITs to materialize in a database system for a given query workload. In summary, we address the main obstacles for enabling SITs for optimization, namely which SITs to build, how to build them, and how to exploit them during optimization. Overall, SITs constitute a well-founded approach for dealing with complex data correlations, and positively impact the efficiency of relational database systems.