15.09.2015 11:03
rvncerr 132 112833 Источник
Реляционные базы данных (РБД) используются повсюду. Они бывают самых разных видов, от маленьких и полезных SQLite до мощных Teradata. Но в то же время существует очень немного статей, объясняющих принцип действия и устройство реляционных баз данных. Да и те, что есть — довольно поверхностные, без особых подробностей. Зато по более «модным» направлениям (большие данные, NoSQL или JS) написано гораздо больше статей, причём куда более глубоких. Вероятно, такая ситуация сложилась из-за того, что реляционные БД — вещь «старая» и слишком скучная, чтобы разбирать её вне университетских программ, исследовательских работ и книг.

На самом деле, мало кто действительно понимает, как работают реляционные БД. А многие разработчики очень не любят, когда они чего-то не понимают. Если реляционные БД используют порядка 40 лет, значит тому есть причина. РБД — штука очень интересная, поскольку в ее основе лежат полезные и широко используемые понятия. Если вы хотели бы разобраться в том, как работают РБД, то эта статья для вас.

Сразу нужно подчеркнуть: из этого материала вы НЕ узнаете, как можно использовать БД. Однако для усвоения материала вы должны уметь написать хотя бы простенький запрос на соединение и CRUD-запрос. Этого вполне достаточно для понимания статьи, остальное будет объяснено.

Статья состоит из трёх частей:
  1. Обзор низкоуровневых и высокоуровневых компонентов БД.
  2. Обзор процесса оптимизации запросов.
  3. Обзор управления транзакциями и буферным пулом.


1. Основы


Давным-давно (в далёкой-далёкой галактике) разработчики должны были держать в голове точное количество операций, которые они кодят. Они всем сердцем чувствовали алгоритмы и структуры данных, поскольку не могли себе позволить тратить впустую ресурсы процессора и памяти на своих медленных компьютерах прошлого. В этой главе мы вспомним некоторые концепции, которые необходимы для понимания работы БД.

1.1. О(1) против О(n2)


Сегодня многие разработчики не особо задумываются о временн?й сложности алгоритмов… и они правы! Но когда приходится работать с большим объёмом данных, или если нужно экономить миллисекунды, то временнaя сложность становится крайне важна.

1.1.1. Концепция

Временнaя сложность используется для оценки производительности алгоритма, как долго будет выполняться алгоритм для входных данных определённого размера. Обозначается временнaя сложность как «О» (читается как «О большое»). Это обозначение используется вместе с функцией, описывающей количество операций, осуществляемых алгоритмом для обработки входных данных.

Например, если сказать «этот алгоритм есть О большое от некоторой функции», то это означает, что для определённого объёма входных данных алгоритму нужно выполнить количество операций, пропорциональное значению функции от этого определённого объёма данных.

Здесь важен не объём данных, а динамика увеличения количества операций с ростом объёма. Временнaя сложность не позволяет вычислить точное количество, но зато представляет собой хороший способ оценки.



На этом графике вы видите, как изменяются разные классы сложностей. Для наглядности используется логарифмическая шкала. Иными словами, количество данных быстро увеличивается от 1 до 1 000 000. Мы видим, что:
  • O(1) является «константным временем», то есть её значение постоянно.
  • O(log(n)) — логарифмическое время, возрастает очень медленно.
  • Хуже всего со сложностью обстоят дела у O(n2) — квадратичного времени.
  • Два остальных класса сложности быстро возрастают.


1.1.2. Примеры

При небольшом количестве входных данных разница между О(1) и О(n2) пренебрежимо мала. Допустим, у нас есть алгоритм, которому нужно обработать 2000 элементов.
  • Алгоритму с О(1) для этого потребуется 1 операция.
  • O(log(n)) — 7 операций.
  • O(n) — 2000 операций.
  • O(n*log(n)) — 14 000 операций.
  • O(n2) — 4 000 000 операций.

Кажется, что разница между О(1) и O(n2) огромна, но на деле вы потеряете не более 2 мс. Глазом моргнуть не успеете, в буквальном смысле. Современные процессоры выполняют сотни миллионов операций в секунду, и именно поэтому во многих проектах разработчики пренебрегают оптимизацией производительности.

Но возьмём теперь 1 000 000 элементов, что не слишком много по меркам БД:
  • Алгоритму с О(1) для обработки потребуется 1 операция.
  • O(log(n)) — 14 операций.
  • O(n) — 1 000 000 операций.
  • O(n*log(n)) — 14 000 000 операций.
  • O(n2) — 1 000 000 000 000 операций.

В случае с последними двумя алгоритмами можно будет успеть выпить кофе. А если добавить ещё один 0 к количеству элементов, то за время обработки можно и вздремнуть.

1.1.3. Ещё немного подробностей

Чтобы вы могли ориентироваться:
  • Поиск элемента в хорошей хэш-таблице занимает О(1).
  • В хорошо сбалансированном дереве — O(log(n)).
  • В массиве — O(n).
  • Наилучшие алгоритмы сортировки имеют сложность O(n*log(n)).
  • Плохие алгоритмы сортировки — O(n2).

Ниже мы рассмотрим эти алгоритмы и структуры данных.

Существует несколько классов временн?й сложности:
  • Средняя сложность
  • Сложность в наилучшем случае
  • Сложность в наихудшем случае

Чаще всего встречается третий класс. Кстати, понятие «сложности» применимо также к потреблению алгоритмом памяти и операций ввода/вывода дисковой системы.

Существуют сложности куда хуже, чем n2:
  • n4: характерно для некоторых плохих алгоритмов.
  • 3n: ещё хуже! Ниже будет рассмотрен один алгоритм с подобной временн?й сложностью.
  • n!: вообще адский треш. Замучаетесь ждать результат даже на небольших объёмах данных.
  • nn: если вы дождались результата выполнения этого алгоритма, то впору задаться вопросом, а стоит ли вам вообще этим заниматься?


1.2. Сортировка слиянием


Что вы делаете, когда вам нужно отсортировать коллекцию? Вызываете функцию sort(), верно? Но понимаете ли вы, как она работает?

Есть несколько хороших алгоритмов сортировки, но здесь мы рассмотрим только один из них: сортировку слиянием. Возможно, сейчас вам это знание не кажется полезным, но вы поменяете мнение после глав про оптимизацию запросов. Более того, понимание работы этого алгоритма поможет понять принцип важной операции — соединение слиянием.

1.2.1. Слияние

В основе алгоритма сортировки слиянием лежит одна хитрость: для слияния двух отсортированных массивов размером N/2 каждый требуется всего лишь N операций, называющихся слиянием.

Рассмотрим пример операции слияния:



Как видите, для создания отсортированного массива из 8 элементов, для каждого из них нужно провести по одной итерации в двух исходных массивах. Поскольку они уже заранее отсортированы, то:
  1. Сначала в них сравниваются имеющиеся элементы,
  2. наименьший из них переносится в новый массив,
  3. а затем происходит возврат в тот массив, откуда был взят предыдущий элемент.
  4. Шаги 1-3 повторяются до тех пор, пока в одном из исходных массивов не останется лишь один элемент.
  5. После этого из второго массива переносятся все оставшиеся элементы.

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

Пример псевдокода сортировки слиянием:

array mergeSort(array a)
   if(length(a)==1)
      return a[0];
   end if

   //recursive calls
   [left_array right_array] := split_into_2_equally_sized_arrays(a);
   array new_left_array := mergeSort(left_array);
   array new_right_array := mergeSort(right_array);

   //merging the 2 small ordered arrays into a big one
   array result := merge(new_left_array,new_right_array);
   return result;

Данный алгоритм разбивает задачу на ряд маленьких подзадач (парадигма «разделяй и властвуй»). Если вы не поняли сути, то попробуйте представить, что алгоритм состоит из двух фаз:
  • Фаза деления — массив делится на более мелкие массивы.
  • Фаза сортировки — мелкие массивы собираются вместе (сливаются).

1.2.2. Фаза деления



В три этапа исходный массив делится на подмассивы, состоящие из одного элемента. Вообще, количество этапов деления определяется как log(N) (в данном случае N=8, log(N) = 3). Идея в том, чтобы на каждом этапе делить входящие массивы пополам. То есть описывается логарифмом с основанием 2.

1.2.3. Фаза сортировки



Здесь происходит обратная операция, объединение массивов с двукратным увеличением их размеров. Для этого требуется проделать на каждом этапе по 8 операций:
  • На первом этапе происходит 4 слияния, по 2 операции каждое.
  • На втором — 2 слияния по 4 операции.
  • На третьем — 1 слияние из 8 операций.

Поскольку количество этапов определяется как log(N), то общее количество операций определяется как N * log(N).

1.2.4. Возможности сортировки слиянием

В чём преимущества данного алгоритма?
  • Его можно модифицировать для уменьшения потребления памяти, если вы хотите не создавать новые массивы, а модифицировать входящий (так называемый «алгоритм замещения»).
  • Его можно модифицировать для уменьшения потребления памяти и использования дисковой подсистемы, снизив количество операций ввода/вывода. Идея заключается в том, что в памяти находятся только те части данных, которые подвергаются обработке в конкретный момент времени. Это особенно важно, когда нужно сортировать многогигабайтные таблицы, а в наличии есть только буфер мегабайт на 100. Данный алгоритм называется «внешней сортировкой».
  • Его можно модифицировать для запуска в нескольких параллельных процессах/потоках/серверах
  • Например, распределённая сортировка слиянием является ключевой особенностью Hadoop.

Этот алгоритм может практически превращать свинец в золото! Он используется в большинстве (если не во всех) СУБД, хотя и не он один. Если вас интересует больше грязных подробностей, можете почитать одну исследовательскую работу, в которой разбираются плюсы и минусы распространённых алгоритмов сортировки.

1.3. Массив, дерево и хэш-таблица


Итак, с временн?й сложностью и сортировкой разобрались. Теперь давайте обсудим три структуры данных, на которых держатся современные БД.

1.3.1. Массив

Двумерный массив — простейшая структура данных. Таблица может быть представлена в виде массива:



Здесь каждая строка представляет собой какой-то объект, колонка — свойство объекта. Причём разные колонки содержат разные типы данных (целые числа, строки, даты и т.д.).

Это очень удобный способ хранения и визуализации информации, но очень неподходящий для случаев, когда нужно найти какое-то конкретное значение. Допустим, вам нужно найти всех сотрудников, работающих в Великобритании. Для этого придётся просмотреть все строки, чтобы найти те, где имеется значение “UK”. На это потребуется N операций (N — количество строк). Не так уж и плохо, но хорошо бы и побыстрее. И здесь нам помогут деревья.

Примечание: большинство современных СУБД используют продвинутые виды массивов, позволяющие эффективнее хранить таблицы (например, на основе куч или индексов). Но это не решает проблему скорости поиска по колонкам.

1.3.2. Дерево и индекс БД

Бинарное дерево поиска — это дерево, в котором ключ в каждом узле должен быть:
  • Больше, чем любой из ключей в ветке слева.
  • Меньше, чем любой из ключей в ветке справа.



Каждый узел представляет собой указатель на строку в связанной таблице.

Вышеприведённое дерево содержит N = 15 элементов. Допустим, нам нужно найти узел со значением 208:
  • Начнём с узла, содержащего ключ 136. Поскольку 136 < 208, то следуем по правой ветке дерева.
  • 398 > 208, значит спускаемся по левой ветке, исходящей из этого узла.
  • 250 > 208, опять идём по левой ветке.
  • 200 < 208, нужно пойти по правой ветке. Но поскольку у узла с ключом 200 нет веток, то искомое значение не существует. Если бы оно существовало, то у узла-200 были бы ветки.

Допустим, теперь нужно найти узел со значением 40:
  • Опять начинаем с корневого узла-136. Раз 136 > 40, значит идём по левой ветке.
  • 80 > 40, снова «поворачиваем налево».
  • 40 = 40, такой узел существует. Извлекаем ID строки, хранящийся в этом узле (это не значение ключа), и ищем по нему в связанной таблице.
  • Зная ID строки, можно очень быстро извлечь нужные данные.

Каждая процедура поиска состоит из определённого количества операций по мере путешествия по ветвям дерева. Количество операций определяется как Log(N), так же как и в случае с сортировкой слиянием.

Но вернёмся к нашей проблеме.

Допустим, у нас есть строковые значения, соответствующие названиям разных государств. Соответственно и узлы дерева содержат строковые ключи. Чтобы найти сотрудников, работающих в “UK”, нужно просмотреть все узлы, чтобы найти соответствующий, и извлечь из него ID всех строк, содержащих данное значение. В отличие от поиска по массиву, здесь нам потребуется всего log(N) операций. Описанная конструкция называется индексом БД.

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

Индекс В+дерева

Несмотря на высокую скорость поиска, дерево плохо работает в случаях, когда нужно получить несколько элементов в пределах двух значений. Временнaя сложность будет равна О(N), потому что нам придётся просмотреть каждый узел и сравнить его с заданными условиями. Более того, данная процедура требует большого количества операций ввода/вывода, ведь нужно считывать всё дерево. То есть нам нужен более эффективный способ запроса диапазона. В современных БД для этого используется модифицированная версия дерева — В+дерево. Его особенность в том, что информацию (ID строк связанной таблицы) хранят лишь самые нижние узлы («листья»), а все остальные узлы предназначены для оптимизации поиска по дереву.



Как видите, здесь вдвое больше узлов. «Узлы принятия решений» помогают найти нужные узлы, содержащие ID строк в таблице. Но сложность поиска всё ещё равна О(log(N)) (добавился один уровень узлов). Однако главной особенностью B-дерева является то, что «листья» образуют наследственные связи.

Допустим, нам нужно найти значения в диапазоне от 40 до 100:
  • Сначала ищем всё, что больше 40 или значения, ближайшего к нему, если 40 не существует. Совсем как в обычном дереве.
  • А затем, с помощью связей наследования, выбираем всё, что меньше 100.

Пусть дерево содержит N узлов, и нам нужно выбрать М наследников. Для поиска конкретного узла потребуется log(N) операций, как и в обычном дереве. Но найдя его, мы тратим только М операций на поиск М наследников. То есть суммарно нам потребуется М + log(N) операций, в отличие от N в случае с обычным деревом. Нам даже не нужно считывать дерево целиком, а только М + log(N) узлов, так что дисковая система задействуется меньше. Если значение М невелико (например, 200), а N — напротив, большое, (1 000 000), то выигрыш в скорости поиска будет очень значителен.

Но есть ложка дёгтя на этом празднике жизни. Если вы добавляете или убираете строки в БД, а, следовательно, и в связанном индексе В+дерева, то:
  • Необходимо сохранять порядок размещения узлов внутри В-дерева, иначе вы ничего не сможете найти.
  • Нужно, чтобы В+дерево состояло из как можно меньшего количества уровней, иначе временнaя сложность будет не О(log(N)), а О(N).

Иными словами, В+дерево должно быть самоуправляемым и самобалансирующимся. В связи с низкоуровневой оптимизацией, В+деревья должны быть полностью сбалансированы. К счастью, всё это можно сделать с помощью операций «умного» удаления и вставки. Но за это приходится платить: операции вставки и удаления в В+дереве имеют сложность О(log(N)). Так что наверняка многим из вас знаком такой совет: не надо увлекаться созданием большого количества индексов. В противном случае сильно падает производительность при добавлении/обновлении/удалении строк, поскольку БД приходится актуализировать и всевозможные индексы, а каждый из них требует О(log(N)) операций. К тому же индексы увеличивают нагрузку на диспетчер транзакций, об этом мы поговорим ниже.

Подробнее о В+деревьях можно почитать на Википедии, а также в статьях (один, два) от ведущих разработчиков MySQL. В них рассказывается о том, как InnoDB (движок MySQL) работает с индексами.

1.3.3. Хэш-таблица

Эта структура данных очень полезна для случаев, когда особенно важна скорость поиска. Понимание работы хэш-таблицы необходимо для последующего понимания такой важной операции, как хэш-соединение (hash join). Хэш-таблица зачастую используется для хранения некоторых внутренних данных (таблицы блокировок, буферного пула). Данная структура используется для быстрого поиска элементов по их ключам. Для построения хэш-таблицы нужны:
  • Ключ для каждого элемента.
  • Хэш-функция, вычисляющая хэши по ключам. Хэши ещё называют блоками.
  • Функция сравнения ключей. Найдя правильный блок, мы можем с помощью этой функции найти искомый элемент внутри блока.

Вот пример простой хэш-таблицы:



Здесь 10 блоков, в качестве хэш-функции брался модуль 10 от значения ключа. То есть для поиска нужного блока достаточно знать последнюю цифру значения ключа: если это 0, то элемент хранится в корзине 0, если 1, то в корзине 1, и т.д. В качестве функции сравнения используется операция сравнения двух целочисленных.

Допустим, нам нужно найти элемент 78:
  • Хэш-таблица вычисляет значение хэша, оно равно 8.
  • Обращаемся к блоку 8 и сразу находим искомый элемент.

То есть мы затратили всего две операции: на вычисление хэша и на поиск внутри блока.
  • Теперь поищем элемент 59:
  • Вычисляем хэш, он равен 9.
  • Обращаемся к блоку 9, первый элемент равен 99. Поскольку 99 не равно 59, то сравниваем со вторым элементом (9), потом с третьим (79), и так далее вплоть до последнего (29).
  • Искомый элемент отсутствует.

Итого мы затратили 7 операций.

Как видите, скорость поиска зависит от искомого значения. Изменим хэш-функцию, будет вычислять хэши по модулю 1 000 000 (то есть берём последние 6 цифр). В этом случае на поиск элемента 59 уйдёт лишь одна операция, поскольку в блоке 000059 нет никаких элементов. Поэтому крайне важно подобрать удачную хэш-функцию, которая будет генерировать блоки с очень небольшим количеством элементов.

В вышеприведённом примере нетрудно подобрать подходящий вариант. Но это слишком простой случай. Гораздо труднее выбрать хэш-функцию, если ключи:
  • Строковые (например, фамилии).
  • Двойные строковые (имена и фамилии).
  • Двойные строковые с датой (добавляются даты рождения)

и т.д.
Но если вам удалось подобрать хорошую хэш-функцию, то сложность поиска по таблице будет равна О(1).

Массив против хэш-таблицы

Почему бы не использовать одни массивы? Дело в том, что:
  • Хэш-таблицу можно загрузить в память наполовину, а остальное оставить на диске.
  • В случае с массивом вам придётся использовать смежное пространство памяти. И если вы загружаете большую таблицу, то очень сложно обеспечить достаточный объём этого самого смежного пространства.
  • Вы можете выбрать любые ключи для хэш-таблицы. Например, название государства И фамилию человека.

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

2. Общий обзор


Мы рассмотрели базовые компоненты БД. Теперь давайте отойдём назад и окинем взглядом всю картину.

БД представляет собой совокупность информации, к которой можно легко получить доступ и модифицировать. Но то же самое можно сказать и о группе файлов. По сути, простейшие БД, наподобие SQLite, как раз и представляют собой лишь кучки файлов. Но тут важно, как именно эти файлы организованы внутри и связаны между собой, поскольку SQLite позволяет:
  • Использовать транзакции для обеспечения сохранности и связанности данных.
  • Быстро обрабатывать данные вне зависимости от их объёма.

В общем виде структуру БД можно представить так:



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

Основные компоненты БД (Core Components):
  • Диспетчер процессов. Во многих БД имеется пул процессов/потоков, которыми нужно управлять. Причём в погоне за производительностью некоторые БД используют свои собственные потоки, а не предоставляемые ОС.
  • Диспетчер сети. Пропускная способность сети имеет большое значение, особенно для распределённых БД.
  • Диспетчер файловой системы. Первым «бутылочным горлышком» любой БД является производительность дисковой подсистемы. Поэтому очень важно иметь диспетчер, который идеально работает с файловой системой ОС или даже заменяет её.
  • Диспетчер памяти. Чтобы не упереться в невысокую производительность дисковой подсистемы, нужно иметь много оперативной памяти. А значит, нужно эффективно ею управлять, что и делает данный диспетчер. Особенно когда у вас много одновременных запросов, использующих память.
  • Диспетчер безопасности. Управляет аутентификацией и авторизацией пользователей.
  • Диспетчер клиентов. Управляет клиентскими соединениями.

Инструменты (Tools):
  • Диспетчер резервного копирования. Назначение очевидно.
  • Диспетчер восстановления. Используется для восстановления когерентного состояния БД после сбоя.
  • Диспетчер мониторинга. Занимается протоколированием всех активностей внутри БД и используется для наблюдения за её состоянием.
  • Диспетчер общего управления. Хранит метаданные (вроде наименований и структуры таблиц) и используется для управления базами, схемами, табличными пространствами и т.д.

Диспетчер запросов (Query Manager):
  • Парсер запросов. Проверяет их валидность.
  • Рерайтер запросов. Осуществляет предварительную оптимизацию.
  • Оптимизатор запросов.
  • Исполнитель запросов. Компилирует и исполняет.

Диспетчер данных (Data Manager):
  • Диспетчер транзакций. Занимается их обработкой.
  • Диспетчер кэша. Используется для отправки данных перед использованием и перед записью на диск.
  • Диспетчер доступа к данным. Управляет доступом к данным в дисковой подсистеме.

Далее мы рассмотрим, как БД управляет SQL-запросами с помощью:
  • Диспетчера клиентов.
  • Диспетчера запросов.
  • Диспетчера данных.

3. Диспетчер клиентов




Используется для управления соединениями с клиентами — веб-серверами или конечными пользователями/приложениями. Диспетчер клиентов обеспечивает разные способы доступа к БД с помощью как всем известных API (JDBC, ODBC, OLE-DB и т.д.), так и с помощью проприетарных.

Когда вы подключаетесь к БД:
  • Диспетчер сначала аутентифицирует вас (проверят логин и пароль), а потом авторизует для использования БД. Эти права доступа определяются вашим DBA.
  • Далее диспетчер проверяет, есть ли доступный процесс (или поток), который может обработать ваш запрос.
  • Также он сверяет, не находится ли база в состоянии высокой нагрузки.
  • Диспетчер может подождать, пока не высвободятся нужные ресурсы. Если период ожидания закончился, а они не высвободились, диспетчер закрывает соединение с сообщением об ошибке.
  • Если же ресурсы имеются, то диспетчер перенаправляет ваш запрос диспетчеру запросов.
  • Поскольку диспетчер клиентов передаёт и получает данные от диспетчера запросов, то он сохраняет их в буфере частями и отправляет вам.
  • При возникновении проблемы диспетчер прерывает соединение с каким-то объяснением и высвобождает ресурсы.

4. Диспетчер запросов




Именно он является сердцем БД. Здесь все плохо написанные запросы превращаются в быстроисполняемый код, затем происходит исполнение, а результат отправляется диспетчеру клиентов. Описанный процесс состоит из нескольких этапов:
  • Запрос сначала проверяется на валидность (парсится).
  • Затем он перезаписывается с целью исключения бесполезных операций и предварительной оптимизации.
  • Далее производится окончательная оптимизация для повышения производительности. После этого запрос трансформируется в план исполнения и доступа к данным.
  • План компилируется.
  • И исполняется.

Если вы хотите узнать больше, то можете изучить следующие материалы:
  • Access Path Selection in a Relational Database Management System. Статья 1979 года посвящена оптимизации.
  • Очень хорошая и глубокая презентация о том, как DB2 9.x оптимизирует запросы.
  • Не менее хорошая презентация о том, как тем же самым занимается PostgreSQL. Здесь информация подана в наиболее понятной форме.
  • Официальная документация SQL по оптимизации. Читается довольно легко, поскольку SQLite используется простые правила. К тому же это единственный официальный документ по данной теме.
  • Хорошая презентация о том, как SQL Server 2005 оптимизирует запросы.
  • Официальный документ об оптимизации в Oracle 12c.
  • Два теоретических курса по оптимизации запросов от автора книги “Database System Concepts”: первый и второй. Хороший материал, акцентирующий внимание на экономии операций ввода/вывода. Но для усвоения требуется хорошо владеть CS.
  • Ещё один теоретический курс, более доступный для понимания. Но он посвящён операторам объединения и управлению операциями ввода/вывода.

4.1. Парсер запросов


Каждый SQL-оператор отправляется в парсер и проверяется на правильность синтаксиса. Если вы сделаете ошибку в запросе, то парсер его отклонит. Например, напишете SLECT вместо SELECT.

Но этим функции парсера не ограничиваются. Он также проверяет, чтобы ключевые слова использовались в правильном порядке. Например, если WHERE будет идти до SELECT, то запрос будет отклонён.

Также парсер анализирует таблицы и их поля внутри запроса. Он использует метаданные БД для проверки:
  • Самого факта существования таблицы.
  • Наличия в ней полей.
  • Возможности осуществления операций с полями имеющихся типов. Например, нельзя сравнивать целочисленные со строковыми, или использовать функцию substring() применительно к целочисленному).

Далее парсер проверяет, имеете ли вы вообще право читать (или записывать) таблицы в запросе. Эти права доступа также задаются вашим DBA.

В ходе всех этих проверок SQL-запрос трансформируется во внутреннее представление (чаще всего в дерево). Если всё в порядке, то оно отправляется в рерайтер запросов.

4.2. Рерайтер запросов


В его задачи входит:
  • Предварительная оптимизация запроса.
  • Исключение ненужных операций.
  • Помощь оптимизатору в поиске наилучшего возможного решения.

Рерайтер применяет к запросу список известных правил. Если запрос всем им удовлетворяет, то он перезаписывается. Вот некоторые из этих правил:
  • Слияние представлений (видов). Если вы используете в запросе представление, то оно трансформируется с помощью SQL-кода.
  • Сведение подзапросов. Наличие подзапросов сильно затрудняет оптимизацию, так что рерайтер старается так модифицировать запрос, чтобы избавиться от подзапросов.

Например, этот запрос: 

SELECT PERSON.*
FROM PERSON
WHERE PERSON.person_key IN
(SELECT MAILS.person_key
FROM MAILS
WHERE MAILS.mail LIKE 'christophe%');

будет заменён на:

SELECT PERSON.*
FROM PERSON, MAILS
WHERE PERSON.person_key = MAILS.person_key
and MAILS.mail LIKE 'christophe%';


  • Исключение ненужных операций. Допустим, вы используете DISTINCT несмотря на то, что у вас применяется условие UNIQUE, предотвращающее появление не уникальных данных. В этом случае ключевое слово DISTINCT удаляется парсером.
  • Предотвращение ненужных объединений. Если вы дважды указали одно и то же условие объединения, поскольку одно из них было скрыто в представлении, или просто бессмысленно из-за транзитивности, то оно удаляется.
  • Арифметические вычисления. Если вы пишете что-то, требующее вычисления, то оно делается однократно в ходе перезаписи. Скажем, WHERE AGE > 10+2 трансформируется в WHERE AGE > 12. А TODATE (какая-то дата) заменяется на дату в соответствующем формате.
  • Partition pruning. Если вы используете партиционированные таблицы, рерайтер может найти подходящие партиции.
  • Перезапись материализованного представления. Если у вас есть материализованное представление, совпадающее с подмножеством предикатов в запросе, то рерайтер проверяет, является ли представление актуальным, и модифицирует запрос так, чтобы он использовал материализованное представление вместо таблиц.
  • Особые правила. Если у вас специфические правила модификации запроса (вроде политик Oracle), то рерайтер может их применить.
  • OLAP-трансформации. Трансформируются функции анализа/кадрирования, звездообразные объединения, свёртывание и т.д. Поскольку рерайтер и оптимизатор очень тесно взаимодействуют, то, скорее всего, OLAP-трансформации может осуществлять и оптимизатор, на усмотрение БД.

После применения политик запрос отправляется в оптимизатор, и там начинается самое веселье.

4.3. Статистика


Прежде чем перейти к рассмотрению оптимизирования запросов, давайте поговорим о статистике, поскольку без неё БД становится совершенно безмозглой. Если вы не скажете ей проанализировать собственные данные, она этого и не сделает, сделав очень плохие допущения.

Какого рода информация нужна БД?

Сначала давайте вспомним, как БД и ОС хранят данные. Для этого они используют такие минимально возможные сущности, как страницы или блоки (размером по 4 или 8 Кбайт по умолчанию). Если вам нужно сохранить 1 Кбайт, то на это всё-равно уйдёт целая страница. То есть вы попусту тратите много места в памяти и на диске.

Вернёмся к нашей статистике. Когда вы просите БД собрать статистику, она:
  • Подсчитывает количество строк/страниц в таблице.
  • Для каждой колонки:
    • Считает количество уникальных значений.
    • Определяет длину значений данных (мин, макс, среднее).
    • Определяет диапазон значений данных (мин, макс, среднее).
  • Собирает информацию об индексах БД.

Вся эта информация помогает оптимизатору спрогнозировать количество операций ввода/вывода, а также потребление ресурсов процессора и памяти при исполнении запроса.

Очень большое значение имеет статистика по каждой колонке. Например, нам нужно в таблице объединить две колонки: «фамилия» и «имя». Благодаря статистике БД знает, что в ней содержится 1 000 уникальных значений «имя» и 1 000 000 — «фамилия». Поэтому база объединит данные именно в таком порядке — «фамилия, имя», а не «имя, фамилия»: это требует гораздо меньше операций сравнения, поскольку вероятность совпадения фамилий гораздо ниже, и в большинстве случаев для сравнения достаточно брать 2-3 первые буквы фамилии.

Но всё это базовая статистика. Можно также попросить БД собрать дополнительную статистику и построить гистограммы. Они дают представление о распределении значений внутри колонок. Например, определить самые часто встречающиеся значения, квантили и т.д. Эта дополнительная статистика помогает БД ещё лучше планировать запрос. Особенно в случае с предикатами равенства (WHERE AGE=18) или предикатами диапазонов (WHERE AGE > 10 AND AGE < 40), поскольку БД будет лучше представлять количество колонок, имеющих отношение к этим предикатам (селективность, избирательность).

Статистика хранится в виде метаданных. Например, вы можете найти её в:
  • Oracle: USER/ALL/DBA_TABLES и USER/ALL/DBA_TAB_COLUMNS
  • DB2: SYSCAT.TABLES и SYSCAT.COLUMNS

Статистику нужно регулярно обновлять. Нет ничего хуже, чем БД, считающая, что состоит из 500 строк, в то время как в ней их 1 000 000. К сожалению, на сбор статистики уходит некоторое время, поэтому в большинстве БД по умолчанию эта операция не выполняется автоматически. Когда у вас миллионы записей, то собрать по ним статистику довольно затруднительно. В этом случае можно собирать только базовую информацию, или брать небольшую часть базы (например, 10%) и собирать по ней полную статистику. Но тут есть риск того, что оставшаяся часть данных может существенно отличаться, и значит ваша статистика окажется нерепрезентативной. А это приведёт к неправильному планированию запроса и увеличению времени его исполнения.

Если вы хотите узнать больше о статистике, читайте документацию к своим БД. Лучше всего это описано для PostgreSQL.

4.4. Оптимизатор запросов


Все современные БД используют CBO (Cost Based Optimization), стоимостную оптимизацию. Суть её заключается в том, что для каждой операции определяется её «стоимость», а затем общая стоимость запроса уменьшается с помощью использования наиболее «дешёвых» цепочек операций.

Для лучшего понимания стоимостной оптимизации мы рассмотрим три распространённых способа объединения двух таблиц и увидим, как даже простой запрос на объединение может превратиться в кошмар для оптимизатора. В нашем рассмотрении мы будем ориентироваться на временн?ю сложность, хотя оптимизатор вычисляет «стоимость» в ресурсах процессора, памяти и операциях ввода/вывода. Просто временнaя сложность — понятие приблизительное, а для определения необходимых ресурсов процессора нужно подсчитывать все операции, включая добавление, операторы if, умножение, итерации и т.д.

Кроме того:
  • Для выполнения каждой высокоуровневой операции процессор выполняет разное количество низкоуровневых операций.
  • Стоимость процессорных операций (с точки зрения циклов) разная у разных видов процессоров, то есть она зависит от конкретной архитектуры ЦПУ.

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

4.4.1. Индексы

Мы говорили о них, когда рассматривали В-деревья. Как вы помните, индексы уже отсортированы. К слову, есть и другие виды индексов, например, битовые (bitmap index). Но они не дают выигрыша с точки зрения использования процессора, памяти и дисковой подсистемы по сравнению с индексами В-деревьев. Кроме того, многие современные БД могут динамически создавать временные индексы для текущих запросов, если это поможет уменьшить стоимость выполнения плана.

4.4.2. Способы обращений

Прежде чем применять операторы объединения, нужно сначала получить необходимые данные. Сделать это можно следующими способами.
  • Полное сканирование. БД просто считывает целиком таблицу или индекс. Как вы понимаете, для дисковой подсистемы индекс читать дешевле, чем таблицу.
  • Сканирование диапазона. Используется, например, когда вы используете предикаты наподобие WHERE AGE > 20 AND AGE < 40. Конечно, для сканирования диапазона индекса вам нужно иметь индекс для поля AGE.

    В первой части статьи мы уже выяснили, что временнaя сложность запроса диапазона определяется как M + log(N), где N — количество данных в индексе, а М — предположительное количество строк внутри диапазона. Значения обеих этих переменных нам известно благодаря статистике. При сканировании диапазона считывается лишь часть индекса, поэтому данная операция стоит меньше по сравнению с полным сканированием.
  • Сканирование по уникальным значениям. Используется в тех случаях, когда вам нужно получить из индекса только какое-то одно значение.
  • Обращение по ID строки. Если БД использует индекс, то б?льшую часть времени она будет заниматься поиском связанных с ним строк. Например, мы делаем такой запрос:

    SELECT LASTNAME, FIRSTNAME from PERSON WHERE AGE = 28

    Если у нас есть индекс для колонки возраста, то оптимизатор воспользуется индексом для поиска всех 28-летних, а затем запросит ID соответствующих строк таблицы, поскольку индекс содержит информацию только о возрасте.

    Допустим, у нас другой запрос:

    SELECT TYPE_PERSON.CATEGORY from PERSON, TYPE_PERSON
WHERE PERSON.AGE = TYPE_PERSON.AGE

    Для объединения с TYPE_PERSON будет использоваться индекс по колонке PERSON. Но поскольку мы не запрашивали информацию у таблицы PERSON, то и обращаться к ней по ID строк никто не будет.

    Данный подход хорош только при небольшом количестве обращений, поскольку он дорог с точки зрения ввода/вывода. Если вам нужно часто обращаться по ID, то лучше воспользоваться полным сканированием.
  • Другие способы. О них можно почитать в документации Oracle. В разных БД могут использоваться разные названия, но принципы везде одни и те же.

4.4.3. Операции объединения

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

Когда мы объединяем две зависимости, алгоритмы объединения управляют ими по-разному. Допустим, A JOIN B является объединением А и В, где А является внешней зависимостью, а В — внутренней.

Чаще всего стоимость A JOIN B не равна стоимости B JOIN A.

Предположим, что внешняя зависимость содержит N элементов, а внутренняя — М. Как вы помните, оптимизатору известных эти значения благодаря статистике. N и M являются кардинальными числами зависимостей.
  • Объединение с помощью вложенных циклов. Это простейший способ объединения.



    Работает он так: для каждой строки внешней зависимости ищутся совпадения по всем строкам внутренней зависимости.

    Пример псеводокода:

    nested_loop_join(array outer, array inner)
  for each row a in outer
    for each row b in inner
      if (match_join_condition(a,b))
        write_result_in_output(a,b)
      end if
    end for
   end for

    Поскольку здесь двойная итерация, временнaя сложность определяется как О(N*M).

    Для каждой из N строк внешней зависимости нужно считать М строк внешней зависимости. То есть этот алгоритм требует N + N*M чтений с диска. Если внутренняя зависимость достаточно мала, то можно поместить её целиком в память, и тогда на долю дисковой подсистемы придётся только M + N чтений. Так что рекомендуется делать внутреннюю зависимость как можно компактнее, чтобы загнать в память.

    С точки зрения временн?й сложности разницы никакой.

    Также можно заменить внутреннюю зависимость индексом, это позволит сэкономить операции ввода/вывода.
    Если внутренняя зависимость не влезает в память целиком, можно использовать другой алгоритм, более экономно использующий диск.
    • Вместо чтения обеих зависимостей построчно, они считываются группами строк (bunch), при этом в памяти сохраняется по одной группе из каждой зависимости.
    • Строки из этих групп сравниваются между собой, а найденные совпадения сохраняются отдельно.
    • Затем в память подгружаются новые группы и тоже сравниваются друг с другом.

    И так далее, пока группы не закончатся.

    Пример алгоритма:

    // improved version to reduce the disk I/O.
nested_loop_join_v2(file outer, file inner)
  for each bunch ba in outer
  // ba is now in memory
    for each bunch bb in inner
	    // bb is now in memory
		for each row a in ba
          for each row b in bb
            if (match_join_condition(a,b))
              write_result_in_output(a,b)
            end if
          end for
       end for
    end for
   end for

    В данном случае временнaя сложность остаётся той же, зато снижается количество обращений к диску: (количество групп внешней + количество групп внешней * количество групп внутренней). С увеличением размера групп ещё больше уменьшается количество обращений к диску.

    Примечание: в этом алгоритме при каждом обращении считывается больший объём данных, но это не играет роли, поскольку обращения последовательные.
  • Хэш-объединение. Это более сложная операция, но во многих случаях её стоимость ниже.



    Алгоритм следующий:
    1. Считываются все элементы из внутренней зависимости.
    2. В памяти создаётся хэш-таблица.
    3. Один за другим считываются все элементы из внешней зависимости.
    4. Для каждого элемента вычисляется хэш (с помощью соответствующей функции из хэш-таблицы), чтобы можно было найти соответствующий блок во внутренней зависимости.
    5. Элементы из блока сравниваются с элементами из внешней зависимости.

    Чтобы оценить этот алгоритм с точки зрения временн?й сложности, нужно сделать несколько допущений:
    • Внутренняя зависимость содержит Х блоков.
    • Хэш-функция распределяет хэши почти одинаково для обеих зависимостей. То есть все блоки имеют идентичный размер.
    • Стоимость поиска соответствия между элементами внешней зависимости и всеми элементами внутри блока равна количеству элементов внутри блока.

    Тогда временнaя сложность будет равна:

    (М / Х) * (N / X) + стоимость_создания_хэш-таблицы(М) + стоимость_хэш-функции * N

    А если хэш-функция создаёт достаточное маленькие блоки, то временнaя сложность будет равна О(М + N).

    Есть ещё один способ хэш-объединения, более экономно расходующий память и не требующий больше операций ввода/вывода:
    1. Вычисляются хэш-таблицы для обеих зависимостей.
    2. Кладутся на диск.
    3. А затем сравниваются поведёрно друг с другом (один блок загружается в память, а второй считывается построчно).

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

    Операцию объединения можно разделить на два этапа:
    1. (Опционально) сначала осуществляется объединение сортировкой, когда оба набора входных данных сортируются по ключам объединения.
    2. Затем осуществляется слияние.

    Сортировка

    Алгоритм сортировки слиянием уже обсуждался выше, в данном случае он вполне себя оправдывает, если вам важно экономить память.

    Но бывает, что наборы данных поступают уже отсортированными, например:
    • Если таблица организована нативно.
    • Если зависимость является индексом при наличии условия объединения.
    • Если объединение происходит с промежуточным отсортированным результатом.

    Объединение слиянием



    Эта операция очень похода на операцию слияния при процедуре сортировки слиянием. Но вместо выбора всех элементов обеих зависимостей мы выбираем только равные элементы.
    1. Сравниваются два текущих элемента обеих зависимостей.
    2. Если они равны, то заносятся в результирующую таблицу, и далее сравниваются два следующих элемента, по одному из каждой зависимости.
    3. Если они не равны, то сравнение повторяется, но вместо наименьшего из двух элементов берётся следующий элемент из той же зависимости, поскольку вероятность совпадения в этом случае выше.
    4. Шаги 1-3 повторяются, пока на закончатся элементы одной из зависимостей.

    Если обе зависимости уже отсортированы, то временнaя сложность равна О(N + M).

    Если обе зависимости ещё нужно отсортировать, то временнaя сложность равна O(N * Log(N) + M * Log(M)).

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

    mergeJoin(relation a, relation b)
  relation output
  integer a_key:=0;
  integer b_key:=0;

  while (a[a_key]!=null and b[b_key]!=null)
    if (a[a_key] < b[b_key]) a_key++; else if (a[a_key] > b[b_key])
      b_key++;
    else //Join predicate satisfied
      write_result_in_output(a[a_key],b[b_key])
      //We need to be careful when we increase the pointers
      integer a_key_temp:=a_key;
      integer b_key_temp:=b_key;
      if (a[a_key+1] != b[b_key])
        b_key_temp:= b_key + 1;
      end if
      if (b[b_key+1] != a[a_key])
        a_key_temp:= a_key + 1;
      end if
      if (b[b_key+1] == a[a_key] && b[b_key] == a[a_key+1])
        a_key_temp:= a_key + 1;
        b_key_temp:= b_key + 1;
      end if
      a_key:= a_key_temp;
      b_key:= b_key_temp;
    end if
  end while

Какой алгоритм выбрать?

Если бы существовал самый лучший способ объединения, то не существовало бы всех этих разновидностей. Так что ответ на этот вопрос зависит от кучи факторов:
  • Объём доступной памяти. Если её мало, забудьте о мощном хэш-объединении. По крайне мере, о его выполнении целиком в памяти.
  • Размер двух наборов входных данных. Если у вас одна таблица большая, а вторая очень маленькая, то быстрее всего сработает объединение с помощью вложенных циклов, потому что хэш-объединение подразумевает дорогую процедуру создания хэшей. Если у вас две очень большие таблицы, то объединение с помощью вложенных циклов поглотит все ресурсы процессора.
  • Наличие индексов. Если у вас два индекса В-деревьев, то лучше использовать объединение слиянием.
  • Нужно ли сортировать результат. Возможно, вы захотите использовать дорогое объединение слиянием (с сортировкой), если работаете с несортированными наборами данных. Тогда на выходе вы получите сортированные данные, которые удобнее объединить с результатами другого объединения. Или потому что запрос косвенно или явно предполагает получение данных, отсортированных операторами ORDER BY/GROUP BY/DISTINCT.
  • Отсортированы ли выходные зависимости. В данном случае лучше использовать объединение слиянием.
  • Зависимости каких типов вы используете. Объединение по эквивалентности (таблицаА.колонка1 = таблицаБ.колонка2)? Внутренние зависимости, внешние, декартово произведение или самообъединение (self-join)? В разных ситуациях некоторые способы объединения не работают.
  • Распределение данных. Если данные отклонены по условию объединения (например, вы объединяете людей по фамилиям, но част встречаются однофамильцы), то ни в коем случае нельзя использовать хэш-объединение. Иначе хэш-функция будет создавать корзины с очень плохим внутренним распределением.
  • Нужно ли выполнять объединение в несколько процессов/потоков.

Алчущие знаний могут углубиться в документацию по DB2, ORACLE и SQL Server.

4.4.4. Упрощённые примеры

Допустим, нам нужно объединить пять таблиц, чтобы получить полное представление о неких людях. Каждый человек может иметь:
  • Несколько номеров мобильных телефонов.
  • Несколько адресов электронной почты.
  • Несколько физических адресов.
  • Несколько номеров банковских счетов.

То есть нужно быстро дать ответ на этот запрос:

SELECT * from PERSON, MOBILES, MAILS,ADRESSES, BANK_ACCOUNTS
WHERE
PERSON.PERSON_ID = MOBILES.PERSON_ID
AND PERSON.PERSON_ID = MAILS.PERSON_ID
AND PERSON.PERSON_ID = ADRESSES.PERSON_ID
AND PERSON.PERSON_ID = BANK_ACCOUNTS.PERSON_ID

Оптимизатору нужно найти наилучший способ обработки данных. Но есть две проблемы:
  1. Какой способ объединения использовать? Есть три варианта (хэш-объединение, объединение слиянием, объединение с помощью вложенных циклов), с возможностью использования 0, 1 или 2 индексов. Не говоря уже о том, что индексы тоже могут быть разными.
  2. В каком порядке нужно производить объединение?

Например, ниже представлены возможные планы для трёх объединений четырёх таблиц:



Исходя из описанного, какие есть варианты действий?
  1. Использовать брутфорс-подход. С помощью статистики подсчитать стоимость каждого из возможных планов исполнения запроса и выбрать самый дешёвый. Но вариантов довольно много. Для каждого порядка объединения можно использовать три разных способа объединения, итого 34=81 возможных планов исполнения. В случае с бинарным деревом задача выбора порядка объединения превращается в задачу о перестановках, и количество вариантов равно (2 * 4)! / (4 + 1)!.. В результате, в данном очень упрощённом примере общее количество возможных планов исполнения запроса составляет 34 * (2 * 4)! / (4 + 1)! = 27 216. Если добавить к этому варианты, когда при объединении слиянием используется 0, 1 или 2 индекса В-дерева, то количество возможных планов повышается до 210 000. Мы уже упоминали, что это ОЧЕНЬ ПРОСТОЙ запрос?
  2. Поплакать и уволиться. Очень соблазнительно, но непродуктивно, да и деньги нужны.
  3. Попробовать несколько планов и выбрать самый дешёвый. Раз обсчитать стоимость всех возможных вариантов не получается, можно взять произвольный тестовый набор данных и прогнать по нему все виды планов, чтобы оценить их стоимость и выбрать лучший.
  4. Применить «умные» правила для уменьшения количества возможных планов.
    Есть два типа правил:
    1. «Логические», с помощью которых можно исключить бесполезные варианты. Но они далеко не всегда применимы. Например, «при объединении с помощью вложенных циклов внутренняя зависимость должна являться наименьшим набором данных».
    2. Можно не искать наиболее выгодное решение и применить более жёсткие правила для уменьшения числа возможных планов. Скажем, «если зависимость мала, используем объединение с помощью вложенных циклов, но никогда — объединение слиянием или хэш-объединение».

Даже столь простой пример ставит нас перед огромным выбором. А в реальных запросах могут присутствовать и другие операторы отношения: OUTER JOIN, CROSS JOIN, GROUP BY, ORDER BY, PROJECTION, UNION, INTERSECT, DISTINCT и т.д. То есть количество возможных планов исполнения будет ещё больше.

Так как же БД делает выбор?

4.4.5. Динамическое программирование, «жадный» алгоритм и эвристика

Реляционная БД использует разные подходы, о которых было сказано выше. И задачей оптимизатора является поиск подходящего решения в течение ограниченного времени. В большинстве случаев оптимизатор ищет не наилучшее, а просто хорошее решение.

Брутфорс может подойти в случае с маленькими запросами. А благодаря способам исключения ненужных вычислений даже для запросов среднего размера можно использовать грубую мужскую силу. Это называется динамическим программированием.

Его суть заключается в том, что многие планы исполнения очень похожи.



На этой иллюстрации все четыре плана используют поддерево A JOIN B. Вместо вычисления его стоимости для каждого плана, мы можем посчитать его лишь раз и затем использовать эти данные столько, сколько нужно. Иными словами, с помощью мемоизации мы решаем проблему перекрытия, то есть избегаем лишних вычислений.

Благодаря такому подходу вместо временн?й сложности (2*N)!/(N+1)! мы получаем «всего лишь» 3N. Применительно к предыдущему примеру с четырьмя объединениями это означает уменьшение количества вариантов с 336 до 81. Если взять запрос с 8 объединениями (небольшой запрос), то уменьшение сложности будет с 57 657 600 до 6 561.

Если вы уже знакомы с динамическим программированием или алгоритмизацией, можете поиграться с этим алгоритмом:

procedure findbestplan(S)
if (bestplan[S].cost infinite)
   return bestplan[S]
// else bestplan[S] has not been computed earlier, compute it now
if (S contains only 1 relation)
         set bestplan[S].plan and bestplan[S].cost based on the best way
         of accessing S  /* Using selections on S and indices on S */
     else for each non-empty subset S1 of S such that S1 != S
   P1= findbestplan(S1)
   P2= findbestplan(S - S1)
   A = best algorithm for joining results of P1 and P2
   cost = P1.cost + P2.cost + cost of A
   if cost < bestplan[S].cost
       bestplan[S].cost = cost
      bestplan[S].plan = “execute P1.plan; execute P2.plan;
                 join results of P1 and P2 using A”
return bestplan[S]

Динамическое программирование можно использовать и для более крупных запросов, но придётся вводить дополнительные правила (эвристику), чтобы уменьшить число возможных планов:
  • Если мы анализируем только какой-то один тип планов (например, следование по левым веткам дерева), то вместо 3N получим сложность на уровне N*2N.



  • Добавление логических правил («если таблица является индексом для данного предиката, использовать объединение слиянием только для индекса, а не таблицы») помогает уменьшить число вариантов с небольшим риском исключения наилучших решений.
  • Добавление правил «на лету» (например, «выполнить операции объединения ДО всех остальных операций отношений») также сильно помогает уменьшить широту выбора.

Жадные алгоритмы

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

В данном случае план исполнения запроса строится пошагово с помощью некоего правила (эвристики). Благодаря ему жадный алгоритм ищет наилучшее решение для каждого этапа по отдельности. План начинается с оператор JOIN, а затем на каждом этапе добавляется новый JOIN в соответствии с правилом.

Рассмотрим простой пример. Возьмём запрос с 4 объединениями 5 таблиц (A, B, C, D и E). Несколько упростим задачу и представим, что единственным вариантом является объединение с помощью вложенных алгоритмов. Будем использовать правило «применять объединение с наименьшей стоимостью».
  • Начинаем с одной из таблиц, например, А.
  • Вычисляем стоимость каждого объединения с А (она будет как в роле внешней, так и внутренней зависимости).
  • Находим, что дешевле всего нам обойдётся A JOIN B.
  • Затем вычисляем стоимость каждого объединения с результатом A JOIN B (его тоже рассматриваем в двух ролях).
  • Находим, что выгоднее всего будет (A JOIN B) JOIN C.
  • Опять делаем оценку возможных вариантов.
  • …
  • В конце получаем такой план исполнения запроса: (((A JOIN B) JOIN C) JOIN D) JOIN E)/

Тот же алгоритм можно применить для оценки вариантов, начинающихся с таблицы B, затем с C и т.д. В результате получим пять планов, из которых выбираем самый дешёвый.

Данный алгоритм называется «алгоритм ближайшего соседа».

Не будем углубляться в подробности, но при хорошем моделировании сложности сортировки N*log(N) данная проблема может быть легко решена. Временнaя сложность алгоритма равна О(N*log(N)) вместо О(3N) для полной версии с динамическим программированием. Если у вас большой запрос с 20 объединениями, то это будет 26 против 3 486 784 401. Большая разница, верно?

Но есть нюанс. Мы предполагаем, что если найдём наилучший способ объединения двух таблиц, то получим самую низкую стоимость при объединении результатом предыдущих объединений со следующими таблицами. Однако даже если A JOIN B будет самым дешёвым вариантом, то (A JOIN C) JOIN B может иметь стоимость ниже, чем (A JOIN B) JOIN C.

Так что если вам позарез нужно найти самый дешёвый план всех времён и народов, то можно посоветовать многократно прогонять жадные алгоритмы с использованием разных правил.

Другие алгоритмы

Если вы уже сыты по горло всеми этими алгоритмами, то можете пропустить эту главу. Она не обязательна для усвоения всего остального материала.

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

Ищутся варианты замены динамического программирования для исполнения больших запросов. Те же жадные алгоритмы являются подмножеством эвристических алгоритмов. Они действуют сообразно правилу, запоминают результат одного этапа и используют его для поиска лучшего варианта для следующего этапа. И алгоритмы, которые не всегда используют решение, найденное для предыдущего этапа, называются эвристическими.

В качестве примера можно привести генетические алгоритмы:
  • Каждое решение представляет собой план полного исполнения запроса.
  • Вместо одного решения (плана) алгоритм на каждом этапе формирует Х решений.
  • Сначала создаётся Х планов, делается это случайным образом.
  • Из них сохраняются только те планы, чья стоимости удовлетворяет некоему критерию.
  • Затем эти планы смешиваются, что бы создать Х новых планов.
  • Некоторые из новых планов модифицируются случайным образом.
  • Предыдущие три шага повторяются Y раз.
  • Из планов последнего цикла мы получаем наилучший.

Чем больше циклов, тем более дешёвый план можно рассчитать. Естественный отбор, закрепление признаков, вот это всё.
Кстати, генетические алгоритмы интегрированы в PostgreSQL.

В БД используются и такие эвристические алгоритмы, как симулированная нормализация (Simulated Annealing), итеративное улучшение (Iterative Improvement), двухфазная оптимизация (Two-Phase Optimization). Но не факт, что они применяются в корпоративных системах, возможно, их удел — исследовательские продукты.

4.4.6. Настоящие оптимизаторы

Тоже необязательная глава, можно и пропустить.

Давайте отойдём от теоретизирования и рассмотрим реальные примеры. Например, как работает оптимизатор SQLite. Это «лёгкая» БД, использующая простую оптимизацию на основе жадного алгоритма с дополнительными правилами:
  • SQLite никогда не меняет порядок таблиц в операции CROSS JOIN.
  • Используется объединение с помощью вложенных циклов.
  • Внешние объединения всегда оцениваются в том порядке, в котором они осуществлялись.
  • Вплоть до версии 3.8.0 для поиска наилучшего плана исполнения запроса используется жадный алгоритм «ближайшего соседа» (Nearest Neighor). А с версии 3.8.0 применяется «N ближайших соседей» (N3, N Nearest Neighbors).

А вот другой пример. Если почитать документацию IBM DB2, то мы узнаем, что её оптимизатор используется 7 разных уровней оптимизации:
  • Жадные алгоритмы:
    • 0 — минимальная оптимизация. Используется сканирование индекса, объединение с помощью вложенных циклов и исключение перезаписи некоторых запросов.
    • 1 — низкая оптимизация
    • 2 — полная оптимизация
  • Динамическое программирование:
    • 3 — средняя оптимизация и грубая аппроксимация
    • 5 — полная оптимизация, используются все эвристические методики
    • 7 — то же самое, но без эвристики
    • 9 — максимальная оптимизация любой ценой, без оглядки на затрачиваемые усилия. Оцениваются все возможные способы объединения, включая декартовы произведения.

По умолчанию применяется уровень 5. Сюда входит:
  • Сбор всей возможной статистики, включая частотные распределения и квантили.
  • Применение всех правил перезаписи запросов, включая составление табличного маршрута для материализованных запросов). Исключение составляют правила, требующие интенсивных вычислений, применяемые для очень ограниченного числа случаев.
  • При переборе вариантов объединения с помощью динамического программирования:
    • Ограниченно используется составная внутренняя зависимость.
    • Для звездообразных схем с таблицами преобразования ограниченно используются декартовы произведения.
  • Рассматривается широкий диапазон способов доступа, включая предварительную выборку списка (об этом ниже), специальную операцию с индексами AND и составление табличного маршрута для материализованных запросов.

Конечно, разработчики не делятся подробностями об эвристике, используемой в их продукте, ведь оптимизатор — едва ли не самая важная часть БД. Однако известно, что по умолчанию для определения порядка объединения используется динамическое программирование, ограничиваемое эвристикой.

Прочие условия (GROUP BY, DISTINCT и т.д.) обрабатываются простыми правилами.

4.4.7. Кэш плана запросов

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

Исполнитель запросов


На данном этапе наш план уже оптимизирован. Он перекомпилируется в исполняемый код и, если ресурсов достаточно, исполняется. Операторы, содержащиеся в плане (JOIN, SORT BY и т.д.) могут обрабатываться как последовательно, так и параллельно, решение принимает исполнитель. Для получения и записи данных он взаимодействует с диспетчером данных.

5. Диспетчер данных




Диспетчер запросов исполняет запрос и нуждается в данных из таблиц и индексов. Он запрашивает их у диспетчера данных, но тут есть две трудности:
  • Реляционные БД используют транзакционную модель. Нельзя в конкретный момент времени получить любые желаемые данные, потому что в это время они могут кем-то использоваться/модифицироваться.
  • Извлечение данных — самая медленная операция в БД. Поэтому диспетчеру данных нужно уметь прогнозировать свою работу, чтобы своевременно заполнять буфер памяти.

5.1. Диспетчер кэша


Как уже не раз говорилось, самым узким местом в БД является дисковая подсистема. Поэтому для увеличения производительности используется диспетчер кэша.



Вместо того, чтобы получать данные напрямую от файловой системы, исполнитель запросов обращается за ними к диспетчеру кэша. Тот использует содержащийся в памяти буферный пул, что позволяет радикально увеличить производительность БД. В цифрах это трудно оценить, поскольку многое зависит от того, что вам нужно:
  • Последовательный доступ (полное сканирование) или случайный (доступ по ID строки).
  • Читать или записывать.

Также большое значение имеет тип накопителей, используемых в дисковой системе: «винчестеры» с разной скоростью вращения шпинделя, SSD, наличие RAID в разных конфигурациях. Но можно сказать, что использование памяти в 100-100 000 раз быстрее, чем диска.

Однако тут мы сталкиваемся с другой проблемой. Диспетчеру кэша нужно положить данные в память ДО того, как они понадобятся исполнителю запросов. Иначе тому придётся ждать их получения с медленного диска.

5.1.1. Упреждение

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

Когда исполнитель обрабатывает первую порцию данных, он просит диспетчер кэша заранее подгрузить следующую порцию. А когда переходит к её обработке, то просит ДК подгрузить третью и подтверждает, что первую порцию можно удалить из кэша.

Диспетчер кэша хранит эти данные в буферном пуле. Он также добавляет к ним сервисную информацию (триггер, latch), чтобы знать нужны ли они ещё в буфере.

Иногда исполнитель не знает, какие данные ему будут нужны, или некоторые БД не имеют подобного функционала. Тогда используется спекулятивное упреждение (speculative prefetching) (например, если исполнитель запрашивает данные 1, 3, 5, то наверняка запросит в будущем 7, 9, 11) или последовательное упреждение (sequential prefetching) (в данном случае ДК просто подгружает с диска следующую по порядку порцию данных.

Для контроля качества упреждения в современных БД используется метрика «коэффициент использования буфера/кэша» (buffer/cache hit ratio). Она показывает, как часто запрашиваемые данные оказываются в кэше, без необходимости обращения к диску. Однако низкое значение коэффициента не всегда говорит о плохом использовании кэша. Подробнее об этом можно почитать в документации Oracle.

Нельзя забывать, что буфер ограничен объёмом доступной памяти. То есть для загрузки одних данных нам приходится периодически удалять другие. Заполнение и очистка кэша потребляет часть ресурсов дисковой подсистемы и сети. Если у вас есть часто исполняемый запрос, то было бы контрпродуктивно каждый раз загружать и очищать используемые им данные. Для решения данной проблемы в современных БД используется стратегия замены буфера.

5.1.2. Стратегии замены буфера

Большинство БД (по крайне мере, SQL Server, MySQL, Oracle и DB2) используют для этого алгоритм LRU (Least Recently Used). Он предназначен для поддержания в кэше тех данных, которые недавно использовались, а значит велика вероятность, что они могут понадобиться снова.



Для облегчения понимания работы алгоритма примем, что данные в буфере на блокируются триггерами (latch), а значит могут быть удалены. В нашем примере буфер может хранить три порции данных:
  1. Диспетчер кэша используется данные 1 и кладёт их в пустой буфер.
  2. Затем он использует данные 4 и тоже отправляет их в буфер.
  3. То же самое делается и с данными 3.
  4. Далее берутся данные 9. Но буфер-то уже заполнен. Поэтому из него удаляются данные 1, так как они не использовались дольше всего. После этого в буфер помещаются данные 9.
  5. Диспетчер кэша снова использует данные 4. Они уже есть в буфере, поэтому помечаются как последние использованные.
  6. Снова становятся востребованы данные 1. Чтобы их поместить в буфер, из него удаляются данные 9, как не использовавшиеся дольше всего.

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

Улучшения алгоритма

Чтобы этого не произошло, в некоторых БД используются специальные правила. Согласно документации Oracle:

«Для очень больших таблиц обычно используется прямой доступ, то есть блоки данных считываются напрямую, чтобы избежать переполнения буфера кэша. Для таблиц среднего размера может использоваться как прямой доступ, так и чтение из кэша. Если система решит использовать кэш, то БД помещает блоки данных в конец списка LRU, чтобы предотвратить очистку буфера».

Также используется улучшенная версия LRU — LRU-K. В SQL Server применяется LRU-K при К = 2. Суть этого алгоритма в том, что при оценке ситуации он учитывает больше информации о прошлых операциях, а не только запоминает последние использованные данные. Буква К в названии означает, что алгоритм принимает во внимание, какие данные использовались последние К раз. Им присваивается определённый вес. Когда в кэш загружаются новые данные, то старые, но часто используемые не удаляются, потому что их вес выше. Конечно, если данные больше не используются, то они всё-таки будут удалены. И чем дольше данные остаются невостребованными, тем сильнее уменьшается со временем их вес.

Вычисление веса довольно накладно, поэтому в SQL Server используется LRU-K при К равном всего лишь 2. При некотором увеличении значения К эффективность алгоритма улучшается. Вы можете ближе познакомиться с ним благодаря одной работе 1993-го года.

Другие алгоритмы

Конечно, LRU-K не единственное решение. Существуют также 2Q и CLOCK (оба похожи на LRU-K), MRU (Most Recently Used, в котором используется логика LRU, но применяется другое правило, LRFU (Least Recently and Frequently Used) и т.д. В некоторых БД можно выбирать, какой алгоритм будет использоваться.

5.1.3. Буфер записи

Мы говорили только о буфере чтения, но БД используют и буферы записи, которые накапливают данные и сбрасывают на диск порциями, вместо последовательной записи. Это позволяет экономить операции ввода/вывода.
Помните, что буферы хранят страницы (неделимые единицы данных), а не ряды из таблиц. Страница в буферном пуле называется «грязной», если она модифицирована, но не записана на диск. Есть много разных алгоритмов, с помощью которых выбирается время записи грязных страниц. Но это во многом связано с понятием транзакций.

5.2. Диспетчер транзакций


В его обязанности входит отслеживание, чтобы каждый запрос исполнялся с помощью собственной транзакции. Но прежде чем поговорить о диспетчере, давайте проясним концепцию ACID-транзакций.

5.2.1. «Под кислотой» (игра слов, если кто не понял)

ACID-транзакция (Atomicity, Isolation, Durability, Consistency) — это элементарная операция, единица работы, которая удовлетворяет 4 условиям:
  • Атомарность (Atomicity). Нет ничего «меньше» транзакции, никакой более мелкой операции. Даже если транзакция длится 10 часов. В случае неудачного выполнения транзакции система возвращается в состояние «до», то есть транзакция откатывается.
  • Изолированность (Isolation). Если в одно время выполняются две транзакции А и В, то их результат не должен зависеть от того, завершилась ли одна из них до, во время или после исполнения другой.
  • Надёжность (Durability). Когда транзакция зафиксирована (commited), то есть успешно завершена, использовавшиеся ею данные остаются в БД вне зависимости от возможных происшествий (ошибки, падения).
  • Консистентность (согласованность) (Consistency). В БД записываются только валидные данные (с точки зрения реляционных и функциональных связей). Консистентность зависит от атомарности и изолированности.




Во время выполнения какой-либо транзакции можно исполнять различные SQL-запросы на чтение, создание, обновление и удаление данных. Проблемы начинаются, когда две транзакции используют одни и те же данные. Классический пример — перевод денег со счёта А на счёт Б. Допустим, у нас есть две транзакции:
  • Т1 берёт $100 со счёта А и отправляет их на счёт Б.
  • Т2 берёт $50 со счёта А и тоже отправляет их на счёт Б.

Теперь рассмотрим эту ситуацию с точки зрения ACID-свойств:
  • Атомарность позволяет быть уверенным, что какое бы событие не произошло в ходе Т1 (падение сервера, сбой сети), не может случиться так, что $100 будут списаны с А, но не придут на Б (в противном случае говорят о «несогласованном состоянии»).
  • Изолированность говорит о том, что даже если Т1 и Т2 осуществляются одновременно, в результате с А будет списано $100 и та же сумма поступит на Б. Во всех остальных случаях опять говорят о несогласованном состоянии.
  • Надёжность позволяет не беспокоиться о том, что Т1 исчезнет, если база упадёт сразу после коммита Т1.
  • Консистентность предотвращает возможность создания денег или их уничтожения в системе.

Ниже можно не читать, это уже не важно для понимания остального материала.

Многие БД не обеспечивают полную изолированность по умолчанию, поскольку это приводит к огромным издержкам в производительности. В SQL используется 4 уровня изолированности:
  • Сериализуемые транзакции (Serializable). Наивысший уровень изолированности. По умолчанию используется в SQLite. Каждая транзакция исполняется в собственной, полностью изолированной среде.
  • Повторяемое чтение (Repeatable read). По умолчанию используется в MySQL. Каждая транзакция имеет свою среду, за исключением одной ситуации: если транзакция добавляет новые данные и успешно завершается, то они будут видимы для других, всё ещё выполняющихся транзакций. Но если транзакция модифицирует данные и успешно завершается, то эти изменения будут не видны для всё ещё выполняющихся транзакций. То есть для новых данных принцип изолированности нарушается.

    Например, транзакция А выполняет 

    SELECT count(1) from TABLE_X

    Потом транзакция Б добавляет в таблицу Х и коммитит новые данные. И если после этого транзакция А снова выполняет count(1), то результат будет уже другим.

    Это называется фантомным чтением.
  • Чтение зафиксированных данных (Read commited). По умолчанию используется в Oracle, PostgreSQL и SQL Server. Это то же самое, что и повторяемое чтение, но с дополнительным нарушением изолированности. Допустим, транзакция А читает данные; затем они модифицируются или удаляются транзакцией Б, которая коммитит эти действия. Если А снова считает эти данные, то она увидит изменения (или факт удаления), сделанные Б.

    Это называется неповторяемым чтением (non-repeatable read).
  • Чтение незафиксированных данных (Read uncommited). Самый низкий уровень изолированности. К чтению зафиксированных данных добавляется новое нарушение изолированности. Допустим, транзакция А читает данные; затем они модифицируются транзакцией Б (изменения не коммитятся, Б всё ещё выполняется). Если А считает данные снова, то увидит сделанные изменения. Если же Б будет откачена назад, то при повторном чтении А не увидит изменений, словно ничего и не было.

    Это называется грязным чтением.


Большинство БД добавляют собственные уровни изолированности (например, на основе снэпшотов, как в PostgreSQL, Oracle и SQL Server). Также во многих БД не реализованы все четыре вышеописанных уровня, особенно чтение незафиксированных данных.

Пользователь или разработчик может сразу же после установления соединения переопределить уровень изолированности по умолчанию. Для этого достаточно добавить очень простую строчку кода.

5.2.2. Управление параллелизмом

Главное, для чего нам нужны изолированность, согласованность и атомарность, это возможность осуществлять операции записи над одними и теми же данными (добавлять, обновлять и удалять).

Если все транзакции будут только читать данные, то смогут работать одновременно, не влияя на другие транзакции.
Если хотя бы одна транзакция изменяет данные, читаемые другими транзакциями, то БД нужно найти способ скрыть от них эти изменения. Также нужно удостовериться, что сделанные изменения не будут удалены другими транзакциями, которые не видят изменённых данных.

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

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

Идеальный способ решения проблемы выглядит так (при каждом создании или отмене транзакции):
  • Мониторить все операции каждой транзакции.
  • Если две и более транзакции конфликтуют из-за чтения/изменения одних и тех же данных, то менять очерёдность операций внутри участников конфликта, чтобы свести к минимуму количество причин.
  • Выполнять конфликтующие части транзакций в определённом порядке. Неконфликтующие транзакции в это время выполняются параллельно.
  • Иметь в виду, что транзакции могут быть отменены.

Если подходить к вопросу более формально, то это проблема конфликта расписаний. Решать её очень трудно, а оптимизация требует больших ресурсов процессора. Корпоративные БД не могут позволить себе часами искать наилучшее расписание для каждой новой транзакции. Поэтому используются менее совершенные подходы, при которых на конфликты тратится больше времени.

5.2.3. Диспетчер блокировок

Для решения вышеописанной проблемы во многих БД используются блокировки (locks) и/или версионность данных.
Если транзакции нужны какие-то данные, то она блокирует их. Если другой транзакции они тоже потребовались, то её придётся ждать, пока первая транзакция не снимет блокировку.

Это называется эксклюзивной блокировкой.

Но слишком расточительно использовать эксклюзивные блокировки в случаях, когда транзакциям нужно всего лишь считать данные. Зачем мешать чтению данных? В таких случаях используются совместные блокировки. Если транзакции нужно считать данные, они применяет к ним совместную блокировку и читает. Это не мешает другим транзакциям тоже применять совместные блокировки и читать данные. Если же какой-то из них нужно изменить данные, то ей придётся подождать, пока все совместные блокировки не будут сняты. Только после этого она сможет применить эксклюзивную блокировку. И тогда уже всем остальным транзакциям придётся ждать её снятия, чтобы считывать эти данные.



Диспетчер блокировок — это процесс, который применяет и снимает блокировки. Они хранятся в хэш-таблице (ключами являются блокируемые данные). Диспетчер знает для всех данных, какие транзакции применили блокировки или ждут их снятия.

Взаимная блокировка (deadlock)

Использование блокировок может привести к ситуации, когда две транзакции бесконечно ожидают снятия блокировок:



Здесь транзакция А эксклюзивно заблокировала данные 1 и ожидает освобождения данных 2. В то же время транзакция Б эксклюзивно заблокировала данные 2 и ожидает освобождения данных 1.

При взаимной блокировке диспетчер выбирает, какую транзакцию отменить (откатить назад). И решение принять не так просто:
  • Будет ли лучше убить транзакцию, которая изменила последний набор данных (а значит, откат будет наименее болезненным)?
  • Будет ли лучше убить самую молодую транзакцию, поскольку пользователи других транзакций прождали дольше?
  • Будет ли лучше убить транзакцию, которой требуется меньше времени для завершения?
  • На сколько других транзакций повлияет откат?

Но прежде чем принять решение, диспетчер должен убедиться, действительно ли возникла взаимная блокировка.

Представим хэш-таблицу в виде диаграммы, как на иллюстрации выше. Если на диаграмме присутствует циклическая связь, то взаимная блокировка подтверждена. Но поскольку проверять на наличие циклов достаточно дорого (ведь диаграмма, на которой отражены все блокировки, будет весьма большой), зачастую используется более простой подход: использование таймаутов. Если блокировка не снимается в течение определённого времени, значит транзакция вошла в состояние взаимной блокировки.

Перед наложением блокировки диспетчер также может проверить, не приведёт ли это к возникновению взаимной блокировки. Но чтобы однозначно на это ответить, тоже придётся потратиться на вычисления. Поэтому подобные предпроверки зачастую представлены в виде набора базовых правил.

Двухфазная блокировка

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

В DB2 и SQL Server применяется протокол двухфазной блокировки, при котором транзакция делится на две фазы:
  • Фазу подъёма (growing phase), когда транзакция может только применять блокировки, но не снимать их.
  • Фазу спада (shrinking phase), когда транзакция может только снимать блокировки (с данных, которые уже обработаны и не будут обрабатываться снова), но не применять новые.

Частый конфликт, случающийся в отсутствие двухфазной блокировки:



До транзакции А X = 1 и Y = 1. Она обрабатывает данные Y = 1, которые были изменены транзакцией В уже после начала транзакции А. В связи с принципом изолированности транзакция А должна обрабатывать Y = 2.

Цели, решаемые с помощью этих двух простых правил:
  • Снимать блокировки, которые больше не нужны, чтобы уменьшить время ожидания других транзакций.
  • Предотвращать случаи, когда транзакция получают данные, модифицированные ранее запущенной транзакцией. Такие данные не совпадают с запрашиваемыми.

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

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

Версионность данных

Ещё один способ решения проблемы конфликта транзакций — использование версионности данных.
  • Все транзакции могут модифицировать одни и те же данные в одно и то же время.
  • Каждая транзакция работает с собственной копией (версией) данных.
  • Если две транзакции изменяют одни и те же данные, то принимается только одна из модификаций, другая будет отклонена, а сделавшая её транзакция будет откачена (и, может быть, перезапущена).

Это позволяет увеличить производительность, поскольку:
  • Читающие транзакции не блокируют записывающие, и наоборот.
  • Неповоротливый диспетчер блокировок не оказывает влияния.

В общем, всё что угодно будет лучше, чем блокировки, за исключением случаев, когда две транзакции записывают одни и те же данные. Причём это может привести к огромному перерасходу дискового пространства.

Оба подхода — блокировки и версионность — имеют плюсы и минусы, многое зависит от того, в какой ситуации они применяются (больше чтений или больше записей). Можете изучить очень хорошую презентацию, посвящённую реализации мультиверсионного управления параллелизмом в PostgreSQL.

В некоторых БД (DB2 до версии 9.7, SQL Server) используются только блокировки. Другие, вроде PostgreSQL, MySQL и Oracle, используются комбинированные подходы.

Примечание: версионность оказывает интересное влияние на индексы. Иногда в уникальном индексе появляются дубликаты, индекс может содержаться больше записей, чем строк в таблице и т.д.

Если часть данных считывается при одном уровне изолированности, а потом он увеличивается, то вырастает количество блокировок, а значит теряется больше времени на ожидания транзакций. Поэтому большинство БД не используют по умолчанию максимальный уровень изолированности.

Как обычно, за более подробной информацией обращайтесь к документации: MySQL, PostgreSQL, Oracle.

5.2.4. Диспетчер логов

Как мы уже знаем, ради увеличения производительности БД хранит часть данных в буферной памяти. Но если сервер падает во время коммита транзакции, то находящиеся в памяти данные будут потеряны. А это нарушает принцип надёжности транзакций.

Конечно, можно всё писать на диск, но при падении вы останетесь с недописанными данными, а это уже нарушение принципа атомарности.

Любые изменения, записанные транзакцией, должны быть отменены или завершены.

Это делается двумя способами:
  • Теневые копии/страницы. Каждая транзакция создаёт собственную копию БД (или её часть), и работает с этой копией. В случае ошибки копия удаляется. Если всё прошло успешно, то БД мгновенно переключается на данные из копии с помощью одной уловки на уровне файловой системы, а потом удаляет «старые» данные.
  • Лог транзакции. Это специальное хранилище. Перед каждой записью на диск БД пишет информацию в лог транзакции. Так что в случае сбоя БД будет знать, как удалить или завершить незавершённую транзакцию.

WAL

В больших БД с многочисленными транзакциями теневые копии/страницы занимают невероятно много места в дисковой подсистеме. Поэтому в современных БД используется лог транзакции. Он должен размещаться в защищённом от сбоев хранилище.

Большинство продуктов (в частности, Oracle, SQL Server, DB2, PostgreSQL, MySQL и SQLite) работают с логом транзакции через протокол WAL (Write-Ahead Logging). Данные протокол содержит три правила:
  1. Каждая модификация в БД должна сопровождаться записью в лог, и она должна вноситься ДО того, как данные будут записаны на диск.
  2. Записи в логе должны располагаться в соответствии с очерёдностью соответствующих событий.
  3. Когда транзакция коммитится, запись об этом должна вноситься в лог ДО момента успешного завершения транзакции.



За выполнением этих правил следит диспетчер логов. Логически он расположен между диспетчером кэша и диспетчером доступа к данным. Диспетчер логов регистрирует каждую операцию, выполняемую транзакциями, до момента записи на диск. Вроде верно?

НЕВЕРНО! После всего, через что мы с вами прошли в этой статье, пора бы уже запомнить, что всё связанное с БД подвергается проклятью «эффекта базы данных». Если серьёзно, то проблема в том, что нужно найти способ писать в лог, при этом сохраняя хорошую производительность. Ведь если лог транзакций работает медленно, то он тормозит все остальные процессы.

ARIES

В 1992 год исследователи из IBM создали расширенную версию WAL, которую назвали ARIES. В том или ином виде ARIES используется большинством современных БД. Если вы захотите поглубже изучить этот протокол, можете проштудировать соответствующую работу.

Итак, ARIES расшифровывается как Algorithms for Recovery and Isolation Exploiting Semantics. У этой технологии две задачи:
  1. Обеспечить хорошую производительность при записи логов.
  2. Обеспечить быстрое и надёжное восстановление.

Есть несколько причин, по которым БД приходится откатывать транзакцию:
  1. Пользователь отменил её.
  2. Ошибка сервера или сети.
  3. Транзакция нарушила целостность БД. Например, вы применили к колонке условие UNIQUE, а транзакция добавила дубликат.
  4. Наличие взаимных блокировок.

Но иногда БД может и восстанавливать транзакцию, допустим, в случае сетевой ошибки.

Как это возможно? Чтобы ответить на это, нужно сначала разобраться с тем, какая информация сохраняется в логе.

Логи
Каждая операция (добавления/удаления/изменения) во время выполнения транзакции ведёт к появлению записи в логе. Запись содержит:
  • LSN (Log Sequence Number). Это уникальный номер, значение которого определяется хронологическим порядком. То есть если операция А произошла до операции Б, LSN для А будет меньше LSN для Б. В реальности способ генерирования LSN сложнее, поскольку он связан и со способом хранения лога.
  • TransID. Идентификатор транзакции, осуществившей операцию.
  • PageID. Место на диске, где находятся изменённые данные.
  • PrevLSN. Ссылка на предыдущую запись в логе, созданную той же транзакцией.
  • UNDO. Способ отката операции.

    Например, если была проведена операция обновления, то в UNDO записывается предыдущее значение/состояние изменённого элемента (физический UNDO) или обратная операция, позволяющая вернуться в предыдущее состояние (логический UNDO). В ARIES используется только логический, с физическим работать очень тяжело.
  • REDO. Способ повтора операции.

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

Насколько известно, UNDO не используется только в PostgreSQL. Вместо этого используется сборщик мусора, убирающий старые версии данных. Это связано с реализацией версионности данных в этой СУБД.

Чтобы вам было легче представить состав записи в логе, вот визуальный упрощённый пример, в котором выполняется запрос UPDATE FROM PERSON SET AGE = 18;. Пусть он исполняется в транзакции номер 18:



Каждый лог имеет уникальный LSN. Связанные логи относятся к одной и той же транзакции, причём линкуются они в хронологическом порядке (последний лог списка относится к последней операции).

Буфер логов
Чтобы запись в лог не превратилась в узкое место системы, используется буфер логов.



Когда исполнитель запросов запрашивает модифицированные данные:
  1. Диспетчер кэша хранит их в буфере.
  2. Диспетчер логов хранит в собственном буфере соответствующий лог.
  3. Исполнитель запросов определяет, завершена ли операция, и, соответственно, можно ли запрашивать изменённые данные.
  4. Диспетчер логов сохраняет нужную информацию в лог транзакции. Момент внесения этой записи задаётся алгоритмом.
  5. Диспетчер кэша записывает изменения на диск. Момент осуществления записи также задаётся алгоритмом.

Когда транзакция коммитится, это означает, что выполнены все шаги с 1 по 5. Запись в лог транзакции осуществляется быстро, поскольку представляет собой «добавление лога куда-то в лог транзакции». В то же время запись данных на диск представляет собой более сложную процедуру, при этом учитывается, что данные впоследствии должны быть быстро считаны.

Политики STEAL и FORCE

Для увеличения производительности шаг номер 5 нужно делать после коммита, поскольку в случае сбоя всё ещё возможно восстановить транзакцию с помощью REDO. Это называется «политика NO-FORCE».

Но БД может выбрать и политику FORCE ради уменьшения нагрузки во время восстановления. Тогда шаг номер 5 выполняется до коммита.

Также БД выбирает, записывать ли данные на диск пошагово (политика STEAL) или, если диспетчер буфера должен дождаться коммита, записать всё разом (NO-STEAL). Выбор зависит от того, что вам нужно: быструю запись с долгим восстановлением или быстрое восстановление?

Как упомянутые политики влияют процесс восстановления:
  • Для STEAL/NO-FORCE нужны UNDO и REDO. Производительность высочайшая, но более сложная структура логов и процессов восстановления (вроде ARES). Эту комбинацию политик использует большинство БД.
  • Для STEAL/FORCE нужен только UNDO.
  • Для NO-STEAL/NO-FORCE — только REDO.
  • Для NO-STEAL/FORCE вообще ничего не нужно. Производительность в данном случае самая низкая, и требуется огромное количество памяти.

Восстановление

Итак, как нам можно использовать наши замечательные логи? Предположим, что новый сотрудник порушил БД (правило №1: всегда виноват новичок!). Вы её перезапускаете и начинается процесс восстановления.
ARIES восстанавливает в три этапа:
  1. Анализ. Считывается весь лог транзакции, чтобы можно было восстановить хронологию событий, произошедших в процессе падения базы. Это помогает определить, какую транзакцию нужно откатить. Откатываются все транзакции без приказа о коммите. Также система решает, какие данные должны были записаться на диск во время сбоя.
  2. Повтор. Для обновления БД до состояния перед падением используется REDO. Его логи обрабатываются в хронологическом порядке. Для каждого лога считывается LSN страницы на диске, содержащей данные, которые нужно изменить.

    Если LSN(страницы_на_диске)>=LSN(записи_в_логе), то значит данные уже были записаны на диск перед сбоем. Но значение было перезаписано операцией, которая была выполнена после записи в лог и до сбоя. Так что ничего не сделано, на самом деле.

    Если LSN(страницы_на_диске)<LSN(записи_в_логе), то страница на диске уже обновлена.

    Повтор выполняется даже для транзакций, которые будут откачены, потому что это упрощает процесс восстановления. Но современные БД наверняка этого не делают.
  3. Отмена. На этом этапе откатываются все незавершённые на момент сбоя транзакции. Процесс начинается с последних логов каждой транзакции и обрабатывает UNDO в обратном хронологическом порядке с помощью PrevLSN.

В процессе восстановления лог транзакции должен знать о действиях, выполняемых при восстановлении. Это нужно для синхронизации сохраняемых на диск данных теми, что записаны в логе транзакции. Можно удалить записи транзакций, которые откатываются, но это очень трудно сделать. Вместо этого ARIES вносит компенсирующие записи в лог транзакции, логически аннулирующие записи откатываемых транзакций.

Если транзакция отменена «вручную», или диспетчером блокировок, или из-за сбоя сети, то этап анализа не нужен. Ведь информация для REDO и UNDO содержится в двух таблицах, размещённых в памяти:
  • В таблице транзакций (тут хранятся состояния всех текущих транзакций).
  • В таблице грязных страниц (здесь содержится информация о том, какие данные нужно записать на диск).

Как только появляется новая транзакция, эти таблицы обновляются диспетчером кэша и диспетчером транзакций. А поскольку таблицы хранятся в памяти, то при падении БД они пропадают.

Этап анализа нужен как раз для восстановления обеих таблиц с помощью информации из лога транзакций. Для ускорения этого этапа в ARIES используются контрольные точки. На диск время от времени записывается содержимое обеих таблиц, а также последний на момент записи LSN. Так что во время восстановления анализируются только логи, следующие после этого LSN.

6. Заключение


В качестве дополнительного обзорного чтива про базы данных можно порекомендовать статью Architecture of a Database System. Это хорошее введение в тему, написанное довольно понятным языком.

Если вы внимательно прочитали весь вышеизложенный материал, то наверняка получили представление о том, насколько велики возможности баз данных. Однако в этой статье не затронуты другие важные проблемы:
  • Как управлять кластеризованными БД и глобальными транзакциями.
  • Как получить снэпшот, если база всё работает.
  • Как эффективно хранить и сжимать данные.
  • Как управлять памятью.

Так что подумайте дважды, прежде чем выбирать между забагованной NoSQL и цельной реляционной БД. Не поймите неправильно, некоторые NoSQL-базы очень хороши. Но они ещё далеки от совершенства и могут помочь только в решении специфических проблем, связанных с некоторыми приложениями.

Итак, если вас кто-нибудь спросит, а как же работают базы данных, то вместо того, чтобы плюнуть и уйти, вы можете ответить:



Или же просто можете дать ссылку на эту статью.

Комментарии (132)


  1. justCxx
    15.09.2015 14:23
    #8573259
    +14

    Сильно!


  1. Londeren
    15.09.2015 14:54
    #8573353
    +11

    Спасибо за перевод! Читал в оригинале, очень понравилось, написано доступным понятным языком.


  1. musicriffstudio
    15.09.2015 15:02
    #8573375
    +1

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


  1. Suvitruf
    15.09.2015 15:03
    #8573377
    +7

    Спасибо за перевод, вот только заключение слишком субьективно.

    Так что подумайте дважды, прежде чем выбирать между забагованной NoSQL и цельной реляционной БД. Не поймите неправильно, некоторые NoSQL-базы очень хороши. Но они ещё далеки от совершенства и не могут помочь в решении специфических проблем, связанных с некоторыми приложениями.
    Специфические проблемы? Некоторые приложения? Лучше в заключении было бы написать: «Всему свой инструмент». Для многих задач NoSQL решения подходят лучше реляционных БД.


    1. gandjustas
      15.09.2015 15:12
      #8573393
      +7

      NoSQL лучше подходит для очень немногих задач.


      1. Suvitruf
        15.09.2015 15:20
        #8573415
        +8

        Это не делает NoSQL БД «забагованными». Слишком негативный посыл у автора оригинального поста в отношении NoSQL.


        1. 4dmonster
          15.09.2015 15:34
          #8573467
          +3

          Причём, если в высказывании автора поменять местами RDBMS и NoSQL, получиться тоже совершенно истинное утверждение.

          Так что подумайте дважды, прежде чем выбирать между забагованной реляционной БД и цельной NoSQL. Не поймите неправильно, некоторые реляционные базы очень хороши. Но они ещё далеки от совершенства и не могут помочь в решении специфических проблем, связанных с некоторыми приложениями.


          1. gandjustas
            15.09.2015 15:54
            #8573541
            -3

            Вы из всей статьи прочитали только один абзац?
            Фраза, конечно, не имеет никакого смысла. Можно вообще любые два термина из мира ПО подставить и смысл не изменится, но статья совершенно не об этом.

            Кстати, есть ли о NoSQL базах такие статьи?


            1. 4dmonster
              15.09.2015 16:10
              #8573589
              +1

              Мне статья как раз очень понравилась, она комплексная и полная.
              Поэтому резануло глаза заключение — как-будто кто-то другой прилепил.

              О NoSQL я не видел сводных статей, а вот статьи с разбором какой-то конкретной NoSQL, встречались.


        1. gandjustas
          15.09.2015 15:51
          #8573533
          +7

          Большинство NoSQL баз по сравнению со взрослыми РСУБД таки забагованные и в этом автор прав.
          Но для тех задач, где используются NoSQL базы, это не сильно большая проблема.

          А вы разве первый раз сталкиваетесь с таким отношением к NoSQL со стороны тех, кто разбирается в РСУБД?


          1. Suvitruf
            15.09.2015 16:08
            #8573581

            Но для тех задач, где используются NoSQL базы, это не сильно большая проблема.
            Можно конкретизировать, для каких задач? Если вы хотели этим сказать, что NoSQL не рассчитаны на большие нагрузки, то это не так.

            Проблемы у любого продукта есть. Но в случае с современными NoSQL решениями все эти проблемы довольно быстро исправляются, они более динамичны. С одной стороны это хорошо, но с точки зрения стабильности может и нет. Мы вот используем RethinkDB для нашей ММО. За время разработки парни уже не одно обновление выкатили, что не может не радовать.

            Или взять тот же Riak (он у нас как бэк энд для ежа используется). Если мне память не изменяет, то те же Riot'ы для Лиги используют ежа со всё тем же Риаком. И сие дело держит миллионы юзеров.


            1. gandjustas
              15.09.2015 16:22
              #8573641
              +1

              Нагрузки тут не при чем. Почти всегда нагрузки компенсируются вливанием бабла в железо и построением кешей. Независимо от СУБД.

              А вот надежность хранения и согласованность данных — это нельзя компенсировать добавлением железа. И тут у NoSQL проблемы. Мало того, что нету никакого контроля целостности на прикладном уровне, так еще и резервное копирование и восстановление не всегда работает как надо.

              Поэтому вы вряд ли найдете учетную систему на базе NoSQL, особенно если там фигурируют деньги. Также NoSQL редко встречается в задачах с конкурентным доступом к данным.


              1. vedenin1980
                15.09.2015 16:36
                #8573669
                +5

                Нагрузки тут не при чем. Почти всегда нагрузки компенсируются вливанием бабла в железо и построением кешей. Независимо от СУБД.

                Сложно будет убедить гугл, что им нужно увеличить количество серверов раз в десять (от 10 тыс. до 100 тыс) чтобы использовать православные СУБД вместо NoSql. Проблема СУБД с современными большими данными оказалось в том что данных в некоторых случаях что вливание бабла в железо уже не работает никак, или же напоминает попытки носить воду в решете.

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

                Не всегда это нужно

                Мало того, что нету никакого контроля целостности на прикладном уровне, так еще и резервное копирование и восстановление не всегда работает как надо.

                сильно зависит от Nosql


                1. gandjustas
                  15.09.2015 17:05
                  #8573711
                  +1

                  Аппеляции к гуглу не имеет смысла. В мире один гугл и сотни тысяч учетных систем. И никто из читающих тут не делает гугл, а большая часть занимается учетными системами в том или ином виде. Поэтому можно с высокой долей вероятности говорить, что любые проблемы быстродействия можно решить вливанием бабла в железо.

                  Не всегда это нужно

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

                  сильно зависит от Nosql

                  В среднем по больнице у NoSQL проблемы с восстановлением данных. Чаще используется подход, что упавшую базу просто поднимают из живой реплики. Но это не защищает от программных ошибок, которые портят данные (в том числе в реплике). А на малых кластерах еще вполне возможно вывести из строя несколько узлов разом и потерять данные.


                  1. vedenin1980
                    15.09.2015 17:32
                    #8573775
                    +1

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

                    Кто сказал? Большие данные давно уже рядовой инструмент многих компаний, я часто сталкивался с данными, которые в SQL модель не влезут никак.

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

                    Нельзя, 1) big data это давно уже не экзотика, а они в SQL не ложаться. 2) нет смысла для сборка банальной статистики посещений сайта тратить миллионы долларов на супер навороченую СУБД, когда в noSql сделать это куда быстрее, дешевле и даже надежнее (так как она не упадет от нагрузки)

                    Это гораздо чаще нужно, чем не нужно.

                    Нет. Далеко не вся информация финансовая и сверх критичная. Ну, потеряется пара просмотров и кликов в статистике сайта в миллардах показах. Нужно для этого городить огород? Нет. Очень часто при потере небольшого куска данных у 0.0001% пользователей ничего ужасного не произойдет, скажем если у кого-то пользователя на форуме сообщение не дойдет до сервера, он нажмет назад и пошлет его ещё раз или перепишет его ещё раз, это не стоит того чтобы тратить десятки тысяч $ на сервера и базы данных.

                    P.S. Надо ещё понимать, что качество у разных СУБД тоже разное, между Oracle и MySql две большие разницы, несколько раз были случаи когда MySql весьма серьезно глючил вплоть до отказа базы данных (особенно когда работает на пределе производительности), а Oracle и ему подобные стоят столько что просто не по карману многим организациям.
                    P.P.S. В целом, на каждую задачу свой инструмент и идеализировать СУБД или noSql и применять их там где не нужно — тоже не разумно.


                    1. dezconnect
                      15.09.2015 23:29
                      #8574467

                      И как в NoSQL решает вопрос биг дата? Те же структуры в профиль только зачастую с худшими планировщиками и индексами. А отмапредьюсить данные можно на любой субд было бы желание.


                    1. aktuba
                      15.09.2015 23:31
                      #8574471
                      +2

                      я часто сталкивался с данными, которые в SQL модель не влезут никак.

                      Можно пример? Честно, ни разу с подобным не сталкивался, поэтому интересно, какие-такие данные не могут влезть в sql. Вроде как vk, fb, twi не жаловались публично.

                      когда в noSql сделать это куда быстрее, дешевле и даже надежнее (так как она не упадет от нагрузки)

                      Бред.

                      В целом, на каждую задачу свой инструмент и идеализировать СУБД или noSql и применять их там где не нужно — тоже не разумно.

                      Согласен. Но вот в чем проблема: чаще всего sql-базы покроют функционал nosql, а наоборот — очень редко и с потерей основных плюсов (скорость, например).


                      1. vedenin1980
                        16.09.2015 00:18
                        #8574511
                        +3

                        Вроде как vk, fb, twi не жаловались публично.

                        Что значит не жаловались? Fb использует касандру, линкедИн — волдерморта, гугл — свой аналог hadoop hbase, vb — свою собственную nosql базу данных, twitter — Hbase, pig, FlockDB и касандру. Как раз, использование только sql у гигантов практически не встречается, хотя в стеке для некоторых задач sql используется, но далеко не для всех.

                        Но вот в чем проблема: чаще всего sql-базы покроют функционал nosql, а наоборот — очень редко и с потерей основных плюсов (скорость, например).

                        Странная логика, если мне нужно key-value хранилищн, хранилище отдельных json докуменов или хранить сложные графы я возьму соотвествующие nosql базы данных. Sql может заменить, но за счет производительности, места и ресурсов, что зачастую окажется не допустимым для данной задачи.

                        Бред.

                        В чем? Nosql зачастую работает намного быстрее, например скорость in-memory key-value хранилища будет намного быстрее sql, если нужно хранить именно ключ-значение и надежность не критична, соотвественно ресурсов потребуется значительно меньше.

                        Честно, ни разу с подобным не сталкивался, поэтому интересно, какие-такие данные не могут влезть в sql.

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

                        И как в NoSQL решает вопрос биг дата? Те же структуры в профиль только зачастую с худшими планировщиками и индексами. А отмапредьюсить данные можно на любой субд было бы желание.

                        HDFS Hadoop'a это тоже вполне NoSQL (и всякие обертки вроде Hiv'a), отмапредьюсить это уже только результат, который, конечно, уже может быть сохранен в СУБД. А сами биг дата нельзя просто взять сохранить и обработать в СУБД, иначе это не совсем биг дата.


                        1. aktuba
                          16.09.2015 01:15
                          #8574575
                          -1

                          Что значит не жаловались?

                          То, что наравне с nosql используют и рсубд. Key-value имеет свою нишу, с этим я согласен. Но заявлять что данные не влезут в sql — бред.

                          Sql может заменить, но за счет производительности, места и ресурсов, что зачастую окажется не допустимым для данной задачи.

                          Ну так я это и говорил — sql покроет потребности (пусть и за счет ресурсов), а вот nosql редко сможет полноценно заменить sql.

                          Nosql зачастую работает намного быстрее, например скорость in-memory key-value хранилища будет намного быстрее sql, если нужно хранить именно ключ-значение и надежность не критична, соотвественно ресурсов потребуется значительно меньше.

                          Если не секрет, откуда такие данные? SQL разучился работать в памяти, без диска? SQL разучился работать по primary? Можно ссылку на сравнения? Не троллинг, реально интересно. По нашим тестам (а мы протестировали с десяток), nosql выигрывает только на самых простых вариантах. Чуть сложнее выборка или сложные данные для вставки (затрагивающие, по итогу, 5-6 коллекций) — nosql становится явным аутсайдером.

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

                          Эммм… Они не «влезли» в sql? Что это значит? Место? Скорость? Плохая архитектура?

                          А сами биг дата нельзя просто взять сохранить и обработать в СУБД, иначе это не совсем биг дата.

                          С фига-ли?! о_О


                          1. vintage
                            16.09.2015 01:18
                            #8574579
                            -2

                            Ну так я это и говорил — sql покроет потребности (пусть и за счет ресурсов), а вот nosql редко сможет полноценно заменить sql.
                            Графовая БД легко заменяет реляционную, но не наоборот.


                            1. gandjustas
                              16.09.2015 01:24
                              #8574585
                              -1

                              Графовая БД легко заменяет реляционную, но не наоборот.

                              Да что вы?
                              Вот есть простая задача — продажа билетов в театр. Куча киосков по городу подключены к центральной базе. Как сделать так, чтобы гарантированно не продать два билета на одно место? Билеты могут продаваться в любом количестве.
                              Выбирайте любой движок на ваше усмотрение.

                              ЗЫ. На любой РСУБД это делается элементарно.


                              1. nsinreal
                                16.09.2015 02:28
                                #8574631
                                +2

                                В любой достаточно адекватной системе есть механизм бронирования. Например, как работает заказ билетов на поезд:
                                1. Юзер выбирает место, оно бронируется под него на 15 минут
                                2. Юзер втыкает минуту, выбирает еще одно место, оно бронируется под него на 15 минут
                                3. У юзера остается 14 минут, чтобы успеть оплатить оба билета (или 15 минут, чтобы успеть оплатить только второй билет)
                                4. После оплаты юзером билеты считаются купленными юзером.
                                5. По истечению времени билет возвращается в свободные билеты.

                                Это я к тому, что мир на самом деле сложный. Я только что привнес просто дополнительной сложности, извините.

                                Касательно вопроса — а как таки сделать уникальность привязки места к юзеру? Я только что пошел в документацию Neo4j (бд которую я в первый раз в глаза вижу) и нашел несколько способов это сделать, помимо очевидных костылей типа двухфазного коммита.


                                1. gandjustas
                                  16.09.2015 02:36
                                  #8574637
                                  -1

                                  1. Юзер выбирает место, оно бронируется под него на 15 минут
                                  2. Юзер втыкает минуту, выбирает еще одно место, оно бронируется под него на 15 минут

                                  И у нас будут два пользователя, которые покупают места 14 и 15, а второй покупает места 15 и 14. Упс, дедлок. Или вы заставите одно из них ждать пока 15 минут другого закончатся?
                                  Или откатить обоих, но они попытаются повторить ту же транзакцию в том же порядке.

                                  Это я к тому, что мир на самом деле сложный. Я только что привнес просто дополнительной сложности, извините.
                                  Да-да, вот только в РСУБД это делается одним unique constraint.

                                  Вы не понимаете, что только что попытались изобрести механизм блокировок, который уже есть в любой РСУБД? При этом надо будет написать немало кода чтобы реализовать ваш сценарий.

                                  Я только что пошел в документацию Neo4j
                                  Ссылки в студию.


                                  1. nsinreal
                                    16.09.2015 03:15
                                    #8574661

                                    Или вы заставите одно из них ждать пока 15 минут другого закончатся?

                                    Да, в этом смысл бронирования. В том, что другой юзер вообще не увидит забронированный билет. А юзер, который забронировал билет — будет видеть время, которое у него осталось для совершения оплаты билетов. Это UX-требование, это то как должна работать система уважающая пользователя

                                    Вы не понимаете, что только что попытались изобрести механизм блокировок, который уже есть в любой РСУБД? При этом надо будет написать немало кода чтобы реализовать ваш сценарий.

                                    Да-да, я изобрел механизм блокировок, который есть в любой РСУБД. И это UX-требование и это блять удобно для пользователя. И этим UX-требованием я хотел продемонстрировать, что механизмы блокировок, которые реализованы в бд нужно дублировать мануально в случае существования таких требований.
                                    Поэтому вместо стандартных блокировок можно использовать то хранилище, которое не навязывает свой механизм блокировок, а позволяет делать что угодно без лишних проблем и просадок по перфомансу. Встречный вопрос: есть сущность в бд, её могут случайно открыть два пользователя конкурретно на редактирование. Как вы будете обрабатывать это и возможные последствия этого?

                                    Ссылки в студию.

                                    neo4j.com/docs/stable/query-create-unique.html. Пойдет?


                                    1. gandjustas
                                      16.09.2015 03:19
                                      #8574665
                                      -1

                                      Все понятно. Когда не достигли желаемого сделали вид, что желали достигнутого.


                                      1. nsinreal
                                        16.09.2015 03:25
                                        #8574667
                                        -1

                                        Эм? Если ты хочешь исключить бронирование билета из процесса покупки, то ничего страшного не произойдет. Create Unique решит проблему одновременной покупки билета. Просто твоя система будет говном с точки зрения UX, но это же ничего страшного, да? Зато ты не будешь изобретать блокировки, которые уже релизованы в твоей РСУБД.

                                        Не отмазывайтесь, отвечайте на вопрос, как вы будете обрабатывать ситуацию возможности открытия двумя разными юзера одной сущности на редактирование? Что вы будете делать, чтобы не изобретать блокировки и mvcc, кроме как положите на эту ситуацию?


                                        1. vintage
                                          16.09.2015 03:38
                                          #8574683

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


                                          1. nsinreal
                                            16.09.2015 03:46
                                            #8574691

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


                                        1. gandjustas
                                          16.09.2015 03:43
                                          #8574689
                                          -1

                                          UX на базу никак не завязан, так что кидаться такими заявлениями бессмысленно.

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

                                          Не отмазывайтесь, отвечайте на вопрос, как вы будете обрабатывать ситуацию возможности открытия двумя разными юзера одной сущности на редактирование?
                                          С точки зрения UX вообще нельзя ничего блокировать. Поэтому оптимистичная блокировка (легковесный аналог MVCC) + автомерж изменений при конфликтах. Но к тому что делается в базе не имеет никакого отношения.


                                          1. nsinreal
                                            16.09.2015 03:51
                                            #8574695
                                            +1

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

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

                                            С точки зрения UX вообще нельзя ничего блокировать. Поэтому оптимистичная блокировка (легковесный аналог MVCC) + автомерж изменений при конфликтах. Но к тому что делается в базе не имеет никакого отношения.

                                            По-моему процесс мерджа подразумевает три источника данных: base, this, remote. А это значит, что вам нужно хранить историю изменений. А это дублирование механизмов, заложенных в бд, нет?.. Кроме того, автомердж без подтверждения юзера — плохое решение с точки зрения UX.


                              1. vintage
                                16.09.2015 02:41
                                #8574645
                                -1

                                create class Theater
create class Person
create class Ticket

create property Ticket.theater link Theater
create property Ticket.person link Person
create property Ticket.place integer
create property Ticket.timeslot short

create index Ticket.unique on Ticket (
    theater , 
    person , 
    place , 
    timeslot
) unique

create property Theater.tickets linkset Ticket
create property Person.tickets linkset Ticket

insert into Theater content {}
insert into Person content {}

begin
    let theater = select from Theater limit 1
    let person = select from Person limit 1

    let ticket = insert into Ticket set
        theater = $theater,
        person = $person,
        place = 1,
        timeslot = 1

    update $theater add tickets = ticket
    update $person add tickets = ticket
end


                                1. gandjustas
                                  16.09.2015 02:55
                                  #8574649
                                  -1

                                  create index Ticket.unique on Ticket ( theater , person , place , timeslot ) unique

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

                                  Или есть магические способы обеспечения уникальности?


                                  1. vintage
                                    16.09.2015 03:11
                                    #8574659
                                    +1

                                    Да, там есть и транзакции, и блокировки, и mvcc, а что?


                                    1. gandjustas
                                      16.09.2015 03:16
                                      #8574663

                                      То что в этой базе используются те же алгоритмы, что и в РСУБД. Тогда чем графовая лучше? и почему они может заменить реляционную, а наоборот нет? Я вижу в лучшем случае паритет, а при детальном рассмотрении окажется куча подводных камней в графовой базе.


                                      1. vintage
                                        16.09.2015 03:33
                                        #8574673
                                        +1

                                        > То что в этой базе используются те же алгоритмы, что и в РСУБД.
                                        Я вам больше скажу — эти алгоритмы используются далеко не только в базах данных.

                                        > Тогда чем графовая лучше?
                                        Тем, что хранит прямые ссылки на связанные записи, что позволяет получать их за константное время, не делая джойнов и не держа кучу индексов для их ускорения.

                                        > и почему они может заменить реляционную, а наоборот нет?
                                        Потому, что работа с графами и даже с деревьями в рсубд — это треш и угар. Тысячи статей по рсубд повествуют нам о таблицах смежностей, материализованных путях, вложенных множествах. Только вот в гсудб это всё не нужно. А таблицы с отношениями — это всего-лишь частный случай графа.

                                        > Я вижу в лучшем случае паритет, а при детальном рассмотрении окажется куча подводных камней в графовой базе.
                                        Попробуйте, будет интересно про них почитать :-)


                                        1. gandjustas
                                          16.09.2015 03:55
                                          #8574699
                                          +1

                                          Я вам больше скажу — эти алгоритмы используются далеко не только в базах данных.
                                          И в чем же тогда преимущества?

                                          Тем, что хранит прямые ссылки на связанные записи, что позволяет получать их за константное время, не делая джойнов и не держа кучу индексов для их ускорения.
                                          Не очень понимаю как это делается.
                                          Вот у нас есть узел графа, сохраненный на диске. «Прямая ссылка» ссылка на него — смещение в файле данных.
                                          Мы в этот узел добавляем ссылки на другие узлы и место для хранения узла у нас кончается, надо узел переместить куданить. Смещение поменялось. Что происходит с прямыми ссылками на этот узел?

                                          Или все хранится тупо в памяти? Тогда чем это лучше inmemory и хеш-индексов? Они тоже O(1).

                                          Потому, что работа с графами и даже с деревьями в рсубд — это треш и угар.
                                          С деревьями как раз проблем нет. Ordpath давно изобрели. Лет 7 назад точно. С графами — да, под них не оптимизируется. Но на практике я целый один раз за 10 лет делал транзитивное замыкание в РСУБД.


                                          1. vintage
                                            16.09.2015 04:18
                                            #8574731

                                            И в чем же тогда преимущества?
                                            В архитектуре, а не алгоритмах.

                                            Что происходит с прямыми ссылками на этот узел
                                            Я не вдавался в подробности. Скорее всего там связный список просто.

                                            Или все хранится тупо в памяти?
                                            Можно и в памяти хранить.

                                            Тогда чем это лучше хеш-индексов? Они тоже O(1).
                                            Да хотя бы даже тем, что это не один индекс на всю таблицу, в много маленьких в каждом linkset-свойстве.

                                            С деревьями как раз проблем нет. Ordpath давно изобрели. Лет 7 назад точно.
                                            Это и есть «материализованный путь». С селектами по нему проблем и правда нет. А вот переносы поддеревьев требуют изменения всех вложенных узлов.

                                            Но на практике я целый один раз за 10 лет делал транзитивное замыкание в РСУБД.
                                            Конечно, ведь в рсудб с этим всё сложно и приходится придумывать костыли типа ordpath и компании :-)


                                            1. gandjustas
                                              16.09.2015 04:24
                                              #8574735
                                              -1

                                              В архитектуре, а не алгоритмах.

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

                                              Я не вдавался в подробности. Скорее всего там связный список просто.

                                              Что является ссылкой если данные хранятся на диске?

                                              Можно и в памяти хранить.

                                              Тогда чем оно лучше inmemory с хеш-индексами?

                                              Да хотя бы даже тем, что это не один индекс на всю таблицу, в много маленьких в каждом linkset-свойстве.
                                              Есть техническое описание? Пока не понимаю о чем речь, как оно работает и в чем преимущества.

                                              Это и есть «материализованный путь». С селектами по нему проблем и правда нет. А вот переносы поддеревьев требуют изменения всех вложенных узлов.
                                              И что? Это проблема? Мы-то знаем, что записи редки и пользователи готовы ждать когда жмут кнопку «сохранить».

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


                                              1. vintage
                                                16.09.2015 04:29
                                                #8574737

                                                orientdb.com/docs/last/Concepts.html


                                                1. gandjustas
                                                  16.09.2015 05:52
                                                  #8574757

                                                  Хотел было коммент написать по пунктам, но там столько… Везде полу-правда. Реально надо просто брать запросы и делать забеги.


                                                  1. vintage
                                                    16.09.2015 06:45
                                                    #8574769

                                                    Ну например?


                          1. vedenin1980
                            16.09.2015 01:48
                            #8574605
                            +1

                            То, что наравне с nosql используют и рсубд. Key-value имеет свою нишу, с этим я согласен. Но заявлять что данные не влезут в sql — бред.

                            Есть в мире СУБД способная вместить весь поисковый индекс гугла? В любой реально крупной компании рано или поздно появялется свой «поисковый индекс гугла» из-за которого не получается везде использовать sql, в том числе и потому что данные не «влезут» (да и просто никто разумный не будет пихать в СУБД например все видео ютуба, только чтобы везде использовать СУБД).

                            Эммм… Они не «влезли» в sql? Что это значит? Место? Скорость?

                            В первую очередь место, они тупо влазили только на Hadoop кластер с оберткой Hiv'a, возможно что-то вроде многосерверного Oracl'а сумел их прожевать, но цена такого решения была бы астрономической. Да и не нужно это было.

                            По нашим тестам (а мы протестировали с десяток), nosql выигрывает только на самых простых вариантах. Чуть сложнее выборка или сложные данные для вставки (затрагивающие, по итогу, 5-6 коллекций) — nosql становится явным аутсайдером.

                            Что именно с чем тестировали? Открытый nosql c открытыми СУБД? Или откртый nosql с чем-то вроде Oracla? И что за странное условие сложных выборок или сложных данных с 5-6 коллекциями? Key-value хорошы именно когда запись и выборка всегда простешие один ключ — одно значение. Документные базы данных хороши когда надо писать сложные документы без связей целиком. Ни в том ни в другом случае, ни сложных выборок, ни вставок в 5-6 коллекций быть не должно по определению (по крайне мере в качестве основного сценария). Скорее всего вы пытались использовать nosql для реляционных данных, а это явно неправильно.


                            1. vedenin1980
                              16.09.2015 02:05
                              #8574609
                              +1

                              Ради интереса вот вам несколько задач для использование nosql — хранение сессий пользователей сайта в памяти используя key-value и таблицу СУБД или сохранение и получение (целиком) гигантской анкеты с различными количеством различных полей и данных с сайта как один документ монги или как несколько десятков таблиц в СУБД. Вы уверены что для этих задач СУБД покажет лучшую производительность?
                              Естественно, если вы попытаетесь в key-value или монгу сохранять явные реляционные таблицы со сложными связями с друг другом ничего хорошего из этого не выйдет, не для того они нужны.


                              1. vedenin1980
                                16.09.2015 02:19
                                #8574619
                                +1

                                С фига-ли?! о_О

                                Из самого определения больших данных. Большие данные это огромные массивы данных, которые очень сложно или практически невозможно обрабатывать традиционными средствами СУБД и которые требуют параллельной работы кластеров серверов и noSql решений.


                            1. aktuba
                              16.09.2015 14:59
                              #8575423

                              vedenin1980

                              Есть в мире СУБД способная вместить весь поисковый индекс гугла?

                              Почему нет? В чем проблема-то? В создании кластера? В создании правильной архитектуры? Где вы увидели ограничение на количество данных в «SQL»? 1 млрд. записей — это много или мало? А 1 трлн?

                              в том числе и потому что данные не «влезут»

                              Сейчас мы скатимся к тому, что разработчики данных компаний криворукие…

                              В первую очередь место, они тупо влазили только на Hadoop кластер с оберткой Hiv'a

                              Эмм… Т.е. место все-таки было. Но в sql данные не залезли, а в nosql залезли… Плюс, говоря про hadoop упоминаете кластер, а для sql кластер нельзя было использовать? Какая-то не стыковка, если честно.

                              Что именно с чем тестировали?

                              Различные nosql с mysql. Было желание еще с pg потестировать, но все nosql проиграли по скорости/месту mysql-у и pg даже не трогали.

                              Под проигрышем по скорости я подразумеваю различные тесты на чтение и запись данных. Как простых, так и чуть сложных. По чтению почти все nosql выигрывали у mysql. По записи — проигрывали практически все.

                              По поводу места — разброс сильный. Для сравнения, одна из самых популярных nosql mongodb на одних и тех-же данных занимает х3 места, по сравнению с mysql.

                              Ни в том ни в другом случае, ни сложных выборок, ни вставок в 5-6 коллекций быть не должно по определению (по крайне мере в качестве основного сценария).

                              Честно говоря — я минут 15 сидел и пытался представить приложение, которое использует только kye-value или только документ-ориентированое без связей. Не смог. Подскажете?

                              хранение сессий пользователей сайта в памяти используя key-value и таблицу СУБД

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

                              получение (целиком) гигантской анкеты с различными количеством различных полей и данных с сайта как один документ монги или как несколько десятков таблиц в СУБД.

                              Тут вы меня снова в ступор загнали… Ну ок, предположим есть какая-то супер-гигантская анкета в миллиард полей. Почему она в одном документе монги, а в рсубд размазана на «несколько десятков таблиц» оставим в стороне. Но даже в таких условиях я не вижу никаких проблем использовать субд.

                              Вы уверены что для этих задач СУБД покажет лучшую производительность?

                              Нет, не уверен. А вы уверены в обратном? Например, в примере с сессиями я уверен что рсубд будет не хуже, а скорее и лучше, за счет связей с реальными данными.

                              Из самого определения больших данных.

                              Не нашел по ссылкам указания на то, что из-за размера данных их нельзя сохранить в slq. Скажите, big data — это какой размер? Сколько записей/(мега/гига/тера)байтов данных?


                              1. vintage
                                16.09.2015 15:13
                                #8575459
                                +1

                                Проблема РСУБД не столько в объёме данных, сколько в объёме индексов, скорость которых сильно деградирует с ростом числа записей и связей между ними. А индексов этих нужно много, ибо без них джойны будут катастрофически неэффективными. Другая серьёзная проблема — жёсткая схема, требующая единовременно перелопачивать всю базу при её изменении, что очень долго при большом числе данных.


                                1. gandjustas
                                  16.09.2015 21:34
                                  #8576023
                                  -1

                                  Странная у вас логика. Если мы используем NoSQL, то все выборки у нас по ключу и достаем мы только блобы. А когда речь заходит про РСУБД, то появляются джоины. и сложные запросы. Откуда?
                                  Почему нельзя просто в те же блобы записать json в РСУБД?


                                  1. vintage
                                    16.09.2015 21:49
                                    #8576037
                                    +1

                                    Если мы используем NoSQL, то все выборки у нас по ключу и достаем мы только блобы.
                                    Это key-value базы данных. NoSQL ими не ограничивается.

                                    А когда речь заходит про РСУБД, то появляются джоины. и сложные запросы.
                                    Появляется реляционная алгебра.

                                    Почему нельзя просто в те же блобы записать json в РСУБД?
                                    Можно, и получим обычное key-value хранилище :-)


                                    1. MacIn
                                      17.09.2015 00:04
                                      #8576211

                                      Можно, и получим обычное key-value хранилище :-)

                                      Вот именно. Так почему бы и не воспользоваться РСУБД в этом случае?


                                      1. vintage
                                        17.09.2015 00:23
                                        #8576245

                                        А зачем, если специализированное key-value хранилище можно сделать более производительным? :-)


                                        1. MacIn
                                          17.09.2015 00:44
                                          #8576273

                                          Например, чтобы использовать одно, унифицированное средство хранения данных, а не два разношерстных. Да и какова разница в производительности? Я без сарказма — на самом деле интересно. Вон, многие пишут, что производительнее. Есть реальные примеры, с числами?


                                          1. vintage
                                            17.09.2015 00:57
                                            #8576291

                                            «А зачем использовать универсальное средство, если всё-равно его реляционными штучками не пользуешься?» — поэтому и запилили специализированные СУБД без того, чем не пользовались.

                                            Да чисел разных в интернетах полно. Вот, например: github.com/benstopford/awesome-db-benchmarks
                                            www.techempower.com/benchmarks


                                            1. MacIn
                                              17.09.2015 01:48
                                              #8576325

                                              поэтому и запилили специализированные СУБД без того, чем не пользовались.

                                              А если уже пользуешься, зачем второй движок? РСУБД повсеместны.

                                              Замечательно, спасибо за ссылки.
                                              В случае первой единственный тест, который подходит для сравнения — это сравнение MySQL и MongoDB.
                                              static.ph.ed.ac.uk/dissertations/hpc-msc/2012-2013/RDBMS%20vs%20NoSQL%20-%20Performance%20and%20Scaling%20Comparison.pdf

                                              В принципе, документ отражает, что во всех тестах «победитель» зависит от конфигурации и в большинстве испробованных конфигураций это MySQL(для выборки, см. графики 4.1 и далее). Кроме последнего теста со сложным вложенным запросом, где безусловным победителем с серьезным отрывом выходит MongoDB. Ценой, как отмечено, денормализации, в отличие от РСУБД, которая была нормализована. Но это совсем не простой key-value — про простой случай см. выше.
                                              Для вставок и др. операций результаты другие, т.е. однозначного «NoSQL быстрее» или наоборот, нет.


                                              1. vintage
                                                17.09.2015 11:26
                                                #8576713

                                                Специализированные могут быть быстрее за счёт специализации. Например Redis по бенчмаркам гораздо быстрее MongoDB (хотя, скорее всего ценой надёжности).


                              1. vedenin1980
                                16.09.2015 15:34
                                #8575515

                                Почему нет? В чем проблема-то? В создании кластера? В создании правильной архитектуры? Где вы увидели ограничение на количество данных в «SQL»?

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

                                1 млрд. записей — это много или мало? А 1 трлн?

                                Мало, размер поискового индекса гугла десятки и сотни трлн. записей.

                                Скажите, big data — это какой размер?

                                От десятка терабайт до сотен петабайт.

                                Честно говоря — я минут 15 сидел и пытался представить приложение, которое использует только kye-value или только документ-ориентированое без связей. Не смог. Подскажете?

                                1) Легко, действия пользователя с рекламой на сайте (гугл аналитикс и яндекс директ и ему подобные сервисы). Увидел пользователь объявление — ушел запрос к key-value с его данными, кликнул на объявление — ушел второй запрос к key-value, закрыл рекламу — третий запрос. Потеря небольшого кол-ва данных не сильно важна, городить sql нет смысла, так как запросы именно что единичные (и не связанные с остальным сайтом, который вообще может быть не нашим, как в случае гугла аналитика).
                                2) с документ-ориентированое без связей — любые посты на сайте без комментариев, доски объявлений, каталоги, новостные порталы, любые сайты с преимущественно статическим контентом. Без связей не значит что в документе не будет url'ов, значит что идти по этим связям чтобы получить инфу не нужно. К тому же, никто не мешает совмещать sql и nosql на одном сайте.

                                Сейчас мы скатимся к тому, что разработчики данных компаний криворукие…

                                Ну это вы обвиняете что гугл, твитер и прочие гиганты не понимают что могли бы прекрасно жить с одними СУБД, зачем-то затеяли игры с нестабильным nosql.


                                1. aktuba
                                  16.09.2015 16:16
                                  #8575581

                                  vintage:

                                  И первое, и второе утверждения абсолютно верны. Но тут нужна некая оговорка: при не правильной архитектуре. Например, fb когда-то заявляли (ссылку не дам, просто отложилось в памяти), что юзают sql, но без джойнов. Такой подход вполне имеет право на жизнь, верно? Причем, решая проблему первого вашего утверждения.

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

                                  vedenin1980:

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

                                  Пруфа нет. А существует пруф, который доказывает невозможность подобного?

                                  Мало, размер поискового индекса гугла десятки и сотни трлн. записей.

                                  Ух-ты… Big data — это только гугл? Не знал). Это раз. Два — откуда такая информация? Три — где пруф, что «десятки и сотни трлн. записей» — это big data? Четыре — где пруф, что такое количество записей нельзя сохранить в sql? Ну и пять — какие именно записи? Что-то мне подсказывает, что та же монга не переварит подобное количество, особенно если делать выборки с or/and в перемешку.

                                  От десятка терабайт до сотен петабайт.

                                  Пруф? А то мне тут некоторые товарищи доказывали, что big data — это от 1М записей)))). Без уточнения структуры записей, размера и пр. характеристик.

                                  Легко, действия пользователя с рекламой на сайте (гугл аналитикс и яндекс директ и ему подобные сервисы).

                                  Не, не подходит. Точнее — только частично подходит (увидел и закрыл). Клик — уже не прокатывает. Необходимо списать деньги с рекламодателя, сохранить статистику по данному виду рекламы, источнику, самому пользователю. Да, это можно разбить в несколько заходов, часть выполнить в фоне, эмулировать транзакционность и пр. Но по сути, это попытка реализовать реляционность на базе nosql. Если добавим сюда отслеживание какую рекламу уже смотрел пользователь (чтобы не выводить повторно), какую рекламу рекомендовать или запретить — вообще печально получается…

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

                                  Отличной пример для big data! Вопрос — где в данном примере плюс nosql перед sql?

                                  Ну это вы обвиняете что гугл, твитер и прочие гиганты не понимают что могли бы прекрасно жить с одними СУБД, зачем-то затеяли игры с нестабильным nosql.

                                  Так, стоп. Где это я заявлял подобное? Можно пруф? Вроде как говорил, что «наравне с nosql используют и рсубд» (http://habrahabr.ru/company/mailru/blog/266811/?reply_to=8575515#comment_8574575). Зачем вы мне приписываете свои неверные выводы?


                                  1. vintage
                                    16.09.2015 16:49
                                    #8575637
                                    +2

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

                                    Может опишите правильную архитектуру, где схема никогда не меняется или где продолжительный alter table является плюсом, а не минусом?


                                    1. gandjustas
                                      16.09.2015 21:25
                                      #8576011
                                      -1

                                      Продолжительный alter table бывает только в mysql. Все взрослые движки умеют делать metadata-only operation добавления колонки.


                                      1. vintage
                                        16.09.2015 21:50
                                        #8576041

                                        Добавление колонки — наиболее простой вид изменения схемы :-)


                                        1. gandjustas
                                          16.09.2015 21:54
                                          #8576055

                                          А какие операции есть, которые потребуют длительных операций в РСУБД и не потребуют таковых в NoSQL?


                                          1. vintage
                                            16.09.2015 22:01
                                            #8576063

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


                                            1. gandjustas
                                              17.09.2015 01:39
                                              #8576321

                                              В sql делают наоборот. Обновляют схему, скрывая изменения за view, а потом обновляют код. И никаких разных форматов.


                                              1. vintage
                                                17.09.2015 11:32
                                                #8576725

                                                1. Обновление схемы в общем случае — долгий процесс.
                                                2. Миграция в общем случае — это изменение схемы плюс трансформация данных. Для второго в любом случае нужен программный код.
                                                Как тут поможет «скрытие изменений за view» — ума не приложу.


                                                1. gandjustas
                                                  17.09.2015 13:32
                                                  #8576987

                                                  Скрытие изменений за view поможет так, что приложение не узнает об изменении схемы. Это для того, чтобы ничего не останавливать на время миграции.


                                                  1. vintage
                                                    17.09.2015 14:03
                                                    #8577069

                                                    Понял о чём вы, но это половинчатое решение. Ведь само изменение схемы (например, меняем int на bigint) на большом числе записей может быть очень долгим в РСУБД.


                                1. gandjustas
                                  16.09.2015 21:45
                                  #8576029
                                  -1

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

                                  А разве есть пруфы того же самого для NoSQL? Особенно за пределами гугла и fb.

                                  Я вот работаю с несколькими банками, там процессинг в Oracle. Порядка 100 трлн операций.
                                  Это бигдата?
                                  Есть хоть один пример аналога на NoSQL?


                                1. gandjustas
                                  16.09.2015 21:52
                                  #8576047
                                  -1

                                  Мало, размер поискового индекса гугла десятки и сотни трлн. записей.

                                  Поисковый индекс и РСУБД — совершенно разные вещи. В индексе нет операций конкурентного обновления, то есть он для пользователя read-only. Это означает, что можно индекс раскидать по любому количеству серверов и добавлять быстродействие путем вливания дополнительного бабла в серваки.

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


              1. nsinreal
                16.09.2015 00:21
                #8574515

                построением кешей

                Так-так, я тут вижу слово «кеш», а ниже вижу слова «целостность» и «согласованность». Это вгоняет меня в какой-то диссонанс. Не, я понимаю как можно юзать кеш и обеспечивать целостность и согласованность, но все же ). Кстати, а кеш — это sql или nosql?

                Мало того, что нету никакого контроля целостности на прикладном уровне, так еще и резервное копирование и восстановление не всегда работает как надо.

                Контроль целостности? Как много я могу проконтролировать на уровне sql-сервера? Или вот еще вопрос: почему в интернетах рекомендуют выпиливать reference constraints при работе с большим объемом данных?
                Ну и еще. В большинстве систем количество чтений больше количества записей, значит имеет смысл делать денормализованную бд, а то рано или поздно упрешься в то, что подгрузка данных занимает долгое время. Чем мне пожертвовать, перфомансом или честной реляционностью и честнейшей гарантированной sqlем согласованностью?

                По поводу проблем с копированием и восстановлением — ну это больше уже проблема конкретных молодых баз данных. Впрочем, старость продуктов на основе sql сервера тоже не всегда помогает вытянуть данные из покрашевшейся бд.

                Также NoSQL редко встречается в задачах с конкурентным доступом к данным

                Странно, а я то думал, что key-value store (а они тоже вполне себе NoSQL решения) с атомарными операциями и compare&swap операциями обеспечивают хорошую производительность и согласованность данных. Алсо, честные быстрые конкуррентные транзакции в SQL — это очень и очень тяжко. Я не буду убеждать вас, что транзакционность не нужна. Да, она в 50% случаев нафиг не нужна, в 40% случаев её делают неправильно и просто не замечают проблем, а в 10% случаях она реально нужна. Но просто транзакционность можно делать по разному, не только через автоматически расставленные sql сервом локи и кривой недопиленный mvcc.


                1. gandjustas
                  16.09.2015 01:20
                  #8574581

                  Так-так, я тут вижу слово «кеш», а ниже вижу слова «целостность» и «согласованность». Это вгоняет меня в какой-то диссонанс. Не, я понимаю как можно юзать кеш и обеспечивать целостность и согласованность, но все же ). Кстати, а кеш — это sql или nosql?

                  Начну с конца — так будет понятнее. Кеш — не хранилище. Поэтому не имеет смысла говорить о SQL или NoSQL. У него нет задачи долговременного хранения данных. Хотя инструменты типа Redis могут сохранять состояние кеши от этого хранилищами не становятся. Задача у любого кеша — сделать данные «ближе» к потребителю.

                  Отличительная особенность кеша — его всегда можно сбросить и пересобрать из долгосрочного хранилища. Важный вопрос — когда сбросить. А если у нас есть хранилище (хотя это может быть тот же самый Redis), то его сбрасывать нельзя.

                  Диссонанс у вас от того, что вы не понимаете задач кеша и хранилища, тем более что некоторые решения для кеширования позиционируются как NoSQL базы данных.

                  Как много я могу проконтролировать на уровне sql-сервера?

                  Во взрослых движках — сколь угодно много.

                  Или вот еще вопрос: почему в интернетах рекомендуют выпиливать reference constraints при работе с большим объемом данных?
                  Это довольно странный совет, который скорее вреден, чем полезен. Я знаю только один сценарий когда отключение контроля целостности оправдано — загрузка большого объема данных. Но почти во всех базах можно просто отключить временно проверки и не удалять внешние ключи.

                  В большинстве систем количество чтений больше количества записей, значит имеет смысл делать денормализованную бд, а то рано или поздно упрешься в то, что подгрузка данных занимает долгое время. Чем мне пожертвовать, перфомансом или честной реляционностью и честнейшей гарантированной sqlем согласованностью?

                  Идеи про денормализованность — совершенно бредовые для OLTP.

                  Для начала в каждой серьезной системе должен быть кеш для запросов, которые редко меняются. Это сразу снимает 90% вопросов быстродействия.

                  Далее в каждой серьезной БД есть материализованные представления, которые позволяют не нарушать целостность и поддерживать «денормализацию». Это снимет еще 90% из оставшихся.

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

                  Это снимет 90% вопросов из оставшихся. Но в большинстве систем это уже перебор, обычно на втором шаге можно остановиться.

                  Я вам расскажу краткую историю откуда денормализация взялась.
                  Когда у нас возникает OLAP задача — то есть анализ большого объема данных с вычислением агрегатных функций, то возникает проблема с так-называемыми snowflake джоинами. Когда центральная таблица фактов джоинится с кучей таблиц измерений, а те в свою очередь джоинятся с другими таблицами. Оказалось, что эффективного алгоритма оптимизации таких джоинов нет и статистика не помогает. Поэтому рекомендуется денормализовывать таблицы в хранилищах для OLAP, чтобы быстрее работали такие запросы.

                  Еще раз повторю — чтобы денормализация была эффективной нужны большие выборки и snowflake джоины, при этом фильтры задаются пользователем интерактивно и заранее запросы неизвестны.

                  В OLTP я такое видел крайне редко и решается обычно через кеши и материализованные представления.

                  а я то думал, что key-value store (а они тоже вполне себе NoSQL решения) с атомарными операциями и compare&swap операциями обеспечивают хорошую производительность и согласованность данных

                  Они не обеспечивают ничего. Очень мало задач, которые можно свести к получению элемента по ключу и обновлению элемента по ключу. Возникает вопрос как найти список нужных ключей, да еще и в нужном порядке. В key-value один вариант — хранить список где-то. Но вот тут как раз и наступает жопа, когда два пользователя пытаются добавить ключ в список.

                  Вообще для key-value идеальное решение — файлы на диске. Ключ — имя, value — содержимое. Работает быстрее и надежнее любой базы.

                  Да, она в 50% случаев нафиг не нужна, в 40% случаев её делают неправильно и просто не замечают проблем, а в 10% случаях она реально нужна.
                  Проблема в том, что на старте проекта крайне сложно сказать где не нужна будет транзакционность. При этом во взрослых движках можно отключить и механизмы конкуренции, и сделать delayed durability, и inmemory storage задействовать. А в nosql нельзя «включить» транзакционность, если её не было. Поэтому при прочих равных лучше выбирать SQL-базу и добавить кеш для скорости, чем писать тонну кода, чтобы хоть какое-то подобие согласованности поддерживать в nosql. За исключением некоторых специфических сценариев.


                  1. nsinreal
                    16.09.2015 02:07
                    #8574613

                    Диссонанс у вас от того, что вы не понимаете задач кеша и хранилища, тем более что некоторые решения для кеширования позиционируются как NoSQL базы данных.

                    Не-не, диссонанс у меня из-за того, что данные в кеше будут или грязными, или устаревшими. Другого не дано. В такой постановке вопроса рассказывать про целостность когда я на UI могу увидеть херню вместо данных это немного странно. При этом кеш вносит еще больше проблем связанных с тем, что одни и те же данные нужно абсолютно по разному забирать в зависимости от задач (для выборки данных для UI). Т.е. не просто по разному (что решалось бы кое-каким универсальным кодом), а абсолютно по разному.

                    Во взрослых движках — сколь угодно много.

                    Покажите мне взрослые движки, пожалуйста. Я сейчас про кейсы типа «к сущности можно привязать не больше n количества других сущностей, где n — число заданное в конфигурации этой сущности» (ну или хотя бы где n — константа) и прочие милые вещи.

                    Я знаю только один сценарий когда отключение контроля целостности оправдано — загрузка большого объема данных. Но почти во всех базах можно просто отключить временно проверки и не удалять внешние ключи.

                    Ну да, я про этот сценарий и говорю. И тут началось, временное отключение проверок, давайте в жопу пошлем целостность на время. Вместо того, чтобы поддерживать целостность на уровне приложения всегда и приучиваться к такому стилю программирования мы будем делать другое. Мы временами когда припекет, заставим программистов, не привыкших к стилю контроля целостности на уровне приложения будем заставлять писать код, который гарантирует подобного рода целостность.

                    Далее в каждой серьезной БД есть материализованные представления, которые позволяют не нарушать целостность и поддерживать «денормализацию»

                    Ага, вот только пойдите в документацию своего взрослого движка и сравните ограничения на материализованных вьюхи и обычные вьюхи. А еще можно триггеры хуячить, чо бы и нет. Вообще минимум ограничений. Только производительность при вставке/апдейте проседает, потому что механизмы универсальные и неидеальные.

                    Идеи про денормализованность — совершенно бредовые для OLTP.

                    Это значит что в вашей практике не было необходимости делать денормализацию бд или вы готовы подкрепить подобные заявления чем-то?

                    Очень мало задач, которые можно свести к получению элемента по ключу и обновлению элемента по ключу

                    Прикалываетесь или как? Реляционная субд построена на идее индексов (да, можно сделать таблицу без кластерного индекса, я знаю). Индекс — это (key) — (included fields + primary key of value), т.е. key — value. Реляционная субд — это key-value, какие-то гарантии транзакционности и атомарности, а также query language, который не заставляет пересылать данные туда-сюда для того чтобы сделать joinы. Вопрос в том, насколько эффективнее реляционная субд по сравнению с мануальной обработкой всего этого.

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

                    Ну тут я тоже могу сослаться на взрослые движки, которые позволяют добавить в спискок конкуррентно. Пространство nosql решений весьма обширное.

                    Вообще для key-value идеальное решение — файлы на диске. Ключ — имя, value — содержимое. Работает быстрее и надежнее любой базы.

                    Чушь.

                    Проблема в том, что на старте проекта крайне сложно сказать где не нужна будет транзакционность

                    Вы этой фразой переводите реляционные БД в область инструментов для прототипирования, нет?

                    При этом во взрослых движках можно отключить и механизмы конкуренции

                    Пруфы плиз. Меня интересует полное отключение writer-writer locking. Какие взрослые движки это умеют? Вообще у меня скаладывается впечатление, что ни один из нас не видит полноценно картину.

                    Поэтому при прочих равных лучше выбирать SQL-базу и добавить кеш для скорости, чем писать тонну кода, чтобы хоть какое-то подобие согласованности поддерживать в nosql

                    А когда проседает и выборка, и вставка, что делать? Тонны кода — это весьма громогласное утверждение, если вы пишете объемную систему.

                    За исключением некоторых специфических сценариев.

                    Вопрос в том, насколько часто у вас проявляются специфичные сценарии. А вообще, если был груб, то извините, моя злость на реляционные БД сопряжена попытками получить приемлемую производительность там, где было бы разумнее заюзать key-value хранилища вместо «детского» движка )


                    1. gandjustas
                      16.09.2015 02:25
                      #8574623

                      Не-не, диссонанс у меня из-за того, что данные в кеше будут или грязными, или устаревшими.

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

                      Покажите мне взрослые движки, пожалуйста.

                      SQL Server, Oracle, DB2 и к ним приближается Postgres.

                      Ну да, я про этот сценарий и говорю.

                      И как часто встречается такая проблема в OLTP? На моем опыте — один из ста.

                      Ага, вот только пойдите в документацию своего взрослого движка и сравните ограничения на материализованных вьюхи и обычные вьюхи
                      Если речь идет об оптимизации джоинов, то почти нет.

                      А еще можно триггеры хуячить, чо бы и нет. Вообще минимум ограничений. Только производительность при вставке/апдейте проседает, потому что механизмы универсальные и неидеальные.
                      А денормализация бесплатная чтоли?

                      Это значит что в вашей практике не было необходимости делать денормализацию бд или вы готовы подкрепить подобные заявления чем-то?

                      Конечно могу. Я неоднократно оптимизировал приложения путем убирания ручной денормализации.

                      Вопрос в том, насколько эффективнее реляционная субд по сравнению с мануальной обработкой всего этого.
                      На несколько порядков, так как оптимизирует чтение с диска. Диск — самая медленная часть компьютера. NoSQL обычно оптимизируют доступ в памяти, но и inmemory движки взрослых СУБД делают то же самое.

                      Ну тут я тоже могу сослаться на взрослые движки, которые позволяют добавить в спискок конкуррентно.
                      Названия в студию. А еще крайне желательно описание как они это делают. В монге вообще долгое время был лок на базу, потом на коллекцию, только недавно прикрутили локи на документы. И это при том, что у монги возможности поддержания согласованности крайне низкие.

                      Меня интересует полное отключение writer-writer locking. Какие взрослые движки это умеют?
                      Oracle, SQL Server они умеют read commited snapshot. Фактически не навешивает блокировки при записи. Насчет DB2 не уверен.

                      А когда проседает и выборка, и вставка, что делать?
                      Миллион рецептов в зависимости от субд. В SQL Server есть partition switching.

                      Вопрос в том, насколько часто у вас проявляются специфичные сценарии.
                      Крайне редко, именно поэтому сценарии специфические.


                      1. nsinreal
                        16.09.2015 03:04
                        #8574653
                        -1

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

                        Блять, ты вообще читаешь что ты пишешь? Ты говоришь о трудностях обеспечения согласованности и целостности nosql бд и при этом говоришь о легкости обеспечения согласованности двух независимых хранилищ. Как это?

                        SQL Server

                        Тоже мне. серьезный взрослый движок.

                        И как часто встречается такая проблема в OLTP? На моем опыте — один из ста.

                        На твоем опыте.

                        Если речь идет об оптимизации джоинов, то почти нет.

                        И как у SQL Serverа с материализованными вьюхами, содержащими left joinы? А никак, нельзя такие. И множество функций юзать тоже нельзя в материализованных вьюхах.

                        Конечно могу. Я неоднократно оптимизировал приложения путем убирания ручной денормализации.

                        Господи, да никто не спорит, что денормализированная бд может слоупочить. И никто не спорит, что неправильный дизайн тоже может слоупочить. Но я просил пруфы, что денормализация это вредный совет в 100% случаев. Меньше не надо, а то по совокупности моих претензий может выйти что юзать не sql решение.

                        Oracle, SQL Server они умеют read commited snapshot. Фактически не навешивает блокировки при записи. Насчет DB2 не уверен

                        SQL Server снепшоты умеет через tempdb. Я хотел снять нагрузку с бд удалив writer-writer lock, мне предлагают юзать tempdb, который тоже вполне себе нагружает бд. Это не то, что я хочу от бд. Я хочу чтобы она позволила мне вставить несколько тысяч записей конкурентно, тратя ресурсы только на реорганизацию индексов. Это плата за умность реляционных бд — они не дают тебе сделать того, в чем ты уверен. А я уверен, что никто не будет трогать мои новые записи до того, как я завершу их вставку, поэтому мне лок на них не нужен.

                        В SQL Server есть partition switching

                        У SQL Server 2008 лимит на количество партиций был в тысячу. Сейчас вроде повыше, но все равно константа. Что как бы позволяет плясать, но не очень сильно и хорошо.

                        Названия в студию. А еще крайне желательно описание как они это делают

                        Вы знаете, тут меня подловили. Я понадеялся на redis, у которого есть стандартная возможность добавлять в список, но там ничего не сказано по поводу того, насколько хорошо обрабатывается конкурентность (так что можно только надеяться на то, что там все ок). Понадеялся на другие key-value stores — так там стандартное решение это юзать key ranges (а это подходит под эти цели, но концепт немного другой). Ну или обычно это не спефика для решений, которые должны быстро работать и шардиться. Так что сорри, тут обманул.

                        Крайне редко, именно поэтому сценарии специфические.

                        Они для вас специфические. Вам не кажется, что специфические для вас сценарии в других проектах могут происходить чаще? Или хуже того, что с развитием сложности проектов специфичные решения станут все более и более частыми?


                        1. gandjustas
                          16.09.2015 03:37
                          #8574679
                          +2

                          Блять, ты вообще читаешь что ты пишешь? Ты говоришь о трудностях обеспечения согласованности и целостности nosql бд и при этом говоришь о легкости обеспечения согласованности двух независимых хранилищ. Как это?
                          Повторяю:
                          Механизм обеспечения целостности кеша — сброс и пересбор из хранилища. Сброс кеша сложная задача, но решаемая.
                          Механизм обеспечения целостности в хранилище — транзакции и проверки. Это тоже сложная задача, но тоже решаемая.
                          Почти все NoSQL базы занимают промежуточное положение. Они вроде как хранилища, но без транзакционности, с другой стороны кеш, но без возможности сброса.,

                          Тоже мне. серьезный взрослый движок.

                          Ну он по крайней мере умеет честную сериализованность транзакций делать, а oracle — не умеет.
                          И как у SQL Serverа с материализованными вьюхами, содержащими left joinы? А никак, нельзя такие. И множество функций юзать тоже нельзя в материализованных вьюхах.
                          И что? Вы вообще агитируете за NoSQL где никаких джоинов нет, вроде как не мешает программы писать.

                          Но я просил пруфы, что денормализация это вредный совет в 100% случаев.
                          Какие пруфы вам нужны?
                          Вам очевидно, что денормализация требует больше ресурсов при записи?
                          Вам очевидно, что денормализация требует больше кода?
                          Вам очевидно, что денормализация — не гарантия более быстрых запросов?
                          Надеюсь вы из этого сможете сделать вывод.

                          Если не очевидно, тогда можно не продолжать.

                          SQL Server снепшоты умеет через tempdb
                          И что? Это вовсе не означает что будет реальная запись на диск. Вы в курсе как buffer pool работает?

                          У SQL Server 2008 лимит на количество партиций был в тысячу. Сейчас вроде повыше, но все равно константа. Что как бы позволяет плясать, но не очень сильно и хорошо.
                          Про partition merge в курсе?

                          Вы знаете, тут меня подловили. Я понадеялся на redis, у которого есть стандартная возможность добавлять в список, но там ничего не сказано по поводу того, насколько хорошо обрабатывается конкурентность (так что можно только надеяться на то, что там все ок).
                          В редисе добавление в список лочит список. Спасает только то, что это все в памяти. Но в том же SQL Server inmemory можно добиться того же эффекта без лока на всю inmem таблицу.

                          Вам не кажется, что специфические для вас сценарии в других проектах могут происходить чаще?
                          Понимаете в чем фишка. Большая часть программистов, которая работает с базами, делает учетные системы в том или ином виде. А для них сценарии, где пригодны NoSQL базы, ну крайне специфические.


                          1. nsinreal
                            16.09.2015 03:55
                            #8574697

                            Механизм обеспечения целостности кеша — сброс и пересбор из хранилища. Сброс кеша сложная задача, но решаемая.
                            Механизм обеспечения целостности в хранилище — транзакции и проверки. Это тоже сложная задача, но тоже решаемая.

                            А механизм обеспечения целостности кеша и хранилища вместе? На каждую стартующую транзакцию сбрасывать кеш и блокировать его, пока транзакция не завершится? Я только это вижу в качестве решения противодействию нахождении в кеша старых данных.


                            1. gandjustas
                              16.09.2015 04:04
                              #8574709

                              Тут проблема в том, что в кеше тогда нужно держать список ключей всех строк, на основании которых кеш построен. То есть при любой записи нужно обходить весь кеш и находить те записи, которые нужно сбрсить. Дорогое удовольствие.

                              Приложение может алгоритмически вычислять ключи кеша для сброса, а база этого сделать не может.


                          1. nsinreal
                            16.09.2015 03:59
                            #8574701

                            Вам очевидно, что денормализация требует больше ресурсов при записи?
                            Вам очевидно, что денормализация требует больше кода?
                            Вам очевидно, что денормализация — не гарантия более быстрых запросов?

                            Интересно пишешь. Первые два утверждения абсолютные, третье не абсолютное. «Не гарантия» — т.е. может не быть, а может и быть.
                            И отсюда у тебя вывод что в 100% случаев денормализация это вредный совет (да, я там фиксировал на 100%, но вы же не поправили «в редких случаях»). Если бы третье было бы абсолютным, то в совокупности с другими утверждениями по законам логики вывод был бы правильным. Но третье утверждение не является абсолютным (и ты это понимаешь), поэтому вывод неправильный.


                            1. gandjustas
                              16.09.2015 04:12
                              #8574721

                              А я не говорил, что денормализация в 100% случаев плохо. Я лишь комментировал ваше утверждение

                              В большинстве систем количество чтений больше количества записей, значит имеет смысл делать денормализованную бд

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

                              В большинстве случаев надо делать кеш.


                          1. nsinreal
                            16.09.2015 04:00
                            #8574705

                            Почти все NoSQL базы занимают промежуточное положение. Они вроде как хранилища, но без транзакционности, с другой стороны кеш, но без возможности сброса.

                            А что если этого достаточно для реализации транзакционности руками?


                            1. gandjustas
                              16.09.2015 04:05
                              #8574711

                              А что если этого достаточно для реализации транзакционности руками?

                              Проблема в том, что сегодня может быть достаточно, а завтра требования поменяются и станет не достаточно и что тогда делать?


                          1. nsinreal
                            16.09.2015 04:03
                            #8574707

                            И что? Это вовсе не означает что будет реальная запись на диск. Вы в курсе как buffer pool работает?

                            Мм, т.е. вы таки хотите сказать что in-memory MVCC быстрее чем запись вообще без локов на свежезаписанные записи?


                            1. gandjustas
                              16.09.2015 04:09
                              #8574715

                              При добавление записей в inmemory с MVCC не возникает никаких локов. Только атомарные операции.


                              1. nsinreal
                                16.09.2015 04:11
                                #8574719

                                Есть таблица, она должна быть не in-memory и персистентной. В неё нужно вставлять много записей временами. MVCC — это дополнительный оверхед на ресурсы, не IO диска, так память. Локи это тоже дополнительный оверхед на ресурсы. Без локов, без mvcc, руками — невозможно в SQL Server, но даст отсутствие лишнего оверхеда. Я об этом говорю, о избавлении от оверхеда вообще


                                1. gandjustas
                                  16.09.2015 04:15
                                  #8574725

                                  Я говорю о том же самом. inmemory таблицы тоже пишутся на диск. Но для них не пишутся индексы. Поэтому можно иметь быстрые выборки с помощью хеш-индексов (O(1)) и не иметь оверхеда блокировок при добавлении записей. Еще раз — mvcc для inmemory не использует блокировки вообще.

                                  А еще можно включить delayed durability чтобы не ждать записи на диск.


                          1. nsinreal
                            16.09.2015 04:07
                            #8574713
                            -1

                            Понимаете в чем фишка. Большая часть программистов, которая работает с базами, делает учетные системы в том или ином виде. А для них сценарии, где пригодны NoSQL базы, ну крайне специфические.

                            У меня фишка прикольнее. Я долго не мог осознать как писать решения на чистых key-value storах. Для меня это было на грани «вы че ебанутые, а как транзакции, а как же атомарность, я че руками должен это делать все?». Потом со временем в голову начало приходить, что я могу последовательно переписывая многие вещи отказаться от многих кейсов использования sql. При этом получить профит. Хотя это и трудно моментами продумать. Но я понимаю о чем вы говорите.


                      1. nsinreal
                        16.09.2015 03:35
                        #8574677
                        -1

                        А денормализация бесплатная чтоли?

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


                        1. gandjustas
                          16.09.2015 03:38
                          #8574681

                          Мои замеры показывают ровно обратное.


                          1. nsinreal
                            16.09.2015 04:13
                            #8574723

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


    1. MacIn
      15.09.2015 23:28
      #8574461

      Для многих задач NoSQL решения подходят лучше реляционных БД.

      Например?


      1. vedenin1980
        16.09.2015 00:32
        #8574529
        +1

        Хранение ключ-значение, когда мы всегда работает со значением целиком (key-value хранилища), хранение целого документа без всяких связей с другими документами (документные хранилища вроде монги), хранение сложных графов и деревьем (графичиеские базы данных), хранение огромных файлов, очень быстрое хранилище в памяти. Эмулировать с помощью СУБД все это обычно можно, но обычно весьма дорогой ценой.


        1. MacIn
          16.09.2015 00:43
          #8574543
          -2

          Эмулировать с помощью СУБД все это обычно можно, но обычно весьма дорогой ценой.

          Отчего же? Key-value — очень запросто реализуется, файлы — тоже.


          1. vedenin1980
            16.09.2015 01:00
            #8574563
            +1

            Реализуется, но засчет времени отклика, производительности сервера, затрат на место на диске. Чудес не бывает, in-memory key-value хранилище будет работать быстрее (и с меньшими затратами ресурсов), чем СУБД которой нужно сначала SQL запрос распарсить, потом индексы перестроить и дождаться честной записи на жесткой диск. Тоже самое с записью/чтением цельного json документа монго и join'ами по десятку баз СУБД, чтобы записать те же данные.


            1. vintage
              16.09.2015 01:14
              #8574571
              +1

              1. Есть реляционные СУБД и не реляционные.
              2. Реляционные тоже могут быть in-memory.


              1. vedenin1980
                16.09.2015 01:25
                #8574587

                2. Могут, только задачи парсинга sql запросов и перестройки индекса это же не отменяет. К тому же key-value не требуется поддержка всех возможностей sql запросов и они могут оптимизировать свою работу за счет хорошо оптимизированых хэш-таблиц с доступом O(1), в то время как СУБД обычно использует бинарное дерево c его O(log n).


                1. gandjustas
                  16.09.2015 01:43
                  #8574601
                  -2

                  Могут, только задачи парсинга sql запросов и перестройки индекса это же не отменяет.

                  Запрос парсится ровно один раз.

                  К тому же key-value не требуется поддержка всех возможностей sql запросов и они могут оптимизировать свою работу за счет хорошо оптимизированых хэш-таблиц с доступом O(1), в то время как СУБД обычно использует бинарное дерево c его O(log n).

                  Вы в курсе, что взрослые движки РСУБД имеют inmemory движки с хеш-индексам, по сути хеш-таблицами в памяти?
                  А для чтения данных с диска пока что ничего быстрее b+-деревьев не придумали. Даже Mongodb использует древообразные индексы.


                  1. nsinreal
                    16.09.2015 02:12
                    #8574615
                    +1

                    Запрос парсится ровно один раз.

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


                    1. gandjustas
                      16.09.2015 02:27
                      #8574627

                      Не бинарный код, а план запроса. Хотя Native Stored Proc в SQL Server позволяет процедуры скомпилировать в бинарный код.

                      Все РСУБД научились кешировать планы примерно 15 лет назад.


                      1. nsinreal
                        16.09.2015 03:32
                        #8574671
                        -1

                        Про то, что есть кеширование планов не знает только ленивый. Native Stored Proc работает только с memory таблицами.


                        1. gandjustas
                          16.09.2015 04:16
                          #8574727

                          Это вы утверждаете, что запрос парсится каждый раз.


                          1. nsinreal
                            16.09.2015 04:18
                            #8574729

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


                            1. gandjustas
                              16.09.2015 04:20
                              #8574733

                              Вам процитировать ваше сообщение?

                              Если запрос есть в кеше, то больше никаких операций не происходит. По хешу достается план и запускается выполнение.


                  1. vedenin1980
                    16.09.2015 02:35
                    #8574635

                    Запрос парсится ровно один раз

                    Если мы пошлем миллион запросов «insert database1.table1 value (valueN);» в разных сессиях, где valueN — каждый раз новое значение, то сколько раз будут парситься запросы? Один или миллион?
                    Не говоря уже о том что кроме парсинга запроса, СУБД поднимет список всех баз, потом список всех таблиц, потом список прав данного пользователя на эту таблицу, то есть ещё до того как вообще-то что-то сделать СУБД уже выполнила три запроса к трем таблицам.


                    1. gandjustas
                      16.09.2015 02:38
                      #8574641

                      Миллион.
                      Но в здравом уме никто так не пишет, все используют параметры.

                      Кроме того для примитивных запросов есть автопараметризация. Там конечно выполняется парсинг, но построение плана не происходит.


            1. MacIn
              16.09.2015 15:15
              #8575465

              Так мы о in-memory или о НЕ реляционных дисковых? Если говорить о дисковых, то надо сравнивать дисковые key-value с дисковыми СУБД. Если вы делаете простой запрос, такой же, как для ke-value, т.е. "дай мне значение из колонки Х где колонка У = N", это такой примитив, про «парсинг» которого смешно говорить. Самые большие затраты — на ввод-вывод, а не парсинг чего-либо в памяти.
              Индексы перестроить? В вашем key-value нет индекса? Ваш key-value не пишет на диск?


          1. nsinreal
            16.09.2015 01:10
            #8574569
            +4

            Потому что реляционная бд это универсальное решение, которое предназначено хоть как-то работать со всем чего от неё ожидают. Это цена универсальности.
            Key-value хранилище заточенно под определенные задачи. Любое заточенное решение по определению потенциально должно работать лучше чем универсальное решение. За конкретными бенчмарками можно сходить в гугл.
            Но вообще, если я вас не убедил, то ответьте на такой интересный вопрос: зачем на рынке появляются отдельные key-value хранилища когда уже 40 лет есть замечательные и восхитительные реляционные БД. И уж тем более, зачем люди меняют замечательные и восхитительные реляционные БД на унылые key-value хранилища, они чо упоротые?


            1. MacIn
              16.09.2015 15:17
              #8575469

              За конкретными бенчмарками можно сходить в гугл.

              Так вот это и хочется выяснить, задавая вопрос о том, зачем они нужны. А с гуглом я и сам поговорить умею. Зачем тогда тут общаться? Можно не выкладывать статьи и не обсуждать их. Зачем? Ведь каждый может в гугле ввести запрос и найти информацию.
              Все-таки надеешься, что человек сможет ответить по существу, например «у нас используется для xyz операций (с конкретикой) — оказалось, что работает в n раз быстрее и ест меньше ресурсов при хранении».

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


        1. gandjustas
          16.09.2015 01:26
          #8574589
          -2

          Все это прекрасно делается в любой взрослой СУБД.


        1. DarthVictor
          16.09.2015 13:13
          #8575249

          А зачем в таком случае отдельная СУБД? Файловая система с такой задачей не лучше справится? Находить файл по ключу. Я не троллю, я серьезно не видел серьезных сравнений и потому спрашиваю.


          1. nsinreal
            16.09.2015 14:02
            #8575319
            +1

            а) файловые системы не любят когда файлов слишком много. Базовый совет по огранизации file storage на основе файловой системы — взять guid или хеш и его части использовать как вложенные поддиректории.
            б) много мелких файлов — гарантия фрагментации
            в) файловая система медленная, поверх неё нужна еще in-memory прослойка. Тупо mapить такое количество файлов не выйдет — их слишком много и они мелкие. Не говоря уже о том, что часть данных не будет помещаться в ОЗУ.
            г) key-value хранилища бывают разные, некоторые с поддержкой транзакций

            Бенч увы не приведу, это только общие рассуждения.


            1. DarthVictor
              17.09.2015 10:56
              #8576661

              Просто есть сильное подозрение, что 1-й будет неверен уже при сравнении с каким-нибудь рейзером, а второй и третий познаются в сравнении, так как и у файловых систем кэш есть, и у NoSQL СУБД фрагментация.


          1. MacIn
            16.09.2015 18:07
            #8575777

            NTFS использует то же B-Tree для индексирования имен файлов, емнип.


  1. Renius
    15.09.2015 15:13
    #8573399
    +3

    Блестяще! Спасибо!


  1. Karroplan
    15.09.2015 15:34
    #8573463
    +6

    Алгоритму с О(1) для этого потребуется 1 операция.
    ну вот это крайне неверно. O(1) может легко потребовать 10^6 операций, например. и поэтому при маленьких существуют случаи когда O(1) работает медленнее O(n^2)


    1. rvncerr
      15.09.2015 15:44
      #8573503
      +1

      Тут на самом деле у автора вряд ли стояла цель разобрать полностью всю «Big-Oh notation». Конечно, сравнение верно только начиная с некоторого n, но давайте представим, что тут вместо общего случая тут рассмотрен просто один из примеров, причем учебный, целью которого является лишь поверхностно коснуться «Big-Oh notation» без сильного погружения в математику.

      Для вводной статьи это ОК, кто захочет большего, тот найдет.
      ИМХО.


      1. Karroplan
        15.09.2015 22:04
        #8574319
        +3

        ну это понятно ) просто я за четкость формулировок. в этой фразе явная дезинформация, которая у кого-то может отложиться в памяти. Можно было сделать один абзац про O(1) и этого бы хватило


  1. ruRikki
    15.09.2015 15:34
    #8573471
    +2

    Не могу уйти не сказав спасибо, настолько хорошо написано, и вернусь еще не раз…
    PS гипнотизер перед «Или же просто можете дать ссылку на эту статью» так просто или помогает?


    1. Zlobober
      15.09.2015 15:45
      #8573505

      Он не перед «дать ссылку», а после «вместо того, чтобы плюнуть и уйти, вы можете ответить:»


      1. ruRikki
        15.09.2015 16:18
        #8573627
        +1

        В постскриптуме ИМХО. Мне понравилось… необычно… притягивает и почему то хочется порекомендовать еще кому-нибудь. Как будто усиливает позитив от и без этого хорошей статьи.


  1. SyCraft
    15.09.2015 15:47
    #8573519
    +2

    Отличный материал!


  1. Core2Duo
    15.09.2015 18:43
    #8573923
    +4

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


  1. Aquahawk
    15.09.2015 21:25
    #8574227

    Сегодня многие разработчики не особо задумываются о временн?й сложности алгоритмов… и они правы!

    нет. Мне больше нечего сказать.


    1. PaulBardack
      15.09.2015 23:32
      #8574473

      Это длительный спор, но правы как одни, так и другие.


      1. excoder
        16.09.2015 21:20
        #8576005
        +1

        Печально, что современному разработчику, пользующемуся, на минуточку, реляционной базой данных, вот так вот на пальцах приходится разъяснять про алгоритмическую сложность сортировки слиянием. Это почти что макака с гранатой, что и подтверждается практикой. Вроде бы и пользуются базой данных, да не очень. Выходит сплошной mongodb-is-web-scale.com.


    1. KvanTTT
      16.09.2015 00:31
      #8574525

      Зависит от задачи. Обывателю-разработчику действительно о ней задумываться не обязательно.


  1. PaulBardack
    15.09.2015 23:31
    #8574469
    +3

    Очень полезная статья. Компактно представлены тезисы, которые можно прочитать из 700-страничных книг по БД.
    Спасибо!


  1. Artiomtb
    18.09.2015 18:58
    #8579213

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


  1. armo
    19.09.2015 01:26
    #8579815

    Никого не смущает, что O(n^2) не похожа на параболу на графике?


    1. vintage
      19.09.2015 02:29
      #8579843
      +2

      Там же логарифмическая шкала.


      1. qw1
        20.09.2015 10:00
        #8580895

        на y = log(x2) = 2•log(x)
        тоже не похоже


        1. rvncerr
          20.09.2015 16:56
          #8581097
          +2

          Так по x шкала тоже логарифмическая. Это немного неожиданно для глаза. :)


          1. qw1
            20.09.2015 19:09
            #8581131

            Да, не заметил. В таких осях действительно интересно сравнивать сложность.


  1. Shablonarium
    24.09.2015 16:03
    #8589055
    +2

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


  1. antsiferov
    29.09.2015 16:54
    #8595343
    -1

    Привет! Здесь опечатка?
    Для каждой из N строк внешней зависимости нужно считать М строк внешней зависимости.