Server-side filtering of unstructured data items at object storage services

• US 10,664,508 B1
• Filed: 04/13/2018
• Issued: 05/26/2020
• Est. Priority Date: 04/13/2018
• Status: Active Grant

• Current Assignee: Amazon Technologies, Inc. (Amazon.com, Inc.)
• Original Assignee: Amazon Technologies, Inc. (Amazon.com, Inc.)
• Inventors: Laurence, Douglas Stewart, Liao, Ning, Schiefer, Josef, Choudhary, Sameer, Zhao, Ruiwen, Banfield, Michael, Yuan, Fusheng, Qu, Kaiwen
• Primary Examiner(s): Jacob, Ajith
• Application Number:
  US15/952,806
• Time in Patent Office: 774 Days
• CPC Class Codes: G06F 16/30 of unstructured textual data document management systems G06F16/93
• CPC Class Codes: G06F 16/334 Query execution G06F16/335 takes precedence
• CPC Class Codes: G06F 16/335 Filtering based on additional data, e.g. user or group profiles filtering in web context G06F16/9535, G06F16/9536
• CPC Class Codes: G06F 16/903 Querying for retrieval from the web G06F16/953
• CPC Class Codes: G06F 16/9035 Filtering based on additional data, e.g. user or group profiles

Abstract

Unstructured data items are stored in an item collection. An access request comprising an input interpretation rule and a filtering criterion is directed to at least a portion of the item collection. Records are extracted from an unstructured data item using the input interpretation rule. A response to the access request is obtained, based at least partly in a determination that one of the records satisfies the filtering criterion.

Claims

1. A system, comprising:

one or more computing devices of an object storage service;

wherein the one or more computing devices include instructions that upon execution on a processor cause the one or more computing devices to;

store, in response to one or more programmatic requests, a plurality of unstructured data items of an item collection at a first set of one or more storage devices, wherein the plurality includes a first unstructured data item;

obtain a first programmatic request to retrieve at least a portion of contents of the first unstructured item collection;

in response to determining that the first programmatic request comprises a first input serialization specification and a first filter query,

obtain, from the one or more storage devices using the first input serialization specification, (a) a first formatted record corresponding to at least a first portion of the first unstructured data item and (b) a second formatted record corresponding to at least a second portion of the first unstructured data item;

obtain a response to the first request, based at least in part on a determination that the first formatted record satisfies at least one predicate of the first filter query, and based at least in part on a determination that the second formatted record does not satisfy at least one predicate of the first filter query; and

transmit the response to one or more destinations.

2. The system as recited in claim 1, wherein the first request comprises a first output transformation specification, and wherein the instructions upon execution on a processor cause the one or more computing devices to:

generate, based at least in part on the first output transformation specification, a transformed version of at least a portion of the first formatted record; and

include, in the response, the transformed version.

3. The system as recited in claim 1, wherein the instructions upon execution on the processor cause the one or more computing devices to:

cache a first result set corresponding to the first filter query at a second set of devices, wherein the result set comprises at least a portion of the first formatted record;

determine that a result set corresponding to a second filter query can be obtained using at least a portion of the first result set, wherein the second filter query is indicated in a second programmatic request; and

determine a response to the second programmatic request without accessing the first set of storage devices.

4. The system as recited in claim 1, wherein to obtain the first programmatic request, the instructions upon execution on the processor cause the one or more computing devices to:

determine that a REST API (Representational State Transfer application programming interface) has been invoked.

5. The system as recited in claim 1, wherein the first formatted record is obtained based at least in part on a first record delimiter indicated in the first input serialization specification, wherein the instructions upon execution on the processor cause the one or more computing devices to:

in response to determining that a second programmatic request directed to the first unstructured data item comprises a second input serialization specification and a second filter query, wherein the second input serialization specification indicates a second record delimiter,

obtain, from the one or more storage devices using the second record delimiter, a third formatted record corresponding to at least a third portion of the first unstructured data item, wherein the third portion overlaps at least in part with the first portion, and wherein the third portion overlaps at least in part with the second portion; and

generate, using the second filter query, a response to the second programmatic request, wherein the response to the second programmatic request includes at least a portion of the third formatted record.

6. A method, comprising:

performing, by one or more computing devices of an object storage service;

storing a plurality of unstructured data items of an item collection, including a first unstructured data item;

in response to determining that a first programmatic request directed to at least a portion of the item collection comprises a first input interpretation rule and a first filtering criterion,

obtaining, using the first input interpretation rule, (a) a first record corresponding to at least a first portion of the first unstructured data item and (b) a second record corresponding to at least a second portion of the first unstructured data item;

obtaining a response to the first programmatic request, based at least in part on a determination that the first record satisfies the first filtering criterion, and based at least in part on a determination that the second record does not satisfy the first filter criterion.

7. The method as recited in claim 6, wherein the first programmatic request comprises an output transform specification, wherein the response comprises a transformed version of at least a portion of the first record, and wherein the transformed version is obtained using the output transform specification.

8. The method as recited in claim 6, wherein obtaining the first record comprises accessing a first set of storage devices, the method further comprising performing, by the one or more computing devices:

caching a first result set corresponding to the first filtering criterion at a second set of devices, wherein the result set comprises at least a portion of the first record;

determining that a result set corresponding to a second filtering criterion can be obtained using at least a portion of the first result set, wherein the second filtering criterion is indicated in a second programmatic request; and

obtaining a response to the second programmatic request without accessing the first set of storage devices.

9. The method as recited in claim 8, further comprising performing, by the one or more computing devices:

determining, prior to caching the first result set, that a caching permission with respect to the first result set has been granted by a client of the object storage service.

10. The method as recited in claim 6, further comprising performing, by the one or more computing devices:

obtaining an indication, via a programmatic interface, of one or more field-level access permission settings for records extractable from a second unstructured data item of the item collection, wherein individual ones of the records extractable from the second unstructured data item comprise one or more fields; and

verifying, prior to providing a response to a second programmatic request directed at least to the second unstructured data item, wherein the second programmatic request includes a second input interpretation rule and a second filtering criterion, that providing the response would not violate the one or more field-level access permission settings.

11. The method as recited in claim 6, wherein the first programmatic request is received from a first client of the object storage service, the method further comprising performing, by the one or more computing devices:

obtaining, based at least in part on analysis of one or more of (a) a set of previously submitted programmatic requests directed to the item collection or (b) contents of metadata pertaining to the item collection, a predicted filtering criterion of a future programmatic request from the first client;

obtaining, from the item collection, a result set corresponding to the predicted filtering criterion prior to receiving a programmatic request comprising the predicted filtering criterion, wherein the result set comprises at least a portion of the first record;

storing the result set corresponding to the predicted filtering criterion in a cache; and

providing, using the cache, a response to a second programmatic request received from the client.

12. The method as recited in claim 6, further comprising performing, by the one or more computing devices:

collecting respective sets of metrics from one or more stages of a filtering pipeline, wherein the filtering pipeline comprises at least a parsing stage and a predicate evaluation stage, and wherein the filtering pipeline is used to determine whether the first record satisfies the first filtering criterion;

tuning, based at least in part on a machine learning-based analysis of the respective sets of metrics, one or more parameters of at least one stage of the one or more stages.

13. The method as recited in claim 12, wherein a first parameter of the one or more parameters comprises one or more of:

(a) a number of concurrent threads of execution or (b) a record batch size.

14. The method as recited in claim 6, wherein the first programmatic request is received via a web services application programming interface (API).

15. The method as recited in claim 6, wherein the first filtering criterion is expressed in a language based at least in part on a version of Structured Query Language (SQL).

16. A non-transitory computer-accessible storage medium storing program instructions that when executed on one or more processors cause the one or more processors to:

store a plurality of unstructured data items of an item collection, including a first unstructured data item;

in response to determining that a first programmatic request directed to at least a portion of the item collection comprises a first input interpretation rule and a representation of a first filtering criterion,

obtain, using the first input interpretation rule, (a) a first record corresponding to at least a first portion of the first unstructured data item and (b) a second record corresponding to at least a second portion of the second unstructured data item;

obtain a response to the first request, based at least in part on a determination that the first record satisfies the first filtering criterion, and based at least in part on a determination that the second record does not satisfy the first filtering criterion.

17. The non-transitory computer-accessible storage medium as recited in claim 16, wherein the first programmatic request comprises an output transform specification, wherein the response comprises a transformed version of at least a portion of the first record, and wherein the transformed version is obtained using the output transform specification.

18. The non-transitory computer-accessible storage medium as recited in claim 16, wherein the first record is obtained from a first set of storage devices, and wherein the instructions when executed on the one or more processors cause the one or more processors to:

cache a first result set corresponding to the first filtering criterion at a second set of devices, wherein the result set comprises at least a portion of the first record;

determine that a result set corresponding to a second filtering criterion can be obtained using at least a portion of the first result set, wherein the second filtering criterion is indicated in a second programmatic request; and

obtain a response to the second programmatic request without accessing the first set of storage devices.

19. The non-transitory computer-accessible storage medium as recited in claim 16, wherein the first programmatic request is obtained from a first client of the object storage service, wherein the instructions when executed on the one or more processors cause the one or more processors to:

obtain, based at least in part on analysis of a set of previously submitted programmatic requests directed to the item collection, a predicted filtering criterion of a future programmatic request from the first client;

determine, from the item collection, a result set corresponding to the predicted filtering criterion prior to receiving a programmatic request comprising the predicted filtering criterion, wherein the result set comprises at least a portion of the first record;

store the result set corresponding to the predicted filtering criterion in a cache; and

provide, using the cache, a response to a second programmatic request received from the client.

20. The non-transitory computer-accessible storage medium as recited in claim 16, wherein the first programmatic request comprises an indication of a compression algorithm used to store at least some data items of the item collection, and wherein to obtain the first record, the instructions when executed on the one or more processors cause the one or more processors to utilize a decompression algorithm corresponding to the compression algorithm.