=head1 Using Randomized Algorithms for Optimizing Join Queries Yannis Ionnidas & Younkyung Cha Kang, University of Wisconsin, Madison, 1990 B The authors performed experiments using 2 different randomized algorithms to find close-to-minimal cost access plans: I (SA) and I (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 I (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. =head1 More detail =over 4 =item * B 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 I by finding & recording several I. A I from to a higher cost I is I and a move to a lower cost state is I. Downhill moves are preferred. In this scheme, states are access plans and neighbors are similar access plans that have only a couple I performed on them. =item * B 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 I. The temperature begins at a relatively high temperature and, after each I, lowers. A stage ends when the algorithm reaches I 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. =item * B 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 I is recorded. When some stopping condition is reached, the smallest local minimum found is returned. =item * B<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. =item * B 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. =back =head1 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 I the actual true minimal plan. Although their plan space may indeed have been a cup, other plan spaces for other testbeds may not be.