Cache': техника группировки

Евгений Каратаев

В этой статье рассмотрим техническую часть группировки данных. В качестве базы данных выберем СУБД Cache', поскольку в ней существует возможность самостоятельно использовать собственные структуры данных. Из общих слов на тему "зачем" можно сказать, что типа такие задачи возникают при составлении отчетов, что это очень важно, не всегда понятно, и прочее. Все вопросы на тему "зачем" в дальнейшем будем опускать и займемся вопросом "как". А именно, как сделать так, чтобы работало, работало хорошо и чтобы было понятно, какие возможности предоставляет техника группирования.

Операция группировки в базах SQL-типа объявляется опцией GROUP BY и зачастую сопровождается опцией ORDER BY. Те, кто имел дело с языком SQL, наверняка примерно представляют, что это такое и к чему приводит. Те же, кто не использует язык SQL, имеют с одной стороны отсутствие простого декларативного объявления своих намерений, и, с другой стороны, гораздо большую гибкость и могущество, не ограниченные ничем и никакими реализациями и их магическими ограничениями. Будем следовать второму варианту - ручное программирование операции группировки, и рассмотрим виды группирования и их особенности, плюсы и минусы.

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

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

Создадим тестовые данные скриптом вида:

create(n)

s:'$d(n) n=100

s:(n<1) n=-n

k ^group

n i,color,colors,figure,figures,count

s colors="красный~золотой~синий~зеленый~серебряный~желтый"

s figures="шарик~шишка~снежинка~белка~лебедь~рыбка"

f i=1:1:n d

. s color=$p(colors,"~",$r(6)+1)

. s figure=$p(figures,"~",$r(6)+1)

. s count=$r(10)+1

. s ^group(i)=color_"~"_figure_"~"_count

q

Здесь i - это некий условный номер партии. При группировании по полям цвет и фигура часть строк с их одинаковыми значениями объединяются в одну строку: если были строки

красный шарик 10

красный шарик 8

синий шарик 5

синий шарик 15

То при группировании мы должны получить

красный шарик 10

8

синий шарик 5

15

То есть из четырех исходных получили две выходные, причем в выходных строках в одну ячейку попали от одного до нескольких значений (количество игрушек в партии). Формально говоря, мы можем сделать с ними что хотим, но поскольку речь ведем о группировке, то в группировке принято из этих нескольких значений, попадающих в одну ячейку, составлять одно значение и приводить таким образом, выходные данные к классическому определению таблицы с атомарными значениями в каждой ячейке. Характер манипулирования такими наборами с целью получения одного значения называется функцией группирования. Наиболее часто встречаются самые простейшие - вроде банального сложения в столбик или вычисления их количества. В более сложных случаях значения, попавшие в одну ячейку, могут быть отсортированы по выбранному критерию, например, по дате получения партии, из которой было взято это значение и в совокупности с датой получения партии может быть получена например средняя скорость поступления таких изделий. Вообще говоря, эти функции группирования составляют совершенно отдельный интереснейший для прикладных специалистов класс задач, находящийся на стыке задач класса OLAP и Data Mining. В этой статье мы опустим их разнообразие и будем пользоваться только простейшей функцией - сложение в столбик, которой в SQL соответствует функций SUM. В приведенном выше примере запрос на SQL выглядел бы примерно как

select color, figure, SUM(count)

from NewYearToys

group by color, figure

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

Итак, группировка может быть классифицирована по типу выборки данных и по ширине группировки. По типу выборки данных группировка делится на группировку с ориентацией на выборку с помощью функции $ORDER и с ориентацией на выборку с помощью функции $QUERY. По ширине группировки деление идет на нормальную и широкую.

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

переменная( группирующее поле 1 ...

группирующее поле 2 ...

группирующее поле N ) = набор негруппирующих полей

Здесь под таинственными символами и обозначены различия типов группировки - в случае использования функции $ORDER используем конкатенацию значений группирующих полей, в случае использования функции $QUERY используем обычные запятые, рассматривая значения группирующих полей в качестве значений индексов соответствующего уровня.

Выполним группировку для функции $QUERY:

GroupQ()

; group to use $QUERY function

; use SUM function

k group

n i,color,figure,count

s i=""

f s i=$o(^group(i)) q:i="" d

. s color=$p(^group(i),"~",1)

. s figure=$p(^group(i),"~",2)

. s count=$p(^group(i),"~",3)

. s group(color,figure)=count+$G(group(color,figure),0)

q

Здесь выполняется проход по исходным данным, для наглядности значения полей сохраняются в отдельных переменных, после чего выполняется сложение. Функция $G используется для случая, если это сложение выполняется первый раз. Вместо сложения можем использовать любую иную функцию группирования, но в нашем примере будем пользоваться для простоты только одним сложением в столбик. После того, как данные сгруппированы в виде

group(color,figure)=SUM(count)

мы можем их получить одним проходом с помощью функции $QUERY:

WriteGroupedQ()

d QroupQ()

n color,figure,count,cf

s cf="group"

f s cf=$Q(@cf) q:cf="" d

. s color=$qs(cf,1)

. s figure=$qs(cf,2)

. s count=@cf

. w color,?15,figure,?30,count,!

q

Здесь значения полей получаются с помощью функции $QSUBSCRIPT. В случае использования этого типа группировки мы можем использовать несколько полей группирования и все равно сможем получить результат одним проходом. В целях создания более-менее формализованной обобщенной функции мы можем использовать номера в аргументах $QS. Если их получать из формальной спецификации запроса, то нет необходимости организовывать вложенные циклы прохода по уровням индексов.

Рассмотрим парный вышеприведенному метод группирования, ориентированный на использование функции $ORDER:

GroupO()

; group to use $ORDER function

; use SUM function

k group

n i,color,figure,count

s i=""

f s i=$O(^group(i)) q:i="" d

. s color=$p(^group(i),"~",1)

. s figure=$p(^group(i),"~",2)

. s count=$p(^group(i),"~",3)

. s group(color_$C(10)_figure)=

count+$G(group(color_$C(10)_figure),0)

q

Здесь результат получается в виде переменной с одним значением индекса, в котором с помощью разделителей используется символ $C(10). Для получения результата группировки можем использовать также только один проход, но с использованием функции $ORDER:

WriteGroupedO()

d GroupO()

n color,figure,count,cf

s cf=""

f s cf=$O(group(cf)) q:cf="" d

. s color=$P(cf,$C(10),1)

. s figure=$P(cf,$C(10),2)

. s count=group(cf)

. w color,?15,figure,?30,count,!

q

Здесь мы также можем составить обобщенную функцию группировки, если получим номера полей из формального запроса и подставим их в аргумент функции $PIECE.

В обоих типах группировки в правой части может стоять не одно значение негруппирующего поля, а несколько. Их можно хранить как в формате с разделителями, так и в списочном виде. В приведенном примере использовалось только одно негруппирующее поле, поэтому в случае если их несколько, код следует соответственно подправить.

Отметим плюсы и минусы обоих методов группирования. В первом случае (ориентация на $QUERY) результат выдается в отсортированном виде, и порядок сортировки является индексным порядком. Каких-либо дополнительных пересортировок уже не требуется. При этом следует помнить, что операция $QS может занять больше времени, чем $P во втором случае. К тому же обязательно следует скорректировать код для случая получения в качестве значения поля пустой строки. Например, всегда дополнять строку пробелом при группировании и удаления этого пробела при выдаче результата. Во втором случае, вообще говоря, отсортированность результата не гарантируется и определяется выбранным символом - разделителем. Если он меньше пробела, то результат будет отсортирован. И, так же как в первом случае, следует дополнять индексное значение неким символом на случай получения группировки только по одному полю и при возможности получения в качестве значения поля пустой строки.

В случае использования групировки, ориентированной на функцию $ORDER, результат, конечно, будет неким образом отсортирован, но результат врядли будет удовлетворительным, поскольку будет применяться индексная сортировка к агрегату полей, что является строковой сортировкой. В случае использования нестроковых (числовых) значений полей следует приводить их значения к строкам таким образом, чтобы сортировка проводилась в правильном порядке, соответствующем типу данных. Например, в случае использования целых чисел их следует заменять примерно как: число 123 заменяем на строку "+00000123". То есть во-первых добавляем символ знака, во-вторых дополняем нулями до некоторой выбранной длины. В случае использования дробных чисел ситуация усложняется - следует в строку вносить символ знака числа, десятичный символ, дробную часть, знак и величину порядка. Причем расположить эти части следует в порядке, обеспечивающем именно строковую сортировку. После проведения группировки с такой сортировкой в функции визуализации также следует провести соответствующую коррекцию данных, чтобы убрать нагромождение дополняющих нулей.

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

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

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

В этой ситуации помогает условная замена значений полей на соответствующие этим значениям числовые идентификаторы. Скажем, цвету красный сопоставляется число 1, цвету синий - 2 и так далее, после чего в группировании принимают участие не длинные поля типа названия организации, а короткие числа.

Эти промежуточные идентификаторы значений должны быть числами, для которых можно задать, во-первых, взаимно однозначное соответствие между значением и числом и, во-вторых, на наборе чисел должен быть определен порядок, соответствующий порядку значений полей. Выполняем два прохода. В первом получаем список значений группирующих полей, попавших в выборку, во втором проводим собственно группировку. При выдаче результата используем отображение числовых значений на значения полей. Примерный код получения списка значений:

WideGroup()

k group,map

n i,color,figure,count

s i=""

f s i=$O(^group(i)) q:i="" d

. s color=$p(^group(i),"~",1)

. s figure=$p(^group(i),"~",2)

. ; save colors and figures into special lists

. s map("color",color)=""

. s map("figure",figure)=""

После этого в локальной переменной map содержатся два списка с цветами и фигурами. Отметим, что до полного прохода по результатам выборки данных, попавших на группировку (в нашем случае это O(^group(i))) мы просто не можем построить сортированного списка числовых идентификаторов значений, поскольку данные приходят в заведомо несортированном виде.

После получения списков значений группирующих полей можем построить отображение на соответствующие числовые значения:

s color=""

f  s color=$O(map("color",color)) q:color="" d

. ; map color to ordered number

. s map("color",color)=$I(map("color"))

. ; map ordered number to color

. s map("Ncolor",map("color",color))=color

s figure=""

f s figure=$O(map("figure",figure)) q:figure="" d

. ; map figure to ordered number

. s map("figure",figure)=$I(map("figure"))

. ; map ordered number to figure

. s map("Nfigure",map("figure",figure))=figure

После этого в локальной переменной map имеем отображение значений цветов и фигур на числа, причем числа благодаря использованию индексной сортировки в O(map("color",color)) и O(map("figure",figure)) упорядочены в том же порядке. После этого, используя отображения значений на числа, можем провести широкую группировку:

n ncolor,nfigure

s i=""

f s i=$O(^group(i)) q:i="" d

. s color=$p(^group(i),"~",1)

. s figure=$p(^group(i),"~",2)

. s ncolor=map("color",color)

. s nfigure=map("figure",figure)

. s count=$p(^group(i),"~",3)

. s group(ncolor,nfigure)=count+$G(group(ncolor,nfigure),0)

q

Объединив образцы кода вместе, получим функцию, которая выполняет широкую группировку. Отметим, что никакой оптимизации здесь не приводилось, а получение данных, попадающих на группирование, не всегла такая простая операция, как просто проход по глобали. И, чтобы не выполнять ее дважды, имеет смысл в реальном коде сохранить выборку во временной глобали. И использовать глобали для группирования и отображения группирующих значений на числа. Поскольку данных может оказаться столь много, что они просто не поместятся в области данных процесса.

При выводе сгруппированных данных следует, конечно же, помнить, что группировали мы не значения, а их номера, поэтому используем построенное ранее отображение:

WriteWideGrouped()

d WideGroup()

n color,ncolor,figure,nfigure,count,cf

s cf="group"

f s cf=$Q(@cf) q:cf="" d

. s ncolor=$qs(cf,1)

. s nfigure=$qs(cf,2)

. s count=@cf

. s color=map("Ncolor",ncolor)

. s figure=map("Nfigure",nfigure)

. w color,?15,figure,?30,count,!

q

Сложно говорить о группировке и не затронуть группировку с подытогами. Например, получение той же группировки, но в которую вставлены данные отдельно по цветам безотносительно фигур игрушек, а также общая величина. Ничего сложного в этом нет. Конечно же, следует использовать тот же механизм группирования, но для каждой строки писать суммирование не только со строкой, идентифицируемой группой полей, но и идентифицируемой специальным маркером подитога вместо группирующего поля. Например, выбрав в качестве маркера подитога символ $C(11), получим группирование с подытогами по цвету:

; group to use $QUERY function

; use SUM function

k group

n i,color,figure,count

s i=""

f s i=$o(^group(i)) q:i="" d

. s color=$p(^group(i),"~",1)

. s figure=$p(^group(i),"~",2)

. s count=$p(^group(i),"~",3)

. s group(color,figure)=count+$G(group(color,figure),0)

. s group(color,$C(11))=count+$G(group(color,$C(11)),0)

q

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