Joining database tables

• US 9,292,571 B1
• Filed: 01/18/2013
• Issued: 03/22/2016
• 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:
  US13/745,534
• Time in Patent Office: 1,159 Days
• US Class Current: 1/1
• 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 attributes of data stored in the database that are relevant to generating a response to the received query;

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

identifying tables included in the database that include values for the attributes identified as being relevant to generating a response to the received query based on having accessed the information indicative of the attributes for which values are included in the different tables included in the database includes;

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

based on having accessed the information indicative of the attributes for which values are included in the different tables included in the database, identifying a first table included in the database that includes values for the first attribute,

selecting a second attribute from among the attributes identified as being relevant to generating a response to the received query, where the second attribute is different from the first attribute and values for the second attribute are not included in the first table, and

based on having accessed the information indicative of the attributes for which values are included in the different tables included in the database, identifying a second table included in the database that includes values for the second attribute includes;

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

based on having accessed the information indicative of the attributes for which values are included in the different tables included in the database, identifying at least one intermediate table for joining the second table to the first table from among the tables included in the database; and

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 of attributes identified as being relevant to generating a response to the received query includes 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 includes;

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.

2. 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 attributes of data stored in the database that are relevant to generating a response to the received query;

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

identifying tables included in the database that include values for the attributes identified as being relevant to generating a response to the received query based on having accessed the information indicative of the attributes for which values are included in the different tables included in the database includes;

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

based on having accessed the information indicative of the attributes for which values are included in the different tables included in the database, identifying a first table included in the database that includes values for the first attribute,

selecting a second attribute from among the attributes identified as being relevant to generating a response to the received query, where the second attribute is different from the first attribute and values for the second attribute are not included in the first table, and

identifying a second table included in the database that includes values for the second attribute based on having accessed the information indicative of the attributes for which values are included in the different tables included in the database includes;

based on having accessed the information indicative of the attributes for which values are included in the different tables included in the database, 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; and

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 of attributes identified as being relevant to generating a response to the received query includes 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.

3. The method of claim 2 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 includes 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 includes 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.

4. 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 attributes of data stored in the database that are relevant to generating a response to the received query;

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

identifying tables included in the database that include values for the attributes identified as being relevant to generating a response to the received query based on having accessed the information indicative of the attributes for which values are included in the different tables included in the database includes;

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

based on having accessed the information indicative of the attributes for which values are included in the different tables included in the database, identifying a first table included in the database that includes values for the first attribute,

selecting a second attribute from among the attributes identified as being relevant to generating a response to the received query, where the second attribute is different from the first attribute and values for the second attribute are not included in the first table, and

identifying a second table included in the database that includes values for the second attribute based on having accessed the information indicative of the attributes for which values are included in the different tables included in the database includes;

based on having accessed the information indicative of the attributes for which values are included in the different tables included in the database, identifying multiple tables included in the database that include values for the second attribute;

identifying, from among the multiple tables identified as tables that include values for the second attribute, multiple tables as tables that can be joined directly to the first table;

determining, for each table identified as a table that includes values for the second attribute that can be joined directly to the first table, a number of attributes identified as being relevant to generating a response to the received query for which values are included in the table other than the second attribute and any attributes identified as being relevant to generating a response to the received query for which values are included in the first table;

based on having determined, for each table identified as a table that includes values for the second attribute that can be joined directly to the first table, the number of attributes identified as being relevant to generating a response to the received query for which values are included in the table other than the second attribute and any attributes identified as being relevant to generating a response to the received query for which values are included in the first table, determining that a particular one of the tables identified as tables that include values for the second attribute that can be joined directly to the first table includes values for more attributes identified as being relevant to generating a response to the received query other than the second attribute and any attributes identified as being relevant to generating a response to the received query for which values are included in the first table than any of the other 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 as a consequence of having determined that the particular table includes values for more attributes identified as being relevant to generating a response to the received query other than the second attribute and any attributes identified as being relevant to generating a response to the received query for which values are included in the first table than any of the other tables identified as tables that include values for the second attribute that can be joined directly to the first table; and

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 of attributes identified as being relevant to generating a response to the received query includes 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.

5. 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 attributes of data stored in the database that are relevant to generating a response to the received query;

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

identifying tables included in the database that include values for the attributes identified as being relevant to generating a response to the received query based on having accessed the information indicative of the attributes for which values are included in the different tables included in the database includes;

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

based on having accessed the information indicative of the attributes for which values are included in the different tables included in the database, identifying a first table included in the database that includes values for the first attribute,

selecting a second attribute from among the attributes identified as being relevant to generating a response to the received query, where the second attribute is different from the first attribute and values for the second attribute are not included in the first table, and

identifying a second table included in the database that includes values for the second attribute based on having accessed the information indicative of the attributes for which values are included in the different tables included in the database includes;

based on having accessed the information indicative of the attributes for which values are included in the different tables included in the database, identifying multiple tables included in the database that include values for the second attribute;

identifying, from among the multiple tables identified as tables that include values for the second attribute, multiple tables as tables that can be joined directly to the first table;

determining, for each table identified as a table that includes values for the second attribute that can be joined directly to the first table, a number of attributes identified as being relevant to generating a response to the received query for which values are included in the table other than the second attribute and any attributes identified as being relevant to generating a response to the received query for which values are included in the first table;

based on having determined, for each table identified as a table that includes values for the second attribute that can be joined directly to the first table, the number of attributes identified as being relevant to generating a response to the received query for which values are included in the table other than the second attribute and any attributes identified as being relevant to generating a response to the received query for which values are included in the first table, identifying multiple tables that include values for more attributes identified as being relevant to generating a response to the received query other than the second attribute and any attributes identified as being relevant to generating a response to the received query for which values are included in the first table than any of the other tables identified as tables that include values for the second attribute that can be joined directly to the first table;

determining that a particular one of the tables identified as tables that include values for the second attribute, that can be joined directly to the first table, and that include values for more attributes identified as being relevant to generating a response to the received query other than the second attribute and any attributes identified as being relevant to generating a response to the received query for which values are included in the first table than any of the other tables identified as tables that include values for the second attribute that can be joined directly to the first table includes values for fewer attributes than any of the other tables identified as tables that include values for the second attribute, that can be joined directly to the first table, and that include values for more attributes identified as being relevant to generating a response to the received query other than the second attribute and any attributes identified as being relevant to generating a response to the received query for which values are included in the first table than any of the other 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 a consequence of having determined that the particular table includes values for fewer attributes than any of the other tables identified as tables that include values for the second attribute, that can be joined directly to the first table, and that include values for more attributes identified as being relevant to generating a response to the received query other than the second attribute and any attributes identified as being relevant to generating a response to the received query for which values are included in the first table than any of the other tables identified as tables that include values for the second attribute that can be joined directly to the first table; and

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 of attributes identified as being relevant to generating a response to the received query includes 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.

6. 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 attributes of data stored in the database that are relevant to generating a response to the received query based on the received query includes;

identifying a filter to be applied to values of a first attribute of data stored in the database, and

identifying a second attribute that is relevant to generating a response to the received query includes identifying another filter to be applied to values of a second 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;

identifying tables included in the database that include values for the attributes identified as being relevant to generating a response to the received query based on having accessed the information indicative of the attributes for which values are included in the different tables included in the database includes;

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

identifying a second table that includes values for the second attribute identified as being relevant to generating a response to the received query based on having accessed the information indicative of the attributes for which values are included in the different tables included in the database includes identifying a second table that includes values for one or more attributes for applying the other filter to values of the second attribute; and

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 of attributes identified as being relevant to generating a response to the received query includes;

applying the filter to the values of the first attribute included in the first table to generate a filtered first table, and

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

applying the other filter to the values of the second attribute included in the second table to generate a filtered second table, and

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

7. The method of claim 6 wherein:

identifying attributes of data stored in the database that are relevant to generating a response to the received query based on the received query includes identifying one or more additional filters to be applied to values of one or more additional attributes of data stored in the database; and

identifying a second table that includes values for one or more attributes for applying the other filter to values of the second attribute includes;

identifying multiple tables that include values for one or more attributes for applying the other filter to values of the second attribute,

determining, for each table identified as including values for one or more attributes for applying the other filter to values of the second attribute, a number of the one or more additional filters that can be applied to the table,

determining, for each table identified as including values for one or 10 more attributes for applying the other filter to values of the second attribute, a cost associated with joining the table to the first table,

computing, for each table identified as including values for one or more attributes for applying the other filter to values of the second attribute, a ratio of the number of additional filters that can be applied to the table to the cost associated with joining the table to the first table,

determining that the ratio computed for a particular one of the tables identified as including values for one or more attributes for applying the other filter to the values of the second attribute is greater than the ratios computed for the other tables identified as including values for one or more attributes for applying the other filter to the values of the second attribute, and

selecting the particular table as the second table as a consequence of having determined that the ratio computed for a particular one of the tables identified as including values for one or more attributes for applying the other filter to the values of the second attribute is greater than the ratios computed for the other tables identified as including values for one or more attributes for applying the other filter to the values of the second attribute.

8. The method of claim 6 wherein:

identifying attributes of data stored in the database that are relevant to generating a response to the received query based on the received query includes identifying one or more additional filters to be applied to values of one or more additional attributes of data stored in the database; and

identifying a second table that includes values for one or more attributes for applying the other filter to values of the second attribute includes;

identifying multiple tables that include values for one or more attributes for applying the other filter to values of the second attribute,

determining, for each table identified as including values for one or more attributes for applying the other filter to values of the second attribute, a number of the one or more additional filters that can be applied to the table,

determining, for each table identified as including values for one or more attributes for applying the other filter to values of the second attribute, a cost associated with joining the table to the first table,

computing, for each table identified as including values for one or more attributes for applying the other filter to values of the second attribute, a ratio of the number of additional filters that can be applied to the table to the cost associated with joining the table to the first table,

identifying multiple of the tables identified as including values for one or more attributes for applying the other filter to the values of the second attribute for which the computed ratios are greater than the ratios computed for the other tables identified as including values for one or more attributes for applying the other filter to the values of the second attribute,

determining that only a particular one of the tables identified as including values for one or more attributes for applying the other filter to the values of the second attribute for which the computed ratios are greater than the ratios computed for the other tables identified as including values for one or more attributes for applying the other filter to the values of the second attribute can be joined directly to the first table, and

selecting the particular table as the second table as a consequence of having determined that only the particular table can be joined directly to the first table.

9. The method of claim 6 wherein:

identifying attributes of data stored in the database that are relevant to generating a response to the received query based on the received query includes identifying one or more additional filters to be applied to values of one or more additional attributes of data stored in the database; and

identifying a second table that includes values for one or more attributes for applying the other filter to values of the second attribute includes;

identifying multiple tables that include values for one or more attributes for applying the other filter to values of the second attribute,

determining, for each table identified as including values for one or more attributes for applying the other filter to values of the second attribute, a number of the one or more additional filters that can be applied to the table,

determining, for each table identified as including values for one or more attributes for applying the other filter to values of the second attribute, a cost associated with joining the table to the first table,

computing, for each table identified as including values for one or more attributes for applying the other filter to values of the second attribute, a ratio of the number of additional filters that can be applied to the table to the cost associated with joining the table to the first applied to the table,

identifying multiple of the tables identified as including values for one or more attributes for applying the other filter to the values of the second attribute for which the computed ratios are greater than the ratios computed for the other tables identified as including values for one or more attributes for applying the other filter to the values of the second attribute,

determining that multiple of the tables identified as including values for one or more attributes for applying the other filter to the values of the second attribute for which the computed ratios are greater than the ratios computed for the other tables identified as including values for one or more attributes for applying the other filter to the values of the second attribute can be joined directly to the first table,

determining, for each table identified as including values for one or more attributes for applying the other filter to the values of the second attribute for which the computed ratios are greater than the ratios computed for the other tables identified as including values for one or more attributes for applying the other filter to the values of the second attribute that can be joined directly to the first table, a number of attributes identified as being relevant to generating a response to the received query for which values are included in the table other than the second attribute and any attributes identified as being relevant to generating a response to the received query for which values are included in the first table,

based on having determined, for each table identified as including values for one or more attributes for applying the other filter to the values of the second attribute for which the computed ratios are greater than the ratios computed for the other tables identified as including values for one or more attributes for applying the other filter to the values of the second attribute that can be joined directly to the first table,

identifying, from among the tables identified as including values for one or more attributes for applying the other filter to the values of the second attribute for which the computed ratios are greater than the ratios computed for the other tables identified as including values for one or more attributes for applying the other filter to the values of the second attribute that can be joined directly to the first table, a particular table as including values for the greatest number of attributes identified as being relevant to generating a response to the received query other than the second attribute and any attributes identified as being relevant to generating a response to the received query for which values are included in the first table, and

selecting the particular table as the second table as a consequence of having determined that the particular table includes values for the greatest number of attributes identified as being relevant to generating a response to the received query other than the second attribute and any attributes identified as being relevant to generating a response to the received query for which values are included in the first table.

10. The method of claim 6 wherein:

identifying attributes of data stored in the database that are relevant to generating a response to the received query based on the received query includes identifying one or more additional filters to values of one or more additional attributes of data stored in the database; and

identifying a second table that includes values for one or more attributes for applying the other filter to values of the second attribute includes;

identifying multiple tables that include values for one or more attributes for applying the other filter to values of the second attribute,

determining, for each table identified as including values for one or more attributes for applying the other filter to values of the second attribute, a number of the one or more additional filters that can be applied to the table,

determining, for each table identified as including values for one or more attributes for applying the other filter to values of the second attribute, a cost associated with joining the table to the first table,

computing, for each table identified as including values for one or more attributes for applying the other filter to values of the second attribute, a ratio of the number of additional filters that can be applied to the table to the cost associated with joining the table to the first table,

identifying multiple of the tables identified as including values for one or more attributes for applying the other filter to the values of the second attribute for which the computed ratios are greater than the ratios computed for the other tables identified as including values for one or more attributes for applying the other filter to the values of the second attribute,

determining that multiple of the tables identified as including values for one or more attributes for applying the other filter to the values of the second attribute for which the computed ratios are greater than the ratios computed for the other tables identified as including values for one or more attributes for applying the other filter to the values of the second attribute can be joined directly to the first table,

determining, for each table identified as including values for one or more attributes for applying the other filter to the values of the second attribute for which the computed ratios are greater than the ratios computed for the other tables identified as including values for one or more attributes for applying the other filter to the values of the second attribute that can be joined directly to the first table, a number of attributes identified as being relevant to generating a response to the received query for which values are included in the table other than the second attribute and any attributes identified as being relevant to generating a response to the received query for which values are included in the first table,

based on having determined, for each table identified as including values for one or more attributes for applying the other filter to the values of the second attribute for which the computed ratios are greater than the ratios computed for the other tables identified as including values for one or more attributes for applying the other filter to the values of the second attribute that can be joined directly to the first table, identifying, from among the tables identified as including values for one or more attributes for applying the other filter to the values of the second attribute for which the computed ratios are greater than the ratios computed for the other tables identified as including values for one or more attributes for applying the other filter to the values of the second attribute that can be joined directly to the first table, multiple tables as including values for more attributes identified as being relevant to generating a response to the received query other than the second attribute and any attributes identified as being relevant to generating a response to the received query for which values are included in the first table than any of the other tables identified as including values for one or more attributes for applying the other filter to the values of the second attribute for which the computed ratios are greater than the ratios computed for the other tables identified as including values for one or more attributes for applying the other filter to the values of the second attribute that can be joined directly to the first table,

determining, for each table identified as including values for more attributes identified as being relevant to generating a response to the received query other than the second attribute and any attributes identified as being relevant to generating a response to the received query for which values are included in the first table than any of the other tables identified as including values for one or more attributes for applying the other filter to the values of the second attribute for which the computed ratios are greater than the ratios computed for the other tables identified as including values for one or more attributes for applying the other filter to the values of the second attribute that can be joined directly to the first table, a number of attributes identified as being relevant to generating a response to the received query for which values are included in the table other than the second attribute and any attributes identified as being relevant to generating a response to the received query for which values are included in the first table;

based on having determined, for each table identified as including values for more attributes identified as being relevant to generating a response to the received query other than the second attribute and any attributes identified as being relevant to generating a response to the received query for which values are included in the first table than any of the other tables identified as including values for one or more attributes for applying the other filter to the values of the second attribute for which the computed ratios are greater than the ratios computed for the other tables identified as including values for one or more attributes for applying the other filter to the values of the second attribute that can be joined directly to the first table, the number of attributes identified as being relevant to generating a response to the received query for which values are included in the table other than the second attribute and any attributes identified as being relevant to generating a response to the received query for which values are included in the first table, identifying multiple tables that include values for more attributes identified as being relevant to generating a response to the received query other than the second attribute and any attributes identified as being relevant to generating a response to the received query for which values are included in the first table than any of the other tables identified as tables that include values for the second attribute that can be joined directly to the first table;

determining that a particular one of the tables identified as tables that include values for more attributes identified as being relevant to generating a response to the received query other than the second attribute and any attributes identified as being relevant to generating a response to the received query for which values are included in the first table than any of the other tables identified as tables that include values for the second attribute that can be joined directly to the first table includes values for fewer attributes than any of the other tables identified as tables that include values for more attributes identified as being relevant to generating a response to the received query other than the second attribute and any attributes identified as being relevant to generating a response to the received query for which values are included in the first table than any of the other 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 a consequence of having determined that the particular table includes values for fewer attributes than any of the other tables identified as tables that include values for more attributes identified as being relevant to generating a response to the received query other than the second attribute and any attributes identified as being relevant to generating a response to the received query for which values are included in the first table than any of the other tables identified as tables that include values for the second attribute that can be joined directly to the first table.

11. 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 attributes of data stored in the database that are relevant to generating a response to the received query;

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

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

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 of attributes identified as being relevant to generating a response to the received query;

identifying, based on the received query, a first filter to be applied to values of a first attribute that is related to a particular attribute such that application of the first filter returns values for the particular attribute that are related to at least one value of the first attribute specified by the first filter;

identifying, based on the received query, other filters to be applied to values of other attributes that are related to the particular attribute such that application of each other filter returns values for the particular attribute that are related to at least one value of another attribute specified by the other filter;

determining that values for the particular attribute that are returned responsive to applying the first filter and that values for the particular attribute that are returned responsive to applying the other filters can be represented as bit vector filters on a lookup table for the particular attribute included in the database;

based on having accessed the information indicative of the attributes for which values are included in the different tables included in the database,

identifying multiple tables included in the database that include values for the first attribute and the particular attribute;

determining, for each table identified as including values for the first attribute and the particular attribute, a number of the other attributes for which values are included in the table;

based on having determined, for each table identified as including values for the first attribute and the particular attribute, the number of the other attributes for which values are included in the table, determining that a particular one of the tables identified as including values for the first attribute and the particular attribute includes a greater number of the other attributes than any of the other tables identified as including values for the first attribute and the particular attribute;

applying the first filter to values of the first attribute included in the particular table;

representing results of applying the first filter to values of the first attribute included in the particular table as a first bit vector filter on the lookup table for the particular attribute;

for each of the other attributes for which values are included in the particular table;

applying a corresponding one of the other filters to values of the other attribute included in the particular table, and

representing results of applying the corresponding other filter to values of the other attribute included in the particular table as another bit vector filter on the lookup table for the particular attribute;

for each of the other attributes for which values are not included in the particular table;

applying a corresponding one of the other filters to values of the other attribute included in a table that includes values for the other attribute and the particular attribute, and

representing results of applying the corresponding other filter to values of the other attribute included in the table as an additional bit vector filter on the lookup table for the particular attribute;

combining the bit vector filters on the lookup table for the particular attribute representing the results of applying the first filter and the other filters to create a new bit vector filter on the lookup table for the particular attribute; and

applying the new bit vector filter to the lookup table for the particular attribute to generate a filtered lookup table for the particular attribute, wherein;

joining the tables included in the database identified as including values for the attributes identified as being relevant to generating a response to the received query includes joining the filtered lookup table to a table including values for at least one attribute identified as being relevant to generating a response to the received query.

12. The method of claim 11 further comprising:

storing, in computer memory, the first bit vector filter on the lookup table for the particular attribute;

receiving an additional query related to data stored in the database;

determining, based on the additional received query, that the first filter is relevant to generating a response to the additional received query; and

accessing the stored first bit vector filter on the lookup table for the particular attribute as part of generating a response to the additional received query as a consequence of having determined that the first filter is relevant to generating a response to the additional received query.

13. 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 attributes of data stored in the database that are relevant to generating a response to the received query;

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

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

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 of attributes identified as being relevant to generating a response to the received query;

identifying, based on the received query, a filter to be applied to values of at least a first attribute of data stored in the database that is related to a second attribute of data stored in the database;

determining that values for both the first and second attributes are included in the new table; and

applying the filter to values of the first attribute included in the new table to create, within computer memory, a filtered new table that reflects relationships between the filtered values of the first attribute and values of the second attribute.

14. 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 including (i) a first fact table that includes first facts associated with values of a first attribute, and (ii) a second fact table that includes second facts associated with values of a second attribute;

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

identifying, based on the received query, a first metric to be computed based on the first facts included in the first fact table,

as a consequence of identifying the first metric as a 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 based on the association of the first facts with values of the first attribute included in the first fact table,

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

as a consequence of identifying the second metric as a metric to be computed based on the second facts included in the second fact table, identifying the second attribute as an attribute that is relevant to generating a response to the query based on the association of the second facts with values of the second attribute included in the second fact table;

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

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

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 of attributes identified as being relevant to generating a response to the received query includes 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.

15. 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 attributes of data stored in the database that are relevant to generating a response to the received query based on the received query includes;

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;

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

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

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 of attributes identified as being relevant to generating a response to the received query.