Managing complex queries with predicates

• US 9,971,831 B2
• Filed: 11/25/2015
• Issued: 05/15/2018
• Est. Priority Date: 11/25/2015
• Status: Active Grant

• Current Assignee: AirBNB Incorporated
• Original Assignee: International Business Machines Corporation
• Inventors: Chainani, Naresh K., Chinta, Kiran K., Zhang, Liping
• Primary Examiner(s): Rostami, Mohammad S
• Assistant Examiner(s): May, Robert F
• Application Number:
  US14/951,773
• Publication Number:
  US 20170147686A1
• Time in Patent Office: 902 Days
• Field of Search: 707999005, 707610, 707640, 707812, 707723, 707758, 707754, 707750, 707718, 707714, 707741
• CPC Class Codes: G06F 16/245 Query processing
• CPC Class Codes: G06F 16/24539 using cached or materialised query results
• CPC Class Codes: G06F 16/24542 Plan optimisation
• CPC Class Codes: G06F 16/24549 Run-time optimisation
• CPC Class Codes: G06F 16/2455 Query execution
• CPC Class Codes: G06F 16/3338 Query expansion
• CPC Class Codes: G06F 16/335 Filtering based on additional data, e.g. user or group profiles filtering in web context G06F16/9535, G06F16/9536

Abstract

A first query is detected. The first query is for a storage device, and pulls a result set from the storage device using a set of predicates. The first query satisfies a size criterion. A new set of predicates of the result set is identified. The new set of predicates does not include any predicates of the original set of predicates. A second query which is the same as the first query is detected. The new set of predicates is used to determine the result set.

Claims

1. A method of processing complex queries, comprising:

detecting a first query directed towards a dataset which satisfies a size criterion, wherein the first query includes a set of initial predicates and results in a first result set;

identifying one or more new predicates from the result set, wherein the one or more new predicates are not within the set of initial predicates;

detecting a second query directed towards the dataset, wherein the second query is the same as the first query;

determining that predicates of the one or more new predicates filter a threshold amount of tuples of an initial set of tuples;

determining an order of the one or more new predicates such that a new predicate which filters relatively more tuples of the initial set of tuples is before a new predicate which filters relatively less tuples of the initial set of tuples; and

utilizing the one or more new predicates to process the second query in the order and determine a second result set for the second query.

2. The method of claim 1, the method further comprising:

detecting one or more modifications to the dataset;

determining that the one or more modifications invalidate a new predicate of the one or more new predicates; and

invalidating the new predicate.

3. The method of claim 2, wherein the one or more modifications includes an addition of data to the dataset, wherein the data relates to the new predicate.

4. The method of claim 2, wherein the one or more modifications includes a deletion of a threshold amount of related data of the dataset, wherein the related data relates to the new predicate.

5. The method of claim 1, wherein the size criterion includes a threshold number of tuples of the first result set.

6. The method of claim 1, wherein the first query and the second query are both sub-queries of a parent query which has a plurality of sub-queries.

7. A system, comprising:

a processor; and

a memory coupled to the processor, wherein the memory comprises instructions which, when executed by the processor, cause the processor to;

detect a first query directed towards a dataset which satisfies a size criterion, wherein the first query includes a set of initial predicates and results in a first result set;

identify one or more new predicates from the result set, wherein the one or more new predicates are not within the set of initial predicates;

detect a second query directed towards the dataset, wherein the second query corresponds with the first query;

determine that predicates of the one or more new predicates filter a threshold amount of tuples of an initial set of tuples;

determine an order of the one or more new predicates such that a new predicate which filters relatively more tuples of the initial set of tuples is before a new predicate which filters relatively less tuples of the initial set of tuples; and

utilize the one or more new predicates to process the second query in the order and determine a second result set for the second query.

8. The system of claim 7, wherein the memory further comprises instructions which, when executed by the processor, cause the processor to:

detect one or more modifications to the dataset;

determine that the one or more modifications invalidate a new predicate of the one or more new predicates; and

invalidate the new predicate.

9. The system of claim 8, wherein the one or more modifications includes an addition of data to the dataset, wherein the data relates to the new predicate.

10. The system of claim 7, wherein the first query is identical to the second query.

11. The system of claim 7, wherein the size criterion includes a threshold number of tuples of the first result set.

12. The system of claim 7, wherein the first query and the second query are both sub-queries of a parent query which has a plurality of sub-queries.

13. A computer program product for processing complex queries, the computer program product disposed upon a non-transitory computer readable storage medium, the computer program product comprising computer program instructions that, when executed by a computer processor of a computer, cause the computer to:

detect a first query directed towards a dataset which satisfies a size criterion, wherein the first query includes a set of initial predicates and results in a first result set;

identify one or more new predicates from the result set, wherein the one or more new predicates are not within the set of initial predicates;

detect a second query directed towards the dataset, wherein the second query is the same as the first query;

determine that predicates of the one or more new predicates filter a threshold amount of tuples of an initial set of tuples;

determine an order of the one or more new predicates such that a new predicate which filters relatively more tuples of the initial set of tuples is before a new predicate which filters relatively less tuples of the initial set of tuples; and

utilize the one or more new predicates to process the second query in the order and determine a second result set for the second query.

14. The computer program product of claim 13, wherein the computer program product further comprises computer program instructions that, when executed by a computer processor of a computer, cause the computer to:

detect one or more modifications to the dataset;

determine that the one or more modifications invalidate a new predicate of the one or more new predicates; and

invalidate the new predicate.

15. The computer program product of claim 14, wherein the one or more modifications includes a deletion of a threshold amount of related data of the dataset, wherein the related data relates to the new predicate.

16. The computer program product of claim 13, wherein the size criterion includes a threshold number of tuples of the first result set.

17. The computer program product of claim 13, wherein the first query and the second query are both sub-queries of a parent query which has a plurality of sub-queries.