Hello,
We are calling salesforce REST API for object history from java.
Following are the sample queries, getting fired for different standard as well as custom objects

e.g.
1. SELECT Id, IsDeleted, Parent.Name, CreatedBy.Name, CreatedBy.Email, CreatedDate, Field, OldValue, NewValue FROM customObject4__History WHERE  CreatedDate > 2016-04-24T18:08:49Z order by CreatedDate

2. SELECT Id, IsDeleted, Parent.Name, Parent.LastModifiedBy.Name, Parent.LastModifiedBy.Email, Parent.LastModifiedDate, Field, OldValue, NewValue FROM customObject4__History where Parent.LastModifiedDate > 2016-04-24T18:09:09Z and Field = 'created' and IsDeleted = true order by Parent.LastModifiedDate

The response we receive is as below. This seems for query on large data sets.

 REST API return status of 400 with response: [{"message":"Your query request was running for too long.","errorCode":"QUERY_TIMEOUT"}]., status: 400]

From the analysis it seems that if the query is taking more than 2 minutes to run, salesforce server gives QUERY_TIMEOUT error.

1. Is there any way QUERY timeout can be increased? Can salesforce do it?
2. Query optimization is another way. Any pointers on how can above query be optmized? I understand the fields used in filter (where clause) should have an index for better performance (CreatedDate is by default indexed). What about other fields Parent.LastModifiedDate, Fields and IsDeleted ?
3. Does order by clause hampers performance?
4. Would batch size option help?

Any pointers on above queries would help.

Thanks,
Lalita