Hi @szopsz,
I guess there are multiple questions in your posting here.
First, you can use the _count reduce function to get a number of the keys in the index based on your criteria. The Java SDK has the query API where it lets you enable or disable the reduce function on demand. Depending on which SDK you are using, thats a little different (2.0 vs 1.4).
In the 1.4 SDK, there is the paginator you can use, which does automatic pagination and for non-reduced views uses the startkey (+ startkeyDocID) approach to reduce overhead, if you have a reduced view of some sort this approach doesn’t work. I think it will in your case though.
You could then get the page for each paginator call and move the computation of the results to a thread pool. The other way would be that you do a _count reduce call first and then split it up. But the problem there is as you said you don’t know the IDs at this point and also keep in mind that data might change during the calls.
If you tell us what you want to achieve maybe we find a solution?