Развитие идей и приложений реляционной СУБД System R


Оптимизация в System R - часть 4


Если в V2 места уже нет, и значение поля соединения кортежа s меньше значения поля кортежа, находящегося в V2, с наибольшим значением поля соединения, то все кортежи с таким значением поля соединения удаляются из V2, а s - заносится. В противном случае s не заносится в V2. После окончания формирования V2 (завершения сканирования S) сканируется отношение R, и поочередно выбираются кортежи. Если очередной кортеж r удовлетворяет предикату ограничения из условия выборки, V2 просматиривается на предмет наличия кортежей с таким же, как у r, значением полей соединения. Если такие кортежи находятся, производится соединение кортежа r с каждым из них, и формируется очередная порция результирующего отношения. Если при формировании V2 не все кортежи отношения S, удовлетворяющие предикату ограничения, поместились в эту область, производится повторное сканирование отношения S, и формируется новое множество V2, в которое включатся только кортежи со значением полей соединения большим максимального значения поля соединения кортежей в предыдущем варианте V2. Снова сканируется R, и процесс повторяется. Для организации структуры V2 можно использовать двоичные деревья, хэш-таблицы и т.д.

4) Если существуют индексы для отношений R и S на полях соединения и для всех предикатов ограничения, то с использованием индексов ограничения формируются два списка tid'ов кортежей отношений R и S, удовлетворяющих предикатам ограничения. Эти два списка сортируются и заносятся в файлы R1 и S1. Путем параллельного просмотра индексов на полях соединения R и S находятся пары tid'ов кортежей, являющихся участниками соединения (без учета ограничений). Для каждой такой пары (tid1, tid2) проверяется, присутствуют ли tid1 в R1, а tid2 - в S1 (т.е. удовлетворяют ли кортежи предикатам ограничения). Если эти условия выполнены, соответствующие кортежи читаются и соединяются, образуя очередной кортеж результирующего отношения.

Заметим, что в целях упрощения изложения мы не упомянули о том, что в методах 1-3 при выборке кортежа во временную память для сокращения ее объема производится проекция кортежей на те поля, которые упомянуты в списке выборки запроса, плюс поля соединения.




Начало  Назад  Вперед



Книжный магазин