When a query is received by a stateful data processing service, the service determines, for each table scan (and associated operations) of a query, whether to select the table scan for execution by a stateless data processing service. The selected table scans are sent to the stateless data processing service for execution, and results are received by the stateful data processing service. The stateful data processing service may also execute other table scans of the query locally, against a local data cache. If the data is not present in the local data cache, then the stateful data processing service will copy the table data into the local data cache before executing the table scan. A query result based on the remote and/or local table scans may then be returned to the client.