公开(公告)号：US09626398B2

公开(公告)日：2017-04-18

申请号：US13477789

申请日：2012-05-22

Applicant: Goetz Graefe ,  Harumi Kuno ,  Hideaki Kimura

Inventor： Goetz Graefe ,  Harumi Kuno ,  Hideaki Kimura

IPC: G06F17/30

CPC classification number: G06F17/30327

Abstract: A method of implementing a tree data structure comprises creating a parent and child relationship between a first node and a second node, in which the first node and second node are at the same hierarchical level of the tree data structure, and maintaining only one incoming pointer for each of the nodes in the tree data structure at all times. A tree data structure in which each node in the tree data structure has a single incoming pointer, and in which the tree data structure comprises a pointer directed to a local overflow node from a node at the same hierarchical level as the local overflow node.

公开(公告)号：US09396227B2

公开(公告)日：2016-07-19

申请号：US13434744

申请日：2012-03-29

Applicant: Goetz Graefe ,  Harumi Kuno

Inventor： Goetz Graefe ,  Harumi Kuno

IPC: G06F17/30

CPC classification number: G06F17/30362

Abstract: A system, method, and non-transitory computer readable medium for providing controlled lock violation for data transactions are presented. The system includes a processor for executing a first data transaction and a second data transaction, the first and second data transactions operating on a plurality of data resources. A controlled lock violation module grants to the second transaction a conflicting lock to a data resource locked by the first transaction with a lock, the conflicting lock granted to the second transaction while the first transaction holds its lock. The controlled lock violation module can be applied to distributed transactions in a two-phase commit and to canned transactions.

Abstract translation: 提出了一种用于为数据交易提供受控锁定冲突的系统，方法和非暂时性计算机可读介质。 该系统包括用于执行第一数据事务和第二数据事务的处理器，第一和第二数据事务在多个数据资源上运行。 控制的锁定违规模块向第二个事务授予对具有锁定的第一事务锁定的数据资源的冲突锁定，当第一个事务保持其锁定时，冲突锁被授予第二个事务。 受控锁定违规模块可以应用于两阶段提交和罐头交易中的分布式事务。

公开(公告)号：US09298761B2

公开(公告)日：2016-03-29

申请号：US12433418

申请日：2009-04-30

Applicant: Goetz Graefe

Inventor： Goetz Graefe

IPC: G06F7/00 ,  G06F17/30

CPC classification number: G06F17/30327

Abstract: A method for implementing adaptive merging in database indexes includes selecting a key range from a database query having a range predicate and searching a database for data matching the key range. The data matching the key range is merged to form a collected dataset which is stored for future retrieval. A method for optimizing B-tree representation of a database using actual queries is also provided.

Abstract translation: 一种用于在数据库索引中实现自适应合并的方法包括从具有范围谓词的数据库查询中选择密钥范围，并在数据库中搜索与密钥范围匹配的数据。 匹配关键范围的数据被合并以形成收集的数据集，存储以供将来检索。 还提供了使用实际查询优化数据库的B树表示的方法。

公开(公告)号：US20130054567A1

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

申请号：US13218898

申请日：2011-08-26

Applicant: Goetz Graefe

Inventor： Goetz Graefe

IPC: G06F17/30

CPC classification number: G06F17/30463

Abstract: There is provided a computer-implemented method of dynamically reordering operations in a query plan. An exemplary method comprises processing a first set of tuples according to a first operation. The query plan is pipelined and specifies that the first operation generates input for a second operation. The query plan further specifies that the second operation is executed after the first operation. The computer-implemented method further includes determining that the second operation is to precede the first operation based on a specified policy. The computer-implemented method further includes executing the second operation for a second set of tuples before executing the first operation for the second set of tuples. The second operation generates an input for the first operation. The first operation is executed after the second operation.

Abstract translation: 提供了一种在查询计划中动态重新排序操作的计算机实现的方法。 一种示例性方法包括根据第一操作来处理第一组元组。 查询计划是流水线的，并指定第一个操作为第二个操作生成输入。 查询计划还指定在第一操作之后执行第二操作。 计算机实现的方法还包括基于指定的策略来确定第二操作在第一操作之前。 计算机实现的方法还包括在为第二组元组执行第一操作之前对第二组元组执行第二操作。 第二操作产生用于第一操作的输入。 在第二操作之后执行第一操作。

公开(公告)号：US20120254199A1

公开(公告)日：2012-10-04

申请号：US13077460

申请日：2011-03-31

Applicant: Harumi Kuno ,  Goetz Graefe

Inventor： Harumi Kuno ,  Goetz Graefe

IPC: G06F17/30

CPC classification number: G06F7/32

Abstract: A merge optimization system to optimize a run merge process for runs including keys from a data source. The system may include a run generation module to generate a run of the keys in a predetermined order. The system may further include a key characterization module to characterize a distribution of the keys across the run at run generation time, and a run merge module executed by a computer system to selectively associate the runs based on the characterization.

Abstract translation: 合并优化系统，用于优化运行合并进程，包括数据源中的密钥。 系统可以包括运行生成模块，以按预定顺序生成密钥的运行。 系统还可以包括密钥表征模块，用于表征在运行生成时间的运行中的密钥的分布，以及由计算机系统执行的运行合并模块，以基于表征选择性地关联运行。

公开(公告)号：US20120254171A1

公开(公告)日：2012-10-04

申请号：US13075570

申请日：2011-03-30

Applicant: Goetz Graefe ,  Harumi Kuno

Inventor： Goetz Graefe ,  Harumi Kuno

IPC: G06F17/30

CPC classification number: G06F17/30 ,  G06F7/24

Abstract: A computer executed method of exploiting correlations between original and desired data sequences during run generation comprises, with a processor, adding a number of data values from a data source to a first memory device, the first memory device defining a workspace, determining whether the data values within the workspace should be output in ascending or descending order for a number of runs, and writing a number of the data values as a run to a second memory device in the determined order.

Abstract translation: 一种在运行生成期间利用原始数据序列与期望数据序列之间的相关性的计算机执行方法包括：利用处理器，将来自数据源的多个数据值添加到第一存储器设备，所述第一存储器设备定义工作空间，确定数据 工作空间中的值应当以多个运行的升序或降序输出，并以确定的顺序将多个数据值作为运行写入第二个存储器件。

公开(公告)号：US08108400B2

公开(公告)日：2012-01-31

申请号：US12493189

申请日：2009-06-27

Applicant: Goetz Graefe

Inventor： Goetz Graefe

IPC: G06F7/00

CPC classification number: G06F17/30321

Abstract: A segment encompasses a number of segment records less than the total number of records of a database. The segment records have values for a field of the database. Lowest and highest values of the segment records for the field, and a bitmap for the segment, can be determined and stored. Selected bits of the bitmap each correspond to a value for the field. Each selected bit is set to one where at least one segment record has the value to which the bit corresponds. An index relating to just the segment records can be determined and stored. The lowest and highest values, and the bitmap, are adapted to permit determination of whether the segment has to be loaded into memory to locate records that satisfy a query. The index is adapted to permit searching of the segment records after the segment has been loaded into the memory.

Abstract translation: 分段包含小于数据库记录总数的段记录。 段记录具有数据库字段的值。 可以确定和存储字段的段记录的最低和最高值以及段的位图。 位图的选定位各自对应于该字段的值。 每个选择的位被设置为一个，其中至少一个段记录具有该位对应的值。 可以确定和存储与仅仅片段记录有关的索引。 最低和最高值以及位图适用于允许确定该段是否必须加载到存储器中以定位满足查询的记录。 该索引适于在片段已经被加载到存储器中之后允许搜索片段记录。

公开(公告)号：US20110138145A1

公开(公告)日：2011-06-09

申请号：US13027938

申请日：2011-02-15

Applicant: Michael M. Magruder ,  David Detlefs ,  John Joseph Duffy ,  Goetz Graefe ,  Vinod K. Grover

Inventor： Michael M. Magruder ,  David Detlefs ,  John Joseph Duffy ,  Goetz Graefe ,  Vinod K. Grover

IPC: G06F12/00

CPC classification number: G06F9/467 ,  G06F17/30356 ,  G06F17/30359 ,  G06F17/30362

Abstract: Various technologies and techniques are disclosed for supporting parallel nested transactions in a transactional memory system. Multiple closed nested transactions are created for a single parent transaction, and the closed nested transactions are executed concurrently as parallel nested transactions. Various techniques are used to ensure effects of the parallel nested transactions are hidden from other transactions outside the parent transaction until the parent transaction commits. For example, versioned write locks are used with parallel nested transactions. When a transactional memory word changes from a write lock to a versioned write lock, an entry is made in a global versioned write lock map to store a pointer to a write log entry that the versioned write lock replaced. When the versioned write lock is encountered during transaction processing, the global versioned write lock map is consulted to translate the versioned write lock to the pointer to the write log entry.

Abstract translation: 公开了用于支持事务存储器系统中的并行嵌套事务的各种技术和技术。 为单个父事务创建多个封闭的嵌套事务，并且封闭的嵌套事务将作为并行嵌套事务并发执行。 使用各种技术来确保并行嵌套事务对父事务之外的其他事务的影响，直到父事务提交为止。 例如，版本化的写锁与并行嵌套事务一起使用。 当事务性内存单词从写入锁定更改为版本化写入锁定时，将在全局版本化写入锁定映射中创建一个条目，以存储指向版本化写入锁定替换的写入日志条目的指针。 当在事务处理期间遇到版本化的写锁时，请参考全局版本的写入锁定映射，以将版本化的写锁定转换为写入日志条目的指针。

公开(公告)号：US20110055232A1

公开(公告)日：2011-03-03

申请号：US12461842

申请日：2009-08-26

Applicant: Goetz Graefe

Inventor： Goetz Graefe

IPC: G06F7/08 ,  G06F17/30

CPC classification number: G06F12/08

Abstract: A method, executed on a suitably programmed processor, provides for ordering records using a memory hierarchy. The memory hierarchy includes and two or more lower levels of the memory hierarchy. The method includes the steps of (a) receiving unsorted input records; (b) reading the input records in pages and writing one or more pages of the input records to the primary memory; (c) sorting the pages of input records to create a run; (d) if a size of the run exceeds primary memory capacity, moving data that just exceeds the primary memory capacity to a secondary level of the memory hierarchy; (e) repeating steps (a)-(d) until either (i) all unsorted input records have been read into primary memory and sorted, or (ii) a capacity of the secondary level of the memory hierarchy is exceeded; (f) following step (e)(ii), moving data that just exceeds the secondary memory capacity from the secondary level to a tertiary level of the memory hierarchy until the capacity of the secondary level no longer is exceeded; and (g) following either of steps (c), (e)(i), or (f), merging runs to create a merge output.

Abstract translation: 在适当编程的处理器上执行的方法使用存储器层次结构提供订购记录。 存储器层次结构包括存储器层级的两个或多个较低级别。 该方法包括以下步骤：（a）接收未排序的输入记录; （b）以页面读取输入记录，并将一个或多个输入记录页写入主存储器; （c）对输入记录的页面进行排序以创建运行; （d）如果运行的大小超过主存储器容量，则将刚刚超过主存储器容量的数据移动到存储器层次的次级; （e）重复步骤（a） - （d），直到（i）所有未排序的输入记录都已读入主存储器并排序，或（ii）超过存储器层次的次级级别的容量; （f）在步骤（e）（ii）之后，将超过辅助存储器容量的数据从次级级别移动到存储层级的高级级别，直到超过次级级别的容量不再被超过; 和（g）遵循步骤（c），（e）（i）或（f）中的任何一个，合并运行以创建合并输出。

公开(公告)号：US20100198809A1

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

申请号：US12364170

申请日：2009-02-02

Applicant: Goetz Graefe ,  Harumi Kuno ,  Janet L. Wiener

Inventor： Goetz Graefe ,  Harumi Kuno ,  Janet L. Wiener

IPC: G06F17/30

CPC classification number: G06F16/24549

Abstract: Computer-implemented systems and associated operating methods take measurements and landmarks associated with robustness maps and perform tests evaluating the robustness of a database engine's operator implementations and/or query components. The illustrative computer-implemented system comprises logic that receives one or more robustness maps of measured database system performance acquired during database execution in a predetermined range of runtime conditions and uses information from the robustness map or maps to perform regression testing wherein landmarks in the robustness maps are operated upon as a robustness bugs describing conditions under which a predetermined implementation of a database operator or query component degrades in a manner different from a predetermined expected manner.

Abstract translation: 计算机实现的系统和相关的操作方法进行与鲁棒性映射关联的测量和界标，并执行评估数据库引擎的操作员实现和/或查询组件的鲁棒性的测试。 示例性计算机实现的系统包括逻辑，其接收在预定运行时间条件范围内在数据库执行期间获取的测量数据库系统性能的一个或多个鲁棒性映射，并使用来自鲁棒性映射或映射的信息来执行回归测试，其中鲁棒性映射中的地标 被操作为描述以预定方式不同的方式降低数据库操作者或查询组件的预定实现的条件的鲁棒性错误。