Пост про короля квайнов напомнил мне, что я уже давно хотел обсудить с общественностью вопросы их (квайнов) практического применения. В самом деле, обидно, что такая красивая с точки зрения программирования вещь на деле никому и не нужна. Музыку им не поиграть, страницу не сверстать, данные не загрузить…
Когда деревья были большими, а MS SQL Server 2000 актуальным, возникла у меня проблема ускорения одного запроса на вполне даже работающем проекте. Проблема была в том, чтобы по возможности быстро загрузить данные из древовидной структуры в базе. Примерно вот такой:
CREATE TABLE folders (
id INT PRIMARY KEY,
parent_id INT FOREIGN KEY REFERENCES folders (id),
heavy_data CHAR(500)
)
Конечно, как обычно бывает в жизни, таблиц было несколько, полей было больше, хранились там другие вещи, но сути это не меняет. Стояла задача, допустим, найти все подкаталоги с id кратным 1000 внутри определенного родителя. На самом деле, конечно, задача была другая, со множеством условий и вариаций, но очень похожая по способу решения и результату.
Как мне кажется, самый очевидный путь здесь – сложить во временную таблицу родительский каталог и его уровень. А потом «джойнить» и вставлять туда же исходную таблицу, добавляя условие, что уровень у родителя добавляемых записей должен быть последним. Сложно объяснить на словах, а в коде очень просто:
-- начинаем с родительского каталога
SELECT 0 level,* INTO #tmp FROM folders WHERE id = 3
-- и грузим все дочерние каталоги
DECLARE @level int = 0
WHILE @@ROWCOUNT > 0
BEGIN
SET @level = @level + 1
INSERT INTO #tmp
SELECT @level, child.* FROM #tmp parent
INNER JOIN folders child
ON child.parent_id = parent.id AND parent.level = @level - 1
END
SELECT * FROM #tmp WHERE id % 1000 = 0
Вроде бы, неплохо. Просто и достаточно эффективно. Но хотелось бы быстрее.
Можно заметить, что во временной таблице постепенно накапливается «мусор» с предыдущих уровней. В «джойне» он ничего не добавляет, но все равно проверяется. Мы бы могли на каждом уровне складывать найденный записи в другую таблицу, а мусор выкидывать. Кстати, найдено будет куда меньше записей, чем выкинуто, так как мы берем только каждую тысячную.
Давайте организуем ротацию двух временных таблиц #odd и #even таким образом, чтобы, например, на четных уровнях «переливать» данные из #even в #odd, а на нечетных – обратно. В SQL Server 2000 выражения типа SELECT INTO работают быстрее, чем равноценные INSERT INTO. Так что будем просто удалять таблицу назначения перед «переливанием».
-- результат вначале пустой
SELECT * INTO #result1 FROM folders WHERE 1=2
-- а каталог случайный
SELECT * INTO #odd FROM folders WHERE id = 3
-- начинаем с нечетных. Почему нет?
DECLARE @odd bit = 1
-- грузим все дочерние каталоги
WHILE @@ROWCOUNT > 0
BEGIN
IF @odd = 1
BEGIN
SET @odd = 0
INSERT INTO #result1
SELECT * FROM #odd WHERE id % 1000 = 0
DROP TABLE #even
SELECT child.* INTO #even FROM #odd parent
INNER JOIN folders child
ON child.parent_id = parent.id
END
ELSE
BEGIN
SET @odd = 1
INSERT INTO #result1
SELECT * FROM #even WHERE id % 1000 = 0
DROP TABLE #odd
SELECT child.* INTO #odd FROM #even parent
INNER JOIN folders child
ON child.parent_id = parent.id
END
END
И тут в планы вмешивается глупый компилятор запросов, который не позволяет два раза создавать таблицу #odd, несмотря на то, что мы ее сначала честно убиваем. Можно бы было попытаться, использовать рекурсию. Но в MSSQL 2000 это не так-то просто: CTE нет, и использовать хранимые процедуры не получится (не спрашивайте, не помню точно почему, но тогда я это проверял).
Можно попробовать просто очищать таблицы, не удаляя их:
…
TRUNCATE TABLE #odd
INSERT INTO #odd
SELECT child.* FROM #even parent
…
но это медленнее, и никакого выигрыша не получается.
Попробуем не чередовать временные таблицы, а использовать #tmp0 -> #tmp1 -> #tmp2, и так далее. Глубина вложенности неизвестна заранее (хотя и не очень велика). Используем EVAL и будем подставлять нужные циферки. Опять проблема: результат из EVAL так просто не вытащить, его временные таблицы снаружи недоступны.
Ну так мы пойдем внутрь! Будем вызывать EVAL рекурсивно.
SELECT * INTO #result FROM folders WHERE 1=2
SELECT * INTO #tmp0 FROM folders WHERE id = 3
-------------------------------------------------------------------
-- Повторяем следующие запросы пока @@ROWCOUNT > 0:
-- INSERT INTO #result
-- SELECT * FROM #tmpX WHERE id % 1000 = 0
--
-- SELECT * INTO #tmpY FROM #tmpX parent
-- INNER JOIN folders child
-- ON parent.id = child.parent_id
--
-- где Y = X + 1
--------------------------------------------------------------------
DECLARE @query varchar (4000) = '
PRINT !
DECLARE @query varchar (4000) = $
DECLARE @new_query varchar (4000) = $
SET @query = REPLACE (@query, CHAR(33), ! + 1)
SET @query = REPLACE (@query, CHAR(38), & + 1)
SET @query = REPLACE (@query, CHAR(36), CHAR(39) + @new_query + CHAR(39))
INSERT INTO #result
SELECT * FROM #tmp! WHERE id % 1000 = 0
SELECT child.* INTO #tmp& FROM #tmp! parent
INNER JOIN folders child
ON parent.id = child.parent_id
if @@ROWCOUNT > 0
EXEC (@query)
'
DECLARE @new_query varchar (4000) = @query
SET @query = REPLACE (@query, CHAR(33), 0) -- ! >> родительская таблица
SET @query = REPLACE (@query, CHAR(38), 1) -- & >> дочерняя таблица
SET @query = REPLACE (@query, CHAR(36), CHAR(39) + @new_query + CHAR(39)) -- $ >> '@new_query'
EXEC (@query)
Ой, что же это получилось? Получился квайн. Ну, почти. Только циферки каждый раз отличаются, но, по-моему, это придирки. Лучше посмотрим на результаты:
По-простому: 6926 ms
По-продвинутому: 5286 ms
По-квайновски: 4850 ms
А результаты такие, что отрыв не очень впечатляет. В некоторых запусках получается даже медленнее. Но это я пишу сейчас, и проверяю на MSSQL 2012. А вот на 2000 версии все было иначе, и отрыв был в два-четыре раза (в зависимости от данных). И поэтому какое-то время такой код был оправдан. Он жил в продакшне, разрастался новыми параметрами, окружался новой логикой, и в конце концов стал выглядеть этакой трясиной, соваться в которую уже совершенно не хотелось. К тому же, поддерживать совместимость с двухтысячной версией MSSQL стало больше не нужно, и все карты были за то, чтобы этот кусок переписать.
Но ведь это же квайн! Причем, бывший полезным. Это же мимими! Вот вы бы убили квайн?
Я убил. Но до сих пор не понимаю, надо ли гордиться тем что он был или стыдиться этого.
PS. Может быть, можно было решить эту проблему эффективнее и без подобных извращений. Но тогда не только трава была зеленее, и ничего другого я не придумал.
Полный код примера смотреть здесь: https://bitbucket.org/azubr/habr-quine/src. Осторожно, он создает таблицу на пол-гигабайта. Можно уменьшить количество создаваемых записей перед запуском, если жалко ресурсов.
Автор: Zubr
