DATABASE DISTRIBUTION SYSTEM AND METHODS FOR SCALE-OUT APPLICATIONS

• US 20110246448A1
• Filed: 08/31/2010
• Published: 10/06/2011
• Est. Priority Date: 11/04/2009
• Status: Active Grant

• Current Assignee: NEC Corporation
• Original Assignee: NEC Laboratories America Inc (NEC Corporation)
• Inventors: Tatemura, Junichi, Po, Oliver, Hacigumus, Vabit Hakan, Sawires, Arsany
• Granted Patent: US 8,620,903 B2
• Time in Patent Office: Days
• US Class Current: 707/714
• CPC Class Codes: G06F 16/24526 Internal representations for queries
• CPC Class Codes: G06F 16/24532 of parallel queries
• CPC Class Codes: G06F 16/2471 Distributed queries

Abstract

Systems and method are disclosed for query optimization in a scale-out system with a single query processing machine and a distributed storage engine to store data by receiving a query rewritten for an internal schema; optimizing a query execution plan for the query; and executing the plan and returning result to an application.

Claims

1. A method for query optimization in a scale-out system with a single query processing machine and a distributed storage engine to store data, comprising:

receiving a query rewritten for an internal schema;

optimizing a query execution plan for the query; and

executing the plan and returning result to an application.

2. The method of claim 1, comprising determining an executable plan with a minimum number of requests to the storage engine if an effective parallelism available to the query engine is below a predetermined threshold.

3. The method of claim 2, wherein the executable plan is optimized to include inter-operator parallelism that does not increase a number of requests.

4. The method of claim 2, comprising conforming to an access limitation imposed by the storage engine where no relation R can be visited before at least one other relation with one or more pointers to R is accessed.

5. The method of claim 4, comprising elevating each relation R when every relation with filtering power over R is accessed before R.

6. The method of claim 1, comprising determining a plan with the smallest depth, regardless of the total number of requests to be issued, if an effective parallelism exceeds a predetermined threshold.

8. The method of claim 1, wherein the query plan runs on one machine while making parallel storage requests to the distributed storage engine having a plurality of machines.

7. The method of claim 7, comprising conforming to an access limitation imposed by the storage engine where no relation R can be visited before at least one other relation with pointers to R is accessed.

9. A system for query optimization in a scale-out system with a single query processing machine and a distributed storage engine to store data, comprising:

means for receiving a query rewritten for the internal schema;

means for optimizing a query execution plan; and

means for executing the plan and returning result to an application.

10. The system of claim 9, wherein the distributed storage engine stores or retrieves key-value pairs.

11. The system of claim 9, wherein the distributed storage engine imposes an access limitation and a plan is executable only if the plan conforms to the access limitation.

12. The system of claim 9, comprising means for determining an executable plan with a minimum number of requests to the storage engine if an effective parallelism available to the query engine is low.

13. The system of claim 12, wherein the executable plan is optimized to include inter-operator parallelism that does not increase number of requests.

14. The system of claim 12, comprising means for conforming to an access limitation imposed by the storage engine where no relation R can be visited before at least one other relation with pointers to R is accessed.

15. The system of claim 14, comprising means for elevating each relation R as long as every relation with filtering power over R is accessed before R.

16. The system of claim 9, comprising means for determining a plan with the smallest depth, regardless of the total number of requests to be issued, if an effective parallelism exceeds a threshold.

17. The system of claim 9, comprising means for conforming to an access limitation imposed by the storage engine where no relation R can be visited before at least one other relation with pointers to R is accessed.

18. The system of claim 9, wherein the query plan runs on one machine while making parallel storage requests to the distributed storage engine composed of many machines.

19. The system of claim 9, wherein the query plan comprises a data-flow graph having a get operator and a merge operator, wherein the get operator joins the data from a parent operator and data from a key-value store by issuing key-based operation over the key-value store;

wherein the merge operator joins data from multiple parents; and

wherein join conditions of the get and merge operators are derived from a join graph that represents join conditions of the query.

20. The system of claim 9, wherein the query plan comprises a linear plan where differences in parallelism among plans are ignored, comprising minimizing an expected total retrieval cost estimated from statistics of a database instance.

21. The system of claim 9, wherein the query plan comprises a conservatively parallel plan that introduces inter-operator parallelism without sacrificing total retrieval cost.

22. The system of claim 9, wherein the query plan comprises a speculatively parallel plan that starts retrieving data from relations as soon as possible to try to finish execution early even if more data is retrieved than minimally needed.