High-performance database engine implementing a positional delta tree update system

A computer system comprising:

• a column-store organized database store providing for the storage of a database table;
• and
• a central processor subsystem, including a cache memory and main memory, coupled to said database store, said central processor subsystem being operative to execute as a database engine system responsive to database requests received relative to said database table, including query requests to return data tuples and update requests to store data tuples, said database engine system including:
• a write-store structure, established within the main memory accessible by said central processor subsystem, providing for the storage of differential update data in a write positional delta tree structure, wherein said differential update data is stored with positional data relating said differential update data with positions defined with respect to a stable state of said database table;
• a read-store structure, wherein said write-store structure provides for the storage of first differential update data and said read-store structure provides for the storage of second differential update data, said second differential update data being stored in a read positional delta tree structure, wherein said second differential update data is stored with pre-computed positional data relating said second differential update data with positions defined with respect to said stable state of said database table;
• a merge scan processor, coupled to said write-store structure, operative to dynamically merge said differential update data with read data tuples retrieved from said database table if the differential update data does not modify the same tuple already committed to said positional delta tree and to optimize the dynamic merger of read data tuples with said differential update data for read-mostly operation of the database engine system, wherein said merge scan processor is coupled to said read-store structure, said merge scan processor being operative to dynamically merge said first and second differential update data with read data tuples retrieved from said database table, wherein said pre-computed positional data identifies the merge position of said first and second differential update data with respect said stable state positions of said read data tuples;
• an update processor operative in response to update requests providing update data tuples to store said first differential update data in said write-store structure, said write positional delta tree structure representing differential updates in 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 relative to said stable state positions for said first differential update data stored in corresponding child node subtrees, and wherein leaf nodes store references to entries in update type defined differential value tables, wherein said update processor is responsive to transaction start and commit requests, wherein a transaction-store is provided with respect to a transaction start request, wherein said transaction-store provides for the storage of transaction differential update data in a transaction positional delta tree structure, wherein said transaction differential update data is stored with pre-computed positional data relating said transaction differential update data with positions defined with respect to said stable state of said database table, wherein said update processor is further operative to provide an isolation-store as an instance copy of said write-store structure relative to said transaction start request, wherein query requests are resolved within the scope of a database transaction by dynamic merge access by said merge scan processor to said isolation-store in preference to said write-store structure;
• a merge processor operative to transfer said first differential update data from said write-store structure to said read-store structure and a checkpoint processor operative with said merge scan processor, to transfer and merge said second differential update data with data tuples stored in said database table, adjusting said stable state positions of said read data tuples, wherein said merge scan processor is further coupled to said transaction store and operative to dynamically merge said transaction, first, and second differential update data with read data tuples retrieved from said database table, wherein said pre-computed positional data identifies the merge position of said transaction, first and second differential update data with respect said stable state positions of said read data tuples;
• and wherein update data tuples provided with respect to update requests are stored as transaction differential update data in said transaction-store pending receipt of a transaction commit request corresponding to said transaction start request, said update processor being further operative to transfer said transaction differential update data from said transaction-store to said write-store structure in response to said transaction commit request;
• wherein said positional data identifies the merge position of said differential update data with respect said stable state positions of said read data tuples, whereby the merger of said differential update data and read data tuples provides current data tuples responsive to a predetermined database request;
• and
• wherein said update processor, in response to said commit request, is operative to conditionally transfer said transaction differential update data to said write store dependent on the absence of an actual conflict between said transaction differential update data and said write differential update data, said update processor being operative to first align said transaction and write differential update data into a common domain with respect to said stable state positions existing in said database table and second detect attribute update overlaps a same domain tuple position, wherein an overlapping update represents said actual conflict.