在Oracle中独立高效地查找多列的前N个值

Question

假设我有300亿行数据，每行有多个列，并且我想独立高效地查找每个列中出现次数最多的前N个值，且要用最简洁的SQL语句。例如，如果我有：

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

如果我想要排名第一，那么结果将如下所示：

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

我可能能想到一些方法来实现，但不确定它们是否最优，尤其是当有300亿行数据时，这点非常重要；而且SQL语句可能会变得庞大且难看，可能会使用太多的临时空间。

使用Oracle数据库。

- Joda

---

你如何解决平局？ - Matt Ball

每列有多少个不同的值？只有几万个，还是更多？ - Thilo

@MattBall 由dense_rank决定解决连接问题。 - Joda

@Thilo 在某些情况下，不同的值可能会达到数百万个，而在其他情况下可能只有2或3个。 - Joda

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（或子查询因子，我认为在Oracle术语中），并仅从每个列中提取最高频率值：

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子句中以调整在出现并列情况时所需采取的措施。

这类似于Thilo、ysth和其他人建议的概念，不过您让Oracle跟踪所有计数。

编辑：哦，解释计划表明它执行了四个完整表扫描；可能需要再思考一下...

编辑2：将未记录的MATERIALIZE提示添加到CTE中似乎解决了这个问题；它正在创建一个瞬态临时表来保存结果，并且只执行了一个完整表扫描。虽然在此时间样本数据集上解释计划成本更高，但我有兴趣听取任何关于这样做的不利因素的评论。

- Alex Poole

---

看看我刚刚发布的类似解决方案。可能还有改进的空间。 - Joda

Answer 2

目前在纯 Oracle SQL 中，我想到的最好方法类似于 @AlexPoole 所做的。我使用 count(A) 而不是 count(*) 将 null 推到底部。

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)来加速操作，但这样有可能会得到一个扭曲的结果。对于一个有20亿行的表格，这样做可以在53分钟内返回答案。

- Joda

Answer 3

不可能。

这里没有什么诀窍，只有原始的工作。

简单来说，您必须遍历表中的每一行，并计算您感兴趣的每个列的出现次数，然后对这些结果进行排序，以找到具有最高值的结果。

对于单个列，这很容易：

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

获取第一行。

N列等于N个表扫描。

如果您编写逻辑并通过表格一次传递，则可以计算每个列的每个值的每个实例的数量。

如果您有300亿行，每行有300亿个值，您将得到存储它们所有的机会，并且它们都具有1的计数。您可以为每个感兴趣的列执行此操作。

如果这些信息对您很重要，最好在数据进入时独立地和增量地跟踪它们。但那是另一个问题。

- Will Hartung

---

"N列等于N个表扫描。" 我很担心。我想知道它们是否可以“并行”运行，这样每个块只需从磁盘加载一次，然后所有子查询都可以看到它，然后再继续下一个块。这样，性能方面就与单个扫描差不多了。 - Thilo

Answer 4

假设每列中的不同值不太多，您需要执行以下操作：

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）或作为客户端程序。

- Thilo

Answer 5

以下是我提出的一种天真的方法。我认为对于超过几十万个数据集来说，这种方法完全不可行。也许一位大师可以以此为基础提供更合适的答案。

查询结果需要多新？ 您可以将下面查询的“group by”部分的结果选择到某种缓存中，例如每晚一次。

然后您可以在此基础上进行最终选择。

另一个可能性是在相关表上创建一个触发器，该触发器会使用每个插入/更新/删除操作更新一个“计数器”表。

计数器表如下：

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

- JosephStyons

---

“对于几十万以上的数据集来说，这完全是不可行的。”实际上，我认为只有在存在大量不同值时才会变得不可行。行数并不那么重要（即按比例缩放，但无法避免）。问题在于您仅选择了一列。因此，在SQL中，您可能需要为每个列重复大扫描，而聪明的程序可以将它们组合起来。 - Thilo

我主要会将它用于一次性的任务，例如我想要描述一个我不拥有的陌生表格的内容，因此触发器等方法并不适用。 - Joda

Answer 6

循环遍历您的记录，保持内存计数，记录每个感兴趣列的每个值被遇到的次数。

每隔一段时间（每X个记录或当您累积了达到固定内存限制的数据量时），循环遍历内存计数，并在某些磁盘存储中递增相应的计数并清除内存信息。

具体细节取决于您使用的编程语言。

- ysth

---

我可能做不到。但是假设我能够做到，那么这个操作的高效存储过程会是什么样子？我希望只需一次遍历表格即可完成。 - Joda

单次通过表格似乎不可行（需要进行太多排序）。如果您有四个单独的索引，您可以通过这四个索引进行单次遍历（完全不需要排序）。 - Thilo

我可能想对一个有100列的表中的每一列都这样做，但是没有足够的磁盘空间让它们都有索引。 - Joda

@Thilo：top N不涉及对整个表进行排序。 - ysth

Top N并不能给你计数（只是最大的N个值，而不是最常出现的N个值）。但我同意，这些也可以不排序完成。单次遍历，计数器映射。如果您没有太多不同的值，无论行数如何都可以使用。 - Thilo

啊，我完全错过了最频繁的部分。 - ysth