Joining database tables

• US 9,875,277 B1
• Filed: 03/21/2016
• Issued: 01/23/2018
• Est. Priority Date: 01/18/2013
• Status: Active Grant

• Current Assignee: Microstrategy Incorporated
• Original Assignee: Microstrategy Incorporated
• Inventors: Kiryakov, Yuliyan, Li, Benjamin Z., Liao, Rixin
• Primary Examiner(s): Moser, Bruce
• Application Number:
  US15/075,385
• Time in Patent Office: 673 Days
• Field of Search: None
• CPC Class Codes: G06F 16/2453 Query optimisation
• CPC Class Codes: G06F 16/24537 of operators
• CPC Class Codes: G06F 16/24544 Join order optimisation
• CPC Class Codes: G06F 16/24552 Database cache management
• CPC Class Codes: G06F 16/2456 Join operations
• CPC Class Codes: G06F 16/284 Relational databases

Abstract

In one implementation, a query is received that is related to data stored in a database that is implemented in computer memory. Based on the received query, attributes of data stored in the database that are relevant to generating a response to the received query are identified. Information that is indicative of attributes for which values are recorded in different tables included in the database is accessed. Based on having accessed this information, tables included in the database that record values for the attributes identified as being relevant to generating a response to the received query are identified. These tables then are joined to create, within computer memory, a new table that reflects relationships between values of attributes identified as being relevant to generating a response to the received query.

Claims

1. A computer-implemented method comprising:

receiving a query related to data stored in a database that is implemented in computer memory and that includes multiple different tables, where individual ones of the tables include values for attributes of data stored in the database;

based on the received query, identifying a filter to be applied to values of a particular attribute of data stored in the database;

accessing information that is indicative of attributes for which values are included in the different tables included in the database;

based on accessing the information indicative of the attributes for which values are included in the different tables included in the database, identifying a particular table that includes values for one or more attributes for applying the filter to values of the particular attribute;

applying the filter to the values of the particular attribute included in the particular table to generate a filtered particular table;

based on the received query, identifying additional attributes of data stored in the database that are relevant to generating a response to the received query;

based on accessing the information indicative of the attributes for which values are included in the different tables included in the database, identifying one or more additional tables that include values for the additional attributes identified as being relevant to generating a response to the received query, comprising;

selecting a first attribute from among the additional attributes identified as being relevant to generating a response to the received query;

identifying a first table included in the database that includes values for the first attribute;

selecting a second attribute from among the additional attributes identified as being relevant to generating a response to the received query; and

identifying a second table included in the database that includes values for the second attribute; and

joining the filtered particular table to the one or more additional tables to create, within computer memory, a new table that reflects relationships between filtered values of the particular attribute and additional attributes identified as being relevant to generating a response to the received query, comprising;

joining the filtered particular table to the one or more additional tables comprises joining the first and second tables to create a new table that reflects relationships between values of the first attribute and values of the second attribute.

2. The method of claim 1, wherein:

identifying a second table included in the database that includes values for the second attribute comprises;

identifying a second table included in the database that includes values for the second attribute that cannot be joined directly to the first table; and

identifying at least one intermediate table for joining the second table to the first table, and

joining the first and second tables to create a new table that reflects relationships between values of the first attribute and values of the second attribute comprises;

joining the at least one intermediate table to the first table to create an intermediary table; and

joining the second table to the intermediary table to create the new table that reflects relationships between values of the first attribute and values of the second attribute.

3. The method of claim 1, wherein identifying a second table included in the database that includes values for the second attribute comprises:

identifying multiple tables included in the database that include values for the second attribute;

determining that a particular one of the multiple tables identified as tables that include values for the second attribute can be joined directly to the first table; and

selecting the particular table as the second table.

4. The method of claim 3, wherein:

determining that a particular one of the multiple tables identified as tables that include values for the second attribute can be joined directly to the first table comprises determining that the particular table is the only one of the multiple tables identified as tables that include values for the second attribute that can be joined directly to the first table; and

selecting the particular table as the second table comprises selecting the particular table as the second table as a consequence of having determined that the particular table is the only one of the multiple tables identified as tables that include values for the second attribute that can be joined directly to the first table.

5. The method of claim 1, wherein:

identifying additional attributes of data stored in the database that are relevant to generating a response to the received query comprises;

identifying one or more attributes for which values are to be returned in a response to the received query;

identifying one or more attributes that are relevant to computing a metric to be returned in response to the received query;

identifying an attribute by which results of the metric are to be grouped; and

identifying one or more attributes as keys to a fact table that stores facts that are relevant to generating a response to the received query.

6. The method of claim 1, wherein:

the database comprises;

a first fact table that includes first facts associated with values of a first attribute; and

a second fact table that includes second facts associated with values of a second attribute,

identifying additional attributes of data stored in the database that are relevant to generating a response to the received query comprises;

identifying a first metric to be computed based on the first facts included in the first fact table;

identifying the first attribute as an attribute that is relevant to generating a response to the query;

identifying a second metric to be computed based on the second facts included in the second fact table; and

identifying the second attribute as an attribute that is relevant to generating a response to the query,

joining the filtered particular table to the one or more additional tables comprises joining tables included in the database identified as including values for attributes identified as being relevant to generating a response to the received query to create, within computer memory, a new table that reflects relationships between values for the first attribute and values for the second attribute, and

the method further comprises;

computing the first metric using values of the first attribute included in the new table as keys into the first fact table; and

computing the second metric using values of the second attribute included in the new table as keys into the second fact table.

7. A system comprising:

one or more computers; and

one or more storage devices storing instructions that are operable, when executed by the one or more computers, to cause the one or more computers to perform operations comprising;

receiving a query related to data stored in a database that is implemented in computer memory and that includes multiple different tables, where individual ones of the tables include values for attributes of data stored in the database;

based on the received query, identifying a filter to be applied to values of a particular attribute of data stored in the database;

accessing information that is indicative of attributes for which values are included in the different tables included in the database;

based on accessing the information indicative of the attributes for which values are included in the different tables included in the database, identifying a particular table that includes values for one or more attributes for applying the filter to values of the particular attribute;

applying the filter to the values of the particular attribute included in the particular table to generate a filtered particular table;

based on the received query, identifying additional attributes of data stored in the database that are relevant to generating a response to the received query, comprising;

identifying one or more attributes for which values are to be returned in a response to the received query;

identifying one or more attributes that are relevant to computing a metric to be returned in response to the received query;

identifying an attribute by which results of the metric are to be grouped; and

identifying one or more attributes as keys to a fact table that stores facts that are relevant to generating a response to the received query;

based on accessing the information indicative of the attributes for which values are included in the different tables included in the database, identifying one or more additional tables that include values for the additional attributes identified as being relevant to generating a response to the received query; and

joining the filtered particular table to the one or more additional tables to create, within computer memory, a new table that reflects relationships between filtered values of the particular attribute and additional attributes identified as being relevant to generating a response to the received query.

8. The system of claim 7, wherein:

identifying one or more additional tables that include values for the additional attributes identified as being relevant to generating a response to the received query comprises;

selecting a first attribute from among the additional attributes identified as being relevant to generating a response to the received query;

identifying a first table included in the database that includes values for the first attribute;

selecting a second attribute from among the additional attributes identified as being relevant to generating a response to the received query; and

identifying a second table included in the database that includes values for the second attribute, and

joining the filtered particular table to the one or more additional tables comprises joining the first and second tables to create a new table that reflects relationships between values of the first attribute and values of the second attribute.

9. The system of claim 8, wherein:

identifying a second table included in the database that includes values for the second attribute comprises;

identifying a second table included in the database that includes values for the second attribute that cannot be joined directly to the first table; and

identifying at least one intermediate table for joining the second table to the first table, and

joining the first and second tables to create a new table that reflects relationships between values of the first attribute and values of the second attribute comprises;

joining the at least one intermediate table to the first table to create an intermediary table; and

joining the second table to the intermediary table to create the new table that reflects relationships between values of the first attribute and values of the second attribute.

10. The system of claim 8, wherein identifying a second table included in the database that includes values for the second attribute comprises:

identifying multiple tables included in the database that include values for the second attribute;

determining that a particular one of the multiple tables identified as tables that include values for the second attribute can be joined directly to the first table; and

selecting the particular table as the second table.

11. The system of claim 10, wherein:

determining that a particular one of the multiple tables identified as tables that include values for the second attribute can be joined directly to the first table comprises determining that the particular table is the only one of the multiple tables identified as tables that include values for the second attribute that can be joined directly to the first table; and

selecting the particular table as the second table comprises selecting the particular table as the second table as a consequence of having determined that the particular table is the only one of the multiple tables identified as tables that include values for the second attribute that can be joined directly to the first table.

12. The system of claim 7, wherein:

the database comprises;

a first fact table that includes first facts associated with values of a first attribute; and

a second fact table that includes second facts associated with values of a second attribute,

identifying additional attributes of data stored in the database that are relevant to generating a response to the received query comprises;

identifying a first metric to be computed based on the first facts included in the first fact table;

identifying the first attribute as an attribute that is relevant to generating a response to the query;

identifying a second metric to be computed based on the second facts included in the second fact table; and

identifying the second attribute as an attribute that is relevant to generating a response to the query,

joining the filtered particular table to the one or more additional tables comprises joining tables included in the database identified as including values for attributes identified as being relevant to generating a response to the received query to create, within computer memory, a new table that reflects relationships between values for the first attribute and values for the second attribute, and

the operations further comprise;

computing the first metric using values of the first attribute included in the new table as keys into the first fact table; and

computing the second metric using values of the second attribute included in the new table as keys into the second fact table.

13. A non-transitory computer-readable medium storing software comprising instructions executable by one or more computers which, upon such execution, cause the one or more computers to perform operations comprising:

receiving a query related to data stored in a database that is implemented in computer memory and that includes multiple different tables, where individual ones of the tables include values for attributes of data stored in the database, the database comprising;

a first fact table that includes first facts associated with values of a first attribute; and

a second fact table that includes second facts associated with values of a second attribute;

based on the received query, identifying a filter to be applied to values of a particular attribute of data stored in the database;

accessing information that is indicative of attributes for which values are included in the different tables included in the database;

based on accessing the information indicative of the attributes for which values are included in the different tables included in the database, identifying a particular table that includes values for one or more attributes for applying the filter to values of the particular attribute;

applying the filter to the values of the particular attribute included in the particular table to generate a filtered particular table;

based on the received query, identifying additional attributes of data stored in the database that are relevant to generating a response to the received query, comprising;

identifying a first metric to be computed based on the first facts included in the first fact table;

identifying the first attribute as an attribute that is relevant to generating a response to the query;

identifying a second metric to be computed based on the second facts included in the second fact table; and

identifying the second attribute as an attribute that is relevant to generating a response to the query;

based on accessing the information indicative of the attributes for which values are included in the different tables included in the database, identifying one or more additional tables that include values for the additional attributes identified as being relevant to generating a response to the received query;

joining the filtered particular table to the one or more additional tables to create, within computer memory, a new table that reflects relationships between filtered values of the particular attribute and additional attributes identified as being relevant to generating a response to the received query, comprising;

joining tables included in the database identified as including values for attributes identified as being relevant to generating a response to the received query to create, within computer memory, a new table that reflects relationships between values for the first attribute and values for the second attribute;

computing the first metric using values of the first attribute included in the new table as keys into the first fact table; and

computing the second metric using values of the second attribute included in the new table as keys into the second fact table.

14. The medium of claim 13, wherein:

identifying one or more additional tables that include values for the additional attributes identified as being relevant to generating a response to the received query comprises;

selecting a first attribute from among the additional attributes identified as being relevant to generating a response to the received query;

identifying a first table included in the database that includes values for the first attribute;

selecting a second attribute from among the additional attributes identified as being relevant to generating a response to the received query; and

identifying a second table included in the database that includes values for the second attribute, and

joining the filtered particular table to the one or more additional tables comprises joining the first and second tables to create a new table that reflects relationships between values of the first attribute and values of the second attribute.

15. The medium of claim 14, wherein:

identifying a second table included in the database that includes values for the second attribute comprises;

identifying a second table included in the database that includes values for the second attribute that cannot be joined directly to the first table; and

identifying at least one intermediate table for joining the second table to the first table, and

joining the first and second tables to create a new table that reflects relationships between values of the first attribute and values of the second attribute comprises;

joining the at least one intermediate table to the first table to create an intermediary table; and

joining the second table to the intermediary table to create the new table that reflects relationships between values of the first attribute and values of the second attribute.

16. The medium of claim 14, wherein identifying a second table included in the database that includes values for the second attribute comprises:

identifying multiple tables included in the database that include values for the second attribute;

determining that a particular one of the multiple tables identified as tables that include values for the second attribute can be joined directly to the first table; and

selecting the particular table as the second table.

17. The medium of claim 13, wherein:

identifying additional attributes of data stored in the database that are relevant to generating a response to the received query comprises;

identifying one or more attributes for which values are to be returned in a response to the received query;

identifying one or more attributes that are relevant to computing a metric to be returned in response to the received query;

identifying an attribute by which results of the metric are to be grouped; and

identifying one or more attributes as keys to a fact table that stores facts that are relevant to generating a response to the received query.