# Query Optimization in Distributed Database Based on Improved Artificial Bee Colony Algorithm
## 2 Proposed Method
### Improved Artificial Bee Colony Algorithm  
The bees in the artificial bee colony (ABC) algorithm are categorized into three groups [33; 34; 35] including leader bees, follower bees, and scout bees. Half of the colony consists of leader bees, and the other half consists of follower bees. Leader bees are responsible  
Figure 1: Query execution process in a distributed database. for finding available food sources, collecting information, and passing food information to the follower bees. The follower bees select good food sources from the information passed on by the leader bees to further search for food. When the quality of a food source does not improve by a predetermined number of iterations, the corresponding leader bee abandons the food source, and then the leader bee becomes a scout bee and starts searching for a new food source in a location farther away. The location of a food source corresponds to a possible solution to the optimization problem, which in this paper is a feasible query execution plan (QEP), whereas the amount of food from each food source represents the quality (fitness) of the solution in question. Meanwhile, the number of leader bees is equal to the number of food sources. The specific steps are as follows:  
The first step is data preprocessing. The input to the algorithm is the data sharding-site matrix (DSM) generated from the metadata table of the database system during the query process. However, this input matrix is not yet directly usable by the algorithm, so it also needs to be de-zeroed and transposed to generate a search domain matrix executable by the artificial bee colony algorithm. As shown in Figure 2, in the data sharding-site matrix, \"1\" represents that the data sharding exists in the corresponding site, and \"0\" is the opposite. In the feasible domain matrix, each row represents the site number that stores a certain data sharding; for example, the first row shows that the sites that store data sharding 1 are site 1, site 2, and site 5. In the second step, each leader bee searches for a food source. The initial position of the food source \(X_{i}=\{X_{i1},X_{i2},\,\ldots,\,X_{id}\}\) is randomly generated in the search domain matrix according to the equation below:  
\[X_{id}=Random(L_{d}) \tag{1}\]  
where \(d=0,\,1,\,2\,\ldots D\), with D being the dimension of the feasible solution. In this paper, D represents the data site where one of the required data shardings of a feasible query execution plan is located; \(Random(L_{d})\) denotes the random selection of a data site with the \(d\)-th data sharding in the row where the \(d\)-th data sharding is located in the search domain matrix. The fitness value of a food source is measured as the execution cost of a feasible query execution plan. In distributed databases, the cost of a query is mainly the communication cost incurred by the transmission of data among sites. In order to minimize the cost of a query, the transmission of data among sites should be minimized. Therefore, the concentration of data sites selected in the query execution plan should be as high as possible, as expressed in equation below:  
\[Fit=\sum_{i=1}^{M}\frac{S_{i}}{N}(1-\frac{S_{i}}{N}) \tag{2}\]  
Figure 2: Data preprocessing. where \(M\) is the number of sites involved in the query plan, \(N\) is the number of data shardings involved in the query plan, \(S_{i}\) is the number of times the i-th site is used in the query plan, and the query cost \(Fit\) between 0 and \((N-1)/N\). 0 means optimal, that is to say, that the query plan involves data shardings in the same site, with no need to carry out the site-to-site data transfer. Additionally, \((N-1)/N\); that is to say, the data shardings involved in query plan are all from different sites, and all the data need to carry out the transmission of site-to-site transfer.