Эффективность

KazaX
Дата: 18.11.2008 03:21:22
Привет!
Не поможешь?

SELECT R.A, S.C
FROM R, S
WHERE R.B = S.B

не подскажете как должен выглядить псевдокод для вышеприведенного запроса , для реализации - block nested loop.
Предположим
блоки, считывают с диска по 50 КБ,
R имеет 10^6 записей и занимает 100 МБ,
S имеет 10^5 записей и занимает 200 МБ,
Кэш содержит два блока.
Необходимо оценить требуемый i/o для наивного соединения, и block nested loop. Какой внешнии луп будет эффективнee {на R или S }?

Спасибо
Elic
Дата: 18.11.2008 08:41:42
KazaX
для наивного соединения
Милый детский бред
ITGOOD
Дата: 18.11.2008 15:33:37
Псевдокод примерно такой:

Для каждой записи из таблицы R
Цикл
   Для каждой записи из таблицы S
   Цикл
     Если R.B=S.B тогда
        Добавить найденное соединение в выходной буфер;
     Конец Если;
   Конец Цикла;
Конец Цикла;

Соответственно таблица S будет прочитана столько раз, сколько строк в таблице R.
Эффективность i/o цикла можно посчитать ориентировочно из числа необходимых для соединения строк:
Пусть в таблице R - x строк, а в таблице S - y строк.
Eff=x*y+x;
Из формулы видно, что чем меньше число строк в таблице R, тем меньше строк надо будет прочитать.
Разница при выборе ведущей таблицы составит x-y. Т.е. если R - 100 Мб, а S - 200 МБ, то: при ведущей таблице S будет прочитано на 100 МБ больше, чем при ведущей таблице R.

P.S. Это лично мое мнение, которое может отличаться от более авторитетных источников.
Я и ёжик
Дата: 18.11.2008 16:21:46
ITGOOD

Соответственно таблица S будет прочитана столько раз, сколько строк в таблице R.
Эффективность i/o цикла можно посчитать ориентировочно из числа необходимых для соединения строк:
Пусть в таблице R - x строк, а в таблице S - y строк.
Eff=x*y+x;
Из формулы видно, что чем меньше число строк в таблице R, тем меньше строк надо будет прочитать.
Разница при выборе ведущей таблицы составит x-y. Т.е. если R - 100 Мб, а S - 200 МБ, то: при ведущей таблице S будет прочитано на 100 МБ больше, чем при ведущей таблице R.

P.S. Это лично мое мнение, которое может отличаться от более авторитетных источников.

Вроде начало правильное, а дальше хрень какая то.
Мы читаем не строками, однако.

Внешнюю таблицу читаем один раз, внутреннюю столько раз сколько строк во внешней, читаем целиком, я так понял индексов нет.

Eff = Size(Внешн) + Rows(Внешн)*Size(Внутр)

Eff(R ведущая) = Size(R) + Rows(R)*Size(S) = 100 + 1000000*200 =200 000 100
Eff(S ведущая) = Size(S) + Rows(S)*Size(R) = 200 + 100000*100 = 10 000 000

При ведущей таблице S будет прочитано почти на 190 Мб меньше.
Я и ёжик
Дата: 18.11.2008 16:24:55
Я и ёжик

При ведущей таблице S будет прочитано почти на 190 Мб меньше.

Наврал :), более чем на 190000000 Мб
Я и ёжик
Дата: 18.11.2008 16:29:58
Блин, возьмите меня в школу обратно...
Я и ёжик

Eff = Size(Внешн) + Rows(Внешн)*Size(Внутр)

Eff(R ведущая) = Size(R) + Rows(R)*Size(S) = 100 + 1000000*200 =200 000 100
Eff(S ведущая) = Size(S) + Rows(S)*Size(R) = 200 + 100000*100 = 10 000 200

При ведущей таблице S будет прочитано на 189 999 900 Мб меньше.
Я и ёжик
Дата: 18.11.2008 16:31:18
Ничего, что я тут в циферки поиграю?
DВА
Дата: 18.11.2008 16:58:02
Я и ёжик
Ничего, что я тут в циферки поиграю?

ничего, продолжайте :)
ITGOOD
Дата: 18.11.2008 17:06:02
Я и ёжик
Eff = Size(Внешн) + Rows(Внешн)*Size(Внутр)

Eff(R ведущая) = Size(R) + Rows(R)*Size(S) = 100 + 1000000*200 =200 000 100
Eff(S ведущая) = Size(S) + Rows(S)*Size(R) = 200 + 100000*100 = 10 000 000


Начало верное, но в цифрах чушь полная :)

Надо считать либо в строках, либо в блоках. Умножение строк на размер таблицы смысла не несет.
Если перефразировать мою вышеприведенную формулу, то
x=Rows(R)
y=Rows(S)
либо в мегабайтах (С этой точки зрения мы представляем таблицу - как некий поток данных в блоках либо в строках. Согласитесь, что если мы прочитали блок - то можно считать, что прочитали и все строки в этом блоке). Можно перефразировать и так:
x=Size(R)
y=Size(S)

Приходим к формулам:
Eff(x)=x+x*y
Eff(y)=y+x*y

Множитель x*y в формулах одинаковый. Вычтем из первой формулы вторую, получим:
Eff(x)-Eff(y)=x-y
О чем я и написал в предыдущем посте.

Следует обратить внимание, что если обе таблицы уместятся в оперативной памяти, то чтение с жесткого диска для каждой из таблиц произойдет один раз. В этом случае разницей x-y можно пренебречь, поскольку чтение в оперативной памяти происходит на три порядка быстрее, чем с жесткого диска. Т.е. разница составит приблизительно ((x-y)/1000)*скорость чтения с диска. Если каждый раз тупо читать с диска, то разница будет (x-y)*скорость чтения с диска.

Получается, что разница при выборе одной или другой таблицы будет приблизительно в пределах:
(x-y)/1000 < Eff(x,y) < x-y

Какими порциями при этом читается таблица - по одной строке или по 50 Kb - не принципиально.
ITGOOD
Дата: 18.11.2008 17:12:22
Неожиданно для себя, открыл, что формулы
Eff(x)=x+x*y
Eff(y)=y+x*y
верны только для счета по строкам.
При чтении блоками, формулы другие :)

Однако результат Eff(x)-Eff(y) будет тем же.