1. A method for scheduling queries, the method comprising: maintaining a queue of queries, the queue identifying an order for executing the queries; receiving a new query; determining, for the new query and for each of the queries in the queue, a stretch metric indicative of a Quality of Service (QoS) measure, wherein the stretch metric for each of the queries is based on an end time of the query, an arrival time of the query, and the processing time of the query; minimizing an I p norm of the stretch metric for at least some of the queries in the queue, wherein p is a finite, real number greater than 1; determining, by a processor, a weight for the new query and a weight for each of the queries in the queue, wherein the weight for a query is based on the stretch metric of the query, and wherein the weight of a largest query in the queue is determined to be a largest weight only if such determination does not cause the stretch metric of the smallest query in the queue to exceed a predetermined threshold wait time; determining, by the processor, a position in the queue to insert the new query by comparing the weight of the new query to the weights of the queries in the queue; inserting the new query in the determined position in the queue; and selecting a query from the queue to execute based on the order for executing the queries identified from the queue, wherein the query with the largest weight is executed first.