Overall latency is reduced when processing tasks such as search queries by determining which tasks are “expensive,” or likely to exceed desired latency thresholds. For expensive queries processed according to partitions, the segments for each partition can be divided among various sub-queries, which allow each partition to be processed in parallel by multiple devices without the need for repartitioning. Further, the responses to the sub-queries can be monitored, and if one or more responses are not received within a specified amount of time then each sub-query for which a response is missing can be resent. The first response received will be consolidated with the results from the other queries, and the result returned.