Существует ли общее правило по сложности запросов SQL к производительности?

Ответ 1

Это зависит от используемого плана запроса.

Даже без индексов современные серверы могут использовать HASH JOIN и MERGE JOIN, которые быстрее, чем O(N * M)

Более конкретно, сложность HASH JOIN равна O(N + M), где N - хешированная таблица, а M - таблица поиска. Хеширование и хэш-поиск имеют постоянную сложность.

Сложность a MERGE JOIN равна O(N*Log(N) + M*Log(M)): это сумма раз, чтобы сортировать обе таблицы плюс время для их сканирования.

SELECT  T1.name, T2.date
FROM    T1, T2
WHERE   T1.id=T2.id
        AND T1.color='red'
        AND T2.type='CAR'

Если индексов нет, двигатель выберет либо HASH JOIN, либо MERGE JOIN.

HASH JOIN работает следующим образом:

• Выбран хед-таблица (обычно это таблица с меньшим количеством записей). Скажем, t1

• Отсканированы все записи из t1. Если записи содержат color='red', эта запись переходит в хэш-таблицу с id в качестве ключа и name в качестве значения.

• Отсканированы все записи из t2. Если запись содержит type='CAR', ее поиск id выполняется в хеш-таблице, а значения name из всех хеш-хитов возвращаются вместе с текущим значением data.

MERGE JOIN работает следующим образом:

• Создана копия t1 (id, name), отсортированная по id

• Создана копия t2 (id, data), отсортированная по id

• Указатели устанавливаются в минимальные значения в обеих таблицах:

  >1  2<
   2  3
   2  4
   3  5
  

• Указатели сравниваются в цикле, и если они совпадают, записи возвращаются. Если они не совпадают, указатель с минимальным значением продвигается:

  >1  2<  - no match, left pointer is less. Advance left pointer
   2  3
   2  4
   3  5
  
   1  2<  - match, return records and advance both pointers
  >2  3
   2  4
   3  5
  
   1  2  - match, return records and advance both pointers
   2  3< 
   2  4
  >3  5
  
   1  2 - the left pointer is out of range, the query is over.
   2  3
   2  4<
   3  5
  >
  

В таком случае сделать запрос более сложным может сделать его быстрее, потому что меньше строк подвергаются испытаниям уровня соединения?

Конечно.

Ваш запрос без предложения WHERE:

SELECT  T1.name, T2.date
FROM    T1, T2

проще, но возвращает больше результатов и работает дольше.

Ответ 2

Будьте осторожны, чтобы слить слишком много разных вещей. У вас есть логическая стоимость запроса, основанная на количестве проверяемых строк, (возможно) меньшей логической стоимости, основанной на количестве фактически возвращенных строк и несвязанной физической стоимости, основанной на количестве страниц, которые необходимо изучить.

Эти три связаны, но не сильно.

Количество проверенных строк является самой большой из этих затрат и наименее легко контролируется. Строки должны соответствовать алгоритму соединения. Это также является наименее значимым.

Количество возвращенных строк является более дорогостоящим, поскольку эта пропускная способность ввода-вывода между клиентским приложением и базой данных.

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

SQL Query с одной таблицей O (n). Это количество строк. Он также O (p) основан на количестве страниц.

С более чем одной таблицей рассмотренные строки O (nm...). Это алгоритм вложенных циклов. Однако в зависимости от мощности отношения результирующий набор может быть как O (n), потому что отношения все 1:1. Но каждая таблица должна быть проверена для соответствия строк.

A Hash Join заменяет O (n * log (n)) индекс + таблица читает с помощью O (n) прямых хеш-запросов. Вам все равно придется обрабатывать строки O (n), но вы обходите некоторые чтения индексов.

Merge Join заменяет вложенные петли O (nm) с помощью операции сортировки O (log (n + m) (n + m)).

С индексами физическая стоимость может быть уменьшена до O (log (n) m), если таблица просто проверяется на существование. Если строки требуются, то индекс скорости доступа к строкам, но все соответствующие строки должны быть обработаны. O (нм), потому что размер набора результатов, независимо от индексов.

Страницы, рассмотренные для этой работы, могут быть меньше, в зависимости от избирательности индекса.

Точка индекса не должна уменьшать количество проверенных строк. Это уменьшает затраты физического ввода-вывода на выборку строк.

Ответ 3

Выполняется ли время выполнения запроса SQL O (n) по сравнению с количеством объединений, если индексы не используются?

Как правило, они будут O (n ^ m), где n - количество записей для каждой таблицы, а m - количество соединяемых таблиц.

И может ли индексирование улучшать текущую сложность по времени большого или наоборот, или это уменьшает время всего запроса на некоторый постоянный фактор?

И. Индексы позволяют осуществлять прямой поиск, когда соединения сильно фильтруются (т.е. С хорошим предложением WHERE), и они позволяют быстрее присоединяться, когда они находятся в правильных столбцах.

Индексы не помогают, когда они не находятся в столбцах, которые соединяются или фильтруются.

Ответ 4

Посмотрите, как clustered vs некластеризованные индексы work

Это с чистой технической точки зрения... для легкого объяснения мой хороший приятель mladen написал простую статью, чтобы понять индексирование.

Индексы определенно помогают, но я рекомендую читать, чтобы понять плюсы и минусы.