Using the Hurwicz Criterion to Optimize Selection Queries Under Partial Ignorance

Optimizing queries in real-world situations under imperfect conditions is still a problem that has not been fully solved. We consider finding the optimal order in which to execute a given set of selection operators under partial ignorance of their selectivities. The selectivities are modeled as intervals rather than exact values and we apply various methods from decision theory in order to measure optimality. On the one hand, we evaluate the different techniques theoretically, showing which axioms of decision theory they satisfy and for which cases they efficiently provide an optimal solution. On the other hand, we also conduct an empirical evaluation, illustrating the differences of the approaches in terms of the relative error to the optimal solution. We demonstrate that a hybrid algorithm combining optimistic and pessimistic aspects performs best.