公开(公告)号：US06304866B1

公开(公告)日：2001-10-16

申请号：US08884602

申请日：1997-06-27

申请人： Jyh-Herng Chow ,  John Frederick Hornibrook ,  Bruce Gilbert Lindsay ,  Geoffrey Peddle ,  Eugene Jon Shekita ,  Amit Somani ,  Surendra Kumar Verma ,  Honesty Cheng Young

发明人： Jyh-Herng Chow ,  John Frederick Hornibrook ,  Bruce Gilbert Lindsay ,  Geoffrey Peddle ,  Eugene Jon Shekita ,  Amit Somani ,  Surendra Kumar Verma ,  Honesty Cheng Young

IPC分类号： G06F1730

CPC分类号： G06F9/505 ,  G06F2209/5017 ,  Y10S707/99932 ,  Y10S707/99933

摘要： In a multiprocessing system, multiple concurrently operating task execution units are operated to perform an aggregate task by using incremental and on-demand sub-task allocation. A command is received to perform a machine-executed task divisible into multiple sub-tasks, i.e., an “aggregate task”. A granularity is then established, for dividing the aggregate task into sub-tasks. Preferably, the granularity is not too large to permit potentially uneven sub-task allocation, and not too small to incur excessive overhead in allocating sub-tasks. Having established the granularity, multiple task execution units are independently operated on-demand to sequentially self-allocate and execute sub-tasks of the aggregate tasks. Each sub-task is sized according to the established granularity. Operating “on-demand”, each task execution unit sequentially allocates and executes one sub-task at a time, then proceeding to the next unexecuted sub-task. Thus, the multiprocessing system operates like multiple people drinking water from a common glass through individual straws—although each drinker works independently, all finish simultaneously, thus completing the aggregate task as expeditiously as possible.

摘要翻译： 在多处理系统中，通过使用增量和按需子任务分配来操作多个并发操作任务执行单元来执行聚合任务。 接收到用于执行可分为多个子任务（即，“聚合任务”）的机器执行任务的命令。 然后建立粒度，将聚合任务划分为子任务。 优选地，粒度不是太大，不能允许潜在的不均匀的子任务分配，并且不太小，在分配子任务时不会产生过多的开销。 建立粒度后，多个任务执行单元按需独立运行，顺序自动分配和执行总任务的子任务。 每个子任务的大小根据建立的粒度。 每个任务执行单元按“按需”运行，一次顺序分配并执行一个子任务，然后进行到下一个未执行的子任务。 因此，多处理系统通过个人吸管，像普通玻璃饮水一样运作，虽然每个饮酒者独立工作，但是同时完成，从而尽可能快地完成总体任务。

公开(公告)号：US5671403A

公开(公告)日：1997-09-23

申请号：US367502

申请日：1994-12-30

申请人： Eugene Jon Shekita ,  Honesty Cheng Young

发明人： Eugene Jon Shekita ,  Honesty Cheng Young

IPC分类号： G06F17/30

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

摘要： A query optimizer for optimizing join queries in a relational database system by iterative application of dynamic programming (DP) to select optimal subgraph join execution plans. Unlike traditional DP optimization methods, bounds on search space time and space complexity can be established and adjusted by imposing a subgraph threshold. Each bounded subgraph is selected using a greedy heuristic (GH) hill-climbing procedure or other similarly useful technique to build a low-cost execution plan. The low-cost GH subgraph execution plan is then discarded in favor of an optimal DP subgraph execution plan selected by a dynamic programming optimizer for each subgraph identified by the bounded GH optimization process. The complexity bound may be dynamically tuned to improve execution plan quality responsive to changes in query complexity.

摘要翻译： 用于通过迭代应用动态规划（DP）来优化关系数据库系统中的连接查询以选择最佳子图连接执行计划的查询优化器。 与传统的DP优化方法不同，可以通过施加子图阈值来建立和调整搜索空间时间和空间复杂度的界限。 使用贪婪启发式（GH）爬山程序或其他类似有用的技术来选择每个有界子图，以构建低成本执行计划。 然后丢弃低成本的GH子图执行计划，以利于动态规划优化器为由有界GH优化过程识别的每个子图选择的最佳DP子图执行计划。 可以动态调整复杂性限制，以响应于查询复杂度的变化来提高执行计划质量。

公开(公告)号：US06226639B1

公开(公告)日：2001-05-01

申请号：US09158741

申请日：1998-09-22

申请人： Bruce Gilbert Lindsay ,  Sridhar Rajagopalan ,  Eugene Jon Shekita

发明人： Bruce Gilbert Lindsay ,  Sridhar Rajagopalan ,  Eugene Jon Shekita

IPC分类号： G06F1730

CPC分类号： G06F17/30501 ,  G06F17/30498 ,  Y10S707/99931 ,  Y10S707/99935

摘要： A system and method for joining a build table to a probe table in response to a query for data includes over partitioning the build table into “N” build partitions using a uniform hash function and writing the build partitions into main memory of a database computer. When the main memory becomes full, one or more partitions is selected as a victim partition to be written to disk storage, and the process continues until all build table rows or tuples have either been written into main memory or spilled to disk. Then, a packing algorithm is used to initially designate never-spilled partitions as “winners” and spilled partitions as “losers”, and then to randomly select one or more winners for prospective swapping with one or more losers. The I/O savings associated with each prospective swap is determined and if any savings would be realized, the winners are designated as losers the losers are designated as winners. The swap determination can be made multiple times, e.g., 256, after which losers are moved entirely to disk and winners are moved entirely to memory. At the end of the swapping, probe table rows associated with winner partitions are joined to rows in the winner build partitions while probe table rows associated with loser partitions are spilled to disk. Then, the loser build partitions are written to main memory for joining with corresponding probe table partitions, to undertake the requested join of the build table and probe table in an I/O- and memory-efficient manner.

摘要翻译： 响应于数据查询将构建表连接到探测表的系统和方法包括使用统一散列函数将构建表过度分割为“N”构建分区，并将构建分区写入数据库计算机的主存储器。 当主内存变满时，将选择一个或多个分区作为要写入磁盘存储器的受害分区，并且该过程继续进行，直到所有构建表行或元组都已写入主内存或溢出到磁盘。 然后，打包算法用于初始地将未分配的分区指定为“获胜者”，将分区分散为“输家”，然后随机选择一个或多个获胜者进行与一个或多个输家的潜在交换。 确定与每个预期掉期相关的I / O节省，如果实现了任何节省，则获胜者被指定为失败者被指定为赢家的输家。 交换确定可以进行多次，例如256次，之后输家完全移动到磁盘，获胜者完全移动到内存。 在交换结束时，与优胜者分区关联的探测表行将连接到优胜者构建分区中的行，而与失败分区关联的探测表行会溢出到磁盘。 然后，失败者构建分区被写入主存储器以与相应的探测表分区相连接，以I / O和存储器高效的方式承载构建表和探测表的所请求的连接。

公开(公告)号：US5960428A

公开(公告)日：1999-09-28

申请号：US919739

申请日：1997-08-28

申请人： Bruce Gilbert Lindsay ,  Guy Maring Lohman ,  Mir Hamid Pirahesh ,  Eugene Jon Shekita ,  David Everett Simmen ,  Monica Sachiye Urata

发明人： Bruce Gilbert Lindsay ,  Guy Maring Lohman ,  Mir Hamid Pirahesh ,  Eugene Jon Shekita ,  David Everett Simmen ,  Monica Sachiye Urata

IPC分类号： G06F17/30

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

摘要： Unwieldy star/join queries are performed more efficiently using a filtered fact table. Suitable queries include star/join queries with a large fact table joined with multiple subsidiary dimension tables, where indices exist over fact table join columns. The query is analyzed to prepare a query plan for the dimension table accesses. This plan is supplemented by adding nested loop join operations, where the inner table is a dimension table plan and the outer table is an index scan performed over a fact table index of the join column with the dimension table. The plan is also supplemented by filtering records resulting from the nested loop joins using a sequence of dynamic bit vectors, ultimately yielding a list of probable fact table records. The plan is further supplemented by fetching these records to construct a distilled fact which is used, instead of the large original table, to execute the query in considerably less time. If desired, the supplemented query plan and other competing approaches may studied to provide cost estimates, with the least costly approach being actually implemented.

摘要翻译： 使用已过滤的事实表，更有效地执行无故障的星号/连接查询。 合适的查询包括带有多个附属维度表的大型事实表的星号/连接查询，其中索引存在于事实表连接列上。 分析查询以准备维度表访问的查询计划。 此计划通过添加嵌套循环连接操作来补充，其中内部表是维度表计划，外部表是在具有维度表的连接列的事实表索引上执行的索引扫描。 该计划还补充了使用一系列动态位向量的嵌套循环连接过滤记录，最终产生可能的事实表记录的列表。 该计划进一步补充了通过获取这些记录来构建一个使用的蒸馏事实，而不是大的原始表，在相当短的时间内执行查询。 如果需要，可以研究补充的查询计划和其他竞争方法，以提供成本估算，最低成本的方法正在实际实施。

公开(公告)号：US6105020A

公开(公告)日：2000-08-15

申请号：US415799

申请日：1999-10-11

申请人： Bruce Gilbert Lindsay ,  Eugene Jon Shekita ,  David Everett Simmen ,  Kaarel Truuvert

发明人： Bruce Gilbert Lindsay ,  Eugene Jon Shekita ,  David Everett Simmen ,  Kaarel Truuvert

IPC分类号： G06F17/30

CPC分类号： G06F17/30466 ,  G06F17/30471 ,  Y10S707/99932 ,  Y10S707/99933

摘要： A system and method for a relational database system for identifying star joins in a query and for breaking the query down for bitmap ANDing. The fact table of the star join is located, and cycles between and within dimension tables are broken. Then, the minimal set of tables necessary to execute the star join is identified, and the dimension tables that should appear in the bitmap ANDing plan are also identified. A bitmap ANDing plan is then generated, or, if the query does not qualify for bitmap ANDing, a conventional execution plan is generated.

摘要翻译： 一种关系数据库系统的系统和方法，用于识别查询中的星形连接，并将查询中断用于位图“和”运算。 星形连接的事实表位于，尺寸表之间和内部之间的循环被破坏。 然后，确定执行星形连接所需的最小的一组表，并且还会识别出现在位图“安全”计划中的维度表。 然后生成位图“和”计划，或者如果该查询不符合位图“与”功能，则会生成常规执行计划。

公开(公告)号：US06253197B1

公开(公告)日：2001-06-26

申请号：US09167395

申请日：1998-10-06

申请人： Bruce Gilbert Lindsay ,  Eugene Jon Shekita

发明人： Bruce Gilbert Lindsay ,  Eugene Jon Shekita

IPC分类号： G06F1730

CPC分类号： G06F17/30498 ,  Y10S707/99933 ,  Y10S707/99953

摘要： A system and method for joining a build table to a probe table in response to a query for data includes executing a hash loops join of the build table and the probe table. Matched rows are joined and output when the rows match each other by satisfying a join predicate. In an outer join, unmatched rows in the probe table are joined to a NULL build table field values and output, such that all rows of the probe table are output regardless of whether they have matched rows in the build table. In an early-out join, on the other hand, a “match once” table defines the probe table and in response to a query for unique probe table outputs, the joining of a probe table row, once joined and output a first time, to any other rows in the other table is prevented regardless of whether the row might match other rows. In both the hash loops early-out join and the hash loops outer join, when the build table is larger than main memory, the roles of the build and probe tables are reversed.

摘要翻译： 响应于对数据的查询将构建表连接到探测表的系统和方法包括执行构建表和探测表的散列循环连接。 匹配的行被连接并通过满足连接谓词来匹配行时输出。 在外连接中，探测表中的不匹配的行将连接到NULL构建表字段值和输出，以便无论在构建表中是否具有匹配行，都会输出探测表的所有行。 另一方面，在早期连接中，“匹配一次”表定义探针表，并且响应于对唯一探针表输出的查询，加入探针表行，一旦连接并输出第一次， 不管该行是否与其他行匹配，都会阻止其他表中的任何其他行。 在哈希循环早期连接和散列循环外连接中，当构建表大于主内存时，构建和探测表的角色相反。

公开(公告)号：US06947945B1

公开(公告)日：2005-09-20

申请号：US09531802

申请日：2000-03-21

申请人： Michael James Carey ,  Jayavel Shanmugasundaram ,  Eugene Jon Shekita ,  Narayana Iyer

发明人： Michael James Carey ,  Jayavel Shanmugasundaram ,  Eugene Jon Shekita ,  Narayana Iyer

IPC分类号： G06F17/30

CPC分类号： G06F17/30917 ,  G06F17/30932 ,  G06F17/30941 ,  Y10S707/99943

摘要： A method for publishing relational data as XML by translating XML queries into queries against an relational database. Conversion of the relational database into an XML database is not required. Each relational table is mapped to a virtual XML document, and XML queries are issued over these virtual documents. An XML query is parsed and transformed into a language-neutral intermediate representation, which is a sequence of operations describing how the output document is derived from the underlying relational tables. The intermediate representation is then translated into an SQL query over the underlying relational tables and into instructions for a tagger. The SQL query is executed, and the SQL query results are then fed into the tagger, which follows tagger instructions to generate the marked up output.

摘要翻译： 通过将XML查询转换为关系数据库的查询，将关系数据作为XML发布的方法。 不需要将关系数据库转换为XML数据库。 每个关系表映射到一个虚拟XML文档，并通过这些虚拟文档发出XML查询。 解析XML查询并将其转换为语言中立的中间表示，它是描述输出文档如何从底层关系表导出的操作序列。 然后将中间表示形式转换为基于关系表的SQL查询和标记器的指令。 执行SQL查询，然后将SQL查询结果输入到标记器中，标签器遵循标记器指令生成标记输出。

公开(公告)号：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中的复杂查询语句，无共享环境。

公开(公告)号：US07043487B2

公开(公告)日：2006-05-09

申请号：US10331739

申请日：2002-12-28

申请人： Rajasekar Krishnamurthy ,  Jayavel Shanmugasundaram ,  Eugene Jon Shekita

发明人： Rajasekar Krishnamurthy ,  Jayavel Shanmugasundaram ,  Eugene Jon Shekita

IPC分类号： G06F17/30

CPC分类号： G06F17/30595 ,  G06F17/30896 ,  Y10S707/954

摘要： A method for storing XML documents in a relational database system while exploiting XML Schema information to capture information about types, inheritance, equivalence classes, and integrity constraints in the generated relational schema, enabling efficient querying. The invention simplifies complex XML schema types, translates the simplified XML schema types into relational tables, and then stores relations corresponding to each XML element in relational table rows. The simplification includes grouping all occurrences of a given element together, assembling two or more element types into element groups if the schema indicates that elements of those element types will occur the same number of times, and applying a number of transformation rules to the element groups. The translation includes constructing a type graph from the simplified schema, building an element graph for each global element in the simplified schema from the type graph, and generating relational tables from the element graph.

摘要翻译： 一种用于在关系数据库系统中存储XML文档的方法，同时利用XML模式信息来捕获关于生成的关系模式中的类型，继承，等价类和完整性约束的信息，从而实现高效的查询。 本发明简化了复杂的XML模式类型，将简化的XML模式类型转换为关系表，然后将对应于每个XML元素的关系存储在关系表行中。 简化包括将给定元素的所有出现分组在一起，如果模式指示这些元素类型的元素将发生相同次数，并将多个变换规则应用于元素组，则将两个或多个元素类型组合到元素组中 。 翻译包括从简化模式构建类型图，从类型图构建简化模式中的每个全局元素的元素图，以及从元素图生成关系表。

公开(公告)号：US06345267B1

公开(公告)日：2002-02-05

申请号：US09517355

申请日：2000-03-02

申请人： 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分类号： G06F1730

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中的复杂查询语句，无共享环境。