Блог

Я ищу эффективный способ извлечения ДВУХ верхних строк для каждой группы данных в SQL. У меня есть очень большая таблица данных (около 10 миллиардов строк). Каждая строка данных описывается четырьмя измерениями (которые составляют первичный ключ), а таблица разбита на разделы по одному из измерений (последний столбец первичного ключа).

 -- Medium table (2 to 3 million rows)
CREATE TABLE [smallDatabase].[dbo].[dimTableA] (
    [colA] [int] NOT NULL PRIMARY KEY
    ,[valueA] [int]
);

-- Small table (<1000 rows)
CREATE TABLE [smallDatabase].[dbo].[dimTableB] (
    [colB] [int] NOT NULL PRIMARY KEY
    ,[valueB] [int]
);

-- Small table (<10000 rows)
CREATE TABLE [smallDatabase].[dbo].[dimTableC] (
    [colC] [int] NOT NULL PRIMARY KEY
    ,[valueC] [int]
);

-- Small table (100 to 200 rows)
CREATE TABLE [smallDatabase].[dbo].[dimTableD] (
    [colD] [int] NOT NULL PRIMARY KEY
    ,[grouperD] [int] NOT NULL
    ,[dateD] [date]
);

CREATE PARTITION FUNCTION [pfColD](int) AS RANGE RIGHT FOR VALUES (1, 2, 3, ..., n);
CREATE PARTITION SCHEME [psColD] AS PARTITION [pfColD] TO ([PRIMARY], [PRIMARY], [PRIMARY], ..., [PRIMARY]);

-- Large table (~10 billion rows)
CREATE TABLE [bigDatabase].[dbo].[factBigTable] (
    [colA] [int] NOT NULL
    ,[colB] [int] NOT NULL
    ,[colC] [int] NOT NULL
    ,[colD] [int] NOT NULL
    ,[datum] [float] NULL
    ,PRIMARY KEY (
        [colA] ASC
        ,[colB] ASC
        ,[colC] ASC
        ,[colD] ASC
    )
) ON psColD([colD]);
  

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

 CREATE TABLE #filter (
    [colA] [int] NOT NULL
    ,[colB] [int] NOT NULL
    ,PRIMARY KEY (
        [colA] ASC
        ,[colB] ASC
    )
);
  

Я нашел несколько других решений в Интернете, которые предлагают использовать номер строки для выбора двух верхних строк, например:

 -- Get the most recent two data points for each group of data
SELECT *
FROM (
    SELECT big.*
        ,dimD.[grouperD]
        ,ROW_NUMBER() OVER (
            PARTITION BY dimD.[grouperD], big.[colA], big.[colB], big.[colC]
            ORDER BY dimD.[dateD] DESC
        ) AS rowNumber
    FROM [bigDatabase].[dbo].[factBigTable] AS big
    INNER JOIN [smallDatabase].[dbo].[dimTableD] AS dimD
        ON big.[colD] = dimD.[colD]
    INNER JOIN #filter
        ON big.[colA] = #filter.[colA]
            AND big.[colB] = #filter.[colB]
) AS bigDataRanked
WHERE rowNumber <= 2;
  

Это действительно дает мне точные данные, которые я ищу; однако, это очень медленно!

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

Один алгоритм, который я попробовал, отлично выглядел на бумаге, но в конечном итоге выполнялся очень медленно из-за разреженного характера данных. Идея заключалась в:

1. Кэшируйте список каждой группы. Т.е. [grouperD], [colA], [ColB] и [ColC]. Следите за строками, найденными для каждой группы.
2. Наведите курсор на [Холодный], упорядоченный по [Датированный]. Остановитесь, когда в каждой группе будет найдено по 2 строки.
3. Выберите строки из [factBigTable], которые соответствуют группам, в которых найдено строк меньше 2. Кэшируйте результаты.
4. Для кэшированных результатов увеличьте количество найденных строк.
5. Переместите кэшированные результаты в промежуточную таблицу для последующего использования.
6. Переходим к следующему [холодному] циклу.

Каждый цикл выполняется относительно быстро, поскольку SQL способен использовать PK seeks для большинства запросов. Однако у некоторых из моих групп был очень низкий max [colD], поэтому цикл приходилось повторять много раз.

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

1. Для подмножества данных, о которых мы заботимся (т.Е. для присоединения к фильтру), кэшируйте все первичные ключи для каждой группы.
2. Выберите и кэшируйте максимальное значение [colD] для каждой группы.
3. Удалите максимальное значение из списка PK по группе.
4. Снова выберите и кэшируйте максимальное значение [colD] для каждой группы. Чтобы получить вторую по максимуму [холодную].
5. Используйте кэшированные ключи max и second to max для поиска всех необходимых нам строк.

Есть ли у кого-нибудь другие идеи о том, как быстро получить строки, которые я ищу?Это ни в коем случае не должно выполняться в одном запросе. Я согласен с таким количеством промежуточных или временных таблиц, какое необходимо для быстрого получения данных. Кроме того, я открыт для добавления индексов или других изменений модели данных. Я бы предпочел этого не делать — просто потому, что таблица такая большая, любое изменение, вероятно, повлечет за собой значительные проблемы с хранением — но, если это единственный способ, тогда я заставлю его работать.

не могу прокомментировать, недостаточно большой, но любопытно, о какой версии sql server мы говорим?

Я сомневаюсь, что это будет быстрее (особенно, если мы говорим о миллиардах строк до RowNumber <= 2), но я бы всегда предпочел разгрузить операцию row_number() до меньшего подмножества, если это возможно.

 ;with bigDataRanked as (
SELECT big.*
        ,dimD.[grouperD]
        ,dimD.[dateD]
    FROM [bigDatabase].[dbo].[factBigTable] AS big
    INNER JOIN [smallDatabase].[dbo].[dimTableD] AS dimD
        ON big.[colD] = dimD.[colD]
    INNER JOIN #filter
        ON big.[colA] = #filter.[colA]
            AND big.[colB] = #filter.[colB]
) 
select bdr.*, ROW_NUMBER() OVER (
            PARTITION BY bdr.[grouperD], bdr.[colA], bdr.[colB], bdr.[colC]
            ORDER BY bdr.[dateD] DESC) rowNumber
from bigDataRanked bdr -- will have an additional column dateD returned from dimTableD (from bdr.*)
where rowNumber <= 2;