Optimal query scheduling for resource utilization optimization

Patent metadata

Field	Value
Publication number	US-11989181-B2
Application number	US-202318177726-A
Country	US
Kind code	B2
Filing date	Mar 2, 2023
Priority date	Jan 13, 2020
Publication date	May 21, 2024
Grant date	May 21, 2024

Abstract

The present disclosure provides a method, system and computer program product for optimal query scheduling for resource utilization option. In an embodiment of the disclosure, a process for optimal query scheduling includes receiving in an information retrieval data processing system at a contemporaneous time, a request for deferred query execution of a specified query to a future time after the contemporaneous time. The method additionally includes determining a frequency of change of data corresponding to a field referenced in the specified query. Then, on condition that the frequency of change is below a threshold value, an intermediate time prior to the future time but after the contemporaneous time can be identified and the specified query scheduled for execution at the intermediate time instead of the future time. But, otherwise the specified query can be scheduled at the future time as originally requested.

First claim

What is claimed is:

1. A computer-implemented method when executed on data processing hardware causes the data processing hardware to perform operations comprising:
receiving a plurality of requests to schedule execution of a corresponding plurality of queries at a future time;
for each respective query of the corresponding plurality of queries, determining a frequency underlying data associated with the respective query changes;
determining that the frequency the underlying data associated with a respective one of the corresponding plurality of queries changes satisfies a threshold frequency; and
in response to determining that the frequency the underlying data associated with the respective one of the corresponding plurality of queries changes satisfies the threshold frequency, scheduling execution for the respective one of the corresponding plurality of queries at an intermediate time, the intermediate time occurring prior to the future time.

2. The method of claim 1 , wherein the intermediate time comprises a point in time when additional resources of the data processing hardware are available.

3. The method of claim 1 , wherein the operations further comprise, for another respective query of the corresponding plurality of queries:
computing an estimated cost of execution of the another respective query; and
determining that the estimated cost of execution of the another respective query satisfies a threshold cost of execution.

4. The method of claim 3 , wherein the operations further comprise, in response to determining that the estimated cost of execution of the another respective query satisfies the threshold cost of execution, filtering the another respective query into a subset of queries.

5. The method of claim 3 , wherein computing the estimated cost of execution comprises matching at least a portion of the respective query to an entry in a table of query fragments and historical execution times.

6. The method of claim 1 , wherein the operations further comprise, for another respective query of the corresponding plurality of queries:
determining that the frequency the underlying data associated with the another respective query changes fails to satisfy the threshold frequency; and
in response to determining that the frequency the underlying data associated with the another respective query changes fails to satisfy the threshold frequency, scheduling the another respective query for execution at the future time.

7. The method of claim 1 , wherein receiving the plurality of requests comprises receiving the corresponding plurality of queries from query clients.

8. The method of claim 7 , wherein the operations further comprise returning, to one of the query clients, a corresponding result for each query of the corresponding plurality of queries.

9. The method of claim 1 , wherein the operations further comprise receiving each request of the plurality of requests at a contemporaneous time.

10. The method of claim 1 , wherein determining that the frequency the underlying data associated with the respective one of the corresponding plurality of queries changes satisfies the threshold frequency comprises matching a field of the respective one of the corresponding plurality of queries with a data structure indicating a known volatility of a plurality of fields.

11. A system comprising:
data processing hardware; and
memory hardware in communication with the data processing hardware, the memory hardware storing instructions that when executed on the data processing hardware cause the data processing hardware to perform operations comprising:
receiving a plurality of requests to schedule execution of a corresponding plurality of queries at a future time; and
for each respective query of the corresponding plurality of queries, determining a frequency underlying data associated with the respective query changes;
for a respective one of the corresponding plurality of queries, determining that the frequency the underlying data associated with the respective one of the corresponding plurality of queries changes satisfies a threshold frequency; and
in response to determining that the frequency the underlying data associated with the respective one of the corresponding plurality of queries changes satisfies the threshold frequency, scheduling the respective one of the corresponding plurality of queries for execution at an intermediate time, the intermediate time occurring prior to the future time.

12. The system of claim 11 , wherein the intermediate time comprises a point in time when additional resources of the data processing hardware are available.

13. The system of claim 11 , wherein the operations further comprise, for another respective query of the corresponding plurality of queries:
computing an estimated cost of execution of the another respective query; and
determining that the estimated cost of execution of the another respective query satisfies a threshold cost of execution.

14. The system of claim 13 , wherein the operations further comprise, in response to determining that the estimated cost of execution of the another respective query satisfies the threshold cost of execution, filtering the another respective query into a subset of queries.

15. The system of claim 13 , wherein computing the estimated cost of execution comprises matching at least a portion of the respective query to an entry in a table of query fragments and historical execution times.

16. The system of claim 11 , wherein the operations further comprise, for another respective query of the corresponding plurality of queries:
determining that the frequency the underlying data associated with the another respective query changes fails to satisfy the threshold frequency; and
in response to determining that the frequency the underlying data associated with the another respective query changes fails to satisfy the threshold frequency, scheduling the another respective query for execution at the future time.

17. The system of claim 11 , wherein receiving the plurality of requests comprises receiving the corresponding plurality of queries from query clients.

18. The system of claim 17 , wherein the operations further comprise returning, to one of the query clients, a corresponding result for each query of the corresponding plurality of queries.

19. The system of claim 11 , wherein the operations further comprise receiving each request of the plurality of requests at a contemporaneous time.

20. The system of claim 11 , wherein determining that the frequency the underlying data associated with the respective one of the corresponding plurality of queries changes satisfies the threshold frequency comprises matching a field of the respective one of the corresponding plurality of queries with a data structure indicating a known volatility of a plurality of fields.

Assignees

• Google Llc

Inventors

• Cisek Julius
• Kumar Gaurav
• Mistry Shaunak
• Petersen Kalen

Classifications

• G06F16/24545 Primary

  Selectivity estimation or determination · CPC title

• G06F16/245 Primary

  Query processing · CPC title