SciDB была создана для работы с научными данными, которые чаще всего представлены в виде многомерных массивов очень большого размера. Архитектура SciDB предполагает распределённую и параллельную обработку этих данных. В отличие от традиционных СУБД, где единицей хранения обычно является кортеж (запись), SciDB использует вертикальное хранение данных, при котором каждый атрибут хранится отдельно. Массив разбит на чанки - блоки фиксированного логического размера. Размер чанка выбирается из соображений оптимизации работы с диском и передачи данных по сети. Обычно он составляет несколько мегабайт, что позволяет эффективно читать данные с диска без лишних перемещений головки диска.

Научные приложения имеют дело с плотными и разреженными матрицами. SciDB поддерживает два типа разреженных матриц: логически плотные и логически разреженные. В первом случае мы имеем дело с обычным прямоугольным массивом, большинство элементов которого имеют одинаковое значение (обычно "0", но, в общем случае, может быть несколько часто повторяющихся значений). При этом, все эти значения участвуют в вычислениях (например, в умножении матриц). Логически разреженные матрицы имеют "дырки" и "рваные" (ragged) границы. В этом случае некоторые элементы матрицы считаются пустыми и не подлежат обработке. Для их представления SciDB использует специальный атрибут - битовую маску, которая отмечает пустые элементы для всего массива. Наличие такого атрибута позволяет эффективно производить некоторые манипуляции с массивами без доступа непосредственно к данным массива, манипулируя только относительно небольшой битовой маской.

Для эффективной работы как с плотными, так и с разреженными данными, SciDB использует RLE-кодирование чанка. Суть RLE (Run Length Encoding) заключается в кодировании последовательности элементов с одинаковым значением парой <значение, длина>. SciDB применяет RLE как для битовой маски, так и для самих данных (payload). Причём используется двойной уровень адресации – RLE-представление битовой маски задает позиции в RLE-представлении самих данных, позволяя избежать избыточного хранения координат для всех атрибутов массива (следствие вертикального хранения данных). Хранение смещения вместо длины (как в классической реализации RLE) позволяет осуществлять быстрое позиционирование в чанке с использованием двоичного поиска.

RLE-формат позволяет не только существенно сжать разреженные данные, но и эффективно их обрабатывать. Во-первых, за счет уменьшения числа производимых операций (можно выполнить операцию один раз для каждого сегмента, полученного в результате пересечения RLE-сегментов операндов). Во-вторых, реализация векторных операций с использованием RLE даёт возможность вынести многочисленные проверки (выход за границу массива, проверка ячейки на пустоту, проверка значения на NULL...) вне тела основного цикла обработки данных, ускоряя выполнение цикла.

В докладе будет рассказано о том, как использование RLE-представления и векторных операций в SciDB позволяет достичь высокой производительности в операциях с разреженными массивами. Кроме того, будет описана общая архитектура SciDB и за счёт чего достигается выигрыш в скорости выполнения запросов по сравнению с классическими СУБД.

Литература:

1. Philippe Cudré-Mauroux, Hideaki Kimura, Kian-Tat Lim, Jennie Rogers, Roman Simakov, Emad Soroush, Pavel Velikhov, Daniel L. Wang, Magdalena Balazinska, Jacek Becla, David J. DeWitt, Bobbi Heath, David Maier, Samuel Madden, Jignesh M. Patel, Michael Stonebraker, Stanley B. Zdonik: A Demonstration of SciDB: A Science-Oriented DBMS. PVLDB 2(2): 1534-1537 (2009)
   http://www.cs.washington.edu/homes/soroush/papers/scidb-vldb09.pdf
2. Michael Stonebraker, Paul Brown, Alex Poliakov, Suchi Raman: The Architecture of SciDB. SSDBM 2011: 1-16
   http://www.springerlink.com/content/u646u344r82218x3/