FILTERING QUERIED DATA ON DATA STORES

• US 20120166447A1
• Filed: 12/28/2010
• Published: 06/28/2012
• Est. Priority Date: 12/28/2010
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Nice, Nir, Sitton, Daniel, Kremer, Dror, Feldman, Michael
• Granted Patent: US 10,311,105 B2
• Time in Patent Office: Days
• US Class Current: 707/746
• 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 o 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 requests targeting a data set on a data store having a processor, the method comprising:

executing on the processor instructions configured to;

upon receiving a data item, store the data item in the data set; and

upon receiving a request specifying at least one filter criterion;

retrieve the data items of the data set satisfying the at least one filter criterion to generate a filtered data subset, and

send the filtered data subset in response to the request.

2. The method of claim 1:

the data store comprising at least one index for at least one filter criterion;

the instructions configured to, upon receiving the data item, index the data item in at least one index according to at least one filter criterion; and

retrieving the data items of the data set satisfying the at least one filter criterion comprising;

for respective filter criteria, using an index corresponding to the filter criterion, identifying the data items satisfying the filter criterion.

3. The method of claim 2, at least one index selected from an index set comprising:

an event index specifying an 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.

4. The method of claim 2, the index specifying, for a filter criterion value of a filter criterion corresponding to the index, a data item set identifying the data items having the filter criterion value for the filter criterion.

5. The method of claim 4:

indexing a data item in the at least one index comprising;

for respective filter criteria, adding the data item to the data item set of data items having the filter criterion value for the filter criterion; and

identifying the data items satisfying a filter criterion having a filter criterion value comprising;

retrieving the data item set of data items having the filter criterion value for the filter criterion.

6. The method of claim 5:

the data store having a data item buffer configured to store received data items; and

storing the data item comprising;

when the data items stored in the data item buffer exceeds 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.

7. The method of claim 4:

the data store comprising at least one data item partition configured to store data items having a filter criterion value for a filter criterion; and

retrieving the data items of the data set satisfying the at least one filter criterion comprising;

for at least one filter criterion value for respective filter criteria, retrieving the data items stored in the data item partition storing data items having the filter criterion value for the filter criterion.

8. The method of claim 7, the instructions configured to, upon receiving a data item:

identify at least one filter criterion value for at least one filter criterion corresponding to the index;

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.

9. The method of claim 7:

the data store comprising;

at least one data item partition configured to store data items having a first filter criterion value for a first filter criterion and a second filter criterion value for a second filter criterion; and

at least one index configured to identify, for data items having a first filter criterion value for the first filter criterion, the respective data item partitions storing data items also having respective second filter criterion values for the second filter criterion.

10. The method of claim 9, storing a data item comprising:

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

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

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

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

store the data item in the data item partition.

11. The method of claim 9, retrieving at least one data item in response to a request specifying 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, identify the data item partitions storing data items having the first filter criterion value for the first filter criterion;

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

retrieve the at least one data item stored in the data item partition.

12. The method of claim 1:

the request specifying a first filtered data subset to be used to generate the filtered data subset; and

retrieving the data items of the data set comprising;

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.

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

14. The method of claim 1, retrieving the data items comprising:

retrieving all of the data items of the data set; and

sending only the data items satisfying the at least one filter criterion.

15. The method of claim 14:

the data store comprising a data item processor set comprising at least one data item processor having a state and at least one filtering condition and configured to;

upon receiving a data item, update the state of the data item processor; and

upon the state of the data item processor satisfying the at least one filtering condition, authorize the data item to be sent; and

sending only the data items satisfying the at least one filter criterion comprising;

providing respective data items to the data item processor set, and

sending the data items authorized to be sent by the data item processor set.

16. The method of claim 1:

the request received from a requester; and

the instructions configured to, before sending 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

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

17. A method of applying a query to a data set stored by a data store, the method performed by a device having a processor and comprising:

executing on the processor instructions configured to;

from the query, generate a request specifying at least one filter criterion;

send the request to the data store; and

upon receiving from the data store a filtered data subset in response to the request, apply the query to the filtered data subset.

18. The method of claim 17:

the query comprising;

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

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

generating the request comprising;

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

sending the request to the data store comprising;

sending the first request to the data store; and

applying the query comprising;

upon 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

upon receiving from the data store the second filtered data subset in response to the second request, apply the query to the second filtered data subset.

19. The method of claim 17, the instructions configured 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

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

20. A computer-readable storage medium comprising instructions that, when executed on a processor of a data store comprising a processor, a data item buffer, and a data item processor set comprising at least one data item processor having a state and at least one filtering condition and configured to:

upon receiving a data item, update the state of the data item processor; and

upon the state of the data item processor satisfying the at least one filtering condition, authorize the data item to be sent;

and the data store having access to a data set comprising at least one index specifying, for at least one filter criterion value of at least one filter criterion, a data item set identifying a data item partition of data items having the filter criterion value for the filter criterion, the at least one index selected from an index set comprising;

an event index specifying an 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,

fulfill requests received from a requester and targeting the data set by;

upon receiving a data item;

adding the data item to the data item buffer; and

when the data items stored in the buffer exceeds a data item buffer size threshold;

indexing the data item in at least one index according to at least one filter criterion by;

identifying a data item set comprising a data item partition of data items having the filter criterion value of the data item for the filter criterion; and

adding the data item to the data item partition of the data item set; and

emptying the data item buffer; and

upon receiving a request specifying at least one filter criterion;

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

send the filtered subset data size to the requester; and

upon receiving from the requester a filtered data subset authorization;

for respective filter criteria, using an index corresponding to the filter criterion, identifying a data item set for data items having the filter criterion value of the filter criterion;

retrieving the data item partition of the data item set to generate a filtered data subset; and

sending only the data items satisfying the at least one filter criterion by;

providing respective data items to the data item processor set, and

sending the data items authorized to be sent by the data item processor set.