Heuristic database querying with dynamic partitioning

Patent metadata

Field	Value
Publication number	US-12373434-B2
Application number	US-202418440624-A
Country	US
Kind code	B2
Filing date	Feb 13, 2024
Priority date	Jul 29, 2022
Publication date	Jul 29, 2025
Grant date	Jul 29, 2025

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, logically partitioning a search space of the database into a plurality of partitions for execution of the first query, wherein logically partitioning the search space comprises, for each of the plurality of partitions,
determining the partition of the search space, wherein determining the partition of the search space comprises selecting one or more values of a first key from a set of unsearched values of the first key based on first heuristics;
augmenting the first query with the first key and the one or more values of the first key to generate an augmented query, wherein augmenting the first query with the first key and the one or more values of the first key comprises appending, to the first query, the first key and the one or more values of the first key;
based on executing the augmented query, obtaining a subset of results of the first query, wherein the subset of results comprise data of resources maintained in the database that satisfy the first query and correspond to the partition of the search space; and
paginating the subset of results.

2. The method of claim 1 , wherein appending, to the first query, the first key and the one or more values of the first key comprises appending to the first query a predicate or clause comprising the first key and the one or more values of the first key.

3. The method of claim 1 , wherein determining the partition of the search space further comprises,
determining a plurality of candidate partitions of the search space;
generating a plurality of query plans corresponding to the plurality of candidate partitions, wherein the plurality of query plans comprises a first query plan corresponding to the partition of the search space;
evaluating the plurality of query plans; and
selecting the first query plan from the plurality of query plans for execution.

4. The method of claim 3 , wherein determining the plurality of candidate partitions comprises, for each of the plurality of candidate partitions, selecting one or more unsearched values of the first key from the set of unsearched values based on the first heuristics, and wherein generating the plurality of query plans comprises generating the plurality of query plans for a plurality of augmented queries corresponding to the plurality of candidate partitions.

5. The method of claim 3 , wherein evaluating the plurality of query plans comprises computing heuristic scores for the plurality of query plans based on second heuristics, and wherein selecting the first query plan is based on determining that the first query plan has a best one of the heuristic scores.

6. The method of claim 5 , wherein computing the heuristic scores for the plurality of query plans based on the second heuristics comprises, for each query plan of the plurality of query plans and corresponding candidate partition of the plurality of candidate partitions, computing a heuristic score based on at least one of an estimated number of records to be searched associated with the query plan, an estimated execution time associated with the query plan, and a quantitative relation between active and deleted resources that correspond to the candidate partition.

7. The method of claim 1 , wherein the database stores resources allocated to an end user by a Software-as-a-Service (SaaS) application vendor or a cloud service provider (CSP), wherein the first query corresponds to the end user.

8. The method of claim 7 , wherein selecting the one or more values of a first key based on the first heuristics comprises determining the one or more values that correspond to at least one of most recent or current ones of the resources based on updates to the database and most relevant ones of the resources based on quantities of resources associated with the one or more values.

9. The method of claim 7 , further comprising determining, for each value in a domain of the first key, counts of active resources and deleted resources of the end user documented in the database in association with the value of the first key, wherein selecting the one or more values of a first key based on the first heuristics comprises determining the one or more values that correspond to a greatest quantitative relation between active resources and deleted resources.

10. The method of claim 7 , further comprising determining a distribution of resources associated with the end user across values in a domain of the first key.

11. The method of claim 10 , further comprising determining if the distribution of resources satisfies a criterion for heuristically partitioning the search space for execution of the first query, wherein heuristically partitioning the search space is based on determining that the distribution of resources satisfies the criterion.

12. One or more non-transitory machine-readable media having program code stored thereon, the program code comprising instructions to:
based on submission of a first query to a database, determine a logical partition of a search space of the database, wherein the instructions to determine the logical partition of the search space comprise instructions to select one or more values of a first key from a set of unsearched values of the first key based on first heuristics;
append the first key and the one or more values of the first key selected from the set of unsearched values to the first query to generate an augmented query;
obtain a subset of results of the first query resulting from execution of the augmented query, wherein the subset of results comprise results comprise data of resources maintained in the database that satisfy the first query and correspond to the logical partition of the search space; and
paginate the subset of results.

13. The non-transitory machine-readable media of claim 12 , wherein the instructions to determine the logical partition of the search space further comprise instructions to,
determine a plurality of candidate partitions of the search space based on the first heuristics;
generate a plurality of query plans corresponding to the plurality of candidate partitions, wherein the plurality of query plans comprises a first query plan corresponding to the logical partition of the search space; and
based on evaluation of the plurality of query plans, select the first query plan from the plurality of query plans for execution.

14. The non-transitory machine-readable media of claim 13 ,
wherein the instructions to determine the plurality of candidate partitions comprise instructions to, for each of the plurality of candidate partitions, select one or more unsearched values of the first key from the set of unsearched values based on the first heuristics, and
wherein the instructions to generate the plurality of query plans comprise instructions to generate the plurality of query plans for a plurality of augmented queries that correspond to the plurality of candidate partitions.

15. The non-transitory machine-readable media of claim 12 , wherein the program code further comprises instructions to repeat the determination of logical partitions of the search space, appending the first key and subsequently selected values of the first key to the first query, obtaining subsets of results of the first query, and pagination of the subsets of results for additional logical partitions of the search space until a search termination criterion has been satisfied.

16. An apparatus comprising:
a processor; and
a computer-readable medium having instructions stored thereon that are executable by the processor to cause t

Assignees

• Palo Alto Networks Inc

Inventors

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

Classifications

• G06F16/24542

  Plan optimisation · CPC title

• G06F16/2471 Primary

  Distributed queries · CPC title

• G06F16/2455 Primary

  Query execution · CPC title