Filtering queried data on data stores

• US 10,311,105 B2
• Filed: 12/28/2010
• Issued: 06/04/2019
• Est. Priority Date: 12/28/2010
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Inventors: Nice, Nir, Sitton, Daniel, Kremer, Dror, Feldman, Michael
• Primary Examiner(s): Trujillo, James
• Assistant Examiner(s): Le, Jessica N
• Application Number:
  US12/979,467
• Publication Number:
  US 20120166447A1
• Time in Patent Office: 3,080 Days
• Field of Search: 707746
• CPC Class Codes: G06F 16/24532 of parallel queries
• CPC Class Codes: G06F 16/90335 Query processing

Abstract

A data set may be distributed over many data stores, and a query may be distributively evaluated by several data stores with the results combined to form a query result (e.g., utilizing a MapReduce framework). However, such architectures may violate security principles by performing sophisticated processing, including the execution of arbitrary code, on the same machines that store the data. Instead of processing queries, a data store may be configured only to receive requests specifying one or more filtering criteria, and to provide the data items satisfying the filtering criteria. A compute node may apply a query by generating a request including one or more filter criteria, providing the request to a data node, and applying the remainder of the query (including sophisticated processing, and potentially the execution of arbitrary code) to the data items provided by the data node, thereby improving the security and efficiency of query processing.

Claims

1. A method of fulfilling queries targeting a data set comprising a set of records that are stored in a data store accessible to a computer having a processor, the method comprising:

executing, on the processor, instructions that cause the computer to;

receive a query targeting the data set, wherein the query specifies a set of selected attributes of the data set and a computation to be applied only to a portion of the data set that matches at least one filter criterion;

partition the query into a filter portion that filters the data set into a filtered data subset according to the at least one filter criterion, and a computation portion specifying at least one computation to be performed only on the filtered data subset of the data store;

according to the filter portion of the query, generate a filtering request to retrieve a filtered data subset comprising a first portion of the data set satisfying the at least one filter criterion and excluding a second portion of the data set not satisfying the at least one filter criterion, according to the at least one filter criterion distinguishing the first portion from the second portion of the data set;

send the generated filtering request to the data store to cause the data store to return the selected attributes of all records satisfying the filter criterion and exclude all records not satisfying the filter criterion; and

responsive to receiving the selected attributes of the filtered data subset from the data store responsive to the filtering request, apply the computation portion of the query to the filtered data subset.

2. The method of claim 1, wherein:

the data store further comprises an index that specifies, for a filter criterion value of the filter criterion, a data item set identifying the data items of the data set having the filter criterion value for the filter criterion, wherein the index is selected from an index set further comprising;

an event index specifying an event represented by respective data items;

a time index specifying a time of an event represented by respective data items; and

a user index specifying at least one user associated with an event represented by respective data items; and

the filtering request further specifies the filter criterion that is indexed by the index stored by the data store.

3. The method of claim 1, wherein:

the data store further comprises a data item buffer that stores received data items; and

storing the data item further comprises;

for the data items stored in the data item buffer exceeding a data item buffer size threshold;

adding respective data items of the data item buffer in the data item set, and

emptying the data item buffer.

4. The method of claim 1, wherein:

the data store further comprises at least one data item partition that stores data items having a filter criterion value for a filter criterion; and

invoking the data store with the request further comprises;

for at least one filter criterion value for respective filter criteria, invoking the data store with the data item partition storing data items having the filter criterion value for the filter criterion.

5. The method of claim 4, wherein executing the instructions further causes the computer to, responsive to receiving a data item:

identify at least one filter criterion value for at least one filter criterion that is indexed by an index used by the data store;

identify a data item partition storing data items having the filter criterion value for the filter criterion; and

store the data item in the data item partition.

6. The method of claim 5, wherein storing a data item further comprises:

identifying a first filter criterion value of the data item for the first filter criterion;

using the index, identifying the data item partitions storing data items having the first filter criterion value for the first filter criterion;

identifying a second filter criterion value of the data item for the second filter criterion;

among the data item partitions, identifying the data item partition storing data items having the second filter criterion value for the second filter criterion; and

storing the data item in the data item partition.

7. The method of claim 5, wherein invoking the data store with the request further comprises:

invoking the data store with the request and a first filter criterion value for a first filter criterion and a second filter criterion value for a second filter criterion comprising;

using the index, identifying the data item partitions storing data items having the first filter criterion value for the first filter criterion;

among the data item partitions, identifying the data item partition storing data items having the second filter criterion value for the second filter criterion; and

invoking the data item partition with the request to retrieve the at least one data item.

8. The method of claim 1, wherein:

the request further specifies a first filtered data subset that is to be used to generate the filtered data subset; and

invoking the data store with the request further comprises;

invoking the data store with the request and the first filtered data subset to retrieve the data items of the data set satisfying the at least one filter criterion and using the first filtered data subset to generate a filtered data subset.

9. The method of claim 8, wherein the first filtered data subset is generated by the data store in response to a preceding request specifying at least one first filter criterion.

10. The method of claim 1, wherein executing the instructions further causes the computer to, before invoking the request to retrieve the filtered data subset:

estimate a filtered data subset size of the filtered data subset;

send the filtered subset data size to the requester; and

responsive to receiving from the requester a filtered data subset authorization, send the filtered data subset in response to the request.

11. The method of claim 1, wherein:

the data items of the data set are distributed between a first data store and a second data store; and

invoking the data store with the filtering request further comprises;

between the first data store and the second data store, identify a selected data store that is likely to contain the data items specified by the query; and

invoke the selected data store with the filtering request.

12. The method of claim 1, wherein:

executing the instructions further causes the device to;

among attributes of the data set, identify a selected attribute that is likely to be targeted by filter criteria; and

responsive to receiving the data item to be stored with the data set, indexing the data item in an index according to the selected attribute.

13. The method of claim 12, wherein:

the index further comprises;

a first index that indexes the data items according to a first attribute, and

a second index that indexes the data items according to a second attribute; and

indexing the data item further comprises;

indexing the data item in the first index according to the first attribute; and

indexing the data item in the second index according to the second attribute.

14. A device that applies queries to a data set comprising a set of records that are stored by a remote data store accessible through a remote server, the device comprising:

a processor, and

a memory storing instructions that, when executed by the processor, instructions that cause the device to;

receive a query targeting the data set, wherein the query specifies a set of selected attributes on the data set and a computation to be applied only to a portion of the data set that matches at least one filter criterion;

partition the query into a filter portion that filters the data set into a filtered data subset that satisfies the at least one filter criterion, and a computation portion specifying at least one computation to be performed only on the filtered data subset;

according to the filter portion of the query, generate a filtering request to retrieve a filtered data subset comprising a first portion of the data set satisfying the at least one filter criterion and excluding a second portion of the data set not satisfying the at least one filter criterion, according to the at least one filter criterion distinguishing the first portion from the second portion of the data set;

send the generated filtering request to the remote data store to return the selected attributes of all records satisfying the filter criterion and excluding all records not satisfying the filter criterion; and

responsive to receiving the selected attributes of the filtered data subset from the remote data store responsive to the filtering request, apply the computation portion of the query to the filtered data subset.

15. The device of claim 14, wherein:

the query further comprises;

a first filter criterion generating a first filtered data subset, and

a second filter criterion generating a second filtered data subset from the first filtered data subset;

generating the request further comprises;

generating a first request specifying the first data subset filtered according to the first filter criterion;

sending the request to the remote data store further comprises;

sending the first request to the remote data store; and

applying the query further comprises;

responsive to receiving from the remote data store the first filtered data subset in response to the first request;

generating a second request specifying the second data subset filtered according to the second filter criterion and using the first filtered data subset; and

sending the second request to the remote data store; and

responsive to receiving from the remote data store the second filtered data subset in response to the second request, apply the computation portion of the query to the second filtered data subset.

16. The device of claim 14, wherein executing the instructions further causes the device to, before receiving the filtered data subset from the remote data store:

receive from the remote data store a filtered data subset size of the filtered data subset;

verify the filtered data subset size to generate a filtered data subset authorization; and

responsive to generating a filtered data subset authorization, send the filtered data subset authorization to the remote data store.

17. A memory device storing instructions that, when executed on a processor of a computer having access to a data store, cause the device to apply queries to a data set stored by the data store, by:

receive a query targeting the data set and specifying a set of selected attributes of the data set and a computation to be applied only to a portion of the data set that matches at least one filter criterion;

partition the query into a filter portion that filters the data set into a filtered data subset according to the at least one filter criterion, and a computation portion specifying at least one computation to be performed only on the filtered data subset of the data store;

according to the filter portion of the query, generate a filtering request to retrieve a filtered data subset comprising a first portion of the data set satisfying the at least one filter criterion and excluding a second portion of the data set not satisfying the at least one filter criterion, according to the at least one filter criterion distinguishing the first portion from the second portion of the data set;

send the generated filtering request to the data store to cause the data store to return the selected attributes of all records satisfying the filter criterion and exclude all records not satisfying the filter criterion; and

responsive to receiving the selected attributes of the filtered data subset from the data store, apply the computation portion of the query only to the filtered data subset.

18. The memory device of claim 17, wherein:

the query further comprises;

a first filter criterion generating a first filtered data subset, and

a second filter criterion generating a second filtered data subset the first filtered data subset;

generating the request further comprises;

generating a first request specifying the first data subset filtered according to the first filter criterion;

sending the request to the data store further comprises;

sending the first request to the data store; and

applying the query further comprises;

responsive to receiving from the data store the first filtered data subset in response to the first request;

generating a second request specifying the second data subset filtered according to the second filter criterion and using the first filtered data subset; and

sending the second request to the data store; and

responsive to receiving from the data store the second filtered data subset in response to the second request, applying the computation portion of the query to the second filtered data subset.

19. The memory device of claim 17, wherein executing further the instructions further causes the computer to, before receiving the filtered data subset from the data store:

receive from the data store a filtered data subset size of the filtered data subset;

verify the filtered data subset size to generate a filtered data subset authorization; and

responsive to generating a filtered data subset authorization, send the filtered data subset authorization to the data store.

20. The memory device of claim 17, wherein:

the data store further comprises an index that specifies, for a filter criterion value of the filter criterion, a data item set identifying the data items of the data set having the filter criterion value for the filter criterion; and

the filtering request further specifies the filter criterion that is indexed by the index stored by the data store.