RANDOMIZED ALGORITHMS FOR OPTIMIZING LARGE JOIN QUERIES +

Query optmuzatton for relatmnal database systems IS a combmatonal optumzahon problem, whtch makes exhaustrve search unacceptable as the query size grows Randomrzed algortthms. such as Simulated Annealmg (SA) and Iteratrve Improvement (II), are viable altemattves to exhaushve search We have adapted these algonthms to the optrmizatton of proJect-select-Jam queries We have tested them on large quertes of various types wrth drfferent databases, concludmg that m most cases SA tdentrfies a lower cost access plan than II To explain thts result, we have studied the shape of the cost funchon over the solutmn space associated with such queues and we have conJectured that tt resembles a ‘cup’ with relatively small vsrtatrons at the bottom Thus has msptred a new Two Phase Optrmtzatton algonthm, which 1s a combmatton of Sunulated Annealing and Iteratrve Improvement Expenmental results show that Two Phase Gpttmtzatron outperforms the ongtnal algonthms m terms of both output quality and runnmg tun