Как вы реализуете сортировку и разбиение на страницы распределенных данных?

Вот проблема, которую я пытаюсь решить:

Мне нужно иметь возможность отображать разбитую на страницы отсортированную таблицу данных, которые хранятся в нескольких сегментах базы данных.

Пейджинг и сортировка - это хорошо известные проблемы, которые большинство из нас может решить любым количеством способов, когда данные поступают из одного источника. Но если вы разделяете свои данные по шардам или используете DHT, или базу данных распределенных документов, или любой другой вариант NoSQL, который вы предпочитаете, все становится сложнее.

Здесь ' простая картина действительно небольшого набора данных:

Shard | Данные
1 | A
1 | D
1 | G
2 | B
2 | E
2 | H
3 | C
3 | F
3 | I

Сортировка по страницам (размер страницы = 3):

Страница | Данные
1 | A
1 | B
1 | C
2 | D
2 | E
2 | F
3 | G
3 | H
3 | I

И если бы мы хотели показать пользователю страницу 2, мы бы вернулись:

D
E
F

Если размер рассматриваемой таблицы составляет примерно 10 миллионов строк или 100 миллионов, вы не можете просто загрузить все данные на веб-сервер / сервер приложений, чтобы отсортировать их и вернуть правильную страницу. И вы, очевидно, не можете позволить каждому отдельному сегменту сортировать и разбивать на страницы свой собственный фрагмент данных, потому что сегменты не знают друг о друге.

Чтобы усложнить ситуацию, данные, которые мне нужно представить, не могут быть слишком далекими. даты, поэтому предварительное вычисление набора полезных сортировок заранее и сохранение результатов для последующего извлечения нецелесообразно.