IP Library Granted Patent US 10,848,434
Granted Patent B2
US 10,848,434 · App. 16/380,555 · Granted Nov 24, 2020

Performance management for query processing

Inventor: Afshin Ganjoo (San Jose, CA)
Assignee: A9.com, Inc.
H04L47/76G06F16/2228G06F16/2272G06F16/2455G06F16/278H04L41/5067H04L43/0852H04L43/16
View Patent ↗
Loading inventors, assignments & file history…
Monitor This Case
Get email alerts when status or documents change.
Order Certified Copies
Most orders are placed with the USPTO same day — all within 24 business hours.
Order via The Patent Place →
Pre-filled with this patent's details
Quick Facts
Patent No.
US 10,848,434
App. No.
16/380,555
Granted
Nov 24, 2020
Kind
B2
Abstract

The processing of search queries for a customer using a set of resource can balance performance with cost, in order to ensure that the processing satisfies customer performance requirements while attempting to minimize the cost to the customer for obtaining that performance. In addition to dynamically updating the allocation of resources used to process the requests, such as to change the number or sizes of allocated resources, the number of indexes to be searched can be updated as well. For example, a search index can be divided into two sub-indexes against which queries can be executed concurrently in order to reduce the latency by about a half. Adjustments to the indexes and resources can be balanced to minimize cost while retaining performance, which can include rejoining sub-indexes or reducing the number of resource as appropriate.

Claims (64)

1. A computer-implemented method, comprising:

determining a latency value, determined from at least one of an average latency or a maximum latency, does not satisfy a latency criterion for processing of search queries against an index of stored data using an allocation of resources;

determining a latency impact of splitting the data index into two or more sub-indexes;

splitting the index into a number of sub-indexes based at least in part upon an amount of latency reduction needed to cause the latency value to satisfy the latency criterion;

modifying the allocation of resources, the modification moving at least a portion of the number of sub-indexes to different instances; and

processing the search queries against the number of sub-indexes.

2. The computer-implemented method of claim 1 , comprising:

splitting the index based at least in part on the latency impact.

3. The computer-implemented method of claim 1 , further comprising:

determining an amount by which to split the index and a way in which to modify the allocation based at least in part upon a resulting cost to an entity associated with the stored data.

4. The computer-implemented method of claim 1 , further comprising:

calculating a predicted latency for subsequent requests processed over a future period of time; and

modifying at least one of the allocation of resources or the number of indexes and sub-indexes based at least in part upon the predicted latency.

5. The computer-implemented method of claim 1 , further comprising:

determining a latency impact of joining the sub-indexes into a smaller number of sub-indexes or a single index;

determining that the latency criterion would still be satisfied as a result of the joining; and

causing the sub-indexes to be joined into a smaller number of sub-indexes or a single index.

6. The computer-implemented method of claim 1 , further comprising:

determining an amount of time since a previous adjustment of a number of indexes and sub-indexes for processing the data; and

verifying that the amount of time at least meets a minimum time requirement before splitting the index into the number of sub-indexes.

7. The computer-implemented method of claim 1 , wherein modifying the allocation of resources comprises changing at least one of a capacity of resources allocated or a number of resources allocated.

8. A system, comprising:

at least one processor; and

memory including instructions that, when executed by the at least one processor, cause the system to:

determine a latency value, determined from at least one of an average latency or a maximum latency, does not satisfy a latency criterion for processing of search queries against an index of stored data using an allocation of resources;

determine a latency impact of splitting the data index into two or more sub-indexes;

split the index into a number of sub-indexes based at least in part upon an amount of latency reduction needed to cause the latency value to satisfy the latency criterion;

modify the allocation of resources, the modification moving at least a portion of the number of sub-indexes to different instances; and

process the search queries against the number of sub-indexes.

9. The system of claim 8 , wherein the instructions when executed further cause the system to:

split the index based at least in part on the latency impact.

10. The system of claim 8 , wherein the instructions when executed further cause the system to:

determine an amount by which to split the index and a way in which to modify the allocation based at least in part upon a resulting cost to an entity associated with the stored data.

11. The system of claim 8 , wherein the instructions when executed further cause the system to:

calculate a predicted latency for subsequent requests processed over a future period of time; and

modify at least one of the allocation of resources or the number of indexes and sub-indexes based at least in part upon the predicted latency.

12. The system of claim 8 , wherein the instructions when executed further cause the system to:

determine a latency impact of joining the sub-indexes into a smaller number of sub-indexes or a single index;

determine that the latency criterion would still be satisfied as a result of the joining; and

cause the sub-indexes to be joined into a smaller number of sub-indexes or a single index.

13. The system of claim 8 , wherein the instructions when executed further cause the system to:

determine an amount of time since a previous adjustment of a number of indexes and sub-indexes for processing the data; and

verify that the amount of time at least meets a minimum time requirement before splitting the index into the number of sub-indexes.

14. The system of claim 8 , wherein modifying the allocation of resources comprises changing at least one of a capacity of resources allocated or a number of resources allocated.

15. A non-transitory computer-readable storage medium including instructions that, when executed by at least one processor of a computing system, cause the computing system to:

determine a latency value, determined from at least one of an average latency or a maximum latency, does not satisfy a latency criterion for processing of search queries against an index of stored data using an allocation of resources;

determine a latency impact of splitting the data index into two or more sub-indexes;

split the index into a number of sub-indexes based at least in part upon an amount of latency reduction needed to cause the latency value to satisfy the latency criterion;

modify the allocation of resources, the modification moving at least a portion of the number of sub-indexes to different instances; and

process the search queries against the number of sub-indexes.

16. The non-transitory computer-readable storage medium of claim 15 , wherein the instructions when executed further cause the computing system to:

split the index based at least in part on the latency impact.

17. The non-transitory computer-readable storage medium of claim 15 , wherein the instructions when executed further cause the computing system to:

determine an amount by which to split the index and a way in which to modify the allocation based at least in part upon a resulting cost to an entity associated with the stored data.

18. The non-transitory computer-readable storage medium of claim 15 , wherein the instructions when executed further cause the computing system to:

calculate a predicted latency for subsequent requests processed over a future period of time; and

modify at least one of the allocation of resources or the number of indexes and sub-indexes based at least in part upon the predicted latency.

19. The non-transitory computer-readable storage medium of claim 15 , wherein the instructions when executed further cause the computing system to:

determine a latency impact of joining the sub-indexes into a smaller number of sub-indexes or a single index;

determine that the latency criterion would still be satisfied as a result of the joining; and

cause the sub-indexes to be joined into a smaller number of sub-indexes or a single index.

20. The non-transitory computer-readable storage medium of claim 15 , wherein the instructions when executed further cause the computing system to:

determine an amount of time since a previous adjustment of a number of indexes and sub-indexes for processing the data; and

verify that the amount of time at least meets a minimum time requirement before splitting the index into the number of sub-indexes.

Assignments (1)
ASSIGNMENT OF ASSIGNOR'S INTEREST Recorded Oct 13, 2024
From: A9.COM, INC.
To: AMAZON TECHNOLOGIES, INC.
Reel/Frame 069167/0493 →
Continuity (2)
Continuation 14963800 · Dec 9, 2015
Related Publication 20190238477A1 · Aug 1, 2019