公开(公告)号：US5548758A

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

申请号：US463968

申请日：1995-06-05

申请人： Mir H. Pirahesh ,  Ting Y. Leung ,  Guy M. Lohman ,  Eugene J. Shekita ,  David E. Simmen

发明人： Mir H. Pirahesh ,  Ting Y. Leung ,  Guy M. Lohman ,  Eugene J. Shekita ,  David E. Simmen

IPC分类号： G06F17/30

CPC分类号： G06F17/30454 ,  Y10S707/99932 ,  Y10S707/99935

摘要： A method and apparatus for optimizing SQL queries in a relational database management system uses early-out join transformations. An early-out join comprises a many-to-one existential join, wherein the join scans an inner table for a match for each row of the outer table and terminates the scan for each row of the outer table when a single match is found in the inner table. To transform a many-to-many join to an early-out join, the query must include a requirement for distinctiveness, either explicitly or implicitly, in one or more result columns for the join operation. Distinctiveness can be specified using the DISTINCT keyword in the SELECT clause or can be implied from the predicates present in the query. The early-out join transformation also requires that no columns of the inner table be referenced after the join, or if an inner table column is referenced after the join, that each referenced column be "bound". A referenced column can be bound in one of three ways: (1) an inner table column can be bound to a constant through an equality predicate, (2) an inner table column can be bound to an outer table column, or (3) an inner table column can be bound to a correlated value, wherein the correlated value originates outside the query block. In all three cases, an inner table column can be bound through the transitivity of equality predicates.

摘要翻译： 用于优化关系数据库管理系统中的SQL查询的方法和装置使用早期连接变换。 早期连接包括多对一存在连接，其中，连接扫描内部表以获取外部表的每一行的匹配，并且当找到单个匹配时终止外部表的每一行的扫描 内表。 要将多对多连接转换为早期连接，查询必须在连接操作的一个或多个结果列中明确或隐式地包含独特性的要求。 可以使用SELECT子句中的DISTINCT关键字指定不同之处，也可以从查询中存在的谓词中暗示。 早期连接转换还要求在连接之后不引用内部列的列，或者如果在连接之后引用了内部列列，则每个引用的列都将被“绑定”。 引用的列可以通过三种方式之一来绑定：（1）内表列可以通过相等谓词绑定到常量，（2）内表列可绑定到外表列，或（3） 可以将内表列绑定到相关值，其中相关值起始于查询块之外。 在所有三种情况下，内表列可以通过相等谓词的传递性来约束。

公开(公告)号：US5548754A

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

申请号：US385177

申请日：1995-02-07

申请人： Mir H. Pirahesh ,  Ting Y. Leung ,  Guy M. Lohman ,  Eugene J. Shekita ,  David E. Simmen

发明人： Mir H. Pirahesh ,  Ting Y. Leung ,  Guy M. Lohman ,  Eugene J. Shekita ,  David E. Simmen

IPC分类号： G06F17/30

CPC分类号： G06F17/30454 ,  Y10S707/99932 ,  Y10S707/99935

摘要： A method and apparatus for optimizing SQL queries in a relational database management system uses early-out join transformations. An early-out join comprises a many-to-one existential join, wherein the join scans an inner table for a match for each row of the outer table and terminates the scan for each row of the outer table when a single match is found in the inner table. To transform a many-to-many join to an early-out join, the query must include a requirement for distinctiveness, either explicitly or implicitly, in one or more result columns for the join operation. Distinctiveness can be specified using the DISTINCT keyword in the SELECT clause or can be implied from the predicates present in the query. The early-out join transformation also requires that no columns of the inner table be referenced after the join, or if an inner table column is referenced after the join, that each referenced column be "bound". A referenced column can be bound in one of three ways: (1) an inner table column can be bound to a constant through an equality predicate, (2) an inner table column can be bound to an outer table column, or (3) an inner table column can be bound to a correlated value, wherein the correlated value originates outside the query block. In all three cases, an inner table column can be bound through the transitivity of equality predicates.

摘要翻译： 用于优化关系数据库管理系统中的SQL查询的方法和装置使用早期连接变换。 早期连接包括多对一存在连接，其中，连接扫描内部表以获取外部表的每一行的匹配，并且当找到单个匹配时终止外部表的每一行的扫描 内表。 要将多对多连接转换为早期连接，查询必须在连接操作的一个或多个结果列中明确或隐式地包含独特性的要求。 可以使用SELECT子句中的DISTINCT关键字指定不同之处，也可以从查询中存在的谓词中暗示。 早期连接转换还要求在连接之后不引用内部列的列，或者如果在连接之后引用了内部列列，则每个引用的列都将被“绑定”。 引用的列可以通过三种方式之一来绑定：（1）内表列可以通过相等谓词绑定到常量，（2）内表列可绑定到外表列，或（3） 可以将内表列绑定到相关值，其中相关值起始于查询块之外。 在所有三种情况下，内表列可以通过相等谓词的传递性来约束。

公开(公告)号：US5615361A

公开(公告)日：1997-03-25

申请号：US384759

申请日：1995-02-07

申请人： Ting Y. Leung ,  Mir H. Pirahesh ,  David E. Simmen ,  Lori G. Strain ,  Sanjai Tiwari

发明人： Ting Y. Leung ,  Mir H. Pirahesh ,  David E. Simmen ,  Lori G. Strain ,  Sanjai Tiwari

IPC分类号： G06F17/30

CPC分类号： G06F17/30436 ,  G06F17/30451 ,  G06F17/30454 ,  Y10S707/954 ,  Y10S707/99933

摘要： The present invention optimizes SQL queries by exploiting uniqueness properties. In identifying whether the generalized 1-tuple condition exists, the query is first analyzed to determine whether any columns referenced in a predicate of the query are bound. According to the present invention, columns may be bound to constant values or correlated columns or columns that are already bound. The bound columns, if any, are then analyzed to determine whether any of the bound columns comprise a key for its associated table. If these conditions exist, then the query satisfies the 1-tuple condition, in that it returns at most one tuple. Once the generalized 1-tuple condition has been identified to exist for the query, important query transformations can be performed for optimization purposes. These query transformations comprise the transformation of scalar subqueries into joins, or the elimination of distinctiveness requirements (i.e., DISTINCT keywords) from SELECT clauses.

摘要翻译： 本发明通过利用唯一性来优化SQL查询。 在识别广义1元组条件是否存在时，首先分析查询以确定查询谓词中引用的任何列是否被绑定。 根据本发明，列可以绑定到已经结合的常数值或相关的列或列。 然后分析绑定的列（如果有的话），以确定任何绑定列是否包含其关联表的键。 如果这些条件存在，则查询满足1元组条件，因为它最多返回一个元组。 一旦确定了查询的广义1元组条件，就可以执行重要的查询转换来进行优化。 这些查询转换包括将标量子查询转换为联接，或从SELECT子句中消除明确性要求（即DISTINCT关键字）。

公开(公告)号：US5590324A

公开(公告)日：1996-12-31

申请号：US384925

申请日：1995-02-07

申请人： Ting Y. Leung ,  Mir H. Pirahesh ,  Michelle M. Jou ,  David E. Simmen

发明人： Ting Y. Leung ,  Mir H. Pirahesh ,  Michelle M. Jou ,  David E. Simmen

IPC分类号： G06F17/30

CPC分类号： G06F17/30454 ,  G06F17/30463 ,  Y10S707/99935

摘要： A method and apparatus for optimizing SQL queries by propagating and exploiting column nullability. Column nullability is identified and propagated using a three-valued logic, wherein a column of a table can be identified nullability information is exploited to optimize query operations through transformations. In one aspect of the present invention, quantified predicates (such as ">ALL") are transformed into simple predicates involving singleton subqueries so that indexing can be exploited. In another aspect of the present invention, "is not null" predicates are generated and pushed for certain aggregate queries. In still another aspect of the present invention, intersect operations are transformed into joins. The end result is that the present invention can significantly enhance the performance of the queries.

摘要翻译： 通过传播和利用列可空性来优化SQL查询的方法和装置。 使用三值逻辑来识别和传播列可空性，其中可以识别表的列可利用性来利用信息来优化通过转换的查询操作。 在本发明的一个方面，量化谓词（例如“> ALL”）被转换成涉及单例子查询的简单谓词，以便可以利用索引。 在本发明的另一方面，“不为空”的谓词被生成并被推送用于某些聚合查询。 在本发明的另一方面，相交操作被转换为联接。 最终结果是本发明可以显着提高查询的性能。

公开(公告)号：US07007006B2

公开(公告)日：2006-02-28

申请号：US10177007

申请日：2002-06-21

申请人： Daniel C. Zilio ,  Gary G. Valentin ,  Guy M. Lohman ,  Calisto P. Zuzarte ,  Roberta J. Cochrane ,  Hamid Pirahesh ,  Markos Zaharioudakis ,  Kit Man Cheung ,  Kevin S. Beyer ,  David E. Simmen ,  Ting Y. Leung ,  Samuel S. Lightstone

发明人： Daniel C. Zilio ,  Gary G. Valentin ,  Guy M. Lohman ,  Calisto P. Zuzarte ,  Roberta J. Cochrane ,  Hamid Pirahesh ,  Markos Zaharioudakis ,  Kit Man Cheung ,  Kevin S. Beyer ,  David E. Simmen ,  Ting Y. Leung ,  Samuel S. Lightstone

IPC分类号： G06F17/30

CPC分类号： G06F17/30312 ,  Y10S707/99932 ,  Y10S707/99934 ,  Y10S707/99935

摘要： The invention herein provides method and apparatus, including software for determining a set of materialized views or indices of the contents or a subset of the contents of a database in a data processing system to be created for one or more users of the database. The method and apparatus provide method and means for evaluating a workload presented by a user to the database; evaluating the data processing system characteristics; evaluating the database characteristics; and, using the above evaluations for recommending a set of suitable materialized views or indices to the user. Another aspect of the invention, which may be used for a workload presented by a user of a database in a data processing system, provides method and apparatus, including software for determining a set of materialized views or indices of the contents or a subset of the contents of the database, by: generating a plurality of materialized view candidates from evaluation of the workload, data processing system characteristics and database characteristics; estimating statistics for the materialized view candidates such as the number of rows, row size, and column statistics; generating a plurality of potential index candidates by evaluating the workload, data processing system characteristics, database characteristics and the materialized view candidates; and, from the materialized view candidates and index candidates selecting a set of suitable materialized views and/or indices for submission to the user.

公开(公告)号：US20080222087A1

公开(公告)日：2008-09-11

申请号：US11383481

申请日：2006-05-15

申请人： Andrey Balmin ,  Tom Eliaz ,  Guy M. Lohman ,  David E. Simmen ,  Chun Zhang

发明人： Andrey Balmin ,  Tom Eliaz ,  Guy M. Lohman ,  David E. Simmen ,  Chun Zhang

IPC分类号： G06F17/30

CPC分类号： G06F16/8365

摘要： An cost based optimizer optimizes access to at least a portion of hierarchically-organized documents, such as those formatted using eXtensible Markup Language (XML), by estimating a number of results produced by the access of the hierarchically-organized documents. Estimating the number of results comprises computing the cardinality of each operator executing query language expressions and further computing a sequence size of sequences of hierarchically-organized nodes produced by the query language expressions. Access to the hierarchically-organized documents is optimized using the structure of the query expression and/or path statistics involving the hierarchically-organized data. The cardinality and the sequence size are used to calculate a cost estimation for execution of alternate query execution plans. Based on the cost estimation, an optimal query execution plan is selected from among the alternate query execution plans.

摘要翻译： 基于成本的优化器通过估计由分级组织的文档的访问产生的结果的数量来优化对至少部分分层组织的文档的访问，例如使用可扩展标记语言（XML）格式化的文档。 估计结果的数量包括计算执行查询语言表达的每个运算符的基数，并进一步计算由查询语言表达式产生的分层组织节点的序列的序列大小。 使用涉及层次组织的数据的查询表达式和/或路径统计量的结构来优化对层级组织的文档的访问。 基数和序列大小用于计算执行备用查询执行计划的成本估算。 基于成本估算，从备用查询执行计划中选择最优查询执行计划。

公开(公告)号：US5619692A

公开(公告)日：1997-04-08

申请号：US394532

申请日：1995-02-17

申请人： Timothy R. Malkemus ,  Eugene J. Shekita ,  David E. Simmen

发明人： Timothy R. Malkemus ,  Eugene J. Shekita ,  David E. Simmen

IPC分类号： G06F17/30

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

摘要： A procedure for detecting a reordering requirement in a directed record stream during query execution in a relational database processing system. The query compiler component of a relational database processing system includes procedures for building query execution plans (QEPs) for evaluation preparatory to selecting an optimal plan for execution. These plans are constructed from the bottom up using an internal graphical representation for the user query that has a number of relation nodes interconnected by directed record streams (data flows). A relational operation within each node imposes an "order requirement" on the outflow stream represented by an order requirement vector O.sub.R. The records within each directed record stream have an "order property" represented by an order property vector O.sub.P. Order detection occurs when these two vectors are compared to determine whether the order property satisfies the order requirement. Order detection by normalization (ODN) according to this invention first normalizes the two order specification vectors to remove all attributes made redundant by the effects of predicates and functional dependencies. Query execution plans constructed using ODN are found to execute an order of magnitude faster than those constructed using order detection without normalization.

摘要翻译： 一种用于在关系数据库处理系统中的查询执行期间检测定向记录流中的重新排序要求的过程。 关系数据库处理系统的查询编译器组件包括用于建立查询执行计划（QEP）的过程，用于评估准备选择最佳执行计划。 这些计划是从下到上使用内部图形表示，用于具有通过定向记录流（数据流）互连的多个关系节点的用户查询。 每个节点之间的关系操作对由订单要求向量OR表示的流出流施加“订单要求”。 每个定向记录流中的记录具有由订单属性向量OP表示的“订单属性”。 当这两个向量进行比较以确定订单属性是否满足订单要求时，发生订单检测。 根据本发明的通过归一化（ODN）的顺序检测首先对两个规格向量进行归一化，以除去由谓词和功能依赖性的影响所产生的所有属性。 发现使用ODN构建的查询执行计划的执行速度比使用没有标准化的顺序检测构建的执行计划要快一个数量级。

公开(公告)号：US06339769B1

公开(公告)日：2002-01-15

申请号：US09152551

申请日：1998-09-14

申请人： Roberta Jo Cochrane ,  George Lapis ,  Ting Yu Leung ,  Mir Hamid Pirahesh ,  Monica Sachiye Urata ,  Richard Sefton Sidle ,  David E. Simmen ,  Calisto Paul Zuzarte

发明人： Roberta Jo Cochrane ,  George Lapis ,  Ting Yu Leung ,  Mir Hamid Pirahesh ,  Monica Sachiye Urata ,  Richard Sefton Sidle ,  David E. Simmen ,  Calisto Paul Zuzarte

IPC分类号： G06F1730

CPC分类号： G06F17/30457 ,  Y10S707/99932 ,  Y10S707/99933 ,  Y10S707/99934 ,  Y10S707/99945

摘要： A method, apparatus, and article of manufacture for optimizing database queries using a materialized view for a table referenced in the query, wherein the materialized view has different properties than the referenced table. The materialized view may be replicated across multiple processors of the computer system, so that some or all of the query can be executed in a local fashion wherein there is no data movement required to perform the operations. The materialized view also may be partitioned across multiple processors of the computer system using a different partitioning key than the referenced table. The materialized view may be a vertical and/or horizontal subset of the table, so that only selected columns and/or tuples from the table are present therein. Columns may be added to the materialized view to contain pre-computed results of complex expressions, and indices may be created on the columns of the materialized view.

摘要翻译： 使用查询中引用的表的实例化视图优化数据库查询的方法，装置和制品，其中物化视图具有与所引用的表不同的属性。 实体化视图可以复制在计算机系统的多个处理器上，使得可以以本地方式执行部分或全部查询，其中不存在执行操作所需的数据移动。 实体化视图还可以使用与参考表不同的分区键在计算机系统的多个处理器上分区。 实例化视图可以是表的垂直和/或水平子集，使得仅在表中存在所选择的列和/或元组。 可以将列添加到物化视图以包含复合表达式的预计算结果，并且可以在物化视图的列上创建索引。

公开(公告)号：US6092062A

公开(公告)日：2000-07-18

申请号：US885073

申请日：1997-06-30

申请人： Guy Maring Lohman ,  Eugene Jon Shekita ,  David E. Simmen ,  Monica Sachiye Urata

发明人： Guy Maring Lohman ,  Eugene Jon Shekita ,  David E. Simmen ,  Monica Sachiye Urata

IPC分类号： G06F17/30

CPC分类号： G06F17/30463 ,  Y10S707/99932 ,  Y10S707/99933 ,  Y10S707/99934 ,  Y10S707/99935 ,  Y10S707/99944

摘要： A relational data base management system includes a query processor that uses a query operator partition property to perform QEP pruning and to ensure that data input to a query operator is partitioned appropriately for the operation. The partition property indicates the group of network nodes across which a table is distributed. The query processor also makes use of partition classes that are designated "interesting classes" to perform preoptimization planning and query pruning, and to perform look-ahead partitioning based on partition classes that are identified as being of interest to future operations, thereby more efficiently evaluating complex query statements in an MPP, shared-nothing environment.

摘要翻译： 关系数据库管理系统包括一个查询处理器，该查询处理器使用查询运算符分区属性执行QEP修剪，并确保输入到查询运算符的数据被适当地分配给操作。 分区属性指示分配表的网络节点组。 查询处理器还利用被指定为“有趣类”的分区类来执行优化前规划和查询修剪，并且基于被识别为未来操作感兴趣的分区类执行先行分区，从而更有效地评估 MPP中的复杂查询语句，无共享环境。

公开(公告)号：US07783625B2

公开(公告)日：2010-08-24

申请号：US11256440

申请日：2005-10-21

申请人： David E. Simmen

发明人： David E. Simmen

IPC分类号： G06F7/00

CPC分类号： G06F17/30463

摘要： Data in materialized query tables (MQTs) are used as statistics for determining the optimal execution plan for a query. When an MQT is defined, it is examined to determine whether its data provides statistics for determining an optimal execution plan for a query. If so, then the MQT is identified, in the RDBMS, as a source for statistics. Information needed to exploit the MQT data as statistics is cataloged in the RDBMS. This information includes a characterization of the type of statistics provided by the MQT, the table and column distributions represented by those statistics, and a query for later retrieving relevant data from the MQT during the query optimization process. When a query is accepted for execution, the cataloged relevant information about MQTs is examined to determine whether an MQT exists that provides statistics relevant to optimization of the query. If such an MQT exists, then the relevant data is retrieved from the MQT using the cataloged query. Using the retrieved statistics, an optimal execution plan may be determined for the query.

摘要翻译： 物化查询表（MQT）中的数据用作确定查询的最佳执行计划的统计信息。 当定义MQT时，将对其进行检查以确定其数据是否提供用于确定查询的最佳执行计划的统计信息。 如果是这样，则在RDBMS中将MQT标识为统计信息源。 在RDBMS中编制统计数据来利用MQT数据所需的信息。 该信息包括由MQT提供的统计信息类型的表征，由这些统计信息表示的表和列分布以及用于稍后在查询优化过程中从MQT检索相关数据的查询。 当查询被接受执行时，将检查有关MQT的编目相关信息，以确定是否存在提供与查询优化相关的统计信息的MQT。 如果存在这样的MQT，则使用编目查询从MQT检索相关数据。 使用检索的统计信息，可以为查询确定最佳执行计划。