A data management system receives a query for data. A deadline for completing the query is supplied along with the query. The data management system determines access plans for the query and selects one of the access plans for execution to return a results set for the query. The selected access plan is selected according to an estimated ability to complete the query prior to the deadline. Further, the access plan is selected according to a lowest resource usage among the plans that can be completed the query prior to the deadline.