US-12619599-B2 - Projections for big database systems

US12619599B2US 12619599 B2US12619599 B2US 12619599B2US-12619599-B2

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.

Inventors

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

Assignees

Palantir Technologies Inc.

Dates

Publication Date: 20260505
Application Date: 20230303

Claims (18)

1 . A system comprising: one or more non-transitory computer readable storage mediums configured to store: program instructions; a canonical dataset; one or more projection datasets; and a buffer; and one or more processors configured to execute the program instructions to cause the system to: access a first data chunk comprising an edit to the canonical dataset; temporarily store the first data chunk in the buffer; receive a query configured to execute on the canonical dataset; analyze the query to determine a requested result of the query; access the one or more projection datasets stored in the one or more non-transitory computer readable storage mediums to determine a selected projection dataset from among the one or more projection datasets to optimize query performance based on referencing projection rules associated with the one or more projection datasets to determine a projection rule that corresponds with the requested result, wherein the selected projection dataset is associated with the projection rule, the projection rule having been pre-applied to the selected projection dataset to obviate applying the projection rule to the selected projection dataset during query execution to reduce query execution time allowing the query to execute faster on the selected projection dataset than on other projection datasets of the one or more projection datasets to which the projection rule has not been pre-applied; combine the selected projection dataset with the buffer in the one or more non-transitory computer readable storage mediums to form a combined projection dataset with data governed by the projection rule; rewrite the query to execute on the combined projection dataset instead of the canonical dataset to produce the requested result of the query faster by executing on the combined projection dataset than by executing on the canonical dataset; execute the rewritten query on the combined projection dataset; and return the requested result.
2 . The system of claim 1 , wherein the one or more processors is further configured to execute the program instructions to cause the system to: combine the buffer with a second projection dataset asynchronously with combining the buffer to the selected projection dataset based on resource availability of the system to form a second combined projection dataset.
3 . The system of claim 1 , wherein the one or more processors is further configured to execute the program instructions to cause the system to: transform the combined projection dataset according to a projection rule set associated with the selected projection dataset.
4 . The system of claim 3 , wherein transforming the combined projection dataset includes one or more of sorting data contents of the combined projection dataset and compacting the data contents of the combined projection dataset.
5 . The system of claim 3 , wherein the one or more processors is further configured to execute the program instructions to cause the system to: combine the buffer with a second projection dataset to form a second combined projection dataset; and transform, according to a second projection rule set associated with the second projection dataset, the second combined projection dataset asynchronously with transforming the selected projection dataset based on resource availability of the system.
6 . The system of claim 1 , wherein the one or more processors is further configured to execute the program instructions to cause the system to: transform the buffer according to a projection rule set associated with the selected projection dataset, wherein transforming the buffer includes one or more of sorting data contents of the buffer and compacting the data contents of the buffer.
7 . The system of claim 1 , wherein the one or more processors is further configured to execute the program instructions to cause the system to: combine the buffer with the selected projection dataset by appending data contents of the buffer to data contents of the selected projection dataset.
8 . The system of claim 1 , wherein the one or more processors is further configured to execute the program instructions to cause the system to: combine the buffer with the selected projection dataset by appending less than all data contents of the buffer to data contents of the selected projection dataset based on at least a timestamp associated with the selected projection dataset indicating a time the selected projection dataset was previously updated and one or more timestamps associated with data in the buffer.
9 . The system of claim 1 , wherein the one or more processors is further configured to execute the program instructions to cause the system to: flush the first data chunk from the buffer.
10 . A computer-implemented method comprising: accessing a first data chunk comprising an edit to a canonical dataset; temporarily storing the first data chunk in a buffer; receiving a query configured to execute on the canonical dataset; analyzing the query to determine a requested result of the query; accessing one or more projection datasets stored in one or more non-transitory computer readable storage mediums to determine a selected projection dataset from among the one or more projection datasets to optimize query performance based on referencing projection rules associated with the one or more projection datasets to determine a projection rule that corresponds with the requested result, wherein the selected projection dataset is associated with the projection rule, the projection rule having been pre-applied to the selected projection dataset to obviate applying the projection rule to the selected projection dataset during query execution to reduce query execution time allowing the query to execute faster on the selected projection dataset than on other projection datasets of the one or more projection datasets to which the projection rule has not been pre-applied; combining the selected projection dataset with the buffer in the one or more non-transitory computer readable storage mediums to form a combined projection dataset with data governed by the projection rule; rewriting the query to execute on the combined projection dataset instead of the canonical dataset to produce the requested result of the query faster by executing on the combined projection dataset than by executing on the canonical dataset; executing the rewritten query on the combined projection dataset; and returning the requested result.
11 . The computer-implemented method of claim 10 further comprising: transforming the combined projection dataset according to a projection rule set associated with the selected projection dataset.
12 . The computer-implemented method of claim 10 further comprising: transforming the buffer according to a projection rule set associated with the selected projection dataset, wherein transforming the buffer includes one or more of sorting data contents of the buffer and compacting the data contents of the buffer.
13 . Non-transitory computer-readable media including computer-executable instructions that, when executed by a computing system, cause the computing system to perform operations comprising: accessing a first data chunk comprising an edit to a canonical dataset; temporarily storing the first data chunk in a buffer; receiving a query configured to execute on the canonical dataset; analyzing the query to determine a requested result of the query; accessing one or more projection datasets stored in one or more non-transitory computer readable storage mediums to determine a selected projection dataset from among the one or more projection datasets to optimize query performance based on referencing projection rules associated with the one or more projection datasets to determine a projection rule that corresponds with the requested result, wherein the selected projection dataset is associated with the projection rule, the projection rule having been pre-applied to the selected projection dataset to obviate applying the projection rule to the selected projection dataset during query execution to reduce query execution time allowing the query to execute faster on the selected projection dataset than on other projection datasets of the one or more projection datasets to which the projection rule has not been pre-applied; combining the selected projection dataset with the buffer in the one or more non-transitory computer readable storage mediums to form a combined projection dataset with data governed by the projection rule; rewriting the query to execute on the combined projection dataset instead of the canonical dataset to produce the requested result of the query faster by executing on the combined projection dataset than by executing on the canonical dataset; executing the rewritten query on the combined projection dataset; and returning the requested result.
14 . The non-transitory computer-readable media of claim 13 , wherein the computer-executable instructions, when executed by the computing system, further cause the computing system to perform operations comprising: transforming the combined projection dataset according to a projection rule set associated with the selected projection dataset.
15 . The non-transitory computer-readable media of claim 13 , wherein the computer-executable instructions, when executed by the computing system, further cause the computing system to perform operations comprising: transforming the buffer according to a projection rule set associated with the selected projection dataset, wherein transforming the buffer includes one or more of sorting data contents of the buffer and compacting the data contents of the buffer.
16 . The system of claim 1 , wherein the projection rule includes one or more of a data sorting rule, a data format rule, or a data aggregation rule.
17 . The computer-implemented method of claim 10 , wherein the projection rule includes one or more of a data sorting rule, a data format rule, or a data aggregation rule.
18 . The non-transitory computer-readable media of claim 13 , wherein the projection rule includes one or more of a data sorting rule, a data format rule, or a data aggregation rule.

Description

CROSS-REFERENCE TO RELATED APPLICATIONS This application is a continuation of U.S. patent application Ser. No. 17/444,715, filed on Aug. 9, 2021, and titled “PROJECTIONS FOR BIG DATABASE SYSTEMS,” which claims a priority benefit under 35 U.S.C. § 119 to U.S. Provisional Patent Application No. 63/067,596, filed on Aug. 19, 2020, and titled “PROJECTIONS FOR BIG DATABASE SYSTEMS.” The disclosures of each of the aforementioned applications are incorporated herein in their entireties for all purposes. Any and all applications for which a foreign or domestic priority claim is identified in the Application Data Sheet as filed with the present application are hereby incorporated by reference under 37 CFR 1.57. TECHNICAL FIELD The present disclosure relates to systems and techniques for data integration, analysis, and visualization. More specifically, projections for immutable versioned big database systems. BACKGROUND A database system may store large quantities of data. For example, a database system may store on the scale of petabytes to exabytes worth of data. However, such big database systems often require specialized architecture, management, processing, and/or maintenance methodologies in order to maintain the big database system, and there may be tradeoffs between different approaches. For example, some existing database systems, such as Online Analytical Processing (OLAP) systems, are designed for applying complex queries to large amounts of historical data and allow for rapid execution time by multiple simultaneous users or perspectives. In some cases, this can be accomplished using versioned datasets, which may improve query speed at the cost of write speed. In other words, the emphasis on response time to complex queries means that these OLAP database systems may not be able to provide the same level of performance with regards to rapidly writing to, and updating, datasets. In contrast, other database systems, such as Online Transactional Processing (OLTP) database systems, are designed for quickly processing a large volume of transactions that may comprise many different kinds of instructions (e.g., read, insert, update and delete). OLTP database systems are not designed specifically to rapidly execute complex queries and instead prioritize the rapid updating of datasets, allowing datasets to be written to and updated frequently with low latency and high data integrity. Accordingly, OLTP database systems are not designed specifically to rapidly execute complex queries and instead prioritize the rapid updating of datasets. Due to these tradeoffs between query performance and write performance, a decision usually has to be made between low latency complex querying or low latency editing. SUMMARY The systems, methods, and devices described herein each have several aspects, no single one of which is solely responsible for its desirable attributes. Without limiting the scope of this disclosure, several non-limiting features will now be discussed briefly. Designing and creating a database system that provides both low latency complex querying and low latency editing is a difficult task, especially when large amounts of data (e.g., petabytes, exabytes etc.) must be stored and queried, or when streaming data is involved. Furthermore, the use of versioned datasets for reducing the latency of complex querying (e.g., by storing multiple data copies) can greatly add to the complexity of the system and will often result in a tremendous increase in the amount of data being stored, more datasets that need to be updated, and additional processing needed to update the datasets. Thus, there exists a need for a database system which are capable of using versioned datasets to provide both low latency complex querying and low latency editing, and which allow for the use of streaming data. Described herein is a database system that may serve as a general data store that is capable of handling datasets or collections of data that are of varying sizes (e.g., from a hundred bytes to terabytes and larger) and formats (e.g., bytes for a table). The components of this database system cooperate and work together in a manner that enables both low-latency edits and low-latency reads for large scale OLAP-oriented database systems, thereby bridging the divide between OLAP and OLTP database systems. The database system may provide low-latency reads through the use of versioned datasets. In particular, multiple projection datasets can be generated and associated with a canonical dataset. Each projection dataset may contain a subset of the data in the canonical dataset and that data may be organized in a particular way depending on the configuration of the projection dataset. In various different scenarios, these projection datasets may provide faster querying over the canonical dataset, and they can be used instead for processing the query. Thus, depending on the query, the database system may be able to select and use the projection da