Responding to a query in a data processing system

• US 8,725,730 B2
• Filed: 05/23/2011
• Issued: 05/13/2014
• 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: Keeton, Kimberly, Morrey, Charles B. III, Soules, Craig A.
• Primary Examiner(s): Wu, Yicun
• Application Number:
  US13/113,507
• Publication Number:
  US 20120303627A1
• Time in Patent Office: 1,086 Days
• Field of Search: 707/741, 707/736
• US Class Current: 707/736
• 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:

producing an output structure by 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;

associating a membership structure with the output structure produced by the particular processing stage; and

in response to a query received from a query client after the output structure has been produced by the particular processing stage, accessing, by at least one processor, the membership structure to determine whether the membership structure indicates that data responsive to the query is present in the partially processed data in the output structure.

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 produced by the particular processing stage comprises associating the membership structure with the output structure produced by 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 produced by the particular processing stage comprises associating the membership structure with the output structure produced by the particular processing stage 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. The method of claim 1, further comprising:

producing an answer for the query from an output structure produced by a second of the processing stages; and

in response to the membership structure indicating that data responsive to the query is present in the output structure produced by the particular processing stage, indicating that the answer for the query from the output structure produced by the second processing stage is potentially out-of-date.

12. The method of claim 11, further comprising:

in response to the indicating, accessing the output structure produced by the particular processing stage to update the answer.

13. The method of claim 11, further comprising:

in response to the indicating, causing display of an indication at the query client that the answer is potentially out-of-date.

14. A data processing system comprising:

at least one processor;

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

a query processing engine executable on the at least one processor to;

receive a query;

in response to the query, access a membership structure to determine whether partially processed data produced by 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 output is potentially out-of-date, according to the determining performed based on accessing the membership structure.

15. The data processing system of claim 14, wherein the query is associated with a freshness specification, and wherein the accessed membership structure is associated with the partially processed data that is within a freshness bound specified by the freshness specification.

16. The data processing system of claim 14, wherein the membership structure includes a Bloom filter.

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

refine the initial answer in response to the indication indicating that 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.

18. The data processing system of claim 14, 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.

19. The data processing system of claim 14, 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.

20. The data processing system of claim 14, wherein the query is associated with a freshness specification, and wherein accessing the membership structure is in response to a determination based on the freshness specification that more up-to-date data is to be retrieved from the output structure produced by the particular processing stage.

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

produce an output structure by 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;

associate a Bloom filter with the output structure produced by the particular processing stage; and

in response to a query received from a query client after the output structure has been produced by the particular processing stage, access the Bloom filter to determine whether the Bloom filter indicates that data responsive to the query is present in the partially processed data in the output structure.

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

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

24. The article of claim 21, wherein the instructions upon execution cause the data processing system to further:

produce an answer for the query from an output structure produced by a second of the processing stages; and

in response to the Bloom filter indicating that data responsive to the query is present in the output structure produced by the particular processing stage, indicate that the answer for the query from the output structure produced by the second processing stage is potentially out-of-date.