Хранение древовидных структур в SQL Server - подход БЕЗ рекурсии

Sanja v.2 07.01.2005 05:06 / 07.01.2005 05:10

Есть у меня форум, написанный на парсере с mysql - сейчас в нём 34 тыс. реплик суммарным весом где-то 26 мегабайт. Для хранения и вывода реплик выводится метод, аналогичный описанному здесь в Примерах, активно сдобренный ^cache[]

Проблема в том, что на больших ветках и в моменты прихода GoogleBot форум начинает безбожно тормозить (всё не закешируешь). Из за этого, а также из-за необходимости мигрировать на SQL Server было решено это всё переписать.

Список предпосылок:

- лучше медленный insert, чем медленный select
- поддерживать целостность древовидной структуры должен SQL server, а не кусок кода на parser (который может быть прерван на середине, кстати)
- формирование дерева для вывода должен осуществлять SQL Server, а не Parser
- в идеале всё дерево должно доставаться банальным SELECT'ом
- в ходе этого SELECT'а БД не должна ничего LEFT JOIN'ить, активно довычислять и т.п. - максимум сортировать

Я перепробовал кучу подходов - ближе всего казалась Nested sets model, но для неё требуется перенумеровывать все записи в таблице при каждом insert'е, что неприемлемо. В итоге я остановился на подходе, когда в базе хранится:

- номер реплики (cid)
- номер реплики-родителя (pid - "parent's ID")
- глубина вложенности реплики (lvl) - у корневой реплики она равна нулю, у ответов на неё - уже единице, у ответов на ответы - двойке и т.п.
- путь к реплике в дереве (hierarchy)

На последнем остановимся поподробнее. Эта штука в англоязычной литературе по теме называется path enumeration и выглядит так, например: "0.1.3.25.143"

Реплика с таким значением hierarchy имеет номер 123, она была добавлена в ответ на реплику 25, а та, в свою очередь, в ответ на реплику 3. Как видите, это очень похоже на имена файлов в файловой системе.

Схема, как видите, избыточная. Номер реплики дублируется и в cid, и в hierarchy, номер родителя (pid) тоже. lvl также вычислябелен из hierarchy - нужно только точки посчитать в hierarchy. Храним мы их отдельно для того, чтобы упростить запросы и ускорить за счёт индексов по ним.

Для совместимости со старым кодом я сделал ещё и столбец tid (thread's ID - общий для всей ветки номер) - также избыточный.

А теперь барабанная дробь и туш: мы выводим дерево всех реплик форума одним select'ом:

SELECT replicate('      ', lvl) + subject AS 
	zagolovok_s_otstupom, author, lvl, cid,
	FROM forum_forumdata
	where lvl > 0
	ORDER BY hierarchy ASC

SQL Server наприсует нужное количество пробелов слева от каждой реплики, чтобы получилось симпатичное дерево.

На моём ноутбуке этот запрос выполняется пять секунд (напомню, в форуме 34 тысячи реплик суммарным весом 26 мегабайт) - при этом в фоне работает Media Player и ещё много чего.

Такое хранение позволяет отвечать на самые заковыристые вопросы, на которые в adjacency model, реализованной Мишей, не ответишь одним select'ом.

Цена всего этого - необходимость посчитать lvl, tid и hierachy при добавлении реплики в форум. Но поскольку форум в день читают несколько сотен человек, а реплики пишут максимум десяток, подход "медленный insert - быстрый select" очень даже оправдан.

Поскольку вместо простецкого MySQL используется SQL Server, все эти вычисления можно переложить на БД, пользуясь для этого триггерами. Для удаления ветки с ответами, переноса её в другую ветку и т.п. создаются stored procedures - то есть никаких манипуляций с деревом средствами парсера не производится.

Вот в итоге структура базы. Жду ваших комментариев, критики и указания на вопиющие ошибки:

-- ------------------------------

IF EXISTS (SELECT * FROM dbo.sysobjects WHERE id = object_id(N'[dbo].FK_pidcid') 
AND OBJECTPROPERTY(id, N'IsForeignKey') = 1) ALTER TABLE [dbo].[forum_forumdata] 
DROP CONSTRAINT FK_pidcid
GO

IF EXISTS (SELECT * FROM dbo.sysobjects WHERE id = object_id(N'dbo.forum_forumdata') 
AND OBJECTPROPERTY(id, N'IsUserTable') = 1) DROP TABLE dbo.forum_forumdata
GO

CREATE TABLE dbo.forum_forumdata
(
-- автнумерация пойдёт с 40K-й реплики (33K уже есть)
-- Десятизначной нумерации реплик для этого форума хватит
-- лет на пятьдесят
cid         INT IDENTITY(40000,1) NOT NULL  CHECK ( cid <= 9999999999 ),
pid         INT                             CHECK ( pid <= 9999999999 ),
tid         INT                             CHECK ( tid <= 9999999999 ),
lvl         INT                             CHECK ( lvl <= 199 ),
-- высота дерева ограничена 199 уровнями вложенности - на порядок больше 
-- необходимого. Если надо, можно увеличить
hierarchy   VARCHAR(2000)                   CHECK ( LEN(hierarchy) <= 1990 ),
subject     VARCHAR(255) NOT NULL,
author      VARCHAR(255) NOT NULL,
email       VARCHAR(255) NOT NULL,
cookie      VARCHAR(255) NOT NULL,
postdate    DATETIME NOT NULL,
ipaddr      VARCHAR(100),
subscribe   CHAR(3) DEFAULT ('no') NOT NULL,
message     TEXT,
CONSTRAINT  PK_cid PRIMARY KEY CLUSTERED ( cid )
)
GO

ALTER TABLE dbo.forum_forumdata
    ADD CONSTRAINT FK_pidcid FOREIGN KEY( pid )
    REFERENCES [dbo].[forum_forumdata] ( cid )
    ON UPDATE NO ACTION
    ON DELETE NO ACTION;
GO

-- К сожалению, в SQL Server у таблицы может быть 
-- только один clustered index - будь это не так, 
-- следующие два индекса я бы тоже сделал clustered:

CREATE NONCLUSTERED INDEX idx_tid          ON dbo.forum_forumdata (tid)
GO

CREATE NONCLUSTERED INDEX idx_hierarchy    ON dbo.forum_forumdata (hierarchy)
GO

CREATE NONCLUSTERED INDEX idx_pid          ON dbo.forum_forumdata (pid)
GO

CREATE NONCLUSTERED INDEX idx_lvl          ON dbo.forum_forumdata (lvl)
GO

CREATE NONCLUSTERED INDEX idx_author       ON dbo.forum_forumdata (author)
GO

CREATE NONCLUSTERED INDEX idx_cookie       ON dbo.forum_forumdata (cookie)
GO

CREATE NONCLUSTERED INDEX idx_ipaddr       ON dbo.forum_forumdata (ipaddr)
GO

IF EXISTS (SELECT * FROM dbo.sysobjects where id = object_id(N'dbo.RemoveItemMoveSubs') 
and OBJECTPROPERTY(id, N'IsProcedure') = 1) drop procedure dbo.RemoveItemMoveSubs
GO

-- удаляет реплику, передаёт детей новому родителю
CREATE PROC RemoveItemMoveSubs
	@cid int,
	@newparent int
AS
	UPDATE CHILD
	SET pid = @newparent
	FROM forum_forumdata AS CHILD JOIN forum_forumdata AS PARENT
		ON CHILD.pid = PARENT.cid
	WHERE PARENT.cid = @cid
	DELETE FROM forum_forumdata
	WHERE cid = @cid
GO

IF EXISTS (SELECT * FROM dbo.sysobjects where id = 
object_id(N'dbo.RemoveItemUpgradeSubs') AND OBJECTPROPERTY(id, N'IsProcedure') = 1) 
DROP PROCEDURE dbo.RemoveItemUpgradeSubs
GO

-- Удаляет реплику и усыновляет "внуков"
CREATE PROC RemoveItemUpgradeSubs
	@cid int
AS
	UPDATE CHILD
	SET pid = PARENT.pid
	FROM forum_forumdata AS CHILD JOIN forum_forumdata AS PARENT
		ON CHILD.pid = PARENT.cid
	WHERE PARENT.cid = @cid
	DELETE FROM forum_forumdata WHERE cid = @cid
GO

IF EXISTS (SELECT * FROM dbo.sysobjects where id = 
object_id(N'dbo.RemoveSubtree') and OBJECTPROPERTY(id, N'IsProcedure') = 1) 
DROP PROCEDURE dbo.RemoveSubtree
GO

-- Удалzет реплику со всеми детишками:
CREATE PROC RemoveSubtree
	@cid int
AS
	DELETE FROM forum_forumdata
	WHERE hierarchy LIKE (SELECT hierarchy
		FROM forum_forumdata
		WHERE cid = @cid) + '%'
GO

if exists (select * from dbo.sysobjects where id = object_id(N'dbo.zerofill') 
AND XTYPE IN (N'FN', N'IF', N'TF')) drop function dbo.zerofill
GO

CREATE FUNCTION dbo.zerofill (@number char(10)) 
-- К сожалению, в SQL Server нет эквивалента Оракловскому LPAD 
-- и MySQL'ному zerofill, поэтому приходится извращаться:
RETURNS char(10)
BEGIN
	DECLARE @temp_char CHAR(10)
	SET @temp_char = ''
	SET @temp_char = 
		REPLICATE('0', 
			DATALENGTH(@temp_char) - DATALENGTH(CAST(CAST(@number as int) as varchar(10)))
		) 
		+ CAST(@number AS CHAR)
	RETURN @temp_char
END
GO

if exists (select * from dbo.sysobjects where id = object_id(N'dbo.trg_forumdata_insert') 
and OBJECTPROPERTY(id, N'IsTrigger') = 1) DROP TRIGGER dbo.trg_forumdata_insert
GO

-- Триггер, который срабатывает при INSERT'е в таблицу
-- (вычисляет lvl, tid и hierarchy)
CREATE TRIGGER trg_forumdata_insert ON forum_forumdata FOR INSERT
	AS
	DECLARE @numrows AS int
	SET @numrows = @@rowcount
	IF @numrows > 1
		BEGIN
			RAISERROR('Многострочные insert-ы не поддерживаются!', 16, 1)
			ROLLBACK TRAN
		END
	ELSE
		IF @numrows = 1
		BEGIN
			UPDATE CHILD
			SET lvl =
				CASE
					WHEN CHILD.pid IS NULL THEN 0
					ELSE PARENT.lvl + 1
				END
			, tid = 
				CASE
					WHEN ((CHILD.pid IS NULL) OR (CHILD.pid = 0)) THEN CHILD.cid
					ELSE PARENT.tid
				END
			, hierarchy = 
				CASE
					WHEN CHILD.pid IS NULL THEN '.' 
					ELSE PARENT.hierarchy
				END
				+ dbo.zerofill(
					CAST(CHILD.cid AS varchar(10))
				) + '.'
			FROM forum_forumdata AS CHILD 
			JOIN inserted AS INS
			ON INS.cid = CHILD.cid
			LEFT OUTER JOIN forum_forumdata AS PARENT
			ON CHILD.pid = PARENT.cid
		END
GO

if exists (select * from dbo.sysobjects where id = 
object_id(N'dbo.trg_forumdata_update') AND OBJECTPROPERTY(id, N'IsTrigger') = 1) 
DROP TRIGGER dbo.trg_forumdata_update
GO

-- Триггер, который срабатывает при UPDATE'е таблицы
-- (заново вычисляет lvl, tid и hierarchy)
CREATE TRIGGER trg_forumdata_update ON forum_forumdata FOR UPDATE
AS
	IF UPDATE(cid)
		BEGIN
			RAISERROR('Номер записи менять нельзя!', 16, 1)
			ROLLBACK TRAN
		END
	ELSE
		IF UPDATE(pid)
		BEGIN
			UPDATE CHILD
			SET lvl = CHILD.lvl - INS.lvl + 
			CASE
				WHEN INS.pid IS NULL THEN 0
				ELSE PARENT.lvl + 1
			END
			, tid =
			CASE
				WHEN (CHILD.pid IS NULL) OR (CHILD.pid = 0) THEN CHILD.cid
				ELSE PARENT.tid
			END
			, hierarchy = ISNULL(PARENT.hierarchy, '.') +
			dbo.zerofill(
				CAST(INS.cid AS varchar(10))
			) + '.' +
			dbo.zerofill(
				right(CHILD.hierarchy, len(CHILD.hierarchy) - len(INS.hierarchy))
			)
			FROM forum_forumdata AS CHILD JOIN INSERTED AS INS
			ON CHILD.hierarchy LIKE INS.hierarchy + '%'
			LEFT OUTER JOIN forum_forumdata AS PARENT
			ON INS.pid = PARENT.cid
		END
GO


TRUNCATE TABLE dbo.forum_forumdata
GO

IF (IDENT_SEED('dbo.forum_forumdata') IS NOT NULL ) 
SET IDENTITY_INSERT dbo.forum_forumdata ON

SET NOCOUNT ON

-- Все добавляемые в дерево реплики будут детьми этой 
-- корневой реплики с номером 0 и pid = NULL
INSERT INTO forum_forumdata (cid, pid, subject, postdate, author, cookie, ipaddr, 
email, message, subscribe) VALUES(0, NULL, 'Root item', '', '', '', '', '', '', '')
GO

-- И ещё немного записей для примера:

IF (IDENT_SEED('dbo.forum_forumdata') IS NOT NULL ) 
SET IDENTITY_INSERT dbo.forum_forumdata ON

INSERT INTO forum_forumdata (cid, pid, subject, postdate, author, cookie, ipaddr, 
email, message, subscribe) VALUES(1, 0, 'Содержимое этого сервера', '23-07-1999 16:52:55', 
'Webmaster', '', '', 'webmaster@gfk.ru', ' Интересует ваше мнение о содержимом. ', 'no')  

INSERT INTO forum_forumdata (cid, pid, subject, postdate, author, cookie, ipaddr, 
email, message, subscribe) VALUES(4, 0, 'Метки для 5-и значной шкалы', '01-07-1999 09:42:46', 
'Давид', '', '', '', ' Я часто приобретаю исследования от различных компаний и я все время 
спорю с ними относительно того, должна ли 5-и значная шкала Лайкерат иметь текстовые метки. 
Я привожу аргумент, что если шкала не имеет меток, то респонденты отвечают в соответствии с 
их собственным индивидуальным восприятием того, что такое 4 или 5. Мне интересны ваши комментари 
по данному вопросу. ', 'no')  

INSERT INTO forum_forumdata (cid, pid, subject, postdate, author, cookie, ipaddr, email, 
message, subscribe) VALUES(5, 4, 'Re: Метки для 5-и значной шкалы', '01-07-1999 09:45:59', 
'Жора', '', '', '', ' Это очень уместный вопрос, который конечно же необходимо обсудить. 
Один из аспектов затрагивает проблему того, необходимо ли привязывать среднюю точку к тексту 
типа ''ни согласен ни не согласен'' или ''равнодушен''. Альтернатива заключается в использовании 
непрерывной шкалы, где ''1'' ассоциируется с наименьшим значением, а ''5'' -- с наивысшим. 
В этом случае ''3'' не ассоциируется с ''равнодушием'', и наоборот. Тут же возникают проблемы 
сравнения средних значений для разных шкал, а также относительное достоинство указываемых баллов 
в вечных вопросах ''how high is up?'' которые позникают в опросах, посвященных удовлетворенности 
пользователей, и т.д. Если вы используете статистики для анализа шкалированных данных, помните, 
что статистические инструменты как правило предполагают, что данные взяты из непрерывных, 
бесконечных и нормально распределенных переменных. ', 'no')  
GO

SET NOCOUNT OFF

IF (IDENT_SEED('dbo.forum_forumdata') IS NOT NULL )	SET IDENTITY_INSERT dbo.forum_forumdata OFF
GO

---