# Revisiting the Design of Parallel Stream Joins on Trusted Execution Environments
## 2 Preliminaries and Background
### Stream joins  
The need to obtain joining results \"early\" (before having read an entire input stream) has been a long identified problem by the research community. We define a _tuple_\(x\) as triplet \(x=t,k,v\), where \(t,k\) and \(v\) are the timestamp, key, and payload of the tuple, respectively. We define the _input stream_ (denoted as \(R\) or \(S\)) as a list of tuples chronologically arriving at the system (e.g., a query processor).  
In this work, we focus on _intra-window join_. It is particularly important for emerging application demands that require maintaining large buffers of historical states [25; 26]. In the following, we simply denote it as _stream join_ for brevity.  
**Definition 1** (Stream join).: _Given input streams \(R\) and \(S\) and a window \(w\), the **stream join** joins a pair of subsets (i.e., \(R^{\prime}\), \(S^{\prime}\)) such that \(R^{\prime}\Join S^{\prime}=\{(r\cup s)|r.key=s.key,r.ts\in w,s.ts\in w,r\in R,s \in S\}\), where each result tuple \((r\cup s)\) has a timestamp, key, and value of \(\max(r.ts,s.ts)\), \(r.key\), and \(r.value\parallel s.value\), respectively._  
Earlier work on stream join [27; 28] historically focused on its single-thread execution efficiency focusing on taking care of out-of-memory issue [28; 29; 30; 31; 32] or providing higher statistical quality of intermediate aggregation results [33; 34]. To cope with the rapid growth of volume of data streams, much effort has been recently put into designing distributed and parallel stream join algorithms [26]. However, to the best of our knowledge, no one has  
\begin{table}
\begin{tabular}{c c} \hline \hline
**Notations** & **Description** \\ \hline \(x=\{t,k,v\}\) & An input tuple \(x\) with three attributes \\ \hline \(R\), \(S\) & Two input streams to join \\ \hline \(\mathit{skew}_{\mathit{key}}\) & Key skewness (unique or zipf) \\ \hline \(\mathit{skew}_{ts}\) & Timestamp skewness (uniform or zipf) \\ \hline \(\mathit{dupe}\) & Average number of duplicates per key \\ \hline \(v\) & Input arrival rate (tuples/ms) \\ \hline \(w\) & Window length (ms) \\ \hline \(N_{R}\) & Total Number of Tuples in Stream \(R\) \\ \hline \(N_{S}\) & Total Number of Tuples in Stream \(S\) \\ \hline \(|X|\) & Maximum Size of Tuple \(\{R;S\}\) or resulting Join \(\{J\}\) \\ \hline \(M_{X}\) & Number of Tuples in Join-Matrix Partition over Stream \(\{R;S\}\) \\ \hline \(\lambda_{X}\) & Tuple arrival rate for \(\{R;S\}\) \\ \hline \(\mathit{Mem}_{\mathit{Encl}}\) & The amount of effective enclave memory available \\ \hline \#Encl & The Number of Secure Enclaves Available \\ \hline \#Thr & The Number of CPU Threads Available \\ \hline \(\#EPC_{S}\) & The Number of Enclave Page Cache Swaps within a given Enclave \\ \hline \(L_{\mathit{ECall}}\) & The Access Latency of an Enclave Call (ECall) \\ \hline \(L_{\mathit{OCall}}\) & The Access Latency of an Outside Call (OCall) \\ \hline \(L_{\mathit{EPC}}\) & The Latency of an Enclave Page Cache Swap \\ \hline \(T_{\mathbf{x}}^{\mathit{Encl}}\) & The execution time of a join in a secure enclave \\ \hline \(C\) & Sum of Initialization and shutdown overheads for app using exact \\  & enclave memory size \\ \hline \(C_{\mathit{Init}}\) & Enclave Initialization overhead per extra EPC page \\ \hline \(C_{\mathit{Shut}}\) & Enclave Shutdown overhead per extra EPC page \\ \hline \hline \end{tabular}
\end{table}
Table 1: Notations used in this paper.  
attempted answering the question of how to design efficient parallel stream join algorithms with security guarantees.