Using Randomized Algorithms for Optimizing Join Queries

Summary. The authors performed experiments using 2 different randomized algorithms to find close-to-minimal cost access plans: Simulated Annealing (SA) and Iterative Improvement (II). As a performance measure, they defined the cheapest plan found by either of the 3 to be minimal. They found that II found relatively cheap plans quickly but did not converge to a plan as cheap as that found by SA. SA, on the other hand, eventually found a close-to-minimal, if not the minimal, but it took longer to find. Based on these observations, the authors combined the two algorithms into what they coined the Two-Phase Optimization (2PO). 2PO uses II to quickly find what they called the ``cup bottom'' (area populated by minimal cost plans)of the plan space. Once in the ``cup bottom'', they switch to SA to find the final plan. 2PO outperformed either.

More detail

• Plan space. All 3 randomized algorithms studied map states into a multi- dimensional field. Each state is weighted with a cost. The goal is to find the state which is the global minimum by finding & recording several local minumums. A move from to a higher cost neighbor is uphill and a move to a lower cost state is downhill. Downhill moves are preferred.

  In this scheme, states are access plans and neighbors are similar access plans that have only a couple transformations performed on them.

• SA algorithm. SA begins at a randomly chosen state & moves between states based on their costs. Which move to take is determined by two things: the cost of the state and the temperature. The temperature begins at a relatively high temperature and, after each stage, lowers. A stage ends when the algorithm reaches equilibrium for that temperature. When the temperature is high, the algorithm is more likely to take a step toward a high cost state and vice-versa. The algorithm ends when the temperature reaches zero.

• II algorithm. Like the SA algorithm, II has the same idea of states with weighted costs, neighbors, moves, etc.. and again the goal is to find the state with the globally minimum cost. Unlike SA, though, II is never willing to make an uphill move. Rather, each stage ends when there is no downhill move to make and the local minimum is recorded. When some stopping condition is reached, the smallest local minimum found is returned.

• 2PO algorithm. As was mentioned in the summary, 2PO combines the best of SA with the best of II. II is performed first for some amount of time so that we can quickly get into an area of the plan space where the cheap plans are likely to reside. Then SA takes over to hone in on the best plan in that area. Experimentation found that this combination was successful since 2PO beat out both in all situations.

• The ``cup''. The authors conclude that since 2PO works so well that their plan space, were it graphed on a 2-d plane, is shaped like a cup with the cup bottom being the place where the cheap access methods hang out. The bottom of the cup is characterized by several local minima. They claim that II quickly gets them to the bottom of the cup and SA finds a good local minima withing the bottom.

After class notes

The measurement of how well the algorithms performed was based on the best plan provided by any of the 3 plans over a given query size NOT the actual true minimal plan.

Although their plan space may indeed have been a cup, other plan spaces for other testbeds may not be.