Избыточная сортировка для совокупной монотонной функции

Question

Я разрабатываю запрос к таблице, которая содержит набор точек во временном ряду.Таблица может вырасти довольно большой, и поэтому я хочу, чтобы запрос эффективно уменьшал выходной результат путем усреднения точек за фиксированные временные интервалы.После написания запроса меня удивляет, как SQL Server (2008) решил выполнить запрос.План выполнения выявляет ненужную операцию сортировки, которая становится дорогой по мере роста временного ряда.Вот проблема, сведенная к простому примеру:

CREATE TABLE [dbo].[Example]
(
    [x] FLOAT NOT NULL,
    [y] FLOAT NOT NULL,
    PRIMARY KEY CLUSTERED 
    (
        [x] ASC
    )
);

SELECT FLOOR([x]), AVG([y])
FROM [dbo].[Example]
GROUP BY FLOOR([x]);

Здесь у меня есть (x, y) пары, которые уже отсортированы по x (из-за кластеризованного первичного ключа), и я усредняю ​​yдля каждого целого числа x (путем усечения с помощью функции FLOOR).Я ожидаю, что таблица уже отсортирована по совокупности, поскольку FLOOR является монотонной функцией.К сожалению, SQL Server решает, что эти данные необходимо пересортировать, и вот план выполнения:

Разве SQL Server не должен быть в состоянии выполнить потоковое агрегирование поданные, сгруппированные по монотонной функции столбцов, которые уже надлежащим образом отсортированы?

Существует ли общий способ переписать такие запросы, чтобы SQL Server увидел, что порядок сохранен?

[Обновление] Я нашел статью на эту тему Вещи, которые нужны SQL: проходимость монотонных функций и, как следует из названия, кажется, что это оптимизация, которую SQL Server еще не сделалdo (в большинстве случаев).

Вот еще более простые запросы по сравнению с [dbo].[Example], которые демонстрируют смысл:

SELECT [x], [y]
FROM [dbo].[Example]
ORDER BY FLOOR([x]) --sort performed in execution plan

SELECT [x], [y]
FROM [dbo].[Example]
ORDER BY 2*[x] --NO sort performed in execution plan

SELECT [x], [y]
FROM [dbo].[Example]
ORDER BY 2*[x]+1 --sort performed in execution plan

При любом сложении или умножении оптимизатор запросов понимает, что данныеуже имеет тот же порядок (и это видно, когда вы группируете по таким выражениям тоже).Таким образом, кажется, что концепция монотонных функций понятна оптимизатору, но обычно не применяется.

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

Answer 1

SQL Server почти всегда игнорирует индексы, когда в столбцах индекса есть какая-либо функция.На это есть веские причины:

• Оптимизатор запросов (QO) использует статистику распределения данных.
  Функция меняет это: ожидаете ли вы, что статистика будет генерироваться для запроса ?
• Функция (в данном случае, безусловно) может сделать недействительной уникальность индекса
  QO может использовать уникальность при генерации плана

Некоторые оптимизации закодированы в QO (например: COUNT против EXISTS в IF), но он не дает строгих математических доказательств: они не применяются к времени ответа на запрос

Для некоторых функций datetime существует MS Connect тоже (с чем я на самом деле не согласен, потому что слишком много перестановок функций для оптимизации: поэтому у нас была бы непоследовательность)

В противном случае решение по индексированным вычисляемым столбцам от Алекса Аза - это то, что я бы сделал

Редактировать:

Прочитайте вашу ссылку в обновленном вопросе.

FLOOR изменяется строго монотонно на монотонно.То есть х уникален, поэтому строго монотонен.FLOOR (x) является монотонным.

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

А для примера x * 2 + 1, который вы разместили: atКак вы думаете, в какой момент SQL Server должен прекратить вычислять выражения?Конечно, это оптимизатор, основанный на затратах.

Я думаю, что справедливо, что SQL Server ведет себя так: изо дня в день мой пример оптимизации EXISTS гораздо более полезен.

Answer 2

Некоторые примечания:

• план, который вы видите, когда таблица пуста, и план, когда в таблице есть X строк, могут быть абсолютно разными планами
• Не думаю, что этоправильно иметь первичный ключ на поле Х.Могут ли быть две точки с одинаковыми значениями X?

Я думаю, у вас будет лучшая производительность запросов, если вы сделаете что-то вроде этого:

create table Point
(
    PointId int identity(1, 1)
        constraint PK_Example_Id primary key,
    X float not null,
    Y float not null,
    FloorX as floor(x) persisted
)

create index IX_Point_FloorX_Y on Point(FloorX, Y)

Добавьте несколько строк:

declare @RowCount int = 10000
while(@RowCount > 0)
begin
    insert Point
    values (cast(crypt_gen_random(2) as int), cast(crypt_gen_random(2) as int))
    set @RowCount -= 1
end

Запрос:

select floor(X), avg(Y)
from Point
group by floor(X)

или

select FloorX, avg(Y)
from Point
group by FloorX

у обоих будет один план

План: без сортировки

Еще один вариант - вы можете создать индексированное представление.В этом случае вам придется запрашивать представление напрямую, если только у вас нет Enterprise Edition, который будет использовать индексированные индексы представления, даже если вы запрашиваете таблицу напрямую.

[Edit] Только что понял, что я не сделалпрямо не отвечу на ваш вопрос.Вы спросили, почему SQL выполняет сортировку, если X является кластеризованным первичным ключом.SQL не выполняет сортировку по X, он выполняет сортировку по floor(x).Другими словами, если x уже отсортировано, то f(x) не обязательно будет иметь тот же порядок, верно?

Answer 3

Это очень хороший вопрос.В таких случаях мы хотим иметь другую таблицу и использовать CROSS APPLY, как в следующем примере, в котором используются таблицы Numbers, в которых хранятся все числа от Min (X) / YourStepInMinutes AND Max (x) / YourStepInMinutes и еще два числа вокруг Min иМаксимум.Этот запрос выполняется как вложенные циклы, не нуждается в сортировке:

SELECT n.n, Avg(p.y)
FROM dbo.Numbers AS n
CROSS APPLY (SELECT p.y 
  FROM dbo.Points AS p 
  WHERE p.x<n*YourStepInMinutes AND (n-1)*YourStepInMinutes<=p.x
) As p

Редактировать: хотя для этого решения требуется несвободное соединение, я бы не стал делать общий оператор, который всегда медленный.Сортировка большого количества данных может внезапно стать очень медленной - вы сортируете на 10% больше строк, а ваша сортировка может быть в 10 раз медленнее.С другой стороны, этот подход лучше масштабируется, потому что он не требует одного большого огромного вида.

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