DOME: dynamic optimization on multiprocessor engines, a statistical approach
Fotios Barlos · 1993
To efficiently handle a continuous increase in the volume of information, elaborate multicomputer database machines and sophisticated software tools are employed. Maximum exploitation of parallelism dictates an even partitioning of the computation across the processing sites. To achieve a uniform load is difficult when the data are highly skewed since characterizing the expected workload can introduce significant overhead. We develop a query optimization approach, named Dynamic Optimization on Multiprocessor Engines (DOME), that uses a dynamic sampling methodology to determine the frequency distribution along each level of the query tree. DOME covers the three main multiprocessor query optimization areas of Workload Partitioning, Site Selection, and Operation Ordering. The DOME optimizer samples the input relations of a query tree and subsequently performs the computation of the query on the samples to generate the intermediate results of the tree. Contrary to previous static optimizers that use analytical formulas to estimate the frequency distribution of the relations at higher levels of the query tree DOME derives the required frequency distribution by analyzing the characteristics of the developed sampled relations. We prove that the application of the same relational operation on relations and their samples produces relations with the same statistical characteristics. We implemented DOME on an Intel i860 hypercube system with 32 nodes and test its behavior through extensive experimentation. DOME provides uniform workload distribution across all the tests. The Workload Partitioning algorithms yields an order of magnitude factor improvement over prior approaches for highly skewed data during Project-Join execution sequences. The Site Selection algorithms provide approximately a six fold factor improvement over a static allocation approach for Join operation. The Operation Ordering approach provides approximately a 20% improvement over a random resolver for Three-Way Join operations with a sample size of 10% of the input relations. Overall, DOME provides savings across the whole domain of the input datasets, and the savings become significant as the skewness of the input relations grows.