Database distribution system and methods for scale-out applications

• US 8,620,903 B2
• Filed: 08/31/2010
• Issued: 12/31/2013
• Est. Priority Date: 11/04/2009
• Status: Active Grant

• Current Assignee: NEC Corporation
• Original Assignee: NEC Laboratories America Inc (NEC Corporation)
• Inventors: Tatemura, Junichi, Sawires, Arsany, Po, Oliver, Hacigumus, V. Hakan
• Primary Examiner(s): Breene, John
• Assistant Examiner(s): Bullock, Joshua
• Application Number:
  US12/873,269
• Publication Number:
  US 20110246448A1
• Time in Patent Office: 1,218 Days
• Field of Search: 707713-714, 707/718, 706/19
• US Class Current: 707/718
• 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, the method comprising:

receiving a query rewritten for an internal schema;

optimizing a query execution plan for the query;

executing the query execution plan and returning result of the execution to an application;

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; and

elevating each relation R when every relation with filtering power over R is accessed before R,

wherein the optimization includes;

determining a first executable plan with a minimum number of requests to the distributed storage engine if an effective parallelism available to the query engine is below a predetermined threshold; and

determining a second executable plan with a smallest depth, regardless of the total number of requests to be issued, if the effective parallelism exceeds the predetermined threshold, and

wherein the query execution plan is configured to support intra-operator parallelism, inter-operator parallelism, and pipeline parallelism.

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