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

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

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

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

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

Осколок |
данных 1 |
1 | D
1 | G
2 | B
2 | E
2 | H
3 | C
3 | F
3 | I

Отсортировано на страницы (Размер страницы = 3):

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

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

D
E
F

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

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

Ответ 1

Существует несколько решений, некоторые из которых могут оказаться вам немыслимыми, но, возможно, один из них будет придерживаться:

Сделайте окантовку по диапазонам ввода для этого значения (например, осколок 1 содержит A-C, осколок 2 D-F и т.д.). В качестве альтернативы используйте другую таблицу с внешними ключами в эту таблицу в качестве индекса и обведите индексную таблицу с помощью этой системы. Таким образом, вы можете легко найти и получить заданные диапазоны. Это решение, вероятно, является лучшим с точки зрения производительности, если вы можете это сделать (он предполагает, что количество осколков статично и осколки надежны).
Определите элементы страницы путем двоичного поиска. Например, скажем, что вам нужны позиции от 100 до 110. Для каждого осколка подсчитайте количество значений лексикографически ниже "М". Если сумма чисел выше 100, уменьшите опорную точку, в противном случае увеличьте ее (используя двоичный поиск). После того, как вы идентифицируете 100-й элемент (первый элемент на своей странице), возьмите 9 верхних 9 (10 - 1) предметов, превышающих этот предмет, из каждого осколка, выберете их, отсортируйте весь список, возьмите верхнюю 9 из списка, добавьте первый элемент и там ваша страница! Этот подход сложнее реализовать и потребует O(log(n)) запросов, поэтому он медленнее, чем (1), но все же может быть достаточно быстрым, если нагрузка не очень тяжелая.
Сохраните номер страницы с каждым значением. Это дало бы вам невероятно быстрое чтение, но ужасно медленно пишет, поэтому оно работает только в сценарии, где очень мало записей (или только добавляется в терминах упорядоченной переменной).