Пост про короля квайнов напомнил мне, что я уже давно хотел обсудить с общественностью вопросы их (квайнов) практического применения. В самом деле, обидно, что такая красивая с точки зрения программирования вещь на деле никому и не нужна. Музыку им не поиграть, страницу не сверстать, данные не загрузить…
Когда деревья были большими, а 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. Осторожно, он создает таблицу на пол-гигабайта. Можно уменьшить количество создаваемых записей перед запуском, если жалко ресурсов.