System and method for indexing queries, rules and subscriptions

• US 7,313,554 B2
• Filed: 09/29/2003
• Issued: 12/25/2007
• Est. Priority Date: 09/29/2003
• Status: Active Grant

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Chen, Shyh-Kwei, Wu, Kun-Lung, Yu, Philip S., Mei, Mark (Gee-Gwo)
• Primary Examiner(s): Rimell, Sam
• Assistant Examiner(s): Colan, Giovanna B.
• Application Number:
  US10/673,651
• Publication Number:
  US 20050071322A1
• Time in Patent Office: 1,548 Days
• Field of Search: 707/3, 707/4, 707/2, 707/100
• US Class Current: 707/745
• CPC Class Codes: G06F 16/2237 Vectors, bitmaps or matrices
• CPC Class Codes: G06F 16/24568 Data stream processing; Continuous queries
• CPC Class Codes: Y10S 707/99933 Query processing, i.e. searching
• CPC Class Codes: Y10S 707/99934 Query formulation, input preparation, or translation

Abstract

This invention introduces a new concept called virtual construct intervals (VCI), where each predicate interval is decomposed into one or more of these construct intervals. These VCIs strictly cover the predicate interval. Namely, every attribute value covered by the predicate interval is also covered by at least one of the decomposed VCIs, and vice versa. Each construct interval has a unique ID or interval coordinate and a set of endpoints. A construct interval is considered activated when a predicate interval using it in its decomposition is added to the system. The predicate ID is then inserted into the ID lists associated with the decomposed VCIs. To facilitate fast search, a bitmap vector is used to indicate the activation of VCIs that cover an event value. The challenge is to find an appropriate set of construct intervals to make predicate decomposition simple and, more importantly, to build efficient bitmap indexes. Because each construct interval covers only a small range of attribute values, the invention also uses bitmap clipping to cut unnecessary bitmap storage. To facilitate bitmap clipping, the invention introduce the covering segment concept. Bit positions outside a covering segment are pruned.

Claims

1. A method for maintaining and using a query index to support continual query monitoring, said method comprising:

defining groups of virtual construct intervals, wherein said virtual construct intervals represent predetermined ranges of data values and correspond to specific bit positions in bit map vectors;

determining predicate intervals, wherein said predicate intervals represent specified ranges of data values from continual queries; and

inserting each of said predicate intervals into said bit map positions of at least one of said groups of said virtual construct intervals such that said specified ranges of data values of said predicate intervals are aligned with said predetermined ranges of said data values of said virtual construct intervals.

2. The method in claim 1, wherein each of said groups of virtual construct intervals is adapted to hold multiple predicate intervals, and

wherein said groups of virtual construct intervals have uniform lengths, and

wherein said predicate intervals have non-uniform lengths.

3. The method in claim 1, further comprising maintaining locations of said predicate intervals within said groups of virtual construct intervals using a predicate ID bitmap vector.

4. The method in claim 1, wherein said process of defining said groups of virtual construct intervals comprises beginning all virtual construct intervals in a group of virtual construct intervals at a same data value and ending said virtual construct intervals in said group of virtual construct intervals at different data values.

5. The method in claim 1, wherein said process of inserting said predicate intervals into said virtual construct intervals, comprises inserting said predicate interval into the same sized virtual construct interval.

6. The method in claim 1, wherein when a predicate interval is larger than any of said virtual construct intervals, said inserting process comprises:

inserting an initial portion of said predicate interval into the largest available virtual construct interval, wherein a length in excess of a length of said initial portion of said predicate interval comprises a remnant predicate interval; and

inserting the remnant predicate interval into the same length virtual construct interval.

7. The method in claim 1, wherein said inserting further comprises inserting said predicate intervals such that each of said virtual construct intervals holds multiple predicate intervals, wherein all of said groups of said virtual construct intervals within said query index have the same pattern of different sized virtual construct intervals.

44. The method of claim 1, wherein said predetermined range intervals of at least some of said virtual construct intervals between and within said groups of construct intervals overlap.

8. A method for maintaining and using a query index to support continual query monitoring, said method comprising:

defining groups of virtual construct intervals, wherein said virtual construct intervals represent predetermined ranges of data values and correspond to specific bit positions in bit map vectors;

determining predicate intervals, wherein said predicate intervals represent specified ranges of data values from continual queries; and

inserting each of said predicate intervals into said bit map positions of at least one of said groups of said virtual construct intervals such that said specified ranges of data values of said predicate intervals are aligned with said predetermined ranges of said data values of said virtual construct intervals,

wherein each of said groups of virtual construct intervals is adapted to hold multiple predicate intervals,

wherein all of said groups of said virtual construct intervals within said query index have the same pattern of different sized virtual construct intervals,

wherein said groups of virtual construct intervals have uniform lengths, and

wherein said predicate intervals have non-uniform lengths.

9. The method in claim 8, further comprising maintaining locations of said predicate intervals within said groups of virtual construct intervals using a predicate ID bitmap vector.

10. The method in claim 8, wherein said process of defining said groups of virtual construct intervals comprises beginning all virtual construct intervals in a group of virtual construct intervals at a same data value and ending said virtual construct intervals in said group of virtual construct intervals at different data values.

11. The method in claim 8, wherein said process of inserting said predicate intervals into said virtual construct intervals, comprises inserting said predicate interval into the same sized virtual construct interval.

12. The method in claim 8, wherein when a predicate interval is larger than any of said virtual construct intervals, said inserting process comprises:

inserting an initial portion of said predicate interval into the largest available virtual construct interval, wherein a length in excess of a length of said initial portion of said predicate interval comprises a remnant predicate interval; and

inserting the remnant predicate interval into the same length virtual construct interval.

13. The method of claim 8, wherein said defining process only defines virtual construct intervals that are between the minimum and maximum possible data values of said predicate intervals.

45. The method of claim 8, wherein said predetermined range intervals of at least some of said virtual construct intervals between and within said groups of construct intervals overlap.

14. A method for maintaining and using a query index to support continual query monitoring, said method comprising:

defining groups of virtual construct intervals, wherein said virtual construct intervals represent predetermined ranges of data values and correspond to specific bit positions in bit map vectors;

determining predicate intervals, wherein said predicate intervals represent specified ranges of data values from continual queries; and

inserting each of said predicate intervals into said bit map positions of at least one of said groups of said virtual construct intervals such that said specified ranges of data values of said predicate intervals are aligned with said predetermined ranges of said data values of said virtual construct intervals,

wherein all of said groups of said virtual construct intervals within said query index have the same pattern of different sized of virtual construct intervals, and

wherein each of said groups of virtual construct intervals is adapted to hold multiple predicate intervals.

15. The method in claim 14, further comprising maintaining locations of said predicate intervals within said groups of virtual construct intervals using a predicate ID bitmap vector.

16. The method in claim 14, wherein said process of defining said groups of virtual construct intervals comprises beginning all virtual construct intervals in a group of virtual construct intervals at a same data value and ending said virtual construct intervals in said group of virtual construct intervals at different data values.

17. The method in claim 14, wherein said process of inserting said predicate intervals into said virtual construct intervals, comprises inserting said predicate interval into the same sized virtual construct interval.

18. The method in claim 14, wherein when a predicate interval is larger than any of said virtual construct intervals, said inserting process comprises:

inserting an initial portion of said predicate interval into the largest available virtual construct interval, wherein a length in excess of a length of said initial portion of said predicate interval comprises a remnant predicate interval; and

inserting the remnant predicate interval into the same length virtual construct interval.

19. The method in claim 14, wherein said groups of virtual construct intervals have uniform lengths, wherein said predicate intervals have non-uniform lengths and wherein said defining process only defines virtual construct intervals that are between the minimum and maximum possible data values of said predicate intervals.

46. The method of claim 14, wherein said predetermined range intervals of at least some of said virtual construct intervals between and within said groups of construct intervals overlap.

20. A method for maintaining and using a query index to support continual query monitoring, said method comprising:

defining groups of virtual construct intervals, wherein said virtual construct intervals represent predetermined ranges of data values and correspond to specific bit positions in bit map vectors;

determining predicate intervals, wherein said predicate intervals represent specified ranges of data values from continual queries; and

inserting each of said predicate intervals into said bit map positions of at least one of said groups of said virtual construct intervals such that said specified ranges of data values of said predicate intervals are aligned with said predetermined ranges of said data values of said virtual construct intervals,

wherein each of said groups of virtual construct intervals is adapted to hold multiple predicate intervals, and

wherein said defining process only defines virtual construct intervals that are between the minimum and maximum possible data values of said predicate intervals.

21. The method in claim 20, further comprising maintaining locations of said predicate intervals within said groups of virtual construct intervals using a predicate ID bitmap vector.

22. The method in claim 20, wherein said process of defining said groups of virtual construct intervals comprises beginning all virtual construct intervals in a group of virtual construct intervals at a same data value and ending said virtual construct intervals in said group of virtual construct intervals at different data values.

23. The method in claim 20, wherein said process of inserting said predicate intervals into said virtual construct intervals, comprises inserting said predicate interval into the same sized virtual construct interval.

24. The method in claim 20, wherein when a predicate interval is larger than any of said virtual construct intervals, said inserting process comprises:

inserting an initial portion of said predicate interval into the largest available virtual construct interval, wherein a length in excess of a length of said initial portion of said predicate interval comprises a remnant predicate interval; and

inserting the remnant predicate interval into the same length virtual construct interval.

25. The method in claim 20, wherein said groups of virtual construct intervals have uniform lengths, wherein said predicate intervals have non-uniform lengths and wherein all of said groups of said virtual construct intervals within said query index have the same pattern of different sized virtual construct intervals.

47. The method of claim 20, wherein said predetermined range intervals of at least some of said virtual construct intervals between and within said groups of construct intervals overlap.

26. A service adapted to maintains and use a query index to support continual query monitoring, said service:

defining groups of virtual construct intervals, wherein said virtual construct intervals represent predetermined ranges of data values and correspond to specific bit positions in bit map vectors;

determining predicate intervals, wherein said predicate intervals represent specified ranges of data values from continual queries; and

inserting each of said predicate intervals into said bit map positions of at least one of said groups of said virtual construct intervals such that said specified ranges of data values of said predicate intervals are aligned with said predetermined ranges of said data values of said virtual construct intervals.

27. The service in claim 26, further comprising maintaining locations of said predicate intervals within said groups of virtual construct intervals using a predicate ID bitmap vector.

28. The service in claim 26, wherein said process of defining said groups of virtual construct intervals comprises beginning all virtual construct intervals in a group of virtual construct intervals at the same attribute value and ending said virtual construct intervals in said group of virtual construct intervals at different attribute values.

29. The service in claim 26, wherein said process of inserting said predicate intervals into said virtual construct intervals, comprises inserting said predicate interval into the same sized virtual construct interval.

30. The service in claim 26, wherein if when a predicate interval is larger than any of said virtual construct intervals, said inserting process comprises:

inserting an initial portion of said predicate interval into the largest available virtual construct interval, wherein a length in excess of a length of said initial portion of said predicate interval comprises a remnant predicate interval; and

inserting the remnant predicate interval into the same length virtual construct interval.

31. The service in claim 26, wherein said groups of virtual construct intervals have uniform lengths, wherein said predicate intervals have non-uniform lengths and wherein said defining process only defines virtual construct intervals that are between the minimum and maximum possible data values of said predicate intervals.

48. The service of claim 26, wherein said predetermined range intervals of at least some of said virtual construct intervals between and within said groups of construct intervals overlap.

32. A system for maintaining and using a query index to support continual query monitoring, said system comprising:

a plurality of bitmap vectors which define groups of virtual construct intervals wherein said virtual construct intervals represent predetermined ranges of data values and correspond to specific bit positions in said bit map vectors;

a predicate insertion handler adapted to insert predicate intervals into said bit map positions of at least one of said groups of said virtual construct intervals wherein said predicate intervals represent specified ranges of data values from continual,

wherein said predicate intervals are inserted such that said specified ranges of data values of said predicate intervals are aligned with said predetermined ranges of said data values of said virtual construct intervals.

33. The system in claim 32, further comprising a predicate ID bitmap vector adapted to maintain locations of said predicate intervals within said groups of virtual construct intervals.

34. The system in claim 32, wherein all of said groups of said virtual construct intervals have the same pattern of different sized of virtual construct intervals.

35. The system in claim 32, wherein said predicate insertion handler inserts said predicate intervals into the same sized virtual construct intervals.

36. The system in claim 32, wherein when a predicate interval is larger than any of said virtual construct intervals, said predicate insertion handler:

inserts an initial portion of said predicate interval into the largest available virtual construct interval, wherein a length in excess of a length of said initial portion of said predicate interval comprises a remnant predicate interval; and

inserts the remnant predicate interval into the same length virtual construct interval.

37. The system in claim 32, wherein said groups of virtual construct intervals have uniform lengths, wherein said predicate intervals have non-uniform lengths and wherein said defining process only defines virtual construct intervals that are between the minimum and maximum possible data values of said predicate intervals.

49. The system of claim 32, wherein said predetermined range intervals of at least some of said virtual construct intervals between and within said groups of construct intervals overlap.

38. A program storage device readable by machine, tangibly embodying a program of instructions executable by the machine to perform a method for maintaining and using a query index to support continual query monitoring, said method comprising:

defining groups of virtual construct intervals, wherein said virtual construct intervals represent predetermined ranges of data values and correspond to specific bit positions in bit map vectors;

determining predicate intervals, wherein said predicate intervals represent specified ranges of data values from continual queries; and

inserting each of said predicate intervals into said bit map positions of at least one of said groups of said virtual construct intervals such that said ranges of data values of said predicate intervals are aligned with said predetermined ranges of said data values of said virtual construct intervals.

39. The program storage device in claim 38, wherein said method further comprises maintaining locations of said predicate intervals within said groups of virtual construct intervals using a predicate ID bitmap vector.

40. The program storage device in claim 38, wherein said process of defining said groups of virtual construct intervals comprises beginning all virtual construct intervals in a group of virtual construct intervals at a same data value and ending said virtual construct intervals in said group of virtual construct intervals at different data values.

41. The program storage device in claim 38, wherein all of said groups of said virtual construct intervals within said query index have the same pattern of different sized of virtual construct intervals.

42. The program storage device in claim 38, wherein when a predicate interval is larger than any of said virtual construct intervals, said inserting process comprises:

inserting an initial portion of said predicate interval into the largest available virtual construct interval, wherein a length in excess of a length of said initial portion of said predicate interval comprises a remnant predicate interval; and

inserting the remnant predicate interval into the same length virtual construct interval.

43. The program storage device in claim 38, wherein said inserting further comprises inserting said predicate intervals such that each of said virtual construct intervals holds multiple predicate intervals, wherein said groups of virtual construct intervals have uniform lengths, wherein said predicate intervals have non-uniform lengths and wherein all of said groups of said virtual construct intervals within said query index have the same pattern of different sized virtual construct intervals.

50. The program storage device of claim 38, wherein said predetermined range intervals of at least some of said virtual construct intervals between and within said groups of construct intervals overlap.