Filtering pipeline optimizations for unstructured data

• US 10,650,032 B1
• Filed: 04/13/2018
• Issued: 05/12/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, Singh, Karmveer Veer, Liao, Ning, Schiefer, Josef, Banfield, Michael, Qu, Kaiwen, Chawla, Karishma, Yuan, Fusheng, Pender, John, Choudhary, Sameer, Faro, Milos, Zhao, Ruiwen
• Primary Examiner(s): Jacob, Ajith
• Application Number:
  US15/952,787
• Time in Patent Office: 760 Days
• CPC Class Codes: G06F 16/30 of unstructured textual data document management systems G06F16/93
• CPC Class Codes: G06F 16/3325 Reformulation based on results of preceding query
• 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

Abstract

Unstructured data items are stored at an object storage service. A filtering criterion to be used to generate a result set for an access request is determined. A test that can be used to determine, without completing parsing of a record identified in an unstructured data item, whether the record satisfies the filtering criterion is identified. Parsing of a particular record is abandoned in response to determining, using the test, that the record satisfies the filtering criterion. A response to the access request is determined using a subset of records that satisfy 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, including a first unstructured data item;

determine a first query comprising one or more predicates to be used to filter data for inclusion in a response to a first access request directed to the item collection;

based at least in part on an examination of the one or more predicates, identify a first character-level test that can be used to determine, without completing parsing of a particular record identified within the first unstructured data item, whether the particular record satisfies the first query;

abandon parsing of a first record of the first unstructured data item in response to determining, using the first character-level test, that the first record does not satisfy the first query;

determine, using at least a subset of records identified in the first unstructured data item, a response to the first access request, wherein the subset does not include the first record.

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

store, in a cache, one or more parsing shortcut tuples, wherein an individual parsing shortcut tuple comprises (a) a first subset of contents of a second record of the first unstructured data item and (b) an indication of whether the second record satisfied the first query; and

abandoning processing of a third record in response to determining, using a first parsing shortcut tuple of the one or more tuples, that the third record satisfies the first filtering criterion.

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

generate an abstract syntax tree representation of the first query, wherein the first test is based at least in part on an analysis of the abstract syntax tree.

4. The system as recited in claim 1, wherein the first access request indicates a character encoding to be used to interpret one or more unstructured data items.

5. The system as recited in claim 1, wherein the first record comprises a first field and a second field, wherein the one or more predicates include a first predicate on the first field and a second predicate on the second field, wherein the instructions upon execution on the processor cause the one or more computing devices to:

trigger, in response to completion of parsing of the first field of a particular record, an evaluation of the first predicate, wherein the evaluation of the first predicate is performed prior to a completion of parsing the second field of the particular 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;

determining a first filtering criterion for inclusion of data of the collection in a result set to be used to generate a response to a first access request;

identifying a first test that can be used to determine, without completing parsing of a particular record identified within the first unstructured data item of the item collection, whether the particular record satisfies the first filtering criterion;

abandoning parsing of a first record identified within the first unstructured data item in response to determining, using the first test, that the first record does not satisfy the first filtering criterion; and

determining, using a subset of records identified within the first unstructured data item, a response to the first access request, wherein the subset does not include the first record.

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

storing, in a cache, one or more parsing shortcut tuples, wherein an individual parsing shortcut tuple comprises (a) a first subset of contents of a second record obtained from an unstructured data item and (b) an indication of whether the second record satisfied the first filtering criterion; and

abandoning processing of a third record in response to determining, using a first parsing shortcut tuple of the one or more tuples, that the third record satisfies the first filtering criterion.

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

generating a parsed representation of the first filtering criterion, wherein identifying the first test is based at least in part on analyzing the parsed representation.

9. The method as recited in claim 8, wherein the parsed representation comprises an abstract syntax tree.

10. The method as recited in claim 6, wherein the first test comprises one or more of:

(a) determining that a number of characters used to represent a particular field of a record exceeds a threshold or (b) determining that a number of characters used to represent a particular field of a record is less than a threshold.

11. The method as recited in claim 6, wherein the first test comprises identifying a substring mismatch.

12. The method as recited in claim 6, wherein the first access request indicates one or more of (a) a first delimiter to be used to distinguish among individual records within a data item, or (b) a second delimiter to be used to distinguish among fields within individual records of a data item.

13. The method as recited in claim 6, wherein the first access request indicates a character encoding to be used to interpret at least a portion an unstructured data item.

14. The method as recited in claim 6, wherein the first filtering criterion comprises a plurality of predicates on respective fields of data items, including a first predicate on a first field and a second predicate on a second field, the method further comprising performing, by the one or more computing devices:

triggering, in response to completion of parsing of the first field of a particular data item, an evaluation of the first predicate, wherein the evaluation of the first predicate is performed prior to a completion of parsing the second field of the particular data item.

15. The method as recited in claim 6, wherein determining the response comprises:

applying a transformation function to a second record identified within the first unstructured data item, wherein the transformation function is indicated in the first access request; and

including, in the response, a result of the transformation function.

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;

determine a first filtering criterion for inclusion of data of the collection in a result set to be used to generate a response to a first access request;

identify a first test that can be used to determine, without completing parsing of a particular record identified within the first unstructured data item of the item collection, whether the particular record satisfies the first filtering criterion;

abandon parsing of a first record identified within the first unstructured data item in response to determining, using the first test, that the first record satisfies the first filtering criterion; and

determine, using a subset of records identified within the first unstructured data item, a response to the first access request, wherein the subset includes the first record.

17. The non-transitory computer-accessible storage medium as recited in claim 16, wherein the instructions when executed on one or more processors cause the one or more processors to:

store, in a cache, one or more parsing shortcut tuples, wherein an individual parsing shortcut tuple comprises (a) a first subset of contents of a second record obtained from an unstructured data item and (b) an indication of whether the second record satisfied the first filtering criterion; and

abandon processing of a third unstructured data item in response to determining, using a first parsing shortcut tuple of the one or more tuples, that the third unstructured data item satisfies the first filtering criterion.

18. The non-transitory computer-accessible storage medium as recited in claim 16, wherein the instructions when executed on one or more processors cause the one or more processors to:

generate a parsed representation of the first filtering criterion, wherein identification of the first test is based at least in part on an analysis of the parsed representation.

19. The non-transitory computer-accessible storage medium as recited in claim 18, wherein the parsed representation comprises an abstract syntax tree.

20. The non-transitory computer-accessible storage medium as recited in claim 16, wherein the first test comprises one or more of:

(a) determining that a number of characters used to represent a particular field of a record exceeds a threshold or (b) determining that a number of characters used to represent a particular field of a record is less than a threshold.