# US 11,308,071 B2 · Update and query of a large collection of files that represent a single dataset stored on a blob store > Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt - Number: US 11,308,071 B2 - Document ID: US11308071B2 - Status: Granted - Kind: B2 - Application number: 16/941,227 - Filed: 2020-07-28 - Published: 2021-01-14 - Granted: 2022-04-19 - Earliest claimed: 2018-05-23 - Assignees: Databricks, Inc. - Applicants: Databricks Inc. - Inventors: Michael Paul Armbrust; Shixiong Zhu; Burak Yavuz - Web page: https://patentgrep.com/patent/US11308071B2 ## CPC - G06F 16/2358: {Change logging, detection, and notification (replication G06F16/27)} - G06F 16/148: {File search processing} - G06F 16/2282: {Tablespace storage structures; Management thereof} - G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N) ## Abstract A system includes an interface and a processor. The interface is configured to receive a table indication of a data table and to receive a transaction indication to perform a transaction. The processor is configured to determine a current position N in a transaction log; determine a current state of the metadata; determine a read set associated with a transaction; attempt to write an update to the transaction log associated with a next position N+1; in response to a transaction determination that a simultaneous transaction associated with the next position N+1 already exists, determine a set of updated files; and in response to a determination that there is not an overlap between the read set associated with the current transaction and the set of updated files associated with the simultaneous transaction, attempt to write the update to the transaction to the transaction log associated with a further position N+2. ## Claims ### Claim 1 A system for updating data, comprising: an interface configured to receive an indication to update a database; and a processor coupled to the interface and configured to: determine a current position N in a transaction log; attempt to write the update as a current transaction to a next position N+1 in the transaction log; determine that a simultaneous transaction associated with the next position N+1 already exists; and in response to a determination that the simultaneous transaction associated with the next position N+1 already exists: determine a set of updated files associated with the simultaneous transaction; determine whether a read set associated with the current transaction overlaps the set of updated files associated with the simultaneous transaction, comprising to: determine whether an overlap between the read set associated with the current transaction and the set of updated files associated with the simultaneous transaction exists; and in response to a determination that the overlap between the read set associated with the current transaction and the set of updated files associated with the simultaneous transaction exists: determine transaction conflict semantics, wherein the transaction conflict semantics comprise semantic rules specific to the transaction type of the transaction for determining whether update overlaps can create a problem; determine a simultaneous transaction conflict semantics, wherein the simultaneous transaction conflict semantics comprise semantic rules based on transaction behavior indicating when a file access overlap does not create a semantic conflict; and in response to a determination that the transaction conflict semantics and the simultaneous transaction conflict semantics do not indicate that the overlap causes a conflict, indicate that that the read set associated with the current transaction does not overlap the set of updated files associated with the simultaneous transaction; and in response to a determination that the read set associated with the current transaction does not overlap the set of updated files associated with the simultaneous transaction, attempt to write the update to a further position N+2 in the transaction log. ### Claim 2 (depends on 1) The system of claim 1, wherein the system for updating data comprises a cluster computing system. ### Claim 3 (depends on 2) The system of claim 2, wherein a plurality of cluster computing systems comprise systems for updating data on a table included in the database. ### Claim 4 (depends on 1) The system of claim 1, wherein the table is scalable to hold large data sets. ### Claim 5 (depends on 4) The system of claim 4, wherein large data sets comprise data sets holding gigabytes of data, terabytes of data, petabytes of data, or exabytes of data. ### Claim 6 (depends on 1) The system of claim 1, wherein the database includes a table that stores data and metadata, wherein the metadata includes file statistical information, a transaction identifier, a column invariant, or a table schema. ### Claim 7 (depends on 6) The system of claim 6, wherein file statistical information comprises column minima, column maxima, a count of rows, average data length per column, a count of null cells per column, a data histogram, a number of distinct values per column, or bloom filter data. ### Claim 8 (depends on 1) The system of claim 1, wherein the indication to update the database is a transaction, wherein the processor is further configured to process the transaction to determine the update. ### Claim 9 (depends on 1) The system of claim 1, wherein the processor is further configured to determine whether the simultaneous transaction associated with the next position N+1+ already exists, and in response to a no-transaction determination that no simultaneous transaction associated with the next position N+1 already exists, indicate transaction success. ### Claim 10 (depends on 1) The system of claim 1, wherein the processor is further configured to, in response to a determination that the read set associated with the transaction and transaction overlaps the set of updated files associated with the simultaneous transaction, indicate transaction failure. ### Claim 11 (depends on 1) The system of claim 1, wherein the processor is further configured to determine the read set associated with the transaction, wherein to determine the read set associated with the transaction, the processor is further configured to determine that metadata was read by the transaction, determine a set of files read by the transaction, or determine a transaction identifier. ### Claim 12 (depends on 1) The system of claim 1, wherein to determine whether a read set associated with the current transaction overlaps the set of updated files associated with the simultaneous transaction, the processor is configured to determine whether a file of the set of updated files associated with the simultaneous transaction is identified by the read set associated with the transaction. ### Claim 13 (depends on 1) The system of claim 1, wherein to determine whether a read set associated with the current transaction overlaps the set of updated files associated with the simultaneous transaction, the processor is configured to determine that no files added by the simultaneous transaction overlap an element of the read set. ### Claim 14 (depends on 1) The system of claim 1, wherein to determine whether a read set associated with the current transaction overlaps the set of updated files associated with the simultaneous transaction, the processor is configured to determine that no files modified by the simultaneous transaction satisfy the read set. ### Claim 15 (depends on 1) The system of claim 1, wherein to determine whether a read set associated with the current transaction overlaps the set of updated files associated with the simultaneous transaction, the processor is configured to determine that no files deleted by the simultaneous transaction satisfy the read set. ### Claim 16 (depends on 1) The system of claim 1, wherein to determine whether a read set associated with the current transaction overlaps the set of updated files associated with the simultaneous transaction, the processor is configured to determine that metadata read by the transaction was not modified by the simultaneous transaction. ### Claim 17 (depends on 1) The system of claim 1, wherein to determine whether a read set associated with the current transaction overlaps the set of updated files associated with the simultaneous transaction, the processor is configured to determine that a transaction identifier associated with the transaction and a transaction identifier associated with the simultaneous transaction do not match. ### Claim 18 A method, comprising: receiving an indication to update a database; determining a current position N in a transaction log; attempting to write the update as a current transaction to a next position N+1 in the transaction log; determining that a simultaneous transaction associated with the next position N+1 already exists; and in response to a determination that the simultaneous transaction associated with the next position N+1 already exists: determining a set of updated files associated with the simultaneous transaction; determining whether a read set associated with the current transaction overlaps the set of updated files associated with the simultaneous transaction, comprising: determining whether an overlap between the read set associated with the current transaction and the set of updated files associated with the simultaneous transaction exists; and in response to a determination that the overlap between the read set associated with the current transaction and the set of updated files associated with the simultaneous transaction exists: determining transaction conflict semantics, wherein the transaction conflict semantics comprise semantic rules specific to the transaction type of the transaction for determining whether update overlaps can create a problem; determining a simultaneous transaction conflict semantics, wherein the simultaneous transaction conflict semantics comprise semantic rules based on transaction behavior indicating when a file access overlap does not create a semantic conflict; and in response to a determination that the transaction conflict semantics and the simultaneous transaction conflict semantics do not indicate that the overlap causes a conflict, indicating that that the read set associated with the current transaction does not overlap the set of updated files associated with the simultaneous transaction; and in response to a determination that the read set associated with the current transaction does not overlap the set of updated files associated with the simultaneous transaction, attempting to write the update to a further position N+2 in the transaction log. ### Claim 19 A computer program product embodied in a non-transitory computer readable medium and comprising computer instructions for: receiving an indication to update a database; determining a current position N in a transaction log; attempting to write the update as a current transaction to a next position N+1 in the transaction log; determining that a simultaneous transaction associated with the next position N+1 already exists; and in response to a determination that the simultaneous transaction associated with the next position N+1 already exists: determining a set of updated files associated with the simultaneous transaction; determining whether a read set associated with the current transaction overlaps the set of updated files associated with the simultaneous transaction, comprising: determining whether an overlap between the read set associated with the current transaction and the set of updated files associated with the simultaneous transaction exists; and in response to a determination that the overlap between the read set associated with the current transaction and the set of updated files associated with the simultaneous transaction exists: determining transaction conflict semantics, wherein the transaction conflict semantics comprise semantic rules specific to the transaction type of the transaction for determining whether update overlaps can create a problem; determining a simultaneous transaction conflict semantics, wherein the simultaneous transaction conflict semantics comprise semantic rules based on transaction behavior indicating when a file access overlap does not create a semantic conflict; and in response to a determination that the transaction conflict semantics and the simultaneous transaction conflict semantics do not indicate that the overlap causes a conflict, indicating that that the read set associated with the current transaction does not overlap the set of updated files associated with the simultaneous transaction; and in response to a determination that the read set associated with the current transaction does not overlap the set of updated files associated with the simultaneous transaction, attempting to write the update to a further position N+2 in the transaction log.