Классика баз данных - статьи
Конкурентная модель
Предположим, что подзапрос можно выполнять с использованием двух альтернативных стратегий s1 и s2, и, по крайней мере, у оценки стоимости одной из них (например, у s1) имеется гиперболическое распределение. При достаточно высокой скошенности гиперболы существенная вероятность стоимости концентрируется в небольшом интервале [0; c] вблизи нулевой стоимости. Если в начале вычисления подзапроса всегда выполняется стратегия s1, пока не будет исчерпана стоимость или подзапрос не будет успешно выполнен, то при небольшой начальной инвестиции ?c существенная часть случаев быстрого завершения s1полностью исчерпывается. Если у обеих стратегий имеется гиперболическое распределение стоимости, то наилучшим способом действия является параллельный запуск s1 и s2 с пропорциональной скоростью продвижения стоимости с переключением в некоторой точке c на единую стратегию s1 или s2 в зависимости от того, у какой из них меньше оцененная средняя стоимость.
Выше мы описали модель прямой конкуренции для выполнения двух альтернативных стратегий. При оптимальном выборе c, определенном в [Ant91], прямая конкуренция гарантирует организацию вычисления s1/s2 с наименьшей средней стоимостью.
Стратегии выполнения запросов часто содержат две и большее число фаз, например, (фаза 1) сканирование индекса обеспечивает множество ID записей, (2a) это множество сортируется, (2b) записи данных выбираются в порядке физического расположения, и каждая страница считывается только один раз. В этом примере стоимость фазы 1 намного меньше общей стоимости фазы 2. Кроме того, при знании множества ID можно точно оценить стоимость фазы 2. Если доступны два индекса, может быть организована конкуренция между применениями описанной стратегии к двум индексам со временем завершения параллельного выполнения, определяемым эксраполированной стоимостью обеих фаз стратегии. По сравнению с прямой конкуренцией, эта двухфазная конкурений является намного более эффективной, поскольку стоимость ее «решающей» первой фазы составляет лишь долю от общей стоимости стратегии.
