Distributed SQL query processing using key-value storage system

• US 9,268,834 B2
• Filed: 12/13/2012
• Issued: 02/23/2016
• Est. Priority Date: 12/13/2012
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Inventors: Aguilera, Marcos K., Leners, Joshua, Walfish, Michael
• Primary Examiner(s): Fleurantin, Jean B
• Application Number:
  US13/712,993
• Publication Number:
  US 20140172898A1
• Time in Patent Office: 1,167 Days
• Field of Search: 707/759, 707/760, 707/831
• US Class Current: 1/1
• CPC Class Codes: G06F 16/2329 using versioning
• CPC Class Codes: G06F 16/2445 Data retrieval commands; View definitions
• CPC Class Codes: G06F 16/2452 Query translation
• CPC Class Codes: G06F 16/24542 Plan optimisation
• CPC Class Codes: G06F 16/27 Replication, distribution or synchronisation of data between databases or within a distributed database system; Distributed database system architectures therefor
• CPC Class Codes: G06F 16/951 Indexing; Web crawling techniques

Abstract

Distributed storage systems support SQL while also providing scalability and fault tolerance by utilizing an SQL library (the SQL execution component) layered on top of a transactional key-value system (the storage component). The SQL library comprises a parser and an execution engine running at the client, while the storage component comprises a key-value system for storing the data. The SQL library parses SQL queries received from client applications and maps them to transactions on the key-value system. The key-value system stores data items identified by key and provides concurrency control mechanisms to handle concurrent transactions. The key-value system may be a distributed system with several storage servers, each attached to one or more storage devices.

Claims

1. A distributed SQL query processing system comprising:

a key-value server featuring transaction snapshot isolation for storing a plurality of key-value objects, and

further featuring transaction atomicity and consistency;

a client that is communicatively coupled to the key-value server;

a key-value library for processing an operation on one of the plurality of key-value objects;

an SQL library for receiving an SQL query from an application and converting the SQL query into the operation for the key-value library to process; and

the application executing on the client for issuing the SQL query to the SQL library.

2. The system of claim 1, wherein the operation for the key-value library to process is a transaction.

3. The system of claim 2, wherein the key-value server also features transaction durability.

4. The system of claim 1, wherein the key-value server further comprises a remote procedure protocol (RPC) server component, and wherein the key-value library further comprises an RPC client component.

5. The system of claim 1, wherein the key-value server utilizes multiversion storage.

6. The system of claim 1, wherein the key-value server comprises a key-value storage, and wherein the key-value library comprises a local key-value storage representative of the key-value storage on the key-value server.

7. The system of claim 1, wherein the key-value library and the SQL library are located at the client.

8. The system of claim 1, further comprising concurrency control.

9. A method for execution on a distributed SQL query processing system, the method comprising:

executing an application on a client for issuing an SQL query to an SQL library;

receiving from the application, at the SQL library executing on a client, the SQL query;

parsing and converting, at the SQL library on the client, the SQL query into a plurality of operations executable on a key-value system featuring transaction snapshot isolation, transaction atomicity, and consistency; and

forwarding the plurality of operations to a key-value server,

wherein the client is communicatively coupled to the key-value server.

10. The method of claim 9, wherein at least one operation is a transaction.

11. The method of claim 10, wherein the transaction uses a temporary table.

12. The method of claim 9, wherein scaling the transactional key-value data storage system comprises adding a second client.

13. The method of claim 9, wherein the SQL query refers to an SQL table, and a rowid is utilized by the system as the primary key for the SQL table and as a key for the transactional key-value data storage system.

14. A computer-readable storage hardware device comprising computer-readable instructions for executing an SQL query using a transactional key-value system featuring transaction snapshot isolation,

transaction atomicity, and consistency,

the computer-readable storage hardware device comprising instructions that cause a processor to parse and convert,

at an SQL library for receiving the SQL query from an application executing on a client that is communicatively coupled to a key-value server, and

for issuing the SQL query to the SQL library,

the SQL query into a plurality of operations executable on the transactional key-value system.

15. The computer-readable medium of claim 14, further comprising instructions for causing the processor to map an SQL table to a plurality of key-value objects in the transactional key-value system.

16. The computer-readable medium of claim 14, further comprising instructions for causing the processor to map a plurality of SQL indices corresponding to an SQL table to a plurality of key-value objects in the transactional key-value system.

17. The computer-readable medium of claim 16, further comprising instructions for causing the processor to map the SQL indices to a distributed skiplist.

18. The computer-readable medium of claim 14, further comprising instructions for causing the processor to cache data at a client using a key-value cache, an SQL cache, or both.

19. The computer-readable medium of claim 18, further comprising instructions for causing the processor to utilize an SQL cache for the table schemas.