We seem to be having quite unusual bad performance on queries that use an index. for example the table looks like

  • ID VARCHAR(50)
  • Col1
  • Col2
  • etc

So we need to insert a row in the database and later look it up on the ID. But the ID a third party has and we have the PK. We need to get the PK back. But a very large range of those IDs have very similar starting values. for example

  • "//45-423484834893457"
  • "//45-573459834589345"
  • "//45-345345345345345

I am not sure how SQL Server is traversing the BTree, if it hashing the values or doing string comparisons starting at the left most position.

Could having a very large range of very similar values (at least first 4 characters are identical) lead to a poorly performing index when querying for those values?


Sorry the look up query is


Marks request:

SQL Server parse and compile time: 
   CPU time = 0 ms, elapsed time = 0 ms.

 SQL Server Execution Times:
   CPU time = 0 ms,  elapsed time = 0 ms.
SQL Server parse and compile time: 
   CPU time = 0 ms, elapsed time = 22 ms.
SQL Server parse and compile time: 
   CPU time = 0 ms, elapsed time = 30 ms.

(1 row(s) affected)
SQL Server parse and compile time: 
   CPU time = 0 ms, elapsed time = 0 ms.

(1 row(s) affected)
SQL Server parse and compile time: 
   CPU time = 0 ms, elapsed time = 0 ms.

<ShowPlanXML xmlns:xsi="http://www.w3.org/2001/XMLSchema-instance" xmlns:xsd="http://www.w3.org/2001/XMLSchema" Version="1.1" Build="10.0.4000.0" xmlns="http://schemas.microsoft.com/sqlserver/2004/07/showplan">
        <StmtSimple StatementCompId="1" StatementEstRows="1" StatementId="1" StatementOptmLevel="TRIVIAL" StatementSubTreeCost="0.0032831" StatementText="SELECT&#xD;&#xA;      LocalMsgId&#xD;&#xA;    FROM&#xD;&#xA;      Pdu (nolock)&#xD;&#xA;  WHERE&#xD;&#xA;     RemoteMsgId = '41/00/2789aeb8/1127796335811'&#xD;&#xA;      &#xD;" StatementType="SELECT" ParameterizedText="(@1 varchar(8000))SELECT [LocalMsgId] FROM [Pdu](nolock) WHERE [RemoteMsgId]=@1" QueryHash="0x677C78E75E33C4C7" QueryPlanHash="0xB358D862A43E4853">
          <QueryPlan CachedPlanSize="16" CompileTime="7406" CompileCPU="1970" CompileMemory="120">
            <RelOp AvgRowSize="23" EstimateCPU="0.0001581" EstimateIO="0.003125" EstimateRebinds="0" EstimateRewinds="0" EstimateRows="1" LogicalOp="Index Seek" NodeId="0" Parallel="false" PhysicalOp="Index Seek" EstimatedTotalSubtreeCost="0.0032831" TableCardinality="5074270">
                <ColumnReference Database="[smpp]" Schema="[dbo]" Table="[Pdu]" Column="LocalMsgId" />
              <IndexScan Ordered="true" ScanDirection="FORWARD" ForcedIndex="false" ForceSeek="false" NoExpandHint="false">
                    <ColumnReference Database="[smpp]" Schema="[dbo]" Table="[Pdu]" Column="LocalMsgId" />
                <Object Database="[smpp]" Schema="[dbo]" Table="[Pdu]" Index="[IX_Pdu_RemoteMsgId]" IndexKind="NonClustered" />
                      <Prefix ScanType="EQ">
                          <ColumnReference Database="[smpp]" Schema="[dbo]" Table="[Pdu]" Column="RemoteMsgId" />
                          <ScalarOperator ScalarString="[@1]">
                              <ColumnReference Column="@1" />
              <ColumnReference Column="@1" ParameterCompiledValue="'41/00/2789aeb8/1127796335811'" />
        <StmtSimple StatementCompId="2" StatementId="2" StatementText="&#xA;SET STATISTICS IO OFF&#xD;&#xA;" StatementType="SET STATS" />
        <StmtSimple StatementCompId="1" StatementId="1" StatementText="SET STATISTICS TIME OFF&#xD;&#xA;" StatementType="SET STATS" />
  • @Tony: We have tried rebuilding the index, still takes about 0.5 sec to locate a single line for those very similar keys. The index is unique yes.
    – uriDium
    Commented Aug 6, 2012 at 17:24
  • @Mark - The width is varchar(64) We can have up to 7 million rows. We run cleaners on it daily to remove old data. So about 7-10 million on average. I guess the average length of that field is about 20-30.
    – uriDium
    Commented Aug 7, 2012 at 8:14

3 Answers 3


It depends on the queries are you using. MS SQL Server use BTree indexes which are always balanced, but if you use query like this:

select * from table where field like 'some%'

and most of your records correspons to this condition, MS SQL Server can decide that it will be cheaper to use table scan instead of index scan or index lookup.

Addition: Anyway you can use computed columns to reverse your field value and create the index on it.

  • Nope the query is pretty much select * from table where ID = @Id
    – uriDium
    Commented Aug 6, 2012 at 17:23
  • 1
    In this case (unique key) the index selectivety is fine and the server will use it.
    – ceth
    Commented Aug 6, 2012 at 17:28

From the execution plan, there's really not much you can do to that one query -- it's already optimal.

The real question I have is: what is the performance problem?

If even single statements are slow, is the system busy enough that index pages are falling out of cache? Is the maximum memory setting configured correctly? Even with such a wide index field, traversing index pages in memory will still be relatively fast.

If you're just looking at Profiler and seeing lots and lots of these small queries, are we talking about some kind of batch process which happens to do single row SELECTs inside a loop? That is an application issue -- doing singleton lookups instead of set-based operations can bring any system to its knees.


Not generally, however they do tend to fragment quickly. Take a look at this post and see if your indexes are really fragmented. If so it will also explain how you can fix that.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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