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

• US 8,620,857 B1
• Filed: 08/13/2012
• Issued: 12/31/2013
• 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): Mamillapalli, Pavan
• Application Number:
  US13/584,638
• Time in Patent Office: 505 Days
• Field of Search: 707/600, 707/601, 707/602, 707/605
• US Class Current: 707/602
• 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 performed by data processing apparatus, the method comprising:

receiving a query that includes grouping information and filtering information;

receiving, from a first computing device optimized for dimension data, a key identified from dimension data processed by the first computing device, and based at least in part on the filtering information;

obtaining, from a second computing device optimized for fact data, a plurality of query results from fact data processed by the second computing device and based at least in part on the received grouping information;

filtering the query results using the received key; and

generating a result set based, at least in part, on the filtered query results.

2. The method of claim 1, where processing the fact data by the second computing device 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 processing the dimension data by the first computing device 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 detail values relating to the filtered query results; and

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

6. The method of claim 1, wherein:

The second 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 first computing device is optimized for query response time.

7. The method of claim 1, further comprising combining the filtered query results with dimension data associated with the received key.

8. The method of claim 1, wherein the grouping information comprises predetermined groupings related to common query requests.

9. The method of claim 1, wherein the filtering information comprises a comparison expression.

10. The method of claim 1, wherein the key comprises information associated with an entity in the dimension data.

11. The method of claim 1, wherein the fact data comprises transaction data.

12. The method of claim 1, wherein the dimension data comprises static descriptive information.

13. A system comprising:

two or more computing devices, the two or more computing devices comprising;

a first computing device optimized for dimension data and

a second computing device optimized for fact data,

wherein one of the two or more computing devices is configured to perform operations comprising;

receiving a query that includes grouping information and filtering information;

receiving, from the first computing device, a key identified from dimension data processed by the first computing device, and based at least in part on the filtering information;

obtaining, from the second computing device, a plurality of query results from fact data processed by the second computing device, and based at least in part on the received grouping information;

filtering the query results using the received key; and

generating a result set based, at least in part, on the filtered query results.

14. The system of claim 13 comprising a fact subsystem configured to perform operations comprising:

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 system of claim 14, wherein each update includes one or more key/value pairs.

16. The system of claim 14 comprising a dimension subsystem configured to perform operations comprising:

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 system of claim 16, wherein:

the fact subsystem is contained in the second computing device; and

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

18. The system of claim 13, wherein:

the second 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 first computing device is optimized for query response time.

19. The system of claim 13, wherein the operations further comprise:

combining the filtered query results with dimension data associated with the received key.

20. 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 that includes grouping information and filtering information;

receiving, from a first computing device optimized for dimension data, a key being identified from dimension data processed by the first computing device, and based at least in part on the filtering information;

obtaining, from a second computing device optimized for fact data, a plurality of query results from fact data processed by the second computing device and based at least in part on the received grouping information;

filtering the query results using the received key; and

generating a result set based, at least in part, on the filtered query results.

21. The non-transitory computer-readable medium of claim 20 operable to cause a fact subsystem included in the second computing device to perform operations comprising:

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.

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

23. The non-transitory computer-readable medium of claim 21 operable to cause a dimension subsystem included in the first computing device to perform operations comprising:

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.

24. The non-transitory computer-readable medium of claim 20, wherein:

the second 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 first computing device is optimized for query response time.

25. The non-transitory computer-readable medium of claim 20, wherein the operations further comprise:

combining the filtered query results with dimension data associated with the received key.