Вернуться
назад в библиотеку
| |
|
История гистограмм является длинной и насыщенной, наполненной детальной информацией на каждом шаге. Она включает применение гистограмм в разных областях науки, успехи и неудачи применения гистограмм при аппроксимировании и сжатии информации, принятие гистограмм в промышленности и решения большого числа проблем, связанных с гистограммами. В этой статье в духе самих методов гистограмм мы сжимаем всю их историю (включая их "будущую историю", как она представляется сегодня) в заданный/фиксированный объем текста, регистрируя, главным образом, детали временных промежутков, событий и результатов, представляющих наивысший интерес (с точки зрения автора). При ограниченном числе проведенных экспериментов семантическое расстояние между сжатой и полной формами истории оказалось относительно небольшим!
Приведенная цитата говорит о том, что гистограммы использовались задолго до того, как получили свое имя, но их дата рождения неясна. Столбчатые диаграммы (bar chart), т.е. гистограммы, в которых с каждым столбцом ассоциируется отдельный 'базисный' элемент, скорее всего, предшествуют гистограммам, и это помогает нам установить нижнюю временную границу их первого появления. Наиболее древняя столбчатая диаграмма появилась в книге шотландского политического экономиста Уильяма Плейфейра (William Playfair)3 "The Commercial and Political Atlas" (London 1786), в которой демонстрируются показатели импорта и экспорта Шотландии в семнадцать стран в 1781 г. [74]. Хотя Плейфейр относился к своему изобретению скептически, в последующие годы оно было принято многими, включая Флоренса Найтингейла (Florence Nightingale), который использовал их в 1859 г. для сравнения смертности в армии в мирное время со смертностью гражданского населения, и путем этого убедил правительство улучшить гигиенические условия в армии.
Из всего сказанного ясно, что гистограммы задумывались как визуальная поддержка статистической аппроксимации. Даже сегодня этот смысл доминирует в общем восприятии гистограмм. В словаре Вебстера гистограмма определяется как "столбчатая диаграмма частотного распределения, в которой ширина столбцов пропорциональна классам, на которые была разделена переменная, а высота столбцов пропорциональная частотам этих классов". Однако гистограммы исключительно полезны, даже если отсоединить их от канонического графического представления и рассматривать как чисто математические объекты, сохраняющие приближения распределений данных. Именно так мы относимся к ним в этой статье.
В последние два десятилетия гистограммы использовались в нескольких областях информатики. Кроме области баз данных, гистограммы играют важную роль, главным образом, в областях обработки изображений и машинного зрения. При заданном изображении (или видео) и визуальном пиксельном параметре, гистограмма фиксирует для каждого возможного значения параметра ("класса" по Вебстеру) число пикселей, имеющихся у этого значения ("частота" по Вебстеру). Такая гистограмма является сводной характеристикой изображения и может быть очень полезна при решении нескольких задач: распознавании похожих изображений, сжатии изображений и т.д. В литературе наиболее распространены диаграммы цветов, например, в системе QBIC [21], но было предложено и несколько других параметров, например, плотность границ, текстурность, градиент яркости и т.д. [61]. Вообще говоря, гистограммы, используемые в областях обработки изображений и машинного зрения, являются точными. Например, в гистограмме цветов содержится раздельное и точное число пикселей для каждого возможного отдельного цвета изображения. Единственным элементом аппроксимации могло бы быть число бит, используемых для представления различных цветов: наличие меньшего числа бит означает, что несколько реальных цветов будет изображаться одним цветом, ассоциируемым с числом пикселей, которое имелось бы совместно у всех заменяемых таким образом цветов. Однако даже такая разновидность аппроксимации не является распространенной. В области баз данных гистограммы используются как механизм выровненного по краям сжатия и аппроксимации распределений данных. В литературе и системах они появились в 1980-х и впоследствии изучались с возрастающей интенсивностью. В этой статье мы концентрируемся на понятии гистограмм, принятом в области баз данных, обсуждаем наиболее важные разработки, относящиеся к этой теме, и кратко характеризуем несколько проблем, которые считаем интересными, и решение которых может еще более расширить применимость и полезность гистограмм.
Распределение данных для Xi - это множество пар Ti = {(vi (1), fi(1)), (vi(2), fi(2)), …, (vi(Di ), fi(Di))}.
Соединенная частота (joint frequency) f(k1, …, kn) комбинации значений < v1(k1), …, vn(kn) >- это число кортежей в R, в которых для всех i атрибут Xi содержит значение vi(ki). Соединенное распределение данных T1,…,n для X1,…,Xn - это полное множество пар (комбинация значение, соединенная частота).
Далее для одномерного случая мы будем использовать введенные обозначения без нижнего индекса i.
Правило разделения: Здесь можно выделить следующие характеристики:
Следуя [67], мы используем p(s,u) для обозначения сериального класса гистограмм с ограничением разделения p, параметром разделения s и параметром источника u.
Алгоритм конструирования: Это алгоритм, который по заданному правилу разделения конструирует гистограммы, соответствующие этому правилу. Часто для одного класса гистограмм существует несколько алгоритмов конструирования с разной эффективностью.
Аппроксимация значений: В этом аспекте фиксируется то, как внутри бакета аппроксимируются значения атрибута, что не зависит от правила разделения гистограммы. Наиболее распространенными альтернативами являются предположение о непрерывности значений (continuous value assumption) и предположение о равномерности протяженностей (uniform spread assumption); в обоих случаях предполагается, что значения равномерно размещаются в диапазоне, покрываемом бакетом, но в первом случае игнорируется число этих значений, а во втором это число регистрируется внутри бакета.
Аппроксимация частоты: В этом аспекте фиксируется то, как внутри бакета аппроксимируются частоты. Доминирующий подход опирается на предположение о равномерности частот (uniform distribution assumption), в котором предполагается, что частоты всех элементов в бакете одни и те же и равны среднему значению реальных частот.
Гарантии ошибок: Имеются верхние границы ошибок оценок, производимых гистограммой, обеспечиваемые на основе информации, которую поддерживает гистограмма.
Многомерная гистограмма на множестве атрибутов конструируется путем разделения соединенного распределения данных этих атрибутов. У таких гистограмм имеются точно такие же характеристики, как и у одномерных гистограмм, за исключением того, что требуется более сложное разделения, и оно не всегда так отчетливо раскладывается в четыре других характеристики, как раньше, например, в этом случае нет реального параметра разделения, поскольку в многомерном пространстве не может быть упорядоченности [66].
Гистограммы с одинаковой шириной представляли собой существенное усовершенствование предположения о равномерном распределении для всего множества значений (т.е., по существу, гистограммы с единственным бакетом), на котором в то время основывались практические системы. Поэтому они были быстро внедрены сначала в коммерческую версию СУБД Ingres, а потом и в другие СУБД.
Насколько нам известно, гистограммы с частотой в качестве параметра разделения представляли первое отклонение от группировки бакетов на основе значений не только в области баз данных, но также и в математике и статистике. Кроме того, их введение позволило существенно обобщить некоторые распространенные практические приемы, которые уже использовались в коммерческих системах (например, в DB2), где информация о значениях с наибольшей частотой поддерживалась индивидуально и точно по причине ее важности для оценки селективности. Такой прием является примером особого вида гистограммы с классом разделения со смещением к краю и частотой в качестве параметра разделения: значения с наивысшим значением параметра разделения поддерживаются в одиночных бакетах. Хотя в нескольких случаях гистограммы со смещением к краю оказываются менее точными, чем общие сериальные гистограммы, они достаточно эффективны.
Ответ на первый вопрос поступил в форме v-оптимальных (v-optimal) гистограмм, которые разделяют распределение данных таким образом, что (грубо говоря) минимизируется дисперсия значений параметра источника внутри каждого бакета [38].
К сожалению, аналитический ответ на второй вопрос отсутствует, но большое число экспериментов привело к формированию пространства характеристик гистограмм, которое мы используем в качестве основы обсуждения в данной статье (разд. 2.3) [67]. В дополнение к ограничениям разделения equi-sum и v-optimal было введено несколько новых возможных ограничений, целью которых, аналогично v-optimal, являлось избежание группировки в одном бакете слишком разных значений параметра источника. Среди этих ограничений мы выделяем ограничение maxdiff, которое устанавливает границы бакетов между соседними значениями параметра источника (в порядке параметра разделения) с наибольшей разностью, и compressed, которое помещает наибольшие значения источника в одиночные бакеты и разделяет оставшиеся значения в стиле equi-sum. В целом, было показано, что новые ограничения разделения (т.е. v-optimal, maxdiff и compressed) являются наиболее эффективными при сдерживании ошибок в оценках размеров результатов запросов.
В этой же работе было указано несколько возможностей для параметров разделения и источника, т.е. значение, протяженность, частота, площадь, накопленная частота и т.д., где частота и площадь являются наилучшими параметрами источника. Интересно, что наилучшим параметром разделения оказалось значение, а не частота, как должно было бы следовать из исходных результатов по поводу оптимальности; это означает, что если значения не являются точно известными, то наличие бакетов с перекрывающимися диапазонами значений не окупается для запросов по диапазону значений.
Наиболее эффективные из этих гистограмм реально внедрены в промышленные продукты (см. разд. 4). Кроме того, в дополнение к оценке селективности для различных реляционных и не реляционных запросов эти гистограммы оказались очень эффективными и при обеспечении приблизительные ответы на запросы [39].
После определения упомянутого пространства гистограмм было проведено несколько исследовательских работ, в которых изучались одна или несколько характеристик пространства и предлагались альтернативные, усовершенствованные подходы. Ниже мы в отдельных подразделах кратко описываем наиболее значимые части работ, посвященных каждой из этих характеристик. За исключением специально отмечаемых случаев, речь идет об одномерных гистограммах.
Только несколько лет спустя были предложены некоторые новые правила разделения [66], которые опирались на универсализм таксономии гистограмм [67]. Наиболее эффективным семейством таких правил было MHIST-2, которое начинает со всего распределения данных, размещенного в одном бакете, и на каждом шаге расщепляет пространство, занимаемое одним из сформированных ранее бакетов, на два подпространства, пока не исчерпается бюджет бакетов. Расщепление производится в том бакете и по тому измерению, которые характеризуются как наиболее "критические", т.е. частное распределение (marginal distribution) которых больше всего нуждается в разделении. Расщепление основывается на используемых (одномерном) ограничении разделения и параметре источника. В сочетании с наиболее эффективными ограничениями разделения (т.е. с v-optimal или maxdiff с частотой или площадью) MHIST-2 представляет значительное усовершенствование исходных многомерных гистограмм с одинаковой глубиной.
После появления MHIST было предложено много интересных правил разбиения. Одним из них является семейство правил GENHIST [31], которое изначально было предложено в контексте многомерных вещественных данных, но его применимость оказалась более широкой. Основная характеристика GENHIST состоит в том, что оно допускает перекрытие бакетов в пространстве многомерных значений: алгоритм начинает свою работу с равномерного сеточного разделения (grid partitioning) пространства, а затем итеративно укрупняет бакеты, содержащие большое число элементов данных. Это порождает два эффекта: во-первых, уменьшается плотность данных в каждом бакете, что сглаживает плотность в целом; во-вторых, бакеты становятся перекрывающимися, что приводит к созданию гораздо большего числа различных областей, чем число самих бакетов. Аппроксимацией распределения данных внутри каждой области является комбинация того, что показывают все перекрывающиеся бакеты, образующие данную область. В результате при небольшом числе бакетов обеспечиваются аппроксимации с низким уровнем ошибок.
Альтернативным подходом является STHoles Histogram [11], который дуален по отношению к GENHIST: вместо области, покрываемой бакетом увеличивающегося размера и перекрывающегося с другими бакетами, в STHoles эта область может уменьшаться в размере благодаря удалению ее части (т.е. открытия отверстия (opening a hole)), образующей отдельный, дочерний бакет. Это приводит к порождению бакетов, не являющихся сплошными прямоугольниками, и тем самым позволяет фиксировать достаточно нерегулярные распределения данных.
Определение эффективных правил многомерного разделения ни в коем случае не является закрытой проблемой; непрерывно предлагаются различные подходы [23].
По отношению к аппроксимации множества значений, попадающих в одномерный бакет, имеются два подхода. При традиционном предположении о непрерывности значений поддерживается наименьший объем информации (только минимальное и максимальное значения), но ничего такого, что могло бы каким-то образом подсказать, сколько значений имеется, и какими они могли бы быть. При использовании более современного предположения о равномерности промежутков [67] также поддерживается число значений внутри каждого бакета, и реальное множество значений аппроксимируется множеством, формируемым путем (виртуального) размещения того же числа значений на равных расстояниях между минимальным и максимальным значениями. В другом варианте этого подхода предлагается сохранять не реальную среднюю протяженность внутри бакета, а протяженность, которая сокращает уровень ошибки общей аппроксимации при запросах по диапазонам значений, принимая во внимание распространенность конкретных диапазонов внутри каждого бакета [46]. Имеется несколько исследований, показывающих превосходство каждого из общих методов над другим; это свидетельствует о том, что абсолютного победителя может и не существовать.
Два упомянутых основных подхода расширены и на случай многомерных бакетов с поддержкой в бакете минимального и максимального значений каждого измерения. При использовании предположения о непрерывности значений больше ничего и не требуется, но при использовании предположения о равномерности промежутков возникает проблема: существование каких (многомерных) значений предполагается в бакете? Если di - это число различных значений в атрибуте Xi , присутствующих в бакете, и vi '(k) - k-ое приближенное число в измерении i (полученное путем применения предположения о равномерности протяженности по этому измерению), то разумно предположить, что в бакете присутствуют все возможные комбинации <v1'(k1), …, vn '(kn )>, 1 ≤ ki ≤ di [66].
В одной интересной исследовательской работе в мир одномерных гистограмм было введено использование стержневой оценки (kernel estimation) [10] специально для работы с вещественными данными. Грубо говоря, в этом методе предлагается выбирать точки существенного изменения функции плотности вероятности в качестве границ бакетов (в духе, напоминающем ограничение разделения maxdiff), а затем применять традиционный метод стержневой оценки для аппроксимирования значений внутри каждого бакета. Это также обобщено на многомерный случай [31].
В зависимости от деталей изменения данных статические гистограммы рано или поздно расходятся с тем, что они должны аппроксимировать, и производимые на их основе оценки могут допускать все более серьезные ошибки. Когда это происходит, администраторы запускают пересчет гистограммы, и в этот момент старая гистограмма отбрасывается, а новая вычисляется заново. Важным аспектом статических гистограмм является сама стоимость вычисления, на которую, главным образом, влияет ограничение разделения. Для большинства таких ограничений (например, equi-sum, maxdiff, compressed) имеются эффективные и простые методы вычисления гистограмм. Однако это не так для ограничения, для которого показана его максимальная эффективность, т.е. для v-optimal; для этого случая стоимость вычисления в общем случае экспоненциально зависит от числа значений параметра источника. В этом отношении ключевым вкладом является предложение алгоритма, основанного на динамическом программировании, который определяет v-оптимальную гистограмму (для любых параметров разделения и источника) за время, квадратично зависимое от числа значений параметра источника и линейно зависимое от числа бакетов, что делает практичными и эти гистограммы [42]. Впоследствии было выполнено несколько работ (в основном теоретических), в которых предлагались алгоритмы, сокращающие время, требуемое для вычисления этих оптимальных гистограмм, сводя его, в конце концов, к линейному и достигая аналогичных усовершенствований и в отношение памяти [30]. Алгоритмы динамического программирования были также предложены для конструирования оптимальных гистограмм для (иерархических) запросов с диапазонами над OLAP-данными [44]. Для многомерного случая проблема определения оптимальной гистограммы NP-полна, поэтому было предложено несколько приблизительных методов [59].
В другой интересной работе были предложены алгоритмы для определения оптимальных наборов гистограмм (в противоположность к определению отдельных гистограмм), основанные на ожидаемой рабочей нагрузке [40]. Эта работа фокусируется на v-оптимальных гистограммах, но ее результаты равно применимы и к другим ограничениям разделения.
Однако даже при существовании эффективных алгоритмов вычисления статическим гистограммам свойственных возрастающие ошибки в промежутках между вычислениями. Более того, статические гистограммы вообще непригодны в среде потоков данных, поскольку отсутствует возможность сохранения поступающих данных и повторного их анализа. В связи с этим в нескольких работах предлагались различные подходы к поддержке динамических/адаптивных/самонастраивающихся гистограмм, которые изменяются при обновлении данных, оставаясь конкурентоспособными со статическими гистограммами. Среди этих работ мы отметим одну по поводу гистограмм, основанных на ограничениях разделения equi-depth и compressed [26], одну для v-оптимальных гистограмм [27] и одну для гистограмм, основанных на (линейных) сплайнах [46]. Имеется также исследовательская работа, фокусирующаяся на потоках данных, в которой поддерживается набросок (соединенного) распределения данных потока, на основе которого может быть сконструирована эффективная многомерная гистограмма [72]; в экспериментах использовались гистограммы STHoles, но в принципе метод можно применить и к другим классам диаграмм.
Другой подход к динамическому конструированию гистограмм, изучавшийся в прошлом, основывается на механизмах обратной связи запросов, в которых учитываются реальные размеры результатов запросов для динамического обновления гистограмм, так что обеспечиваемые ими оценки близки к действительности. По существу, подход состоит в адаптации гистограмм во время выполнения запросов, а не операций обновления. Основными представителями в этой категории являются ST-гистограммы [2] и происходящие от них гистограммы [11], в которых также используются усложненное правило разделения. Эти методы не зависят от конкретных характеристик исходных гистограмм, которые могут конструироваться любым образом, например они могут быть гистограммами с одинаковой глубиной. В придачу к их динамической природе, ключевым достоинством этих подходов является их низкая стоимость.
Эти работы обобщаются в системе LEO [70], поскольку в ней для обновления статистики используются размеры результатов намного более сложных запросов, включая запросы с соединениями и агрегацией, запросы с определенными пользователями функциями и т.д. Интересно, что LEO не обновляет статистику "по месту", а помещается информацию обратной связи в отдельные каталоги, которые используются в комбинации с исходными гистограммами во время проведения оценивания.
По отношению к пространственным данным канонический подход к двухмерным гистограммам не срабатывает, поскольку он предназначен для точечных данных и не расширяется для объектов, которые двумерны сами по себе. Кроме того, частота обычно не является характеристикой пространственных данных, поскольку пространственные объекты не повторяются в базе данных. Было предложено несколько интересных методов для решения дополнительных проблем, которые обычно связаны с правилом разделения, т.е. тем, как пространственные объекты группируются в бакеты. При использовании некоторых методов бакеты формируются путем обобщения традиционных гистограммных ограничений разделения, в то время как в других методах это делается с применением пространственных индексов (например, R-деревьев). Среди наиболее сложных методов можно выделить MinSkew Histogram [5], в котором пространство разделяется путем использования двоичного разделения (на каждом шаге пространство разделяется по одному измерению), что минимизирует общую пространственную скошенность всех бакетов. Дисперсия плотности объектов сохраняется в каждом бакете, так что в некотором смысле этот метод построен в духе v-оптимальных гистограмм. Интересной альтернативой является метод SQ-Histogram [3], в соответствии с которым пространство разделяется по правилу Quad-tree (являющемуся более ограничительным, чем произвольное бинарное разделение), и, в добавок к пространственной близости, принимается во внимание близость размеров и сложность многоугольников (число вершин), помещаемых в один и тот же бакет. Метод MinSkew Histogram был расширен для фиксации скорости движения объектов и сделан пригодным для аппроксимации и пространственно-временных данных [17].
Текущий интерес к XML, конечно, не мог не коснуться XML-аппроксимации, оценок размера результатов запросов и других родственных проблем. Полуструктурированная природа XML сама по себе не приспособлена к применению аппроксимации на основе гистограмм, поскольку отсутствует непосредственное многомерное пространство, которое может разбиваться на бакеты, и требуется формировать некоторые численные характеристики XML. В подходе StatiX [22] используется информация XML Schema для определения потенциальных источников структурного скашивания, а затем строятся одномерные гистограммы для большей части проблемных мест схемы, позволяя аппроксимировать распределения идентификаторов родительских узлов для различных элементов. В подходе XPathLearner [49] используются марковские гистограммы (первого порядка) [1], где частоты обходов всех путей длины 2 сохраняются в двумерных гистограммах. Измерения всегда представляют узлы `from' и `to' путей в графе XML; в первой гистограмме оба узла/измерения являются тегами XML, в то время как во второй гистограмме узел/измерение `from' является тегом XML, а узел/измерение `to' - это значение. При наличии достаточного объема памяти для всех пар тег-тег частоты поддерживаются точно, поскольку их очень немного. В отличие от этого, пары <тег, значение> помещаются в гистограмму, основанную на двумерной версии ограничения разделения "compressed" с использованием частоты как параметра источника. В другом подходе к оценке размеров результатов запроса к XML-данным также строится позиционная гистограмма на двухмерном пространстве, но здесь оба измерения прямо или косвенно связываются с нумерацией каждого узла в предопределенном порядке обхода графа XML [79]. Наконец, гистограммы используются также для цели аппроксимации XML в комбинации с другими структурами данных (или в их составе). Достаточно эффективным основанным на графах подходом является XSketch, в котором предпринимается попытка фиксировать как структурные характеристики файлов XML, так и характеристики значений [63, 64]. Гистограммы используются в различных частях XSketch для фиксации статистических корреляций элементов и значений в заданных окрестностях Xsketch-графа.
В дополнение к использованию для графов XML, предлагается также применять их для фиксации степеней узлов в графах общего вида, что может служить способом сравнения графов и оценки их близости [60].
Также имеется перспективное направление исследований, в котором гистограммы комбинируются с другими методами для обеспечения более высококачественных оценок, чем может обеспечить какой-либо метод в отдельности. В дополнение к нескольким таким комбинациям с применением взятия образцов, особенно интересный метод направлен на преодоление "проклятия размерности" (curse of dimensionality) путем определения решающих областей зависимости и независимости между измерениями в многомерных данных, фиксации их в статистической модели взаимодействий (например, нелинейной модели), которая затем может образовать основу для MHIST-гистограмм меньшей размерности, служащей для аппроксимации всего соединенного распределения данных [19].
Наконец, имеется очень интересное отступление от традиций, когда гистограммы строятся на базовых отношениях, и оценки распределений данных промежуточных результатов запросов получаются путем соответствующих манипуляций над этими гистограммами [12]. В этой работе обсуждается возможность поддержки гистограмм на результатах сложных запросов, что оказывается в некоторых случаях довольно эффективным. Для демонстрации предлагаемого подхода в работе используются основные гистограммы SQL Server (по существу, основанные на maxdiff - см. разд. 4), но основные результаты не зависят от конкретного класса гистограмм. Поскольку число потенциальных гистограмм сложных запросов гораздо больше числа гистограмм базовых отношений, соответственно более сложной является и проблема проектирования баз данных, когда решается, какие гистограммы следует конструировать. К счастью, для этих целей удается применить алгоритм, основанный на рабочей нагрузке.
В DB2 используются гистограммы класса compressed со значениями в качестве параметра разделения и частотой в качестве параметра источника [50]. Пользователи могут специфицировать число одноэлементных и неодноэлементных бакетов, желательных для наиболее частых значений, и, соответственно, часть гистораммы compressed с умолчанием от10 до 20. Отклонение от приведенного выше общего описания состоит в том, что в DB2 внутри неодноэлементных бакетов сохраняются накопленные частоты. Конструирование гистограммы основывается на образцах хранимых данных. В DB2 используется многомерная информация о мощности из индексов на составных атрибутах (когда они доступны) для получения количественных оценок зависимостей, которые могут существовать между атрибутами, и эти оценки используются в процессе оценивания селективности. При отсутствии таких оценок атрибуты считаются независимыми. Возможности обучения LEO [70] играют основную роль в том, как вся доступная информация используется для получения высококачественных оценок.
В Oracle все еще используются гистограммы с одинаковой шириной [78]. Основной подход к многомерной селективности похож на подход DB2 и основывается на использовании всякой информации из составных индексов. Однако, в дополнение к этому, поддерживаются средства динамического взятия образцов для получения при потребности "на лету" информации о зависимостях для сложных предикатов (в настоящее время это работает для предикатов ограничения и функций на одной таблице, а вариант для соединений будет доступен в следующем релизе системы). Также принимаются во внимание зависимости, существующие между атрибутами иерархий измерений куба при выполнении roll-up, и обеспечиваются оценки на соответствующем уровне иерархии. Наконец, в следующем релизе будут использоваться методы обучения для запоминания селективности обрабатывавшихся ранее предикатов и использования этих данных в будущем.
В SQL Server используются гистограммы maxdiff со значениями к качестве параметра разделения и, по существу, средней частоты (в каждом бакете) в качестве параметра источника [9]. Допускается до 199 бакетов, и внутри каждого бакета сохраняются частота максимального значения и (по существу) накопленная частота всех меньших значений. Гистограммы обычно конструируются на основе взятия образцов данных. Составные индексы используются в той же манере, что и в других системах, для получения многомерной информации о селективности.
Заметим, что во всех коммерческих СУБД реализуются строго одномерные гистограммы. За исключением применения некоторой второстепенной косвенной информации, в системах по-прежнему используется предположение о независимости значений атрибутов, и не используются многомерные гистограммы.
Сэмплинг не является прямым конкурентом гистограмм, поскольку это, главным образом, метод времени выполнения (runtime technique), и, кроме того, литература, посвященная сэмплингу, исключительно обширна, так что невозможно проанализировать соответствующие достижения при ограниченном объеме этой статьи. Однако мы должны подчеркнуть, что сэмплинг часто является методом, дополнительным по отношению к гистограммам, поскольку статические гистограммы (и даже некоторые виды динамических гистограмм) обычно конструируются на основе образцов исходных данных [15, 26, 62].
Имеется также несколько специализированных методов, которые были предложены для решения некоторых специфических оценочных проблем, и в этих областях конкурируют с гистограммами. В их число входят методы оценки селективности запросов "select-join" [71] и пространственных запросов [8], использования обратной связи с запросом для обновления хранимой аппроксимирующей кривую/параметрической информации для улучшения оценки селективности [16], оценки селективности алфавитно-цифровых/строковых данных в одномерных [43, 45] и многомерных [41, 77] средах, определения квантилей (quantile) [6, 53, 54] и их динамической поддержки с априорной гарантией [29], приблизительных ответов на агрегатные запросы с соединениями [4], запросы "select-join" и в общей среде оперативной агрегации [33, 32, 51], вычисления частот высокочастотных элементов в потоке [52] и другие. Несмотря на то, что, по сравнению с этими методами, гистограммы не обеспечивают оптимальные решения, общая эффективность и широкая применимость гистограмм позволяет сохранять им конкурентноспособность и в этих случаях.
всестороннее исследование, включающее несколько больше методов, чем упоминалось здесь. В [7] анализируется много методов и производится предварительное сравнение их применимости к различным типам данных. Этот отчет может служить хорошей стартовой точкой для верификации, экстраполяции и дальнейших исследований не только в отношении применимости, но и точных оценок накладных расходов на достижение требуемой эффективности, эффективности алгоритмов и других характеристик.
Как мы узнаем, что параметры для элементов схожи, так что мы можем объединить их в группу и представить их в терминах параметров? Это типичный вопрос традиционного распознавания образов [73], где до применения каких бы то ни было методов кластеризации имеется начальная стадия, на которой из огромного числа возможностей выбираются подходящие измерения элементов. Имеется несколько методов выполнения такого выбора, успех которых изменяется в зависимости от ситуации.
Однако следует подчеркнуть, что, в принципе, эти параметры не обязательно должны присутствовать среди исходных измерений элементов данных, представленных в проблеме, а могут быть их производными. Например, в нескольких аппроксимациях на основе гистограмм, описанных выше, для частот близость определяется напрямую, а для атрибутов это не так, поскольку внимание уделяется их протяженности. (Напомним также об успехе варианта с площадью в качестве параметра источника, которая является произведением частоты на протяженность.) Предполагается что частоты в бакете являются константой, и для их аппроксимации требуется хранить меньший объем информации, чем для значений атрибутов, относительно которых предполагается следование линейному правилу (равные протяженности). Следовательно, традиционная аппроксимация на основе гистограмм при предположениях о равномерном распределении и равномерной протяженности подразумевает кластеризацию пространства частот и протяженностей. Однако, в принципе, этот подход наилучшим образом годится не для всех распределений данных.
Для повышения точности гистограммных аппроксимаций не должно быть какого-либо фиксированного, предопределенного подхода к измерениям значений и частотам. Этот подход даже не обязан быть одним и тем же для разных бакетов. Гистограммы должны быть достаточно гибкими для использования оптимальной аппроксимации для каждого измерения в каждом бакете, такой аппроксимации, которая обеспечивает наилучшие оценки на основе наименьшего объема информации. Определение того, что из себя представляет эта оптимальная аппроксимация, является трудной задачей, для решения которой требуются дальнейшие исследования.
Мы полагаем, что иерархические гистограммы и вообще взаимодействие между аппроксимирующими структурами и индексами следует продолжать исследовать, поскольку, как показывает приводимый ниже анализ, несколько интересных проблем остаются неисследованными. Снова рассмотрим B+-дерево, узлы которого полностью заполнены. В этом случае корень дерева специфицирует разделение на бакеты домена атрибута, соответствующее гистограмме с одинаковой шириной, т.е. каждый бакет содержит примерно одинаковое число элементов. Аналогично, каждый узел дерева специфицирует разделение на бакеты с одинаковой шириной диапазона значений, к которым ведет этот узел.
Основной проблемой превращения B+-деревьев в гистограммы с одинаковой шириной является то, что эти гистограммы далеки от оптимальных при оценке селективности [67]. Гораздо эффективнее гистограммы классов v-optimal и maxdiff. Какие виды индексов следует применять, чтобы каждый узел представлял разделение на бакеты в соответствии с одним из этих правил? Ясно, что деревья были бы несбалансированными. Это сделало бы традиционный поиск в среднем менее эффективным. С другой стороны, другие виды поиска могли бы поддерживаться более эффективно. В частности, в системе, обеспечивающей приблизительные ответы на запросы, корень такого дерева обеспечивал бы более качественный ответ, чем корень соответствующего B+-дерева. Кроме того, система может перейти в поступательный режим, продвигаясь по дереву обычным образом и обеспечивая последовательность ответов с постоянным улучшением качества, в конце концов достигая листов и окончательного, точного ответа.
Возвращаясь к точным ответам на запросы, заметим, что обычно индексы строятся в предположении, что все значения в диапазонах значений одинаково важны. Поэтому важно иметь сбалансированное дерево. Однако часто бывает так, что разные значения обладают разной важностью и разной частотой в ожидаемой рабочей нагрузке [46]. Если эта частота запросов или некоторый другой подобный параметр используется в соединении с развитыми гистограммными правилами разделения на бакеты, то могут генерироваться некоторые очень интересные деревья, обеспечивающие намного лучшую среднюю эффективность поиска, чем у B+-деревьев.
Из всего этого ясно, что взаимодействие между гистограммами и индексами предоставляет ряд благоприятных возможностей, но также выдвигает и несколько технических проблем, которые нуждаются в исследовании. Специальное внимание требуется изучению соотношения плюсов и минусов иерархических гистограмм, являющихся сбалансированными деревьями с разделением на бакеты одинаковой ширины, и несбалансированных иерархических гистограмм с более совершенным разделением на бакеты. Нельзя также исключать возможность некоторых абсолютно новых структур, которые обеспечивали бы еще лучшие средние характеристики, объединяя лучшие черты данных двух миров.
Вторым человеком, который существенно способствовал определению границ наших исследований в области гистограмм, является Виши Пусала (Vishy Poosala). Будучи аспирантом Висконсинского университете, Виши обратился к исходным результатам по "сериальным гистограммам", глубоко в них погрузился и распределил их во многих направлениях. Эта работа в конце концов привела нас к нескольким интересным результатам, которые сыграли важную роль в развитии успешного применения гистограмм. Спасибо Виши за долгую и плодотворную совместную работу как до, так и после его защиты диссертации.
По поводу данной статьи мы хотели бы поблагодарить Миноса Гарофалакиса (Minos Garofalakis), Неоклиса Полизотиса (Neoklis Polyzotis) и снова Виши Пусала за несколько полезных советов и проверку того, что ошибка в аппроксимации истории гистограмм является небольшой.
Перевод: Сергей Кузнецов
| [1]назад | Aboulnaga A., Alameldeen A., Naughton J.: Estimating the Selectivity of XML Path Expressions for Internet Scale Applications. VLDB Conf. (2001) 591-600 |
| [2]назад | Aboulnaga A., Chaudhuri S.: Self-tuning Histograms: Building Histograms Without Looking at Data. SIGMOD Conf. (1999) 181-192 |
| [3]назад | Aboulnaga A., Naughton J.: Accurate Estimation of the Cost of Spatial Selections. ICDE 2000 123-134 |
| [4]назад | Acharya S., Gibbons P., Poosala V., Ramaswamy S.: Join Synopses for Approximate Query Answering. SIGMOD Conf. (1998) 275-286 |
| [5]назад | Acharya S., Poosala V., Ramaswamy S.: Selectivity Estimation in Spatial Databases. SIGMOD Conf. (1999) 13-24 |
| [6]назад | Alsabti K., Ranka S., Singh V.: A One-Pass Algorithm for Accurately Estimating Quantiles for Disk-Resident Data. VLDB Conf. (1997) 346-355 |
| [7]назад | Barbar_a D., et al.: The New Jersey Data Reduction Report. Data Engineering Bulletin 20:4 (1997) 3-45 |
| [8]назад | Belussi A., Faloutsos C.: Estimating the Selectivity of Spatial Queries Using the `Correlation' Fractal Dimension. VLDB Conf. (1995) 299-310 |
| [9]назад | Blakeley J., Kline N.: personal communication. (2003) |
| [10] назад | Blohsfeld B., Korus D., Seeger, B.: A Comparison of Selectivity Estimators for Range Queries on Metric Attributes. SIGMOD Conf. (1999) 239-250 |
| [11]назад | Bruno N., Chaudhuri S., Gravano L.: STHoles: A Multidimensional Workload-Aware Histogram. SIGMOD Conf. (2001) 294-305 |
| [12]назад | Bruno N., Chaudhuri S., Gravano L.: Exploiting Statistics on Query Expressions for Optimization SIGMOD Conf. (2002) 263-274 |
| [13]назад | Buccafurri F., Rosaci D., Sacc_a D.: Improving Range Query Estimation on Histograms. ICDE (2002) 628-238 |
| [14]назад | Chakrabarti K., Garofalakis M., Rastogi R., Shim K.: Approximate Query Processing Using Wavelets. VLDB Journal 10:2-3 (2001) 199-223 |
| [15]назад | Chaudhuri S., Motwani R., Narasayya V.: Random Sampling for Histogram Construction: How Much is Enough? SIGMOD Conf. (1998) 436-447 |
| [16]назад | Chen C., Roussopoulos N.: Adaptive Selectivity Estimation Using Query Feedback. SIGMOD Conf. (1994) 161-172 |
| [17]назад | Choi Y.-J., Chung C.-W.: Selectivity Estimation for Spatio-Temporal Queries to Moving Objects. SIGMOD Conf. (2002) 440-451 |
| [18]назад | De Boor C.: A Practical Guide to Splines. Springer (1994) |
| [19]назад | Deshpande A., Garofalakis M., Rastogi R.: Independence is Good: Dependency-Based Histogram Synopses for High-Dimensional Data. SIGMOD Conf. (2001) 199-210 |
| [20]назад | Donjerkovic D., Ramakrishnan R.: Probabilistic Optimization of Top N Queries. VLDB Conf. (1999) 411-422 |
| [21]назад | Flickner M., et al.: Query by Image and Video Content: The QBIC System. IEEE Computer 28:9 (1995) 23-32 |
| [22]назад | Freire J., Haritsa J., Ramanath M., Roy P., Simeon J.: StatiX: Making XML Count. SIGMOD Conf. (2002) 181-191 |
| [23]назад | Furtado P., Madeira H.: Summary Grids: Building Accurate Multidimensional Histograms. DASFAA Conf. (1999) 187-194 |
| [24]назад | Garofalakis M., Gibbons P.: Wavelet Synopses with Error Guarantees. SIGMOD Conf. (2002) 476-487 |
| [25]назад | Getoor L., Taskar B., Koller D.: Selectivity Estimation Using Probabilistic Models. SIGMOD Conf. (2001) 461-472 |
| [26]назад | Gibbons P., Matias Y., Poosala V.: Fast Incremental Maintenance of Approximate Histograms. VLDB Conf. (1997) 466-475 |
| [27]назад | Gilbert A., Guha S., Indyk P., Kotidis Y., Muthukrishnan S., Strauss M.: Fast, Small-Space Algorithms for Approximate Histogram Maintenance. ACM STOC (2002) 389-398 |
| [28]назад | Gilbert A., Kotidis Y., Muthukrishnan S., Strauss M.: Surfing Wavelets on Streams: One-Pass Summaries for Approximate Aggregate Queries. VLDB Conf. (2001) 79-88 |
| [29]назад | Gilbert A., Kotidis Y., Muthukrishnan S., Strauss M.: How to Summarize the Universe: Dynamic Maintenance of Quantiles. VLDB Conf. (2002) 454-465 |
| [30]назад | Guha S., Indyk P., Muthukrishnan S., Strauss M.: Histogramming Data Streams with Fast Per-Item Processing. ICALP Conf. (2002) 681-692 |
| [31]назад | Gunopulos D., Kollios G., Tsotras V., Domeniconi C.: Approximating Multi-Dimensional Aggregate Range Queries Over Real Attributes. SIGMOD Conf. (2000) 463-474 |
| [32]назад | Haas P., Hellerstein J.: Ripple Joins for Online Aggregation. SIGMOD Conf. (1999) 287-298 |
| [33]назад | Hellerstein J., Haas P., Wang H.: Online Aggregation. SIGMOD Conf. (1997) 171-182 |
| [34]назад | Ioannidis Y.: Universality of Serial Histograms. VLDB Conf. (1993) 256-267 |
| [35]назад | Ioannidis Y.: Approximations in Database Systems. ICDT (2003) 16-30 |
| [36]назад | Ioannidis Y., Christodoulakis S.: On the Propagation of Errors in the Size of Join Results. SIGMOD Conf. (1991) 268-277 |
| [37]назад | Ioannidis Y., Christodoulakis S.: Optimal Histograms for Limiting Worst-Case Error Propagation in the Size of Join Results. ACM TODS 18:4 (1993) 709-748 |
| [38]назад | Ioannidis Y., Poosala V.: Balancing Histogram Optimality and Practicality for Query Result Size Estimation. SIGMOD Conf. (1995) 233-244 |
| [39]назад | Ioannidis Y., Poosala V.: Histogram-Based Approximation of Set-Valued Query-Answers. VLDB Conf. (1999) 174-185 |
| [40]назад | Jagadish H. V., Jin H., Ooi B. C., Tan K.-L.: Global Optimization of Histograms. SIGMOD Conf. (2001) 223-234 |
| [41]назад | Jagadish H. V., Kapitskaia O., Ng R., Srivastava D.: Multi-Dimensional Substring Selectivity Estimation. VLDB Conf. (1999) 387-398 |
| [42]назад | Jagadish H. V., Koudas N., Muthukrishnan S., Poosala V., Sevcik K., Suel T.: Optimal Histograms with Quality Guarantees. VLDB Conf. (1998) 275-286 |
| [43]назад | Jagadish H. V., Ng R., Srivastava D.: Substring Selectivity Estimation. PODS Symposium (1999) 249-260 |
| [44]назад | Koudas N., Muthukrishnan S., Srivastava D.: Optimal Histograms for Hierarchical Range Queries. PODS Symposium (2000) 196-204 |
| [45]назад | Krishnan P., Vitter J., Iyer B.: Estimating Alphanumeric Selectivity in the Presence of Wildcards. SIGMOD Conf. (1996) 282-293 |
| [46]назад | König A., Weikum G.: Combining Histograms and Parametric Curve Fitting for Feedback-Driven Query Result-Size Estimation. VLDB Conf. (1999) 423-434 |
| [47]назад | Kooi R.: The Optimization of Queries in Relational Databases. PhD Thesis, Case Western Reserve University (1980) |
| [48]назад | Lee J.-H., Kim D.-H., Chung C.-W.: Multi-Dimensional Selectivity Estimation Using Compressed Histogram Information. SIGMOD Conf. (1999) 205-214 |
| [49]назад | Lim L., Wang M., Padmanabhan S., Vitter J., Parr R.: XPathLearner: An On-Ling Self-Tuning Markov Histogram for XML Path Selectivity Estimation. VLDB Conf. (2002) 442-453 |
| [50]назад | Lohman G.: personal communication. (2003) |
| [51]назад | Luo G., Ellmann C., Haas P., Naughton J.: A Scalable Hash Ripple Join Algorithm. SIGMOD Conf. (2002) 252-262 |
| [52]назад | Manku G. S., Motwani R.: Approximate Frequency Counts over Data Streams. VLDB Conf. (2002) 346-357 |
| [53]назад | Manku G. S., Rajagopalan S., Lindsay B.: Approximate Medians and Other Quantiles in One Pass and with Limited Memory. SIGMOD Conf. (1998) 426-435 |
| [54]назад | Manku G. S., Rajagopalan S., Lindsay B.: Random Sampling Techniques for Space Efficient Online Computation of Order Statistics of Large Datasets. SIGMOD Conf. (1999) 251-262 |
| [55]назад | Marshall A., Olkin L.: Inequalities: Theory of Majorization and its Applications. Academic Press (1986) |
| [56]назад | Matias Y., Vitter J., Wang M.: Wavelet-Based Histograms for Selectivity Estimation. SIGMOD Conf. (1998) 448-459 |
| [57]назад | Matias Y., Vitter J., Wang M.: Dynamic Maintenance of Wavelet-Based Histograms. VLDB Conf. (2000) 101-110 |
| [58]назад | Muralikrishna M., DeWitt D.: Equi-Depth Histograms for Estimating Selectivity Factors for Multi-Dimensional Queries. SIGMOD Conf. (1988) 28-36 |
| [59]назад | Muthukrishnan S., Poosala V., Suel T.: On Rectangular Partitionings in Two Dimensions: Algorithms, Complexity, and Applications. ICDT (1999) 236-256 |
| [60]назад | Papadopoulos A., Manolopoulos Y.: Structure-Based Similarity Search with Graph Histograms. DEXAWorkshop (1999) 174-179 |
| [61]назад | Pass G., Zabih R.: Comparing Images Using Joint Histograms. Multimedia Systems 7 (1999) 234-240 |
| [62]назад | Piatetsky-Shapiro G., Connell C.: Accurate Estimation of the Number of Tuples Satisfying a Condition. SIGMOD Conf. (1984) 256-276 |
| [63]назад | Polyzotis N., Garofalakis M.: Statistical Synopses for Graph-Structured XML Databases. SIGMOD Conf. (2002) 358-369 |
| [64]назад | Polyzotis N., Garofalakis M.: Structure and Value Synopses for XML Data Graphs. VLDB Conf. (2002) 466-477 |
| [65]назад | Poosala V., Ioannidis Y.: Estimation of Query-Result Distribution and its Application in Parallel-Join Load Balancing. VLDB Conf. (1996) 448-459 |
| [66]назад | Poosala V., Ioannidis Y.: Selectivity Estimation Without the Attribute Value Independence Assumption. VLDB Conf. (1997) 486-495 |
| [67]назад | Poosala V., Ioannidis Y., Haas P., Shekita E.: Improved Histograms for Selectivity Estimation of Range Predicates. SIGMOD Conf. (1996) 294-305 |
| [68]назад | Sitzmann I., Stuckey P.: Improving Temporal Joins Using Histograms. DEXA Conf. (2000) 488-498 |
| [69]назад | Stigler S.: The History of Statistics: The Measurement of Uncertainty before 1900. Harvard University Press (1986) |
| [70]назад | Stillger M., Lohman G., Markl V., Kandil M.: LEO - DB2's LEarning Optimizer. VLDB Conf. (2001) 19-28 |
| [71]назад | Sun W., Ling Y., Rishe N., Deng Y.: An Instant and Accurate Size Estimation Method for Joins and Selection in a Retrieval-Intensive Environment. SIGMOD Conf. (1993) 79-88 |
| [72]назад | Thaper N., Guha S., Indyk P., Koudas N.: Dynamic Multidimensional Histograms. SIGMOD Conf. (2002) 428-439 |
| [73]назад | Theodoridis, S., Koutroumbas K.: Pattern Recognition. Academic Press, 2nd edition (2003) |
| [74]назад | Tufte E.: The Visual Display of Quantitative Information. Graphics Press (1983) |
| [75]назад | Vitter J., Wang M.: Approximate Computation of Multidimensional Aggregates of Sparse Data Using Wavelets. SIGMOD Conf. (1999) 193-204 |
| [76]назад | Vitter J., Wang M., Iyer B.: Data Cube Approximation and Histograms via Wavelets. CIKM Conf. (1998) 96-104 |
| [77]назад | Wang M., Vitter J., Iyer B.: Selectivity Estimation in the Presence of Alphanumeric Correlations. ICDE (1997) 169-180 |
| [78]назад | Witkowski A.: personal communication. (2003) |
| [79]назад | Wu Y., Patel J., Jagadish H. V.: Using Histograms to Estimate Answer Sizes for XML Queries. Information Systems 28:1-2 (2003) 33-59 |