# US 12,222,915 B2 · Accumulating and flushing mutations in a column store > Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt - Number: US 12,222,915 B2 - Document ID: US12222915B2 - Status: Granted - Kind: B2 - Application number: 17/314,813 - Filed: 2021-05-07 - Published: 2021-09-02 - Granted: 2025-02-11 - Earliest claimed: 2015-05-07 - Assignees: Cloudera, Inc. - Applicants: Cloudera, Inc. - Inventors: Todd Lipcon - Web page: https://patentgrep.com/patent/US12222915B2 ## CPC - G06F 16/221: {Column-oriented storage; Management thereof} - G06F 16/2246: {Trees, e.g. B+trees} - G06F 16/2282: {Tablespace storage structures; Management thereof} - G06F 16/23: Updating - G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N) ## Abstract Columnar storage provides many performance and space saving benefits for analytic workloads, but previous mechanisms for handling single row update transactions in column stores suffer from poor performance. A columnar data layout facilitates both low-latency random access capabilities together with high-throughput analytical access capabilities, simplifying Hadoop architectures for use cases involving real-time data. In disclosed embodiments, mutations within a single row are executed atomically across columns and do not necessarily include the entirety of a row. This allows for faster updates without the overhead of reading or rewriting larger columns. ## Claims ### Claim 1 A method for a distributed database system, the method comprising: in response to an insert operation for a database table, storing a new row in a first in-memory store, wherein the first in-memory store is configured to flush to an on-disk store after a flushing criteria is reached; prior to the first in-memory store flushing the new row to the on-disk store, storing a separate mutation record linked to the new row that is stored in the first in-memory store, in response to a second mutation operation that is specified for the new row; and after the flushing criteria is reached, performing: modifying the new row stored in the first in-memory store based on applying the separate mutation record to the new row; and flushing (i) the modified new row to one or more base data files in the on-disk store, and (ii) the separate mutation record associated with the new row to one or more delta files in the on-disk store, wherein the first in-memory store and the on-disk store are configured for disjoint row storage such that a given row of the database table exists in one of a row set (RowSet) in the first in-memory store or a RowSet in the on-disk store. ### Claim 2 (depends on 1) The method of claim 1, wherein the separate mutation record is flushed to the one or more delta files with a timestamp that is associated with the second mutation operation. ### Claim 3 (depends on 1) The method of claim 1, further comprising: in response to a third mutation operation that specifies a flushed row stored in the on-disk store, storing a mutation record in a second in-memory store that is associated with the on-disk store, wherein the second in-memory store is configured to flush to the one or more delta files in the on-disk store after a second flushing criteria is reached. ### Claim 4 (depends on 1) The method of claim 1, wherein the one or more base data files and the one or more delta files are immutable. ### Claim 5 (depends on 1) The method of claim 1, wherein the database table includes (1) a number of columns, including a primary key (PK) column, and (2) a number of rows, each row having a unique PK stored in its corresponding PK column, wherein the number of rows are divided into a plurality of tablets, each tablet divided into a number of RowSets, wherein the RowSets are disjoint with respect to a stored key so that any given key is active in at most one RowSet, and wherein, for a given PK, at most one RowSet contains an active copy of a row with the given PK. ### Claim 6 (depends on 1) The method of claim 1, wherein the database table remains readable by a client of the database table during the flushing of the modified new row and the flushing of the separate mutation record. ### Claim 7 (depends on 1) The method of claim 1, further comprising: subsequent to flushing the modified new row, storing a new set of rows of the database table in the first in-memory store. ### Claim 8 (depends on 1) The method of claim 1, further comprising: processing a time-travel query for the modified new row in the on-disk store based on accessing the separate mutation record in the one or more delta files in the on-disk store. ### Claim 9 A computing system comprising: one or more processors; and one or more memories storing instructions that, when executed by the one or more processors, cause the computing system to perform a process comprising: in response to a first insert operation for a database table, storing a new row in a first in-memory store, wherein the first in-memory store is configured to flush to an on-disk store after a flushing criteria is reached; prior to the first in-memory store flushing the new row to the on-disk store, storing a separate mutation record attached to the new row that is stored in the first in-memory store, in response to a second mutation operation that is specified for the new row; and after the flushing criteria is reached, performing: modifying the new row stored in the first in-memory store based on applying the separate mutation record to the new row; and flushing (i) the modified new row to one or more base data files in the on-disk store, and (ii) the separate mutation record associated with the new row to one or more delta files in the on-disk store, wherein the first in-memory store and the on-disk store are configured for disjoint row storage such that a given row of the database table exists in one of a row set (RowSet) in the first in-memory store or a RowSet in the on-disk store. ### Claim 10 (depends on 9) The computing system of claim 9, wherein the process further comprises: determining that a third mutation operation specifies a flushed row that is stored in the on-disk store based on a Bloom filter for a set of primary keys present in the on-disk store; and storing a mutation record for the third mutation operation in a second in-memory store instead of the first in-memory store based on the third mutation operation specifying the flushed row stored in the on-disk store, wherein the second in-memory store is configured to flush to the one or more delta files in the on-disk store after a second flushing criteria is reached. ### Claim 11 (depends on 10) The computing system of claim 10, wherein the process further comprises: chunking available Bloom filters into pages corresponding to ranges of rows; creating an index for the pages using an immutable B-tree; and storing the pages and the index in a server-wide least recent used (LRU) page cache. ### Claim 12 (depends on 9) The computing system of claim 9, wherein the separate mutation record attached to the new row is implemented as a singly linked list, wherein the singly linked list includes a mutation head that points to a given mutation node, and a next mutation pointer in the given mutation node points to a subsequent mutation node. ### Claim 13 A non-transitory computer-readable medium storing instructions that, when executed by a computing system, cause the computing system to perform a process comprising: in response to a first insert operation for a database table, storing a new row in a first in-memory store, wherein the first in-memory store is configured to flush to an on-disk store after a flushing criteria is reached; prior to the first in-memory store flushing the new row to the on-disk store, storing a separate mutation record associated with the new row that is stored in the first in-memory store, in response to a second mutation operation that is specified for the new row; and after the flushing criteria, performing: modifying the new row stored in the first in-memory store based on applying the separate mutation record to the new row; and flushing (i) the modified new row to one or more base data files in the on-disk store, and (ii) flushing the separate mutation record associated with the new row to one or more delta files in the on-disk store, wherein the first in-memory store and the on-disk store are configured for disjoint row storage such that a given row of the database table exists in one of a row set (RowSet) in the first in-memory store or a RowSet in the on-disk store. ### Claim 14 (depends on 13) The non-transitory computer-readable medium of claim 13, wherein the process further comprises: performing a minor delta compaction operation that reduces a number of one or more delta files in the on-disk store by merging the one or more delta files together, without updating the one or more base data files in the on-disk store. ### Claim 15 (depends on 13) The non-transitory computer-readable medium of claim 13, wherein the separate mutation record is a REDO record, and wherein the process further comprises: performing a major delta compaction operation that migrates REDO records to UNDO records and updatess the one or more base data files in the on-disk store. ### Claim 16 (depends on 13) The non-transitory computer-readable medium of claim 13, wherein the process further comprises: performing a merging compaction operation that merges together a number of RowSets, in one or more on-disk stores, that overlap in range.