Help modify / optimize database schema / indexes for faster query result when using LIKE and EXISTS clauses

Answer 1

I would try to add an index on the foreign keys in your UserSiteRight_T table - they're not yet indexed, and an index on those fields should speed up the lookups:

CREATE NONCLUSTERED INDEX IX01_UserSiteRight
  ON UserSiteRight_T(UserID_i)

CREATE NONCLUSTERED INDEX IX02_UserSiteRight
  ON UserSiteRight_T(SiteID_i)  

and on your SitePath_T table as well:

CREATE NONCLUSTERED INDEX IX01_SitePath
  ON dbo.SitePath_T(SiteID_i)

Try to put these in place, then run your queries again, and compare the run times and the execution plans - do you see any improvement??

It's a common misconception, but SQL Server does not automatically put an index on a foreign key column (like SiteID_i on SitePath_T), even though the general consensus is that a foreign key is useful and potentially speeds up both enforcement of referential integrity, as well as JOINs over those foreign keys.

Answer 2

Based on:

SELECT sp.SiteID_i 
  FROM SitePath_t sp 
 WHERE EXISTS ( SELECT * 
              FROM [dbo].[SitePath_T] usp 
                 , [dbo].[UserSiteRight_T] uusr 
             WHERE uusr.SiteID_i = usp.SiteID_i 
               AND uusr.UserID_i = 2484 
               AND usp.Path_v LIKE sp.Path_v+'%' ) 

(which is just fine based on the fact that you're doing a Semi Join).

It's focussing (rightly) on the uusr table first, to find the records for that user. It's already doing a CIX Seek on that, which is good. From there, it's finding the corresponding records in usp according to the SiteID_i fields.

So next consider the fact that it wants to find the Sites by SiteID_i, and what kind of join you want this to be.

How about a Merge Join? That would be nice, but requires the data to be sorted on both sides. That's fine if the indexes are in the right order...

...and after that, you want to be finding stuff based on the Path. So how about:

CREATE INDEX ix_UUSR on [dbo].[UserSiteRight_T] (UserID_i, SiteID_i);
CREATE INDEX ix_usp on [dbo].[SitePath_T] (SiteID_i) INCLUDE (Path_v);

And then another index on SitePath_T that finds the SiteIDs you want:

CREATE INDEX ix_sp on [dbo].[SitePath_T] (Path_v) INCLUDE (SiteID_i);

There may be a Nested Loop used on this final one, but that's hopefully not too bad. The thing that's going to impact your system will be the first two indexes, which should let you see a Merge Join between the two tables in your EXISTS clause.

Answer 3

The self join on SitePath_T to find parents is killing you. Perhaps you should add a column for ParentSiteID_i and use a normal recursive CTE?

Then it becomes:

WITH Recurse_CTE AS (
  SELECT 
    us.SiteID_i
  , us.ParentSiteID_i
  , 0 AS RecurseDepth_i
  FROM dbo.SitePath_T us
  JOIN dbo.UserSiteRight_T uusr ON us.SiteID_i = uusr.SiteID_i
  WHERE uusr.UserID_i = 2484
  UNION ALL
  SELECT 
    us.SiteID_i
  , us.ParentSiteID_i
  , rcs.RecurseDepth_i+1 AS RecurseDepth_i
  FROM dbo.SitePath_T us
  JOIN Recurse_CTE rcs ON us.SiteID_i = rcs.ParentSiteID_i
  )
SELECT * FROM Recurse_CTE

Throw an index on SitePath_T (ParentSiteID_i) and performance should be snappy.

Answer 4

I would also like to give credit to Rob Farley for understanding the schema/algorithm and providing the indexing schema.

But the problem is not the indexing schema.

It's the Query Optimizer !

More about it in this followup post : http://stackoverflow.com/questions/2040314