Рубрики
Без рубрики

Про суррогатные ключи

Если выполнить SQL-запрос:

  1. SELECT id FROM <таблица>

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

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

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

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

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

На этом этапе многие могут возразить, утверждая, что использование «естественного» составного первичного ключа и передача его из родительской таблицы в дочернюю является плохой идеей. Это разумное замечание. Я сам являюсь не только теоретиком, а также практиком, и поэтому в таких ситуациях рекомендую использовать суррогатный ключ с обязательным наложением ограничения уникальности на потенциальный ключ. Таким образом, мы одновременно защищаемся от появления семантически идентичных строк в таблице и получаем возможность передавать в процедуры, запросы и дочерние таблицы короткое целочисленное значение. Кроме того, стоит помнить, что чем короче ключ, тем более эффективно работают ограничения FOREIGN KEY и операции соединения, а также требуется меньше места для хранения ключа в связанных таблицах.

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

Рубрики
Без рубрики

Про разные варианты одного запроса

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

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

Нам предстоит работать с таблицей person из примерно 300 тысяч строк следующего вида:

idfirst_namemiddle_namelast_namemother_idfather_id
Уникальный идентификатор человекаИмяОтчествоФамилияСсылка на id матери в этой же таблице (person)Ссылка на id отца в этой же таблице (person)

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

idfirst_namemiddle_namelast_namechild_cnt
Уникальный идентификатор человекаИмяОтчествоФамилияКоличество детей у указанного человека

Самый тривиальный вариант, который обычно пишут новички в SQL содержит подзапрос в списке столбцов:

  1. SELECT p.id,
  2.        p.last_name,
  3.        p.first_name,
  4.        p.middle_name,
  5.        (
  6.            SELECT COUNT(*) AS child_cnt
  7.            FROM dbo.person pp
  8.            WHERE pp.father_id = p.id
  9.                  OR pp.mother_id = p.id
  10.        ) AS child_cnt
  11. FROM dbo.person p
  12. ORDER BY p.id;

Надеюсь, вы понимаете в чём проблема этого запроса. Для каждой(!) строки результирующей выборки (а их 300 тысяч) будет выполнен подзапрос с подсчётом количества детей. Суммарная стоимость этого варианта составляет 178230. Что касается времени выполнения, то я так и не дождался результата, поэтому условно будем считать час (на самом деле намного больше).

Казалось бы очевидным улучшением является подсчёт количества детей с помощью соединения таблицы с собой:

  1. SELECT p.id,
  2.        COUNT(p2.father_id)+COUNT(p2.mother_id) AS child_cnt
  3. FROM dbo.person p
  4.     LEFT JOIN dbo.person p2
  5.         ON p2.father_id = p.id
  6.            OR p2.mother_id = p.id
  7. GROUP BY p.id;

Но оптимизатор так не считает. Оценка этого варианта 455435, а в плане виден ненавистный спулинг.

Тем не менее если мы заменим left join на inner join, мы получим список только тех людей, у кого есть хотя бы один ребёнок, но зато с оценкой в ~64.

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

  1. SELECT p.id,
  2.        p.last_name,
  3.        p.first_name,
  4.        p.middle_name,
  5.        COALESCE(r.child_cnt, 0) AS child_cnt
  6. FROM dbo.person p
  7.     LEFT JOIN
  8.     (
  9.         SELECT p.id,
  10.                COUNT(*) AS child_cnt
  11.         FROM dbo.person p
  12.             INNER JOIN dbo.person p2
  13.                 ON p2.father_id = p.id
  14.                    OR p2.mother_id = p.id
  15.         GROUP BY p.id
  16.     ) r
  17.         ON p.id = r.id;

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

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

  1. SELECT p.id,
  2.        COUNT(*) AS child_cnt
  3. FROM dbo.person p
  4.     INNER JOIN dbo.person p2
  5.         ON p2.father_id = p.id
  6. GROUP BY p.id
  7. UNION ALL
  8. SELECT p.id,
  9.        COUNT(*) AS child_cnt
  10. FROM dbo.person p
  11.     INNER JOIN dbo.person p2
  12.         ON p2.mother_id = p.id
  13. GROUP BY p.id;

В этом варианте запроса с оценкой ~15, мы избавляемся от сложного оператора OR в join. Вместо этого мы подсчитываем у скольких людей конкретная персона является отцом, аналогично считаем у скольких людей она является матерью, а результаты просто объединяем.

Но на самом деле можно поступить ещё проще. Нам нет необходимости проверять каждую персону на наличие детей. Мы можем просто посчитать сколько раз каждый человек появлялся в столбцах mother_id / father_id и таким образом получить искомое количество детей.

  1. SELECT r.parent_id,
  2.        COUNT(*) AS child_cnt
  3. FROM
  4. (
  5.     SELECT mother_id AS parent_id
  6.     FROM dbo.person
  7.     WHERE (1 = 1)
  8.           AND (mother_id IS NOT NULL)
  9.     UNION ALL
  10.     SELECT father_id
  11.     FROM dbo.person
  12.     WHERE (1 = 1)
  13.           AND (father_id IS NOT NULL)
  14. ) r
  15. GROUP BY r.parent_id;

С оценкой ~5 мы считаем требуемые данные всего за одну секунду.

Разумеется, как я сказал ещё в самом начале, гораздо проще было бы ускорить этот запрос, просто добавив индекс. Но разве не здорово просто переформулировав то, что ты хочешь получить от сервера, добиться ускорения в сотни раз?

Уже после публикации этой записи мне пришла в голову ещё одна идея. Очевидно, что использование OR в подзапросе существенно замедляет его. Что если оставить подзапрос в SELECT, но при этом разбить его на две части?

  1. SELECT p.id,
  2.        p.last_name,
  3.        p.first_name,
  4.        p.middle_name,
  5.        (
  6.            SELECT COUNT(*) AS child_cnt
  7.            FROM dbo.person pp
  8.            WHERE pp.father_id = p.id
  9.        ) +
  10.        (
  11.            SELECT COUNT(*) AS child_cnt
  12.            FROM dbo.person pp
  13.            WHERE pp.mother_id = p.id
  14.        ) AS child_cnt
  15. FROM dbo.person p
  16. ORDER BY p.id;

Мы видим, что при таком запросе оптимизатор догадался сначала сгруппировать данные по матерям и отцам, а потом собрать итоговую таблицу используя быстрый MERGE JOIN.

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

Рубрики
Без рубрики

hash join и операторы сравнения

Долгое время я был уверен, что особенностью hash join является тот факт, что он работает только с условиями строгого равенства в соединениях. Это довольно логично, если вспомнить, как работают hash-функции.

Основная идея заключается в том, что можно отобразить множество значений из таблицы в менее мощное множество. Например, вместо того, чтобы сравнивать два целых числа (они могут быть в диапазоне от -2 147 483 648 до 2 147 483 647), мы можем сравнить остатки от их деления на 17 (весь диапазон значений лежит от 0 до 16). Если остатки от деления не совпадают, то мы можем уверенно сказать, что и сами числа не совпадут. Если же остатки совпали, то надо в явном виде проверить сами числа, чтобы избежать ошибок из-за коллизий. Выигрыш здесь получается за счёт того, что процент совпадений хороших hash-функций обычно мал, и мы можем сразу отсекать большие объёмы данных. Явным недостатком предложенного метода является то, что для из того, что a>b не следует, что hash(a)>hash(b). Например 18>5, но 18 mod 17 = 1 < 5 mod 17 = 5. Таким образом получается, что hash может использоваться только тогда, когда в условии соединения строгое равенство.

Я и многие мои знакомые думали, что это верно всегда, т.е. даже в составном условии соединения все условия должны быть равенствами, а на практике оказалось, что hash join может использоваться если в условии соединения есть хотя бы одно равенство. В качестве примера создадим две таблички (t1 и t2) и заполним их записями по следующему шаблону:

CREATE TABLE t1
(
    id INT IDENTITY(1, 1),
    val CHAR(36)
);
GO

DECLARE @Counter INT = 1;
WHILE (@Counter <= 100000)
BEGIN
    INSERT dbo.t2
    (
        val
    )
    VALUES
    (NEWID());
    SET @Counter = @Counter + 1;
END;

Ещё пару дней назад я бы сказал, что в запросе точно будет использоваться Nested Loops, но сервер оказался хитрее

SELECT t1.id,
       t1.val,
       t2.id,
       t2.val
FROM dbo.t1 t1
    INNER JOIN dbo.t2 t2
        ON (t2.id = t1.id)
           AND (t1.val > t2.val);

Если у вас возник вопрос, как тут можно использовать hash join, то хитрость вот в чём: по hash-функции сравнивается только поле id (Hash Keys Probe), при несовпадении хешей строка сразу отбрасывается, а при совпадении происходит полное сравнение и id, и val (Probe Residual).

Рубрики
Без рубрики

Оптимальная тактика для WORDLE

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

Я в своё время написал скрипт, который перебрал тройки пятибуквенных слов и нашёл трио слов, которое открывает 15 самых частоиспользуемых букв.

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

Рубрики
Без рубрики

ASSERT

Оператор ASSERT используется для проверки определённых условий. Это оператор будет выполняться для каждой строки из набора данных.

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

DROP TABLE IF EXISTS traffic_light;
CREATE TABLE traffic_light
(
    id INT IDENTITY(1, 1),
    color CHAR(1),
    CONSTRAINT CHECK_COLOR CHECK (color IN ( 'G', 'R' ))
);
INSERT INTO dbo.traffic_light (color) VALUES ('Y');

В этой таблице мы разрешаем цвету условного светофора быть или зелёным, или красным. При вставке данных в эту таблицу SQL Server генерирует следующий план:

Если разобраться с тем, что именно проверяет ASSERT, то мы увидим, что он возвращает 0, если в столбец color передаётся значение отличное от G или R и NULL в противном случае. Ошибка будет сгенерирована, есть ASSERT вернёт значение отличное от NULL.

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

DROP TABLE IF EXISTS possible_light;
CREATE TABLE possible_light
(
    color CHAR(1) PRIMARY KEY
);
INSERT INTO dbo.possible_light (color) VALUES ('R'),('Y'),('G');
ALTER TABLE dbo.traffic_light
ADD CONSTRAINT fk_light
    FOREIGN KEY (color)
    REFERENCES dbo.possible_light (color);

Теперь при вставке данных в первую таблицу план усложнится:

Если идти справа налево, то первый ASSERT как и раньше проверит CHECK ограничение, а второй ASSERT проверит корректность связи по ключам.

В предикате второго оператора ASSERT мы видим непонятное условие Expr1007, но всё станет на свои места, если отобразить план запроса в виде текста:

  |--Assert(WHERE:(CASE WHEN NOT [Pass1008] AND [Expr1007] IS NULL THEN (0) ELSE NULL END))
       |--Nested Loops(Left Semi Join, PASSTHRU:([lessons].[dbo].[traffic_light].[color] IS NULL), OUTER REFERENCES:([lessons].[dbo].[traffic_light].[color]), DEFINE:([Expr1007] = [PROBE VALUE]))
            |--Assert(WHERE:(CASE WHEN [lessons].[dbo].[traffic_light].[color]<>'R' AND [lessons].[dbo].[traffic_light].[color]<>'G' THEN (0) ELSE NULL END))
            |    |--Table Insert(OBJECT:([lessons].[dbo].[traffic_light]), SET:([lessons].[dbo].[traffic_light].[color] = [Expr1004],[lessons].[dbo].[traffic_light].[id] = [Expr1003]))
            |         |--Compute Scalar(DEFINE:([Expr1004]=CONVERT_IMPLICIT(char(1),[@1],0)))
            |              |--Compute Scalar(DEFINE:([Expr1003]=getidentity((1525580473),(6),NULL)))
            |                   |--Constant Scan
            |--Clustered Index Seek(OBJECT:([lessons].[dbo].[possible_light].[PK__possible__900DC6E8209DDE1B]), SEEK:([lessons].[dbo].[possible_light].[color]=[lessons].[dbo].[traffic_light].[color]) ORDERED FORWARD)

По строке DEFINE:([Expr1007] = [PROBE VALUE]) становится понятно, что это выражение — просто результат объединения таблиц. Этим выражением ASSERT проверяет, что вставляемое значение действительно есть в таблице possible_light.

Наконец, рассмотрим ещё один случай, где оператор ASSERT может встречаться в реальной работе. Речь идёт о подзапросах. Во многих ситуациях встречается «скалярный» подзапрос. Т.е. такой подзапрос, который возвращает строго одно значение. В качестве тестового запроса рассмотрим следующий код:

SELECT * FROM dbo.traffic_light tl
WHERE (tl.color>
(SELECT pl.color FROM dbo.possible_light pl WHERE (1=1)and(pl.color>'A'))
)

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

Самый интересный блок тут это часть где данные из possible_light агрегируются, чтобы подсчитать количество строк, а потом полученное значение передаётся в ASSERT. Думаю, вы уже сами догадались, что Expr1004 это результат агрегации

Stream Aggregate(DEFINE:([Expr1004]=Count(*)...

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

Рубрики
Без рубрики

Нахождение последней записи

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

IDPhoneSMSType
Уникальный монотонно возрастающий идентификатор SMS.Номер телефона на который отправлено сообщениеТип сообщения

Первое решение, которое пришло мне в голову — использовать cross apply, чтобы для каждого уникального номера телефона подзапросом найти соответствующий тип:

;WITH [cte] 
     AS (SELECT [S].[phone] 
         FROM   [dbo].[smslog] AS [S] 
         GROUP  BY [S].[phone]) 
SELECT [ca].[id], 
       [cte].[phone], 
       [ca].[smstype] 
FROM   [cte] 
       CROSS apply (SELECT TOP 1 [ca_s].[id], 
                                 [ca_s].[smstype] 
                    FROM   [dbo].[smslog] AS [ca_s] 
                    WHERE  ( 1 = 1 ) 
                           AND ( [ca_s].[phone] = [cte].[phone] ) 
                    ORDER  BY [ca_s].[id] DESC) AS [ca] 

Довольно очевидным шагом является избавление от CROSS APPLY и замена его на JOIN:

;WITH [cte] 
     AS (SELECT [S].[phone], 
                Max ([S].[id]) AS ‘maxID’ 
         FROM   [dbo].[smslog] AS [S] 
         GROUP  BY [S].[phone]) 
SELECT [S].[id], 
       [S].[phone], 
       [S].[smstype], 
       [cte].[phone], 
       [cte].[maxid] 
FROM   [dbo].[smslog] AS [S] 
       INNER JOIN [cte] 
               ON ( 1 = 1 ) 
                  AND ( [S].[id] = [cte].[maxid] ) 

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

;WITH [cte] 
     AS (SELECT [S].[id], 
                [S].[phone], 
                [S].[smstype], 
                Row_number () 
                  OVER ( 
                    partition BY [S].[phone] 
                    ORDER BY [S].[id] DESC ) AS ‘rn’ 
         FROM   [dbo].[smslog] AS [S]) 
SELECT [cte].[id], 
       [cte].[phone], 
       [cte].[smstype] 
FROM   [cte] 
WHERE  ( 1 = 1 ) 
       AND ( [cte].[rn] = 1 ) 

Все представленные выше планы запросов получены, когда на таблице нет никаких индексов, но важно понимать, что их добавление может значительно изменить план. Например, после добавления некластеризованного индекса по полям (Phone;ID) и включённым полем smstype в третьем запросе вообще исчезает этап сортировки, а время тратится практически исключительно на просмотр индекса.

Рубрики
Без рубрики

О важности первичных ключей

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