An adaptive query execution plan enhancement is provided by: selecting a sample of literal sets from an execution history of a query statement; determining a plurality of access paths by applying each literal set in the sample to the query statement; for each given access path of the plurality of access paths, determining a total execution cost by applying each literal set in the sample to the given access path; and selecting a preferred access path from the plurality of access paths based on the total execution costs for each given access path. A plurality of preferred access paths for a plurality of query statements in an application workload is collected and may be presented as a query execution plan enhancement recommendation to users.