# US 12,222,943 B2 · Optimized data structures of a relational cache with a learning capability for accelerating query execution by a data system > Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt - Number: US 12,222,943 B2 - Document ID: US12222943B2 - Status: Granted - Kind: B2 - Application number: 18/343,427 - Filed: 2023-06-28 - Published: 2023-10-26 - Granted: 2025-02-11 - Earliest claimed: 2018-04-24 - Assignees: Dremio Corporation - Applicants: Dremio Corporation - Inventors: Tomer Shiran; Jacques Nadeau; Steven Michael Phillips - Web page: https://patentgrep.com/patent/US12222943B2 ## CPC - G06F 16/24542: {Plan optimisation} - G06F 16/2228: {Indexing structures} - G06F 16/24537: {of operators} - G06F 16/24549: {Run-time optimisation} - G06N 20/00: Machine learning - G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N) - G06N: COMPUTING ARRANGEMENTS BASED ON SPECIFIC COMPUTATIONAL MODELS ## Abstract A method performed by a data system includes automatically learning relationship(s) among datasets based on one or more of a user query or an observation of a data flow through the data system. The method further includes generating an optimized data structure based on the learned relationships among the datasets. The data system then modifies a query plan to obtain query results that satisfy a query by reading the optimized data structure in lieu of reading the datasets. ## Claims ### Claim 1 A computer-readable storage medium, excluding transitory signals and carrying instructions, which, when executed by at least one data processor of a data system, cause the data system to: automatically determine relationships among multiple datasets based on multiple virtual datasets, wherein each of the multiple virtual datasets includes a query and a reference to a dataset of the multiple datasets; generate an optimized data structure based on the relationships among the multiple datasets, wherein the optimized data structure is stored in a non-volatile memory of the data system; receive multiple queries; determine whether the optimized data structure includes one or more datasets in common with query plans for the multiple queries; modify each query plan that has the one or more datasets in common to read the optimized data structure stored in the non-volatile memory in lieu of reading the multiple datasets; and return query results that satisfy the multiple queries based on the modified query plans. ### Claim 2 (depends on 1) The computer-readable storage medium of claim 1, wherein to automatically determine relationships among the multiple datasets comprises causing the data system to: determine a relationship between two datasets based on a join between the two datasets as indicated in a query of a virtual dataset. ### Claim 3 (depends on 1) The computer-readable storage medium of claim 1, wherein to automatically determine relationships among the multiple datasets comprises causing the data system to: determine a relationship between two datasets based on a stated relationship included in a virtual dataset. ### Claim 4 (depends on 1) The computer-readable storage medium of claim 1, wherein the data system is further caused to, prior to each query plan being modified: autonomously generate the optimized data structure based on a determination that reading the optimized data structure in lieu of reading at least some datasets from multiple data sources improves processing of an expected workload, and wherein the expected workload is based on a quantity or frequency of queries included in the multiple virtual datasets. ### Claim 5 A non-transitory, computer-readable storage medium storing instructions, which, when executed by at least one data processor of a data system, cause the data system to: automatically determine relationships among multiple datasets based on queries processed by the data system or an observation of a data flow of the data system; generate an optimized data structure based on the relationships among the multiple datasets, wherein the optimized data structure is stored in a non-volatile memory of the data system; receive multiple queries; determine that the optimized data structure includes a particular dataset in common with a respective query plan of the each of the multiple queries; modify each respective query plan that has the particular dataset to read the optimized data structure stored in the non-volatile memory; and return query results that satisfy the multiple queries based on the modified query plans. ### Claim 6 (depends on 5) The non-transitory, computer-readable storage medium of claim 5, wherein to automatically determine the relationships among the multiple datasets comprises causing the data system to: determine the relationships among the multiple datasets based on a pattern of the queries received by the data system, wherein the optimized data structure is generated based on the pattern of queries. ### Claim 7 (depends on 5) The non-transitory, computer-readable storage medium of claim 5, wherein to automatically determine the relationships among the multiple datasets comprises causing the data system to: determine the relationships among the multiple datasets based on the data flow of the data system including a runtime statistic, wherein the optimized data structure is generated based on the runtime statistic. ### Claim 8 (depends on 5) The non-transitory, computer-readable storage medium of claim 5, wherein to automatically determine the relationships among the multiple datasets comprises causing the data system to: determine the relationships among the multiple datasets based on the data flow of the data system including a workload distribution, wherein the optimized data structure is generated based on the workload distribution. ### Claim 9 (depends on 5) The non-transitory, computer-readable storage medium of claim 5, wherein the optimized data structure is generated based on an aggregation of the multiple datasets. ### Claim 10 (depends on 5) The non-transitory, computer-readable storage medium of claim 5, wherein the optimized data structure preserves a quantity of records equal to a quantity of records of one of the multiple datasets. ### Claim 11 (depends on 5) The non-transitory, computer-readable storage medium of claim 5, wherein the multiple datasets include a fact table and multiple dimension tables, and wherein generating the optimized data structure comprises causing the data system to: preserve a quantity of records of the fact table even though any of the multiple dimension tables have a quantity of records different from the fact table. ### Claim 12 (depends on 11) The non-transitory, computer-readable storage medium of claim 11, wherein to automatically determine the relationships among the multiple datasets comprises causing the data system to: autonomously determining a fact-dimension relationship among the multiple datasets. ### Claim 13 (depends on 5) The non-transitory, computer-readable storage medium of claim 5, wherein the multiple queries include a first query and a second query, wherein a first query plan of the first query is associated with a different combination of datasets compared to a second query plan of the second query. ### Claim 14 (depends on 5) The non-transitory, computer-readable storage medium of claim 5, wherein the data system is further caused to, prior to automatically determining the relationships among the multiple datasets: processing the multiple datasets in response to the multiple queries. ### Claim 15 (depends on 5) The non-transitory, computer-readable storage medium of claim 5, wherein a query of the multiple queries refers to at least one of the multiple datasets that are contained in multiple data sources, the data system being further caused to: obtain the result without reading any of the multiple datasets from the multiple data sources. ### Claim 16 (depends on 5) The non-transitory, computer-readable storage medium of claim 5, wherein a query of the multiple queries refers to at least one of the multiple datasets that are contained in multiple data sources, the data system being further caused to: obtain the result by reading at least some of the multiple datasets from the multiple data sources in addition to reading the optimized data structure. ### Claim 17 (depends on 5) The non-transitory, computer-readable storage medium of claim 5, wherein the data system is caused to, prior to the query plan being modified: determine that a query of the multiple queries can be accelerated based on the optimized data structure stored in a cache of the data system. ### Claim 18 (depends on 5) The non-transitory, computer-readable storage medium of claim 5, wherein to automatically determine the relationships among the multiple datasets and to generate the optimized data structure occurs at runtime of one or more query executions. ### Claim 19 (depends on 5) The non-transitory, computer-readable storage medium of claim 5, wherein the multiple datasets correspond to multiple physical datasets, and wherein to modify the query plan comprises causing the data system to: expand one or more views of the multiple physical datasets or of other views so that the query plan refers only to the multiple physical datasets. ### Claim 20 (depends on 5) The non-transitory, computer-readable storage medium of claim 5, wherein the data system is further caused to, prior to the query plan being modified: autonomously generate the optimized data structure based on a determination that reading the optimized data structure in lieu of reading at least some dataset from multiple data sources improves processing of an expected workload. ### Claim 21 A method performed by a data system comprising: automatically determining relationships among multiple datasets based on queries processed by the data system or an observation of a data flow of the data system; generating an optimized data structure based on the relationships among the multiple datasets, wherein the optimized data structure is stored in a non-volatile memory of the data system; receiving multiple queries; determining whether the optimized data structure includes a particular dataset in common with a respective query plan of each of the multiple queries; modifying each respective query plan that has the particular dataset to read the optimized data structure stored in the non-volatile memory; and returning a respective query result that satisfies each of the multiple query based on a respective modified query plan. ### Claim 22 (depends on 21) The method of claim 21, wherein automatically determining the relationships among the multiple datasets comprises: determining the relationships among the multiple datasets based on a runtime statistic indicated in the data flow of the data system, wherein the optimized data structure is generated based on the runtime statistic. ### Claim 23 (depends on 22) The method of claim 22, wherein automatically determining the relationships among the multiple datasets comprises: determining the relationships among the multiple datasets based on a workload distribution indicated in the data flow of the data system, wherein the optimized data structure is generated based on the workload distribution.