The patent's inventors are Tatemura, Junichi (
This patent was filed on
From the background information supplied by the inventors, news correspondents obtained the following quote: "The present invention relates to query optimization in database distribution systems.
"Key value stores have been recently used for scale-out (horizontal scaling) data management, especially for web applications. Data is divided into small data fragments and distributed over multiple storage nodes. A key is associated with each fragment of the data, and the key-value store provides key-based operations (such as put and get) that enable an application to access data fragments by key without knowing their physical location. Key-based operations provide an abstraction layer of the data and make it possible to scale out data stores: the system can easily add and remove storage nodes without disrupting applications that access the data using such operations.
"However, the key-based operations also make it non-trivial to efficiently process more complicated data access, such as a relational query including join. A traditional relational database management system (RDBMS) often relies on various ways to access data stored on disks. Especially a scan operation takes a key role to let the RDBMS efficiently read a set of data in a table. Unfortunately, key-value stores usually do not support such scan operators. A query must be executed using only key-based lookup operations (i.e., get operations) to retrieve data fragments one by one, which can be much more expensive than a scan operator due to response time overhead of each operation.
"On the other hand, one of the inherent features of such stores is the capability of responding to multiple requests in the same time, i.e. parallelizing the requests processing. In systems that use key-values stores for the backend storage while providing a relational interface to the applications, the query optimizer of the relational queries should be able to take advantage of the parallelization capabilities of the underlying key values stores.
"One challenge here is to make optimization aware of effective parallelism: the degree of parallelism that is effective to faster execution time. Parallel key lookup is effective if it can hide latency of each lookup, but excessive parallelism does not improve performance if the query execution is already busy (i.e., it becomes CPU bound). The effective parallelism depends on the ratio between the response time of key lookup and the computation time of a query, which differs in different environments. Thus an automated approach based on optimization is crucial to efficiently execute a query on key value stores."
Supplementing the background information on this patent, VerticalNews reporters also obtained the inventors' summary information for this patent: "Systems and method are disclosed for query optimization in a scale-out system with a single query processing machine and a distributed key-value storage engine to store data by: deciding the best ordering and parallelization scheme of the different operators in the query execution plan, the optimizer should output the plan that takes the shortest time to answer the query.
"In another aspect, systems and methods 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.
"Advantages of the preferred embodiment may include one or more of the following. The preferred embodiment provides a solution for the query optimization problem in the context of a scale-out data management system. The execution plans produced by the invention run much faster than plans that may be produced without special care for optimization that takes into account the special nature of the scale-out system and its effective parallelization capacity. Notice that the number of effective parallelism can be different in different environments (e.g., different data centers) and that optimization of a query with parallelism in consideration would be a difficult and tedious task without automation that is enabled by the invention. Faster query execution means faster applications, better resource utilization, and more satisfied customers. It also means better throughput i.e. more queries and thus more profit. The produced plan also assumes only very basic interface of the storage engine, thus it can run on very scalable storage engines with basic key-value interface. This means that the system provides flexible and cheap scaling capability, which is needed by many modern applications, such as web applications and Software-As-a-Service applications where the number of queries to the system can grow and shrink very quickly and thus the data management system should be able to elastically grow and shrink with no major rebuilding required. The system provides higher scalability for web application with less engineering effort (i.e., fast and inexpensive). Combined with cloud computing infrastructure, it enables elastic resource management of web applications for evolving workloads. The system achieves the fundamental advantage of relational systems: physical data independence, while enjoying the scale-out and reliability of the modern storage engines."
For the URL and additional information on this patent, see: Tatemura, Junichi; Sawires, Arsany; Po, Oliver; Hacigumus, V. Hakan. Database Distribution System and Methods for Scale-Out Applications. U.S. Patent Number 8620903, filed
Keywords for this news article include: Information Technology,
Our reports deliver fact-based news of research and discoveries from around the world. Copyright 2014, NewsRx LLC
Most Popular Stories
- Chinese May Have Spotted Malaysia Airlines Debris
- Social Media Causee Sleep Deprivation in Students
- Obama, Ukraine Discuss Russian Incursion in Crimea
- First-time Jobless Claims Drop Unexpectedly
- General Electric Plans IPO of Credit Card Unit
- Why Buffett Bets Big on Green Energy
- SXSW Crash Kills 2, Injures 23
- First-time U.S. Jobless Claims Hit 3-month Low
- 'Candy Crush' Maker Files IPO
- U.S. Business Inventories Up, Retail Sales Down