Achieving High Freshness and Optimal Throughput in CPU-Limited Execution of Multi-join Continuous Queries - Advances in Databases - page 51

Symbol Meaning
t I Tuple of stream I

t I .ts Timestamp of tuple t I

λ i Arrival rate of stream I

| S I | Window size of state I

σ i Selectivity of join on state S I

λ i Probe allowance of stream I, ( ≤λ i ).

Fig. 3. List of notation

r = 750 /sec
2

σ

σ

2 = 0.005
|S C |
= 1000

2 = 0.005
|S C |
= 1000

|S AB |
= 200

|S AB |
= 200

2

2

λ

c ' = 0

λ ab ' = 150

λ ab = r λ c=600

σ σ

1

λ c =600

A= 0.001 B= 0.005

|S B |
= 500

r = 750 /sec
1

σ 1 = 0.001

|S B |
= 500

|S A |
= 5000

σ 1 = 0.001

|S B |
= 500

|S A |
= 5000

|S A |
= 5000

1

1

λ λ

a = 500 b =700 λ a ' = 0 λ b ' = 150

λ λ a = 500 b =700

(a) Single Join (b) 2-Join Plan

λ λ a= 500 b =700

Fig. 4. Join plans with parameter settings Fig. 5. JDA over a 2-join plan

cost model proposed by Kang et al. [10] that computes the join cost in terms of the
three sub-tasks, namely, probe , insert and purge operations. For simplicity, the model
assumes count-based windows. The key idea is that the cost of probe dominates the
total join cost while insert and purge operations are relatively inexpensive .For
details on the model and its extension to time-based windows refer to [10]. Fig. 3 lists
the notation.

Throughput. The run-time throughput (Eq. 1) of a join operator A B (Fig. 4.a) con-

sists of two contributing half-way join components, namely, r =(a S B )andr =(b

S A ). Throughput is also called the output rate and is defined as the number of joined
tuples produced per time unit . For tuple t A ,S A is the own state whereas S B is the partner
state.

r = r + r = λ ×σ ×| S B |+λ ×σ ×| S A | (1)

a B b A

CPU Limitation in a Join. When CPU is limited, the throughput of A B can be re-

written as in Eq. 2. The total available computing resources , denoted as ,maybe

determined from the system. Terms available resources and service rate are used inter-
changeably.

μ

λ a ×σ B ×| S B |+λ b ×σ A ×| r = r + r = S A |,

λ a +λ b ≤μ.

(2)

In Eq. 2, the resources allocated to a join is divided between the two half-way joins.

Stream A is assigned a probe allowance , denoted by

μ

λ a , which is a portion

μ

a of

μ

λ a = min( λ b not exceeding the input rate

a ),
λ b ). As the probe cost dominates the total join cost, the resource restriction only affects

λ

a , i.e.,

μ

a ,

λ

a ). Similarly,

= min(( μ - μ