公开(公告)号：US20070226178A1

公开(公告)日：2007-09-27

申请号：US11388934

申请日：2006-03-24

申请人： Stephan Ewen ,  Holger Kache ,  Guy Lohman ,  Volker Markl ,  Vijayshankar Raman

发明人： Stephan Ewen ,  Holger Kache ,  Guy Lohman ,  Volker Markl ,  Vijayshankar Raman

IPC分类号： G06F17/30

CPC分类号： G06F17/30442 ,  Y10S707/99953

摘要： A method for predictable query execution through early materialization is provided. The method deals with the problem of cardinality misestimation in query execution plans, by pre-executing sub-plans on a query execution plan that have questionable estimates and collecting statistics on the output of these sub-plans. If needed, the overall query execution plan is changed in light of these statistics, before optimizing and executing the remainder of the query.

摘要翻译： 提供了一种通过早期实现来预测查询执行的方法。 该方法处理查询执行计划中基数误判的问题，预先执行查询执行计划的子计划，并对这些子计划的输出进行统计。 如果需要，在优化和执行查询的其余部分之前，根据这些统计信息更改整体查询执行计划。

公开(公告)号：US20070226186A1

公开(公告)日：2007-09-27

申请号：US11389596

申请日：2006-03-24

申请人： Stephan Ewen ,  Holger Kache ,  Volker Markl ,  Vijayshankar Raman

发明人： Stephan Ewen ,  Holger Kache ,  Volker Markl ,  Vijayshankar Raman

IPC分类号： G06F17/30

CPC分类号： G06F17/30463

摘要： A way for progressively refining a query execution plan during query execution in a federated data system is provided. Re-optimization constraints are placed in the query execution plan during query compilation. When a re-optimization constraint is violated during query execution, a model of the query execution plan is refined using a partially executed query to form a new query execution plan. The new query execution plan is compiled. The compiled new query execution plan is executed.

摘要翻译： 提供了一种在联合数据系统中查询执行期间逐步完善查询执行计划的方法。 在查询编译期间，重新优化约束被放置在查询执行计划中。 当在查询执行期间违反重新优化约束时，使用部分执行的查询来改进查询执行计划的模型以形成新的查询执行计划。 新的查询执行计划被编译。 执行编译的新查询执行计划。

公开(公告)号：US07490110B2

公开(公告)日：2009-02-10

申请号：US11388934

申请日：2006-03-24

申请人： Stephan Eberhard Ewen ,  Holger Kache ,  Guy Maring Lohman ,  Volker Gerhard Markl ,  Vijayshankar Raman

发明人： Stephan Eberhard Ewen ,  Holger Kache ,  Guy Maring Lohman ,  Volker Gerhard Markl ,  Vijayshankar Raman

IPC分类号： G06F17/30

CPC分类号： G06F17/30442 ,  Y10S707/99953

摘要： A method for predictable query execution through early materialization is provided. The method deals with the problem of cardinality misestimation in query execution plans, by pre-executing sub-plans on a query execution plan that have questionable estimates and collecting statistics on the output of these sub-plans. If needed, the overall query execution plan is changed in light of these statistics, before optimizing and executing the remainder of the query.

摘要翻译： 提供了一种通过早期实现来预测查询执行的方法。 该方法处理查询执行计划中基数误判的问题，预先执行查询执行计划的子计划，并对这些子计划的输出进行统计。 如果需要，在优化和执行查询的其余部分之前，根据这些统计信息更改整体查询执行计划。

公开(公告)号：US07877381B2

公开(公告)日：2011-01-25

申请号：US11389596

申请日：2006-03-24

申请人： Stephan Eberhard Ewen ,  Holger Kache ,  Volker Gerhard Markl ,  Vijayshankar Raman

发明人： Stephan Eberhard Ewen ,  Holger Kache ,  Volker Gerhard Markl ,  Vijayshankar Raman

IPC分类号： G06F7/00 ,  G06F17/00

CPC分类号： G06F17/30463

摘要： A way for progressively refining a query execution plan during query execution in a federated data system is provided. Re-optimization constraints are placed in the query execution plan during query compilation. When a re-optimization constraint is violated during query execution, a model of the query execution plan is refined using a partially executed query to form a new query execution plan. The new query execution plan is compiled. The compiled new query execution plan is executed.

摘要翻译： 提供了一种在联合数据系统中查询执行期间逐步完善查询执行计划的方法。 在查询编译期间，重新优化约束被放置在查询执行计划中。 当在查询执行期间违反重新优化约束时，使用部分执行的查询来改进查询执行计划的模型以形成新的查询执行计划。 新的查询执行计划被编译。 执行编译的新查询执行计划。

公开(公告)号：US20050267866A1

公开(公告)日：2005-12-01

申请号：US10855609

申请日：2004-05-28

申请人： Volker Markl ,  Vijayshankar Raman

发明人： Volker Markl ,  Vijayshankar Raman

IPC分类号： G06F7/00 ,  G06F17/30

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

摘要： “Determining Validity Ranges of Query Plans Based on Suboptimality” A method for approximating a validity range for a domain of cardinalities of input to an optimal query plan is provided. Such a validity range is iteratively approximated using a modified Newton-Raphson method to find roots of cost functions for optimal and alternative query plans, respectively. The Newton-Raphson method is combined with a method of incrementing roots of cost functions, known as input cardinalities, such that discontinuous and non-differentiable points in cost functions are avoided. In this manner, input cardinalities remain within a domain for which a valid range can be specified. Additionally, a robustness measure is determined by a sensitivity analysis performed on an approximated validity range. Using a robustness measure provided by a sensitivity analysis and resultant validity range and, query plan sub-optimality detection is simplified, re-optimization is selectively triggered, and robustness information is provided to a system or user performing corrective actions.

摘要翻译： “确定基于次优性的查询计划的有效范围”提供了一种近似有效范围的方法，该方法用于将输入到基本查询计划的基数的域的范围近似。 这种有效范围使用修正的牛顿 - 拉夫逊方法迭代近似，以分别找到最优和替代查询计划的成本函数的根。 Newton-Raphson方法与增加成本函数的根的方法相结合，称为输入基数，从而避免了成本函数中的不连续和不可微性的点。 以这种方式，输入基数保持在可以指定有效范围的域内。 另外，通过对近似有效范围进行的灵敏度分析来确定鲁棒性度量。 使用由灵敏度分析和合成有效范围提供的鲁棒性度量，并且简化了查询计划亚最优检测，重新优化被选择性地触发，并且向执行校正动作的系统或用户提供鲁棒性信息。

公开(公告)号：US20050097078A1

公开(公告)日：2005-05-05

申请号：US10698828

申请日：2003-10-31

申请人： Guy Lohman ,  Marki Volker ,  Mir Pirahesh ,  Vijayshankar Raman ,  David Simmen

发明人： Guy Lohman ,  Marki Volker ,  Mir Pirahesh ,  Vijayshankar Raman ,  David Simmen

IPC分类号： G06F7/00 ,  G06F17/30

CPC分类号： G06F17/30979 ,  Y10S707/99931 ,  Y10S707/99932 ,  Y10S707/99933 ,  Y10S707/99934 ,  Y10S707/99935

摘要： A method, system, and computer program product to make query processing more robust in the face of optimization errors. The invention validates the statistics and assumptions used for compiling a query as the query is executed and, when necessary, progressively re-optimizes the query in mid-execution based on the knowledge learned during its partial execution. The invention selectively places a number of CHECK operators in a query execution plan to validate the optimizer's cardinality estimates against actual cardinalities. Errors beyond a threshold trigger re-optimization, and the optimizer decides whether the old plan is still optimal and whether to re-use previously computed results. The invention addresses arbitrary SQL queries whose plans can contain sub-queries, updates, trigger checking, and view maintenance operations. The invention can handle concurrent update transactions or updates of common sub-expressions in a query execution plan without compromising consistency and isolation as locking information is tied to the record ID.

摘要翻译： 一种方法，系统和计算机程序产品，使查询处理在面对优化错误时更加鲁棒。 本发明验证了在执行查询时用于编译查询的统计和假设，并且在必要时，根据在其部分执行期间学到的知识，在中间执行中逐渐重新优化查询。 本发明选择性地将多个CHECK运算符放置在查询执行计划中以根据实际基数验证优化器的基数估计。 超出阈值的错误触发重新优化，优化器决定旧计划是否仍然最优，以及是否重新使用先前计算的结果。 本发明解决任意SQL查询，其计划可以包含子查询，更新，触发器检查和查看维护操作。 本发明可以处理查询执行计划中的并发更新事务或公用子表达式的更新，而不会在锁定信息与记录ID相关联的情况下不影响一致性和隔离。

公开(公告)号：US09069810B2

公开(公告)日：2015-06-30

申请号：US13558178

申请日：2012-07-25

申请人： Min-Soo Kim ,  Lin Qiao ,  Vijayshankar Raman ,  Eugene J. Shekita

发明人： Min-Soo Kim ,  Lin Qiao ,  Vijayshankar Raman ,  Eugene J. Shekita

IPC分类号： G06F17/30 ,  G06F12/08

CPC分类号： G06F17/3033 ,  G06F12/0802 ,  G06F17/30097 ,  G06F17/30109 ,  G06F17/30864 ,  G06F2212/1044 ,  G06F2212/465

摘要： System, method and computer program products for storing data by computing a plurality of hash functions of data values in a data item, and determining a corresponding memory location for one of the plurality of hash functions of data values in the data item. Each memory location is of a cacheline size wherein a data item is stored in a memory location. Each memory location can store a plurality of data items. A key portion of all data items is contiguously stored within the memory location, and a payload portion is contiguously stored within the memory location. Payload portions are packed as bit-aligned in a fixed-sized memory location, comprising a bucket in a bucketized hash table, each bucket sized to store multiple key portions and payload portions that are packed as bit-aligned in a fixed-sized bucket. Corresponding key portions are stored as compressed keys in said fixed-sized bucket.

摘要翻译： 用于通过计算数据项中的数据值的多个散列函数来存储数据的系统，方法和计算机程序产品，以及确定数据项中数据值的多个哈希函数之一的相应存储器位置。 每个存储器位置具有高速缓存行大小，其中数据项被存储在存储器位置中。 每个存储器位置可以存储多个数据项。 所有数据项的关键部分被连续地存储在存储器位置内，并且有效载荷部分被连续地存储在存储器位置内。 有效载荷部分在固定大小的存储器位置中以比特对齐的方式打包，包括桶形哈希表中的桶，每个桶的大小设置为存储多个密钥部分和在固定大小的桶中以比特排列方式打包的有效载荷部分。 对应的密钥部分作为压缩密钥存储在所述固定大小的桶中。

公开(公告)号：US08862571B2

公开(公告)日：2014-10-14

申请号：US13537665

申请日：2012-06-29

申请人： Ronald J. Barber ,  Lin Qiao ,  Vijayshankar Raman ,  Richard S. Sidle

发明人： Ronald J. Barber ,  Lin Qiao ,  Vijayshankar Raman ,  Richard S. Sidle

IPC分类号： G06F7/00

CPC分类号： G06F17/30315 ,  G06F17/30463

摘要： Embodiments of the present invention provide query processing for column stores by accumulating table record attributes during application of query plan operators on a table. The attributes and associated attribute values are compacted when said attribute values are to be consumed for an operation in the query plan, during the execution of the query plan. Table column record values are materialized late in query plan execution.

公开(公告)号：US08856103B2

公开(公告)日：2014-10-07

申请号：US13587377

申请日：2012-08-16

申请人： Ronald J. Barber ,  Lin Qiao ,  Vijayshankar Raman ,  Richard S. Sidle

发明人： Ronald J. Barber ,  Lin Qiao ,  Vijayshankar Raman ,  Richard S. Sidle

IPC分类号： G06F7/00

CPC分类号： G06F17/30315 ,  G06F17/30463

摘要： Embodiments of the present invention provide query processing for column stores by accumulating table record attributes during application of query plan operators on a table. The attributes and associated attribute values are compacted when said attribute values are to be consumed for an operation in the query plan, during the execution of the query plan. Table column record values are materialized late in query plan execution.

摘要翻译： 本发明的实施例通过在表上的查询计划操作符应用期间累加表记录属性来提供列存储的查询处理。 在执行查询计划期间，当查询计划中的操作要使用所述属性值时，属性和关联的属性值将被压缩。 表列记录值在查询计划执行时间较晚。

公开(公告)号：US08676865B2

公开(公告)日：2014-03-18

申请号：US12123598

申请日：2008-05-20

申请人： Wei Han ,  Lin Qiao ,  Vijayshankar Raman

发明人： Wei Han ,  Lin Qiao ,  Vijayshankar Raman

IPC分类号： G06F7/00 ,  G06F17/30

CPC分类号： G06F17/30958

摘要： A query processing method intersects two or more unsorted lists based on a conjunction of predicates. Each list comprises a union of multiple sorted segments. The method performs lazy segment merging and an adaptive n-ary intersecting process. The lazy segment merging comprises starting with each list being a union of completely unmerged segments, such that lookups into a given list involve separate lookups into each segment of the given list. The method intersects the lists according to the predicates while performing the lazy segment merging, such that the lazy segment merging reads in only those portions of each segment that are needed for the intersecting. As the intersecting proceeds and the lookups are performed, the intersecting selectively merges the segments together, based on a cost-benefit analysis of the cost of merging compared to the benefit produced by reducing a number of lookups.

摘要翻译： 查询处理方法基于谓词的连接与两个或多个未排序的列表相交。 每个列表包括多个排序段的并集。 该方法执行延迟段合并和自适应n元相交处理。 懒惰段合并包括从每个列表开始，这些列是完全未合并的段的并集，使得到给定列表中的查找涉及到给定列表的每个段的单独查找。 该方法在执行延迟段合并时根据谓词与列表相交，使得懒惰段合并仅读取相交所需的每个段的那些部分。 当相交进行和查找被执行时，相交的选择性地将段合在一起，基于与合并成本的成本效益分析相比，通过减少多个查找产生的收益。