Querying multidimensional data with independent fact and dimension pipelines combined at query time

• US 8,244,667 B1
• Filed: 10/18/2007
• Issued: 08/14/2012
• Est. Priority Date: 10/18/2007
• Status: Active Grant

• Current Assignee: Google LLC (Alphabet Inc.)
• Original Assignee: Google Inc. (Alphabet Inc.)
• Inventors: Weinberger, Benjamin, Plakal, Manoj, Robinson, Will
• Primary Examiner(s): Trujillo, James
• Assistant Examiner(s): Mamillapalli, Pavan
• Application Number:
  US11/874,468
• Time in Patent Office: 1,762 Days
• Field of Search: 707/2, 707/3, 707/4, 707/5, 707/600, 707/603, 707/737, 707/754
• US Class Current: 707/603
• CPC Class Codes: G06F 16/24556 Aggregation; Duplicate elimination
• CPC Class Codes: G06F 16/283 Multi-dimensional databases or data warehouses, e.g. MOLAP or ROLAP

Abstract

Separate subsystems are dedicated to handle fact and dimension data storage and retrieval in an optimized manner. Each subsystem acquires, processes, and stores its data separately in a manner appropriate to the characteristics of that data. A query engine combines the data from each subsystem at query time. When a user queries the system, the query engine interacts with each of the subsystems to fetch the data needed to generate a single result set.

Claims

1. A method comprising:

at a first computing device, receiving a query, the query including grouping information and filtering information;

at the first computing device, producing, in response to the query, a result set from fact data, the fact data including keyed values and being stored at the first computing device, wherein the first computing device is optimized for the fact data, and wherein producing the result set includes;

receiving, from a second computing device, a key for accessing a value of the fact data, the key being identified from dimension data and based at least in part on the filtering information, the dimension data being stored at the second computing device, wherein the second computing device is optimized for the dimension data;

aggregating, from the fact data and based at least in part on the grouping information, a plurality of query results; and

filtering the aggregated query results using the key received from the second computing device; and

generating the result set based on the filtered query results.

2. The method of claim 1, where aggregating the query results comprises:

obtaining the fact data as incremental updates;

aggregating the updates into a number of predetermined groupings; and

storing the predetermined groupings in a first data structure.

3. The method of claim 2, where each update includes one or more key/value pairs.

4. The method of claim 2, further comprising obtaining dimension data at the second computing device, where obtaining the dimension data comprises:

obtaining the dimension data from one or more sources;

processing the dimension data based on characteristics of the dimension data; and

storing the processed dimension data in a second data structure.

5. The method of claim 1, further comprising:

providing, at the first computing device, detail values relating to the filtered query results; and

decorating the filter query results using the detail values such that the result set includes user readable result strings.

6. The method of claim 1, wherein:

the first computing device is optimized by operations comprising;

grouping one or more pre-formatted queries; and

executing the grouped queries according to a schedule, where a common calculation in the grouped queries is performed before the grouped queries are executed; and

the second computing device is optimized for query response time.

7. A system comprising:

one or more computing devices configured to perform operations comprising;

receiving a query, the query including grouping information and filtering information; and

responsive to the query, producing, using a fact subsystem and a dimension subsystem, a result set, the result set being produced from fact data and dimension data, the fact data including one or more keyed values, the dimension data including definitions of one or more keys of the fact data, wherein;

the dimension subsystem is optimized for the dimension data and is configured to perform first operations comprising;

storing the dimension data; and

identifying, from the dimension data and based at least in part on the filtering information, a key for accessing the fact data;

the fact subsystem is optimized for the fact data and is configured to perform second operations comprising;

storing the fact data;

aggregating, from the fact data and based at least in part on the grouping information, a plurality of query results; and

filtering the aggregated query results using the key identified by the dimension subsystem; and

the result set includes the filtered query results.

8. The system of claim 7, wherein the fact subsystem is operable for:

obtaining the fact data as incremental updates;

aggregating the updates into a number of predetermined groupings; and

storing the predetermined groupings in a first data structure.

9. The system of claim 8, where each update includes one or more key/value pairs.

10. The system of claim 8, wherein the dimension subsystem is operable for:

obtaining dimension data from one or more sources;

processing the dimension data based on characteristics of the dimension data; and

storing the processed dimension data in a second data structure.

11. The system of claim 7, wherein:

the dimension subsystem is contained in a first computing device; and

the fact subsystem is contained in a second computing device, the second computing device being connected to the first computing device through a communications network.

12. The system of claim 7, wherein:

the fact subsystem is optimized by operations comprising;

grouping one or more pre-formatted queries; and

executing the grouped queries according to a schedule, where a common calculation in the grouped queries is performed before the grouped queries are executed; and

the dimension subsystem is optimized for query response time.

13. A non-transitory computer-readable storage medium having instructions stored thereon, the instructions operable to cause one or more computing devices to perform operations comprising:

receiving a query, the query including grouping information and filtering information; and

responsive to the query, producing, using a fact subsystem and a dimension subsystem, a result set, the result set being produced from fact data and dimension data, the fact data including one or more keyed values, the dimension data including definitions of one or more keys of the fact data, wherein;

the dimension subsystem is optimized for the dimension data and is configured to perform first operations comprising;

storing the dimension data; and

identifying, from the dimension data and based at least in part on the filtering information, a key for accessing the fact data;

the fact subsystem is optimized for the fact data and is configured to perform second operations comprising;

storing the fact data;

aggregating, from the fact data and based at least in part on the grouping information, a plurality of query results; and

filtering the aggregated query results using the key identified by the dimension subsystem; and

the result set includes the filtered query results.

14. The non-transitory computer-readable medium of claim 13, where the second operation further comprise:

obtaining the fact data as incremental updates;

aggregating the updates into a number of predetermined groupings; and

storing the predetermined groupings in a first data structure.

15. The non-transitory computer-readable medium of claim 14, where each update includes one or more key/value pairs.

16. The non-transitory computer-readable medium of claim 14, where the first operations further comprise:

obtaining the dimension data from one or more sources;

processing the dimension data based on characteristics of the dimension data; and

storing the processed dimension data in a second data structure.

17. The non-transitory computer-readable medium of claim 13, wherein:

the fact subsystem is optimized by operations comprising;

grouping one or more pre-formatted queries; and

executing the grouped queries according to a schedule, where a common calculation in the grouped queries is performed before the grouped queries are executed; and

the dimension subsystem is optimized for query response time.