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