Interval query indexing techniques for use in accordance with data stream processing systems are disclosed. For example, in an illustrative aspect of the invention, a technique for use in processing a data stream comprises the following steps/operations. First, an attribute range of query intervals associated with the data stream is partitioned into one or more segments. Then, a set of virtual intervals is defined for each of the one or more segments. A query interval index is then built using the set of virtual intervals. The query interval index may be built by decomposing each query interval into one or more of the virtual intervals, and associating a query identifier with the decomposed virtual intervals.