Mechanisms for performing database queries are provided. With these mechanisms, in response to a query request, a query plan intended for minimum query response time and a query plan intended for minimum query total time for the query request are obtained execution of the minimum query response time query plan and the minimum query total time query plan is started. Before the execution of the minimum query total time query plan reaches a specified point, an initial query result obtained from the execution of the minimum query response time query plan is output. In response to the execution of the minimum query total time query plan reaching the specified point, continuing the execution of the minimum query total time query plan to output remaining query results.