Русский
Русский
English
Статистика
Реклама

Как реляционная СУБД делает JOIN?

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

С 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_activefrom 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 spentfrom generate_series(1, 10000); /* 10000 - это общее число визитов в СТО*/

В данном случае число клиентов CTOPравно 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_idwhere 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

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

Таким образом мы приходим к понимаю, что время доступа к каждому конкретному элементу коллекции крайне важно. Одно из главных преимуществ реляционных СУБД в том, что они всегда готовы к добавлению новых данных в любой диапазон. При этом это добавление произойдет максимально эффективным образом - не будет релокации всего диапазона данных или т.п. Кроме того данные СУБД часто хранится в одном файле - таблицы и их данные. Если утрировать, то здесь также используется связанный список. В случае с 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 Loopset enable_mergejoin to 'off';set enable_material to 'off';select sum(v.spent) from public.visit vjoin public.person p on p.id = v.person_idwhere 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 vjoin public.person p on p.id = v.person_idwhere v.visit_datetime <= '2020-12-31' and p.is_active = True

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

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

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

Выводы

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

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

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

Источник: habr.com
К списку статей
Опубликовано: 03.06.2021 14:23:54
0

Сейчас читают

Комментариев (0)
Имя
Электронная почта

Высокая производительность

Postgresql

Программирование

Net

Sql

Категории

Последние комментарии

© 2006-2021, personeltest.ru