Имеется таблица [Поставки] с двумя полями [Время] [Количество]
и уникальным индексом [Время]
Запросы типа

select A.Время, sum(B.Количество) as Накопление
from Поставки AS A, Поставки AS B
where A.Время>=B.Время
group by A.Время

или

select A.Время, sum(B.Количество) as Накопление
from       Поставки AS A
inner join Поставки AS B
on         A.Время>=B.Время
group by   A.Время

или

select
  A.Время,
  (
    select sum(B.Количество)
    from   Поставки AS B
    where  A.Время>=B.Время
  ) as Накопление
from Поставки AS A

тормозят безбожно хотя пройтись по таблице из миллиона записей можно быстро

select sum(A.количество)
from  Поставки AS A
where A.Время<>ДатаАпокалипсиса
and   A.количество<>666

Как получить результат за линейное а не квадратичное время?

Здравствуйте, Аноним, Вы писали:

Ну если количество обрабатываемых строк растет квадратично, то с чего время будет линейным?

Линейное время или близкое к нему могли бы дать аналитические функции, если СУБД поддерживает.

Аноним 730 wrote:

> Имеется таблица [Поставки] с двумя полями [Время] [Количество]
> и уникальным индексом [Время]

>
> Как получить результат за линейное а не квадратичное время?

А ты посчитай, возможно ли это вообще.


> Запросы типа
>
> select A.Время, sum(B.Количество) as Накопление
> from Поставки AS A, Поставки AS B
> where A.Время>=B.Время
> group by A.Время
>

O( Na * Nb )
если применяется индекс по полю Время
O( Na * log (Nb) )

(не факт, что индекс будет эффективным,
поскольку в таблице скорее всего для каждого значения времени
половина записей из этой таблицы по времени меньше, и половина -- больше.
Итого -- пол-таблицы на одно значение. Применение индекса не эффективно
А оценить эффективность индекса у современного оптимизатора в таком
случае возможности нет, надо залезть сначала в каждое значение каждой
записи, т.е. выполнять запрос).

> или
>
> select A.Время, sum(B.Количество) as Накопление
> from Поставки AS A
> inner join Поставки AS B
> on A.Время>=B.Время
> group by A.Время

ЭТо один и тот же запрос с предыдущим.

> или
>
> select
> A.Время,
> (
> select sum(B.Количество)
> from Поставки AS B
> where A.Время>=B.Время
> ) as Накопление
> from Поставки AS A
>

O( Na * Nb )
или соответственно с индексом
O( Na * log (Nb) )
Замечания о применении индекса такие же, как и в первом случае.


> тормозят безбожно хотя пройтись по таблице из миллиона записей можно быстро
>
> select sum(A.количество)
> from Поставки AS A
> where A.Время<>ДатаАпокалипсиса
> and A.количество<>666
>

O(Na)


Ну и что ты хочешь ? Пиши правильные запросы.

Совет: при JOIN -е любые операции, кроме = , не применяются.
Семантика таких операций туманна, а практическая полезность
равна нулю (на больших таблицах).