Здравствуйте, извините если спросил не в той ветке, просто не нашел более подходящей.
Суть вопроса: Предположим у нас есть обычная база данных книжного магазина: таблица книги, таблица авторы, таблица авторство(таблица соответствий авторов и книг).
Скажем нам надо найти авторов книги с таким-то названием. И мы имеем 2 пути это сделать: либо select ... from books, authors, authorship where (...), либо сделать это 2 вложенными запросами(сначало ID нужной книги, потом ID нужных авторов, потом их самих) Какой из вариантов лучше?

Насколько я понимаю предпочтительней 1 вариант, но почему?
Пусть у нас будут те самые 3 таблицы. Пусть будет всего 1000 книг и у каждой всего лишь один автор. Получим по 1000 элементов в каждой таблице. Когда мы пишем select ... from books, authors, authorship мы получаем одну большую таблицу в которой сгенерированные всевозможные комбинации строк из 3 таблиц. То есть таблица с 1000^3 элементов, то есть в худшем случае просмотрим 1000^3 элементов.
А в случае со вложенными запросами мы в худшем случае просмотрим 1000 элементов в первой таблице, столько же во 2 и в 3. То есть 3000. Я понимаю, что будут накладные расходы на вызов отдельного запроса, но разве они будут насколько критичными?
Заранее спасибо!

Здравствуйте, 80LevelElf, Вы писали:

LE>Здравствуйте, извините если спросил не в той ветке, просто не нашел более подходящей.
LE>Суть вопроса: Предположим у нас есть обычная база данных книжного магазина: таблица книги, таблица авторы, таблица авторство(таблица соответствий авторов и книг).
LE>Скажем нам надо найти авторов книги с таким-то названием. И мы имеем 2 пути это сделать: либо select ... from books, authors, authorship where (...), либо сделать это 2 вложенными запросами(сначало ID нужной книги, потом ID нужных авторов, потом их самих) Какой из вариантов лучше?

LE>Насколько я понимаю предпочтительней 1 вариант, но почему?
LE>Пусть у нас будут те самые 3 таблицы. Пусть будет всего 1000 книг и у каждой всего лишь один автор. Получим по 1000 элементов в каждой таблице. Когда мы пишем select ... from books, authors, authorship мы получаем одну большую таблицу в которой сгенерированные всевозможные комбинации строк из 3 таблиц. То есть таблица с 1000^3 элементов, то есть в худшем случае просмотрим 1000^3 элементов.
LE>А в случае со вложенными запросами мы в худшем случае просмотрим 1000 элементов в первой таблице, столько же во 2 и в 3. То есть 3000. Я понимаю, что будут накладные расходы на вызов отдельного запроса, но разве они будут насколько критичными?
LE>Заранее спасибо!
Вам нужно почитать какую-нибудь литературу про то, как работают реальные РСУБД.
Во-первых, вы сравниваете не то: надо сравнивать с вложенными запросами не select ... from books, authors, authorship where (...), а

select ... from books 
  inner join authorship on books.id = authorship.book_id 
  inner join authors on authorship.author_id = author.id

Тогда вам будет немножко легче понять, почему реальный движок не будет просматривать временную таблицу размером в триллион записей. Даже при прямолинейном рассмотрении джойнов станет понятно, что сначала движок просмотрит 1000 записей в таблице books и для каждой из них найдет запись в таблице authorship. Результат по прежнему будет размером в 1000 записей, и теперь надо будет для каждой из них найти запись в таблице authors.
При этом, конечно же, просматривать всю 1000 записей правой части оператора join сервер тоже не будет, он воспользуется индексом. А стоимость поиска значения в индексе равна логарифму размера индекса по очень большому основанию. Скажем, для 1000 записей есть хорошие шансы обойтись двумя обращениями к диску.

Любой современный движок на основе SQL, стоящий внимания, автоматически конвертирует запросы с декартовым произведением и where в запросы с join. Поэтому никакого просмотра триллиона записей не будет: в реальности стоимость выполнения будет примерно линейной от количества записей в ваших таблицах.

Теперь можно рассмотреть, почему запрос с join лучше, чем два вложенных запроса.
Дело в том, что оптимальный порядок join сильно зависит от статистики реальных данных. Если у вас всего одна книга, у которой есть 1000 авторов, то выгоднее начинать сканирование с книги. Если наоборот — один автор у тысячи книг — то выгоднее начинать сканирование с автора. Всё потому, что стоимость nested loops join ~ o(N1*log(N2)), поэтому выгоднее под логарифмом держать большее из двух чисел. Когда вы руками пишете вложенные запросы, вы закладываете определённый план запроса, который может оказаться неоптимальным для реальных данных. Оставляя запрос с join, вы даёте движку шанс учесть реальную статистику при выборе плана.