  Optimising 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 modelled as intervals
rather than exact values and we apply a concept from decision theory, the
minimisation of the maximum regret, as a measure of optimality. We show that
the associated decision problem is NP-hard, which renders a brute-force
approach to solving it impractical. Nevertheless, by investigating properties
of the problem and identifying special cases which can be solved in polynomial
time, we gain insight that we use to develop a novel heuristic for solving the
general problem. We also evaluate minmax regret query optimisation
experimentally, showing that it outperforms a currently employed strategy of
optimisers that uses mean values for uncertain parameters.
