Low-latency query processor

• US 9,946,752 B2
• Filed: 04/27/2015
• Issued: 04/17/2018
• Est. Priority Date: 04/27/2015
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Inventors: Lydick, Neil E., Aski, Vijaykumar K.
• Primary Examiner(s): Uddin, Mohammed R
• Application Number:
  US14/696,493
• Publication Number:
  US 20160314173A1
• Time in Patent Office: 1,086 Days
• Field of Search: 707722, 707713, 707716, 707718, 707999002
• CPC Class Codes: G06F 16/24553 of query operations
• CPC Class Codes: G06F 16/2457 with adaptation to user needs
• CPC Class Codes: G06F 16/256 in federated or virtual databases

Abstract

Techniques for implementing a low-latency query processor accommodating an arbitrary number of data rows with no column indexing. In an aspect, data is stored across a plurality of component databases, with no requirement to strictly allocate data to partitions based on row keys. A histogram table is provided to map object relationships identified in a user query to the component databases where relevant data is stored. A server processing the user query communicates with component databases via an intermediary module. The intermediary module may include intermediary nodes dynamically assigned to connect to the component databases to retrieve and process the queried data.

Claims

1. A central server apparatus comprising:

a processor;

an application programming interface (API) module to receive and respond to a user query; and

at least one table to generate a histogram output signal identifying a plurality of component databases relevant to an ancestor-descendant relationship extracted from the user query;

wherein the central server apparatus is to submit a query to the plurality of component databases via a plurality of intermediary nodes selected according to a dynamically configured query plan, and to respond to the user query based on results generated by the plurality of component databases and received via the plurality of intermediary nodes; and

wherein each of the plurality of intermediary nodes comprises a cloud computing server;

the query plan specifying the plurality of intermediary nodes such that each intermediary node is directly coupled to no more than a predetermined maximum number of component databases; and

dynamically configuring the query plan to select the plurality of intermediate nodes as a function of load balancing and bandwidth optimization.

2. The apparatus of claim 1, each intermediary node further performing functions comprising sorting, filtering, and paginating results returned from the plurality of component databases prior to returning results to the central server.

3. The apparatus of claim 1, the query plan further specifying a plurality of Layer II intermediary nodes coupled to the plurality of intermediary nodes, each of the plurality of Layer II intermediary nodes being directly coupled to a subset of the plurality of component databases.

4. The apparatus of claim 1, the at least one table comprising:

a root database identifying a root partition index corresponding to a root object derived from the user query; and

a relationship histogram table generating the histogram output signal based on the root partition index and the extracted ancestor-descendant relationship.

5. The apparatus of claim 1, the at least one table comprising a single look-up table generating the histogram output signal based on a root object derived from the user query and the extracted ancestor-descendant relationship.

6. A method comprising:

receiving a user query through an application programming interface (API);

identifying a plurality of component databases relevant to the user query by querying at least one table coupled to a central server, the plurality of component databases storing data corresponding to an ancestor-descendant relationship extracted from the user query;

submitting a query for data to the plurality of component databases via a plurality of intermediary nodes selected according to a dynamically configured query plan; and

responding to the user query through the API based on results generated by the at least one relevant component database and received via the plurality of intermediary nodes;

wherein each of the plurality of intermediary nodes comprises a cloud computing server;

the query plan specifying the plurality of intermediary nodes such that each intermediary node is directly coupled to no more than a predetermined maximum number of component databases; and

dynamically configuring the query plan to select the plurality of intermediate nodes as a function of load balancing and bandwidth optimization.

7. The method of claim 6, further comprising:

at each intermediary node, sorting, filtering, and paginating results returned from the plurality of component databases prior to returning results to the central server.

8. The method of claim 6, the query plan further specifying a plurality of Layer II intermediary nodes coupled to the plurality of intermediary nodes, each of the plurality of Layer II intermediary nodes being directly coupled to a subset of the plurality of component databases.

9. The method of claim 6, further comprising locating and returning a sorted result of sequence number n to the central server by:

sampling an element while skipping w−

1 elements from each of the plurality of component databases, wherein w comprises a skip-read window size;

sorting and reading the sampled elements until all of the plurality of component databases have been processed, or until an uncertainty window exceeds the value of n; and

re-submitting a modified query excluding the sort and read sampled elements and further reducing the value of w to locate the sorted result of sequence number n.

10. A system comprising:

a processor;

a central server to receive and respond to a user query; and

a plurality of component databases;

wherein the central server is to;

access at least one table generating a histogram output signal identifying at least one of the plurality of component databases relevant to an ancestor-descendant relationship extracted from the user query by the central server; and

submit a query to the plurality of component databases via a plurality of intermediary nodes selected according to a dynamically configured query plan;

wherein each of the plurality of intermediary nodes comprises a cloud computing server;

the query plan specifying the plurality of intermediary nodes such that each intermediary node is directly coupled to no more than a predetermined maximum number of component databases; and

dynamically configuring the query plan to select the plurality of intermediate nodes as a function of load balancing and bandwidth optimization.

11. The system of claim 10, each intermediary node further performing functions comprising sorting, filtering, and paginating results returned from the plurality of component databases prior to returning results to the central server.

12. The system of claim 11, each intermediary node configured to paginate results returned from the plurality of component databases by:

running a probe query to determine an n-th sorted element per the user query; and

retrieve results from the plurality of component databases using a modified query excluding the first n results returned.