1. A method for adaptive query execution plan enhancement by a computer system comprising a processor, comprising: 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, comprising, for each given literal set in the sample: generating a new query statement by substituting variables in the query statement with the given literal set; explaining the new query statement to obtain a given critical access path; associating the given critical access path with the given literal set; and incrementing a total sampling count associated with 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.