Techniques for analyzing an execution of a query statement based on a random archive are disclosed. A plurality of query statements that are executed during a particular time period are identified. A random sampling function is executed to randomly select a set of query statements from the plurality of query statements. Execution plans and/or performance metrics associated with each execution of the randomly-selected query statements are stored into a random archive. Responsive to determining that a performance metric for a current execution of a particular query statement does not satisfy a performance criteria, information associated with the particular query statement from the random archive is analyzed. A model plan characteristic associated with an execution of the particular query statement stored in the random archive is determined. An execution plan associated with the model plan characteristic is determined for another execution of the particular query statement.