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

Question

1) Сравнивается ли время выполнения SQL-запроса O (n) с количеством соединений, если индексы не используются? Если нет, то какие отношения мы можем ожидать? И может ли индексирование улучшить реальную сложность времени big-O, или оно только сокращает время запроса на некоторый постоянный коэффициент?

Немного расплывчатый вопрос, я уверен, что он сильно варьируется, но я говорю здесь в общем смысле.

2) Если у вас есть запрос типа:

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

Прав ли я, если предположить, что БД сначала выполнит фильтрацию по одной таблице на T1.color и T2.type, прежде чем оценивать условия нескольких таблиц? В таком случае усложнение запроса может сделать его более быстрым, поскольку меньшее количество строк подвергается тестам на уровне соединения?

Answer 1

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

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

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

Сложность 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 работает следующим образом:

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

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

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

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

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

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

3. Для указателей установлены минимальные значения в обеих таблицах:

   >1  2<
    2  3
    2  4
    3  5
   

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

   >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

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

Answer 2

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

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

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

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

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

SQL-запрос с одной таблицей: O ( n ). Это количество строк. Это также O ( p ) в зависимости от количества страниц.

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

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

Соединение слиянием заменяет O (n m) вложенных циклов на операцию сортировки O (log (n + m) (n + m)).

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

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

Смысл индекса не в том, чтобы так сильно уменьшать количество проверяемых строк. Это позволяет снизить стоимость ввода-вывода при извлечении строк.

Answer 3

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

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

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

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

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

Answer 4

Узнайте, как кластеризовано против некластеризованных индексов работает

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

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