Why select top ... order by indexed column still sort?

Question

I created the following index to cover the select top statement.

-- Column A, B have type of int
create unique index ix_ on T (A, B) with (data_compression = page) 
-- tried to create non-unique index too and the execution plan is the same

select top 20 A, B from T order by A, B -- 19 seconds
select top 20 A, B from T -- return result instantly

However, it still take a while (19 seconds on my table which has 50 million rows) and execution plan shows there is still a "Sort"?

The execution plan shows

Select (Cost: 0%) ← Top (Cost: 0%) ← Parallelism (Gather Streams) (Cost: 0%) ← Sort (Top N Sort) Cost: 93% ← Index Scan (NonClustered) [T.ix_] Cost: 7%

---

Execution Plan

<?xml version="1.0" encoding="utf-16"?>
<ShowPlanXML xmlns:xsi="http://www.w3.org/2001/XMLSchema-instance" xmlns:xsd="http://www.w3.org/2001/XMLSchema" Version="1.2" Build="12.0.4100.1" xmlns="http://schemas.microsoft.com/sqlserver/2004/07/showplan">
  <BatchSequence>
    <Batch>
      <Statements>
        <StmtSimple StatementCompId="1" StatementEstRows="20" StatementId="1" StatementOptmLevel="FULL" CardinalityEstimationModelVersion="120" StatementSubTreeCost="552.009" StatementText="select  top 20 A A, B B --, checksum(*) cs&#xA;from T with (index(ix_))&#xA;order by A, B" StatementType="SELECT" QueryHash="0x1531573504856080" QueryPlanHash="0x5D4FED760C34AF43" RetrievedFromCache="true">
          <StatementSetOptions ANSI_NULLS="true" ANSI_PADDING="true" ANSI_WARNINGS="true" ARITHABORT="true" CONCAT_NULL_YIELDS_NULL="true" NUMERIC_ROUNDABORT="false" QUOTED_IDENTIFIER="true" />
          <QueryPlan DegreeOfParallelism="8" MemoryGrant="1024" CachedPlanSize="24" CompileTime="2" CompileCPU="2" CompileMemory="256">
            <ThreadStat Branches="1" UsedThreads="8">
              <ThreadReservation NodeId="0" ReservedThreads="8" />
            </ThreadStat>
            <MemoryGrantInfo SerialRequiredMemory="16" SerialDesiredMemory="24" RequiredMemory="896" DesiredMemory="960" RequestedMemory="1024" GrantWaitTime="0" GrantedMemory="1024" MaxUsedMemory="896" />
            <OptimizerHardwareDependentProperties EstimatedAvailableMemoryGrant="768000" EstimatedPagesCached="768000" EstimatedAvailableDegreeOfParallelism="8" />
            <RelOp AvgRowSize="15" EstimateCPU="2E-06" EstimateIO="0" EstimateRebinds="0" EstimateRewinds="0" EstimatedExecutionMode="Row" EstimateRows="20" LogicalOp="Top" NodeId="0" Parallel="false" PhysicalOp="Top" EstimatedTotalSubtreeCost="552.009">
              <OutputList>
                <ColumnReference Database="[DB]" Schema="[dbo]" Table="[T]" Alias="[T]" Column="B" />
                <ColumnReference Database="[DB]" Schema="[dbo]" Table="[T]" Alias="[T]" Column="A" />
              </OutputList>
              <RunTimeInformation>
                <RunTimeCountersPerThread Thread="0" ActualRows="20" ActualEndOfScans="1" ActualExecutions="1" />
              </RunTimeInformation>
              <Top RowCount="false" IsPercent="false" WithTies="false">
                <TopExpression>
                  <ScalarOperator ScalarString="(20)">
                    <Const ConstValue="(20)" />
                  </ScalarOperator>
                </TopExpression>
                <RelOp AvgRowSize="15" EstimateCPU="0.0286101" EstimateIO="0" EstimateRebinds="0" EstimateRewinds="0" EstimatedExecutionMode="Row" EstimateRows="20" LogicalOp="Gather Streams" NodeId="1" Parallel="true" PhysicalOp="Parallelism" EstimatedTotalSubtreeCost="552.009">
                  <OutputList>
                    <ColumnReference Database="[DB]" Schema="[dbo]" Table="[T]" Alias="[T]" Column="B" />
                    <ColumnReference Database="[DB]" Schema="[dbo]" Table="[T]" Alias="[T]" Column="A" />
                  </OutputList>
                  <RunTimeInformation>
                    <RunTimeCountersPerThread Thread="0" ActualRows="20" ActualEndOfScans="0" ActualExecutions="1" />
                  </RunTimeInformation>
                  <Parallelism>
                    <OrderBy>
                      <OrderByColumn Ascending="true">
                        <ColumnReference Database="[DB]" Schema="[dbo]" Table="[T]" Alias="[T]" Column="A" />
                      </OrderByColumn>
                      <OrderByColumn Ascending="true">
                        <ColumnReference Database="[DB]" Schema="[dbo]" Table="[T]" Alias="[T]" Column="B" />
                      </OrderByColumn>
                    </OrderBy>
                    <RelOp AvgRowSize="15" EstimateCPU="212.739" EstimateIO="303.269" EstimateRebinds="0" EstimateRewinds="0" EstimatedExecutionMode="Row" EstimateRows="20" LogicalOp="TopN Sort" NodeId="2" Parallel="true" PhysicalOp="Sort" EstimatedTotalSubtreeCost="551.98">
                      <OutputList>
                        <ColumnReference Database="[DB]" Schema="[dbo]" Table="[T]" Alias="[T]" Column="B" />
                        <ColumnReference Database="[DB]" Schema="[dbo]" Table="[T]" Alias="[T]" Column="A" />
                      </OutputList>
                      <MemoryFractions Input="1" Output="1" />
                      <RunTimeInformation>
                        <RunTimeCountersPerThread Thread="8" ActualRebinds="1" ActualRewinds="0" ActualRows="12" Batches="0" ActualEndOfScans="0" ActualExecutions="1" ActualExecutionMode="Row" />
                        <RunTimeCountersPerThread Thread="3" ActualRebinds="1" ActualRewinds="0" ActualRows="12" Batches="0" ActualEndOfScans="0" ActualExecutions="1" ActualExecutionMode="Row" />
                        <RunTimeCountersPerThread Thread="7" ActualRebinds="1" ActualRewinds="0" ActualRows="12" Batches="0" ActualEndOfScans="0" ActualExecutions="1" ActualExecutionMode="Row" />
                        <RunTimeCountersPerThread Thread="6" ActualRebinds="1" ActualRewinds="0" ActualRows="20" Batches="0" ActualEndOfScans="1" ActualExecutions="1" ActualExecutionMode="Row" />
                        <RunTimeCountersPerThread Thread="5" ActualRebinds="1" ActualRewinds="0" ActualRows="12" Batches="0" ActualEndOfScans="0" ActualExecutions="1" ActualExecutionMode="Row" />
                        <RunTimeCountersPerThread Thread="4" ActualRebinds="1" ActualRewinds="0" ActualRows="12" Batches="0" ActualEndOfScans="0" ActualExecutions="1" ActualExecutionMode="Row" />
                        <RunTimeCountersPerThread Thread="2" ActualRebinds="1" ActualRewinds="0" ActualRows="12" Batches="0" ActualEndOfScans="0" ActualExecutions="1" ActualExecutionMode="Row" />
                        <RunTimeCountersPerThread Thread="1" ActualRebinds="1" ActualRewinds="0" ActualRows="12" Batches="0" ActualEndOfScans="0" ActualExecutions="1" ActualExecutionMode="Row" />
                        <RunTimeCountersPerThread Thread="0" ActualRebinds="0" ActualRewinds="0" ActualRows="0" ActualEndOfScans="0" ActualExecutions="0" />
                      </RunTimeInformation>
                      <TopSort Distinct="false" Rows="20">
                        <OrderBy>
                          <OrderByColumn Ascending="true">
                            <ColumnReference Database="[DB]" Schema="[dbo]" Table="[T]" Alias="[T]" Column="A" />
                          </OrderByColumn>
                          <OrderByColumn Ascending="true">
                            <ColumnReference Database="[DB]" Schema="[dbo]" Table="[T]" Alias="[T]" Column="B" />
                          </OrderByColumn>
                        </OrderBy>
                        <RelOp AvgRowSize="15" EstimateCPU="5.81245" EstimateIO="30.16" EstimateRebinds="0" EstimateRewinds="0" EstimatedExecutionMode="Row" EstimateRows="42226500" LogicalOp="Index Scan" NodeId="3" Parallel="true" Partitioned="true" PhysicalOp="Index Scan" EstimatedTotalSubtreeCost="35.9724" TableCardinality="42226500">
                          <OutputList>
                            <ColumnReference Database="[DB]" Schema="[dbo]" Table="[T]" Alias="[T]" Column="B" />
                            <ColumnReference Database="[DB]" Schema="[dbo]" Table="[T]" Alias="[T]" Column="A" />
                          </OutputList>
                          <RunTimeInformation>
                            <RunTimeCountersPerThread Thread="8" ActualRows="3993270" Batches="0" ActualEndOfScans="1" ActualExecutions="1" ActualExecutionMode="Row" />
                            <RunTimeCountersPerThread Thread="7" ActualRows="2713924" Batches="0" ActualEndOfScans="1" ActualExecutions="1" ActualExecutionMode="Row" />
                            <RunTimeCountersPerThread Thread="6" ActualRows="8866373" Batches="0" ActualEndOfScans="1" ActualExecutions="1" ActualExecutionMode="Row" />
                            <RunTimeCountersPerThread Thread="5" ActualRows="10625143" Batches="0" ActualEndOfScans="1" ActualExecutions="1" ActualExecutionMode="Row" />
                            <RunTimeCountersPerThread Thread="4" ActualRows="4254726" Batches="0" ActualEndOfScans="1" ActualExecutions="1" ActualExecutionMode="Row" />
                            <RunTimeCountersPerThread Thread="3" ActualRows="3195887" Batches="0" ActualEndOfScans="1" ActualExecutions="1" ActualExecutionMode="Row" />
                            <RunTimeCountersPerThread Thread="2" ActualRows="3626671" Batches="0" ActualEndOfScans="1" ActualExecutions="1" ActualExecutionMode="Row" />
                            <RunTimeCountersPerThread Thread="1" ActualRows="4950538" Batches="0" ActualEndOfScans="1" ActualExecutions="1" ActualExecutionMode="Row" />
                            <RunTimeCountersPerThread Thread="0" ActualRows="0" ActualEndOfScans="0" ActualExecutions="0" />
                          </RunTimeInformation>
                          <RunTimePartitionSummary>
                            <PartitionsAccessed PartitionCount="41">
                              <PartitionRange Start="1" End="41" />
                            </PartitionsAccessed>
                          </RunTimePartitionSummary>
                          <IndexScan Ordered="false" ForcedIndex="true" ForceSeek="false" ForceScan="false" NoExpandHint="false" Storage="RowStore">
                            <DefinedValues>
                              <DefinedValue>
                                <ColumnReference Database="[DB]" Schema="[dbo]" Table="[T]" Alias="[T]" Column="B" />
                              </DefinedValue>
                              <DefinedValue>
                                <ColumnReference Database="[DB]" Schema="[dbo]" Table="[T]" Alias="[T]" Column="A" />
                              </DefinedValue>
                            </DefinedValues>
                            <Object Database="[DB]" Schema="[dbo]" Table="[T]" Index="[ix_]" Alias="[T]" IndexKind="NonClustered" Storage="RowStore" />
                          </IndexScan>
                        </RelOp>
                      </TopSort>
                    </RelOp>
                  </Parallelism>
                </RelOp>
              </Top>
            </RelOp>
          </QueryPlan>
        </StmtSimple>
      </Statements>
    </Batch>
  </BatchSequence>
</ShowPlanXML>

Answer 1

Your table is partitioned by B.

The index inherits this partitioning scheme unless you specify otherwise. For example with

create unique index ix_ on T (A, B)  with (data_compression = page) on [primary] 

(In which case it becomes non aligned and prevents some operations such as metadata only switching)

The lowest "A" value might be in any partition.

This isn't optimised very well. You can keep the aligned index and use this rewrite based on the code here

SELECT TOP 20 A, B 
FROM sys.partitions AS P
  CROSS APPLY ( SELECT TOP 20 A, B 
                FROM dbo.T
                WHERE $PARTITION.YourPartitionFunction(T.B) = P.partition_number 
                ORDER BY A,B
                ) AS A
WHERE P.object_id = OBJECT_ID('dbo.T')
AND P.index_id = INDEXPROPERTY( OBJECT_ID('dbo.T'), 'ix_', 'IndexID' )
ORDER BY  A,B

It will get the top 20 rows from each of the 41 partitions (without a sort) then just sort the 820 rows that result from that to get the final top 20 (rather than the whole 42 million).