公开(公告)号：US20100005077A1

公开(公告)日：2010-01-07

申请号：US12168821

申请日：2008-07-07

申请人： Ravi Krishnamurthy ,  Chi-Young Ku ,  James Shau ,  Chun Zhang ,  Kapil Surlaker ,  Jeremy Branscome ,  Michael Corwin ,  Joseph I. Chamdani

发明人： Ravi Krishnamurthy ,  Chi-Young Ku ,  James Shau ,  Chun Zhang ,  Kapil Surlaker ,  Jeremy Branscome ,  Michael Corwin ,  Joseph I. Chamdani

IPC分类号： G06F17/30

CPC分类号： G06F16/24542

摘要： Embodiments of the present invention generate and optimize query plans that are at least partially executable in hardware. Upon receiving a query, the query is rewritten and optimized with a bias for hardware execution of fragments of the query. A template-based algorithm may be employed for transforming a query into fragments and then into query tasks. The various query tasks can then be routed to either a hardware accelerator, a software module, or sent back to a database management system for execution. For those tasks routed to the hardware accelerator, the query tasks are compiled into machine code database instructions. In order to optimize query execution, query tasks may be broken into subtasks, rearranged based on available resources of the hardware, pipelined, or branched conditionally

摘要翻译： 本发明的实施例生成和优化在硬件中至少部分可执行的查询计划。 在接收到查询后，查询将被重写和优化，以便查询的片段的硬件执行偏差。 可以采用基于模板的算法将查询转换成片段，然后转换为查询任务。 然后可以将各种查询任务路由到硬件加速器，软件模块，或者发送回数据库管理系统以执行。 对于路由到硬件加速器的任务，将查询任务编译为机器码数据库指令。 为了优化查询执行，查询任务可能被分解为子任务，根据硬件的可用资源，流水线或有条件的分支进行重新排列

公开(公告)号：US20080189251A1

公开(公告)日：2008-08-07

申请号：US11895997

申请日：2007-08-27

申请人： Jeremy Branscome ,  Michael Corwin ,  Liuxi Yang ,  James Shau ,  Ravi Krishnamurthy ,  Joseph I. Chamdani

发明人： Jeremy Branscome ,  Michael Corwin ,  Liuxi Yang ,  James Shau ,  Ravi Krishnamurthy ,  Joseph I. Chamdani

IPC分类号： G06F17/30

CPC分类号： G06F16/2453

摘要： Embodiments of the present invention provide processing elements that are capable of performing high level database operations in hardware based on machine code instructions. These processing elements employ a dataflow architecture that operates on data in hardware without interruption or software. A scanning/indexing processing element may comprise logic that analyze database column groups stored in local memory, perform parallel field extraction and comparison, and generates a list of row pointers (row ids or RIDs) referencing those rows whose value(s) satisfy an applied predicate. The scanning/indexing processing may also be used to project database column groups, search and join index structures, and manipulate in-flight metadata flows, composing, merging, reducing, and modifying multi-dimensional lists of intermediate and final results. Furthermore, a scanning/indexing processing element may be used for joins with indexes, like a Group Index, which involves the association of each input tuple with potentially many related data components, in a one-to-many mapping. An XCAM processing element may comprise logic to perform associative database operations, like accumulation and aggregation, sieving, sorting and associative joins.

摘要翻译： 本发明的实施例提供了能够基于机器码指令在硬件中执行高级数据库操作的处理元件。 这些处理元件采用在不中断或软件的情况下对硬件上的数据进行操作的数据流架构。 扫描/索引处理元件可以包括分析存储在本地存储器中的数据库列组，执行并行字段提取和比较的逻辑，并且生成参考其值满足应用的那些行的行指针（行ID或RID）的列表 谓词。 扫描/索引处理也可用于投影数据库列组，搜索和连接索引结构，以及操纵机上元数据流，组合，合并，减少和修改中间和最终结果的多维列表。 此外，扫描/索引处理元件可以用于具有诸如组索引的索引的连接，该索引涉及每个输入元组与潜在的许多相关数据组件的关联，在一对多映射中。 XCAM处理元件可以包括执行关联数据库操作的逻辑，例如累积和聚合，筛选，排序和关联连接。

公开(公告)号：US08458129B2

公开(公告)日：2013-06-04

申请号：US12144486

申请日：2008-06-23

申请人： Kapil Surlaker ,  Ravi Krishnamurthy ,  Krishnan Meiyyappan ,  Alan Beck ,  Hung Tran ,  Jeremy Branscome ,  Joseph I. Chamdani

发明人： Kapil Surlaker ,  Ravi Krishnamurthy ,  Krishnan Meiyyappan ,  Alan Beck ,  Hung Tran ,  Jeremy Branscome ,  Joseph I. Chamdani

IPC分类号： G06F7/00

CPC分类号： G06F17/30356 ,  G06F17/30551

摘要： Embodiments of the present invention provide fine grain concurrency control for transactions in the presence of database updates. During operations, each transaction is assigned a snapshot version number or SVN. A SVN refers to a historical snapshot of the database that can be created periodically or on demand. Transactions are thus tied to a particular SVN, such as, when the transaction was created. Queries belonging to the transactions can access data that is consistent as of a point in time, for example, corresponding to the latest SVN when the transaction was created. At various times, data from the database stored in a memory can be updated using the snapshot data corresponding to a SVN. When a transaction is committed, a snapshot of the database with a new SVN is created based on the data modified by the transaction and the snapshot is synchronized to the memory. When a transaction query requires data from a version of the database corresponding to a SVN, the data in the memory may be synchronized with the snapshot data corresponding to that SVN.

摘要翻译： 在存在数据库更新的情况下，本发明的实施例为事务提供细粒度并行性控制。 在操作期间，为每个事务分配一个快照版本号或SVN。 SVN是指可以定期或按需创建的数据库的历史快照。 因此，事务与特定的SVN相关联，例如，当事务被创建时。 属于事务的查询可以访问一个时间点一致的数据，例如对应于创建事务时的最新SVN。 在不同时间，可以使用对应于SVN的快照数据来更新存储在存储器中的数据库的数据。 提交事务时，将根据事务修改的数据创建具有新SVN的数据库快照，并将快照与内存同步。 当事务查询需要来自与SVN对应的数据库的版本的数据时，存储器中的数据可以与对应于该SVN的快照数据同步。

公开(公告)号：US20090319486A1

公开(公告)日：2009-12-24

申请号：US12144486

申请日：2008-06-23

申请人： Kapil Surlaker ,  Ravi Krishnamurthy ,  Krishnan Meiyyappan ,  Alan Beck ,  Hung Tran ,  Jeremy Branscome ,  Joseph I. Chamdani

发明人： Kapil Surlaker ,  Ravi Krishnamurthy ,  Krishnan Meiyyappan ,  Alan Beck ,  Hung Tran ,  Jeremy Branscome ,  Joseph I. Chamdani

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

CPC分类号： G06F17/30356 ,  G06F17/30551

摘要： Embodiments of the present invention provide fine grain concurrency control for transactions in the presence of database updates. During operations, each transaction is assigned a snapshot version number or SVN. A SVN refers to a historical snapshot of the database that can be created periodically or on demand. Transactions are thus tied to a particular SVN, such as, when the transaction was created. Queries belonging to the transactions can access data that is consistent as of a point in time, for example, corresponding to the latest SVN when the transaction was created. At various times, data from the database stored in a memory can be updated using the snapshot data corresponding to a SVN. When a transaction is committed, a snapshot of the database with a new SVN is created based on the data modified by the transaction and the snapshot is synchronized to the memory. When a transaction query requires data from a version of the database corresponding to a SVN, the data in the memory may be synchronized with the snapshot data corresponding to that SVN.

摘要翻译： 在存在数据库更新的情况下，本发明的实施例为事务提供细粒度并行性控制。 在操作期间，为每个事务分配一个快照版本号或SVN。 SVN是指可以定期或按需创建的数据库的历史快照。 因此，事务与特定的SVN相关联，例如，当事务被创建时。 属于事务的查询可以访问一个时间点一致的数据，例如对应于创建事务时的最新SVN。 在不同时间，可以使用对应于SVN的快照数据来更新存储在存储器中的数据库的数据。 提交事务时，将根据事务修改的数据创建具有新SVN的数据库快照，并将快照与内存同步。 当事务查询需要来自与SVN对应的数据库的版本的数据时，存储器中的数据可以与对应于该SVN的快照数据同步。

公开(公告)号：US08244718B2

公开(公告)日：2012-08-14

申请号：US11895952

申请日：2007-08-27

申请人： Joseph I. Chamdani ,  Raj Cherabuddi ,  Michael Corwin ,  Jeremy Branscome ,  Liuxi Yang ,  Ravi Krishnamurthy

发明人： Joseph I. Chamdani ,  Raj Cherabuddi ,  Michael Corwin ,  Jeremy Branscome ,  Liuxi Yang ,  Ravi Krishnamurthy

IPC分类号： G06F7/00

CPC分类号： G06F17/30442

摘要： Embodiments of the present invention provide a database system that is optimized by using hardware acceleration. The system may be implemented in several variations to accommodate a wide range of queries and database sizes. In some embodiments, the system may comprise a host system that is coupled to one or more hardware accelerator components. The host system may execute software or provide an interface for receiving queries. The host system analyzes and parses these queries into tasks. The host system may then select some of the tasks and translate them into machine code instructions, which are executed by one or more hardware accelerator components. The tasks executed by hardware accelerators are generally those tasks that may be repetitive or processing intensive. Such tasks may include, for example, indexing, searching, sorting, table scanning, record filtering, and the like.

摘要翻译： 本发明的实施例提供了通过使用硬件加速来优化的数据库系统。 该系统可以以若干变型实现，以适应广泛的查询和数据库大小。 在一些实施例中，系统可以包括耦合到一个或多个硬件加速器组件的主机系统。 主机系统可以执行软件或提供用于接收查询的接口。 主机系统将这些查询分析并解析成任务。 然后，主机系统可以选择一些任务并将它们转换成由一个或多个硬件加速器组件执行的机器码指令。 硬件加速器执行的任务通常是可能是重复性或处理密集型的任务。 这样的任务可以包括例如索引，搜索，排序，表扫描，记录过滤等。

公开(公告)号：US20080183688A1

公开(公告)日：2008-07-31

申请号：US11895952

申请日：2007-08-27

申请人： Joseph I. Chamdani ,  Raj Cherabuddi ,  Michael Corwin ,  Jeremy Branscome ,  Liuxi Yang ,  Ravi Krishnamurthy

发明人： Joseph I. Chamdani ,  Raj Cherabuddi ,  Michael Corwin ,  Jeremy Branscome ,  Liuxi Yang ,  Ravi Krishnamurthy

IPC分类号： G06F17/30

CPC分类号： G06F17/30442

摘要： Embodiments of the present invention provide a database system that is optimized by using hardware acceleration. The system may be implemented in several variations to accommodate a wide range of queries and database sizes. In some embodiments, the system may comprise a host system that is coupled to one or more hardware accelerator components. The host system may execute software or provide an interface for receiving queries. The host system analyzes and parses these queries into tasks. The host system may then select some of the tasks and translate them into machine code instructions, which are executed by one or more hardware accelerator components. The tasks executed by hardware accelerators are generally those tasks that may be repetitive or processing intensive. Such tasks may include, for example, indexing, searching, sorting, table scanning, record filtering, and the like.

摘要翻译： 本发明的实施例提供了通过使用硬件加速来优化的数据库系统。 该系统可以以若干变型实现，以适应广泛的查询和数据库大小。 在一些实施例中，系统可以包括耦合到一个或多个硬件加速器组件的主机系统。 主机系统可以执行软件或提供用于接收查询的接口。 主机系统将这些查询分析并解析成任务。 然后，主机系统可以选择一些任务并将它们转换成由一个或多个硬件加速器组件执行的机器码指令。 硬件加速器执行的任务通常是可能是重复性或处理密集型的任务。 这样的任务可以包括例如索引，搜索，排序，表扫描，记录过滤等。

公开(公告)号：US08234267B2

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

申请号：US13048031

申请日：2011-03-15

申请人： Jeremy Branscome ,  Michael Corwin ,  Liuxi Yang ,  Joseph I. Chamdani

发明人： Jeremy Branscome ,  Michael Corwin ,  Liuxi Yang ,  Joseph I. Chamdani

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

CPC分类号： G06F17/30442

摘要： Embodiments of the present invention provide a hardware accelerator that assists a host database system in processing its queries. The hardware accelerator comprises special purpose processing elements that are capable of receiving database query/operation tasks in the form of machine code database instructions, execute them in hardware without software, and return the query/operation result back to the host system. For example, table and column descriptors are embedded in the machine code database instructions. For ease of installation, the hardware accelerators employ a standard interconnect, such as a PCle or HT interconnect. The processing elements implement a novel dataflow design and Inter Macro-Op Communication (IMC) data structures to execute the machine code database instructions. The hardware accelerator may also comprise a relatively large memory to enhance the hardware execution of the query/operation tasks requested. The hardware accelerator utilizes hardware-friendly memory addressing, which allows for arithmetic derivation of a physical address from a global database virtual address simply based on a row identifier. The hardware accelerator minimizes memory reads/writes by keeping most intermediate results flowing through IMCs in pipelined and parallel fashion. Furthermore, the hardware accelerator may employ task pipelining and pre-fetch pipelining to enhance its performance.

摘要翻译： 本发明的实施例提供了一种辅助主机数据库系统处理其查询的硬件加速器。 硬件加速器包括能够以机器码数据库指令的形式接收数据库查询/操作任务的专用处理元件，无需软件执行硬件，并将查询/运算结果返回主机系统。 例如，表和列描述符嵌入在机器码数据库指令中。 为了便于安装，硬件加速器采用标准互连，如PCle或HT互连。 处理元件实现了一种新颖的数据流设计和Inter Macro-Op Communication（IMC）数据结构来执行机器码数据库指令。 硬件加速器还可以包括相对大的存储器，以增强所请求的查询/操作任务的硬件执行。 硬件加速器使用硬件友好的存储器寻址，这允许仅仅基于行标识符从全局数据库虚拟地址算术推导物理地址。 硬件加速器通过保持大多数中间结果以流水线和并行方式流过IMC来最小化存储器读/写。 此外，硬件加速器可以采用任务流水线和预取流水线来增强其性能。

公开(公告)号：US08224800B2

公开(公告)日：2012-07-17

申请号：US13048015

申请日：2011-03-15

申请人： Jeremy Branscome ,  Michael Corwin ,  Liuxi Yang ,  Joseph I. Chamdani

发明人： Jeremy Branscome ,  Michael Corwin ,  Liuxi Yang ,  Joseph I. Chamdani

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

CPC分类号： G06F17/30442

摘要： Embodiments of the present invention provide a hardware accelerator that assists a host database system in processing its queries. The hardware accelerator comprises special purpose processing elements that are capable of receiving database query/operation tasks in the form of machine code database instructions, execute them in hardware without software, and return the query/operation result back to the host system. For example, table and column descriptors are embedded in the machine code database instructions. For ease of installation, the hardware accelerators employ a standard interconnect, such as a PCle or HT interconnect. The processing elements implement a novel dataflow design and Inter Macro-Op Communication (IMC) data structures to execute the machine code database instructions. The hardware accelerator may also comprise a relatively large memory to enhance the hardware execution of the query/operation tasks requested. The hardware accelerator utilizes hardware-friendly memory addressing, which allows for arithmetic derivation of a physical address from a global database virtual address simply based on a row identifier. The hardware accelerator minimizes memory reads/writes by keeping most intermediate results flowing through IMCs in pipelined and parallel fashion. Furthermore, the hardware accelerator may employ task pipelining and pre-fetch pipelining to enhance its performance.

公开(公告)号：US08229918B2

公开(公告)日：2012-07-24

申请号：US13048024

申请日：2011-03-15

申请人： Jeremy Branscome ,  Michael Corwin ,  Liuxi Yang ,  Joseph I. Chamdani

发明人： Jeremy Branscome ,  Michael Corwin ,  Liuxi Yang ,  Joseph I. Chamdani

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

CPC分类号： G06F17/30442

摘要： Embodiments of the present invention provide a hardware accelerator that assists a host database system in processing its queries. The hardware accelerator comprises special purpose processing elements that are capable of receiving database query/operation tasks in the form of machine code database instructions, execute them in hardware without software, and return the query/operation result back to the host system. For example, table and column descriptors are embedded in the machine code database instructions. For ease of installation, the hardware accelerators employ a standard interconnect, such as a PCle or HT interconnect. The processing elements implement a novel dataflow design and Inter Macro-Op Communication (IMC) data structures to execute the machine code database instructions. The hardware accelerator may also comprise a relatively large memory to enhance the hardware execution of the query/operation tasks requested. The hardware accelerator utilizes hardware-friendly memory addressing, which allows for arithmetic derivation of a physical address from a global database virtual address simply based on a row identifier. The hardware accelerator minimizes memory reads/writes by keeping most intermediate results flowing through IMCs in pipelined and parallel fashion. Furthermore, the hardware accelerator may employ task pipelining and pre-fetch pipelining to enhance its performance.

公开(公告)号：US20080189252A1

公开(公告)日：2008-08-07

申请号：US11895998

申请日：2007-08-27

申请人： Jeremy Branscome ,  Michael Corwin ,  Liuxi Yang ,  Joseph I. Chamdani

发明人： Jeremy Branscome ,  Michael Corwin ,  Liuxi Yang ,  Joseph I. Chamdani

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

CPC分类号： G06F17/30442

摘要： Embodiments of the present invention provide a hardware accelerator that assists a host database system in processing its queries. The hardware accelerator comprises special purpose processing elements that are capable of receiving database query/operation tasks in the form of machine code database instructions, execute them in hardware without software, and return the query/operation result back to the host system. For example, table and column descriptors are embedded in the machine code database instructions. For ease of installation, the hardware accelerators employ a standard interconnect, such as a PCIe or HT interconnect. The processing elements implement a novel dataflow design and Inter Macro-Op Communication (IMC) data structures to execute the machine code database instructions. The hardware accelerator may also comprise a relatively large memory to enhance the hardware execution of the query/operation tasks requested. The hardware accelerator utilizes hardware-friendly memory addressing, which allows for arithmetic derivation of a physical address from a global database virtual address simply based on a row identifier. The hardware accelerator minimizes memory reads/writes by keeping most intermediate results flowing through IMCs in pipelined and parallel fashion. Furthermore, the hardware accelerator may employ task pipelining and pre-fetch pipelining to enhance its performance.

摘要翻译： 本发明的实施例提供了一种辅助主机数据库系统处理其查询的硬件加速器。 硬件加速器包括能够以机器码数据库指令的形式接收数据库查询/操作任务的专用处理元件，无需软件执行硬件，并将查询/运算结果返回主机系统。 例如，表和列描述符嵌入在机器码数据库指令中。 为了便于安装，硬件加速器采用标准互连，例如PCIe或HT互连。 处理元件实现了一种新颖的数据流设计和Inter Macro-Op Communication（IMC）数据结构来执行机器码数据库指令。 硬件加速器还可以包括相对大的存储器，以增强所请求的查询/操作任务的硬件执行。 硬件加速器使用硬件友好的存储器寻址，这允许仅仅基于行标识符从全局数据库虚拟地址算术推导物理地址。 硬件加速器通过保持大多数中间结果以流水线和并行方式流过IMC来最小化存储器读/写。 此外，硬件加速器可以采用任务流水线和预取流水线来增强其性能。