1

I have a Category table like below :

enter image description here

I have a recursive relationship on this Category table. I use soft delete in my project. I have 2000 rows in Category table. When I want to show data in a UI dropdown it takes about 3 minutes.

Which columns need an index to improve query speed?

Table definition:

 CREATE TABLE [dbo].[Category](
    [CategoryId] [uniqueidentifier] NOT NULL,
    [CategoryCode] [int] IDENTITY(1,1) NOT NULL,
    [CategoryName] [nvarchar](400) NOT NULL,
    [ParentId] [uniqueidentifier] NULL,
    [DisplayOrder] [int] NOT NULL,
    [Description] [nvarchar](max) NULL,
    [IsActive] [bit] NOT NULL,
    [IsShowOnMenu] [bit] NOT NULL,
    [AttachmentId] [uniqueidentifier] NULL,
    [Depth] [int] NOT NULL,
    [Path] [nvarchar](max) NULL,
    [IsDeleted] [bit] NOT NULL,

 CONSTRAINT [PK_dbo.Category] PRIMARY KEY CLUSTERED 
(
    [CategoryId] ASC
)WITH (PAD_INDEX = OFF, STATISTICS_NORECOMPUTE = OFF, IGNORE_DUP_KEY = OFF, ALLOW_ROW_LOCKS = ON, ALLOW_PAGE_LOCKS = ON) ON [PRIMARY]
)

My query is in C#. I used C# statment to generate show all category in dropdown. My query is:

exec sp_executesql N'SELECT 
[Project1].[DisplayOrder] AS [DisplayOrder], 
[Project1].[CategoryId] AS [CategoryId], 
[Project1].[CategoryName] AS [CategoryName]
FROM ( SELECT 
    [Extent1].[CategoryId] AS [CategoryId], 
    [Extent1].[CategoryName] AS [CategoryName], 
    [Extent1].[DisplayOrder] AS [DisplayOrder]
    FROM [dbo].[Category] AS [Extent1]
    WHERE (([Extent1].[IsDeleted] = @DynamicFilterParam_1) OR (@DynamicFilterParam_2 IS NOT NULL)) AND ([Extent1].[ParentId] = @p__linq__0)
)  AS [Project1]
ORDER BY [Project1].[DisplayOrder] ASC',N'@DynamicFilterParam_1 bit,@DynamicFilterParam_2 bit,@p__linq__0 uniqueidentifier',@DynamicFilterParam_1=0,@DynamicFilterParam_2=NULL,@p__linq__0='8d8dd739-a132-e3ef-5443-159ecf8adc44'

Above query runs for each item, because I need to get all children.

  • 3
    I would expect a composite index on ParentId and CategoryId would be most beneficial to a recursive query, especially if clustered or with included columns to cover the query and perhaps filtered. Even with no useful index, 3 minutes seem very high, even with many levels of recursion. Provide the DDL and query like Michael requested. – Dan Guzman May 28 '16 at 12:39
  • 2
    I think you should try to refactor your code on the client side so you only have to fetch the 2000 rows once. Having the data client side an doing loops an lookups or whatever is needed to build the structure you want will be faster than hitting the db with that query 2000 times. – Mikael Eriksson May 29 '16 at 6:11
  • 2
    As @Mikael Eriksson said, you are not doing recursion inside SQL server itself, but rather from C# by executing this query repeatedly (2000 times). Based on the above, indexes will not solve your problem (you may get an improvement of, say, 25% but you will not get the "orders of magnitude" improvement that you are looking for). You need to change the overall design, by either using caching on C# and building the tree in C# or generating a tree in the database and returning that to C#. – Alex Jun 2 '16 at 10:39
  • @KarInter can you add the actual plan xml (use pastebin and link it here) please ? – Kin Shah Jun 2 '16 at 18:46
2
+50

Try this index for some noticeable improvement:

CREATE NONCLUSTERED INDEX [CatIndex1] ON [dbo].[Category]
(
    [ParentID] ASC
)
INCLUDE (   [CategoryID],
    [CategoryName],
    [DisplayORder]) 

I am interested in the time reduction. Please let me know your findings.

p.s. consider sorting only once with the ORDER BY if you're running it multiple times. Perhaps put data into a C# DataTable or SQL temp table and sort at the very end of all retrieval operations.

  • Yea! glad this works for you. Let us know your reduction in processing time and what finally worked the best. – Sting Jun 10 '16 at 14:56
2

There are a number of ways the design of your model can change to speed up this kind of query.

a) Materialized path

You basically store a path for each node in the tree. Retrieving the sub tree is something like:

select ...
from category
where path like :current_path || '%';

When adding a category somewhere in the tree, the new path becomes the path of the parent + parent.

b) nested sets

For each category you store an upper and a lower bound. Retrieving the sub tree is something like:

select ...
from category
where upper_bound < :current_upper_bound
  and lower_bound > :current_lower_bound;

Maintaining the tree is a bit of a challenge. Inserting a category somewhere may cause a renumbering of large parts of the table. If you're tree is dynamic and changes a lot you should probably look for a different solution.

c) Transitive closure

The idea is to keep a separate table holding the transitive closure of the tree. Say:

CREATE TABLE dbo.Category_Closure (
    CategoryId ... NOT NULL,
    AncestorId ... NOT NULL,
        PRIMARY KEY (CategoryId, AncestorId)
);

Retrieving the sub tree is something like:

select c.*
from category c
join category_closure cc
    on c.CategoryId = cc.CategoryId
where cc.AncestorId = :current_category_id;

When adding a category somewhere in the tree, you also add the ancestors of the new parent + the parent together with the new category in the closure table. Using triggers to maintain the closure table is an common approach.

There's a lot of materials written regarding this. I suggest you google for:

Nested sets + sql
Materialized Path + sql
Transitive Closure + sql

I have some notes on Transitive Closure and how to maintain it via triggers at:

http://dustbite.se/tree/

that may be of interest

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.