公开(公告)号：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.

公开(公告)号：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.

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

公开(公告)号：US07680767B2

公开(公告)日：2010-03-16

申请号：US11725206

申请日：2007-03-16

申请人： Atul Adya ,  Jose A. Blakeley ,  Per-Ake Larson ,  Sergey Melnik

发明人： Atul Adya ,  Jose A. Blakeley ,  Per-Ake Larson ,  Sergey Melnik

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

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

摘要： A data access architecture is provided that includes a mapping architecture for mapping data as may be used by an application to data as persisted in a database. The mapping architecture makes use of two types of mapping views—a query view that helps in translating queries and an update view that helps in translating updates. Incremental view maintenance can be used to translate data between the application and database.

摘要翻译： 提供了一种数据访问架构，其包括映射体系结构，用于将应用程序可能使用的数据映射为持久存储在数据库中的数据。 映射架构使用两种类型的映射视图 - 一种查询视图，可帮助翻译查询和更新视图，有助于翻译更新。 增量视图维护可用于在应用程序和数据库之间转换数据。

公开(公告)号：US06578131B1

公开(公告)日：2003-06-10

申请号：US09300715

申请日：1999-04-27

申请人： Per-Ake Larson ,  Murali R. Krishnan ,  George V. Reilly

发明人： Per-Ake Larson ,  Murali R. Krishnan ,  George V. Reilly

IPC分类号： G06F1206

CPC分类号： G06F9/526 ,  G06F17/30949

摘要： A scaleable hash table for shared memory multi-processor (SMP) that supports very high rates of concurrent operations (e.g., insert, delete, and lookup), while simultaneously reducing cache misses. The SMP system has a memory subsystem and a processor subsystem interconnected via a bus structure. The hash table is stored in the memory subsystem to facilitate access to data items. The hash table is segmented into multiple buckets, with each bucket containing a reference to a linked list of bucket nodes that hold references to data items with keys that hash to a common value. Individual bucket nodes contain multiple signature-pointer pairs that reference corresponding data items. Each signature-pointer pair has a hash signature computed from a key of the data item and a pointer to the data item. The first bucket node in the linked list for each of the buckets is stored in the hash table. To enable multithread access, while serializing operation of the table, the SMP system utilizes two levels of locks: a table lock and multiple bucket locks. The table lock allows access by a single processing thread to the table while blocking access for other processing threads. The table lock is held just long enough for the thread to acquire the bucket lock of a particular bucket node. Once the table lock is released, another thread can access the hash table and any one of the other buckets.

摘要翻译： 用于共享存储器多处理器（SMP）的可扩展哈希表，其支持非常高的并发操作速率（例如，插入，删除和查找），同时减少高速缓存未命中。 SMP系统具有通过总线结构互连的存储器子系统和处理器子系统。 哈希表存储在存储器子系统中以便于访问数据项。 散列表被分段成多个桶，每个桶包含对桶节点的链接列表的引用，其存储对具有哈希到公共值的密钥的数据项的引用。 单个桶节点包含引用相应数据项的多个签名 - 指针对。 每个签名 - 指针对具有从数据项的键和指向数据项的指针计算的散列签名。 每个桶的链表中的第一个桶节点存储在哈希表中。 要启用多线程访问，在序列化表的操作期间，SMP系统使用两个级别的锁：表锁和多个桶锁。 表锁允许单个处理线程访问表，同时阻止其他处理线程的访问。 表锁只能持续足够长的时间才能使线程获取特定桶节点的桶锁。 一旦表锁被释放，另一个线程就可以访问哈希表和其他任何一个存储桶。