Distributed SQL query processing using key-value storage system

Patent metadata

Field	Value
Publication number	US-9626404-B2
Application number	US-201614989027-A
Country	US
Kind code	B2
Filing date	Jan 6, 2016
Priority date	Dec 13, 2012
Publication date	Apr 18, 2017
Grant date	Apr 18, 2017

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.

First claim

What is claimed:

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.

Assignees

• Microsoft Technology Licensing Llc

Inventors

• Aguilera Marcos K
• Leners Joshua
• Walfish Michael

Classifications

• G06F17/30463

  Physics · mapped topic

• G06F17/30864

  Physics · mapped topic

• G06F17/30356

  Physics · mapped topic

• G06F17/30427

  Physics · mapped topic

• G06F17/30575

  Physics · mapped topic