公开(公告)号：US06330552B1

公开(公告)日：2001-12-11

申请号：US09162638

申请日：1998-09-28

申请人： Christopher M. Farrar ,  Harry A. Leslie ,  Pedro Celis ,  Diana L. Shak ,  Jay H. Vaishnav ,  Michael J. Skarpelos

发明人： Christopher M. Farrar ,  Harry A. Leslie ,  Pedro Celis ,  Diana L. Shak ,  Jay H. Vaishnav ,  Michael J. Skarpelos

IPC分类号： G06F1760

CPC分类号： G06Q10/04 ,  G06Q30/0283 ,  Y10S707/99931 ,  Y10S707/99932

摘要： A method and apparatus is disclosed for accurately estimating the cost of a database query, including the total computer resources used and estimated elapsed time for the production of a first row and last row of an operator involved in the query and/or the total resources used and elapsed time for returning the overall response to a database query. The method and apparatus accurately accounts for resources used and elapsed time associated with blocking operators, such as sorts and hash joins, which cannot produce a first row until they have completed their operations.

摘要翻译： 公开了一种用于精确估计数据库查询的成本的方法和装置，包括所使用的总计算机资源和用于生成涉及查询的运营商的第一行和最后一行的估计经过时间和/或所使用的总资源 以及将整体响应返回到数据库查询的时间。 该方法和装置准确地说明了与阻塞运算符（例如排序和散列连接）相关联的资源所用的资源和经过的时间，在完成其操作之前不能产生第一行。

公开(公告)号：US06263345B1

公开(公告)日：2001-07-17

申请号：US09162245

申请日：1998-09-28

申请人： Christopher M. Farrar ,  Harry A. Leslie ,  Pedro Celis ,  Diana L. Shak

发明人： Christopher M. Farrar ,  Harry A. Leslie ,  Pedro Celis ,  Diana L. Shak

IPC分类号： G06F1730

CPC分类号： G06F17/30454 ,  G06F17/30463 ,  G06F17/30536 ,  Y10S707/954 ,  Y10S707/966 ,  Y10S707/99932 ,  Y10S707/99933 ,  Y10S707/99945

摘要： The invention provides a mechanism for using statistics, in connection with various database query cost modeling techniques, to more accurately estimate the number of rows and UECs that will be produced by relational operators and predicates in database systems. The ability to accurately estimate the number of rows and UECs returned by a relational operator and/or a predicate is fundamental to computing the cost of a query execution plan. This, in turn, drives the optimizer's ability to select the query plan best suited for the desired performance goal. According to the present invention, histogram statistics are synthesized bottom up from the leaf nodes to the root node of a query tree. Given input statistics in the form of histograms for each operand of a relational operator or predicate, the present inventive method and apparatus merge the input statistics in a way that it simulates the effects of the run time operator on the actual data, so as to produce a predicted row count and UEC for each histogram interval representative of the data that actually will be produced by each such operator or predicate in the query tree. A database query optimizer may use these statistics to select and implement an optimal query plan.

摘要翻译： 本发明提供了一种使用统计学的机制，结合各种数据库查询成本建模技术来更精确地估计将由数据库系统中的关系运算符和谓词产生的行数和UEC。 精确估计关系运算符和/或谓词返回的行数和UEC的能力是计算查询执行计划成本的基础。 这反过来又推动了优化器选择最适合于所需性能目标的查询计划的能力。 根据本发明，从查询树的叶节点到根节点从下向上合成直方图统计量。 给定关系运算符或谓词的每个操作数的直方图形式的输入统计量，本发明的方法和装置以输入统计的方式合并输入统计量，以便模拟运行时间算子对实际数据的影响，从而产生 每个直方图间隔的预测行数和UEC代表实际将由查询树中的每个这样的运算符或谓词产生的数据。 数据库查询优化器可以使用这些统计信息来选择和实现最优查询计划。

公开(公告)号：US06438741B1

公开(公告)日：2002-08-20

申请号：US09283309

申请日：1999-03-31

申请人： Awny K. Al-omari ,  Hansjorg Zeller ,  Diana L. Shak

发明人： Awny K. Al-omari ,  Hansjorg Zeller ,  Diana L. Shak

IPC分类号： G06F945

CPC分类号： G06F17/30463 ,  Y10S707/99932

摘要： The present invention reduces the compile time in a top-down rule based system by identifying the complexity of a query prior to applying a rule to an expression. If the complexity of the query is above a threshold, the present invention determines whether the rule should be applied based upon several factors including the type of rule and the position of the node in the search space. Those rules that need not be applied are randomly pruned at a determined rate that prevents search space explosion and prevents the elimination of large contiguous portions of the search space. Pruned rules are not applied, while those rules that are not pruned are applied.

摘要翻译： 本发明通过在将规则应用于表达之前识别查询的复杂度来减少在自上而下的基于规则的系统中的编译时间。 如果查询的复杂度高于阈值，则本发明基于包括规则的类型和搜索空间中节点的位置的若干因素确定是否应该应用规则。 不需要应用的那些规则将以确定的速率随机修剪，从而防止搜索空间爆炸，并防止消除搜索空间的大连续部分。 修剪的规则不被应用，而不修剪的规则被应用。