In most database systems, the values of many important run-time parameters of the system, 
the data, or the query are unknown at query optimization time.  Parametric query 
optimization attempts to identify several execution plans, each one of which is optimal 
for a subset of all possible values of the run-time parameters.  We present a general 
formulation of this problem and study it primarily for the buffer size parameter.  We 
adopt randomized algorithms as the main approach to this style of optimization and enhance 
them with a sideways information passing feature that increases their effectiveness in the 
new task. Experimental results of these enhanced algorithms show that they optimize queries 
for large numbers of buffer sizes in the same time needed by their conventional versions 
for a single buffer size, without much sacrifice in the output quality.