EmmyMiao87 commented 4 years ago

背景

在实际的业务场景中，通常存在两种场景并存的分析需求：对固定维度的聚合分析和对原始明细数据任意维度的分析。

例如，在销售场景中，每条订单数据包含这几个维度信息（item_id, sold_time, customer_id, price）。在这种场景下，有两种分析需求并存：

业务方需要获取某个商品在某天的销售额是多少，那么仅需要在维度（item_id, sold_time）维度上对 price 进行聚合即可。
分析某个人在某天对某个商品的购买明细数据。

在现有的 Doris 数据模型中，如果仅建立一个聚合模型的表，比如（item_id, sold_time, customer_id, sum(price)）。由于聚合损失了数据的部分信息，无法满足用户对明细数据的分析需求。

如果仅建立一个 Duplicate 模型，虽可以满足任意维度的分析需求，但由于不支持 Rollup，分析性能不佳，无法快速完成分析。

如果同时建立一个聚合模型和一个 Duplicate 模型，虽可以满足性能和任意维度分析，但两表之间本身无关联，需要业务方自行选择分析表。不灵活也不易用。

设计目标

支持基于 Duplicate 数据模型创建 Materialized Views 表，既满足用户直接使用明细表分析的需求，也同时满足某些特定维度分析的高效查询。

Materialized Views 功能同时覆盖所有现有对 Aggregate 数据模型创建 Rollup 表的逻辑。

Materialized Views 介绍

名词解释

Duplicate 数据模型：Doris中的用于存放明细数据的数据模型，建表可指定，数据不会被聚合。
Base 表：Doris 中通过 CREATE TABLE 命令创建出来的表。
Materialized Views 表：简称 MVs，物化视图。物化视图一般是某个 base 表做 SPJG 变换后的结果表。

介绍

使用聚合函数（如sum和count）的查询，在已经包含聚合数据的表中可以更高效地执行。这种改进的效率对于查询大量数据尤其适用。

物化视图实现原理：表中的数据被物化在存储节点中，并且在增量更新中能和 Base 表保持一致。

用户创建 MVs 表后，查询优化器支持选择一个最高效的 MVs 映射，并直接对 MVs 表进行查询而不是 Base 表。

由于 MVs 表数据通常比 Base 表数据小很多，因此命中 MVs 表的查询速度会快很多。视 MVs 表聚合情况而定，查询效率会提高 5~100 倍左右，甚至更多。

例子

对于销售场景的分析来说，业务方创建了一个存储订单信息的表 sales。

CREATE TABLE sales (
  order_time datatime,
  user_id int,
  sex string,
  country string,
  quantity int,
  price bigint) ENGINE=OLAP
DUPLICATE KEY(`order_time`, `user_id`, `sex`, `country`, `quantity`)
DISTRIBUTED BY HASH(`order_time`) BUCKETS 100
PROPERTIES (
  "storage_type" = "COLUMN"
)

此时，如果想对计算出不同城市，不同性别的人，购买的总物品个数，和总价格，则可以基于 sales 这个 Base 表创建如下 MVs 表。

create materialized view agg_sales as
  SELECT country, sex, sum(quantity), sum(price)
  FROM sales
  GROUP BY country, sex;

这时，如果查询下面 query 就可以命中 MVs 表, 业务方可以通过 EXPLAIN 语句来确定是否命中了 MVs 表。

select country, sex, sum(quantity), sum(price) 
from sales 
group by country, sex;

支持的分析语义

Selections：不支持
Projection：支持
Join：不支持
Group by：支持聚合函数：SUM, MAX, MIN, HLL_UNION（二阶段支持）, BITMAP_UNION（二阶段支持）
Order by：支持

查询数据

查询时根据当前的 query 选出一个 Base 表或最优的 MVs 表进行查询。或用户也可以指定选中某个 MVs 表。

Doris 如何选出一个最合适 query 的表：

根据特定的代数关系规则，收集备选的 MVs 表。（key 和 value 列是 MVs 表子集的）
从备选表中选出能匹配前缀索引最多的，如果都无法匹配则不 filter 备选表
从 step2 备选的 MVs 表中找到最小的 Rowcount 的表
使用 step3 选出的最佳 MVs 表改写原始查询

比如下面这些查询就可以匹配到刚才创建的 agg_sales 这个 MVs 表

SELECT country, sex, sum(quantity), sum(price) from sales GROUP BY country, sex

SELECT sex, sum(quantity) from sales GROUP BY sex

SELECT sum(price), country from sales GROUP BY country

但下面这些则无法匹配到

SELECT user_id, country, sex, sum(quantity), sum(price) from sales GROUP BY user_id, country, sex; // group by 列不是 MV 表 key 列的子集

SELECT sex, avg(quantity) from sales GROUP BY sex; // MV 表中不存在 avg(quantity) 聚合列

SELECT country, max(price) from sales GROUP BY country; // MV 表中不存在 max(price) 聚合列

用户指定查询 MV 表

有时，用户能确定查询要选中哪个 Rollup 表，就在 Base 表后增加一个指定的 Rollup 名称，使用方法如下：

select country, sex, sum(quantity), sum(price) from sales [agg_sales]

注意：如果用户选择的 MV 表无法匹配 Query，则查询会失败

DISTINCT

查询中带有 DISTINCT 关键字也可以匹配到 MV 表。下面例子说明：

查询语句, 
select country, count(distinct user_id) from sales group by country;

查询可以提配到下面这个 MV 表，这个表之所以需要一个 sum(price) 的列，主要是因为 MV 表至少需要一个聚合列。

create materialized view country_user_sales as
    select country, user_id , sum(price) 
    from sales 
    group by country, user_id;

HLL

对明细数据进行 HLL 聚合并且在查询时，使用 HLL 函数分析数据。主要适用于快速计算 PV, UV，count(distinct) 。

创建 Rollup 表
create materialized view dt_uv as 
    select dt, page_id, HLL_UNION(hll_hash(user_id)) 
    from user_view
    group by dt, page_id;

查询时，需要指定 HLL 分析函数，比如下面查询就可以匹配到 MV 表。 注意：MV 表中的 UV 列类型是 HLL，所以既要声明列变换函数 HLL_HASH, 并在外层指定聚合函数 HLL_UNION。

求每个网页每天的的PV
select dt, page_id, HLL_CARDINALITY(HLL_UNION(HLL_HASH(user_id))) from user_view;
求网站每天的UV
select dt, HLL_CARDINALITY(HLL_UNION(HLL_HASH(user_id))) from user_view;

注意：创建 MV 表时，可以指定 HLL_UNION 作为聚合函数，但查询时不能单独指定 HLL_UNION 函数，必须结合其他 HLL 分析函数一起使用

BITMAP

对明细数据进行 BITMAP_UNION 聚合，并且查询的时候使用 BITMAP 函数分析数据。

创建 Rollup 表
create materialized view dt_uv  as
    select dt, page_id, bitmap_union(to_bitmap(user_id))
    from user_view
    group by dt, page_id;

查询时，需要指定 BITMAP 分析函数，比如下面查询就可以匹配到 MV 表。

求每个网页每天的的PV
select dt, page_id, bitmap_count(bitmap_union(to_bitmap(user_id))) from user_view;
求网站每天的UV
select dt, bitmap_count(bitmap_union(to_bitmap(user_id))) from user_view

导入数据

对 Base 表的增量导入都会作用到所有关联的 MVs 表中。在 Base 表及所有的 MVs 表均完成后，导入才算完成，数据才能被看到。

Base 表和 MVs 表之间的数据是一致的。查询 Base 表和查询 MVs 表不会存在数据差异。

限制

schema change:
- 新增列：只会在 Base 表上新增
- 删除列：如果删除的列在 Base 表和 MVs 表上均存在，则均会生效。删除 MVs 的 key 列则会使得 MVs 根据新的 key 重新聚合。如果删除列后 MVs 不存在 value 列则不能删除该列。
- 修改列的类型：限制同当前 Rollup
delete:
- delete from: 如果删除条件中涉及的列，在表关联 MVs 表中均存在，且都是 Key 列，则可以删除。否则，不行。
- drop partition: 支持，即使 MVs 表没有 Partition column，也可以删除。
- truncate table: 支持，同步删除 MVs 数据
- drop table: 支持，同步删除 MVs 表

必要条件

Doris version 0.12.0 +

待定问题

如何支持对明细表的 HLL_HASH 聚合

现状：

不支持对原始数据进行 HLL_HASH 聚合，只能在导入的时候指定 HLL_HASH 函数

如何支持 AVG 聚合算子

目前不支持预聚合表，指定聚合类型为 AVG 函数。
查询时，可以指定聚合类型 AVG。
将 AVG 改写为 SUM/COUNT 目前 COUNT 在预聚合中也不支持

方案一：如果预聚合表需要支持指定 AVG 作为聚合函数，就需要在每次增量更新时，重新执行并计算聚合列。
方案二：预聚合指定 SUM 和 COUNT 两个聚合函数，查询匹配时，将 AVG 改写为 SUM/COUNT 进行 MVs 匹配。

如何支持 Replace 聚合算子

背景：业务方希望保留明细数据，但同时需要 Replace 型的预聚合表。

现状：

目前根本不支持查询指定 Replace 聚合。
创建预聚合表时，虽可以指定 Replace 函数，但无法判断明细数据的先后问题。

Replace 方法比较特殊，他在匹配时查询的 key 列和 MVs 表的 key 列相同，否则无法命中 MVs 表。

create materialized view replace_quantity as 
    select order_time, user_id, sex, country, replace(quantity) 
    from sales
    group by order_time, user_id, sex, country;

下面 query 就不能匹配到上面的 replace_quantity 表

select user_id, sex, country, replace(quantity) 
from sales
group by user_id, sex, country

morningman commented 4 years ago

alter table sales add rollup agg_sales as SELECT country, sex, sum(quantity), sum(price) FROM sales GROUP BY country, sex

ALTER TABLE sales ADD ROLLUP(country, sex, sum(quantity), sum(price));

直接这样是不是简洁点？

morningman commented 4 years ago

delete from: 禁止执行

delete from 是可以，只要所有rollup都包含条件列

kangkaisen commented 4 years ago

A great work!

imay commented 4 years ago

alter table sales add rollup agg_sales as SELECT country, sex, sum(quantity), sum(price) FROM sales GROUP BY country, sex

ALTER TABLE sales ADD ROLLUP(country, sex, sum(quantity), sum(price));

直接这样是不是简洁点？

I think a SQL query is better for following reasons

it is consistent with query
it is easy to extend, such as adding bitmap_union

imay commented 4 years ago

select country, sex, sum(quantity), sum(price) from sales [agg_sales]

This is confict with our partition syntax, I think you can use this /** */ syntax

imay commented 4 years ago

@EmmyMiao87 And you can think about supporting materialized view whose key column is generated from origin key with some converting. Such as supporting date rollup through a datetime column.

EmmyMiao87 commented 4 years ago

alter table sales add rollup agg_sales as SELECT country, sex, sum(quantity), sum(price) FROM sales GROUP BY country, sex

ALTER TABLE sales ADD ROLLUP(country, sex, sum(quantity), sum(price));

直接这样是不是简洁点？

后者唯一的问题在于不好扩展，我再想想

EmmyMiao87 commented 4 years ago

delete from: 禁止执行

delete from 是可以，只要所有rollup都包含条件列

嗯，如果rollup 的 key 包含所有条件列确实可以删除，我改一下

kangkaisen commented 4 years ago

alter table sales add rollup agg_sales as SELECT country, sex, sum(quantity), sum(price) FROM sales GROUP BY country, sex

ALTER TABLE sales ADD ROLLUP(country, sex, sum(quantity), sum(price)); 直接这样是不是简洁点？

I think a SQL query is better for following reasons

it is consistent with query

it is easy to extend, such as adding bitmap_union

Maybe We can refer to this paper: https://courses.cs.washington.edu/courses/cse591d/01sp/opt_views.pdf

Calcite Implement this algorithm and I also Implemented this algorithm in Presto. But this algorithm is a litter complex and need a CBO query optimizer, which could be a long-term solution.

EmmyMiao87 commented 4 years ago

@EmmyMiao87 And you can think about supporting materialized view whose key column is generated from origin key with some converting. Such as supporting date rollup through a datetime column.

This is a real requirement for some users. But if both the day of date and the mouth of date are related the base table, user could not keep the different partition date between different Rollup table.

EmmyMiao87 commented 4 years ago

详细设计

名词解释

Materialized Views: 简称 MVs，物化视图。

查询选择最优 MVs

当前选择 MVs 的问题：

只有声明在第一位的表才有可能打开 PreAgg，如果表不声明在第一位，则一定不打开 PreAgg。只能覆盖特定的某些 Query。
比较聚合方式，和比较列对应关系相互分隔。PreAgg 只比较和base表的聚合方式，不比较 Rollup 表和 Query 列对应关系，打开 PreAgg 也可能无法选中 Rollup 表。

暂定不重写 Query，依旧在 OlapScanNode 中确定选择的 MVs 表。

如果在整个查询前先选择 MVs，则有些可能包含一些可能可以被裁剪的列。

step1：在生成完所有 ScanNode 后，开始对所有 ScanNode 进行 MVs 表的选择。
step2: 遍历所有的 ScanNode，并为其选择合适的 MVs 表。
- Predicates 阶段：主要根据查询语句过滤不符合条件的 MVs，产生备选集合。
  - step2.1：筛选出 Projection 表中子集列中包含 AggInfo 中的 group by 列和 aggregate 列，作为备选。
  - step2.2：筛选出不包含聚合的 MVs 中列的子集中包含 Scan node 的所有列，作为备选。
  - step2.3: 如果是aggregate模型的表，且前面两次均为结果为空，则将key列包含全base 表的key列的rollup均加入备选。
- Priorities 阶段：从备选集合中根据策略，选择出最优的 MV 作为结果。
  - step2.3：根据 ScanNode 的谓词，从备选 MVs 表中选择出对应前缀索引最多的 MVs 表。
  - step2.4：从第三步的结果中，根据 RowCount 选择出行数最小的 MVs。
  - step2.5: 从第四步的结果中，选出列数最小的 MV 表作为 ScanNode 的最终扫描表。

在不支持 SPJG 型 MVs 的情况下，聚合条件涉及多个表的多个列时，无法匹配到带预聚合的 MVs。但并不影响其匹配到其他非预聚合的 MVs

EmmyMiao87 commented 4 years ago

创建 Materialized View

step1: 用户创建 MV
step2: 检查声明的 MV 语句是否符合要求
- 查询语句，语义解析正确
- Select clause 语句中列不能带别名
- From clause 只能涉及 Base 表名，不能是 MV 表名，且只能单张表。
- Where clause 禁止声明
- Group by 中除支持的几种聚合函数外，其余函数均不支持，也可以不声明聚合信息（对于duplicate 数据模型）
- Order by 所有声明在排序中的列将作为 MV 表的 key 列
step3: 通过 MVSelector 选择合适的 Base 表。注意：这里的 Base 表可能是某个 MV 表
step4: 创建 MVJob 元信息包括：MaterializedIndex, Tablet, Replica。提交 MV Job

**step1**
CREATE Materialized View [MV name] AS
  SELECT select_expr[, select_expr ...]
  FROM [Base table name]
  GROUP BY column_name[, column_name ...]
  ORDER BY column_name[, column_name ...]

例子：原始表主要存储的是每个查询语句在不同阶段的耗时，是一个 duplicate 模型的明细表。
包含 key 列（query_id, backend_id）和 value 列（type, time） 

query 1： 查询 query_id 为1的查询语句的总耗时，直接匹配 base 表即可
select query_id, sum(time) from base_table where query_id=1 group by query_id;

query 2: 查询 backend_id 为1的聚合类查询耗时的75分位数为多少。
select backend_id, PERCENTILE_APPROX(time, 0.75) from base_table where backend_id=1 and type='GROUP_BY' group by backend_id;

为 query 2 创建新的 MV 表，使用(backend_id, type)作为 key 列，加快查询速度。
create materialized view backend_type_table as 
    select backend_id, type, query_id, time 
    from base_table 
    order by backend_id, type

Class AddMaterializedViewClause {
    String mvName;
    SelectStmt mvQuery;

    void analyze() {
        **step2**
        mvQuery.analyze();
    }
}

Class MVHandler {
    void processAddRollup(AddMaterializedViewClause addMVClause) {
        if (olapTable.getKeysType() ==  KeysType.DUP_KEYS) {
            SelectStmt mvQuery = addMVClause.getMVQuery();
            **step2**
            checkMVQuery(mvQuery);
            **step3**
            rollupSelector.selectBestMV(mvQuery.getAggInfo(), mvQuery.getFromClause.get(0));
            **step4**
            createMetaOfMV();
            addAlterJobV2(mvJob);
        }
    }

    void checkMVQuery(SelectStmt mvQuery) throw DdlException() {
        1. check select clause
        2. check from clause
        3. check where clause
        4. check aggregate info
        5. check order by clause
    }
}

Class MVSelector {
    long selectBestMV(AggregateInfo aggInfo, OlapTable baseTable) {
        下部分详细说明
    }
}

morningman commented 4 years ago

Can I declare columns of aggregate type in the Order by clause?

select k1, k2, sum(v1) from tbl group by k1,k2 order by sum(v1)

EmmyMiao87 commented 4 years ago

Can I declare columns of aggregate type in the Order by clause?
select k1, k2, sum(v1) from tbl group by k1,k2 order by sum(v1)

The columns of order by clause must be the group by columns. Also the order of columns must be same as the order of columns in select list

chaoyli commented 4 years ago

I suggest you change MaterializedIndex name to MaterializedView.

EmmyMiao87 commented 4 years ago

The materialized view 1.0 has been completed. The materialized view 2.0 please move to #3344

littleforce163 commented 2 years ago

支持物化视图 join 多表吗

hf200012 commented 2 years ago

支持物化视图 join 多表吗

no

apache / doris

支持物化视图 #2101

背景

设计目标

Materialized Views 介绍

名词解释

介绍

例子

支持的分析语义

查询数据

用户指定查询 MV 表

DISTINCT

HLL

BITMAP

导入数据

推荐使用

限制

必要条件

待定问题

如何支持对明细表的 HLL_HASH 聚合

如何支持 AVG 聚合算子

如何支持 Replace 聚合算子

详细设计

名词解释

查询选择最优 MVs

创建 Materialized View