Классика баз данных - статьи
к параллельной оценке альтернативных стратегий,
Аналогичный подход к параллельной оценке альтернативных стратегий, в котором извлекается выгода от сокращения неопределенности, предлагается в [Roy91]. Сокращение неопределенности в этом подходе достигается путем рандомизации выполнения стратегии и использования части промежуточных результатов в качестве случайных образцов для вычисления оценок стоимости. В сравнении с конкурентной моделью рандомизированне выполнение не покрывает несколько важных случаев:
- Из подзапроса запрашивается n записей при n < мощности результата – накакие рандомизация или взятие обзазцов не могут улучшить знание n, если n неизвестно, например, если n поставляется пользовательским приложением во время выполнения.
- Некоторые стратегии, такие как слияние с использованием индексов, обычно реализуются с использованием непрерывного сканирования, рандомизация которого зарушила бы порядок слияния.
- Короткие подзапросы, при выполнении которых производится небольшой объем ввода-вывода, взяли бы на себя слишком большую долю накладных расходов рандомизации.
Мы рассматривали возможность использования рандомизации в Rdb для ускорения конкурентного сокращения неопределенности в тех случаях, когда рандомизация применима. К сожалению, в соответствии с нашими экспериментами, рандомизированный индексный доступ, основанный на методе принятия/отклонения привел к трем тысячам отклонений на один спуск по B-дереву для таблицы с 1M записей. К счастью, мы решили эту проблему, введя псевдоупорядоченные B-деревья [Ant92], так что с накладными расходами в 1% на поддержание приблизительных мощностей ветвей скорость отклонения была сокращена до 50%. В дополнение к этому, для индексных диапазонов единственный спуск по псевдоупорядоченному дереву до наименьшей ветви, покрывающей диапазон, может иметь точность приблизительных мощностей, достаточную для принятия решения о переключении стратегии.
Параллельное выполнение альтернативных стратегий следует использовать с предосторожностями с средах с частыми обновлениями, потому что при этом устанавливается не минимально необходимое число блокировок.Пилотное взятие образцов без блокировок, при котором при встрече заблокированного объекта к нему повторяются попытки обращения, может разрешить некоторые неопределенности и сократить число альтернатив до начала реальной обработки В Rdb мы производим пилотное взятие образцов путем одиночного спуска по B-дереву к ветви, содержащей диапазон.
