How to sort horizontal partitioned data

Question

I have a telco billing software system. In it there are daily logs of users' calls. The logs are horizontally partitioned by date (month). Each partition is stored in a separate database and may be spread over multiple instances.

In the UI the user will specify a date range. The data returned can be sorted on any field. The date range may span over multiple partitions. The application must support paging through the date range's data.

I cannot load too many records into memory for sorting. Putting sort inside the query only gives me sorted data inside one result-set.

So I need to sort data from multiple partitions which are each individually sorted. How can I return sorted records to the UI from multiple sorted result-sets?

EDIT: After more analysis on this problem, We have some more inputs. There is requirement of pagination also. Due to this we need to find out one more way to do realtime sorting on multiple resultsets.

Answer 1

By relying on ResultSet's ability to load limited data in memory we are able to come up with a solution in Java using Dynamic Comparator. Solution is to take first record from each resultSet and sort it in java and return first element from sorted data.

Detailed Solution:

First we built a program which can give us a dymanic Comparator based on the criteria choosed on the screen.

Second We have written one AggregateResultSet wrapper over the DAO which is wrapping over ResultSets from different partitions. Note: these individual ResultSets are already sorted with same criteria. Then AggregateResultSet will be given a dynamic comparator.

This AggregateResultSet will have a data structure to store first element of each result set initially. It will return the next element on call to next(). This element would be the element which comes first as per dynamicComparator. During next() call, We remove this element from temporary data structure and insert the next element from the same result set in the temporary data structure. This way AggregateResultSet will return data in expected order, by merging/storing/sorting very limited data in Java.

We hope to receive no comparison issues as we have mostly numeric/string data in sorting.