Column-store database architecture utilizing positional delta tree update system and methods

• US 10,152,504 B2
• Filed: 03/08/2010
• Issued: 12/11/2018
• Est. Priority Date: 03/11/2009
• Status: Active Grant

• Current Assignee: Actian Corporation
• Original Assignee: Actian Netherlands BV (HCL Technologies Limited)
• Inventors: Heman, Sandor A B C, Boncz, Peter A., Zukowski, Marcin, Nes, Nicolaas J.
• Primary Examiner(s): Yen, Syling
• Application Number:
  US12/719,825
• Publication Number:
  US 20100235335A1
• Time in Patent Office: 3,200 Days
• Field of Search: 707791, 707802, 707803, 707809, 7079991
• CPC Class Codes: G06F 16/221 Column-oriented storage; Management thereof
• CPC Class Codes: G06F 16/2246 Trees, e.g. B+trees
• CPC Class Codes: G06F 16/23 Updating

Abstract

A column-store database computer system responsive to database requests for the update and retrieval of data from within a stable data table providing for the storage of database tuples within a column-store organized database structure. A positional delta tree data structure is implemented in the memory space of the computer system and is operatively coupled in an update data transfer path between a database engine interface and the stable data table. The positional delta tree data structure includes a differential data storage layer operative to store differential update data values in positionally defined relative reference to database tuples stored by the stable data table.

Claims

1. A database engine implemented in a computer system that is coupled to a database store that provides for the storage of a database table, said database engine being operative in responsive to database query requests relative to said database table to return a current sequence of data tuples corresponding to a predetermined database query request, said database engine comprising:

a write-store structure that provides for the storage of data tuple updates pending application to said database table, the data tuple updates being stored in a positional delta tree data structure having a tree node and one or more leaf nodes that stores differential updates;

a computer implemented merge scan processor, coupled to said write-store structure, operative to retrieve from said database table an initial sequence of data tuples responsive to said predetermined database query request, said merge scan processor being further dynamically operative to selectively merge said data tuple updates with said initial sequence of data tuples using the positional delta tree data structure to provide said current sequence of data tuples;

an update processor, coupled to said write-store structure, said update processor operative, in response to database update requests relative to said database table, to receive and store differential data tuples in said write-store structure, wherein said update processor, within a defined transaction, is operative to allocate a transaction-store to receive and store differential data tuples, said update processor being further operative to transfer differential data tuples stored in said transaction-store to said write-store structure conditionally on commit of said defined transaction; and

a query processor operative to allocate a snapshot write-store structure with respect to said defined transaction wherein said snapshot write-store structure contains a copy of the differential data tuples existing in said write-store structure at the initiation of said defined transaction, wherein database query requests relative to said database table complete relative to said snapshot write-store structure in preference to said write-store structure.

2. The database engine of claim 1 wherein differential data tuple updates stored by said write-store structure are stored in a pre-computed mapped relationship between stable tuple positions, defined as positions existent in said database table at a first point in time, and effective tuple positions, defined as corresponding to said stable tuple positions at a second point in time subject to the application of differential data tuples received and stored between said first and second points in time.

3. The database engine of claim 2 wherein said write-store structure is organized as a tree structure storing differential data tuples as leaf nodes in said tree structure related through mapping nodes that store a delta value with respect to each directly connected child node, each said delta value representing the net change in effective tuple position for updates stored in the corresponding child subtree of nodes, wherein leaf nodes store references to entries in update type defined value tables.

4. The database engine of claim 1 wherein the transfer of differential data tuples stored in said transaction-store to said write-store structure is further conditional on conflicting existence of a prior committed transaction, wherein conflict occurs where the time range of differential data tuples transferred in said prior committed transaction overlaps with the time range of differential data tuples to be transferred in said defined transaction and any of the differential data tuples transferred in said prior committed transaction intersects with any of the differential data tuples to be transferred in said defined transaction.

5. The database engine of claim 4 wherein said update processor is operative to determine existence of an actual conflict by performance of an attribute-level ordered comparison of the differential data tuples to be transferred in said defined transaction with effective tuple position domain of the differential data tuples transferred in said prior committed transaction, wherein the comparison is dependent on alignment of the stable tuple position domain of the differential data tuples to be transferred in said defined transaction and the effective tuple position domain of the differential data tuples transferred in said prior committed transaction.

6. The database engine of claim 5 further comprising a read-store structure coupled to said write-store structure to receive transfers of differential data tuples prior stored in said write-store structure, said read-store structure being further coupled to said merge scan processor, wherein said merge scan processor is dynamically operative to selectively merge said data tuple updates from said read-store structure and said write-store structure with said initial sequence of data tuples to provide said current sequence of data tuples.

7. The database engine of claim 6 further comprising a merge processor coupled to said write-store structure and said read-store structure, said merge processor being operative to direct the transfer of differential data tuples prior stored in said write-store structure to said read-store structure.

8. The database engine of claim 7 further comprising a checkpoint processor coupled to said read-store structure, said checkpoint processor being operative to direct a merger of the differential data tuples prior stored in said read-store structure with a corresponding sequence of data tuples stored by said database table and persist update data tuples in said database table.

9. The database engine of claim 8 wherein said transaction-store and said read-store structure are respectively organized as a tree structure storing differential data tuples as leaf nodes in said tree structure related through mapping nodes that store a delta value with respect to each directly connected child node, each said delta value representing the net change in effective tuple position for updates stored in the corresponding child subtree of nodes, wherein leaf nodes store references to entries in update type defined value tables.

10. The database engine of claim 9 wherein said database table is organized as a column-store database table.

11. The database engine of claim 10 further comprising a main memory store and a central processing unit subsystem including a cache memory store providing for the storage of data in each of a plurality of cache memory lines, wherein said read-store structure and said write-store structure are nominally resident in said main memory store, and wherein the nodes of said tree structures of said read-store structure and said write-store structure are sized to fit within respective cache memory lines, whereby substantial portions of said tree structures remain resident in and are accessed from said cache memory store.

12. The database engine of claim 11 wherein said main memory store includes a memory space portion implemented as a persistent memory.

13. The database engine of claim 12 wherein said persistent memory is Flash memory.

14. The database engine of claim 10 wherein said main memory store includes an external persistent storage device, wherein said merge processor is operative to copy predetermined portions of said read-store structure to said external persistent storage device, and wherein said checkpoint processor is operative to merge said predetermined portions of said read-store structure for storage in said database table.

15. The database engine of claim 14 wherein said external persistent storage device is implemented as a Flash-based disk emulation storage device.

16. The database engine of claim 1, wherein the merge positions are a stable identifier and a current row identifier.

17. The database engine of claim 16, wherein the stable identifier corresponds to tuple positions defined within a stable table.

18. A database engine implemented in a computer system that is coupled to a database store that provides for the storage of a database table, said database engine being operative in responsive to database query requests relative to said database table to return a current sequence of data tuples corresponding to a predetermined database query request, said database engine comprising:

a write-store structure that provides for the storage of data tuple updates pending application to said database table, the data tuple updates being stored in a positional delta tree data structure having a tree node and one or more leaf nodes that stores differential updates;

a computer implemented merge scan processor, coupled to said write-store structure, operative to retrieve from said database table an initial sequence of data tuples responsive to said predetermined database query request, said merge scan processor being further dynamically operative to selectively merge said data tuple updates with said initial sequence of data tuples using the positional delta tree data structure to provide said current sequence of data tuples;

an update processor, coupled to said write-store structure, said update processor operative, in response to database update requests relative to said database table, to receive and store differential data tuples in said positional delta tree and wherein said positional delta tree stores said differential update in a manner to identify an update tuple data position within said database table; and

a query processor, coupled to said write-store structure, said query processor operative to respond to query requests to provide responsive tuple data, with respect to said database table, wherein said query processor operates to dynamically merge said differential update with tuple data retrieved from said database table using the positional delta tree and the position of tuple data read from said database table.

19. The database engine of claim 18, wherein the update processor stores said differential update such that the pre-computed position of said differential update is defined by a mapping between stable tuple positions existing in said database table at a first point in time, and effective tuple positions, defined as corresponding to said stable tuple positions at a second point in time reflecting an application of said differential update to said database table prior to a second point in time.

20. The database engine of claim 19, wherein said update processor manages said positional delta tree within said write-store structure to represent differential updates as leaf nodes related through mapping nodes storing delta values with respect directly connected child nodes, wherein each said delta value represents a net change in effective tuple position for updates stored in the corresponding child subtree of nodes, and wherein leaf nodes store references to entries in update type defined differential value tables.

21. The database engine of claim 20, wherein said computer system includes a central processing subsystem including a cache memory store providing for the storage of cache lines of data, and wherein nodes of said positional delta tree are sized to permit one or more nodes of said positional delta tree to be read into and stored as a cache line of data.

22. The database engine of claim 18 further comprising a persistent memory accessible by the query processor that stores a portion of said second plurality of differential updates.

23. The database engine of claim 22, wherein said persistent memory is a Flash based memory store operating as a directly accessible memory.

24. The database engine of claim 22, wherein said persistent memory is a Flash based disk emulation memory store.