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

Недавно я вел в Европе углубленный курс по T-SQL, и один из учащихся, Николас Барро из компании Avanade France SAS, предложил небольшую интересную задачу. Она была не очень сложной, но любопытной, и надеюсь, вы тоже получите удовольствие, работая над ней.

Задача, предложенная Николасом, состоит в подготовке произвольной буквенной циклической, допускающей пропуски, последовательности со значениями в форме LLL, где L — буква латинского алфавита от A до Z (26 символов). Компания Николаса использует значение последовательности как флаг совпадения для сопоставления, например, между платежом и счетом-фактурой. Первое сформированное значение должно быть AAA, а последующие формируются так, как если бы буквы были цифрами с основанием 26:

AAA
AAB
…
AAY
AAZ
ABA
ABB
…
ZZY
ZZZ

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

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

CREATE OR ALTER PROC
  dbo.NextValForMySequence
  @val CHAR(3) OUTPUT
AS
<ваш программный код здесь>
GO

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

DECLARE @myval AS CHAR(3);
EXEC dbo.NextValForMySequence
  @val = @myval OUTPUT;
SELECT @myval;

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

Рисунок 1. Желаемые выходные данные

Хранение значения как строки символов и блокирование последовательности

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

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

Следующий ход был предложен Полом Уайтом. Обратите внимание на использование двоичной сортировки для столбца. Дело в том, что нам нужны только прописные буквы без акцентуации от A до Z. При использовании словарного порядка без учета регистра шаблон [A-Z] представляет следующие символы (упорядоченные), как показано на рисунке 2.

Рисунок 2. Шаблон [A-Z] без учета регистра

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

Рисунок 3. Шаблон [A-Z] с учетом регистра

Как мы видим, он просто исключает a и æ. При двоичной сортировке вы получаете только прописные буквы без акцентуации: ABCDEFGHIJKLMNOPQRSTUVWXYZ.

В листинге 2 приводятся запросы, использованные для определения совпадений в каждой сортировке.

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

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

В листинге 3 приводится полный программный код процедуры.

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

преобразуйте букву в значение в диапазоне от 0 до 25 с использованием выражения ASCII (<буква>) — 65 (65 является ascii-значением буквы A);
умножьте результат на 26 в степени отсчитываемой от нуля позиции символа справа налево.

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

(
(ASCII(SUBSTRING(@val, 1, 1)) - 65) *
26 * 26 +
(ASCII(SUBSTRING(@val, 2, 1)) - 65) * 26 +
(ASCII(SUBSTRING(@val, 3, 1)) - 65) + 1) %
17576;

Затем новое целочисленное значение преобразуется в строку символов с использованием инверсной логики:

    CHAR(65 + @intval / 26 / 26 % 26) +
    CHAR(65 + @intval / 26 % 26) +
    CHAR(65 + @intval % 26);

Оператор «/» выполняет целочисленное деление, а оператор «%» дает остаток от целочисленного деления.

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

Вы получите выходные данные, приведенные на рисунке 4.

Рисунок 4. Результат исполнения листинга 4

Чтобы протестировать производительность этой процедуры, выполните ее в цикле 1 000 000 раз (листинг 5).

На моем компьютере для выполнения этого кода потребовалось 96 секунд, то есть в среднем 96 микросекунд на один проход.

Хранение значения как целого числа и блокирование последовательности

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

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

val
——
ZZZ

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

Затем вы изменяете хранимую процедуру, чтобы выполнить простое прибавление целого числа, и переходите к следующему значению (листинг 7).

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

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

Вы получите выходные данные, показанные на рисунке 5.

Рисунок 5. Результаты исполнения листинга 9

Протестируйте его в цикле 1 000 000 раз (листинг 9).

На моем компьютере для выполнения этого кода потребовалось 35 секунд, то есть в среднем 35 микросекунд на один проход.

Поскольку инструкция UPDATE использует монопольную блокировку, которая действует до конца транзакции, в этом решении реализуется блокирование последовательности на уровне транзакции, гарантирующее отсутствие пропусков. Но напомню, что в нашем случае такого требования не было. Если пропуски допустимы, блокирование на уровне транзакций может привести к излишним потерям производительности при использовании длинных транзакций и получению значения последовательности на ранней стадии транзакции. Чтобы в этом убедиться, откройте два соединения (назовем их соединение 1 и соединение 2). Выполните следующий программный код для соединения 1, чтобы открыть явную транзакцию и запросить новое значение после SET NOCOUNT ON;

BEGIN TRAN;
DECLARE @myval AS CHAR(3);
EXEC dbo.NextValForMySequence
  @val = @myval OUTPUT;
SELECT @myval;

Сеанс получает монопольную блокировку для строки, чтобы применить обновление, и держит ее, пока транзакция открыта. Когда я запустил этот программный код, я получил значение последовательности ABB. Запомните полученное значение. Затем выполните следующий программный код для соединения 2, чтобы запросить новое значение:

SET NOCOUNT ON;
USE tempdb;
DECLARE @myval AS CHAR(3);
EXEC dbo.NextValForMySequence
  @val = @myval OUTPUT;
SELECT @myval;

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

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

ROLLBACK TRAN;

Обновление, примененное для соединения 1, отменяется (в моем случае возвращается значение ABA), и монопольная блокировка снимается. Соединение 2 теперь получает монопольную блокировку, которой оно ожидало, и переходит к значению последовательности ABB, первому, не использованному соединением 1.

Я выполнил тест производительности с помощью средства OStress, это часть пакета RML Utilities для SQL Server (https://www.microsoft.com/en-us/download/details.aspx?id=4511), имитируя несколько одновременных запросов для нового значения последовательности, выполненных в явной транзакции. Следующий программный код, выполненный из командной строки, тестирует 100 одновременных отдельных запросов:

OStress -S.\SQL2017 -dtempdb -Q"SET
   NOCOUNT ON; BEGIN TRAN;
   DECLARE @myval AS CHAR(3);
   EXEC dbo.NextValForMySequence
   @val = @myval OUTPUT; WAITFOR
   DELAY '00:00:00.100'; COMMIT TRAN"
   -n100 -r1

Каждый пакет T-SQL (параметр Q) открывает транзакцию, запрашивает новое значение последовательности, применяет задержку 100 миллисекунд, имитируя работу, которую необходимо совершить после того, как получено значение последовательности, и фиксирует транзакцию. Далее приводится описание параметров, используемых в этом примере: S — экземпляр SQL Server, с которым вы соединены; d — база данных; Q — пакет T-SQL; n — число потоков; r — число проходов на поток. Для того чтобы выполнить этот программный код на моем компьютере, потребовалось 10,479 секунды.

Следующий программный код тестирует 1000 одновременных запросов:

OStress -S.\SQL2017 -dtempdb -Q"SET
   NOCOUNT ON; BEGIN TRAN;
   DECLARE @myval AS CHAR(3);
   EXEC dbo.NextValForMySequence
   @val = @myval OUTPUT; WAITFOR
   DELAY '00:00:00.100'; COMMIT TRAN"
   -n1000 -r1

Для выполнения этого программного кода на моем компьютере потребовалось 104,311 секунды.

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

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

Чтобы исключить необязательные задержки вследствие блокирования на уровне транзакций, присутствующие в предыдущем решении, требуется неблокирующая последовательность. Этого можно достичь, применяя для хранения последний использованный объект последовательности (https://docs.microsoft.com/es-es/sql/t-sql/statements/create-sequence-transact-sql) вместо таблицы. Реализация объекта последовательности в SQL Server представляет неблокирующее, допускающее пропуски решение. Когда формируется запрос для нового значения последовательности с использованием NEXT VALUE FOR FUNCTION, SQL Server блокирует объект лишь на тот момент, пока не будет завершено изменение значения, но затем немедленно снимает блокировку, чтобы позволить другим запросить новые значения в соответствии с нашими нуждами, то есть в диапазоне от 0 до 17575, циклически (листинг 10).

Затем измените процедуру, чтобы запросить значение из объекта последовательности (листинг 11).

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

Вы получите выходные данные, приведенные на рисунке 6.

Рисунок 6. Результаты исполнения листинга 12

Используйте программный код листинга 13, чтобы организовать 1 000 000 повторений.

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

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

SET NOCOUNT ON;
BEGIN TRAN;
DECLARE @myval AS CHAR(3);
EXEC dbo.NextValForMySequence
  @val = @myval OUTPUT;
SELECT @myval;

Запомните полученное значение последовательности. У меня было ABB.

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

SET NOCOUNT ON;
DECLARE @myval AS CHAR(3);
EXEC dbo.NextValForMySequence
  @val = @myval OUTPUT;
SELECT @myval;

На этот раз запрос не блокируется, но вы немедленно получаете новое значение, в моем случае ABC.

Для соединения 1 выполните следующий программный код для отмены транзакции:

ROLLBACK TRAN;

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

Протестируйте 100 одновременных запросов с использованием явных транзакций, применив средство Ostress:

OStress -S.\SQL2017 -dtempdb -Q"SET
   NOCOUNT ON; BEGIN TRAN;
   DECLARE @myval AS CHAR(3);
   EXEC dbo.NextValForMySequence
   @val = @myval OUTPUT; WAITFOR
   DELAY '00:00:00.100'; COMMIT TRAN"
   -n100 -r1

Этот программный код был выполнен на моем компьютере за 1,125 секунды (в 10 раз быстрее, чем предыдущее решение).

Протестируйте 1000 одновременных запросов:

OStress -S.\SQL2017-dtempdb -Q"SET
   NOCOUNT ON; BEGIN TRAN;
   DECLARE @myval AS CHAR (3);
   EXEC dbo.NextValForMySequence
   @val = @myval OUTPUT; WAITFOR
   DELAY '00:00:00.100'; COMMIT TRAN"
   -n1000-r1

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

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

Листинг 1. Создание и начальное заполнение таблицы

SET NOCOUNT ON;
USE tempdb;
GO

DROP TABLE IF EXISTS dbo.MySequence;
GO
CREATE TABLE dbo.MySequence
(
  val CHAR(3) NOT NULL
    CONSTRAINT CHK_MySequence_val
      CHECK (val COLLATE Latin1_General_BIN
        LIKE '[A-Z][A-Z][A-Z]')
);

INSERT INTO dbo.MySequence(val) VALUES('ZZZ');

Листинг 2. Запросы, использованные для определения совпадений в каждой сортировке

SELECT STRING_AGG(CHAR(n), '')
  WITHIN GROUP (ORDER BY CHAR(n) COLLATE Latin1_General_CI_AS) AS dictionary_case_insensitive
FROM dbo.GetNums(0, 255)
WHERE CHAR(n) COLLATE Latin1_General_CI_AS LIKE '[A-Z]';

SELECT STRING_AGG(CHAR(n), '')
  WITHIN GROUP (ORDER BY CHAR(n) COLLATE Latin1_General_CS_AS) AS dictionary_case_sensitive
FROM dbo.GetNums(0, 255)
WHERE CHAR(n) COLLATE Latin1_General_CS_AS LIKE '[A-Z]';

SELECT STRING_AGG(CHAR(n), '')
  WITHIN GROUP (ORDER BY CHAR(n) COLLATE Latin1_General_BIN) AS binary_order
FROM dbo.GetNums(0, 255)
WHERE CHAR(n) COLLATE Latin1_General_BIN LIKE '[A-Z]';

Листинг 3. Полный код процедуры

CREATE OR ALTER PROC dbo.NextValForMySequence
  @val CHAR(3) OUTPUT
AS

SET NOCOUNT, XACT_ABORT ON;

BEGIN TRAN;

SET @val = (SELECT val FROM dbo.MySequence WITH (UPDLOCK));

DECLARE @intval AS INT =
  (
    (ASCII(SUBSTRING(@val, 1, 1)) - 65) * 26 * 26 +
    (ASCII(SUBSTRING(@val, 2, 1)) - 65) * 26 +
    (ASCII(SUBSTRING(@val, 3, 1)) - 65) + 1
  ) % 17576;

UPDATE dbo.MySequence
  SET @val = val =
    CHAR(65 + @intval / 26 / 26 % 26) +
    CHAR(65 + @intval / 26 % 26) +
    CHAR(65 + @intval % 26);

COMMIT TRAN;
GO

Листинг 4. Процедура преобразования строк в число

DECLARE @myval AS CHAR(3);

EXEC dbo.NextValForMySequence
  @val = @myval OUTPUT;

SELECT @myval;

Листинг 5. Тестирование производительности процедуры

SET NOCOUNT ON;

DECLARE @i AS INT = 1, @myval AS CHAR(3);
WHILE @i <= 1000000
BEGIN
  EXEC dbo.NextValForMySequence
    @val = @myval OUTPUT;
  SET @i += 1;
END;

Листинг 6. Другое определение таблицы MySequence

DROP TABLE IF EXISTS dbo.MySequence;
GO

CREATE TABLE dbo.MySequence
(
  intval INT NOT NULL
    CONSTRAINT CHK_MySequence_intval CHECK (intval BETWEEN 0 AND 17575),
  val AS
    CHAR(65 + intval / 26 / 26 % 26) +
    CHAR(65 + intval / 26 % 26) +
    CHAR(65 + intval % 26)
);
GO

INSERT INTO dbo.MySequence(intval) VALUES(17575);

SELECT val FROM dbo.MySequence;

Листинг 7. Измененная процедура с добавлением целого числа

CREATE OR ALTER PROC dbo.NextValForMySequence
  @val CHAR(3) OUTPUT
AS

SET NOCOUNT, XACT_ABORT ON;

DECLARE @intval AS INT;

UPDATE dbo.MySequence
  SET @intval = intval = (intval + 1) % 17576;

SET @val =
  CHAR(65 + @intval / 26 / 26 % 26) +
  CHAR(65 + @intval / 26 % 26) +
  CHAR(65 + @intval % 26);
GO

Листинг 8. Тестирование измененной процедуры

DECLARE @myval AS CHAR(3);

EXEC dbo.NextValForMySequence
  @val = @myval OUTPUT;

SELECT @myval;

Листинг 9. Тестирование производительности измененной процедуры

SET NOCOUNT ON;
DECLARE @i AS INT = 1, @myval AS CHAR(3);
WHILE @i <= 1000000
BEGIN
  EXEC dbo.NextValForMySequence
    @val = @myval OUTPUT;
  SET @i += 1;
END;

Листинг 10. Запрос с использованием NEXT VALUE FOR FUNCTION

DROP TABLE IF EXISTS dbo.MySequence;
GO
DROP SEQUENCE IF EXISTS dbo.MySequence;
GO

CREATE SEQUENCE dbo.MySequence AS INT
  MINVALUE 0
  MAXVALUE 17575
  CYCLE;

Листинг 11. Запрос значения из объекта последовательности

CREATE OR ALTER PROC dbo.NextValForMySequence
  @val CHAR(3) OUTPUT
AS

SET NOCOUNT, XACT_ABORT ON;

DECLARE @intval AS INT = NEXT VALUE FOR dbo.MySequence;

SET @val =
  CHAR(65 + @intval / 26 / 26 % 26) +
  CHAR(65 + @intval / 26 % 26) +
  CHAR(65 + @intval % 26);
GO

Листинг 12. Тестирование процедуры для неблокирующей целочисленной последовательности

DECLARE @myval AS CHAR(3);
EXEC dbo.NextValForMySequence
  @val = @myval OUTPUT;

SELECT @myval;

Листинг 13. Тестирование производительности процедуры для неблокирующей целочисленной последовательности
SET NOCOUNT ON;

DECLARE @i AS INT = 1, @myval AS CHAR(3);
WHILE @i <= 1000000
BEGIN
  EXEC dbo.NextValForMySequence
    @val = @myval OUTPUT;
  SET @i += 1;
END;