External data access with split index

• US 9,715,515 B2
• Filed: 01/31/2014
• Issued: 07/25/2017
• Est. Priority Date: 01/31/2014
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Inventors: Gankidi, Vinitha Reddy, Halverson, Alan D., Teletia, Nikhil, Patel, Jignesh M.
• Primary Examiner(s): DANG, THANH HA T
• Application Number:
  US14/170,493
• Publication Number:
  US 20150220583A1
• Time in Patent Office: 1,271 Days
• Field of Search: 707696
• CPC Class Codes: G06F 16/2272 Management thereof
• CPC Class Codes: G06F 16/245 Query processing
• CPC Class Codes: G06F 16/41 Indexing; Data structures therefor; Storage structures
• CPC Class Codes: G06F 3/067 Distributed or networked storage systems, e.g. storage area networks [SAN], network attached storage [NAS]

Abstract

A split-index can be employed for access to external data. The index can be created on a primary data storage system for data stored externally on a secondary data storage system. After creation, the index can be utilized to expedite at least query execution over the externally stored data. The index can be updated upon detection of changes to data. Further, even when the index is not completely up to date, the index can be exploited for query execution. Furthermore, hybrid execution is enabled with the index and without the index.

Claims

1. A method, comprising:

creating, by a processor, an index locally in a relational data storage system for data stored external to the relational data storage system in a non-relational data storage system;

receiving a query, by the relational data storage system, for at least a portion of the data in the non-relational data storage system;

determining that the index is current with respect to an indexed portion of the data stored external to the relational data storage system, and stale with respect to an updated portion of the data stored external to the relational data storage system;

identifying, as a first selected data subset, data of the indexed portion that satisfies the query based on the index;

scanning the updated portion of the data stored external to the relational data storage system to identify a second selected data subset matching the query; and

returning the first selected data subset and the second selected data subset in response to the query.

2. The method of claim 1, further comprising:

restricting identifying the data satisfying the query with the index to a query with selectivity according to a probability that a segment of the data satisfies a filter expression of a query.

3. The method of claim 1, further comprising:

updating the index to reflect changes to the data stored externally in the non-relational data storage system.

4. The method of claim 1, further comprising:

determining one or more updates to the index based on one or more changes to the data stored externally in the non-relational data storage system concurrently with query execution.

5. The method of claim 4, further comprising:

committing the updates to the index during a temporary pause in processing activity.

6. The method of claim 1, further comprising:

processing at least a portion of the query over the data in the non-relational data storage system without the index.

7. The method of claim 1, further comprising:

executing a portion of the query over relational data stored in the relational data storage system in combination with data satisfying the query from the non-relational data storage system.

8. A system, comprising:

a processor; and

a memory storing instructions, wherein execution of the instructions by the processor causes a device to;

create an index locally in a relational data storage system for data stored external to the relational data storage system in a non-relational data storage system;

receive a query, by the relational data storage system, for at least a portion of the data in the non-relational data storage system;

determine that the index is current with respect to an indexed portion of the data stored external to the relational data storage system, and stale with respect to an updated portion of the data stored external to the relational data storage system;

identify, as a first selected data subset, data of the indexed portion that satisfies the query based on the index;

scanning the updated portion of the data stored external to the relational data storage system to identify a second selected data subset matching the query; and

return the first selected data subset and the second selected data subset in response to the query.

9. The system of claim 8, wherein the relational data storage system is a relational data warehouse system.

10. The system of claim 9, wherein the non-relational data storage system is a non-relational distributed file system.

11. The system of claim 8, wherein execution of the instructions further causes the device to execute the query over the data stored externally without the index for data that changed since the index was created.

12. The system of claim 8, wherein execution of the instructions further causes the device to control execution of a query over the data externally stored with the index based on a signal in the query that indicates that the index is to be utilized.

13. The system of claim 8, wherein execution of the instructions further causes the device to update the index in view of changes to the data.

14. The system of claim 13, wherein execution of the instructions further causes the device to perform an incremental update.

15. The system of claim 8, wherein execution of the instructions by the processor further causes the device to control execution of a query over the data externally stored with the index based on selectivity according to a probability that a segment of the data satisfies a filter expression of a query.

16. A computer-readable storage medium having instructions stored thereon, wherein execution of the instructions by a processor of a device causes the device to:

create an index locally in a relational data warehouse system for data stored external to the relational data warehouse system in a non-relational distributed file system;

receive a query, by the relational data warehouse system, for at least a portion of the data stored in the non-relational distributed file system;

determine that the index is current with respect to an indexed portion of the data stored external to the relational data warehouse, and stale with respect to an updated portion of the data stored external to the relational data warehouse;

identify, as a first selected data subset, data of the indexed portion that satisfies the query based on the index;

scan the updated portion of the data stored external to the relational data storage system to identify a second selected data subset matching the query;

return the first selected data subset and the second selected data subset in response to the query.

17. The computer-readable storage medium of claim 16, wherein execution of the instructions by the processor further causes the device to acquire a portion of the data from the non-relational distributed file system for the query without the index.

18. The computer-readable storage medium of claim 16, wherein execution of the instructions by the processor further causes the device to incrementally update the index in response to one or more changes to the data.

19. The computer-readable storage medium of claim 16, wherein execution of the instructions by the processor further causes the device to evaluating a portion of the query over relational data stored in the relational data warehouse system in conjunction with the data satisfying the query from the non-relational distributed file system.