Вопрос по SQL из статьи Джоэла Спольски

Question

Из статьи Джоэла Спольски о дырявых абстракциях:

[C] некоторые запросы SQL в тысячи раз медленнее, чем другие логически эквивалентные запросы. Известным примером этого является то, что некоторые SQL-серверы значительно быстрее, если указать «где a = b и b = c и a = c», чем если указать только «где a = b и b = c», даже если набор результатов такой же.

Кто-нибудь знает подробности этого?

Answer 1

Очевидно, что a = b и b = c => a = c - это связано с транзитивным замыканием. Джоэл говорил о том, что некоторые SQL-серверы плохо оптимизируют запросы, поэтому некоторые из SQL-запросов могут быть написаны с «дополнительными» квалификаторами, как в примере.

В этом примере помните, что a, b и c, как указано выше, часто ссылаются на разные таблицы, и такие операции, как a = b, выполняются как объединения. Предположим, что количество записей в таблице a равно 1000, b равно 500 и c равно 20. Затем объединение a, b требует сравнения строк 1000x500 (это мой тупой пример; на практике могут быть гораздо лучшие алгоритмы объединения, которые уменьшают сложность много), а б, в требуется 500х20 сравнений. Оптимизирующий компилятор определит, что сначала должно быть выполнено объединение b, c, а затем результат должен быть объединен для a = b, так как ожидается меньше строк с b = c. Всего существует около 500x20 + 500x1000 сравнений для (b = c) и (a = b) соответственно. После этого пересечения должны быть вычислены между возвращенными строками (я думаю, также через соединения, но не уверен).

Предположим, что сервер Sql может иметь модуль логического вывода, который также выведет, что это означает a = c. Тогда он, вероятно, выполнит соединение b, c, а затем соединение a, c (опять же, это гипотетический случай). Это займет 500x20 + 1000x20 сравнений и после этого пересечения вычислений. Если ожидаемый # (a = c) меньше (из-за некоторого знания предметной области), тогда второй запрос будет намного быстрее.

В целом мой ответ стал слишком длинным, но это означает, что оптимизация SQL-запросов не является тривиальной задачей, и поэтому некоторые SQL-серверы могут делать это не очень хорошо.

Более подробную информацию можно найти по адресу http://en.wikipedia.org/wiki/Query_optimizer или, по некоторым данным, в базах данных, читающих это.

Но с философской точки зрения SQL (как абстракция) должен был скрыть все аспекты реализации. Он должен был быть декларативным (сам сервер SQL может использовать методы оптимизации SQL-запросов, чтобы перефразировать запрос, чтобы сделать их более эффективными). Но в действительности это не так - часто запросы к базе данных должны быть переписаны людьми, чтобы сделать их более эффективными.

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

Answer 2

Вот более простое объяснение, где все все в одной таблице.

Предположим, что A и C оба проиндексированы, а B нет. Если оптимизатор не может понять, что A = C, он должен использовать неиндексированный B для обоих условий WHERE.

Но если вы затем скажете серверу, что a = c, он может сначала эффективно применить этот фильтр и значительно уменьшить размер рабочего набора.

Answer 3

Я думаю, что «определенное» слово здесь является оперативным. Чтобы оптимизатор действительно понимал, что a = c, он должен был бы проанализировать и затем полностью соединить равенство a с «c» в транзитивных отношениях, чтобы вывести отношение.

Я думаю, что в будущем оптимизаторы SQL могут стать такими умными (если они этого еще не сделали), так что IMO это не совсем общее утверждение со стороны Джоэла.