Классика баз данных - статьи
Затем эти бакеты еще раз
Затем эти бакеты еще раз просматриваются в порядке увеличения возраста, подсчитывается общее число записей acc, и цикл завершается на том бакете, для которого acc оказывается не меньше tot/2. Тесты показали, что скорость выполнения этого алгоритма в основном ограничивается скоростью считывания данных с диска: немногим более 15 минут на один проход по данным при типичной скорости последовательного чтения в 90 мегабайт в секунду. Центральный процессор при этом все время постыдно недоиспользуется.
Чтобы найти возрастную медиану по странам и полу:
int age, sex, country; int cnt[2][256][128]; int tot,acc; byte r[16]; fill cnt with 0; do read 16 bytes into r; age = r[0] & 01111111b; sex = r[1] & 10000000b; ctry = r[11] & 11111111b; cnt[sex][ctry][age] += 1; until end of file;
Затем:
for sex = 0 to 1 do for ctry = 0 to 255 do output ctry, sex; tot = sum (cnt[sex][ctry][age]); acc = 0; for age = 0 to 127 do acc += cnt[sex][ctry][age]; if(acc >= tot/2) output age; go to next ctry; end if; next age; next ctry; next sex;
Рис. 1. Вычисление возрастной медианы для жителей мужского и женского пола каждой страны мира за время, исчисляемое минутами
На самом деле, наша таблица "всех людей мира" поместится в основной памяти объемом в 128 гигабайт одного сервера Dell стоимостью в 15000 долларов. При работе с данными в основной памяти моя простая программа подсчета возрастной медианы по странам и полам выполнялась менее минуты. При таких показателях я бы усомнился называть эти данные "большими", учитывая, в частности, что мы живем в мире, в одном из исследовательских центров которого (LHC (Large Hadron Collider) в ЦЕРНе (CERN, European Organization for Nuclear Research)) преполагается ежегодно производить данные объемом в 15000 больше [10].
Однако для многих широко используемых приложений наш гипотетический набор данных из 6,75 миллиардов строк в действительности ставит серьезную проблему. Я пробовал загрузить свою фиктивную 100-гигабайтную всемирную перепись в широко используемую систему баз данных корпоративного уровня (PostgreSQL [6]), работающую на относительно мощной аппаратуре (восьмиядерная рабочая станция Mac Pro с 20 гигабайтами основной памяти и двухтерабайтным диском RAID 0), но был вынужден прервать процесс загрузки после шести часов работы, поскольку объем области хранения базы данных уже во много раз превышал объем исходного набора данных, и диск рабочей станции был почти полон. (Конечно, отчасти так получилось из-за "распаковки" данных.
