Big Data Computing

325Efficient Processing of Stream Data over Persistent Data

are joined against the disk-based master data tuples on p, and all matching

tuples are removed from the queue. We now have to determine the earliest

time that p could be loaded again by HYBRIDJOIN. For p to be loaded again,

a stream tuple must be at the front of the queue and has to match a master

data tuple on p. The rst stream tuple that can do so is the aforementioned

stream tuple with position i + h

s

, because all earlier stream tuples that match

data on p have been deleted from the queue. This proves the theorem.

Comparison with INLJ: Theorem 2: HYJ(s) = O(INLJ(s))

Proof

INLJ performs a constant number of disk accesses per stream tuple. For the

theorem, it sufces to prove that