Robust heuristics for scalable optimization of complex SQL queries

Modern database systems incorporate a query optimizer to identify the most efficient "query execution plan" for executing the declarative SQL queries submitted by users. A dynamic-programming-based approach is used to exhaustively enumerate the combinatorially large search space of plan alternatives and, using a cost model, to identify the optimal choice. While dynamic programming (DP) works very well for moderately complex queries with up to around a dozen base relations, it usually fails to scale beyond this stage due to its inherent exponential space and time complexity. Therefore, DP becomes practically infeasible for complex queries with a large number of base relations, such as those found in current decision-support and enterprise management applications. To address the above problem, a variety of approaches have been proposed in the literature. Some completely jettison the DP approach and resort to alternative techniques such as randomized algorithms, whereas others have retained DP by using heuristics to prune the search space to computationally manageable levels. In the latter class, a well-known strategy is "iterative dynamic programming" (IDP) wherein DP is employed bottom-up until it hits its feasibility limit, and then iteratively restarted with a significantly reduced subset of the execution plans currently under consideration. The experimental evaluation of IDP indicated that by appropriate choice of algorithmic parameters, it was possible to almost always obtain "good" (within a factor of twice of the optimal) plans, and in the few remaining cases, mostly "acceptable" (within an order of magnitude of the optimal) plans, and rarely, a "bad" plan. While IDP is certainly an innovative and powerful approach, we have found that there are a variety of common query frameworks wherein it can fail to consistently produce good plans, let alone the optimal choice. This is especially so when star or clique components are present, increasing the complexity of th- e join graphs. Worse, this shortcoming is exacerbated when the number of relations participating in the query is scaled upwards.

Stepwise Crystallization: Illustrative Examples of the Use of Metalloligands Cu-6(mna)(6)](6-) and (Ag-6(Hmna)(2)(mna)(4)](4-) (H(2)mna=2-Mercapto Nicotinic Acid) in the Formation of Heterometallic Two- and Three-Dimensional Assemblies with brucite, pcu, and sql Topologies

Three new inorganic coordination polymers, {Mn(H2O)(6)]-Mn-2(H2O)(6)](Cu-6(mna)(6)]center dot 6H(2)O}, 1, {Mn-4(OH)(2)(H2O)(10)] (Cu-6(mna)6]center dot 8H(2)O}, 2, and {Mn-2(H2O)(5)]Ag-6(Hmna)(2)(mna)(4)]center dot 20H(2)O}, 3, have been synthesized at room temperature through a sequential crystallization route. In addition, we have also prepared and characterized the molecular precursor Cu-6(Hmna)(6)]. Compounds 1 and 3 have a two-dimensional structure, whereas 2 has a three-dimensional structure. The formation of 2 has been achieved by minor modification in the synthetic composition, suggesting the subtle relationship between the reactant composition and the structure. The hexanudear copper and silver duster cores have Cu center dot center dot center dot Cu and Ag center dot center dot center dot Ag distances close to the sum of the van der Waals radii of Cu1+ and Ag1+, respectively. The connectivity between Cu-6(mna)(6)](6-) cluster units and Mn2+ ions gives rise to a brucite related layer in 1 and a pcu-net in 2. The Ag-6(Hmna)(2)(mna)(4)](4-) cluster in 3, on the other hand, forms a sql-net with Mn2+. Compound 1 exhibits an interesting and reversible hydrochromic behavior, changing from pale yellow to red, on heating at 70 degrees C or treatment under a vacuum. Electron paramagnetic resonance studies indicate no change in the valence states, suggesting the color change could be due to changes in the coordination environment only. The magnetic studies indicate weak antiferromagnetic behavior. Proton conductivity studies indicate moderate proton migrations in 1 and 3. The present study dearly establishes sequential crystallization as an important pathway for the synthesis of heterometallic coordination polymers.

Efficiently Approximating Query Optimizer Plan Diagrams

Given a parametrized n-dimensional SQL query template and a choice of query optimizer, a plan diagram is a color-coded pictorial enumeration of the execution plan choices of the optimizer over the query parameter space. These diagrams have proved to be a powerful metaphor for the analysis and redesign of modern optimizers, and are gaining currency in diverse industrial and academic institutions. However, their utility is adversely impacted by the impractically large computational overheads incurred when standard brute-force exhaustive approaches are used for producing fine-grained diagrams on high-dimensional query templates. In this paper, we investigate strategies for efficiently producing close approximations to complex plan diagrams. Our techniques are customized to the features available in the optimizer's API, ranging from the generic optimizers that provide only the optimal plan for a query, to those that also support costing of sub-optimal plans and enumerating rank-ordered lists of plans. The techniques collectively feature both random and grid sampling, as well as inference techniques based on nearest-neighbor classifiers, parametric query optimization and plan cost monotonicity. Extensive experimentation with a representative set of TPC-H and TPC-DS-based query templates on industrial-strength optimizers indicates that our techniques are capable of delivering 90% accurate diagrams while incurring less than 15% of the computational overheads of the exhaustive approach. In fact, for full-featured optimizers, we can guarantee zero error with less than 10% overheads. These approximation techniques have been implemented in the publicly available Picasso optimizer visualization tool.