Эффективно найти топ-N значений из нескольких столбцов независимо в Oracle

Question

Предположим, у меня 30 миллиардов строк с несколькими столбцами, и я хочу эффективно найти N наиболее часто встречающихся значений для каждого столбца независимо и с максимально элегантным SQL-запросом.Например, если у меня есть

FirstName LastName FavoriteAnimal FavoriteBook
--------- -------- -------------- ------------
Ferris    Freemont Possum         Ubik
Nancy     Freemont Lemur          Housekeeping
Nancy     Drew     Penguin        Ubik
Bill      Ribbits  Lemur          Dhalgren

и я хочу топ-1, то результатом будет:

FirstName LastName FavoriteAnimal FavoriteBook
--------- -------- -------------- ------------
Nancy     Freemont Lemur          Ubik

Я, вероятно, могу придумать способы сделать это, но неуверен, что они оптимальны, что важно, когда 30 миллиардов строк;и SQL может быть большим и некрасивым, и, возможно, будет использовано слишком много временного пространства.

Использование Oracle.

Answer 1

Это должно сделать только один проход по столу. Вы можете использовать аналитическую версию count(), чтобы получить частоту каждого значения независимо:

select firstname, count(*) over (partition by firstname) as c_fn,
    lastname, count(*) over (partition by lastname) as c_ln,
    favoriteanimal, count(*) over (partition by favoriteanimal) as c_fa,
    favoritebook, count(*) over (partition by favoritebook) as c_fb
from my_table;

FIRSTN C_FN LASTNAME C_LN FAVORIT C_FA FAVORITEBOOK C_FB
------ ---- -------- ---- ------- ---- ------------ ----
Bill      1 Ribbits     1 Lemur      2 Dhalgren        1
Ferris    1 Freemont    2 Possum     1 Ubik            2
Nancy     2 Freemont    2 Lemur      2 Housekeeping    1
Nancy     2 Drew        1 Penguin    1 Ubik            2

Затем вы можете использовать это как CTE (или, как я полагаю, в терминологии оракула) как факторинг подзапроса, и извлекать только значение самой высокой частоты из каждого столбца:

with tmp_tab as (
    select /*+ MATERIALIZE */
        firstname, count(*) over (partition by firstname) as c_fn,
        lastname, count(*) over (partition by lastname) as c_ln,
        favoriteanimal, count(*) over (partition by favoriteanimal) as c_fa,
        favoritebook, count(*) over (partition by favoritebook) as c_fb
    from my_table)
select (select firstname from (
        select firstname,
            row_number() over (partition by null order by c_fn desc) as r_fn
            from tmp_tab
        ) where r_fn = 1) as firstname,
    (select lastname from (
        select lastname,
            row_number() over (partition by null order by c_ln desc) as r_ln
        from tmp_tab
        ) where r_ln = 1) as lastname,
    (select favoriteanimal from (
        select favoriteanimal,
            row_number() over (partition by null order by c_fa desc) as r_fa
        from tmp_tab
        ) where r_fa = 1) as favoriteanimal,
    (select favoritebook from (
        select favoritebook,
            row_number() over (partition by null order by c_fb desc) as r_fb
        from tmp_tab
        ) where r_fb = 1) as favoritebook
from dual;

FIRSTN LASTNAME FAVORIT FAVORITEBOOK
------ -------- ------- ------------
Nancy  Freemont Lemur   Ubik

Вы делаете один проход через CTE для каждого столбца, но это все равно должно попасть в реальную таблицу только один раз (благодаря подсказке materialize). И вы можете захотеть добавить к пунктам order by, чтобы настроить, что делать, если есть связи.

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

Редактировать: Хм, объясните план показывает, что он делает четыре полных сканирования таблицы; возможно, нужно подумать об этом немного больше ... Редактировать 2: Добавление (недокументированного) MATERIALIZE подсказки к CTE, кажется, решает эту проблему; он создает временную временную таблицу для хранения результатов и выполняет только одно полное сканирование таблицы. Стоимость плана объяснения выше, хотя бы - по крайней мере, для этого набора данных времени. Заинтересуйтесь любыми комментариями по поводу любых недостатков в этом.

Answer 2

Лучшее, что я когда-либо придумал с чистым Oracle SQL, это что-то похожее на то, что делал @AlexPoole.Я использую счет (A), а не счет (*), чтобы подтолкнуть нули к низу.

with 
NUM_ROWS_RETURNED as (
    select 4 as NUM from dual
),
SAMPLE_DATA as (
    select /*+ materialize */ 
        A,B,C,D,E
    from (
                  select 1 as A, 1 as B, 4 as C, 1 as D, 4 as E from dual
        union all select 1     , -2    , 3     , 2     , 3      from dual
        union all select 1     , -2    , 2     , 2     , 3      from dual
        union all select null  , 1     , 1     , 3     , 2      from dual
        union all select null  , 2     , 4     , null  , 2      from dual
        union all select null  , 1     , 3     , null  , 2      from dual
        union all select null  , 1     , 2     , null  , 1      from dual
        union all select null  , 1     , 4     , null  , 1      from dual
        union all select null  , 1     , 3     , 3     , 1      from dual
        union all select null  , 1     , 4     , 3     , 1      from dual
    )
),
RANKS as (
    select /*+ materialize */ 
        rownum as RANKED 
    from 
        SAMPLE_DATA 
    where 
        rownum <= (select min(NUM) from NUM_ROWS_RETURNED)
)
select
    r.RANKED,
    max(case when A_RANK = r.RANKED then A else null end) as A,
    max(case when B_RANK = r.RANKED then B else null end) as B,
    max(case when C_RANK = r.RANKED then C else null end) as C,
    max(case when D_RANK = r.RANKED then D else null end) as D,
    max(case when E_RANK = r.RANKED then E else null end) as E
from (
    select 
        A,  dense_rank() over (order by A_COUNTS desc) as A_RANK,
        B,  dense_rank() over (order by B_COUNTS desc) as B_RANK,
        C,  dense_rank() over (order by C_COUNTS desc) as C_RANK,
        D,  dense_rank() over (order by D_COUNTS desc) as D_RANK,
        E,  dense_rank() over (order by E_COUNTS desc) as E_RANK
    from (
        select 
            A,  count(A) over (partition by A) as A_COUNTS,
            B,  count(B) over (partition by B) as B_COUNTS,
            C,  count(C) over (partition by C) as C_COUNTS,
            D,  count(D) over (partition by D) as D_COUNTS,
            E,  count(E) over (partition by E) as E_COUNTS
        from
            SAMPLE_DATA
    )
)
cross join 
    RANKS r
group by
    r.RANKED
order by
    r.RANKED
/

дает:

RANKED|   A|   B|   C|   D|   E
------|----|----|----|----|----
     1|   1|   1|   4|   3|   1
     2|null|  -2|   3|   2|   2
     3|null|   2|   2|   1|   3
     4|null|null|   1|null|   4

с планом:

--------------------------------------------------------------------------------------------------
| Id  | Operation                         | Name         | Rows  | Bytes | Cost (%CPU)| Time     |
--------------------------------------------------------------------------------------------------
|   0 | SELECT STATEMENT                  |              |     1 |    93 |    57  (20)| 00:00:01 |
|   1 |  TEMP TABLE TRANSFORMATION        |              |       |       |            |          |
|   2 |   LOAD AS SELECT                  |              |       |       |            |          |
|   3 |    VIEW                           |              |    10 |   150 |    20   (0)| 00:00:01 |
|   4 |     UNION-ALL                     |              |       |       |            |          |
|   5 |      FAST DUAL                    |              |     1 |       |     2   (0)| 00:00:01 |
|   6 |      FAST DUAL                    |              |     1 |       |     2   (0)| 00:00:01 |
|   7 |      FAST DUAL                    |              |     1 |       |     2   (0)| 00:00:01 |
|   8 |      FAST DUAL                    |              |     1 |       |     2   (0)| 00:00:01 |
|   9 |      FAST DUAL                    |              |     1 |       |     2   (0)| 00:00:01 |
|  10 |      FAST DUAL                    |              |     1 |       |     2   (0)| 00:00:01 |
|  11 |      FAST DUAL                    |              |     1 |       |     2   (0)| 00:00:01 |
|  12 |      FAST DUAL                    |              |     1 |       |     2   (0)| 00:00:01 |
|  13 |      FAST DUAL                    |              |     1 |       |     2   (0)| 00:00:01 |
|  14 |      FAST DUAL                    |              |     1 |       |     2   (0)| 00:00:01 |
|  15 |   LOAD AS SELECT                  |              |       |       |            |          |
|* 16 |    COUNT STOPKEY                  |              |       |       |            |          |
|  17 |     VIEW                          |              |    10 |       |     2   (0)| 00:00:01 |
|  18 |      TABLE ACCESS FULL            | SYS_TEMP_0FD9|    10 |   150 |     2   (0)| 00:00:01 |
|  19 |     SORT AGGREGATE                |              |     1 |       |            |          |
|  20 |      FAST DUAL                    |              |     1 |       |     2   (0)| 00:00:01 |
|  21 |   SORT GROUP BY                   |              |     1 |    93 |    33  (34)| 00:00:01 |
|  22 |    MERGE JOIN CARTESIAN           |              |   100 |  9300 |    32  (32)| 00:00:01 |
|  23 |     VIEW                          |              |    10 |   800 |    12  (84)| 00:00:01 |
|  24 |      WINDOW SORT                  |              |    10 |   800 |    12  (84)| 00:00:01 |
|  25 |       WINDOW SORT                 |              |    10 |   800 |    12  (84)| 00:00:01 |
|  26 |        WINDOW SORT                |              |    10 |   800 |    12  (84)| 00:00:01 |
|  27 |         WINDOW SORT               |              |    10 |   800 |    12  (84)| 00:00:01 |
|  28 |          WINDOW SORT              |              |    10 |   800 |    12  (84)| 00:00:01 |
|  29 |           VIEW                    |              |    10 |   800 |     7  (72)| 00:00:01 |
|  30 |            WINDOW SORT            |              |    10 |   150 |     7  (72)| 00:00:01 |
|  31 |             WINDOW SORT           |              |    10 |   150 |     7  (72)| 00:00:01 |
|  32 |              WINDOW SORT          |              |    10 |   150 |     7  (72)| 00:00:01 |
|  33 |               WINDOW SORT         |              |    10 |   150 |     7  (72)| 00:00:01 |
|  34 |                WINDOW SORT        |              |    10 |   150 |     7  (72)| 00:00:01 |
|  35 |                 VIEW              |              |    10 |   150 |     2   (0)| 00:00:01 |
|  36 |                  TABLE ACCESS FULL| SYS_TEMP_0FD9|    10 |   150 |     2   (0)| 00:00:01 |
|  37 |     BUFFER SORT                   |              |    10 |   130 |    33  (34)| 00:00:01 |
|  38 |      VIEW                         |              |    10 |   130 |     2   (0)| 00:00:01 |
|  39 |       TABLE ACCESS FULL           | SYS_TEMP_0FD9|    10 |   130 |     2   (0)| 00:00:01 |
--------------------------------------------------------------------------------------------------

Predicate Information (identified by operation id):
---------------------------------------------------
16 - filter( (SELECT MIN(4) FROM "SYS"."DUAL" "DUAL")>=ROWNUM)

Но с одной из реальных таблиц это выглядит (для слегка измененного запроса):

----------------------------------------------------------------------------------------------------------------------------------------------------------
| Id  | Operation                            | Name         | Rows  | Bytes |TempSpc| Cost (%CPU)| Time     | Pstart| Pstop |    TQ  |IN-OUT| PQ Distrib |
----------------------------------------------------------------------------------------------------------------------------------------------------------
|   0 | SELECT STATEMENT                     |              |     1 |   422 |       |  6026M  (1)|999:59:59 |       |       |        |      |            |
|   1 |  TEMP TABLE TRANSFORMATION           |              |       |       |       |            |          |       |       |        |      |            |
|   2 |   LOAD AS SELECT                     |              |       |       |       |            |          |       |       |        |      |            |
|*  3 |    COUNT STOPKEY                     |              |       |       |       |            |          |       |       |        |      |            |
|   4 |     PX COORDINATOR                   |              |       |       |       |            |          |       |       |        |      |            |
|   5 |      PX SEND QC (RANDOM)             | :TQ10000     |    10 |       |       |     2   (0)| 00:00:01 |       |       |  Q1,00 | P->S | QC (RAND)  |
|*  6 |       COUNT STOPKEY                  |              |       |       |       |            |          |       |       |  Q1,00 | PCWC |            |
|   7 |        PX BLOCK ITERATOR             |              |    10 |       |       |     2   (0)| 00:00:01 |     1 |   115 |  Q1,00 | PCWC |            |
|   8 |         INDEX FAST FULL SCAN         | IDX          |    10 |       |       |     2   (0)| 00:00:01 |     1 |   115 |  Q1,00 | PCWP |            |
|   9 |   SORT GROUP BY                      |              |     1 |   422 |       |  6026M  (1)|999:59:59 |       |       |        |      |            |
|  10 |    MERGE JOIN CARTESIAN              |              |    22G|  8997G|       |  6024M  (1)|999:59:59 |       |       |        |      |            |
|  11 |     VIEW                             |              |  2289M|   872G|       |  1443M  (1)|999:59:59 |       |       |        |      |            |
|  12 |      WINDOW SORT                     |              |  2289M|   872G|   970G|  1443M  (1)|999:59:59 |       |       |        |      |            |
|  13 |       WINDOW SORT                    |              |  2289M|   872G|   970G|  1443M  (1)|999:59:59 |       |       |        |      |            |
|  14 |        WINDOW SORT                   |              |  2289M|   872G|   970G|  1443M  (1)|999:59:59 |       |       |        |      |            |
|  15 |         WINDOW SORT                  |              |  2289M|   872G|   970G|  1443M  (1)|999:59:59 |       |       |        |      |            |
|  16 |          WINDOW SORT                 |              |  2289M|   872G|   970G|  1443M  (1)|999:59:59 |       |       |        |      |            |
|  17 |           WINDOW SORT                |              |  2289M|   872G|   970G|  1443M  (1)|999:59:59 |       |       |        |      |            |
|  18 |            VIEW                      |              |  2289M|   872G|       |   248M  (1)|829:16:06 |       |       |        |      |            |
|  19 |             WINDOW SORT              |              |  2289M|   162G|   198G|   248M  (1)|829:16:06 |       |       |        |      |            |
|  20 |              WINDOW SORT             |              |  2289M|   162G|   198G|   248M  (1)|829:16:06 |       |       |        |      |            |
|  21 |               WINDOW SORT            |              |  2289M|   162G|   198G|   248M  (1)|829:16:06 |       |       |        |      |            |
|  22 |                WINDOW SORT           |              |  2289M|   162G|   198G|   248M  (1)|829:16:06 |       |       |        |      |            |
|  23 |                 WINDOW SORT          |              |  2289M|   162G|   198G|   248M  (1)|829:16:06 |       |       |        |      |            |
|  24 |                  WINDOW SORT         |              |  2289M|   162G|   198G|   248M  (1)|829:16:06 |       |       |        |      |            |
|  25 |                   PARTITION RANGE ALL|              |  2289M|   162G|       |  3587K  (4)| 11:57:36 |     1 |   115 |        |      |            |
|  26 |                    TABLE ACCESS FULL | LARGE_TABLE  |  2289M|   162G|       |  3587K  (4)| 11:57:36 |     1 |   115 |        |      |            |
|  27 |     BUFFER SORT                      |              |    10 |   130 |       |  6026M  (1)|999:59:59 |       |       |        |      |            |
|  28 |      VIEW                            |              |    10 |   130 |       |     2   (0)| 00:00:01 |       |       |        |      |            |
|  29 |       TABLE ACCESS FULL              | SYS_TEMP_0FD9|    10 |   130 |       |     2   (0)| 00:00:01 |       |       |        |      |            |
----------------------------------------------------------------------------------------------------------------------------------------------------------

Predicate Information (identified by operation id):
---------------------------------------------------
3 - filter(ROWNUM<=10)
6 - filter(ROWNUM<=10)

Я мог бы использовать from LARGE_TABLE sample (0.01), чтобы ускорить процесс, рискуя получить искаженную картинку.Это вернул ответ за 53 минуты для таблицы с 2 миллиардами строк.

Answer 3

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

1. Создать карту для каждого столбца, в которой хранятся счетчики для каждого отдельного значения
2. Читать всю таблицу (строка за строкой, но только один раз)
3. Для каждого ряда увеличить счетчики
4. После этого посмотрите на свои карты и вытащите наиболее частые значения

Для одного столбца SQL сделает это:

select value from (
   select value, count(*) from the_table
   group by value
   order by count(*) desc 
) where rownum < 2

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

Таким образом, вам, вероятно, придется написать программу для этого, либо на сервере (PL / SQL или Java, если доступно), либо в качестве клиентской программы.

Answer 4

Вы не можете.

Здесь нет хитрости, просто грубая работа.

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

Для одного столбца это просто:

SELECT col, count(*) FROM table GROUP BY col ORDER BY count(*) DESC

и получите первый ряд.

N столбцов равно N сканирований таблицы.

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

Если у вас есть 30 миллиардов строк с 30 миллиардами значений, вы можете сохранить их все, и все они имеют число 1. И вы можете сделать это для каждого столбца, который вас интересует.

Если эта информация важна для вас, вам лучше отслеживать ее независимо и постепенно по мере поступления ваших данных. Но это другая проблема.

Answer 5

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

Насколько актуальными должны быть результаты запроса? Вы можете выбрать результаты «группировки по» части нижеприведенного запроса в какой-то кэш, возможно, на ночной основе.

Тогда вы можете сделать окончательный выбор.

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

Стол счетчика будет выглядеть так:

field_value   count
Nancy         2
Bill          1
Ferris        1

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

Короче говоря, я думаю, вам нужно подумать о способах наблюдения этих данных косвенно . Я не думаю, что будет какой-либо способ обойти факт, что фактические подсчеты займут много времени. Но если у вас есть способ постепенно отслеживать то, что изменилось, то вам придется выполнять тяжелую работу только один раз. Тогда ваш кеш + что нового должен дать вам то, что вам нужно.

select top 1
  firstname, COUNT(*) as freq
from
  (
  select
    'Ferris' as firstname, 'Freemont' as lastname,
    'Possum' as favoriteanimal, 'Ubik' as favoritebook
  union all
  select 'Nancy','Freemont','Lemur','Housekeeping'
  union all
  select 'Nancy','Drew','Penguin','Ubik'
  union all
  select 'Bill','Ribbits','Lemur','Dhalgren'
  ) sample_data
group by
  firstname
order by
  COUNT(*) desc

Answer 6

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

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

Подробности зависят от того, какой язык программирования вы используете.