Классика баз данных - статьи
Оптимизация поиска
Первой проблемой является оптимизация поиска. В простой программе, показанной на рис. 1, тратится время, пропорциональной числу служащих, хотя лишь для немногих из них фамилия будет начинаться с заданного префикса. Для улучшения этого алгоритма могут применяться традиционные методы оптимизации баз данных, основанные на использовании индекса. Это может существенно сократить время выполнение, которое станет пропорциональным числу служащих с фамилиями, соответствующими первому условию.
Явные индексы (P1). Распространенным методом является изменение порядка подопераций, таких как итерирование и проверка условия. Так, оптимизатор запросов может использовать индекс для вычисления множества идентификаторов записей, удовлетворяющих условию, а затем найти соответствующие данные путем поиска этих идентификаторов во втором индексе. Этот аспект плана иллюстрируется на рис. 4, где эта оптимизация применяется к исходному Java-коду.
Проверка префикса реализуется путем поиска по индексу: метод match возвращает итератор над множеством элементов индекса, соответствующих первому условию. Затем для нахождения данных о служащих используется эффективный индекс, отображающий идентификаторы записей в значения записей. Если большинство фамилий не начинается с заданного префикса, этот метод будет гораздо эффективнее линейного поиска. Явное программирование с использованием индексов поддерживается в Exodus [] и Ontos [].
void printInfo(String prefix) { for (IndexItem l in employeeNameIndex.match(“S”)) { Employee e = employeeID_Index.lookup(l.ID); if (e.salary > managerID_Index.lookup(e.managerID).salary) { print( e.name ); print( e.salary ); Department d = departmentID_Index.lookup(e.deptID); print( d.name ); } } }
Рис. 4. Оптимизированная выдача на печать информации о служащих
Если такие оптимизации должны выполняться вручную, производительность программиста существенно понижается, поскольку даже при незначительном изменении исходного неоптимизированного кода, например, при добавлении в оператор if дополнительного условия, может потребоваться значительное переписывание оптимизированного кода.
