Modeling and Optimization for Massive Data Allocation in Database Panpan Niu1 , Boxiang Ren2 , Hao Wu1 , Xin Yao2
arXiv:2605.31002v1 [cs.DB] 29 May 2026
1
Department of Mathematical Sciences, Tsinghua University 2 2012 Labs, Huawei Technologies Co., Ltd June 1, 2026
Abstract In the era of big data, e-commerce and Internet platforms face the challenge of processing massive amounts of data. However, due to data being scattered across different machines in distributed database, extra communication costs are incurred in gathering relevant data to complete transactions. Without a carefully designed data placement scheme, this cost can severely impact the performance of Online Transaction Processing systems. To meet industry requirements, algorithms that output a data placement scheme that achieves i) data balance and ii) low communication overhead within a fixed period of time are eagerly investigated. Although some existing methods have been studied, they do not adequately meet the aforementioned requirements. In this paper, inspired by the normalized cut of spectral clustering, we introduce a novel model for data allocation problem. The normalized cut reconciles the inherent conflict between the two objectives. Taking into account the variable characteristics of the model, we formulate the problem as a 0-1 optimization problem, and solve the relaxed problem using the Bregman proximal gradient method with guaranteed convergence. The numerical experiments reveal that the convergent solutions can be smoothly rounded to discrete solutions. Furthermore, our algorithm surpasses both simple and meta-heuristic partitioning schemes by minimizing migration costs while maintaining a superior balance.
1
Introduction
The database management system (DBMS) (Codd, 1970) has been applied in various fields, including e-commerce systems (Li, 2019; Ahmed et al., 2021), computerized library systems (Herrnansyah et al., 2016) and geographic information systems (GIS) (Schneider, 1997). As technology advances, enterprises face an exponential increase in data volume, often reaching billions of units. For example, Google, the largest search engine company, handles more than 85.5 billion new visits per month. Storing such vast amounts of data in memory using a single-node DBMS is no longer feasible. To address these challenges, a distributed database management system (DDBMS) (Özsu and Valduriez, 1999) has been proposed, leveraging multiple servers to manage large-scale data. Things become far more complicated when executing a transaction under the distributed setting. The DDBMS must coordinate these servers to aggregate the relevant data blocks into one node The first two authors contributed equally to this work. Corresponding author: Xin Yao ([email protected]).
1
before executing that transaction. However, if the data placement scheme is poorly designed, this process could cause serious data traffic and lead to a cliff-like drop in throughput (Pavlo et al., 2012; Shibata et al., 2010). Hence, the importance of developing an effective data partitioning strategy cannot be overstated. In the field of databases, formulating an effective data partitioning strategy is commonly known as the Data Allocation Problem (DAP). Numerous algorithms have been proposed to solve DAP, including workload-agnostic partitioning techniques (DeWitt and Gray, 1992), greedy or heuristic algorithms (Atrey et al., 2020; Taft et al., 2014; Pavlo et al., 2012; Serafini et al., 2016), graph-based methods (Curino et al., 2010; Quamar et al., 2013; Golab et al., 2014), deep learning reinforcement algorithms (Hilprecht et al., 2019, 2020), etc. Among these, graph-based methods, such as those using METIS (Karypis, 1997) or hMETIS (Karypis and Kumar, 1998), two publicly available graph partitioning libraries, have shown great potential. However, the full potential of these methods in terms of partition performance remains underexplored (Golab et al., 2014). Furthermore, these algorithms inherently rely on various forms of greedy or heuristic techniques that focus on local graph properties, and a rigorous analysis of these approaches is often lacking (Khandekar et al., 2009; Desale et al., 2015; Stanton and Kliot, 2012). Therefore, there remains significant interest in developing methods that yield high-quality partitioning solutions with guaranteed convergence to solve DAP. In recent years, researchers have formulated the DAP as a series of combinatorial optimization problems (Curino et al., 2010; Taft et al., 2014; Serafini et al., 2016; Quamar et al., 2013; Atrey et al., 2020; Golab et al., 2014; Yang et al., 2018; Firnkes, 2019). Notably, the Hypergraph Partitioning Problem and the Graph Partitioning Problem (GPP) are prominent representations of these approaches. In the case of the former (Quamar et al., 2013; Yang et al., 2018; Firnkes, 2019), which attempts to address a more general problem, historical workloads are modeled as a hypergraph, with each hyperedge corresponding to a transaction. However, hypergraph partitioning often results in worse performance compared to conventional graph partitioning (Golab et al., 2014). Therefore, this paper focuses on the GPP (Curino et al., 2010; Serafini et al., 2016). As noted in Pavlo et al. (2012); Curino et al. (2010), GPP aims to balance the workload across nodes while minimizing the number of transactions that require access to multiple servers. A key challenge in DAP is the inherent conflict between these two objectives (Serafini et al., 2016). Inspired by spectral clustering (Von Luxburg, 2007), we apply a graph-based Normalized Cut1 (NCut) to address the challenges posed by GPP. The NCut model resolves these conflicting objectives through a unified function. It has been proved by Shi and Malik (2000) that the problem of minimizing NCut is NPComplete. Several approximation algorithms (Van Den Heuvel et al., 2008; Ng et al., 2001; Shi and Malik, 2000; Yan et al., 2009; Dhillon et al., 2004) have been proposed. For instance, Shi and Malik (2000) and Ng et al. (2001) successively propose two classical spectral methods. However, spectral methods are impractical in scenarios involving extensive databases due to their computational complexity of O(N 3 ), with N the number of data points (Yan et al., 2009). A critical observation is the capacity of the Bregman Proximal Gradient (BPG) (Beck and Teboulle, 2009, 2003; Bauschke et al., 2003) method to address this challenge. Although BPG was initially proposed for convex optimization, it is also powerful when applied to constrained non-convex optimization problems with theoretical guarantees (Bolte et al., 2018). In this paper, we introduce a novel model for the DAP by formulating it as an NCut model, in1
Ratio Cut is also an available option. However, as demonstrated in (Nie et al., 2010), NCut often outperforms Ratio Cut and leads to more balanced clustering.
2
Server 1
Server 2
Server 3
Server 4
User Request
Network Local
Network
Network
The transmission overhead is 4. Data
Accessed data by the user request
Distributed Database
User
Figure 1: Data migration process in a distributed database. The process of data migration involves transferring data fragments between different nodes. The Data represents the actual data fragments stored in the leaf nodes of B+ trees (Elmasri and Navathe, 2016). They can be simply understood as blocks of data. spired by spectral clustering. The sum-of-fractions structure of the NCut model effectively captures two major concerns of DAP: the numerators aim to reduce migration costs, while the denominators promote load balancing. To tackle the combinatorial nature of NCut, we reformulate it as an integer programming problem and further relax it into a continuous optimization problem. To address the resulting non-convexity of the relaxed problem, we employ the BPG method and provide a convergence analysis, ensuring that the algorithm reliably converges to high-quality solutions. Numerical experiments reveal that the convergent solutions obtained by BPG can be effectively rounded to discrete solutions, demonstrating the practical feasibility of our approach. Compared to simple and meta-heuristic partitioning schemes, our algorithm achieves superior performance by minimizing migration costs while maintaining better load balance. These results highlight the potential of our method to enhance data allocation strategies in distributed database systems, where high-quality solutions are crucial for improving system throughput. This paper is organized as follows. Section 2 develops an NCut model for DAP. In Section 3, we use BPG method to solve the relaxed problem and provide proofs of convergence. The numerical experiments in Section 4 demonstrate the advantages of our approach. Finally, Section 5 concludes the paper.
2
DAP Modeling
We first outline the main components of distributed database systems. Figure 1 illustrates the processing flow of a transaction. The process begins when a user submits a transaction request, which can involve operations such as an update or a select query. The DDBMS selects a server to execute the procedural control code and the relevant queries (Pavlo et al., 2011, 2012). In practice, the selected server is typically the one that already stores the largest portion of the data required by the transaction. Unlike local transactions, distributed transactions involve data that is spread across multiple servers. In such cases, data residing on other servers must be migrated to the chosen server via network communication. For example, as shown in Figure 1, server 2 contains the majority of the relevant data, while the other servers transmit the remaining data blocks to it. Notably, the migration time involved in this process accounts for a large portion of the overall transaction processing time (Pavlo et al., 2012). The migration time primarily depends on the
3
number of transferred data. Specifically, migration time is typically orders of magnitude larger than the partitioning time. Therefore, we strategically allocate more time to the partitioning process to achieve a better partitioning result. This approach effectively reduces the overall migration overhead, thereby optimizing the system’s overall performance. The main objective of the DAP in Online Transaction Processing (OLTP) systems is to minimize the number of distributed transactions while ensuring a balanced workload across all nodes. Interestingly, despite being formulated differently, the DAP shares significant similarities in optimization objectives and constraints with the Graph Partitioning Problem, as demonstrated by previous studies (Golab et al., 2014; Curino et al., 2010). Leveraging these similarities, we transform the DAP into a well-established GPP framework. In the proposed model, the data blocks in the leaf nodes of B+ trees are treated as vertices. Let these vertices be represented as a set, denoted by V = {v1 , v2 , ..., vN }. Co-accesses between two vertices are modeled as edges, with the weight defined by the number of transactions that simultaneously access both vertices. This results in a graph G = (V, E), where E represents the set of edges. Minimizing the number of distributed transactions and maintaining a balanced workload across nodes are closely related to finding a balanced partitioning of the graph G (Curino et al., 2010). Specifically, given K subsets, a feasible partitioning scheme divides V into P1 , P2 , ..., PK , such that Pi ∩ Pj = ∅ for i ̸= j, and ∪m Pm = V . Let X = (xij )N ×K = (x1 , x2 , ..., xK ) (
where xij =
1, if vi ∈ Pj , 0, otherwise.
Since each data is uniquely assigned to a site, it satisfies the following no-replication constraint: K X
x i = 1N ,
i=1
where 1N denotes the all-one vector in RN . Addressing the challenge of determining a suitable level of load imbalance constraint in GPP becomes challenging, as noted by Serafini et al. (2016). Here, we propose an NCut model that effectively tackles this challenge. First, we represent the two objectives of DAP in terms of equations involving X. To quantify the workload of a component Pi ⊆ V , we define vol(P ) as follows: X X vol(Pi ) := dj = wst xsi = xTi W 1N (1) vj ∈Pi
vs ∈Pi ,vt ∈V
P where, di = nj=1 wij represents the weighted degree of a node vi ∈ V , and W ∈ RN ×N is the adjacency matrix of G. The di indicates the potential number of migrations for vi across all transactions. Thus, vol(Pi ), utilized later for balancing, denotes the communication load undertaken by server i. Next, we define cut of Pi as X X X cut(Pi ) := wij = wst − wst = xTi W (1N − xi ). (2) vi ∈Pi ,vj ̸∈Pi
vs ∈Pi ,vt ∈V
vs ∈Pi ,vt ∈Pi
The cut(Pi ) measures the total weight of edges connecting Pi with other partitions. From the 1 PK perspective of DAP, the 2 i=1 cut(Pi ) provides an approximation to the communication overhead induced by distributed transactions. Assuming each vertex has the same size and inspired 4
by Spectral Clustering (Von Luxburg, 2007), the objective and balanced constraint of GPP are approximately equivalent to minimizing the NCut: NCut(P1 , .., PK ) =
1 X cut(Pi ) 1 X xTi W (1N − xi ) . = 2 vol(Pi ) 2 xTi W 1N
PK
K
K
i=1
i=1
1 achieves its minimum when all vol(Pi ) are equal. Thus, On one hand, the function i=1 vol(P i) NCut assesses the load balancing of Pi within a scheme {P1 , P2 , ..., Pk } using (1). On the other hand, NCut leverages (2) to evaluate the communication overhead among partitions. By combining these two components, the NCut model can serve as a unified evaluation criterion that simultaneously optimizes both objectives in DAP. This is empirically validated in Section 4 through numerical experiments. For further elaboration, please refer to Shi and Malik (2000); Von Luxburg (2007). In summary, the DAP is rewritten as the following optimization problem:
P1 :
K X xT W (1N − xi ) i
min X
xTi W 1N
i=1
xi ∈ {0, 1}N ,
s.t.
K X
∀i ∈ {1, 2, ..., K}
xi = 1N .
(3a) (3b) (3c)
i=1
This problem is NP-hard (Andreev and Räcke, 2004), which implies that computing exact solutions becomes computationally intractable for large-scale instances. Therefore, we focus on developing an efficient approximation algorithm that can provide near-optimal solutions within a reasonable computation time in the next section.
3
The Algorithm and Convergence Analysis
In this section, we present our approach for solving the relaxed problem, along with its theoretical convergence guarantees. Specifically, we develop a BPG-based approach for the relaxed problem of NCut problems and provide its convergence properties.
3.1
The Bregman Proximal Gradient algorithm for NCut
The problem P1 is an integer programming problem, which is difficult to tackle. To resolve it, taking into account (3c), we relax (3b) and obtain a continuous problem P2 . P2 :
min X
s.t.
K X xT W (1N − xi ) i
xTi W 1N
i=1
xi ≥ 0, K X
∀i ∈ {1, 2, ..., K}
x i = 1N .
(4a) (4b) (4c)
i=1
Relaxations from integer programming problems to continuous problems often lead to challenges in the rounding process, i.e., transforming continuous solutions into discrete ones. Rounding techniques have been widely used and proven effective in many optimization scenarios, as demonstrated 5
in Karger et al. (1999); Buchbinder et al. (2017). Our numerical experiments further validate that our approach for the continuous problem yields solutions close to a 0-1 solution in practice, thereby facilitating the rounding process and ensuring practical applicability. We now proceed to solve the relaxed problem P2 . This is a non-convex optimization problem with linear constraints. Proximal gradient (PG) methods are well-suited for this class of problems, particularly those with row/column sum constraints, where explicit solutions are often attainable. By choosing Bregman divergence in the regularization term of PG, the non-negativity constraints are naturally absorbed into the objective function, resulting in a concise update rule. Moreover, existing theoretical analyses on the application of Bregman Proximal Gradient to non-convex and nonsmooth optimization can be leveraged to establish convergence guarantees for our problem. For optimization problems P2 , we denote ) ( K X xi = 1N , C = X = {x1 , x2 , .., xK } ∈ RN ×K xij ≥ 0, i=1
which is a product of probability simplexes, and f (X) =
K X xT W (1N − xi ) i
xTi W 1N
i=1
.
Considering the simplex constraints, we use the Bregman distance Dh (x, y) := h(x) P − h(y) − ⟨∇h(y), x − y⟩ (Bregman, 1967; Bauschke et al., 1997) with entropy function h(x) = i,j xij ln xij , which leads to a simpler iteration formula compared to Euclidean norm. Employing the BPG iteration scheme, we obtain the following iteration formula: X X ∂f xij t+1 t t X = argminX∈C λt (5) (X ), xi + xij ln t − (xij − xij ) , ∂xi xij i
where
i,j
∂f xT W 1N (W 1N − 2W xi ) − xTi W (1N − xi )W 1N (X) = i . ∂xi (xTi W 1N )2
By utilizing the first-order optimality condition, the iterative formula can be written as follows: ∂f
X t+1 = PC (X t ◦ e−λt ∂X (X ) ), t
(6)
where ◦ denotes Hadamard product, and PC (·) represents the Bregman projection of C. Since C represents a product of probability simplexes, we can obtain PC (X) by dividing each row of X by the sum of the row. Algorithm 1 shows the pseudo-code of our algorithm. Here we use superscript t to denote the t-th iteration of a variable and utilize fixed step size λt = λ in (5) 2 . A constant ϵ is added to the denominator of NCut objective function in both numerical experiments and theoretical analysis for numerical stability. Next, we analyze the computational complexity of Algorithm 1. The adjacency matrix W is represented by a compressed format, such as CSR (Compressed Sparse Row). It takes O(KM ) 2 The step size is a hyperparameter that requires careful tuning. A large value can cause divergence, while a minimal one may result in slow convergence (Zeiler, 2012). Fortunately, the algorithm demonstrates stability over a wide range of step sizes. More details are provided in Section 4.
6
Algorithm 1 Bregman Proximal Gradient algorithm for NCut Require: Adjacency matrix of G W ∈ RN ×N , number of partitions K, step size λ, and the number of iterations T Ensure: Data partition y ∈ {1, · · · , K}N 1 1: X (0) ← K ∗ J + 0.1 ∗ R, where J ∈ RN ×K and R ∈ RN ×K are all-one matrix and uniform random matrix in [0, 1] 2: Normalize X (0) such that the sum of each row is 1 3: for t = 0 to T − 1 do 4: for i = 1 to K do (t) (t) (t) (t) (x )T W 1N (W 1N −2W xi )−(xi )T W (1N −xi )W 1N (t) 5: gi ← i (t) T 2 6: 7:
((xi ) W 1N ) (t) (t) (t) (t) G ← (g1 , g2 , . . . , gK ) Y (t+1) ← X (t) ◦ exp −λG(t)
Normalize Y (t+1) row-wise to obtain X (t+1) 9: for i = 1 to N do (T ) 10: yi ← argmax1≤j≤K xij ; 8:
time to compute the expressions in line 5 because of matrix-vector multiplication, where M is the number of non-zero elements in the sparse matrix. And it takes O(KN ) time from line 7 to line 8. Notably, compared with the traditional Euclidean distance based Bregman iteration, our entropy distance approach eliminates the need for sorting operations and reduces the computational cost of the projection operator to O(N K). Consequently, the overall computational complexity of the algorithm is O(T KM ).
3.2
Convergence Analysis
For the convenience of the proof, we first introduce the definition of L-smad here. More details of L-smad can be found in Bolte et al. (2018). Definition 3.1. (Bolte et al., 2018) A pair of functions (g, h) is L-smad if there exists L ∈ R++ such that Lh − g is convex on C. To employ the convergence analysis framework of BPG designed for non-convex and nonsmooth optimization problems, we need to establish the L-smad property of our relaxed problem, as stated in the following lemma. P P xT i W (1N −xi ) Lemma 3.2. Entropy function h(X) = i,j xij ln xij and g(X) = K i=1 xT W 1N +ϵ satisfy Li smad in C. Proof. The aim is to prove that there exists L ∈ R++ such that Lh−g is convex on C. By definition, we have K N T W (1 − x ) X X x i N L Lh(X) − g(X) = . xij ln xij − i T x W 1 + ϵ N i i=1 j=1 Since X can be separated by columns, it suffices ϕ(X) = L
N X
xij ln xij −
j=1
7
xTi W (1N − xi ) xTi W 1N + ϵ
is a convex function on C1 = {x ∈ Rn |0 ≤ x ≤ 1N }. For h1 (X) = L
PN
i=1 xi ln xi , we have
L ∂ 2 h1 (X) = xi ∂x2i ∂ 2 h1 (X) = 0. ∂xi ∂xj Thus, the Hessian matrix of h1 is diagonal on C1 with diagonal elements not less than L. xT W (1 −x ) For g1 (X) = ixT W 1N +ϵi , we have i
N
∂ 2 g1 ui (X) (X) = T , 2 ∂xi (xi W 1N + ϵ)4 vij (X) ∂ 2 g1 (X) = T . ∂xi ∂xj (xi W 1N + ϵ)4 Given that u and v are continuous functions and bounded on the compact set C1 , there exists a constant M > 0 such that |ui (X)| ≤ M and |vij (X)| ≤ M for all i, j ∈ {1, 2, ..., n}. Since xi is a nonnegative vector, it follows that (xTi W 1N + ϵ)4 ≥ ϵ4 . Therefore, each element of the Hessian of g1 is bounded above by M . Finally, we set ϵ4 L=
NM + 1, ϵ4
then the Hessian matrix of ϕ(X) = h1 (X) − g1 (X) is a symmetric strictly diagonally dominant matrix. Thus, ϕ(X) is a convex function on C1 . The proof of Lemma 3.2 is completed. We have shown the L-smad property of (g, h) in our model. Next, we present our main convergence result. Theorem 3.3. Let {X t } be the iterative sequence generated by BPG, and 0 < λL < 1. Then the following conclusions hold (1) λg(X t+1 ) ≤ λg(X t ) − (1 − λL)Dh (X t+1 , X t ), the sequence {g(X t )}t∈N is non-increasing; P∞ t+1 , X t ) < ∞, and D (X t+1 , X t ) → 0 as t → ∞; (2) h t=1 Dh (X λ g(X 0 )−g∗ t t−1 (3) min1≤t≤T Dh X , X ≤T , where g∗ = inf X∈C g(X) > −∞. 1−λL Theorem 3.3 extends the proof methodology of Bolte et al. (2018) to our setting. It guarantees the non-increasing property of the objective function and provides convergence properties of the iteration sequence in terms of Bregman distance. Furthermore, these results can be extended to the Euclidean distance through the application of Pinsker’s inequality. Remark 1. In this study, we have successfully demonstrated the convergence of our proposed iterative method. However, we have not provided a proof of convergence to the global optimum. This is primarily due to the fact that this problem is inherently NP-hard.
8
4
Numerical Experiments
This section evaluates the effectiveness of the proposed Bregman Proximal Gradient algorithm through numerical simulations. Instead of relying on a specific distributed database system, we construct synthetic workloads that simulate real OLTP transactions. This setting allows us to focus on the algorithmic performance without interference from system-level factors such as I/O latency or network scheduling. Each simulated workload is represented as an undirected weighted graph G = (V, E), where each vertex corresponds to a data block and each edge weight indicates the number of transactions that jointly access two blocks. To generate G, we assume N distinct data blocks and synthesize N transactions. The transaction size follows a distribution |Ti | ∼ ⌊ln(N ) + U (0, log10 N )⌉, where U (a, b) represents a uniform distribution over the interval [a, b]. Two data blocks are connected if they co-occur in the same transaction, and the edge weight wij equals the number of such cooccurrences. This procedure generates structured graphs that reflect the logical access patterns of OLTP transactions. The characteristics of all generated graphs are summarized in Table 1. No. of Vertices 10,000 20,000 40,000 80,000 160,000
No. of Edges 605,738 1,216,335 2,892,674 6,794,955 14,725,786
Mean Weighted Degree 121.8894 122.0058 144.8925 170.0513 184.1762
Table 1: Characteristics of the Synthetic Graphs. To mitigate the impact of randomness, all results are averaged over 10 experiments. In cases where the computational time exceeds 3600s, it is marked as "-". The BPG algorithm is implemented in Python 3.7, using the CuPy library to accelerate sparse matrix-vector multiplication on GPUs. In this work, we compare BPG with the following baselines, including two heuristic algorithms and a clustering method. • Round-robin (RR) (DeWitt and Gray, 1992) partitions data based on their data ID. Together with hash partitioning and range partitioning, they are simple algorithms widely adopted in the industry. Due to their similar performance, we only choose round-robin partitioning for comparison. • Spectral Clustering (SC) (Von Luxburg, 2007) is a powerful clustering technique that leverages the eigenstructure of a similarity matrix to partition data into groups. • METIS (Karypis, 1997) is the best-known software package in graph partition, widely used in the industry. Despite the availability of parallel versions such as ParMETIS (Karypis et al., 1997) and multi-threaded versions like mt-METIS (LaSalle and Karypis, 2013), we opted to use METIS as the comparative algorithm due to its superior partitioning performance.
4.1
Algorithm Verification
We first investigate the convergence behavior of BPG algorithm. Figure 2 illustrates the NCut convergence trajectories with respect to the number of iterations under different problem scales and
9
N=20000, K=32
31.0
N=40000, K=32
31.0
30.5
30.5
30.0
NC t
NC t
30.0
29.5
29.5
29.0
29.0
28.5 28.0
28.5 0
200
63
400 600 800 Iteration steps N=20000, K=64
1000
0
200
400 600 800 1000 0 Iteration steps BPG (λ = 3000) BPG (λ = 10000)
200
63
62
400 600 800 Iteration steps N=40000, K=64
1000
62
61
NC t
NC t
61
60
60
59 59
58 57
58 0
BPG (λ = 1000)
200
400 600 800 1000 Iteration steps BPG (λ = 30000) BPG (λ = 100000)
Figure 2: Convergence trajectories of NCut for the BPG algorithm with respect to the iteration steps under various step sizes (λ). step sizes. Four synthetic DAPs (N, k) are considered: (20000, 32), (20000, 64), (40000, 32), (40000, 64) with the step sizes λ set to 1000, 3000, 10000, 30000, and 100000. As observed, all trajectories exhibit a monotonic decrease as iterations progress, and the empirical results strongly corroborate the theoretical convergence guarantee established in Theorem 3.3. From the figure, it shows that the BPG algorithm demonstrates remarkable stability across a wide range of step sizes, mitigating the risk of divergence or slow convergence discussed in Footnote 2. Consequently, we select λ = 10000 as the default step size for all subsequent experiments. To further understand the effectiveness of the continuous relaxation, we analyze the properties of the converged solution matrix X. Discrete problem P1 is transformed into a continuous problem P2 as outlined in Section 3. Here, we conduct experiments on the properties of the converged solution X from the continuous problem P2 to demonstrate the effectiveness of the relaxation. Table 2 summarizes the value distribution for 12 synthetic DAPs. The results indicate that the vast majority of elements are close to either 0 or 1, with intermediate values (0.01−0.99) constituting less than 0.16%. This demonstrates that the relaxation preserves near-discrete structure, ensuring that the X can be smoothly rounded to the final partition. Furthermore, the number of elements 10
K
N 1 × 104 2 × 104 4 × 104 8 × 104 2 × 104 4 × 104 8 × 104 1.6 × 105
32
64
<0.01 3.10 × 105 6.20 × 105 1.24 × 106 2.48 × 106 1.26 × 106 2.52 × 106 5.04 × 106 1.01 × 107
Count >0.99 9.98 × 103 1.99 × 104 3.96 × 104 7.80 × 104 1.99 × 104 3.97 × 104 7.86 × 104 1.53 × 105
others 4.40 × 101 1.61 × 102 8.01 × 102 4.09 × 103 1.25 × 102 5.94 × 102 2.84 × 103 1.46 × 104
Percentage <0.01 >0.99 others 96.87% 3.12% 0.01% 96.86% 3.11% 0.03% 96.84% 3.09% 0.06% 96.79% 3.05% 0.16% 98.43% 1.56% 0.01% 98.43% 1.55% 0.02% 98.41% 1.54% 0.06% 98.36% 1.49% 0.14%
Table 2: Distribution of element values in the converged solution matrix X. Within this table, columns 3-4 indicate the number of elements in X that are less than 0.01 and greater than 0.99, respectively. Column 5 represents the count of remaining elements. Columns 6-8 display the corresponding percentages for the preceding three columns. exceeding 0.99 closely matches N , confirming that X effectively gives partition assignments for all vertices.
4.2
Algorithm Comparison (a) K = 32
(b) K = 64
30.5
62
30.0
61
NCut
63
NCut
31.0
29.5
60
29.0
59
28.5
58 10000 20000
40000
N ours
80000
20000 40000
80000
SC
METIS
RR
N
160000
Figure 3: A comparison of BPG, SC, METIS and RR with data size N. Left: K = 32. Right: K = 64. The SC line is incomplete due to timeout issues. After verifying convergence, we compare BPG against three baseline methods: SC, METIS, and RR. SC is executed using default parameters. For METIS, the ufactor parameter is set to 200 and 500 for K = 32 and K = 64, respectively. It’s noteworthy that SC can be regarded as an alternative discrete approach for minimizing NCut. Due to the insights gained from the previous subsection, we set the number of iterations T = 500 for BPG to achieve a balance between solution quality and computational efficiency. Figure 3 and Table 3 demonstrate that BPG consistently outperforms RR and SC in partition 11
K
N 1 × 104
32
64
2 × 104
4 × 104 8 × 104 2 × 104 4 × 104 8 × 104 1.6 × 105
ours 28.31 28.30 28.58 28.81 57.77 58.33 58.83 59.07
NCut SC METIS 29.07 28.53 29.14 28.58 28.87 29.13 59.75 58.84 59.48 59.85 60.07
RR 31.00 31.00 31.00 31.00 63.00 63.00 63.00 63.00
Rate 0.78% 0.97% 1.02% 1.09% 1.86% 1.96% 1.72% 1.69%
ours 4.60 5.08 5.15 9.42 8.66 8.71 17.90 63.34
Time (s) SC METIS 271.53 0.64 1739.89 1.09 2.08 4.73 1802.72 1.52 2.87 6.17 14.10
RR 0.0009 0.0019 0.0037 0.0072 0.0019 0.0036 0.0073 0.0154
Table 3: A comparison among the four algorithms for different synthetic DAPs (N, k). Columns 3-6 report the averaged NCut, Column 7 shows BPGs NCut reduction rate relative to METIS, and Columns 811 list average runtimes. quality, achieving lower NCut values across all datasets. Compared with METIS, BPG attains slightly better partition quality, reducing NCut by approximately 1.4% on average. In terms of runtime, METIS remains the fastest method, benefiting from a highly optimized multilevel heuristic framework. Although BPG currently incurs higher computational cost than METIS, it operates substantially faster than the SC approach while maintaining a clear quality advantage. In practical database partitioning scenarios, such as initial sharding or periodic re-partitioning, this additional runtime is often acceptable, as improved partition quality directly translates into reduced communication overhead and better long-term system efficiency. Furthermore, since the present BPG implementation has not yet been fully optimized, significant potential remains to narrow the runtime gap in future work.
4.3
Performance Evaluation in DAP
According to Pavlo et al. (2012), it is stated that the number of data migration and the workload skew are two critical performance indicators in distributed databases. In order to provide an intuitive representation of the DAP, we adopt the Migration Cost (MCost) and the Mean Absolute Deviation (MAD) of the scheme as the evaluation metrics in this subsection. Consider a usersubmitted task comprising L transactions T = {T1 , T2 , . . . , TL }, where Ti ⊂ V for i = 1, 2, . . . , L. Given a partitioning scheme P = {P1 , P2 , . . . , PK }, we define: M Cost(P, T ) =
L X
|Ti | −
i=1
P
M AD(P ) =
N i |Pi | − K
K
max (|Ti ∩ Pj |) ,
j=1,2,...,K
(7)
.
Here, M Cost(P, T ) measures the data migration overhead required to execute task T under partition P , while M AD(P ) quantifies workload imbalance across partitions. The averaged MCost and MAD of the four algorithms on different data sizes with K = 32, and 64 are summarized in Table 4. A clear positive correlation emerges between the NCut values in Table 3 and the MCost and MAD results reported here. Lower NCut values generally correspond to reduced migration cost and improved load balance, indicating that NCut serves as a comprehensive 12
K
N 1 × 104
2 × 104 4 × 104 8 × 104 2 × 104 4 × 104 64 8 × 104 1.6 × 105 32
ours 8.17 × 104 1.64 × 105 3.63 × 105 7.98 × 105 1.70 × 105 3.77 × 105 8.31 × 105 1.74 × 106
MCost(P, T ) SC METIS 4 8.43 × 10 8.20 × 104 1.69 × 105 1.64 × 105 3.65 × 105 8.05 × 105 1.76 × 105 1.71 × 105 3.80 × 105 8.36 × 105 1.75 × 106
RR 9.47 × 104 1.89 × 105 4.15 × 105 9.03 × 105 1.97 × 105 4.30 × 105 9.34 × 105 1.94 × 106
ours 51.76 76.26 103.51 141.18 116.75 204.55 323.85 499.38
MAD(P ) SC METIS 25.18 55.72 36.76 111.50 221.85 442.68 43.45 124.05 248.15 495.11 990.25
RR 0.50 0.00 0.00 0.00 0.50 0.00 0.00 0.00
Table 4: Comparison of the four algorithms under different numbers of data (N). Columns 3-10 report the averaged MCost and MAD for each method. indicator of partition quality, consistent with the formulation presented in Section 2. As shown in Table 4, BPG achieves consistently lower MCost than SC, METIS, and RR, with a reduction rate ranging from approximately 0.34% to 0.99% compared with the state-of-the-art METIS algorithm. Furthermore, BPG outperforms METIS in terms of MAD across most settings, indicating better workload balance. While SC and RR may achieve lower MAD values than BPG, SC suffers from high computational cost and RR yields substantially higher migration cost. Therefore, they are less competitive in the overall trade-off.
5
Conclusion
In this work, we investigated the data allocation problem within the context of database management systems. Our contributions are as follows. Firstly, we propose a novel model for tackling DAP. Second, taking into account the variable characteristics inherent in the model, we formulate the problem as a 0-1 optimization problem, and solve the relaxed problem using the BPG method with guaranteed convergence. Through comprehensive experiments, we show that our proposed BPG algorithm consistently outperforms existing methods in reducing data migration costs while maintaining superior workload balance.
References Falah YH Ahmed, Reshma Sreejith, and Muhammad Irsyad Abdullah. Enhancement of e-commerce database system during the COVID-19 pandemic. In 2021 IEEE 11th IEEE Symposium on Computer Applications & Industrial Electronics (ISCAIE), pages 174–179, Penang, Malaysia, Mar. 2021. IEEE. Konstantin Andreev and Harald Räcke. Balanced graph partitioning. In Proceedings of the Sixteenth Annual ACM Symposium on Parallelism in Algorithms and Architectures, pages 120–124, Barcelona, Spain, 2004. ACM. Ankita Atrey, Gregory Van Seghbroeck, Higinio Mora, Bruno Volckaert, and Filip De Turck. UnifyDR: A generic framework for unifying data and replica placement. IEEE Access, 8:216894– 216910, 2020. 13
Heinz H Bauschke, Jonathan M Borwein, et al. Legendre functions and the method of random bregman projections. Journal of Convex Analysis, 4(1):27–67, 1997. Heinz H Bauschke, Jonathan M Borwein, and Patrick L Combettes. Bregman monotone optimization algorithms. SIAM Journal on Control and Optimization, 42(2):596–636, 2003. Amir Beck and Marc Teboulle. Mirror descent and nonlinear projected subgradient methods for convex optimization. Operations Research Letters, 31(3):167–175, 2003. Amir Beck and Marc Teboulle. A fast iterative shrinkage-thresholding algorithm for linear inverse problems. SIAM Journal on Imaging Sciences, 2(1):183–202, 2009. Jérôme Bolte, Shoham Sabach, Marc Teboulle, and Yakov Vaisbourd. First order methods beyond convexity and lipschitz gradient continuity with applications to quadratic inverse problems. SIAM Journal on Optimization, 28(3):2131–2151, 2018. Lev M Bregman. The relaxation method of finding the common point of convex sets and its application to the solution of problems in convex programming. USSR Computational Mathematics and Mathematical Physics, 7(3):200–217, 1967. Niv Buchbinder, Roy Schwartz, and Baruch Weizman. Simplex transformations and the multiway cut problem. In Proceedings of the 2017 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 2400–2410. SIAM, 2017. E. F. Codd. A relational model of data for large shared data banks. Communications of the ACM, 13(6):377–387, Jan. 1970. Carlo Curino, Evan Philip Charles Jones, Yang Zhang, and Samuel R Madden. Schism: A workloaddriven approach to database replication and partitioning. Proceedings of the VLDB Endowment, 3(1–2):48–57, 2010. Sachin Desale, Akhtar Rasool, Sushil Andhale, and Priti Rane. Heuristic and meta-heuristic algorithms and their relevance to the real world: a survey. International Journal of Computer Engineering in Research Trends, 2(5):296–304, 2015. David DeWitt and Jim Gray. Parallel database systems: The future of high performance database systems. Communications of the ACM, 35(6):85–98, 1992. Inderjit S Dhillon, Yuqiang Guan, and Brian Kulis. Kernel k-means: spectral clustering and normalized cuts. In Proceedings of the tenth ACM SIGKDD international conference on Knowledge discovery and data mining, pages 551–556, Seattle, WA, USA, 2004. ACM. Ramez Elmasri and Shamkant B. Navathe. Fundamentals of database systems. Pearson Education, Boston, MA, USA, 7th edition, 2016. Patrick Firnkes. Throughput optimization in a distributed database system via hypergraph partitioning. Master’s thesis, Karlsruhe Institute of Technology, 2019. Lukasz Golab, Marios Hadjieleftheriou, Howard Karloff, and Barna Saha. Distributed data placement to minimize communication costs via graph partitioning. In Proceedings of the 26th International Conference on Scientific and Statistical Database Management, pages 1–12, Aalborg, Denmark, 2014. ACM. 14
Herrnansyah, Yova Ruldeviyani, and Rizal Fathoni Aji. Enhancing query performance of library information systems using NoSQL DBMS: Case study on library information systems of Universitas Indonesia. In 2016 International Workshop on Big Data and Information Security (IWBIS), pages 41–46, Jakarta, Indonesia, 2016. IEEE. Benjamin Hilprecht, Carsten Binnig, and Uwe Roehm. Learning a partitioning advisor with deep reinforcement learning, 2019. URL https://arxiv.org/abs/1904.01279. Benjamin Hilprecht, Carsten Binnig, and Uwe Röhm. Learning a partitioning advisor for cloud databases. In Proceedings of the 2020 ACM SIGMOD International Conference on Management of Data, pages 143–157, Virtual Conference, 2020. ACM. David R Karger, Philip Klein, Cliff Stein, Mikkel Thorup, and Neal E Young. Rounding algorithms for a geometric embedding of minimum multiway cut. In Proceedings of the Thirty-First Annual ACM Symposium on Theory of Computing, pages 668–678, Atlanta, GA, USA, 1999. ACM. George Karypis. Metis: Unstructured graph partitioning and sparse matrix ordering system. Technical report, Department of Computer Science, University of Minnesota, 1997. George Karypis and Vipin Kumar. A hypergraph partitioning package. Technical report, Army HPC Research Center, Department of Computer Science and Engineering, University of Minnesota, 1998. George Karypis, Kirk Schloegel, and Vipin Kumar. PARMETIS: Parallel graph partitioning and sparse matrix ordering library. Technical Report TR 97-060, Department of Computer Science and Engineering, University of Minnesota, Minneapolis, MN, USA, 1997. Rohit Khandekar, Satish Rao, and Umesh Vazirani. Graph partitioning using single commodity flows. Journal of the ACM (JACM), 56(4):1–15, 2009. Dominique LaSalle and George Karypis. Multi-threaded graph partitioning. In 2013 IEEE 27th International Symposium on Parallel and Distributed Processing, pages 225–236, Boston, MA, USA, 2013. IEEE. Feifei Li. Cloud-native database systems at Alibaba: Opportunities and challenges. Proceedings of the VLDB Endowment, 12(12):2263–2272, Aug. 2019. Andrew Ng, Michael Jordan, and Yair Weiss. On spectral clustering: Analysis and an algorithm. Advances in Neural Information Processing Systems, 14, 2001. Feiping Nie, Chris Ding, Dijun Luo, and Heng Huang. Improved minmax cut graph clustering with nonnegative relaxation. In Machine Learning and Knowledge Discovery in Databases, pages 451–466, Berlin, Heidelberg, 2010. Springer. M Tamer Özsu and Patrick Valduriez. Principles of distributed database systems. Springer, New York, NY, USA, 1999. Andrew Pavlo, Evan PC Jones, and Stanley Zdonik. On predictive modeling for optimizing transaction execution in parallel OLTP systems. Proceedings of the VLDB Endowment, 5(2), 2011.
15
Andrew Pavlo, Carlo Curino, and Stanley Zdonik. Skew-aware automatic database partitioning in shared-nothing, parallel OLTP systems. In Proceedings of the 2012 ACM SIGMOD International Conference on Management of Data, pages 61–72, Scottsdale, AZ, USA, 2012. ACM. Abdul Quamar, K Ashwin Kumar, and Amol Deshpande. Sword: Scalable workload-aware data placement for transactional workloads. In Proceedings of the 16th International Conference on Extending Database Technology, pages 430–441, Genoa, Italy, 2013. ACM. Markus Schneider. Spatial data types for database systems: Finite resolution geometry for geographic information systems. Springer, Berlin, Heidelberg, 1997. Marco Serafini, Rebecca Taft, Aaron J Elmore, Andrew Pavlo, Ashraf Aboulnaga, and Michael Stonebraker. Clay: Fine-grained adaptive partitioning for general database schemas. Proceedings of the VLDB Endowment, 10(4):445–456, 2016. Jianbo Shi and Jitendra Malik. Normalized cuts and image segmentation. IEEE Transactions on Pattern Analysis and Machine Intelligence, 22(8):888–905, 2000. Takeshi Shibata, SungJun Choi, and Kenjiro Taura. File-access patterns of data-intensive workflow applications and their implications to distributed filesystems. In Proceedings of the 19th ACM International Symposium on High Performance Distributed Computing, pages 746–755, Chicago, IL, USA, 2010. ACM. Isabelle Stanton and Gabriel Kliot. Streaming graph partitioning for large distributed graphs. In Proceedings of the 18th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, pages 1222–1230, Beijing, China, 2012. ACM. Rebecca Taft, Essam Mansour, Marco Serafini, Jennie Duggan, Aaron J Elmore, Ashraf Aboulnaga, Andrew Pavlo, and Michael Stonebraker. E-store: Fine-grained elastic partitioning for distributed transaction processing systems. Proceedings of the VLDB Endowment, 8(3):245–256, 2014. Martijn Van Den Heuvel, Rene Mandl, and Hilleke Hulshoff Pol. Normalized cut group clustering of resting-state fmri data. PloS one, 3(4):e2001, 2008. Ulrike Von Luxburg. A tutorial on spectral clustering. Statistics and Computing, 17(4):395–416, 2007. Donghui Yan, Ling Huang, and Michael I Jordan. Fast approximate spectral clustering. In Proceedings of the 15th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, pages 907–916, Paris, France, 2009. ACM. Wenyin Yang, Guojun Wang, Kim-Kwang Raymond Choo, and Shuhong Chen. Hepart: A balanced hypergraph partitioning algorithm for big data applications. Future Generation Computer Systems, 83:250–268, 2018. Matthew D. Zeiler. Adadelta: An adaptive learning rate method, https://arxiv.org/abs/1212.5701.
16
2012.
URL