Плохая производительность простого запроса на самосоединение

Может ли кто-нибудь посоветовать, как улучшить производительность следующего запроса. Обратите внимание, что проблема, похоже, вызвана пунктом where.

Данные (таблица содержит огромный набор строк - 500К+, набор параметров, с которыми она вызывается, предполагает возврат 2-5К записей на запрос, что сейчас занимает 8-10 минут):

USE [SomeDb]
GO

    SET ANSI_NULLS ON
    GO

    SET QUOTED_IDENTIFIER ON
    GO

    CREATE TABLE [dbo].[Data](
        [x] [money] NOT NULL,
        [y] [money] NOT NULL,
     CONSTRAINT [PK_Data] PRIMARY KEY CLUSTERED 
    (
        [x] ASC
    )WITH (PAD_INDEX = OFF, STATISTICS_NORECOMPUTE = OFF, IGNORE_DUP_KEY = OFF, ALLOW_ROW_LOCKS = ON, ALLOW_PAGE_LOCKS = ON) ON [PRIMARY]
    ) ON [PRIMARY]

    GO

Запрос

select top 10000
s.x as sx,
e.x as ex,
s.y as sy,
e.y as ey,
e.y - s.y as y_delta,
e.x - s.x as x_delta
from Data s 
    inner join Data e
    on e.x > s.x and e.x - s.x between xFrom and xTo
--where e.y - s.y > @yDelta -- when uncommented causes a huge delay

Обновление 1 — План выполнения

<?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.2100.60" xmlns="http://schemas.microsoft.com/sqlserver/2004/07/showplan">
  <BatchSequence>
    <Batch>
      <Statements>
        <StmtSimple StatementCompId="1" StatementEstRows="100" StatementId="1" StatementOptmLevel="FULL" StatementOptmEarlyAbortReason="GoodEnoughPlanFound" StatementSubTreeCost="0.0263655" StatementText="select top 100&#xD;&#xA;s.x as sx,&#xD;&#xA;e.x as ex,&#xD;&#xA;s.y as sy,&#xD;&#xA;e.y as ey,&#xD;&#xA;e.y - s.y as y_delta,&#xD;&#xA;e.x - s.x as x_delta&#xD;&#xA;from Data s &#xD;&#xA;    inner join Data e&#xD;&#xA; on e.x &gt; s.x and e.x - s.x between 100 and 105&#xD;&#xA;where e.y - s.y &gt; 0.01&#xD;&#xA;" StatementType="SELECT" QueryHash="0xAAAC02AC2D78CB56" QueryPlanHash="0x747994153CB2D637" 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="0" NonParallelPlanReason="NoParallelPlansInDesktopOrExpressEdition" CachedPlanSize="24" CompileTime="13" CompileCPU="13" CompileMemory="424">
            <MemoryGrantInfo SerialRequiredMemory="0" SerialDesiredMemory="0" />
            <OptimizerHardwareDependentProperties EstimatedAvailableMemoryGrant="52199" EstimatedPagesCached="14561" EstimatedAvailableDegreeOfParallelism="4" />
            <RelOp AvgRowSize="55" EstimateCPU="1E-05" EstimateIO="0" EstimateRebinds="0" EstimateRewinds="0" EstimatedExecutionMode="Row" EstimateRows="100" LogicalOp="Compute Scalar" NodeId="0" Parallel="false" PhysicalOp="Compute Scalar" EstimatedTotalSubtreeCost="0.0263655">
              <OutputList>
                <ColumnReference Database="[SomeDb]" Schema="[dbo]" Table="[Data]" Alias="[s]" Column="x" />
                <ColumnReference Database="[SomeDb]" Schema="[dbo]" Table="[Data]" Alias="[s]" Column="y" />
                <ColumnReference Database="[SomeDb]" Schema="[dbo]" Table="[Data]" Alias="[e]" Column="x" />
                <ColumnReference Database="[SomeDb]" Schema="[dbo]" Table="[Data]" Alias="[e]" Column="y" />
                <ColumnReference Column="Expr1004" />
                <ColumnReference Column="Expr1005" />
              </OutputList>
              <ComputeScalar>
                <DefinedValues>
                  <DefinedValue>
                    <ColumnReference Column="Expr1004" />
                    <ScalarOperator ScalarString="[SomeDb].[dbo].[Data].[y] as [e].[y]-[SomeDb].[dbo].[Data].[y] as [s].[y]">
                      <Arithmetic Operation="SUB">
                        <ScalarOperator>
                          <Identifier>
                            <ColumnReference Database="[SomeDb]" Schema="[dbo]" Table="[Data]" Alias="[e]" Column="y" />
                          </Identifier>
                        </ScalarOperator>
                        <ScalarOperator>
                          <Identifier>
                            <ColumnReference Database="[SomeDb]" Schema="[dbo]" Table="[Data]" Alias="[s]" Column="y" />
                          </Identifier>
                        </ScalarOperator>
                      </Arithmetic>
                    </ScalarOperator>
                  </DefinedValue>
                  <DefinedValue>
                    <ColumnReference Column="Expr1005" />
                    <ScalarOperator ScalarString="[SomeDb].[dbo].[Data].[x] as [e].[x]-[SomeDb].[dbo].[Data].[x] as [s].[x]">
                      <Arithmetic Operation="SUB">
                        <ScalarOperator>
                          <Identifier>
                            <ColumnReference Database="[SomeDb]" Schema="[dbo]" Table="[Data]" Alias="[e]" Column="x" />
                          </Identifier>
                        </ScalarOperator>
                        <ScalarOperator>
                          <Identifier>
                            <ColumnReference Database="[SomeDb]" Schema="[dbo]" Table="[Data]" Alias="[s]" Column="x" />
                          </Identifier>
                        </ScalarOperator>
                      </Arithmetic>
                    </ScalarOperator>
                  </DefinedValue>
                </DefinedValues>
                <RelOp AvgRowSize="39" EstimateCPU="1E-05" EstimateIO="0" EstimateRebinds="0" EstimateRewinds="0" EstimatedExecutionMode="Row" EstimateRows="100" LogicalOp="Top" NodeId="1" Parallel="false" PhysicalOp="Top" EstimatedTotalSubtreeCost="0.0263555">
                  <OutputList>
                    <ColumnReference Database="[SomeDb]" Schema="[dbo]" Table="[Data]" Alias="[s]" Column="x" />
                    <ColumnReference Database="[SomeDb]" Schema="[dbo]" Table="[Data]" Alias="[s]" Column="y" />
                    <ColumnReference Database="[SomeDb]" Schema="[dbo]" Table="[Data]" Alias="[e]" Column="x" />
                    <ColumnReference Database="[SomeDb]" Schema="[dbo]" Table="[Data]" Alias="[e]" Column="y" />
                  </OutputList>
                  <RunTimeInformation>
                    <RunTimeCountersPerThread Thread="0" ActualRows="100" ActualEndOfScans="1" ActualExecutions="1" />
                  </RunTimeInformation>
                  <Top RowCount="false" IsPercent="false" WithTies="false">
                    <TopExpression>
                      <ScalarOperator ScalarString="(100)">
                        <Const ConstValue="(100)" />
                      </ScalarOperator>
                    </TopExpression>
                    <RelOp AvgRowSize="39" EstimateCPU="151828" EstimateIO="0" EstimateRebinds="0" EstimateRewinds="0" EstimatedExecutionMode="Row" EstimateRows="100" LogicalOp="Inner Join" NodeId="2" Parallel="false" PhysicalOp="Nested Loops" EstimatedTotalSubtreeCost="0.0263455">
                      <OutputList>
                        <ColumnReference Database="[SomeDb]" Schema="[dbo]" Table="[Data]" Alias="[s]" Column="x" />
                        <ColumnReference Database="[SomeDb]" Schema="[dbo]" Table="[Data]" Alias="[s]" Column="y" />
                        <ColumnReference Database="[SomeDb]" Schema="[dbo]" Table="[Data]" Alias="[e]" Column="x" />
                        <ColumnReference Database="[SomeDb]" Schema="[dbo]" Table="[Data]" Alias="[e]" Column="y" />
                      </OutputList>
                      <RunTimeInformation>
                        <RunTimeCountersPerThread Thread="0" ActualRows="100" ActualEndOfScans="0" ActualExecutions="1" />
                      </RunTimeInformation>
                      <NestedLoops Optimized="false">
                        <OuterReferences>
                          <ColumnReference Database="[SomeDb]" Schema="[dbo]" Table="[Data]" Alias="[e]" Column="x" />
                          <ColumnReference Database="[SomeDb]" Schema="[dbo]" Table="[Data]" Alias="[e]" Column="y" />
                        </OuterReferences>
                        <RelOp AvgRowSize="23" EstimateCPU="1.80448" EstimateIO="3.76461" EstimateRebinds="0" EstimateRewinds="0" EstimatedExecutionMode="Row" EstimateRows="1" LogicalOp="Clustered Index Scan" NodeId="3" Parallel="false" PhysicalOp="Clustered Index Scan" EstimatedTotalSubtreeCost="0.0032831" TableCardinality="1640290">
                          <OutputList>
                            <ColumnReference Database="[SomeDb]" Schema="[dbo]" Table="[Data]" Alias="[e]" Column="x" />
                            <ColumnReference Database="[SomeDb]" Schema="[dbo]" Table="[Data]" Alias="[e]" Column="y" />
                          </OutputList>
                          <RunTimeInformation>
                            <RunTimeCountersPerThread Thread="0" ActualRows="15225" ActualEndOfScans="0" ActualExecutions="1" />
                          </RunTimeInformation>
                          <IndexScan Ordered="false" ForcedIndex="false" ForceScan="false" NoExpandHint="false">
                            <DefinedValues>
                              <DefinedValue>
                                <ColumnReference Database="[SomeDb]" Schema="[dbo]" Table="[Data]" Alias="[e]" Column="x" />
                              </DefinedValue>
                              <DefinedValue>
                                <ColumnReference Database="[SomeDb]" Schema="[dbo]" Table="[Data]" Alias="[e]" Column="y" />
                              </DefinedValue>
                            </DefinedValues>
                            <Object Database="[SomeDb]" Schema="[dbo]" Table="[Data]" Index="[PK_Data]" Alias="[e]" IndexKind="Clustered" />
                          </IndexScan>
                        </RelOp>
                        <RelOp AvgRowSize="23" EstimateCPU="0.902317" EstimateIO="1.88387" EstimateRebinds="1" EstimateRewinds="0" EstimatedExecutionMode="Row" EstimateRows="100" LogicalOp="Clustered Index Seek" NodeId="4" Parallel="false" PhysicalOp="Clustered Index Seek" EstimatedTotalSubtreeCost="0.0263655" TableCardinality="1640290">
                          <OutputList>
                            <ColumnReference Database="[SomeDb]" Schema="[dbo]" Table="[Data]" Alias="[s]" Column="x" />
                            <ColumnReference Database="[SomeDb]" Schema="[dbo]" Table="[Data]" Alias="[s]" Column="y" />
                          </OutputList>
                          <RunTimeInformation>
                            <RunTimeCountersPerThread Thread="0" ActualRows="100" ActualEndOfScans="15224" ActualExecutions="15225" />
                          </RunTimeInformation>
                          <IndexScan Ordered="true" ScanDirection="FORWARD" ForcedIndex="false" ForceSeek="false" ForceScan="false" NoExpandHint="false" Storage="RowStore">
                            <DefinedValues>
                              <DefinedValue>
                                <ColumnReference Database="[SomeDb]" Schema="[dbo]" Table="[Data]" Alias="[s]" Column="x" />
                              </DefinedValue>
                              <DefinedValue>
                                <ColumnReference Database="[SomeDb]" Schema="[dbo]" Table="[Data]" Alias="[s]" Column="y" />
                              </DefinedValue>
                            </DefinedValues>
                            <Object Database="[SomeDb]" Schema="[dbo]" Table="[Data]" Index="[PK_Data]" Alias="[s]" IndexKind="Clustered" />
                            <SeekPredicates>
                              <SeekPredicateNew>
                                <SeekKeys>
                                  <EndRange ScanType="LT">
                                    <RangeColumns>
                                      <ColumnReference Database="[SomeDb]" Schema="[dbo]" Table="[Data]" Alias="[s]" Column="x" />
                                    </RangeColumns>
                                    <RangeExpressions>
                                      <ScalarOperator ScalarString="[SomeDb].[dbo].[Data].[x] as [e].[x]">
                                        <Identifier>
                                          <ColumnReference Database="[SomeDb]" Schema="[dbo]" Table="[Data]" Alias="[e]" Column="x" />
                                        </Identifier>
                                      </ScalarOperator>
                                    </RangeExpressions>
                                  </EndRange>
                                </SeekKeys>
                              </SeekPredicateNew>
                            </SeekPredicates>
                            <Predicate>
                              <ScalarOperator ScalarString="([SomeDb].[dbo].[Data].[x] as [e].[x]-[SomeDb].[dbo].[Data].[x] as [s].[x])&gt;=($100.0000) AND ([SomeDb].[dbo].[Data].[x] as [e].[x]-[SomeDb].[dbo].[Data].[x] as [s].[x])&lt;=($105.0000) AND ([SomeDb].[dbo].[Data].[y] as [e].[y]-[SomeDb].[dbo].[Data].[y] as [s].[y])&gt;(0.01)">
                                <Logical Operation="AND">
                                  <ScalarOperator>
                                    <Compare CompareOp="GE">
                                      <ScalarOperator>
                                        <Arithmetic Operation="SUB">
                                          <ScalarOperator>
                                            <Identifier>
                                              <ColumnReference Database="[SomeDb]" Schema="[dbo]" Table="[Data]" Alias="[e]" Column="x" />
                                            </Identifier>
                                          </ScalarOperator>
                                          <ScalarOperator>
                                            <Identifier>
                                              <ColumnReference Database="[SomeDb]" Schema="[dbo]" Table="[Data]" Alias="[s]" Column="x" />
                                            </Identifier>
                                          </ScalarOperator>
                                        </Arithmetic>
                                      </ScalarOperator>
                                      <ScalarOperator>
                                        <Const ConstValue="($100.0000)" />
                                      </ScalarOperator>
                                    </Compare>
                                  </ScalarOperator>
                                  <ScalarOperator>
                                    <Compare CompareOp="LE">
                                      <ScalarOperator>
                                        <Arithmetic Operation="SUB">
                                          <ScalarOperator>
                                            <Identifier>
                                              <ColumnReference Database="[SomeDb]" Schema="[dbo]" Table="[Data]" Alias="[e]" Column="x" />
                                            </Identifier>
                                          </ScalarOperator>
                                          <ScalarOperator>
                                            <Identifier>
                                              <ColumnReference Database="[SomeDb]" Schema="[dbo]" Table="[Data]" Alias="[s]" Column="x" />
                                            </Identifier>
                                          </ScalarOperator>
                                        </Arithmetic>
                                      </ScalarOperator>
                                      <ScalarOperator>
                                        <Const ConstValue="($105.0000)" />
                                      </ScalarOperator>
                                    </Compare>
                                  </ScalarOperator>
                                  <ScalarOperator>
                                    <Compare CompareOp="GT">
                                      <ScalarOperator>
                                        <Arithmetic Operation="SUB">
                                          <ScalarOperator>
                                            <Identifier>
                                              <ColumnReference Database="[SomeDb]" Schema="[dbo]" Table="[Data]" Alias="[e]" Column="y" />
                                            </Identifier>
                                          </ScalarOperator>
                                          <ScalarOperator>
                                            <Identifier>
                                              <ColumnReference Database="[SomeDb]" Schema="[dbo]" Table="[Data]" Alias="[s]" Column="y" />
                                            </Identifier>
                                          </ScalarOperator>
                                        </Arithmetic>
                                      </ScalarOperator>
                                      <ScalarOperator>
                                        <Const ConstValue="(0.01)" />
                                      </ScalarOperator>
                                    </Compare>
                                  </ScalarOperator>
                                </Logical>
                              </ScalarOperator>
                            </Predicate>
                          </IndexScan>
                        </RelOp>
                      </NestedLoops>
                    </RelOp>
                  </Top>
                </RelOp>
              </ComputeScalar>
            </RelOp>
          </QueryPlan>
        </StmtSimple>
      </Statements>
    </Batch>
  </BatchSequence>
</ShowPlanXML>

sql sql-server sql-server-2008 sqlperformance self-join
person user1514042    schedule 11.09.2012    source источник
comment
Что показывает `set showplan on' как план запроса?   -  person mmmmmm    schedule 12.09.2012
comment
@Mark Пожалуйста, найдите прилагаемый план выполнения. Наибольший вклад — 12 % сканирования кластеризованного индекса, 100 % — поиск кластеризованного индекса, где индекс кластера — это данные.   -  person user1514042    schedule 12.09.2012
comment
Ваш запрос довольно странный. Он возвращает 10000 строк без порядка. Тем не менее, ваш вопрос говорит, что он возвращает 2-5k. Можете ли вы объяснить немного больше, что он делает?   -  person Gordon Linoff    schedule 12.09.2012
comment
Что такое xFrom и xTo? ЭТИ переменные? если это так, они должны иметь префикс @.   -  person Paul Grimshaw    schedule 12.09.2012
comment
В основном xFrom и XTo - это переменные, формирующие X-диапазон, вы правы, @ просто опущен. Я измеряю определенные X-диапазоны и проверяю, сколько раз Y превышал определенное значение в этих диапазонах.   -  person user1514042    schedule 12.09.2012

Ответы (3)


arrow_upward
5
arrow_downward

Я часто видел большой прирост производительности, вставляя результаты первого запроса (в вашем случае без предложения where) в таблицу TEMP или табличную переменную и выбирая из этого впоследствии (что в основном помогает оптимизатору запросов выбрать подходящее выполнение план).

Также только что заметил, что у вас нет INDEX в столбце Y, что может немного ускорить.

ИЗМЕНИТЬ Кроме того, попробуйте следующее (это дает мне немного лучшую производительность):

SELECT * FROM 
    (SELECT
        s.x as sx,
        e.x as ex,
        s.y as sy,
        e.y as ey,
        e.y - s.y as y_delta,
        e.x - s.x as x_delta
    FROM Data s 
    JOIN Data e
    ON e.x > s.x 
) data
WHERE data.y_delta > @yDelta AND data.x_delta BETWEEN @xFrom AND @xTo
person Paul Grimshaw    schedule 11.09.2012
comment
Не могли бы вы опубликовать код как часть вашего ответа? В таблице всего два столбца, должно быть довольно просто для тех, кто разбирается в предмете. - person user1514042; 12.09.2012
comment
Пример выложу сегодня позже. Пожалуйста, попробуйте также мой предложенный ИНДЕКС в столбце Y. - person Paul Grimshaw; 12.09.2012
comment
пробовал индексировать y - ничего не изменилось, я тоже возлагал большие надежды на эту идею... Должен ли я что-то сделать, чтобы вписаться в индекс, или он должен улучшить производительность сразу после его создания? - person user1514042; 12.09.2012
comment
Вы увидите разницу сразу после ее создания, так что не похоже, что это поможет. - person Paul Grimshaw; 12.09.2012
comment
Я вижу, что предварительная выборка данных во временную таблицу и применение моего предложения where к временной таблице определенно в 100 раз быстрее, но меня беспокоит масштабируемость решения... есть мысли? - person user1514042; 12.09.2012
comment
Я использовал этот метод для запросов, возвращающих миллионы строк, и не вызвал никаких серьезных проблем. Общее правило, которого я придерживаюсь, заключается в том, что если ваши наборы результатов, вероятно, будут менее 1000 строк, используйте табличную переменную, для больших наборов данных используйте таблицу TEMP. - person Paul Grimshaw; 12.09.2012
comment
Я попытался воспроизвести вашу проблему, но запрос выполняется намного быстрее с предложением where, чем без него. Я получаю 192 720 результатов за 2,8 секунды... - person Paul Grimshaw; 12.09.2012
comment
это, вероятно, связано с данными... Мне нужно подождать 4 минуты, чтобы получить 1000 строк. На самом деле время выполнения сильно зависит от значения, используемого в предложении where - чем ближе к невероятному, тем больше времени требуется для поиска. - person user1514042; 12.09.2012
comment
спасибо за это, результаты самые быстрые из тех, что я видел, все еще немного выше приемлемого уровня. Мысли о кэшировании вызывают у меня депрессию... - person user1514042; 12.09.2012

arrow_upward
1
arrow_downward

Основные проблемы заключаются в том, что предложение where дает перекрестное соединение (не то, что я бы назвал простым соединением) (предоставление множества строк означает, что соединение сравнивает множество строк в e для строки в s), а также сравнение .y должно использовать сканирование таблицы (по крайней мере, по временным данным, если не по всей таблице).

Если запрос является общим, то возможное исправление заключается в выполнении объединения один раз и копировании данных в предварительно рассчитанную таблицу и индексировании различий.

person mmmmmm    schedule 11.09.2012
comment
не могли бы вы опубликовать пример sql, улучшающий производительность? в общем сценарии нет абсолютно никакой закономерности в том, как это называется, индексирование всех возможных вариантов займет вечность. - person user1514042; 12.09.2012

arrow_upward
1
arrow_downward

Я могу придумать странную стратегию для повышения производительности. Это включает в себя добавление автоматически увеличивающегося идентификатора в таблицу, затем поиск границ для Xfrom и Xto с точки зрения идентификатора, а затем поиск чего-либо в диапазоне.

Следующий запрос подсказывает, что я имею в виду:

with e1 as (
    select e.*,
           (select min(id) from data s where e.x between s.x + @xfrom and s.x + @xto) as idstart,
           (select max(id) from data s where e.x between s.x + @xfrom and s.x + @xto) as idend
    from data e
)
select <whatever>
from e1 join
     e1 s
     on e1.idstart = s.id
where e1.idstart <= e1.idend union all
select <whatever>
from e1 join
     e1 s
     on e1.idstart+1 = s.id
where e1.idstart+1 <= e1.idend
. . .

Мне повезло с коррелированным подзапросом в индексированном поле, возвращающим следующее значение. После этого соединения являются эквивалентными соединениями, которые должны быть очень быстрыми. В конце концов, вы захотите изменить запрос, чтобы он мог выполнять сравнения, используя таблицу с перечисляемыми значениями.

person Gordon Linoff    schedule 12.09.2012
comment
это звучит очень интересно. Я не так силен в tsql, не могли бы вы поставить полный sql, чтобы я мог выполнять его в анализаторе sql? - person user1514042; 12.09.2012
comment
Это требует реструктуризации таблицы. Можете ли вы лучше описать, что вы делаете с полученными строками и типом данных, с которыми вы работаете? Могут быть и другие подходы. - person Gordon Linoff; 12.09.2012
comment
это система распознавания образов, используемая для анализа случайных процессов. - person user1514042; 12.09.2012