Abstract:Description of data distribution has been commonly used in databases to support query optimization,among which histograms are of particular interest.The existing conventional histogram construction methods have the problem of low efficiency of parallel resource utilization and high data transmission.To address these issues,a distributed and parallel constructing method was proposed for equi-width histogram in relational cloud database.Since the data ranges of different storage nodes are not the same,firstly,the local maximum and minimum values of working nodes were transferred to the application request node using the RPC protocol.These values were compared with each other to get the global maximum and minimum values based on master-slave model before the start of the histogram construction.Secondly,considering the optimization of data transmission during the histogram estimation,each working node scanned,sorted and partitioned the data into buckets according to the global maximum and minimum values which were transmitted from the application request node.Sub-histograms that were constructed in parallel improved the efficiency of resource utilization in the cluster.Finally,sub-histograms were aggregated to obtain the global histogram in the application request node.The algorithm divided the histogram task into multiple small tasks that could be simultaneously executed in a distributed cluster.During the histogram estimation,only a small portion of information about buckets and a few necessary data need to be transmitted over the network.The algorithm has been applied to the relational cloud database to optimize the initial scanning cost of the SQL statement,the data selection rate and other key parameters.The experimental results of the synthetic data and the real data demonstratedthat the amount of the data transmission was unrelated with the table size and the proposed algorithm achievedgood scalability.