METHODS AND APPARATUS FOR PROCESSING A DATABASE QUERY

• US 20120290618A1
• Filed: 07/27/2012
• Published: 11/15/2012
• Est. Priority Date: 10/14/2004
• Status: Active Grant

• Current Assignee: AirBNB Incorporated
• Original Assignee: International Business Machines Corporation
• Inventors: Barsness, Eric Lawrence, Santosuosso, John Matthew
• Granted Patent: US 8,515,993 B2
• Time in Patent Office: Days
• US Class Current: 707/775
• CPC Class Codes: G06F 16/24539 using cached or materialised query results
• CPC Class Codes: G06F 16/24557 Efficient disk access during query execution

Abstract

In a first aspect, a method is provided that includes the steps of (1) pre-computing a query result for each of a plurality of whole segments of data included in a database; (2) receiving a query specifying a defined range of data in the database; (3) determining if any of the whole segments are within the defined range; (4) performing the query on any partial segments of data within the defined range; and (5) determining the result of the query based on the pre-computed query results for any whole segments determined to be within the defined range and the result of the query on any partial segments within the defined range. Numerous other aspects are provided.

Claims

1. A method comprising:

pre-computing a first query result based on a first segment of data stored in a database in response to receiving a first query;

storing the first query result in the database;

receiving a second query specifying a second segment of data stored in the database;

determining whether the first segment of data is included in the second segment of data;

performing the second query on one or more third segments of data included in the second segment of data, wherein the one or more third segments of data do not include data from the first segment of data; and

computing a second query result based on a result of the performing the second query on the one or more third segments of data and, in response to determining that the first segment of data is included in the second segment of data, the first query result.

2. The method of claim 1 wherein the computing a second query result comprises retrieving the first query result from the database in response to determining that the first segment of data is included in the second segment of data.

3. The method of claim 1 wherein the computing a second query result comprises numerically adding together or numerically averaging the first query result and the result of the performing the second query on the one or more third segments of data.

4. The method of claim 1 further comprising computing a second query result based only on a result of the performing the second query on the one or more third segments of data in response to determining that the first segment of data is not included in the second segment of data.

5. The method of claim 1 wherein the first segment of data, the second segment of data, and the one or more third segments of data are each based on a date range.

6. The method of claim 1 wherein the second segment of data consists of the first segment of data and the one or more third segments of data, wherein the first segment of data and the one or more third segments of data are non-overlapping subsets of the second segment of data.

7. A method of processing a database query for information, comprising:

receiving a request to perform a query on a first portion of data stored in a database in a storage device to determine a query result;

determining whether a pre-computed partial result of the query is stored in the database, wherein the pre-computed partial result is a result of the query performed on a second portion of data stored in the database, and the second portion of data is included in the first portion of data;

retrieving the pre-computed partial result from the database in response to determining that the pre-computed partial result is stored in the database;

performing the query on the second portion of data to determine a second partial result in response to determining that the pre-computed partial result is not stored in the database;

performing the query on a third portion of data in the database to determine a third partial result, wherein the third portion of data is included in the first portion of data and not included in the second portion of data; and

determining the query result based on the third partial result and the pre-computed partial result or the second partial result.

8. The method of claim 7 wherein the determining the query result comprises numerically adding together or numerically averaging the third partial result and the pre-computed partial result or the second partial result.

9. The method of claim 7 wherein:

the first portion of data is based on a first range of dates, the second portion of data is based on a second range of dates, and the third portion of data is based on a third range of dates; and

the first range of dates includes the second and third ranges of dates.

10. An apparatus comprising:

a database in a storage device for storing data;

a processor coupled to the storage device and programmed to;

pre-compute a first query result based on a first segment of data stored in the database in response to receiving a first query;

store the first query result in the database;

receive a second query specifying a second segment of data stored in the database;

determine whether the first segment of data is included in the second segment of data;

perform the second query on one or more third segments of data included in the second segment of data, wherein the one or more third segments of data do not include data from the first segment of data; and

compute a second query result based on a result of the performing the second query on the one or more third segments of data and, in response to determining that the first segment of data is included in the second segment of data, the first query result.

11. The apparatus of claim 10 wherein the processor is further programmed to compute a second query result by retrieving the first query result from the database in response to determining that the first segment of data is included in the second segment of data.

12. The apparatus of claim 10 wherein the processor is further programmed to compute a second query result by numerically adding together or numerically averaging the first query result and the result of the performing the second query on the one or more third segments of data.

13. The apparatus of claim 10 wherein the processor is further programmed to compute a second query result based only on a result of the performing the second query on the one or more third segments of data in response to determining that the first segment of data is not included in the second segment of data.

14. The apparatus of claim 10 wherein the first segment of data, the second segment of data, and the one or more third segments of data are each based on a date range.

15. The apparatus of claim 10 wherein the second segment of data consists of the first segment of data and the one or more third segments of data, wherein the first segment of data and the one or more third segments of data are non-overlapping subsets of the second segment of data.