Ответ 1

Поиск "ToTime" с помощью агрегатов вместо объединения

Я хотел бы поделиться действительно диким запросом, который занимает только 1 сканирование таблицы с 1 логическим чтением. Для сравнения, лучший другой ответ на странице, запрос Саймона Кингстона, занимает 2 сканирования.

В очень большом наборе данных (17 408 входных строк, производящих 8 193 строки результатов) он принимает CPU 574 и время 2645, тогда как запрос Саймона Кингстона занимает CPU 63 820 и время 37,108.

Возможно, что с индексами другие запросы на странице могли бы работать во много раз лучше, но мне интересно достичь 111-кратного улучшения ЦП и улучшения скорости в 14 раз, просто переписав запрос.

(Пожалуйста, обратите внимание: я не имею в виду никакого неуважения к Саймону Кингстону или кому-либо еще, я просто взволнован тем, что моя идея для этого запроса так хорошо просматривается. Его запрос лучше, чем мой, поскольку его производительность много, и на самом деле это понятным и поддерживаемым, в отличие от моего.)

Вот невозможный запрос. Трудно понять. Трудно было писать. Но это потрясающе.:)

WITH Ranks AS (
   SELECT
      T = Dense_Rank() OVER (ORDER BY Time, Num),
      N = Dense_Rank() OVER (PARTITION BY Name ORDER BY Time, Num),
      *
   FROM
      #Data D
      CROSS JOIN (
         VALUES (1), (2)
      ) X (Num)
), Items AS (
   SELECT
      FromTime = Min(Time),
      ToTime = Max(Time),
      Name = IsNull(Min(CASE WHEN Num = 2 THEN Name END), Min(Name)),
      I = IsNull(Min(CASE WHEN Num = 2 THEN T - N END), Min(T - N)),
      MinNum = Min(Num)
   FROM
      Ranks
   GROUP BY
      T / 2
)
SELECT
   FromTime = Min(FromTime),
   ToTime = CASE WHEN MinNum = 2 THEN NULL ELSE Max(ToTime) END,
   Name
FROM Items
GROUP BY
   I, Name, MinNum
ORDER BY
   FromTime

Примечание. Для этого требуется SQL 2008 или выше. Чтобы он работал в SQL 2005, измените предложение VALUES на SELECT 1 UNION ALL SELECT 2.

Обновленный запрос

Немного подумав об этом, я понял, что одновременно выполняю две отдельные логические задачи, и это сделало запрос излишне сложным: 1) обрезать промежуточные строки, которые не имеют отношения к окончательному решению (строки, которые не начинайте новую задачу) и 2) вытащите значение "ToTime" из следующей строки. Выполняя # 1 перед # 2, запрос проще и работает примерно с половиной процессора!

Итак, вот упрощенный запрос, который сначала вырезает строки, которые нам не нужны, а затем получает значение ToTime, используя агрегаты, а не JOIN. Да, у него есть 3 функции окон, а не 2, но в конечном итоге из-за меньшего количества строк (после обрезки, которые нам не нужны) у него меньше работы:

WITH Ranks AS (
   SELECT
      Grp =
         Row_Number() OVER (ORDER BY Time)
         - Row_Number() OVER (PARTITION BY Name ORDER BY Time),
      [Time], Name
   FROM #Data D
), Ranges AS (
   SELECT
      Result = Row_Number() OVER (ORDER BY Min(R.[Time]), X.Num) / 2,
      [Time] = Min(R.[Time]),
      R.Name, X.Num
   FROM
      Ranks R
      CROSS JOIN (VALUES (1), (2)) X (Num)
   GROUP BY
      R.Name, R.Grp, X.Num
)
SELECT
   FromTime = Min([Time]),
   ToTime = CASE WHEN Count(*) = 1 THEN NULL ELSE Max([Time]) END,
   Name = IsNull(Min(CASE WHEN Num = 2 THEN Name ELSE NULL END), Min(Name))
FROM Ranges R
WHERE Result > 0
GROUP BY Result
ORDER BY FromTime;

Этот обновленный запрос имеет все те же проблемы, что и в моем объяснении, однако их легче решить, потому что я не имею дело с лишними ненужными строками. Я также вижу, что значение Row_Number() / 2 0, которое я должен был исключить, и я не уверен, почему я не исключил его из предыдущего запроса, но в любом случае это работает отлично и удивительно быстро!

Внешнее применение Tidies Things Up

Наконец, вот версия, в основном идентичная запросу Саймона Кингстона, которую я считаю более понятным синтаксисом.

SELECT
   FromTime = Min(D.Time),
   X.ToTime,
   D.Name
FROM
   #Data D
   OUTER APPLY (
      SELECT TOP 1 ToTime = D2.[Time]
      FROM #Data D2
      WHERE
         D.[Time] < D2.[Time]
         AND D.[Name] <> D2.[Name]
      ORDER BY D2.[Time]
   ) X
GROUP BY
   X.ToTime,
   D.Name
ORDER BY
   FromTime;

Здесь настройка script, если вы хотите выполнить сравнение производительности для большего набора данных:

CREATE TABLE #Data (
    RecordId int,
    [Time]  int,
    Name varchar(10)
);
INSERT #Data VALUES
    (1, 10, 'Running'),
    (2, 18, 'Running'),
    (3, 21, 'Running'),
    (4, 29, 'Walking'),
    (5, 33, 'Walking'),
    (6, 57, 'Running'),
    (7, 66, 'Running'),
    (8, 77, 'Running'),
    (9, 81, 'Walking'),
    (10, 89, 'Running'),
    (11, 93, 'Walking'),
    (12, 99, 'Running'),
    (13, 107, 'Running'),
    (14, 113, 'Walking'),
    (15, 124, 'Walking'),
    (16, 155, 'Walking'),
    (17, 178, 'Running');
GO
insert #data select recordid + (select max(recordid) from #data), time + (select max(time) +25 from #data), name from #data
GO 10

Объяснение

Вот основная идея моего запроса.

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

• Тем не менее, мой запрос позволяет сделать вывод времени в двух разных строках, повторяя строку дважды, с CROSS JOIN (VALUES (1), (2)). Теперь у нас все наши строки дублированы. Идея состоит в том, что вместо того, чтобы использовать JOIN для расчета по столбцам, мы будем использовать некоторую форму агрегации, чтобы свернуть каждую желаемую пару строк в один.

• Следующая задача состоит в том, чтобы каждая дублируемая строка правильно раскладывалась таким образом, чтобы один экземпляр шел с предыдущей парой и один со следующей парой. Это выполняется с помощью столбца T, a ROW_NUMBER(), упорядоченного по Time, а затем разделенного на 2 (хотя я изменил его на DENSE_RANK() для симметрии, поскольку в этом случае он возвращает то же значение, что и ROW_NUMBER). Для эффективности я выполнил деление на следующем шаге, чтобы номер строки можно было повторно использовать в другом расчете (продолжать чтение). Поскольку номер строки начинается с 1 и деление на 2 неявно преобразуется в int, это приводит к созданию последовательности 0 1 1 2 2 3 3 4 4 ..., которая имеет желаемый результат: путем группировки по этому рассчитанному значению, так как мы также упорядочивались по Num в номер строки, мы теперь выполнили, что все множества после первого из них состоят из Num = 2 из предыдущей строки и Num = 1 из следующей строки.

• Следующая трудная задача - выяснить способ устранения строк, которые нам не нужны, и как-то свернуть время начала блока в ту же строку, что и время окончания блока. Мы хотим, чтобы каждый дискретный набор Running или Walking получал свой собственный номер, чтобы мы могли его группировать. DENSE_RANK() является естественным решением, но проблема в том, что он обращает внимание на каждое значение в предложении ORDER BY - у нас нет синтаксиса для выполнения DENSE_RANK() OVER (PREORDER BY Time ORDER BY Name), так что Time не вызывает RANK для изменения, за исключением каждого изменения в Name. После некоторого раздумья я понял, что могу немного подкрасться от логики Итцик Бен-Ган сгруппировал решение островов, и я понял, что ранг строки, упорядоченные с помощью Time, вычитаемые из ранга строк, разделенных на Name и упорядоченные по Time, будут давать значение, которое было бы одинаковым для каждой строки в той же группе, но отличалось от других групп. Методом общих групповых островов является создание двух вычисленных значений, которые как поднимаются в lockstep с такими строками, как 4 5 6 и 1 2 3, что при вычитании дает то же значение (в этом примере case 3 3 3 в результате 4 - 1, 5 - 2 и 6 - 3). Примечание. Сначала я начал с ROW_NUMBER() для моего расчета N, но он не работал. Правильный ответ был DENSE_RANK(), хотя мне жаль говорить, что я не помню, почему я это сделал в то время, и мне пришлось бы снова погрузиться, чтобы понять это. Но в любом случае это то, что T-N вычисляет: число, которое можно сгруппировать, чтобы изолировать каждый "остров" одного статуса (либо "бег", либо "ходьба" ).

• Но это еще не конец, потому что есть некоторые морщины. Прежде всего, строка "next" в каждой группе содержит неправильные значения для Name, N и T. Мы обойдем это, выбрав из каждой группы значение из строки Num = 2, когда оно существует (но если это не так, мы используем оставшееся значение). Это дает выражения типа CASE WHEN NUM = 2 THEN x END: это будет правильно отсеивать неверные значения "следующей" строки.

• После некоторых экспериментов я понял, что группы недостаточно для группировки T - N, потому что обе группы Walking и Running группы могут иметь одинаковое рассчитанное значение (в случае предоставленных данных примера до 17, существует два значения T - N 6). Но просто группировка на Name также решает эту проблему. Ни одна из групп "Бег" или "Ходьба" не будет иметь одинаковое количество промежуточных значений из противоположного типа. То есть, поскольку первая группа начинается с "Running", и есть две строки "Walking", предшествующие следующей "Running" группе, тогда значение для N будет на 2 меньше, чем значение для T в следующем "Running". Я просто понял, что один из способов подумать об этом состоит в том, что вычисление T - N подсчитывает количество строк до текущей строки, которые НЕ принадлежат одному и тому же значению "Запуск" или "Прогулка". Некоторые думают, что это верно: если мы перейдем к третьей группе "Запуск", это будет только третья группа благодаря наличию группы "Walking", разделяющей их, поэтому у нее есть другое количество промежуточных строк, входящих в перед ним, и из-за этого, начиная с более высокого положения, он достаточно высок, так что значения не могут быть дублированы.

• Наконец, поскольку наша заключительная группа состоит только из одной строки (нет конечного времени, и нам нужно отобразить NULL вместо этого), мне пришлось сделать расчет, который можно было бы использовать для определения того, время окончания или нет. Это выполняется с помощью выражения Min(Num) и затем, наконец, обнаруживает, что когда Min (Num) было 2 (что означает, что у нас не было "следующей" строки), тогда вместо Max(ToTime) следует отобразить NULL.

Я надеюсь, что это объяснение будет полезным для людей. Я не знаю, будет ли мой метод "умножения строк" ​​вообще полезен и применим к большинству авторов запросов SQL в производственных средах из-за трудностей с его пониманием и сложности обслуживания, которые он, безусловно, будет представлять следующему человеку, посещающему код (реакция, вероятно, "Что, черт возьми, это делает!?!", за которым следует быстрое "Время переписывать!" ).

Если вы сделали это так далеко, я благодарю вас за ваше время и за то, что я потакаю себе в своей маленькой экскурсии в невероятно веселое sql-загадку.

Смотрите это для себя

A.k.a. имитируя "ПРЕДВАРИТЕЛЬНЫЙ ЗАЯВКУ":

Одна последняя заметка. Чтобы увидеть, как T - N выполняет задание, и отмечая, что использование этой части моего метода может вообще не применяться к сообществу SQL, выполните следующий запрос по первым 17 строкам данных примера:

WITH Ranks AS (
   SELECT
      T = Dense_Rank() OVER (ORDER BY Time),
      N = Dense_Rank() OVER (PARTITION BY Name ORDER BY Time),
      *
   FROM
      #Data D
)
SELECT
   *,
   T - N
FROM Ranks
ORDER BY
   [Time];

Это дает:

RecordId    Time Name       T    N    T - N
----------- ---- ---------- ---- ---- -----
1           10   Running    1    1    0
2           18   Running    2    2    0
3           21   Running    3    3    0
4           29   Walking    4    1    3
5           33   Walking    5    2    3
6           57   Running    6    4    2
7           66   Running    7    5    2
8           77   Running    8    6    2
9           81   Walking    9    3    6
10          89   Running    10   7    3
11          93   Walking    11   4    7
12          99   Running    12   8    4
13          107  Running    13   9    4
14          113  Walking    14   5    9
15          124  Walking    15   6    9
16          155  Walking    16   7    9
17          178  Running    17   10   7

Важной частью является то, что каждая группа "Ходьба" или "Бег" имеет то же значение для T - N, которое отличается от любой другой группы с тем же именем.

Производительность

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

Прежде чем запускать каждый запрос, я использовал DBCC FREEPROCCACHE; DBCC DROPCLEANBUFFERS;. Я устанавливаю MAXDOP на 1 для каждого запроса, чтобы удалить эффекты сбрасывания во времени parallelism. Я выбрал каждый набор результатов в переменных вместо того, чтобы возвращать их клиенту, чтобы измерять только производительность, а не передачу данных клиента. Все запросы получили те же предложения ORDER BY. Все тесты использовали 17408 строк ввода, из которых 8 193 строки результатов.

Никакие результаты не отображаются для следующих людей/причин:

RichardTheKiwi *Could not test--query needs updating*
ypercube       *No SQL 2012 environment yet :)*
Tim S          *Did not complete tests within 5 minutes*

Без индекса:

               CPU         Duration    Reads       Writes
               ----------- ----------- ----------- -----------
ErikE          344         344         99          0
Simon Kingston 68672       69582       549203      49

С индексом CREATE UNIQUE CLUSTERED INDEX CI_#Data ON #Data (Time);:

               CPU         Duration    Reads       Writes
               ----------- ----------- ----------- -----------
ErikE          328         336         99          0
Simon Kingston 70391       71291       549203      49          * basically not worse

С индексом CREATE UNIQUE CLUSTERED INDEX CI_#Data ON #Data (Time, Name);:

               CPU         Duration    Reads       Writes
               ----------- ----------- ----------- -----------
ErikE          375         414         359         0           * IO WINNER
Simon Kingston 172         189         38273       0           * CPU WINNER

Итак, мораль этой истории:

Соответствующие индексы более важны, чем волшебство запросов

С соответствующим индексом, версия Саймона Кингстона выигрывает в целом, особенно при включении сложности запросов/ремонтопригодности.

Хорошо укрепите этот урок! Чтение 38 тыс. На самом деле не так много, и версия Саймона Кингстона за полтора раза была моей. Увеличение скорости моего запроса было вызвано тем, что в таблице не было индекса, а сопутствующие катастрофические затраты это дало любому запросу, нуждающемуся в соединении (которого у меня не было): полная проверка таблицы Hash Match, убивающая ее производительность. С индексом его запрос смог выполнить вложенную петлю с кластеризованным поиском индекса (a.k.a. поиск по закладкам), который сделал вещи очень быстрыми.

Интересно, что кластеризованного индекса только по времени недостаточно. Несмотря на то, что Times были уникальными, то есть только одно имя произошло за раз, ему все еще нужно имя, чтобы быть частью индекса, чтобы правильно использовать его.

Добавление кластеризованного индекса в таблицу, когда полные данные заняли менее 1 секунды! Не пренебрегайте указателями.

Ответ 2

Это не будет работать в SQL Server 2008, только в версии SQL Server 2012 с LAG() и LEAD() аналитические функции, но я оставлю его здесь для всех, кто имеет более новые версии:

SELECT Time AS FromTime
     , LEAD(Time) OVER (ORDER BY Time) AS ToTime
     , Name
FROM
  ( SELECT Time 
         , LAG(Name) OVER (ORDER BY Time) AS PreviousName
         , Name
    FROM Data  
  ) AS tmp
WHERE PreviousName <> Name 
   OR PreviousName IS NULL ;

Протестировано в SQL-Fiddle

С индексом (Time, Name) потребуется сканирование индекса.

Изменить:

Если NULL является допустимым значением для Name, которое должно быть принято как допустимая запись, используйте следующее предложение WHERE:

WHERE PreviousName <> Name 
   OR (PreviousName IS NULL AND Name IS NOT NULL)
   OR (PreviousName IS NOT NULL AND Name IS NULL) ;

Ответ 3

Я предполагаю, что RecordID не всегда являются последовательными, поэтому CTE создает неразрывный последовательный номер.

SQLFiddle

;with SequentiallyNumbered as (
    select *, N = row_number() over (order by RecordId)
      from Data)
, Tmp as (
    select A.*, RN=row_number() over (order by A.Time)
      from SequentiallyNumbered A
 left join SequentiallyNumbered B on B.N = A.N-1 and A.name = B.name
     where B.name is null)
   select A.Time FromTime, B.Time ToTime, A.Name
     from Tmp A
left join Tmp B on B.RN = A.RN + 1;

Набор данных, который я использовал для тестирования

create table Data (
    RecordId int,
    Time  int,
    Name varchar(10));
insert Data values
    (1         ,10     ,'Running'),
    (2         ,18     ,'Running'),
    (3         ,21     ,'Running'),
    (4         ,29     ,'Walking'),
    (5         ,33     ,'Walking'),
    (6         ,57     ,'Running'),
    (7         ,66     ,'Running');

Ответ 4

Здесь CTE-решение, которое получает результаты, которые вы ищете:

;WITH TheRecords (FirstTime,SecondTime,[Name])
AS
(
    SELECT [Time],
    (
        SELECT MIN([Time]) 
        FROM ActivityTable at2
        WHERE at2.[Time]>at.[Time]
        AND at2.[Name]<>at.[Name]
    ),
    [Name]
    FROM ActivityTable at
)
SELECT MIN(FirstTime) AS FromTime,SecondTime AS ToTime,MIN([Name]) AS [Name]
FROM TheRecords
GROUP BY SecondTime
ORDER BY FromTime,ToTime

Ответ 5

Я думаю, что вас существенно интересует, где "Имя" изменяется от одной записи к следующей (в порядке "Время" ). Если вы можете определить, где это происходит, вы можете сгенерировать желаемый результат.

Поскольку вы упомянули CTE, я предполагаю, что вы работаете на SQL Server 2005+ и поэтому можете использовать функцию ROW_NUMBER(). Вы можете использовать ROW_NUMBER() как удобный способ для определения последовательных пар записей, а затем для поиска тех, где изменяется "Имя".

Как насчет этого:

WITH OrderedTable AS
(
    SELECT
        *,
        ROW_NUMBER() OVER (ORDER BY Time) AS Ordinal
    FROM
        [YourTable]
),
NameChange AS
(
    SELECT
        after.Time AS Time,
        after.Name AS Name,
        ROW_NUMBER() OVER (ORDER BY after.Time) AS Ordinal
    FROM
        OrderedTable before
        RIGHT JOIN OrderedTable after ON after.Ordinal = before.Ordinal + 1
    WHERE
        ISNULL(before.Name, '') <> after.Name
)

SELECT
    before.Time AS FromTime,
    after.Time AS ToTime,
    before.Name
FROM
    NameChange before
    LEFT JOIN NameChange after ON after.Ordinal = before.Ordinal + 1