Быстрый поиск в Google дал ответ:
Многие операции более эффективны при использовании столбцового подхода. В частности, операции, требующие доступа к последовательности значений из определенного столбца, выполняются намного быстрее. Если все значения в столбце имеют одинаковый размер (что верно по замыслу kdb), все становится еще лучше. Этот тип шаблона доступа типичен для приложений, для которых используются q и kdb.
Чтобы сделать это конкретным, давайте рассмотрим столбец 64-битных чисел с плавающей запятой:
q).Q.w[] `used
108464j
q)t: ([] f: 1000000 ? 1.0)
q).Q.w[] `used
8497328j
q)
Как видите, память, необходимая для хранения одного миллиона 8-байтовых значений, составляет лишь немногим более 8 МБ. Это потому, что данные хранятся последовательно в массиве. Для пояснения создадим еще одну таблицу:
q)u: update g: 1000000 ? 5.0 from t
q).Q.w[] `used
16885952j
q)
И t, и u совместно используют столбец f. Если бы q организовал свои данные в строки, использование памяти увеличилось бы еще на 8 МБ. Еще один способ убедиться в этом — взглянуть на k.h.
Теперь давайте посмотрим, что происходит, когда мы записываем таблицу на диск:
q)`:t/ set t
`:t/
q)\ls -l t
"total 15632"
"-rw-r--r-- 1 kdbfaq staff 8000016 May 29 19:57 f"
q)
16 байт служебных данных. Ясно, что все числа хранятся на диске последовательно. Эффективность заключается в том, чтобы избежать ненужной работы, и здесь мы видим, что q делает именно то, что нужно делать при чтении и записи столбца — ни больше, ни меньше.
Итак, этот подход экономит пространство. Как такое расположение данных влияет на скорость?
Если мы попросим q просуммировать все 1 миллион чисел, плотно упакованный в памяти весь список даст огромное преимущество по сравнению с организацией, ориентированной на строки, поскольку мы столкнемся с меньшим количеством промахов на каждом этапе иерархии памяти. Избегание промахов кеша и ошибок страниц необходимо для повышения производительности вашего компьютера.
Более того, выполнение математических операций над длинным списком чисел, которые все вместе находятся в памяти, представляет собой проблему, для решения которой современные наборы инструкций ЦП имеют специальные функции, в том числе инструкции для предварительной выборки элементов массива, которые потребуются в ближайшем будущем. Хотя эти функции изначально были созданы для повышения производительности мультимедиа на ПК, они также отлично подходят для статистики. Кроме того, тот же синергизм функций локальности и ЦП позволяет системам, ориентированным на столбцы, выполнять линейный поиск (например, в предложениях where в неиндексированных столбцах) быстрее, чем индексированный поиск (с сопутствующими им ошибками прогнозирования ветвлений), вплоть до поразительного количества строк.
Источники: http://www.kdbfaq.com/kdb-faq/tag/why-kdb-fast
person
Hrach Ghapantsyan
schedule
16.11.2013