Классика баз данных - статьи
Оптимальный параметр разделения
После нескольких лет пассивности по отношению к теме гистограмм интерес возбудился в контексте изучения того, как исходные ошибки в статистике, поддерживаемой системой баз данных, распространяются на оценки результатов сложных запросов []. В частности, было показано, что при некоторых, достаточно общих условиях в худшем случае ошибки в оценке размера результата запроса распространяются экспоненциально (от числа соединений), что устраняет какую-либо надежду на высококачественные оценки для сложных запросов с несколькими соединениями. Первые результаты, которые вели к новым типам гистограмм, были получены при попытке получения статистики, которая была бы оптимальна при минимизации/сдерживании распространения ошибок в размере результата соединений []. Основной использованный математический аппарат был позаимствован из теории мажорирования []. Внимание в основном уделялось ограниченному классу запросов с эквисоединениями, т.е. запросов с одним или несколькими соединениями, в которых в соединении участвует только один атрибут каждого отношения (в более общей постановке, между каждой парой атрибутов соединения каждого отношения существует функциональная зависимость "1-1"). Для этого класса запросов в предположении наличия точного знания множества значений было формально доказано, что оптимальная гистограмма является сериальной с частотой в качестве параметра разделения.
