SQL Server query fast in first run, then extremely slow with other production data

Question

I have a query which takes minutes to return. It's fine once it's loaded into RAM, but the general performance is terrible when I change the parameters beyond what is in the cache. There are approximately 1m rows in thing and 200k rows in location. Both tables have indexes and keys. Apart, the two queries (from thing and locations) return in <1 second, but when I do the join (which is on a FK) it takes upwards of a minute.

Query:

SELECT tip.id
    ,tip.NAME
    ,tip.location
    ,tip.time_start
    ,tip.time_end
    ,tip.is_meetup
    ,tip.utc_offset
    ,tip.type
    ,locations.NAME AS location_name
    ,locations.lat
    ,locations.long
FROM locations
INNER JOIN thing ON locations.id = thing.location
WHERE latitude BETWEEN 37.631281363768117
        AND 37.921136436231883
    AND longitude BETWEEN - 122.60055304642543
        AND - 122.23383795357458
    AND startTime BETWEEN 1373869967
        AND 1389869967

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="11.0.3393.0" xmlns="http://schemas.microsoft.com/sqlserver/2004/07/showplan">
  <BatchSequence>
    <Batch>
      <Statements>
        <StmtSimple StatementCompId="1" StatementEstRows="268.558" StatementId="1" StatementOptmLevel="FULL" StatementSubTreeCost="2.04298" StatementText="SELECT t.id, t.name, t.location, t.time_start, t.time_end, t.is_meetup, t.utc_offset, t.type,&#xD;&#xA;locations.name AS location_name,&#xD;&#xA;locations.latitude AS latitude, locations.longitude AS longitude&#xD;&#xA;FROM locations &#xD;&#xA;INNER JOIN Thing AS t&#xD;&#xA;ON locations.id = t.location &#xD;&#xA;WHERE latitude BETWEEN 32.631281363768117 AND 33.921136436231883&#xD;&#xA;AND longitude BETWEEN -118.60055304642543 AND -116.23383795357458&#xD;&#xA;AND time_start BETWEEN 1390869967 AND 1391869967&#xD;&#xA;" StatementType="SELECT" QueryHash="0x545542B8298CBC85" QueryPlanHash="0xA2BF90229E96DA92" 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="1" CachedPlanSize="40" CompileTime="11" CompileCPU="11" CompileMemory="464">
            <MemoryGrantInfo SerialRequiredMemory="0" SerialDesiredMemory="0" />
            <OptimizerHardwareDependentProperties EstimatedAvailableMemoryGrant="524288" EstimatedPagesCached="131072" EstimatedAvailableDegreeOfParallelism="2" />
            <RelOp AvgRowSize="4342" EstimateCPU="0.00243192" EstimateIO="0" EstimateRebinds="0" EstimateRewinds="0" EstimatedExecutionMode="Row" EstimateRows="268.558" LogicalOp="Inner Join" NodeId="0" Parallel="false" PhysicalOp="Nested Loops" EstimatedTotalSubtreeCost="2.04298">
              <OutputList>
                <ColumnReference Database="[ThingDB]" Schema="[dbo]" Table="[locations]" Column="name" />
                <ColumnReference Database="[ThingDB]" Schema="[dbo]" Table="[locations]" Column="latitude" />
                <ColumnReference Database="[ThingDB]" Schema="[dbo]" Table="[locations]" Column="longitude" />
                <ColumnReference Database="[ThingDB]" Schema="[dbo]" Table="[Thing]" Alias="[t]" Column="id" />
                <ColumnReference Database="[ThingDB]" Schema="[dbo]" Table="[Thing]" Alias="[t]" Column="name" />
                <ColumnReference Database="[ThingDB]" Schema="[dbo]" Table="[Thing]" Alias="[t]" Column="location" />
                <ColumnReference Database="[ThingDB]" Schema="[dbo]" Table="[Thing]" Alias="[t]" Column="time_start" />
                <ColumnReference Database="[ThingDB]" Schema="[dbo]" Table="[Thing]" Alias="[t]" Column="time_end" />
                <ColumnReference Database="[ThingDB]" Schema="[dbo]" Table="[Thing]" Alias="[t]" Column="is_meetup" />
                <ColumnReference Database="[ThingDB]" Schema="[dbo]" Table="[Thing]" Alias="[t]" Column="utc_offset" />
                <ColumnReference Database="[ThingDB]" Schema="[dbo]" Table="[Thing]" Alias="[t]" Column="type" />
              </OutputList>
              <RunTimeInformation>
                <RunTimeCountersPerThread Thread="0" ActualRows="12" ActualEndOfScans="1" ActualExecutions="1" />
              </RunTimeInformation>
              <NestedLoops Optimized="false" WithUnorderedPrefetch="true">
                <OuterReferences>
                  <ColumnReference Database="[ThingDB]" Schema="[dbo]" Table="[locations]" Column="id" />
                  <ColumnReference Column="Expr1005" />
                </OuterReferences>
                <RelOp AvgRowSize="4059" EstimateCPU="0.016229" EstimateIO="0.10831" EstimateRebinds="0" EstimateRewinds="0" EstimatedExecutionMode="Row" EstimateRows="581.799" LogicalOp="Index Seek" NodeId="2" Parallel="false" PhysicalOp="Index Seek" EstimatedTotalSubtreeCost="0.124539" TableCardinality="255461">
                  <OutputList>
                    <ColumnReference Database="[ThingDB]" Schema="[dbo]" Table="[locations]" Column="name" />
                    <ColumnReference Database="[ThingDB]" Schema="[dbo]" Table="[locations]" Column="latitude" />
                    <ColumnReference Database="[ThingDB]" Schema="[dbo]" Table="[locations]" Column="longitude" />
                    <ColumnReference Database="[ThingDB]" Schema="[dbo]" Table="[locations]" Column="id" />
                  </OutputList>
                  <RunTimeInformation>
                    <RunTimeCountersPerThread Thread="0" ActualRows="5487" ActualEndOfScans="1" ActualExecutions="1" />
                  </RunTimeInformation>
                  <IndexScan Ordered="true" ScanDirection="FORWARD" ForcedIndex="false" ForceSeek="false" ForceScan="false" NoExpandHint="false" Storage="RowStore">
                    <DefinedValues>
                      <DefinedValue>
                        <ColumnReference Database="[ThingDB]" Schema="[dbo]" Table="[locations]" Column="name" />
                      </DefinedValue>
                      <DefinedValue>
                        <ColumnReference Database="[ThingDB]" Schema="[dbo]" Table="[locations]" Column="latitude" />
                      </DefinedValue>
                      <DefinedValue>
                        <ColumnReference Database="[ThingDB]" Schema="[dbo]" Table="[locations]" Column="longitude" />
                      </DefinedValue>
                      <DefinedValue>
                        <ColumnReference Database="[ThingDB]" Schema="[dbo]" Table="[locations]" Column="id" />
                      </DefinedValue>
                    </DefinedValues>
                    <Object Database="[ThingDB]" Schema="[dbo]" Table="[locations]" Index="[IX_locations]" IndexKind="NonClustered" />
                    <SeekPredicates>
                      <SeekPredicateNew>
                        <SeekKeys>
                          <StartRange ScanType="GE">
                            <RangeColumns>
                              <ColumnReference Database="[ThingDB]" Schema="[dbo]" Table="[locations]" Column="latitude" />
                              <ColumnReference Database="[ThingDB]" Schema="[dbo]" Table="[locations]" Column="longitude" />
                            </RangeColumns>
                            <RangeExpressions>
                              <ScalarOperator ScalarString="(3.263128136376812e+001)">
                                <Const ConstValue="(3.263128136376812e+001)" />
                              </ScalarOperator>
                              <ScalarOperator ScalarString="(-1.186005530464255e+002)">
                                <Const ConstValue="(-1.186005530464255e+002)" />
                              </ScalarOperator>
                            </RangeExpressions>
                          </StartRange>
                          <EndRange ScanType="LE">
                            <RangeColumns>
                              <ColumnReference Database="[ThingDB]" Schema="[dbo]" Table="[locations]" Column="latitude" />
                              <ColumnReference Database="[ThingDB]" Schema="[dbo]" Table="[locations]" Column="longitude" />
                            </RangeColumns>
                            <RangeExpressions>
                              <ScalarOperator ScalarString="(3.392113643623188e+001)">
                                <Const ConstValue="(3.392113643623188e+001)" />
                              </ScalarOperator>
                              <ScalarOperator ScalarString="(-1.162338379535746e+002)">
                                <Const ConstValue="(-1.162338379535746e+002)" />
                              </ScalarOperator>
                            </RangeExpressions>
                          </EndRange>
                        </SeekKeys>
                      </SeekPredicateNew>
                    </SeekPredicates>
                    <Predicate>
                      <ScalarOperator ScalarString="[ThingDB].[dbo].[locations].[longitude]&gt;=(-1.186005530464255e+002) AND [ThingDB].[dbo].[locations].[longitude]&lt;=(-1.162338379535746e+002)">
                        <Logical Operation="AND">
                          <ScalarOperator>
                            <Compare CompareOp="GE">
                              <ScalarOperator>
                                <Identifier>
                                  <ColumnReference Database="[ThingDB]" Schema="[dbo]" Table="[locations]" Column="longitude" />
                                </Identifier>
                              </ScalarOperator>
                              <ScalarOperator>
                                <Const ConstValue="(-1.186005530464255e+002)" />
                              </ScalarOperator>
                            </Compare>
                          </ScalarOperator>
                          <ScalarOperator>
                            <Compare CompareOp="LE">
                              <ScalarOperator>
                                <Identifier>
                                  <ColumnReference Database="[ThingDB]" Schema="[dbo]" Table="[locations]" Column="longitude" />
                                </Identifier>
                              </ScalarOperator>
                              <ScalarOperator>
                                <Const ConstValue="(-1.162338379535746e+002)" />
                              </ScalarOperator>
                            </Compare>
                          </ScalarOperator>
                        </Logical>
                      </ScalarOperator>
                    </Predicate>
                  </IndexScan>
                </RelOp>
                <RelOp AvgRowSize="299" EstimateCPU="0.0001581" EstimateIO="0.003125" EstimateRebinds="580.799" EstimateRewinds="0" EstimatedExecutionMode="Row" EstimateRows="1" LogicalOp="Index Seek" NodeId="3" Parallel="false" PhysicalOp="Index Seek" EstimatedTotalSubtreeCost="1.90315" TableCardinality="767469">
                  <OutputList>
                    <ColumnReference Database="[ThingDB]" Schema="[dbo]" Table="[Thing]" Alias="[t]" Column="id" />
                    <ColumnReference Database="[ThingDB]" Schema="[dbo]" Table="[Thing]" Alias="[t]" Column="name" />
                    <ColumnReference Database="[ThingDB]" Schema="[dbo]" Table="[Thing]" Alias="[t]" Column="location" />
                    <ColumnReference Database="[ThingDB]" Schema="[dbo]" Table="[Thing]" Alias="[t]" Column="time_start" />
                    <ColumnReference Database="[ThingDB]" Schema="[dbo]" Table="[Thing]" Alias="[t]" Column="time_end" />
                    <ColumnReference Database="[ThingDB]" Schema="[dbo]" Table="[Thing]" Alias="[t]" Column="is_meetup" />
                    <ColumnReference Database="[ThingDB]" Schema="[dbo]" Table="[Thing]" Alias="[t]" Column="utc_offset" />
                    <ColumnReference Database="[ThingDB]" Schema="[dbo]" Table="[Thing]" Alias="[t]" Column="type" />
                  </OutputList>
                  <RunTimeInformation>
                    <RunTimeCountersPerThread Thread="0" ActualRows="12" ActualEndOfScans="5487" ActualExecutions="5487" />
                  </RunTimeInformation>
                  <IndexScan Ordered="true" ScanDirection="FORWARD" ForcedIndex="false" ForceSeek="false" ForceScan="false" NoExpandHint="false" Storage="RowStore">
                    <DefinedValues>
                      <DefinedValue>
                        <ColumnReference Database="[ThingDB]" Schema="[dbo]" Table="[Thing]" Alias="[t]" Column="id" />
                      </DefinedValue>
                      <DefinedValue>
                        <ColumnReference Database="[ThingDB]" Schema="[dbo]" Table="[Thing]" Alias="[t]" Column="name" />
                      </DefinedValue>
                      <DefinedValue>
                        <ColumnReference Database="[ThingDB]" Schema="[dbo]" Table="[Thing]" Alias="[t]" Column="location" />
                      </DefinedValue>
                      <DefinedValue>
                        <ColumnReference Database="[ThingDB]" Schema="[dbo]" Table="[Thing]" Alias="[t]" Column="time_start" />
                      </DefinedValue>
                      <DefinedValue>
                        <ColumnReference Database="[ThingDB]" Schema="[dbo]" Table="[Thing]" Alias="[t]" Column="time_end" />
                      </DefinedValue>
                      <DefinedValue>
                        <ColumnReference Database="[ThingDB]" Schema="[dbo]" Table="[Thing]" Alias="[t]" Column="is_meetup" />
                      </DefinedValue>
                      <DefinedValue>
                        <ColumnReference Database="[ThingDB]" Schema="[dbo]" Table="[Thing]" Alias="[t]" Column="utc_offset" />
                      </DefinedValue>
                      <DefinedValue>
                        <ColumnReference Database="[ThingDB]" Schema="[dbo]" Table="[Thing]" Alias="[t]" Column="type" />
                      </DefinedValue>
                    </DefinedValues>
                    <Object Database="[ThingDB]" Schema="[dbo]" Table="[Thing]" Index="[IX_Thing]" Alias="[t]" IndexKind="NonClustered" />
                    <SeekPredicates>
                      <SeekPredicateNew>
                        <SeekKeys>
                          <Prefix ScanType="EQ">
                            <RangeColumns>
                              <ColumnReference Database="[ThingDB]" Schema="[dbo]" Table="[Thing]" Alias="[t]" Column="location" />
                            </RangeColumns>
                            <RangeExpressions>
                              <ScalarOperator ScalarString="[ThingDB].[dbo].[locations].[id]">
                                <Identifier>
                                  <ColumnReference Database="[ThingDB]" Schema="[dbo]" Table="[locations]" Column="id" />
                                </Identifier>
                              </ScalarOperator>
                            </RangeExpressions>
                          </Prefix>
                          <StartRange ScanType="GE">
                            <RangeColumns>
                              <ColumnReference Database="[ThingDB]" Schema="[dbo]" Table="[Thing]" Alias="[t]" Column="time_start" />
                            </RangeColumns>
                            <RangeExpressions>
                              <ScalarOperator ScalarString="(1390869967)">
                                <Const ConstValue="(1390869967)" />
                              </ScalarOperator>
                            </RangeExpressions>
                          </StartRange>
                          <EndRange ScanType="LE">
                            <RangeColumns>
                              <ColumnReference Database="[ThingDB]" Schema="[dbo]" Table="[Thing]" Alias="[t]" Column="time_start" />
                            </RangeColumns>
                            <RangeExpressions>
                              <ScalarOperator ScalarString="(1391869967)">
                                <Const ConstValue="(1391869967)" />
                              </ScalarOperator>
                            </RangeExpressions>
                          </EndRange>
                        </SeekKeys>
                      </SeekPredicateNew>
                    </SeekPredicates>
                  </IndexScan>
                </RelOp>
              </NestedLoops>
            </RelOp>
          </QueryPlan>
        </StmtSimple>
      </Statements>
    </Batch>
  </BatchSequence>
</ShowPlanXML>

Answer 1

There is about tenfold difference between actual and estimated number of rows coming from Index Seek operator on IX_locations index. It could be that the stats are stale, or that the distribution of data is skewed. But it's just part of the problem.

It would be interesting to know a bit more about Thing table. Taking into account that when you query Things table separately, filtering on startTime column, it returns in sub-second, my guess is that startTime is much more selective and also that this query uses some index on startTime column.

Try selecting from Things into a #temp table and join this to Locations.

Also, select from Locations into #temp table and join Things. Check the execution plan, what's the operator on Things table? If it's seek again, then my recommendation is to select from both Things and Locations into #temp tables first and then join them.