Производительность. Коллекции C# или обычный SQL

Posted by Никита Ляпин on Saturday, May 8, 2021

О чем эта статья и кому адресована?

С SQL работают почти все, но даже опытные разработчики иногда не могут ответить на простой вопрос. Каким образом СУБД выполняет самый обычный INNER JOIN?

С другой стороны - разработчики на C# или других ООП языках часто воспринимают СУБД как всего лишь хранилище. И размещать какие-то бизнес-правила в SQL - плохо. В противовес им создаются библиотеки вроде Linq2Db (не путаем с Linq2Sql - совершенно разные авторы и разные библиотеки). При ее использовании весь код пишется на C# и вы получаете все преимущества типизированного языка. Но это формальность. Затем этот код транслируется на SQL и выполняется на стороне СУБД.

Для того чтобы лучше разобраться как работает одинаковый код на SQL и на C# мы попробуем реализовать одно и то же на первом и на втором, а затем разберем как это работает. Если вы хорошо знаете что такое Nested Loop, Merge Join, Hash Join - вам скорее всего имеет смысл прочитать статью по диагонали. А вот если не знаете - статья для вас должна быть полезной.

Работа с несколькими коллекциями

Предположим, что у нас есть некоторый сервисный центр по техническому обслуживанию автомобилей - станция технического обслуживания (СТО). Есть две сущности: Person - клиенты сервисного центра и Visit - конкретное посещение данного центра. Person кроме идентификатора содержит имя, фамилию и статус активности (например, если клиент поменял машину на другую марку - он переводится в статус не активного и уже не будет в ближайшем времени посещать нас). Visit кроме идентификатора содержит в себе ссылку на клиента, дату визита и сумму, которую заплатил клиент за этот визит. Все вышеперечисленное можно было бы оформить с помощью следующих классов на C# для самого простейшего случая:

internal sealed class Person
{
    internal int Id { get; set; }
    internal string FirstName { get; set; }
    internal string LastName { get; set; }
    internal bool IsActive { get; set; }
}

internal sealed class Visit
{
    internal int Id { get; set; }
    internal int PersonId { get; set; }
    internal DateTime Date { get; set; }
    internal decimal Spent { get; set; }
}

// ...
internal Person[] persons = new Person[];
internal Visit[] visits = new Visit[];
// ...

В базе данных (в дальнейшем мы будем использовать PostgreSQL) для двух этих сущностей есть две таблицы с аналогичными полями:

create table public.visit
(
    id integer,
    person_id integer,
    visit_datetime timestamp without time zone,
    spent money
) tablespace pg_default;

create table public.person
(
    id integer,
    first_name character varying(100) COLLATE pg_catalog."default",
    last_name character varying(100) COLLATE pg_catalog."default",
    is_active boolean
) tablespace pg_default;

Исходный код для данной статьи находится здесь. Если у вас есть какие-то замечания - можете сразу править.

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

Nested Loop

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

public decimal NestedLoop()
{
    decimal result = 0;
    var upperLimit = new DateTime(2020, 12, 31);

    foreach (var person in persons)
    {
        if (person.IsActive == false)
        {
            continue;
        }
        
        foreach (var visit in visits)
        {
            if (person.Id == visit.PersonId && visit.Date <= upperLimit)
            {
                result += visit.Spent;
            }
        }
    }
    return result;
}

Эта идея анимирована ниже:

Алгоритм очень простой, не потребляет дополнительной памяти. Но затратность его O(N²), что будет сказываться на большом числе элементов - чем их больше, тем больше телодвижений необходимо совершить.

Для того, чтобы оценить скорость его работы мы создадим тестовый набор данных с помощью следующего SQL скрипта:

select setseed(0.777);

delete from public.person;
insert into public.person(id, first_name, last_name, is_active)
select row_number() over () as id,
substr(md5(random()::text), 1, 10) as first_name,
substr(md5(random()::text), 1, 10) as last_name,
((row_number() over ()) % 5 = 0) as is_active
from generate_series(1, 5000);/*<-- 5000 это число клиентов*/

delete from public.visit;
insert into public.visit(id, person_id, visit_datetime, spent)
select row_number() over () as id,
(random()*5000)::integer as person_id, /*<-- 5000 это число клиентов*/
DATE '2020-01-01' + (random() * 500)::integer as visit_datetime,
(random()*10000)::integer as spent
from generate_series(1, 10000); /* 10000 - это общее число визитов в СТО*/

В данном случае число клиентов CTO P равно 5000, число их визитов V - 10000. Дата визита, а также сам факт визита для клиента генерируются случайным образом из указанных диапазонов. Признак активности клиента выставляется для каждого пятого. В итоге мы получаем некоторый тестовый набор данных, приближенный к реальному. Для тестового набора нам интересна характеристика - число клиентов и посещений. Или (P,V) равное в нашем случае (5000, 10000). Для этого тестового набора мы сделаем следующее: выгрузим его в обьекты C# и с помощью цикла в цикле (Nested Loop) посчитаем суммарные траты наших посетителей. Как это определено в постановке задачи. На моем компьютере получаем приблизительно 20.040 миллисекунд, затраченное на подсчет. При этом время получение данных из БД составило все те же самые 20.27 миллисекунд. Что в сумме дает около 40 миллисекунд. Посмотрим на время выполнения SQL запроса на тех же данных.

select sum(v.spent) from public.visit v
                    join public.person p on p.id = v.person_id
where v.visit_datetime <= '2020-12-31' and p.is_active = True

Все на том же компьютере получилось порядка 2.1 миллисекунды на все. И кода заметно меньше. Т.е. в 10 раз быстрее самого метода, не считая логики по извлечению данных из БД и их материализации на стороне приложения.

Merge Join

Разница в скорости работы в 20 раз наталкивает на размышления. Скорее всего Nested Loop не очень нам подходит
и мы должны найти что-то получше. И есть такой алгоритм… Называется Merge Join или Sort-Merge Join. Общая суть в том, что мы сортируем два списка по ключу на основе которого происходит соединение. И делаем проход всего в один цикл. Инкрементируем индекс и если значения в двух списках совпали - добавляем их в результат. Если в левом списке идентификатор больше, чем в правом - увеличиваем индекс массива только для правой части. Если, наоборот, в левом списке идентификатор меньше, то увеличиваем индекс левого массива. Затратность такого алгоритма O(N*log(N)).

Результат работы такой реализации радует глаз - 1.4 миллисекунды в C#. Правда данные из базы данных еще нужно извлечь. А это все те же самые дополнительные 20 миллисекунд. Но если вы извлекаете данные из БД, а затем выполняете несколько обработок, то недостаток постепенно нивелируется. Но можно ли подсчитать заданную сумму еще быстрее? Можно! Hash Join поможет нам в этом.

Hash Join

Этот алгоритм подходит для больших массивов данных. Его идея проста. Для каждого из списков считается хэш ключа, далее этот хэш используется для того, чтобы выполнить сам Join. Детально можно посмотреть в видео:

Видео работы Hash Join (на англ. языке)

Затратность алгоритма O(N). В .NET стандартный Linq метод как раз его и реализует. В реляционных СУБД часто используются модификации этого алгоритма (Grace hash join, Hybrid hash join) - суть которых сводится к работе в условиях ограниченной оперативной памяти. Замер скорости работы в C# показывает, что этот алгоритм еще быстрее и выполняется за 0.9 миллисекунды.

Динамический выбор алгоритма

Отлично! Похоже мы нашли универсальный алгоритм, который самый быстрый. Нужно просто использовать его всегда и не беспокоиться более об этом вопросе. Но если мы учтем еще и расход памяти все станет немного сложнее. Для Nested Loop - память не нужна, Merge Join - нужна только для сортировки (если она будет). Для Hash Join - нужна оперативная память.

Оказывается расход памяти - это еще не все. В зависимости от общего числа элементов в массивах скорость работы разных алгоритмов ведет себя по-разному. Проверим для меньшего числа элементов (P, V) равному (50, 100). И ситуация переворачивается на диаметрально противоположную: Nested Loop самый быстрый - 2.202 микросекунды, Merge Join - 4.715 микросекунды, Hash Join - 7.638 микросекунды. Зависимость скорости работы каждого алгоритма можно представить таким графиком:

Для нашего примера можно провести серию экспериментов на C# и получить следующую таблицу:

Method Nested Loop Merge Join Hash Join
(10, 10) 62.89 ns 293.22 ns 1092.98 ns
(50, 100) 2.168 us 4.818 us 7.342 us
(100, 200) 8.767 us 10.909 us 16.911 us
(200, 500) 38.77 us 32.75 us 40.75 us
(300, 700) 81.36 us 52.54 us 54.29 us
(500, 1000) 189.58 us 87.10 us 82.85 us
(800, 2000) 606.8 us 173.4 us 172.7 us
(750, 5000) 1410.6 us 428.2 us 397.9 us

А что если узнать значения X1 и X2 и динамически выбирать алгоритм в зависимости от его значения для данных коллекций? К сожалению не все так просто. Наша текущая реализация исходит из статичности коллекции. Что нужно сделать, чтобы вставить еще один визит за 2020 год? В массив в коде на C#. В массив фиксированного размера он, очевидно, не поместится. Нужно выделять новый массив размером на один элемент больше. Скопировать туда все данные, вставлять новый элемент. Понятно, что это дорого. Как насчет того, чтобы заменить Array на List? Уже лучше, т.к. он предоставляет все необходимое API. Как минимум удобно, но если посмотреть на его реализацию - под капотом используется все тот же массив. Только резервируется памяти больше чем надо… С запасом. Для нас это означает лишние траты памяти. LinkedList? Здесь должно быть все нормально. Давайте поменяем коллекцию и посмотрим что из этого получится.

Method Nested Loop Nested Loop with Linked List
(10, 10) 62.89 ns 262.97 ns
(50, 100) 2.188 us 8.160 us
(100, 200) 8.196 us 32.738 us
(200, 500) 39.24 us 150.92 us
(300, 700) 80.99 us 312.71 us
(500, 1000) 196.3 us 805.20 us
(800, 2000) 599.3 us 2359.1 us
(750, 5000) 1485.0 us 5750.0 us

Время выполнения не только изменилось. Сама кривая стала более крутой и с числом элементов время растет:

Стоит отметить, что добавление индекса может сильно улучшить работу Nested Loop. Такая вариация называется Indexed Nested Loop и по скорости он может составить конкуренцию даже Hash Join. Особенно если учитывать отсутсвие необходимости в дополнительной памяти (кроме самого индекса).

Таким образом мы приходим к понимаю, что время доступа к каждому конкретному элементу коллекции крайне важно. Одно из главных преимуществ реляционных СУБД в том, что они всегда готовы к добавлению новых данных в любой диапазон. При этом это добавление произойдет максимально эффективным образом - не будет релокации всего диапазона данных или т.п. Кроме того данные СУБД часто хранится в одном файле - таблицы и их данные. Если утрировать, то здесь также используется связанный список. В случае с PostgreSQL данные представлены в страницах (page), внутри страницы располагаются кортежи данных (tuples). В общих чертах вы можете себе это увидеть на картинках ниже. А если захотите узнать больше деталей, то ниже также есть и ссылка.

Более детально описано в первоисточнике Здесь

Структура кортежа также адаптирована для хранения практически любых данных в таблице, на их обновление и вставку в любой участок диапазона: Более детально описано в первоисточнике Здесь.

В оперативную память попадают страницы, а попадают они в buffer pool через buffer manager. Все это сказывается на стоимости доступа к каждому конкретному значению таблицы. Вне зависимости от того что используется Nested Loop, Merge Join или Hash Join. Другой вопрос, что в зависимости от алгоритма число обращений может отличаться в разы. Поэтому реляционные СУБД подходят динамически к выбору алгоритма в каждом конкретном запросе и строят план запроса (Query Plan).

Сравним для большого числа элементов насколько будет отличаться время обработки с одним и тем же алгоритмом в БД и на C#. (P, V) будет равно (50000, 100000). В коде на C# загрузка данных из БД занимает 145.13 миллисекунд. Дополнительно к этому выполнение самой логики с Nested Loop на основе обычного массива - 305.38 миллисекунд, Hash Join - 36.59 миллисекунд. Для того чтобы проверить в СУБД такую же реализацию мы будем использовать такой скрипт:

set enable_hashjoin to 'off';--Заставляем БД использовать Nested Loop
set enable_mergejoin to 'off';
set enable_material to 'off';

select sum(v.spent) from public.visit v
join public.person p on p.id = v.person_id
where v.visit_datetime <= '2020-12-31' and p.is_active = True

На аналогичных данных в БД с Nested Loop запрос выполнится за 11247.022 миллисекунд. Что может говорить о сильно большем времени доступа к каждому конкретному элементу:

Но СУБД приходится заставлять работать так, чтобы она использовала Nested Loop. Изменим наш скрипт таким образом:

set enable_hashjoin to 'on';
set enable_mergejoin to 'on';
set enable_material to 'on';

select sum(v.spent) from public.visit v
join public.person p on p.id = v.person_id
where v.visit_datetime <= '2020-12-31' and p.is_active = True

По-умолчанию для такого объема данных будет, конечно выбран Hash Join:

И мы видим, что время выполнение составило 25.806 миллисекунды, что сопоставимо по скорости с реализацией на C# и даже немного быстрее.

Как мы видим, СУБД может динамически подстраиваться под данные и автоматически выбирать алгоритм, наиболее подходящий в данной конкретной ситуации. Процесс выбора такого способа выполнения запроса возложен на планировщик запросов. В итоге он выдает план запроса, где четко расписано какой алгоритм использовать, какой использовать индекс и т.п.

Выводы

На примере простейшей задачи мы в общих чертах разобрали как работает типичная реляционная СУБД при реализации JOIN. Сравнивать коллекции C# и SQL не очень корректно, за внешней схожестью скрывается серьезное различие в предназначении. Реляционная СУБД призвана обеспечить конкурентный доступ к данным максимально эффективным способом (при этом подразумевается, что сами данные могут постоянно модифицироваться). Кроме того, данные могут не помещаться в оперативную память и частично храниться на диске.

Более того, СУБД обязана обеспечить сохранность данных на постоянном носителе - одно из основных ее предназначений. При этом на получение данных СУБД динамически выбирает алгоритм, наиболее эффективный в данном случае. В C# аналагичных библиотек или реализаций просто нет… И это показательно, т.к. лишь свидетельствует об отсутствии такой необходимости. Linq метод Join реализует Hash Join, который потенциально тратит больше оперативной памяти, но это просто не берется в расчет. Т.к. мало кого интересует применительно к решаемым задачам.

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