Sql-server – Why does this Index seek cause a lot more reads than index scan

indexindex-tuningsql server

As I've read that index seeks most of the time are preferred to index scans, I'm trying some stuff out.

I have a query that does 993 reads (checked with SQL Profiler) when it's using an index scan. When using an index seek it needs 44.347 reads. Feels like something is wrong, or I don't understand it.

This is the query for index scan:

select      t5.Id as t5Id
from        table1 t1
left join   table2 t2 on t2.Table1Id = t1.Id
left join   table3 t3 on t3.Table2Id = t2.Id
left join   table4 t4 on t4.Table3Id = t3.Id
left join   table5 t5 on t5.Table4Id = t4.Id

this is the query for index seek:

select      t5.Id as t5Id
from        table1 t1
left join   table2 t2 on t2.Table1Id = t1.Id
left join   table3 t3 on t3.Table2Id = t2.Id
left join   table4 t4 on t4.Table3Id = t3.Id
left join   table5 t5 WITH (FORCESEEK) on t5.Table4Id = t4.Id

The tables are simple and straight forward. At the end I fill them with some dummy data, so it can be reproduced easily.

CREATE TABLE [dbo].[table1](
    [Id] [bigint] IDENTITY(1,1) NOT NULL,
    [Name] [nvarchar](max) NOT NULL,
CONSTRAINT [PK_table1] PRIMARY KEY CLUSTERED 
(
    [Id] ASC
)WITH (PAD_INDEX = OFF, STATISTICS_NORECOMPUTE = OFF, IGNORE_DUP_KEY = OFF, ALLOW_ROW_LOCKS = ON, ALLOW_PAGE_LOCKS = ON) ON [PRIMARY]
) ON [PRIMARY] TEXTIMAGE_ON [PRIMARY]
GO




CREATE TABLE [dbo].[table2](
    [Id] [bigint] IDENTITY(1,1) NOT NULL,
    [Table1Id] [bigint] NOT NULL,
CONSTRAINT [PK_table2] PRIMARY KEY CLUSTERED 
(
    [Id] ASC
)WITH (PAD_INDEX = OFF, STATISTICS_NORECOMPUTE = OFF, IGNORE_DUP_KEY = OFF, ALLOW_ROW_LOCKS = ON, ALLOW_PAGE_LOCKS = ON) ON [PRIMARY]
) ON [PRIMARY]

ALTER TABLE     [dbo].[table2] WITH CHECK
ADD CONSTRAINT  [FK_table2_table1Id] FOREIGN KEY([table1Id])
REFERENCES      [dbo].[table1] ([Id])
GO

ALTER TABLE         [dbo].[table2]
CHECK CONSTRAINT    [FK_table2_table1Id]
GO


CREATE NONCLUSTERED INDEX [IdxTable2_FKTable1Id] ON [dbo].[table2]
(
    [Table1Id] ASC
)
INCLUDE (   [Id]) WITH (PAD_INDEX = OFF, STATISTICS_NORECOMPUTE = OFF, SORT_IN_TEMPDB = OFF, DROP_EXISTING = OFF, ONLINE = OFF, ALLOW_ROW_LOCKS = ON, ALLOW_PAGE_LOCKS = ON) ON [PRIMARY]
GO






CREATE TABLE [dbo].[table3](
    [Id] [bigint] IDENTITY(1,1) NOT NULL,
    [Table2Id] [bigint] NOT NULL,
CONSTRAINT [PK_table3] PRIMARY KEY CLUSTERED 
(
    [Id] ASC
)WITH (PAD_INDEX = OFF, STATISTICS_NORECOMPUTE = OFF, IGNORE_DUP_KEY = OFF, ALLOW_ROW_LOCKS = ON, ALLOW_PAGE_LOCKS = ON) ON [PRIMARY]
) ON [PRIMARY]

ALTER TABLE     [dbo].[table3] WITH CHECK
ADD CONSTRAINT  [FK_table3_table2Id] FOREIGN KEY([table2Id])
REFERENCES      [dbo].[table2] ([Id])
GO

ALTER TABLE         [dbo].[table3]
CHECK CONSTRAINT    [FK_table3_table2Id]
GO


CREATE NONCLUSTERED INDEX [IdxTable3_FKTable2Id] ON [dbo].[table3]
(
    [Table2Id] ASC
)
INCLUDE (   [Id]) WITH (PAD_INDEX = OFF, STATISTICS_NORECOMPUTE = OFF, SORT_IN_TEMPDB = OFF, DROP_EXISTING = OFF, ONLINE = OFF, ALLOW_ROW_LOCKS = ON, ALLOW_PAGE_LOCKS = ON) ON [PRIMARY]
GO







CREATE TABLE [dbo].[table4](
    [Id] [bigint] IDENTITY(1,1) NOT NULL,
    [Table3Id] [bigint] NOT NULL,
CONSTRAINT [PK_table4] PRIMARY KEY CLUSTERED 
(
    [Id] ASC
)WITH (PAD_INDEX = OFF, STATISTICS_NORECOMPUTE = OFF, IGNORE_DUP_KEY = OFF, ALLOW_ROW_LOCKS = ON, ALLOW_PAGE_LOCKS = ON) ON [PRIMARY]
) ON [PRIMARY]

ALTER TABLE     [dbo].[table4] WITH CHECK
ADD CONSTRAINT  [FK_table4_table3Id] FOREIGN KEY([table3Id])
REFERENCES      [dbo].[table4] ([Id])
GO

ALTER TABLE         [dbo].[table4]
CHECK CONSTRAINT    [FK_table4_table3Id]
GO

CREATE NONCLUSTERED INDEX [IdxTable4_FKTable3Id] ON [dbo].[table4]
(
    [Table3Id] ASC
)
INCLUDE (   [Id]) WITH (PAD_INDEX = OFF, STATISTICS_NORECOMPUTE = OFF, SORT_IN_TEMPDB = OFF, DROP_EXISTING = OFF, ONLINE = OFF, ALLOW_ROW_LOCKS = ON, ALLOW_PAGE_LOCKS = ON) ON [PRIMARY]
GO





CREATE TABLE [dbo].[table5](
    [Id] [bigint] IDENTITY(1,1) NOT NULL,
    [Table4Id] [bigint] NOT NULL,
    [Description] [nvarchar](2000) NOT NULL,
CONSTRAINT [PK_table5] PRIMARY KEY CLUSTERED 
(
    [Id] ASC
)WITH (PAD_INDEX = OFF, STATISTICS_NORECOMPUTE = OFF, IGNORE_DUP_KEY = OFF, ALLOW_ROW_LOCKS = ON, ALLOW_PAGE_LOCKS = ON) ON [PRIMARY]
) ON [PRIMARY]

ALTER TABLE     [dbo].[table5] WITH CHECK
ADD CONSTRAINT  [FK_table5_table4Id] FOREIGN KEY([table4Id])
REFERENCES      [dbo].[table5] ([Id])
GO

ALTER TABLE         [dbo].[table5]
CHECK CONSTRAINT    [FK_table5_table4Id]
GO

CREATE NONCLUSTERED INDEX [IdxTable5_FKTable4Id] ON [dbo].[table5]
(
    [Table4Id] ASC
)
INCLUDE (   [Id], [Description]) WITH (PAD_INDEX = OFF, STATISTICS_NORECOMPUTE = OFF, SORT_IN_TEMPDB = OFF, DROP_EXISTING = OFF, ONLINE = OFF, ALLOW_ROW_LOCKS = ON, ALLOW_PAGE_LOCKS = ON) ON [PRIMARY]
GO


set nocount on

DECLARE @i INT = 0;
DECLARE @j INT = 0;
DECLARE @k INT = 0;
DECLARE @l INT = 10;
DECLARE @m INT = 0;

declare @table1Id bigint
declare @table2Id bigint
declare @table3Id bigint
declare @table4Id bigint


begin tran
WHILE @i < 10
BEGIN
    INSERT INTO [dbo].[table1] ([Name]) VALUES (cast(@i as nvarchar(10)))
    SELECT @table1Id = SCOPE_IDENTITY()

    WHILE @j < 10
    BEGIN
        INSERT INTO [dbo].[table2] ([Table1Id]) VALUES (@table1Id)
        SELECT @table2Id = SCOPE_IDENTITY()

        WHILE @k < 10
        BEGIN
            INSERT INTO [dbo].[table3] ([Table2Id]) VALUES (@table2Id)
            SELECT @table3Id = SCOPE_IDENTITY()

            WHILE @l > 0
            BEGIN
                INSERT INTO [dbo].[table4] ([Table3Id]) VALUES (@table3Id)
                SELECT @table4Id = SCOPE_IDENTITY()

                WHILE @m < 10
                BEGIN
                    INSERT INTO [dbo].[table5] ([Table4Id], [Description]) VALUES (@table4Id, 'Not so long description')

                    SET @m = @m + 1;
                END;

                SET @m = 0;
                SET @l = @l - 1;
            END;

            SET @l = 10;
            SET @k = @k + 1;
        END;

        SET @k = 0;
        SET @j = @j + 1;
    END;

    SET @j = 0;
    SET @i = @i + 1;
END;
commit

Best Answer

First let's get an estimate of the number of reads required to do an index scan for IdxTable5_FKTable4Id:

-- get an idea of number of pages in the index
SELECT *
FROM sys.dm_db_partition_stats s
WHERE OBJECT_NAME(s.object_id) IN ('table5')
AND index_id > 1;

On my system the results of that query suggest that SQL Server will need around 900 reads to read the index in full. To test this, I'll run a simple query that is most efficiently implemented as an index scan in SQL Server. The query below needs the ID column for all rows in table5. SQL Server can just look at the index to get all of the data required for the query. Since every row is needed there isn't any wasted work here.

-- get logical reads after query execution
SET STATISTICS IO ON;

select t5.Id
from table5 t5;

Table 'table5'. Scan count 1, logical reads 900, physical reads 0, read-ahead reads 0, lob logical reads 0, lob physical reads 0, lob read-ahead reads 0.

Now let's consider your first test query that doesn't use the hint. The outer table for the final hash match is estimated to have 9657 rows on my system. The query optimizer decided that an index scan on IdxTable5_FKTable4Id is a good enough plan. Here is the query that I ran:

select      t5.Id as t5Id
from        table1 t1
left join   table2 t2 on t2.Table1Id = t1.Id
left join   table3 t3 on t3.Table2Id = t2.Id
left join   table4 t4 on t4.Table3Id = t3.Id
left join   table5 t5 on t5.Table4Id = t4.Id;

Table 'table5'. Scan count 1, logical reads 900, physical reads 0, read-ahead reads 0, lob logical reads 0, lob physical reads 0, lob read-ahead reads 0.

The outer table for the hash join actually had 10000 rows. However, because this is a hash join, SQL Server still needed to scan all 100000 rows from the index even though only 10000 were needed. That's why the same 900 logical reads are needed for this query as the first one. It could be argued that this is wasted effort by the query optimizer. Could it be more efficient to use an index seek to only fetch the 10000 rows that are needed from the index?

First let's get an estimate for the number of reads needed. Your index has a depth of 3:

-- get the index depth of the index
SELECT INDEXPROPERTY ( object_ID('table5'), 'IdxTable5_FKTable4Id' , 'IndexDepth');

Also I will enable TF 8744 to get cleaner results for the purpose of this demo:

-- Trace flag 8744: Disable pre-fetching for ranges
dbcc traceon(8744);

I know that there are 10000 rows from the outer table so one estimate for the number of logical reads is 10000 * (3 + 1) = 40000. Per row, that's 3 for the index depth and 1 to get the data.

Here is the query that was tested:

select      t5.Id as t5Id
from        table1 t1
left join   table2 t2 on t2.Table1Id = t1.Id
left join   table3 t3 on t3.Table2Id = t2.Id
left join   table4 t4 on t4.Table3Id = t3.Id
left join   table5 t5 WITH (FORCESEEK) on t5.Table4Id = t4.Id;

Table 'table5'. Scan count 10000, logical reads 41118, physical reads 0, read-ahead reads 0, lob logical reads 0, lob physical reads 0, lob read-ahead reads 0.

That's pretty close to the estimate of 40000.

What did we learn here? For this index there is a cost of about 4 reads per index seek and a fixed cost of 900 reads to do the scan. This means that from an IO perspective using index seeks will only be more efficient when getting a small percentage of the data from the index. Otherwise getting all of the data using an index scan, even if it isn't needed to return correct results for the query, will be more efficient.

For a final test, let's try just getting back the first 1000 rows from the original test query. On my system the query optimizer naturally picks an index seek even without the hint. Here is the query that I ran:

select TOP (1000)    t5.Id as t5Id
from        table1 t1
left join   table2 t2 on t2.Table1Id = t1.Id
left join   table3 t3 on t3.Table2Id = t2.Id
left join   table4 t4 on t4.Table3Id = t3.Id
left join   table5 t5 on t5.Table4Id = t4.Id;

Table 'table5'. Scan count 100, logical reads 409, physical reads 0, read-ahead reads 0, lob logical reads 0, lob physical reads 0, lob read-ahead reads 0.

For that query index seeks can be viewed as more efficient than an index scan. Note that the outer table has 100 rows so 100 seeks were done. One seek can return more than 1 row. That's why the logical reads are close to 400 as opposed to 4000.

Related Solutions

Sql-server – Index Seek vs Index Scan

Short version: seek is much better

Less short version: seek is generally much better, but a great many seeks (caused by bad query design with nasty correlated sub-queries for instance, or because you are making many queries in a cursor operation or other loop) can be worse than a scan, especially if your query may end up returning data from most of the rows in the affected table.

It helps to cover the whole family for data finding operations to fully understand the performance implications.

Table Scans: With no indexes at all that are relevant to your query the planner is forced to use a table scan meaning that every row is looked at. This can result in every page relating to the table's data being read from disk which is often the worst case. Note that for some queries it will use a table scan even when a useful index is present - this is usually because the data in the table is so small that it is more hassle to traverse the indexes (if this is the case you would expect the plan to change as the data grows, assuming the selectivity measure of the index is good).

Index Scans with Row Lookups: With no index that can be directly used for a seek is found but an index containing the right columns is present an index scan may be used. For instance, if you have a large table with 20 columns with an index on column1,col2,col3 and you issue SELECT col4 FROM exampletable WHERE col2=616, in this case scanning the index to query col2 is better than scanning the whole table. Once matching rows are found then the data pages need to be read to pickup col4 for output (or further joining) which is what the "bookmark lookup" stage is when you see it in query plans.

Index Scans without Row Lookups: If the above example was SELECT col1, col2, col3 FROM exampletable WHERE col2=616 then the extra effort to read data pages is not needed: once index rows matching col2=616 are found all the requested data is known. This is why you sometimes see columns that will never be searched on, but are likely to be requested for output, added to the end of indexes - it can save row lookups. When adding columns to an index for this reason and this reason only, add them with the INCLUDE clause to tell the engine that it doesn't need to optimise index layout for querying based on these columns (this can speed up updates made to those columns). Index scans can result from queries with no filtering clauses too: SELECT col2 FROM exampletable will scan this example index instead of the table pages.

Index Seeks (with or without row lookups): In a seek not all of the index is considered. For the query SELECT * FROM exampletable WHERE c1 BETWEEN 1234 AND 4567 the query engine can find the first row that will match by doing a tree-based search on the index on c1 then it can navigate the index in order until it gets to the end of the range (this is the same with a query for c1=1234 as there could be many rows matching the condition even for an = operation). This means that only relevant index pages (plus a few needed for the initial search) need to be read instead of every page in the index (or table).

Clustered Indexes: With a clustered index the table data is stored in the leaf nodes of that index instead of being in a separate heap structure. This means that there will never need to be any extra row lookups after finding rows using that index no matter what columns are needed [unless you have off-page data like TEXT columns or VARCHAR(MAX) columns containing long data].

You can only have one clustered index for this reason^[1], the clustered index is your table instead of having a separate heap structure, so if you use one^[2] chose where you put it carefully in order to get maximum gain.

Also note that the clustered index because the "clustering key" for the table and is included in every non-clustered index on the table, so a wide clustered index is generally not a good idea.

^{[1] Actually, you can effectively have multiple clustered indexes by defining non-clustered indexes that cover or include every column on the table, but this is likely to be wasteful of space has a write performance impact so if you consider doing it make sure you really need to.}

^{[2] When I say "if you use a clustered index", do note that it is generally recommended that you do have one on each table. There are exceptions as with all rules-of-thumb, tables that see little other than bulk inserts and unordered reads (staging tables for ETL processes perhaps) being the most common counter example.}

Additional point: Incomplete Scans:

It is important to remember that depending on the rest of the query a table/index scan may not actually scan the whole table - if the logic allows the query plan may be able to cause it to abort early. The simplest example of this is SELECT TOP(1) * FROM HugeTable - if you look at the query plan for that you'll see that only one row was returned from the scan and if you watch the IO statistics (SET STATISTICS IO ON; SELECT TOP(1) * FROM HugeTable) you'll see that it only read a very small number of pages (perhaps just one).

The same can happen if the predicate of a WHERE or JOIN ... ON clause can be run concurrently with the scan that is the source if its data. The query planner/runner can sometimes be very clever about pushing predicates back towards the data sources to allow early termination of scans in this way (and sometimes you can be clever in rearranging queries to help it do so!). While the data flows right-to-left as per the arrows in the standard query plan display, the logic runs left-to-right and each step (right-to-left) is not necessarily run to completion before the next can start. In the simple example above if you look at each block in the query plan as an agent the SELECT agent asks the TOP agent for a row which in turn asks the TABLE SCAN agent for one, then the SELECT agent asks for another but the TOP agent knows there is no need doesn't bother to even ask the table reader, the SELECT agent gets a "no more is relevant" response and knows all the work is done. Many operations block this sort of optimisation of course so often in more complicated examples a table/index scan really does read every row, but be careful not to jump to the conclusion that any scan must be an expensive operation.

Sql-server – Parent-Child Tree Hierarchical ORDER

OK, enough brain cells are dead.

SQL Fiddle

WITH cte AS
(
  SELECT 
    [ICFilterID], 
    [ParentID],
    [FilterDesc],
    [Active],
    CAST(0 AS varbinary(max)) AS Level
  FROM [dbo].[ICFilters]
  WHERE [ParentID] = 0
  UNION ALL
  SELECT 
    i.[ICFilterID], 
    i.[ParentID],
    i.[FilterDesc],
    i.[Active],  
    Level + CAST(i.[ICFilterID] AS varbinary(max)) AS Level
  FROM [dbo].[ICFilters] i
  INNER JOIN cte c
    ON c.[ICFilterID] = i.[ParentID]
)

SELECT 
  [ICFilterID], 
  [ParentID],
  [FilterDesc],
  [Active]
FROM cte
ORDER BY [Level];

Best Answer

Related Solutions

Sql-server – Index Seek vs Index Scan

Sql-server – Parent-Child Tree Hierarchical ORDER

Related Question