RESPONDING TO A QUERY IN A DATA PROCESSING SYSTEM

• US 20120303627A1
• Filed: 05/23/2011
• Published: 11/29/2012
• Est. Priority Date: 05/23/2011
• Status: Active Grant

• Current Assignee: Hewlett Packard Enterprise Development LP (Hewlett-Packard Enterprise Company)
• Original Assignee: Hewlett-Packard Development Company, L.P. (HP Inc.)
• Inventors: Morrey, Charles B. III, Soules, Craig A., KEETON, KIMBERLY
• Granted Patent: US 8,725,730 B2
• Time in Patent Office: Days
• US Class Current: 707/741
• CPC Class Codes: G06F 16/2462 Approximate or statistical queries

Abstract

A data processing system includes a plurality of processing stages. In response to a query, a membership structure is accessed to determine whether partially processed data from a particular one of the processing stages.

Claims

1. A method for use in a data processing system having a plurality of processing stages, comprising:

associating a membership structure with at least an output structure of at least a particular one of the processing stages, wherein the processing stages perform respective different operations on data received by the data processing system, and wherein the output structure contains partially processed data produced by the particular processing stage; and

in response to a query, accessing the membership structure to determine whether the membership structure indicates that data responsive to the query is present in the output structure that contains partially processed data.

2. The method of claim 1, wherein the data processing system includes a processing pipeline having the plurality of processing stages, the method further comprising the plurality of processing stages performing a sequence of corresponding operations with respect to the data received by the data processing system.

3. The method of claim 2, wherein associating the membership structure with the output structure of the particular processing stage comprises associating the membership structure with the output structure of one of the processing stages before a last processing stage in the processing pipeline.

4. The method of claim 3, wherein the plurality of processing stages include a sorting stage to sort data in the data updates, and wherein associating the membership structure with the output structure of the particular processing stage comprises associating the membership structure with the output structure of the particular processing stages before the sorting stage in the processing pipeline.

5. The method of claim 1, wherein an indication provided by the membership structure that data responsive to the query is present in the output structure is potentially a false positive.

6. The method of claim 5, wherein the membership structure includes a Bloom filter.

7. The method of claim 5, wherein the membership structure does not produce a false negative when the membership structure indicates that data responsive to the query is not present in the output structure.

8. The method of claim 1, wherein the membership structure includes a tree-based index.

9. The method of claim 1, wherein the membership structure is a counting Bloom filter to track data in plural output structures produced by at least one of the plurality of processing stages.

10. The method of claim 1, wherein the membership structure is a Bloom filter to track data in plural output structures produced by at least one of the plurality of processing stages, and wherein a lookup of the Bloom filter is based on a value that is a combination of a search key and an identifier of one of the plural output structures, where the search key is based on data in the plural output structures.

11. A data processing system comprising:

a plurality of processing stages to apply respective operations on data; and

a query processing engine to;

receive a query;

in response to the query, access a membership structure to determine whether partially processed data of a particular one of the processing stages potentially contains data responsive to the query; and

provide an output in response to the query, wherein the output has an indication regarding whether the result is up-to-date or potentially out-of-date, according to the determining performed based on accessing the membership structure.

12. The system of claim 11, wherein the query is associated with a freshness specification, and wherein the accessed index structure is associated with the partially processed data that is within a freshness bound specified by the freshness specification.

13. The system of claim 11, wherein the membership structure may produce potential false positives but does not produce false negatives.

14. The system of claim 13, wherein the membership structure includes a Bloom filter.

15. The system of claim 11, wherein the output is an initial answer that potentially is out-of-date, and wherein the query processing engine is to further:

refine the initial answer if the initial answer is potentially out-of-date, wherein refining the initial answer comprises;

searching partially processed data of the processing stages; and

updating the initial answer based on the searching.

16. The system of claim 11, wherein the plurality of processing stages are to apply respective different operations on data updates received by the data processing system, wherein the data updates are to update at least one data table maintained by the data processing system.

17. The system of claim 11, wherein the plurality of processing stages include an ingest stage and a sort stage, and wherein the membership structure is associated with the partially processed data of the ingest stage, wherein the ingest stage is to ingest data into the data processing system, and the sort stage is to sort data after ingestion of the data by the ingest stage.

18. An article comprising at least one machine-readable storage medium storing instructions that upon execution cause a data processing system having a processor to:

associate a Bloom filter with an output structure of at least a particular one of a plurality of processing stages, wherein the processing stages perform respective different operations on data received by the data processing system, and wherein the output structure contains partially processed data produced by the particular processing stage; and

in response to a query, access the Bloom filter to determine whether the Bloom filter indicates that data responsive to the query is present in the output structure.

19. The article of claim 18, wherein the output structure includes unsorted data output by the particular processing stage.

20. The article of claim 19, wherein the plurality of processing stages further includes a sorting stage to sort data, wherein an output structure provided by the sorting stage includes sorted data.