Low-latency database system

Patent metadata

Field	Value
Publication number	US-11556535-B2
Application number	US-202117443219-A
Country	US
Kind code	B2
Filing date	Jul 22, 2021
Priority date	Aug 19, 2020
Publication date	Jan 17, 2023
Grant date	Jan 17, 2023

Abstract

A database system comprised of a decoupled compute layer and storage layer is implemented to store, build, and maintain a canonical dataset, a temporary buffer, and an edits dataset. The canonical dataset is a set of batch updated data. The data is appended in chunks to the canonical dataset such that the canonical dataset becomes a historical dataset over time. The buffer is a write ahead log that contains the most recent chunks of data and provides atomicity and durability for the database system. The edits dataset is the set of data that contains edits such as cell mutations, row appends and/or row deletions. The database system enables users to make cell or row-level edits to tables and observe those edits in analytical systems or downstream builds with minimal latency.

First claim

What is claimed is:

1. A system comprising:
one or more non-transitory computer readable storage mediums having program instructions embodied therewith; and
one or more processors configured to execute the program instructions to cause the system to:
receive one or more edits to be made to a first dataset;
temporarily store the one or more edits in a buffer;
dump the buffer to a second dataset by:
appending the one or more edits to the second dataset; and
flushing the one or more edits from the buffer; and

in response to receipt of a query of the first dataset:
collapse the second dataset based on one or more resolution rules;
join the collapsed second dataset to the first dataset;
execute the query on the join between the collapsed second dataset and the first dataset; and
return a result of the query executed on the join between the collapsed second dataset and the first dataset.

2. The system of claim 1 , wherein the one or more processors are configured to execute the program instructions to further cause the system to:
receive one or more additional edits to be made to the first dataset;
temporarily store the one or more additional edits in the buffer; and
in response to receipt of a second query of the first dataset:
join the buffer to the second dataset to form a joined second dataset;
collapse the joined second dataset based on one or more resolution rules;
join the collapsed joined second dataset to the first dataset;
execute the query on the join between the collapsed joined second dataset and the first dataset; and
return a result of the query executed on the join between the collapsed joined second dataset and the first dataset.

3. The system of claim 1 , wherein dumping the buffer to the second dataset is performed periodically.

4. The system of claim 1 , wherein dumping the buffer to the second dataset is performed when contents of the buffer reach a certain size.

5. The system of claim 1 , wherein the one or more edits to be made to the first dataset are provided by a user via a user interface.

6. The system of claim 1 , wherein the returning the result of the query executed on the join comprises:
generating user interface data for a user interface configured to present the result of the executed query; and
displaying the user interface to a user.

7. The system of claim 1 , wherein the one or more resolution rules specify that, for any data item, a most-recent edit for that data item is to be kept in the second dataset.

8. The system of claim 1 , wherein each edit stored in the buffer comprises a row key and a timestamp, wherein the timestamp is associated with a time the respective edit was written to the buffer.

9. The system of claim 1 , wherein the second dataset comprises all the edits dumped from the buffer.

10. The system of claim 1 , wherein the one or more processors are configured to execute the program instructions to further cause the system to:
generate a collapsed form of the second dataset by determining a most-recent edit for each row based on a row key associated with each edit in the second dataset.

11. The system of claim 1 , wherein the one or more processors are configured to execute the program instructions to further cause the system to:
rewrite the query to be applied to the join between the collapsed joined second dataset and the first dataset.

12. A computer-implemented method comprising:
receiving one or more edits to be made to a first dataset;
temporarily storing the one or more edits in a buffer;
dumping the buffer to a second dataset by:
appending the one or more edits to the second dataset; and
flushing the one or more edits from the buffer; and

in response to receipt of a query of the first dataset:
collapsing the second dataset based on one or more resolution rules;
joining the collapsed second dataset to the first dataset;
executing the query on the join between the collapsed second dataset and the first dataset; and
returning a result of the query executed on the join between the collapsed second dataset and the first dataset.

13. The computer-implemented method of claim 12 , further comprising:
receiving one or more additional edits to be made to the first dataset;
temporarily storing the one or more additional edits in the buffer; and
in response to receipt of a second query of the first dataset:
joining the buffer to the second dataset to form a joined second dataset;
collapsing the joined second dataset based on one or more resolution rules;
joining the collapsed joined second dataset to the first dataset;
executing the query on the join between the collapsed joined second dataset and the first dataset; and
returning a result of the query executed on the join between the collapsed joined second dataset and the first dataset.

14. The computer-implemented method of claim 12 , wherein dumping the buffer to the second dataset is performed periodically.

15. The computer-implemented method of claim 12 , wherein dumping the buffer to the second dataset is performed when contents of the buffer reach a certain size.

16. The computer-implemented method of claim 12 , wherein the one or more resolution rules specify that, for any data item, a most-recent edit for that data item is to be kept in the second dataset.

17. Non-transitory computer-readable media including computer-executable instructions that, when executed by a computing system, cause the computing system to perform operations comprising:
receiving one or more edits to be made to a first dataset;
temporarily storing the one or more edits in a buffer;
dumping the buffer to a second dataset by:
appending the one or more edits to the second dataset; and
flushing the one or more edits from the buffer; and

in response to receipt of a query of the first dataset:
collapsing the second dataset based on one or more resolution rules;
joining the collapsed second dataset to the first dataset;
executing the query on the join between the collapsed second dataset and the first dataset; and
returning a result of the query executed on the join between the collapsed second dataset and the first dataset.

18. The non-transitory computer-readable media of claim 17 , wherein dumping the buffer to the second dataset is performed periodically.

19. The non-transitory computer-readable media of claim 17 , wherein dumping the buffer to the second dataset is performed when contents of the buffer reach a certain size.

20. The non-transitory computer-readable media of claim 17 , wherein the one or more resolution rules specify that, for any data item, a most-recent edit for that data item is to be kept in the second dataset.

Assignees

• Palantir Technologies Inc

Inventors

• Elliot Mark
• Ellis Joseph
• Ramsharan Rahij
• Sills Matthew
• Manning Lawrence

Classifications

• G06F16/24534 Primary

  Query rewriting; Transformation · CPC title

• G06F16/2379

  Updates performed during online database operations; commit processing · CPC title

• G06F16/248

  Presentation of query results · CPC title

• G06F16/1805

  Append-only file systems, e.g. using logs or journals to store data · CPC title

• G06F16/24537 Primary

  of operators · CPC title