Heuristic database querying with dynamic partitioning

Patent metadata

Field	Value
Publication number	US-11941006-B2
Application number	US-202217815969-A
Country	US
Kind code	B2
Filing date	Jul 29, 2022
Priority date	Jul 29, 2022
Publication date	Mar 26, 2024
Grant date	Mar 26, 2024

Abstract

Dynamic partitioning of a search space of queries is implemented for flexible, heuristic database querying. Search space partitioning refers to dividing the search space for a submitted query into smaller parts by augmenting the queries to append thereto an additional predicate comprising a dynamic partition key and a value(s) selected based on heuristics (e.g., recency and/or relevancy of the value(s)). A plurality of candidate augmentations of the query and corresponding query plans are generated and evaluated based on additional heuristics to determine which can be executed to yield the best results in terms of result quality and latency. This query plan is selected and executed for retrieval of results that satisfy the query, with pagination utilized for presentation of the results. The procedure of generating candidate query plans, selecting one of the candidates for execution, and paginating results is repeated until a search termination criterion is satisfied.

First claim

The invention claimed is:

1. A method comprising:
based on submission of a first query to a database, determining a plurality of candidate partitions of a search space corresponding to the database, wherein determining the plurality of candidate partitions comprises selecting sets of one or more candidate values of a first key to be appended to the first query;
evaluating the plurality of candidate partitions based on a plurality of heuristics;
selecting a first partition of the plurality of candidate partitions for execution of the first query based on the evaluating, wherein the first partition corresponds to a first of the sets of one or more candidate values of the first key;
obtaining a first subset of results of the first query, wherein the first subset of results is a result of executing the first query on the first partition of the search space; and
paginating the first subset of results of the first query.

2. The method of claim 1 , wherein executing the first query on the first partition of the search space comprises executing the first query having appended thereto a predicate comprising the first key and the first set of one or more candidate values.

3. The method of claim 1 further comprising determining a plurality of query plans for executing the first query on the plurality of candidate partitions of the search space, wherein each of the plurality of query plans corresponds to one of the plurality of candidate partitions and indicates at least one of an estimated execution cost and an estimated number of records to be examined based on executing the first query on the corresponding one of the plurality of candidate partitions.

4. The method of claim 3 , wherein evaluating the plurality of candidate partitions based on the heuristics comprises, for each candidate partition of the plurality of candidate partitions and corresponding query plan of the plurality of query plans,
evaluating the at least one of the estimated execution cost, the estimated number of records to be examined, and a quantitative relation between counts of active resources and deleted resources that correspond to the candidate partition of the search space based on the heuristics; and
determining a score for the candidate partition and query plan based on the evaluating.

5. The method of claim 4 further comprising determining that the first partition has a best score among the plurality of candidate partitions, wherein the first partition is selected based on determining that the first partition has the best score.

6. The method of claim 1 , wherein the database stores data of resources allocated to an end user by a vendor, wherein the vendor is a Software-as-a-Service (SaaS) application vendor or a cloud service provider (CSP), and wherein the plurality of candidate partitions are logical partitions of the database.

7. The method of claim 6 further comprising determining a first subset of possible values of the first key associated with most recent or current ones of the resources documented in the database based on times of updates or access associated with each of the possible values, wherein selecting the sets of one or more candidate values comprises, for each of the sets of one or more candidate values, selecting at least a first of the one or more candidate values from the first subset.

8. The method of claim 6 further comprising determining a second subset of possible values of the first key associated with more relevant ones of the resources documented in the database based on quantities of resources associated with each of the possible values, wherein selecting the sets of one or more candidate values comprises, for each of the sets of one or more candidate values, selecting at least a first of the one or more candidate values from the second subset.

9. The method of claim 1 further comprising, based on obtaining requests for next subsets of results of the first query, for each of the requests, repeating the determining and evaluating of candidate partitions of the search space, selecting one of the candidate partitions, obtaining a next subset of results of the first query, and paginating the next subset of results.

10. The method of claim 9 further comprising terminating the determining and evaluating of candidate partitions of the search space based on determining that a criterion for terminating query execution has been satisfied, wherein the criterion comprises a threshold number of consecutively executed queries that do not return any results.

11. One or more non-transitory machine-readable media having program code stored therein, the program code comprising instructions to:
based on analysis of a query to be executed on a database, logically divide a search space of the query into a plurality of partitions, wherein the instructions to logically divide the search space into a plurality of partitions comprises instructions to, for each partition of the plurality of partitions,
determine a plurality of candidate augmentations to the query based on, for each of the plurality of candidate augmentations, appending to the query a predicate comprising a key and corresponding sets of values selected based on first heuristics;
select one of the plurality of candidate augmentations to the query based on second heuristics, wherein the selected candidate augmentation corresponds to the partition;

execute the query on each of the plurality of partitions; and
paginate results returned from execution of the query on each of the plurality of partitions of the search space.

12. The non-transitory machine-readable media of claim 11 ,
wherein the program code further comprises instructions to determine a plurality of query plans corresponding to the plurality of candidate augmentations to the query, and
wherein the instructions to select the one of the plurality of candidate augmentations to the query comprise instructions to select the one of the plurality of candidate augmentations based on evaluation of at least one of estimated numbers of records to be examined for each of the plurality of query plans, estimated execution costs associated with each of the plurality of query plans, and quantitative relations between counts of active resources and deleted resources to be searched from execution of the plurality of query plans based on the second heuristics.

13. The non-transitory machine-readable media of claim 12 , wherein the program code further comprises instructions to determine scores for each of the plurality of candidate augmentations based on the evaluation, and wherein the instructions to select the one of the plurality of candidate augmentations comprise instructions to select the one of the plurality of candidate augmentations based on a determination that the selected candidate augmentation has a best score among the determined scores.

14. The non-transitory machine-readable media of claim 11 , wherein the program code further comprises instructions to select the corresponding sets of values for each of the plurality of candidate augmentations based on the first heuristics,
wherein the instructions to select the corresponding sets of values based on the first heuristics comprise instructions to, for each of the corresponding sets of values, determine at least one of a first subset of possible values of the key associated with more recently updated resources documented in the database and a second subset of the possible values of the key associated with greater quantities of resources documented in the database and select the corresponding set of values from at least one of the first subset and the second subset.

Assignees

• Palo Alto Networks Inc

Inventors

• Mouleeswaran Chandra Biksheswaran
• Agarwal Amit
• Pathak Prashant Kumar
• Wang Xiaoyan

Classifications

• G06F16/2455 Primary

  Query execution · CPC title

• G06F16/24542

  Plan optimisation · CPC title

• G06F16/2471 Primary

  Distributed queries · CPC title