(495) 925-0049, ITShop интернет-магазин 229-0436, Учебный Центр 925-0049
  Главная страница Карта сайта Контакты
Поиск
Вход
Регистрация
Рассылки сайта
 
 
 
 
 

КВАйны уходят в отрыв

Источник: habrahabr


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

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

Ссылки по теме


 Распечатать »
 Правила публикации »
  Написать редактору 
 Рекомендовать » Дата публикации: 15.08.2013 
 

Магазин программного обеспечения   WWW.ITSHOP.RU
Microsoft 365 Business Standard (corporate)
Microsoft Office 365 Персональный 32-bit/x64. 1 ПК/MAC + 1 Планшет + 1 Телефон. Все языки. Подписка на 1 год.
Microsoft Windows Professional 10, Электронный ключ
Microsoft Office для дома и учебы 2019 (лицензия ESD)
Microsoft Office 365 для Дома 32-bit/x64. 5 ПК/Mac + 5 Планшетов + 5 Телефонов. Подписка на 1 год.
 
Другие предложения...
 
Курсы обучения   WWW.ITSHOP.RU
 
Другие предложения...
 
Магазин сертификационных экзаменов   WWW.ITSHOP.RU
 
Другие предложения...
 
3D Принтеры | 3D Печать   WWW.ITSHOP.RU
 
Другие предложения...
 
Новости по теме
 
Рассылки Subscribe.ru
Информационные технологии: CASE, RAD, ERP, OLAP
Безопасность компьютерных сетей и защита информации
Новости ITShop.ru - ПО, книги, документация, курсы обучения
Программирование на Microsoft Access
CASE-технологии
Мастерская программиста
Проект mic-hard - все об XP - новости, статьи, советы
 
Статьи по теме
 
Новинки каталога Download
 
Исходники
 
Документация
 
 



    
rambler's top100 Rambler's Top100