IP Library Granted Patent US 10,963,438
Granted Patent B1
US 10,963,438 · App. 16/950,342 · Granted Mar 30, 2021

Systems and methods for database query efficiency improvement

Inventors: Bin Dong (Beijing, CN); Zhan Chen (Seattle, WA); Zhiyong Huang (Beijing, CN); Chuanchuan Han (Beijing, CN); Junzhao Zhang (Beijing, CN)
Assignee: COUPANG CORP.
G06F16/217G06F16/211G06F16/214G06F16/221G06F16/24557G06F16/287
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,963,438
App. No.
16/950,342
Granted
Mar 30, 2021
Kind
B1
Abstract

Methods and systems for database query efficiency improvement are disclosed. In one embodiment, a method includes mirroring a primary database to a secondary database; creating a testing database comprising the schema; receiving a query; running the query on the testing database; and evaluating the query by: identifying predicates in the query; determining most common values for each column name by querying the secondary database; creating, for each column name, a list comprising at least one of the most common values; creating a test predicate comprising one of the column names and an entry for the list corresponding to the column name; creating a test query comprising one or more test predicates; determining a resource utilization of the query by running each of the test queries on the secondary database; and providing, to a user interface for display, an efficiency improvement recommendation when the resource utilization exceeds a threshold.

Claims (74)

1. A computer-implemented system for database query efficiency improvement, the system comprising:

a memory storing instructions; and

at least one processor configured to execute the instructions to perform operations comprising:

mirroring a primary database to a secondary database, the second database comprising a schema;

creating a testing database comprising the schema;

receiving a query;

running the query on the testing database; and

evaluating the query, in response to the query successfully completing on the testing database, by:

identifying predicates in the query, each predicate comprising a column name;

determining most common values for each column name by querying the secondary database;

creating, for each column name, a list comprising at least one of the most common values;

creating a test predicate comprising one of the column names and an entry for the list corresponding to the column name;

creating a test query comprising one or more test predicates;

determining a resource utilization of the query by running each of the test queries on the secondary database; and

providing, to a user interface for display, an efficiency improvement recommendation when the resource utilization exceeds a threshold.

2. The system of claim 1 , wherein the list further comprises most common queried values for each column name determined by querying a query store comprising historical queries of the primary database.

3. The system of claim 2 , wherein the list consists of an intersection of the most common queried values and the most common values.

4. The system of claim 2 , wherein the list comprises n-most common values.

5. The system of claim 1 , wherein the efficiency recommendation comprises adding an index to the query.

6. The system of claim 1 , wherein the resource utilization is a first resource utilization and evaluating the query further comprises:

modifying the query based on the efficiency recommendation;

determining a second resource utilization of the modified query; and

providing, to the user interface for display, a resource utilization difference between the first and the second resource utilizations.

7. The system of claim 1 , wherein determining most common values for each column name by querying the secondary database comprises:

determining a count of each value in a column corresponding to the column name;

calculating, for each value, a fraction corresponding to the determined count relative to a total number of entries;

ordering the values based on respective calculated fractions corresponding to the values; and

iteratively selecting unselected values, each of the unselected values having a highest corresponding fraction until a sum of fractions corresponding to the selected values exceeds a fraction threshold.

8. The system of claim 1 , wherein the operations further comprise running the query on the primary database when the resource utilization is less than the threshold.

9. The system of claim 1 , wherein the resource utilization comprises at least one of rows analyzed, processing time, and memory usage.

10. The system of claim 1 , wherein the operations further comprise deduplicating predicates by column name.

11. A computer-implemented method for database query efficiency improvement comprising:

mirroring a primary database to a secondary database, the second database comprising a schema;

creating a testing database comprising the schema;

receiving a query;

running the query on the testing database; and

evaluating the query, in response to the query successfully completing on the

testing database, by:

identifying predicates in the query, each predicate comprising a column name;

determining most common values for each column name by querying the secondary database;

creating, for each column name, a list comprising at least one of the most common values;

creating a test predicate comprising one of the column names and an entry for the list corresponding to the column name;

creating a test query comprising one or more test predicates;

determining a resource utilization of the query by running each of the test queries on the secondary database; and

providing, to a user interface for display, an efficiency improvement recommendation when the resource utilization exceeds a threshold.

12. The method of claim 11 , wherein the list further comprises most common queried values for each column name determined by querying a query store comprising historical queries of the primary database.

13. The method of claim 12 , wherein the list consists of an intersection of the most common queried values and the most common values.

14. The method of claim 12 , wherein the list comprises n-most common values.

15. The method of claim 11 , wherein the efficiency recommendation comprises adding an index to the query.

16. The method of claim 11 , wherein the resource utilization is a first resource utilization and evaluating the query further comprises:

modifying the query based on the efficiency recommendation;

determining a second resource utilization of the modified query; and

providing, to the user interface for display, a resource utilization difference between the first and the second resource utilizations.

17. The method of claim 11 , wherein determining most common values for each column name by querying the secondary database comprises:

determining a count of each value in a column corresponding to the column name;

calculating, for each value, a fraction corresponding to the determined count relative to a total number of entries;

ordering the values based on respective calculated fractions corresponding to the values; and

iteratively selecting unselected values, each of the unselected values having a highest corresponding fraction until a sum of fractions corresponding to the selected values exceeds a fraction threshold.

18. The method of claim 11 , wherein the operations further comprise running the query on the primary database when the resource utilization is less than the threshold.

19. The method of claim 11 , wherein the resource utilization comprises at least one of rows analyzed, processing time, and memory usage.

20. A computer-implemented method for database query efficiency improvement comprising:

mirroring a primary database to a secondary database, the second database comprising a schema;

creating a testing database comprising the schema;

receiving a query;

running the query on the testing database; and

evaluating the query, if the query successfully completes on the testing database, by:

identifying predicates in the query, each predicate comprising a unique column name;

determining most common values for each column name by querying the secondary database;

determining most common queried values for each column name by querying a query store;

creating, for each column name, a list comprising at least one of the most common values and at least one of the most common queried values;

creating test predicates comprising one of the column names and an entry for the list corresponding to the column name;

creating test queries comprising combinations of test predicates;

determining query processing times by running each of the test queries on the secondary database; and

running the query on the primary database when a maximum of the query processing times is less than a threshold.

Assignments (1)
ASSIGNMENT OF ASSIGNOR'S INTEREST Recorded Nov 17, 2020
From: DONG, BIN; CHEN, ZHAN; HUANG, ZHIYONG; HAN, CHUANCHUAN; ZHANG, JUNZHAO
To: COUPANG CORP.
Reel/Frame 054392/0815 →
Cited By (2)
US 12,423,306 US 12,585,397