|
|
|
4.10 Preparing Multilevel Operations4.10.1 ProblemYour system performs many multilevel, hierarchical operations, and the performance of those operations has not been satisfactory. You need to improve that poor performance. 4.10.2 SolutionOne solution is to store additional accessibility information into a service table, and then use that information when querying your hierarchical table. For example, the following ProjectPaths table records the path to, and the depth of, each vertex in the Projects table: CREATE TABLE ProjectPaths( VertexId INTEGER, Depth INTEGER, Path VARCHAR(300) ) After creating the ProjectPaths table, you can use the following procedure to fill the table with the depth and path information for each vertex in the Projects table: CREATE PROCEDURE BuildProjectPathsRecursive
@VertexId INTEGER
AS
SET NOCOUNT ON
DECLARE @Path VARCHAR(300)
DECLARE @Depth INTEGER
SELECT @Depth=a.Depth,@Path=a.Path
FROM ProjectPaths a JOIN Projects p ON p.parent=a.vertexId
WHERE @vertexId=p.vertexId
DELETE FROM ProjectPaths WHERE VertexId=@VertexId
INSERT INTO ProjectPaths VALUES(
@VertexId,
isnull(@Depth,0)+1,
isnull(@Path,'.')+CAST(@VertexId AS VARCHAR(15))+'.')
DECLARE subprojects CURSOR LOCAL FOR
SELECT VertexId FROM Projects p WHERE Parent=@VertexId
OPEN subprojects
FETCH NEXT FROM subprojects INTO @VertexId
WHILE @@FETCH_STATUS=0 BEGIN
EXEC BuildProjectPathsRecursive @VertexId
FETCH NEXT FROM subprojects INTO @VertexId
END
CLOSE subprojects
DEALLOCATE subprojects
SET NOCOUNT OFF
This procedure takes one parameter, which tells the procedure with which node to start. The procedure then works its way down the hierarchy. To process all nodes in the Projects table, invoke this procedure and pass a value of 1 as follows: BuildProjectPathsRecursive 1 The procedure fills the ProjectPaths table with additional information for every vertex. The Depth column records the depth of each vertex. The Path column records the path to each vertex. In the path, the vertex numbers are separated by dots. The ProjectPaths table that will be built contains the following rows: VertexId Depth Path ----------- ----------- ----------- 1 1 .1. 2 2 .1.2. 3 3 .1.2.3. 4 3 .1.2.4. 5 3 .1.2.5. 6 3 .1.2.6. 7 4 .1.2.6.7. 8 2 .1.8. 9 3 .1.8.9. 10 3 .1.8.10. 11 4 .1.8.10.11. 12 3 .1.8.12. 13 2 .1.13. 14 3 .1.13.14. 15 3 .1.13.15. 16 3 .1.13.16. 17 2 .1.17. 18 3 .1.17.18. 19 2 .1.19. 4.10.3 DiscussionThe idea for this recipe has been taken from an article published by Itzik Ben-Gan (SQL Server Magazine, June, 2000). His development of this technique is a recent achievement resulting from his search for an ultimate support structure to improve the efficiency of the classical hierarchical model. Although it was originally promoted as an add-on to an existing hierarchy table, we see no reason why you shouldn't normalize properly and separate the hierarchy and its data from the support structure. The path leading to every vertex is stored in the ProjectPaths table. This represents the work of traversing the hierarchy, and because it is stored in the ProjectPaths table, it only needs to be done once. Please note that the length of the Path field can be changed according to your needs. It does, however, make sense to keep it reasonably small, especially if you want to index it. The stored procedure named BuildProjectPathsRecursive fills the ProjectPaths table with the paths to each vertex in the subtree. It uses the recursive traversal algorithm introduced earlier in this chapter and runs the following code for each vertex: SELECT @Depth=a.Depth,@Path=a.Path
FROM ProjectPaths a JOIN Projects p ON p.parent=a.vertexId
WHERE @vertexId=p.vertexId
DELETE FROM ProjectPaths WHERE VertexId=@VertexId
INSERT INTO ProjectPaths VALUES(
@VertexId,
isnull(@Depth,0)+1,
isnull(@Path,'.')+CAST(@VertexId AS VARCHAR(15))+'.')
The SELECT statement reads the depth and path data from the parent. Next, any old information for the vertex is deleted from the ProjectPaths table, and new data is inserted. If the @Depth or @Path variables are null, indicating that no access path for the parent exists, then an initial value of 0 is set for the depth, and an initial value of a dot (.) is set for the path. Regardless of how the depth gets set, it is increased by one. That's because the @Depth variable represents the depth of the current node's parent. You have to increment that depth by 1 to get the current node's depth. Similarly, the @Path variable contains the path to the parent. The current vertex ID is appended onto that path to yield the path to the current node. These new depth and path values are then inserted into the ProjectPaths table. If you prefer nonrecursive algorithms, you can rewrite the recursive BuildProjectPathsRecursive procedure as a nonrecursive procedure. This code is as follows and uses the stack-based technique shown earlier in the recipe titled Section 4.9: CREATE PROCEDURE BuildProjectsPaths
@VertexId INTEGER
AS
SET NOCOUNT ON
DECLARE @lvl INTEGER
CREATE TABLE #stack (
VertexId INTEGER,
Lvl INTEGER
)
SELECT @Lvl = 1
INSERT INTO #stack
SELECT VertexId,1 FROM Projects WHERE VertexId=@VertexID
WHILE @Lvl > 0 BEGIN
IF EXISTS (SELECT * FROM #stack WHERE lvl = @lvl) BEGIN
SELECT TOP 1 @VertexId = VertexId FROM #stack
WHERE lvl = @lvl
ORDER BY VertexId
DELETE FROM ProjectPaths WHERE VertexId=@VertexId
INSERT INTO ProjectPaths
SELECT p.vertexId,
isnull(a.Depth,0)+1,
isnull(a.Path,'.')+CAST(p.VertexId AS VARCHAR(15))+'.'
FROM ProjectPaths a,Projects p
WHERE @vertexId=p.vertexId AND p.parent*=a.vertexId
DELETE FROM #stack WHERE vertexId = @VertexId
INSERT #stack
SELECT VertexId, @lvl + 1 FROM Projects
WHERE parent = @VertexId
IF @@ROWCOUNT > 0
SELECT @lvl = @lvl + 1
END ELSE
SELECT @lvl = @lvl - 1
END
SET NOCOUNT OFF
|
|
|
|