# EGA: An Efficient GPU Accelerated Groupby Aggregation Algorithm
## 4 Materials and Methods
### Mp-Ega
#### 4.2.3 Using Greedy Merge to Handle Small Partitions  
When many partitions are generated, some may be very small, which is inefficient for GPU processing. Thus, it is necessary to merge small partitions into larger ones. We formalize the partition merging problem through the following mathematical framework: Let all partitions form a set, with the assumption that no partition's size exceeds \(k\) (due to the limitations imposed by GPU global memory capacity). We can merge two partitions if the sum of their sizes is less than \(k\). The challenge lies in merging partitions such that the total number of merged partitions is minimized. A naive approach that traverses all merging possibilities would result in unacceptable time complexity, necessitating the development of a more efficient solution. Our core idea is to merge the two smallest partitions. The algorithm terminates when the merge size of these two partitions exceeds \(k\). The detailed algorithm is as follows: we first construct a min-heap based on partition sizes. If the heap size is equal to 1 or the merge size of the two smallest partitions exceeds \(k\), we terminate the algorithm. Otherwise, we pop the two smallest partitions, merge them into a new partition, and continue merging the current smallest partition until the next merge would exceed \(k\). This process is repeated until the algorithm terminates. The pseudocode for our algorithm can be found in Algorithm 1. Next, we will demonstrate the efficiency of the algorithm through the following theorem. Theorem 4.2: _Suppose \(A=\{a_{1},a_{2},\ldots,a_{n}\}\), \(1\leq a_{i}\leq K\), \(a_{i}\in\mathbb{N}^{+}\), \(1\leq i\leq n\). Now, divide \(A\) into \(x\) disjoint subsets \(B_{1},B_{2},\ldots,B_{x}\) such that \(\forall j\in\{1,2,\ldots,x\},\sum_{b\in B_{j}}b\leq K\). We call this process a cut, and we define the degree of the cut as \(x\). A cut is optimal if its degree is the smallest among all cuts. Suppose that the optimal cut is \(\mathbb{B}\); then, we can find a cut \(\mathbb{C}\) whose degree is \(y\) and \(y<2x\) in \(O(n\log n)\) time complexity._  
Proof. : Since the total number of partitions is limited, we know that the optimal cut must exist. Suppose that the optimal cut is \(\mathbb{B}:B_{1},B_{2},\ldots,B_{x}\). In the initial situation, we can assume that set \(A\) is divided into \(n\) parts: \(C_{1},C_{2},\ldots,C_{n}\), where \(C_{i}=\{a_{i}\}\), \(1\leq i\leq n\). So the initial cut is \(C_{0}:C_{0,1},C_{0,2},\ldots,C_{0,n_{0}}\). Suppose \(C_{i,1},C_{i,2},\ldots,C_{i,n_{i}}\) are sorted by \(\text{Sum}(C_{i,j})\) in ascending order. Let \(\sum_{k=1}^{j}\text{Sum}(C_{i,k})\leq K\) and \(\sum_{k=1}^{j+1}\text{Sum}(C_{i,k})>K\). Then, we merge \(C_{i,1},\ldots,C_{i,j}\) into one set and obtain the new cut \(C_{i+1}\). Suppose that after \(t\) such iterations, we obtain the cut \(\mathbb{C}_{t}\), which satisfies \(\text{Sum}(C_{t,0})+\text{Sum}(C_{t,1})>K\). The degree of cut \(\mathbb{C}_{t}\) is \(y\). Let \(S=\sum_{k=1}^{y}\text{Sum}(C_{t,k})\). Then,  
\[2S=\sum_{k=1}^{y}\Big{(}\text{Sum}(C_{t,k})+\text{Sum}(C_{t,y+1-k})\Big{)}.\]  
Since \(\text{Sum}(C_{t,k})+\text{Sum}(C_{t,y+1-k})\geq\text{Sum}(C_{t,0})+\text{Sum} (C_{t,1})>K\), we have \(2S>yK\). Since \(S=\sum_{k=1}^{x}\text{Sum}(B_{k})\) and \(\text{Sum}(B_{k})\leq K\), we have \(2S\leq 2 Kx\). Combining \(2S>yK\) and \(2S\leq 2 Kx\), we obtain \(yK<2 Kx\), which implies \(y<2x\). So \(\mathbb{C}_{t}\) is the cut we found. Now, let us analyze the time complexity. In every iteration, we merge at least two sets, so the degree of the new cut decreases by at least \(1\). The initial degree is \(n\), so the number of iterations is \(O(n)\). In each iteration, we insert the merged set into an ordered set list, and the time complexity of this operation is \(O(\log n)\). Initially, we sort the initial cut, which has a time complexity of \(O(n\log n)\). Therefore, the overall time complexity is \(O(n\log n)\).