公开(公告)号：US09251214B2

公开(公告)日：2016-02-02

申请号：US12756185

申请日：2010-04-08

申请人： Cristian Diaconu ,  Craig Steven Freedman ,  Per-Ake Larson ,  Michael James Zwilling

发明人： Cristian Diaconu ,  Craig Steven Freedman ,  Per-Ake Larson ,  Michael James Zwilling

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

CPC分类号： G06F17/30377 ,  G06F12/0253 ,  G06F17/30309 ,  G06F17/30501 ,  G06F17/30575 ,  G06F2212/1044

摘要： A computer system includes a memory and a processor coupled to the memory. The processor is configured to execute instructions that cause execution of an in-memory database system that includes one or more database tables. Each database table includes a plurality of rows, where data representing each row is stored in the memory. The in-memory database system also includes a plurality of indexes associated with the one or more database tables, where each index is implemented by a lock-free data structure. Update logic at the in-memory database system is configured to update a first version of a particular row to create a second version of the particular row. The in-memory database system includes a non-blocking garbage collector configured to identify data representing outdated versions of rows.

摘要翻译： 计算机系统包括存储器和耦合到存储器的处理器。 处理器被配置为执行引起执行包括一个或多个数据库表的内存中数据库系统的指令。 每个数据库表包括多行，其中表示每一行的数据被存储在存储器中。 内存中数据库系统还包括与一个或多个数据库表相关联的多个索引，其中每个索引由无锁数据结构实现。 内存数据库系统中的更新逻辑被配置为更新特定行的第一版本以创建特定行的第二版本。 内存中的数据库系统包括一个非阻塞的垃圾收集器，用于标识表示行的过时版本的数据。

公开(公告)号：US20120323970A1

公开(公告)日：2012-12-20

申请号：US13163674

申请日：2011-06-18

申请人： Per-Ake Larson ,  Donghui Zhang

发明人： Per-Ake Larson ,  Donghui Zhang

IPC分类号： G06F17/30

CPC分类号： G06F17/30949

摘要： A table update component may perform updates on a dynamic linear hash table, the updates requested by clients based on request item values. A table capacity status component may determine first capacity indicators associated with the dynamic linear hash table, based on results of the update requests. A table maintenance component may initiate lock-free merges and lock-free splits of hash table buckets associated with the dynamic linear hash table, based on initiating lock-free merges and lock-free splits of linked lists included in hash table buckets associated with the dynamic linear hash table, based on the determined first capacity indicators, the linked lists including hashed items stored in the dynamic linear hash table.

摘要翻译： 表更新组件可以在动态线性哈希表上执行更新，客户端基于请求项值请求更新。 基于更新请求的结果，表容量状态组件可以确定与动态线性散列表相关联的第一容量指示符。 表维护组件可以基于与包含在与哈希表相关联的散列表桶中包括的链接列表的无锁合并和无锁定分割来启动与动态线性散列表相关联的哈希表桶的无锁合并和无锁分割 动态线性哈希表，基于确定的第一容量指示符，链表包括存储在动态线性哈希表中的散列项。

公开(公告)号：US20110153566A1

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

申请号：US12641961

申请日：2009-12-18

申请人： Per-Ake Larson ,  Cristian Diaconu ,  Michael J. Zwilling ,  Craig Steven Freedman

发明人： Per-Ake Larson ,  Cristian Diaconu ,  Michael J. Zwilling ,  Craig Steven Freedman

IPC分类号： G06F17/00

CPC分类号： G06F17/30353 ,  G06F9/466 ,  G06F17/30356

摘要： The subject disclosure relates to a concurrency control technique that ensures isolation among concurrently execution transactions optimistically in a multiversion database by applying two optional tests at the end of a read-write transaction: validating the visibility of the read set of the read-write transaction(s) and phantom detection by re-scanning and confirming no new version have appeared in the view. Depending on desired level of isolation, both, one or none of the test are applied. Each version of a data record in an applicable database can be assigned two timestamps indicating the lifetime the version. The value of a version timestamp, though assigned, may be conditional on a transaction committing.

摘要翻译： 本公开涉及一种并发控制技术，其通过在读写事务结束时应用两个可选测试来确保在多版本数据库中乐观地同时执行事务之间的隔离：验证读写事务的读取集的可见性（ s）和幻影检测通过重新扫描和确认没有新版本出现在视图中。 根据所需的隔离度，两者都应用一个或者没有一个测试。 可以为适用的数据库中的每个版本的数据记录分配两个表示该版本的生命周期的时间戳。 版本时间戳的值（尽管已分配）可能以事务提交为条件。

公开(公告)号：US07555473B2

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

申请号：US11082392

申请日：2005-03-17

申请人： Per-Ake Larson ,  Cesar A. Galindo-Legaria

发明人： Per-Ake Larson ,  Cesar A. Galindo-Legaria

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

CPC分类号： G06F17/30489 ,  G06F17/30454 ,  G06F17/30469 ,  Y10S707/99931 ,  Y10S707/99932 ,  Y10S707/99933 ,  Y10S707/99934 ,  Y10S707/99935

摘要： A partial pre-aggregation database operation improves processing efficiency of database queries by reducing the number of records input into a subsequent database operation, provided the query includes a final aggregation. A query optimizer is provided to determine when it is economical to partially pre-aggregate data records and when it is not. The partial pre-aggregation creates a record store in memory as input records are received. The record store is then used by another database operator, which saves the other database operator from having to re-create the record store.

公开(公告)号：US07467128B2

公开(公告)日：2008-12-16

申请号：US11354375

申请日：2006-02-15

申请人： Per-Ake Larson ,  Jingren Zhou

发明人： Per-Ake Larson ,  Jingren Zhou

IPC分类号： G06F17/30

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

摘要： Maintenance of materialized view for query optimization in a database. The architecture provides the first practical algorithms for incrementally maintaining views with multiple outer joins and aggregated outer-join views. Materialized views with any combination of inner joins, one-sided outer joins and full outer joins, plus an optional aggregation on top, can be processed by algorithm(s) that construct incremental maintenance expressions based on converting the view definition a join-disjunctive normal form and exploiting database constraints to reduce maintenance overhead. A system comprises a view creation component for creating a materialized view definition that includes outer-joins, a conversion component for converting an outer-join view expression into a normal form, and a maintenance component for updating the stored materialized view result associated with the materialized view definition.

摘要翻译： 维护数据库中查询优化的物化视图。 该架构提供了第一个实际算法，用于逐步维护具有多个外连接和聚合外连接视图的视图。 可以通过基于通过将视图定义转换为连接分离正常来构造增量维护表达式的算法来处理具有任何内部联接，单面外部连接和完全外部连接的组合的物化视图以及顶部的可选聚合 形成和利用数据库约束来减少维护开销。 一种系统包括用于创建包括外连接的物化视图定义的视图创建组件，用于将外连接视图表达式转换为正常形式的转换组件，以及用于更新与实例化相关联的存储的物化视图结果的维护组件 视图定义。

公开(公告)号：US07383256B2

公开(公告)日：2008-06-03

申请号：US10977707

申请日：2004-10-29

申请人： Per-Ake Larson ,  Jonathan Goldstein

发明人： Per-Ake Larson ,  Jonathan Goldstein

IPC分类号： G06F17/30

CPC分类号： G06F17/30457 ,  G06F17/30451 ,  Y10S707/99932 ,  Y10S707/99934 ,  Y10S707/99943

摘要： A transformation-based optimizer generates rewritings by applying local algebraic transformation rules on subexpressions of a query. Application of a transformation rule produces substitute expressions, logically equivalent to the original expression. View matching, that is, computing a subexpression from materialized views, is one such transformation rule. The view matching rule applies a view matching technique that determines whether the original query can be computed from one or more of the existing materialized views and, if so, generates substitute expressions. An index structure of materialized views is provided that quickly narrows the search to a set of candidate views on which the view matching techniques can be applied. The index structure, also called a filter tree, speeds up the search for applicable materialized views.

摘要翻译： 基于变换的优化器通过在查询的子表达式上应用本地代数变换规则来生成重写。 转换规则的应用产生替代表达式，逻辑上等同于原始表达式。 查看匹配，即从物化视图计算子表达式，是一个这样的转换规则。 视图匹配规则应用视图匹配技术，其确定是否可以从一个或多个现有物化视图计算原始查询，如果是，则生成替代表达式。 提供了物化视图的索引结构，其快速地将搜索缩小到可应用视图匹配技术的一组候选视图。 索引结构（也称为过滤器树）可加速搜索适用的实例化视图。

公开(公告)号：US20050240556A1

公开(公告)日：2005-10-27

申请号：US11082392

申请日：2005-03-17

申请人： Per-Ake Larson ,  Cesar Galindo-Legaria

发明人： Per-Ake Larson ,  Cesar Galindo-Legaria

IPC分类号： G06F7/00

CPC分类号： G06F17/30489 ,  G06F17/30454 ,  G06F17/30469 ,  Y10S707/99931 ,  Y10S707/99932 ,  Y10S707/99933 ,  Y10S707/99934 ,  Y10S707/99935

摘要： A partial pre-aggregation database operation improves processing efficiency of database queries by reducing the number of records input into a subsequent database operation, provided the query includes a final aggregation. A query optimizer is provided to determine when it is economical to partially pre-aggregate data records and when it is not. The partial pre-aggregation creates a record store in memory as input records are received. The record store is then used by another database operator, which saves the other database operator from having to re-create the record store.

公开(公告)号：US10430298B2

公开(公告)日：2019-10-01

申请号：US12914753

申请日：2010-10-28

申请人： Mike Zwilling ,  Per-Ake Larson ,  Cristian Diaconu

发明人： Mike Zwilling ,  Per-Ake Larson ,  Cristian Diaconu

IPC分类号： G06F16/20 ,  G06F11/14 ,  G06F16/23

摘要： The subject disclosure relates to a database recovery technique that implements various aspects of transaction logging to optimize database recovery performance. Transactions are logged logically with no reference to physical location, which enables logging to be performed via multiple independent log streams in parallel. A set of log streams can further be adjusted to conform to a local configuration of a mirror or secondary node in order to increase mirroring flexibility. Additionally, individual transactions or groups of transactions are recorded using a single log record, which contains timestamp information to enable database recovery without reference to physical checkpoint files. Further, techniques are provided herein for processing transactions without Write Ahead Logging or hardening of undo information. As further described herein, a transaction can be committed via a set of hierarchical stages, which in turn can facilitate integration of an in-memory database system with one or more external database systems.

公开(公告)号：US08812555B2

公开(公告)日：2014-08-19

申请号：US13163674

申请日：2011-06-18

申请人： Per-Ake Larson ,  Donghui Zhang

发明人： Per-Ake Larson ,  Donghui Zhang

IPC分类号： G06F17/30

CPC分类号： G06F17/30949

摘要： A table update component may perform updates on a dynamic linear hash table, the updates requested by clients based on request item values. A table capacity status component may determine first capacity indicators associated with the dynamic linear hash table, based on results of the update requests. A table maintenance component may initiate lock-free merges and lock-free splits of hash table buckets associated with the dynamic linear hash table, based on initiating lock-free merges and lock-free splits of linked lists included in hash table buckets associated with the dynamic linear hash table, based on the determined first capacity indicators, the linked lists including hashed items stored in the dynamic linear hash table.

摘要翻译： 表更新组件可以在动态线性哈希表上执行更新，客户端基于请求项值请求更新。 基于更新请求的结果，表容量状态组件可以确定与动态线性散列表相关联的第一容量指示符。 表维护组件可以基于与包含在与哈希表相关联的散列表桶中包括的链接列表的无锁合并和无锁定分割来启动与动态线性散列表相关联的哈希表桶的无锁合并和无锁分割 动态线性哈希表，基于确定的第一容量指示符，链表包括存储在动态线性哈希表中的散列项。

公开(公告)号：US20110252000A1

公开(公告)日：2011-10-13

申请号：US12756185

申请日：2010-04-08

申请人： Cristian Diaconu ,  Craig Steven Freedman ,  Per-Ake Larson ,  Michael James Zwilling

发明人： Cristian Diaconu ,  Craig Steven Freedman ,  Per-Ake Larson ,  Michael James Zwilling

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

CPC分类号： G06F17/30377 ,  G06F12/0253 ,  G06F17/30309 ,  G06F17/30501 ,  G06F17/30575 ,  G06F2212/1044

摘要： A computer system includes a memory and a processor coupled to the memory. The processor is configured to execute instructions that cause execution of an in-memory database system that includes one or more database tables. Each database table includes a plurality of rows, where data representing each row is stored in the memory. The in-memory database system also includes a plurality of indexes associated with the one or more database tables, where each index is implemented by a lock-free data structure. Update logic at the in-memory database system is configured to update a first version of a particular row to create a second version of the particular row. The in-memory database system includes a non-blocking garbage collector configured to identify data representing outdated versions of rows.

摘要翻译： 计算机系统包括存储器和耦合到存储器的处理器。 处理器被配置为执行引起执行包括一个或多个数据库表的内存中数据库系统的指令。 每个数据库表包括多行，其中表示每一行的数据被存储在存储器中。 内存中数据库系统还包括与一个或多个数据库表相关联的多个索引，其中每个索引由无锁数据结构实现。 内存数据库系统中的更新逻辑被配置为更新特定行的第一版本以创建特定行的第二版本。 内存中的数据库系统包括一个非阻塞的垃圾收集器，用于标识表示行的过时版本的数据。