Ranking query processing method for stream data and stream data processing system having ranking query processing mechanism

• US 8,335,782 B2
• Filed: 08/08/2008
• Issued: 12/18/2012
• Est. Priority Date: 10/29/2007
• Status: Expired due to Fees

• Current Assignee: Hitachi, Ltd.
• Original Assignee: Hitachi, Ltd.
• Inventors: Nishizawa, Itaru, Imaki, Tsuneyuki, Kashiyama, Toshihiko
• Primary Examiner(s): Mofiz, Apu
• Assistant Examiner(s): WALKER, BRYAN L
• Application Number:
  US12/222,413
• Publication Number:
  US 20090112853A1
• Time in Patent Office: 1,593 Days
• Field of Search: 707/731, 707/718, 707/999.005, 707/708, 707/723
• US Class Current: 707/718
• CPC Class Codes: G06F 16/24568 Data stream processing; Continuous queries
• CPC Class Codes: G06F 16/24578 using ranking

Abstract

A mechanism for managing ranking information using a sign of a stream tuple generated when stream data is inserted into, or deleted from, a window is provided. A mechanism for generating only the differential information of ranking calculation results, a mechanism for adding ranking information according to a request, an interface for generating and outputting all ranking information from the differential information, a mechanism for generating all ranking calculation results, and an interface for using these mechanisms are provided.

Claims

1. A ranking query processing method for stream data that receives stream data as a plurality of continually arriving stream tuples to which timestamps are attached and continually executes query processing on the stream data based on a pre-registered query, the method comprising:

determining a lifetime, in a window, of each arriving stream tuple in response to arrival of the stream tuple, and determining an end of a lifetime, in the window, of each previously arrived stream tuple in addition thereto according to a window designation by the query;

generating window differential information indicating insertion of a stream tuple into the window and deletion of a stream tuple from the window at each time;

using the window differential information and archived information to compute a ranking, in the window, concerning an ordered target item between stream tuples that are within the window including stream tuples for which the ranking is outside of an output designation range designated by the query each time a lifetime of a stream tuple starts and each time a lifetime of a stream tuple ends according to ranking processing by the query, and updating a ranking information that indicates the ranking according to the computed ranking;

outputting a stream tuple set of stored stream tuples for which the raking is included in the output designation range designated by the query;

storing the updated ranking information of the stream tuples that are within the window and are present within a lifetime in the window for which the ranking is outside of the output designation range in a ranking information holding buffer that archives the ranking information; and

storing the stream tuples that are within the window and includes tuples for which the ranking is outside of the output designation range.

2. The ranking query processing method for stream data according to claim 1, wherein storing of the ranking information is performed for all stream tuples present within the lifetime.

3. The ranking query processing method for stream data according to claim 1, wherein the ranking information is stored as a table in which each stream tuple and the ranking thereof are mapped within the ranking information holding buffer.

4. The ranking query processing method for stream data according to claim 1, wherein when a ranking information output is designated in the query, the ranking information is output by adding the rankings of the stream tuples to the stream tuples included in the output designation range.

5. The ranking query processing method for stream data according to claim 1, wherein when the ranking information is output, differential information relative to a previous output is generated.

6. The ranking query processing method for stream data according to claim 1, wherein when the ranking information is output, all ranking information is output.

7. The ranking query processing method for stream data according to claim 1, further comprising:

adding, when a stream tuple has arrived, a sign indicating a start of a lifetime to the stream tuple, and adding, when an end of a lifetime of a stream tuple has been determined, another sign indicating the end of the lifetime to the stream tuple, wherein the ranking information is updated using a signed stream tuple.

11. The ranking query processing method for stream data according to claim 1, wherein the output designation range designated by the query specifies an arbitrary place in the ranking as a starting rank for the output designation range.

8. A non-transitory computer-usable storage medium having computer readable instructions stored thereon for execution by a processor to implement a stream data processing system that receives stream data as a plurality of continually arriving stream tuples to which timestamps are attached and continually executes query processing on the stream data based on a pre-registered query, the system comprising:

a window manager that executes a window calculation designated in the query for each arrived stream tuple and determines a lifetime in a window of each stream tuple; and

a ranking processing module that performs ranking processing to compute a ranking between stream tuples in the window including stream tuples for which the ranking is outside of an output designation range designated in the query, outputs a stream tuple set of stored stream tuples for which the ranking is included in the output designation range designated by the query, and stores the stream tuples that are within the window and include tuples for which the ranking is outside of the output designation range,

wherein the window manager includes;

a differential information generator that generates window differential information indicating insertion of a stream tuple into the window and deletion of a stream tuple from the window at each time, and delivers the window differential information to the ranking processing module, and

wherein the ranking processing module includes;

a ranking generator that generates/updates ranking information in a range of stream tuples present in a lifetime in the window from the window differential information delivered by the differential information generator of the window manager and archived information; and

a ranking information holding buffer that archives the ranking information updated by the ranking generator in the range of stream tuples present in the lifetime in the window.

9. The non-transitory computer-readable storage medium according to claim 8, wherein the ranking information holding buffer holds the ranking information as a table in which each stream tuple and the ranking thereof are mapped.

10. The non-transitory computer-readable storage medium according to claim 9, wherein the differential information generator adds, when a stream tuple has arrived, a sign indicating insertion into the window to the stream tuple, adds, at an end time of a lifetime of a determined stream tuple, another sign indicating deletion of the stream tuple from the window, and delivers each sign to the ranking processing module as the window differential information.

12. The non-transitory computer-usable storage medium according to claim 9, wherein the output designation range designated by the query specifies an arbitrary place in the ranking as a starting rank for the output designation range.