  Evaluating query predicates on data samples is the only way to estimate their
selectivity in certain scenarios. Finding a guaranteed optimal query plan is
not a reasonable optimization goal in those cases as it might require an
infinite number of samples. We therefore introduce probably approximately
optimal query optimization (PAO) where the goal is to find a query plan whose
cost is near-optimal with a certain probability. We will justify why PAO is a
suitable formalism to model scenarios in which predicate sampling and
optimization need to be interleaved.
  We present the first algorithm for PAO. Our algorithm is non-intrusive and
uses standard query optimizers and sampling components as sub-functions. It is
generic and can be applied to a wide range of scenarios. Our algorithm is
iterative and calculates in each iteration a query plan together with a region
in the selectivity space where the plan has near-optimal cost. It determines
the confidence that the true selectivity values fall within the aforementioned
region and chooses the next samples to take based on the current state if the
confidence does not reach the threshold specified as problem input. We devise
different algorithm variants and analyze their complexity. We experimentally
compare them in terms of the number of optimizer invocations, samples, and
iterations over many different query classes.
