Granted Patent B2

US 10,664,476 · App. 15/352,131 · Granted May 26, 2020

Inventors: Rajkumar Sen (San Mateo, CA); Samir Jindel (San Francisco, CA); Jack Chen (Cambridge, MA)

Assignee: MemSQL, Inc.

G06F16/24544G06F16/245G06F16/24542G06F16/24557

Abstract

Claims (47)

1. A method for improving performance of a computer system that executes queries related to a database, comprising:

receiving a first query that identifies a plurality of tables in the database, and a plurality of predicates that are to be applied to the tables to select particular records in the database;

estimating a first cost corresponding to the first query using a linear join operation plan,

analyzing the first query to identify one or more satellite tables, each satellite table being a table of the database that is filtered by a selective predicate in the first query, and is connected to only one other table in the database via at least one linking predicate of the first query;

identifying one or more seed tables, each seed table being a table of the database that is connected to a satellite table and at least one other table,

identifying a plurality of candidate operation plans corresponding to the first query, each candidate operation plan being a bushy tree join plan that includes a sub join of a corresponding seed table and its connected satellite table,

estimating a cost associated with each operation plan of the plurality of operation plans;

selecting a least-cost operation plan based on the first cost and the cost associated with each operation plan; and

executing the least-cost operation plan on the computer system in response to the receiving of the first query.

2. The method of claim 1 , wherein analyzing the first query includes building a join graph of the tables in the first query in which each table is a vertex, and each join predicate between a pair of the tables is an edge.

3. The method of claim 1 , wherein each sub-join of each seed table and its connected satellite table includes forming a sub-table corresponding to a join of the seed table and its connected satellite table, and the corresponding bushy join of the operation plan includes a join of the sub-table to a join of other tables of the plurality of tables.

4. The method of claim 3 , wherein the join of the other tables of the plurality of tables is a least cost linear join.

5. The method of claim 3 , wherein each sub-join is a least cost linear join.

6. The method of claim 1 , including identifying at least one sub-join of the seed table and its connected satellite table as another satellite table and including a cost of an operation plan that includes another sub-join of the at least one sub-join and another table of the plurality of tables.

7. A database access system, comprising:

a communication interface that receives a first query that identifies a plurality of tables in a database, and a plurality of predicates that are to be applied to the tables to select particular records in the database;

a processing system coupled to the communication interface that:

estimates a first cost corresponding to the first query using a linear join operation plan,

analyzes the first query to identify one or more satellite tables, each satellite table being a table of the database that is filtered by a selective predicate in the first query, and is connected to only one other table in the database via at least one linking predicate of the first query;

identifies one or more seed tables, each seed table being a table of the database that is connected to a satellite table and at least one other table,

identifies a plurality of candidate operation plans corresponding to the first query, each candidate operation plan being a bushy tree join plan that includes a sub-join of a corresponding seed table and its connected satellite table,

estimates a cost associated with each operation plan of the plurality of operation plans;

selects a least-cost operation plan based on the first cost and the cost associated with each operation plan; and

executes the least-cost operation plan on the computer system;

wherein the communication interface provides results of the execution of the least-cost operation plan by the processing system in response to the receiving of the first query.

8. The database access system of claim 7 , wherein the processing system analyzes the first query by building a join graph of the tables in the first query in which each table is a vertex, and each join predicate between a pair of the tables is an edge.

9. The database access system of claim 7 , wherein the processing system identifies each operation plan by forming a sub-table corresponding to a join of the seed table and its connected satellite table, and forming a join of the sub-table to a join of other tables of the plurality of tables.

10. The database access system of claim 9 , wherein the join of the other tables of the plurality of tables is a least cost linear join.

11. The database access system of claim 9 , wherein each sub join is a least cost linear join.

12. The database access system of claim 7 , wherein the processing system identifies at least one sub-join of the seed table and its connected satellite table as another satellite table and determines a cost of an operation plan that includes another sub-join of the at least one sub-join and another table of the plurality of tables.

13. The database access system of claim 7 , wherein the processing system comprises a server, and the communication interface couples the server to a network.

14. The database access system of claim 7 , wherein the processing system comprises a client device.

15. The database access system of claim 7 , including the database.

16. A non-transitory computer-readable medium that includes a program that, when executed by a processing system, causes the processing system to:

receive a first query that identifies a plurality of tables in the database, and a plurality of predicates that are to be applied to the tables to select particular records in the database;

estimate a first cost corresponding to the first query using a linear join operation plan,

analyze the first query to identify one or more satellite tables, each satellite table being a table of the database that is filtered by a selective predicate in the first query, and is connected to only one other table in the database via at least one linking predicate of the first query;

identify one or more seed tables, each seed table being a table of the database that is connected to a satellite table and at least one other table,

identify a plurality of candidate operation plans corresponding to the first query, each candidate operation plan being a bushy tree join plan that includes a sub join of a corresponding seed table and its connected satellite table,

estimate a cost associated with each operation plan of the plurality of operation plans;

select a least-cost operation plan based on the first cost and the cost associated with each operation plan; and

execute the least-cost operation plan on the computer system in response to the receiving of the first query.

17. The medium of claim 16 , wherein the program causes the processing system to analyze the first query by a process that includes building a join graph of the tables in the first query in which each table is a vertex, and each join predicate between a pair of the tables is an edge.

18. The medium of claim 16 , wherein each sub-join of each seed table and its connected satellite table includes forming a sub-table corresponding to a join of the seed table and its connected satellite table, and the corresponding bushy join of the operation plan includes a join of the sub-table to a join of other tables of the plurality of tables.

19. The medium of claim 18 , wherein the join of the other tables of the plurality of tables is a least cost linear join.

20. The medium of claim 18 , wherein each sub-join is a least cost linear join.

21. The medium of claim 16 , wherein the program also causes the processing system to identify at least one sub-join of the seed table and its connected satellite table as another satellite table and determine a cost of an operation plan that includes another sub-join of the at least one sub-join and another table of the plurality of tables.

Assignments (9)

Continuity (2)