Projections for big database systems

Patent metadata

Field	Value
Publication number	US-11620280-B2
Application number	US-202117444715-A
Country	US
Kind code	B2
Filing date	Aug 9, 2021
Priority date	Aug 19, 2020
Publication date	Apr 4, 2023
Grant date	Apr 4, 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 projection datasets. 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 projection datasets are indexes of the canonical dataset and/or the buffer that may have single or multiple column sort-orders and/or particular data formats. The writes to the canonical dataset, projection datasets, and buffer may be asynchronous and therefore the database system is advantageously less resource constrained.

First claim

What is claimed is:

1. A system comprising:
one or more non-transitory computer readable storage mediums configured to store:
program instructions;
a canonical dataset;
at least a first projection dataset; and
a buffer; and

one or more processors configured to execute the program instructions to cause the system to:
receive a first data chunk comprising an edit to the canonical dataset;
temporarily store the first data chunk in the buffer;
asynchronously:
update the canonical dataset based on the first data chunk; and
update the first projection dataset based on at least a part of the first data chunk; and

flush the first data chunk from the buffer.

2. The system of claim 1 , wherein the first projection dataset comprises a first sorted subset of data of the canonical dataset.

3. The system of claim 2 , wherein the one or more non-transitory computer readable storage mediums are further configured to store:
a second projection dataset comprising a second sorted subset of data of the canonical dataset, wherein the second sorted subset of data is different from the first sorted subset of data.

4. The system of claim 3 , wherein the first and second sorted subsets of data are selected and sorted based on different projection rules.

5. The system of claim 3 , wherein the one or more processors are configured to execute the program instructions to further cause the system to:
asynchronously update the second projection dataset based on the first data chunk.

6. The system of claim 5 , wherein asynchronously updating the first and second projection datasets includes selecting, based on projection rules applicable to the respective first and second projection datasets, portions of the first data chunk needed to update the respective first and second projection datasets.

7. The system of claim 6 , wherein the one or more processors are configured to execute the program instructions to further cause the system to:
periodically compacting the first and second projection datasets.

8. The system of claim 3 , wherein the one or more processors are configured to execute the program instructions to further cause the system to:
in response to receipt of a query of the canonical dataset:
select, based on the query, at least one of the first or second projection datasets;
execute the query on the selected at least one of the first or second projection datasets; and
return a result of the query.

9. The system of claim 8 , wherein the one or more processors are configured to execute the program instructions to further cause the system to:
receive a second data chunk comprising another edit to the canonical dataset;
temporarily store the second data chunk in the buffer; and
in response to receipt of a second query of the canonical dataset:
select, based on the second query, at least another one of the first or second projection datasets;
join the buffer to the selected at least another one of the first or second projection datasets to form a joined projection dataset;
execute the second query on the joined projected dataset; and
return a result of the second query.

10. The system of claim 8 , wherein the selected at least one of the first or second projection datasets includes both the first projection dataset and the second projection dataset.

11. The system of claim 10 , wherein the one or more processors are configured to execute the program instructions to further cause the system to:
further in response to receipt of the query of the canonical dataset:
join the first and second projection datasets to form a joined projection dataset, wherein the query is executed on the joined projected dataset.

12. A computer-implemented method comprising:
receiving a first data chunk comprising an edit to a canonical dataset;
temporarily storing the first data chunk in a buffer;
asynchronously:
updating the canonical dataset based on the first data chunk; and
updating at least one projection dataset based on at least a part of the first data chunk; and

flushing the first data chunk from the buffer.

13. The method of claim 12 , wherein the at least one projection dataset comprises a first projection dataset, and wherein the first projection dataset comprises a first sorted subset of data of the canonical dataset.

14. The method of claim 13 , wherein the at least one projection dataset further comprises a second projection dataset, wherein the second projection dataset comprises a second sorted subset of data of the canonical dataset, and wherein the second sorted subset of data is different from the first sorted subset of data.

15. The method of claim 14 , wherein the first and second sorted subsets of data are selected and sorted based on different projection rules.

16. The method of claim 14 , wherein the second projection dataset is asynchronously updated based on the first data chunk.

17. The method of claim 16 , wherein asynchronously updating the first and second projection datasets includes selecting, based on projection rules applicable to the respective first and second projection datasets, portions of the first data chunk needed to update the respective first and second projection datasets.

18. The method of claim 14 , further comprising periodically compacting the first and second projection datasets.

19. 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 a first data chunk comprising an edit to a canonical dataset;
temporarily storing the first data chunk in a buffer;
asynchronously:
updating the canonical dataset based on the first data chunk; and
updating at least one projection dataset based on at least a part of the first data chunk; and

flushing the first data chunk from the buffer.

20. The non-transitory computer-readable media of claim 19 , wherein the at least one projection dataset comprises a first projection dataset, and wherein the first projection dataset comprises a first sorted subset of data of the canonical dataset.

Assignees

• Palantir Technologies Inc

Inventors

• Duffield Benjamin
• Casale Joshua
• Elliot Mark
• Sills Matthew
• Kruszewski Robert
• Ramsharan Rahij

Classifications

• G06F16/2282 Primary

  Tablespace storage structures; Management thereof · CPC title

• G06F16/248

  Presentation of query results · CPC title

• G06F16/2455

  Query execution · CPC title

• G06F16/24554

  Unary operations; Data partitioning operations · CPC title

• G06F16/2358

  Change logging, detection, and notification (replication G06F16/27) · CPC title