Distributed SQL query processing using key-value storage system

• US 9,626,404 B2
• Filed: 01/06/2016
• Issued: 04/18/2017
• 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:
  US14/989,027
• Publication Number:
  US 20160117363A1
• Time in Patent Office: 468 Days
• Field of Search: 707759, 707760, 707831
• 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 Standard Query Language (SQL) query processing system comprising:

at least a computing device having a processor

a key-value server for storing a plurality of key-value objects, wherein each key-value object of the plurality of key-value objects includes a key comprising a container id concatenated with an object id;

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

an execution component 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 for issuing the SQL query to the execution component.

2. The system of claim 1, wherein the execution component comprises a parser and an execution engine.

3. The system of claim 1, wherein the key-value library is located at a client that is communicatively coupled to the key-value server.

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

5. The system of claim 4, wherein the key-value server features transaction snapshot isolation.

6. 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.

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

8. 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.

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

10. A method for execution on a distributed Standard Query Language (SQL) query processing system, the method comprising:

receiving an SQL query at an execution component of a computing device;

parsing and converting, at the execution component, the SQL query into a plurality of operations executable on a key-value system;

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

storing a plurality of key-value objects at the key-value server, wherein each key-value object of the plurality of key-value objects includes a key comprising a container id concatenated with an object id; and

processing an operation on one of the plurality of key-value objects.

11. The method of claim 10, further comprising executing an application for issuing the SQL query to the execution component.

12. The method of claim 11, wherein the application is executed on a client.

13. The method of claim 12, further comprising communicatively coupling the key-value server to the client.

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

15. A computer-readable storage hardware device comprising computer-readable instructions for executing an Standard Query Language (SQL) query using a transactional key-value system, the computer-readable storage hardware device comprising instructions that cause a processor to:

parse and convert, at an execution component for receiving the SQL query from an application, the SQL query into a plurality of operations executable on the transactional key-value system; and

map an SQL table to a plurality of key-value objects in the transactional key-value system, wherein each key-value object of the plurality of key-value objects includes a key comprising a container id concatenated with an object id.

16. The computer-readable storage hardware device of claim 15, 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 storage hardware device of claim 16, further comprising instructions for causing the processor to map the SQL indices to a distributed skiplist.

18. The computer-readable storage hardware device of claim 15, further comprising instructions for causing the processor to cache data at a client using at least one of a key-value cache or an SQL cache.

19. The computer-readable storage hardware device of claim 15, wherein at least one of the plurality of operations is a transaction.