An apparatus, program product and method perform runtime query optimization during execution of a query to select from among multiple available plans, or implementations, capable of implementing the query. The runtime query optimization utilizes a runtime-derived performance criterion to dynamically select from among multiple query implementations. A performance criterion is dynamically evaluated during execution of at least a portion of a query, and one of a plurality of query implementations defined in the query is selected based upon the dynamically-evaluated performance criterion. Once selected, execution of the query is continued using the selected query implementation.