none
Как вычислить сложность T-SQL скрипта? RRS feed

  • Вопрос

  • Доброе утро! У обычных алгоритмов можно посчитать сложность в О-нотации. Интересует руководство для начинающих по этой теме, в том числе для T-SQL. Спасибо.
    19 февраля 2017 г. 6:24

Ответы

  • SQL тоже язык, так что О-нотацию никто не отменял. Хотя тут уже не оперируют привычными структурами данных, как в языках более низкого уровня, подобных C#/Java и т.п. Тут важно другое:

    1. Производительность. Меряется она так и вот так. Вот сборник очень полезных рецептов. А dbForge Studio for SQL Server самая продвинутая, на мой взгляд, улилита для работы с T-SQL и SQL . Русскоязычная версия бесплатна для использования в не коммерческих целях.

    2. Читабельность кода. Я пользуюсь данным руководством,  и конечно, утилиты от Devart или ApexSQL сильно помогают в этом, автоматизируя многие рутинные задачи.


    Сделаем содержимое сообщества лучше, вместе!

    19 февраля 2017 г. 11:33
    Модератор
  • Сложность SQL-сценариев зависит от многих факторов. Запрос может выполняться по разному (разный алгоритм) в зависимости от объема данных, наличия индексов, кэширования и т.п. Кроме того, на время исполнения запросов влияют характеристики внешнего носителя, если данные считываются с него, что делает вычисление классического O(n) сложной задачей.

    Руководства для начинающих вы тут точно не дождетесь, но вкратце логика такая. Сложность запроса равна сложности самого медленного его этапа. Например, если применяется объединение, оно очень вероятно и будет таковым. Алгоритм, использемый при объединении, зависит от ситуации. Если одно из множеств невелико, используется прямой перебор, сложность которого О(N1*N2). Если оба множества велики, но являются результатом выборки из таблицы с сортированным индексом, используется "объединение слиянием", сложность которого О(N1+N2). (N1,N2 - число строк в объединяемых множествах).

    Таким образом, для вычисления сложности запросов вам нужно совместить
    - План исполнения запроса
    - Сведения об алгоритмах, применяемых СУБД в конкретной ситуации (например здесь для SQL Server: https://technet.microsoft.com/en-us/library/ms190610(v=sql.105).aspx)
    - Сведения о сложности этих алгоритмов, которые можно найти в книгах по теории алгоритмов, или в статьях типа этой: https://makeomatic.ru/blog/2015/10/02/relational_database_1/
    19 февраля 2017 г. 14:00

Все ответы

  • SQL тоже язык, так что О-нотацию никто не отменял. Хотя тут уже не оперируют привычными структурами данных, как в языках более низкого уровня, подобных C#/Java и т.п. Тут важно другое:

    1. Производительность. Меряется она так и вот так. Вот сборник очень полезных рецептов. А dbForge Studio for SQL Server самая продвинутая, на мой взгляд, улилита для работы с T-SQL и SQL . Русскоязычная версия бесплатна для использования в не коммерческих целях.

    2. Читабельность кода. Я пользуюсь данным руководством,  и конечно, утилиты от Devart или ApexSQL сильно помогают в этом, автоматизируя многие рутинные задачи.


    Сделаем содержимое сообщества лучше, вместе!

    19 февраля 2017 г. 11:33
    Модератор
  • Сложность SQL-сценариев зависит от многих факторов. Запрос может выполняться по разному (разный алгоритм) в зависимости от объема данных, наличия индексов, кэширования и т.п. Кроме того, на время исполнения запросов влияют характеристики внешнего носителя, если данные считываются с него, что делает вычисление классического O(n) сложной задачей.

    Руководства для начинающих вы тут точно не дождетесь, но вкратце логика такая. Сложность запроса равна сложности самого медленного его этапа. Например, если применяется объединение, оно очень вероятно и будет таковым. Алгоритм, использемый при объединении, зависит от ситуации. Если одно из множеств невелико, используется прямой перебор, сложность которого О(N1*N2). Если оба множества велики, но являются результатом выборки из таблицы с сортированным индексом, используется "объединение слиянием", сложность которого О(N1+N2). (N1,N2 - число строк в объединяемых множествах).

    Таким образом, для вычисления сложности запросов вам нужно совместить
    - План исполнения запроса
    - Сведения об алгоритмах, применяемых СУБД в конкретной ситуации (например здесь для SQL Server: https://technet.microsoft.com/en-us/library/ms190610(v=sql.105).aspx)
    - Сведения о сложности этих алгоритмов, которые можно найти в книгах по теории алгоритмов, или в статьях типа этой: https://makeomatic.ru/blog/2015/10/02/relational_database_1/
    19 февраля 2017 г. 14:00