Вопросы Теги

Есть ли какое-либо общее правило сложности SQL-запроса По сравнению с производительностью?

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

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

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

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

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

34
задан Quassnoi 14 January 2010 в 17:42
поделиться

4 ответа

Roger Pate, Value_Types - «простые» Отказ Я подозреваю, что вы увидите const, если вы посмотрите на iTerator_traits :: const_iterator> :: Ссылка, которую я думаю, будет «Const Int &».

-121--3713785-

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

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

более конкретно, сложность HASH ANCON представляет собой o (n + m) , где n представляет собой хешированную таблицу и m - это таблица поиска. Хеширование и хэш-поиски имеют постоянную сложность.

Сложность объединения объединения 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'

Если нет определенных индексов, двигатель выберет либо A хеш соединения или A объединение .

Присоединение ASH работает следующим образом:

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

  2. все записи из T1 отсканированы. Если записи выполнены COLOR = 'RED' , эта запись попадает в хэш-таблицу с помощью ID в виде ключа и имя в качестве значения.

  3. Все записи из T2 отсканированы. Если запись удерживает Type = 'Car' , его ID ищет в хеш-таблице, а значения имя из всех хеш-хитов возвращаются вместе с Текущее значение данных данных .

Объединение объединение работает следующим образом:

  1. Копия T1 (ID, имя) создается, отсортирована на ID

  2. Копия T2 (ID, данные) создается, отсортировано на ID

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

    > 1 2 <
  2 3
  2 4
  3 5.

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

    > 1 2 <- Нет совпадения, левый указатель меньше.  Аванс левый указатель
  2 3
  2 4
  3 5.

  1 2 <- Match, Return Records и продвижение обоих указателей
 > 2 3
  2 4
  3 5.

  1 2 - Матч, возвращает записи и продвижение обоих указателей
  2 3 <
  2 4
 > 3 5.

  1 2 - левый указатель вне диапазона, запрос окончен.
  2 3
  2 4 <
  3 5.
 >

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

Конечно.

Ваш запрос без , где пункт: 

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

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

44
ответ дан 27 November 2019 в 16:47
поделиться

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

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

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

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

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

-121--1302512-

Рекурсия должна использоваться только с определенными структурами данных. Файловая система, будучи древовидной структурой, определенно является хорошим примером для рекурсии. Я бы зашел так далеко, чтобы сказать, что это, вероятно, лучший способ выполнить то, что вы пытаетесь сделать.

-121--4196185-

Проверьте, как кластеризованные против некластеризованные индексы работают

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

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

0
ответ дан 27 November 2019 в 16:47
поделиться

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

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

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

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

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

1
ответ дан 27 November 2019 в 16:47
поделиться

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

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

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

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

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

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

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

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

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

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

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

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

15
ответ дан 27 November 2019 в 16:47
поделиться
Другие вопросы по тегам:

Похожие вопросы: