Query generation based on a logical data model

Patent metadata

Field	Value
Publication number	US-11176199-B2
Application number	US-201916373028-A
Country	US
Kind code	B2
Filing date	Apr 2, 2019
Priority date	Apr 2, 2018
Publication date	Nov 16, 2021
Grant date	Nov 16, 2021

Abstract

Systems and methods for query generation based on a logical data model are described. For example, methods may include accessing a first join graph representing tables in a database; receiving a first query that references data in two or more of the tables of the database; selecting a connected subgraph of the first join graph that includes the two or more tables referenced in the first query; generating multiple leaf queries that reference respective subject tables that are each a root table of the connected subgraph or a table including a measure referenced in the first query; generating a query graph that specifies joining of results from queries based on the multiple leaf queries to obtain a transformed query result; and invoking a transformed query on the database that is based on the query graph and the queries based on the multiple leaf queries to obtain the transformed query result.

First claim

What is claimed is:

1. A method comprising:
accessing a first join graph representing tables in a database, wherein the first join graph has vertices corresponding to respective tables in the database and directed edges corresponding to many-to-one join relationships;
receiving a first query that references data in two or more of the tables of the database;
selecting a connected subgraph of the first join graph that includes the two or more tables referenced in the first query;
generating multiple leaf queries that reference respective subject tables that are each a root table of the connected subgraph or a table including a measure referenced in the first query, wherein generating at least two of the leaf queries includes inserting a reference to a primary key column for a shared attribution dimension table of the respective subject tables of the at least two of the leaf queries;
generating a query graph that specifies joining of results from queries based on the multiple leaf queries to obtain a transformed query result for the first query, wherein the query graph has a single root node corresponding to the transformed query result;
invoking a transformed query on the database that is based on the query graph and the queries based on the multiple leaf queries to obtain the transformed query result; and
presenting data based on the transformed query result.

2. The method of claim 1 , comprising:
splitting one of the multiple leaf queries into leaf queries that are perfectly joinable with a respective leaf query of the multiple leaf queries, wherein the queries based on the multiple leaf queries include the leaf queries resulting from the split.

3. The method of claim 1 , wherein one of the multiple leaf queries includes a reference to an attribute in a dimension table that is referenced in the first query.

4. The method of claim 1 , wherein selecting the connected subgraph includes:
selecting an initial connected subgraph of the first join graph that includes the two or more tables referenced in the first query; and
selecting one or more additional attribution dimension tables for inclusion in the connected subgraph, wherein a first root table of the initial connected subgraph is directly connected to a non-shared dimension table that is referenced in the first query, and the one or more additional attribution dimension tables are shared between a second root table of the initial connected subgraph and the first root table.

5. The method of claim 1 , wherein selecting the connected subgraph includes:
biasing table selection to select paths that include tables referenced in the first query.

6. The method of claim 1 , wherein selecting the connected subgraph includes:
biasing table selection to select paths that include root tables of the first join graph.

7. The method of claim 1 , comprising:
decomposing a formula of the first query into component formulas;
pushing down the component formulas to one or more of the multiple leaf queries that reference a column referenced by at least one of the component formulas; and
composing a transformed formula in the single root node of the query graph based on results for the component formulas.

8. The method of claim 7 , wherein the formula is a non-composable formula.

9. The method of claim 7 , wherein the formula has multiple expression roots.

10. The method of claim 7 , wherein the formula includes an aggregation on a measure from a dimension table.

11. A system, comprising:
a network interface,
a processor, and
a memory, wherein the memory stores instructions executable by the processor to:
access a first join graph representing tables in a database, wherein the first join graph has vertices corresponding to respective tables in the database and directed edges corresponding to many-to-one join relationships;
receive a first query that references data in two or more of the tables of the database;
select a connected subgraph of the first join graph that includes the two or more tables referenced in the first query;
generate multiple leaf queries that reference respective subject tables that are each a root table of the connected subgraph or a table including a measure referenced in the first query, wherein generating at least two of the leaf queries includes inserting a reference to a primary key column for a shared attribution dimension table of the respective subject tables of the at least two of the leaf queries;
generate a query graph that specifies joining of results from queries based on the multiple leaf queries to obtain a transformed query result for the first query, wherein the query graph has a single root node corresponding to the transformed query result; and
invoke a transformed query on the database that is based on the query graph and the queries based on the multiple leaf queries to obtain the transformed query result.

12. The system of claim 11 , wherein the memory stores instructions executable by the processor to:
split one of the multiple leaf queries into leaf queries that are perfectly joinable with a respective leaf query of the multiple leaf queries, wherein the queries based on the multiple leaf queries include the leaf queries resulting from the split.

13. The system of claim 11 , wherein one of the multiple leaf queries includes a reference to an attribute in a dimension table that is referenced in the first query.

14. The system of claim 11 , wherein the memory stores instructions executable by the processor to select the connected subgraph by performing operations including:
selecting an initial connected subgraph of the first join graph that includes the two or more tables referenced in the first query; and
selecting one or more additional attribution dimension tables for inclusion in the connected subgraph, wherein a first root table of the initial connected subgraph is directly connected to a non-shared dimension table that is referenced in the first query, and the one or more additional attribution dimension tables are shared between a second root table of the initial connected subgraph and the first root table.

15. The system of claim 11 , wherein the memory stores instructions executable by the processor to select the connected subgraph by performing operations including:
biasing table selection to select paths that include tables referenced in the first query.

16. The system of claim 11 , wherein the memory stores instructions executable by the processor to select the connected subgraph by performing operations including:
biasing table selection to select paths that include root tables of the first join graph.

17. The system of claim 11 , wherein the memory stores instructions executable by the processor to:
decompose a formula of the first query into component formulas;
push down the component formulas to one or more of the multiple leaf queries that reference a column referenced by at least one of the component formulas; and
compose a transformed formula in the single root node of the query graph based on results for the component formulas.

18. The system of claim 17 , wherein the formula is a non-composable formula.

19. The system of claim 17 , wherein the formula has multiple expression roots.

20. A non-transitory computer-readable storage medium that includes instructions that, when executed by a processor, facilitate performance of operations comprising:
accessing a first join graph representing tables in a database, wherein the first join graph has vertices corresponding to respectiv

Assignees

• Thoughtspot Inc

Inventors

• Kothari Rakesh
• Prakash Amit
• Kumar Sandeep
• Bansal Archit
• Agarwal Vaibhav
• Sui Zhiquan
• Kwatra Swati

Classifications

• G06F16/24544 Primary

  Join order optimisation · CPC title

• G06F16/2456

  Join operations · CPC title

• G06F16/9024 Primary

  Graphs; Linked lists (G06F16/9027 takes precedence) · CPC title

• G06F16/2282

  Tablespace storage structures; Management thereof · CPC title

• G06F16/2458

  Special types of queries, e.g. statistical queries, fuzzy queries or distributed queries · CPC title