Классика баз данных - статьи
Новые ограничения разделения
Результаты, показывающие оптимальность использования частоты в качестве параметра разделения, оставляли открытыми два важных вопроса. Во-первых, какие ограничения разделения являются наиболее эффективными, т.е. какие разбиения на бакеты среди всех возможных разбиений на основе частоты? Во-вторых, какие гистограммы являются оптимальными, если множество значений не поддерживается точно, а некоторым образом аппроксимируется?
Ответ на первый вопрос поступил в форме v-оптимальных (v-optimal) гистограмм, которые разделяют распределение данных таким образом, что (грубо говоря) минимизируется дисперсия значений параметра источника внутри каждого бакета [].
К сожалению, аналитический ответ на второй вопрос отсутствует, но большое число экспериментов привело к формированию пространства характеристик гистограмм, которое мы используем в качестве основы обсуждения в данной статье (разд. ) []. В дополнение к ограничениям разделения equi-sum и v-optimal было введено несколько новых возможных ограничений, целью которых, аналогично v-optimal, являлось избежание группировки в одном бакете слишком разных значений параметра источника. Среди этих ограничений мы выделяем ограничение maxdiff, которое устанавливает границы бакетов между соседними значениями параметра источника (в порядке параметра разделения) с наибольшей разностью, и compressed, которое помещает наибольшие значения источника в одиночные бакеты и разделяет оставшиеся значения в стиле equi-sum. В целом, было показано, что новые ограничения разделения (т.е. v-optimal, maxdiff и compressed) являются наиболее эффективными при сдерживании ошибок в оценках размеров результатов запросов.
В этой же работе было указано несколько возможностей для параметров разделения и источника, т.е. значение, протяженность, частота, площадь, накопленная частота и т.д., где частота и площадь являются наилучшими параметрами источника. Интересно, что наилучшим параметром разделения оказалось значение, а не частота, как должно было бы следовать из исходных результатов по поводу оптимальности; это означает, что если значения не являются точно известными, то наличие бакетов с перекрывающимися диапазонами значений не окупается для запросов по диапазону значений.
Наиболее эффективные из этих гистограмм реально внедрены в промышленные продукты (см. разд. ). Кроме того, в дополнение к оценке селективности для различных реляционных и не реляционных запросов эти гистограммы оказались очень эффективными и при обеспечении приблизительные ответы на запросы [].
После определения упомянутого пространства гистограмм было проведено несколько исследовательских работ, в которых изучались одна или несколько характеристик пространства и предлагались альтернативные, усовершенствованные подходы. Ниже мы в отдельных подразделах кратко описываем наиболее значимые части работ, посвященных каждой из этих характеристик. За исключением специально отмечаемых случаев, речь идет об одномерных гистограммах.
