Apache Parquet ZoneMap 过滤支持小记

前置背景

ZoneMap

Min-max 过滤也叫 ZoneMap 过滤。

一个 ZoneMap 一般包含如下信息：

struct ZoneMap<T> {
    T min_value;
    T max_value;
    int64 num_rows;
    boolean has_null;
}

Parquet 的 ZoneMap 含有：

struct ParquetZoneMap<T> {
    T minValue;
    // parquet write 写的 min/max 值不一定是真实存在的
    // 比如这一列有 aaaaaa、bbbbbb、cccccc 三行
    // write 为了节省空间，它写的值是 min=a，max=c，
    // 此时 is_min_value_exact=false，is_max_value_exact=false
    boolean is_min_value_exact; 
    T maxValue;
    boolean is_max_value_exact;
    int64 num_rows;
    int64 null_count;
    int64 distinct_count;
}

ORC 的 ZoneMap 含有：

struct ORCZoneMap<T> {
    T min_value;
    T max_value;
    int64_t num_rows;
    bool hasNull;
}

ZoneMap 需要支持处理的表达式

binary_predicate: =,>,>=,<,<=
null_function: is_null(), is_not_null()
in_list: in(), not in()

ZoneMap 应用限制

比如 $f(a) = 10$ 这个表达式，你需要确保 $f(a)$ 是单调函数，才可以进行 min/max evaluate。

比如 $f(a) = a * a$，minValue = -1，maxValue = 2。如果你直接应用 min/max value 计算，你会发现其 ValueRange 是 1~4，但是这个是错误的，正确范围是 0~4。这是因为 a * a 不是单调函数导致的。

再比如 $f1(a) + f2(b) = 10$ 这个表达式，即使 $f1(a), f2(b)$都是单调函数，你也不能保证 $f1(a) + f2(b)$ 仍然为单调函数。除非你能保证 $f1(a), f2(b)$ 同为单调递增或单调递减函数。然后加法是一套逻辑，减法又是另外一套逻辑，这就导致系统实现上非常复杂。所以目前内表/ORC/DataFusion系统中，大家都只能支持谓词作用在一列的情况下。

StarRocks 内表 zonemap 过滤

内表有一套自己的表达式系统叫 ColumnPredicate，其 zonemap evaluate 逻辑是基于 ColumnPredicate 进行，而不是 ExprContext 这个结构，从 ExprContext -> ColumnPredicate 转换流程分为如下几步：

1. 先把 ExprContext 转换成 ColumnValueRange。这期间会对同一列下的不同谓词进行区间合并。比如 a IN (1, 2, 3) AND a IN (4, 5) 会合并成 a IN (1, 2, 3, 4, 5)。ChunkPredicateBuilder::parse_conjuncts::normalize_expressions 中处理。
2. 把 ColumnValueRange 转换成 TCondition。TCondition 是一个 thrift 结构。内表需要基于 TCondition 结构来转换成 ColumnPredicate。（历史原因，需要绕一圈，不能直接从 ColumnValueRange -> ColumnPredicate）。ChunkPredicateBuilder::parse_conjuncts::build_olap_filters() 中处理。
3. 上面两步只能处理简单谓词，比如 a > 10 这种。对于 col.a > 10 这种 subfield 的 expr，或者 a + 1 > 10 这种都是不支持的。为了解决这个问题，内表搞了一个 ColumnExprPredicate。在 ChunkPredicateBuilder::parse_conjuncts::build_column_expr_predicates() 中处理。
4. 上面操作的都是第一层的谓词。对于 OR 这种树状的 compund 谓词，会在 ChunkPredicateBuilder::parse_conjuncts::_normalize_compound_predicates()处理。这里处理完成后，ChunkPredicateBuilder 就是一颗树一样的结构了。

至此，整个 ChunkPredicateBuilder::parse_conjuncts() 过程结束。ChunkPredicateBuilder 初始化完成，其呈现一种树状的结构（ChunkPredicateBuilder 有 children，children 也是一个 ChunkPredicateBuilder）。

接下来在 OlapChunkSource 里面，调用 ChunkPredicateBuilder::get_predicate_tree_root 得到一颗 PredicateTree 树。也是在这里 TCondition 会被转换成 ColumnPredicate。

PredicateTree 由 PredicateCompoundNode 和 PredicateColumnNode 组成。一个是 AND/OR 节点，一个是叶子节点。

PredicateTree evaluate 的逻辑：每一个 ColumnPredicate 都有一个 ColumnID，然后你传入一个 Chunk 进去，它给你 evaluate 完毕返回。

Status PredicateTree::evaluate(const Chunk* chunk, uint8_t* selection) const {
    return evaluate(chunk, selection, 0, chunk->num_rows());
}

ZoneMap 过滤，需要先通过 ZonemapPredicatesRewriter::rewrite_predicate_tree 对 PredicateTree 进行改写，将 a = 5 改写成 a <= 5 AND a >= 5。

然后通过 ZoneMapFilterEvaluator 对 PredicateTree 进行 evaluate。

virtual bool zone_map_filter(const ZoneMapDetail& detail) const { return true; }

ORC SearchArgument

ORC 引入 SearchArgument 来处理 zonemap 过滤问题。

SearchArgument 通过 ExpressionTree 来表达出一棵表达式树。

ExpressionTree 支持 OR, AND, NOT, LEAF, CONSTANT 五种 Operator。

SearchArgument 通过 TruthValue 表达本次 evaluate 结果；

enum class TruthValue {
  YES,         // all rows satisfy the predicate
  NO,          // all rows dissatisfy the predicate
  IS_NULL,     // all rows are null value
  YES_NULL,    // null values exist, not-null rows satisfy the predicate
  NO_NULL,     // null values exist, not-null rows dissatisfy the predicate
  YES_NO,      // some rows satisfy the predicate and the others not
  YES_NO_NULL  // null values exist, some rows satisfy predicate and some not
};

TruthValue 解读规则很简单，比如 YES_NO 表示本次 zonemap evaluate，有些行满足，有些行不满足。再比如 YES_NO_NULL，表示有些行满足，有些行不满足，同时有些行是 NULL。

所有 ExpressionTree 计算完毕后，返回的都是 TruthValue，而不是传统的 true/false 两种答案。

ExpressionTree 的结构如下：

class ExpressionTree {
 public:
  enum class Operator { OR, AND, NOT, LEAF, CONSTANT };
 private:
  Operator mOperator;
  std::vector<TreeNode> mChildren; // 当 mOperator = OR, AND, NOT 时有值
  size_t mLeaf; // 当 mOperator = LEAF 时有值，存放的是 PredicateLeaf 的 index
  TruthValue mConstant; // 当 mOperator = CONSTANT 时有值
};

对于叶子节点，SearchArgument 使用 PredicateLeaf 表示。

/**
 * The primitive predicates that form a SearchArgument.
 */
class PredicateLeaf {
 public:
  /**
   * The possible operators for predicates. To get the opposites, construct
   * an expression with a not operator.
   */
  enum class Operator {
    EQUALS = 0,
    NULL_SAFE_EQUALS,
    LESS_THAN,
    LESS_THAN_EQUALS,
    IN,
    BETWEEN,
    IS_NULL
  };

  // The possible types for sargs.
  enum class Type {
    LONG = 0,  // all of the integer types
    FLOAT,     // float and double
    STRING,    // string, char, varchar
    DATE,
    DECIMAL,
    TIMESTAMP,
    BOOLEAN
  };

 private:
  Operator mOperator;
  PredicateDataType mType;
  std::string mColumnName;
  bool mHasColumnName;
  uint64_t mColumnId;
  std::vector<Literal> mLiterals;
};

PredicateLeaf 只支持如下几种运算：

EQUALS,
NULL_SAFE_EQUALS,
LESS_THAN,
LESS_THAN_EQUALS,
IN,
BETWEEN,
IS_NULL

如果想要表达出 a > 5 的概念，就是在上面套一个 ExpressionTree(Not) 就可以了。Not (a <= 5)。

PredicateLeaf 通过 columnId 或者 columnName 来定位。

比如 a > 5 OR b <= 5 OR (c + d) > 1 用SearchArgument 表达出的树结构如下：

(c + d) > 1 因为不支持，直接用 YES_NO_NULL 的 TruthValue 替代，不影响整棵 ExpressionTree 树的生成。

当然 SearchArgument 在构建完树后，会进行 CNF 来优化整棵 ExpressionTree。CNF 优化规则：https://community.gamedev.tv/t/help-with-conjunctive-normal-form/224025

Datafusion

Datafusion 使用 PruningPredicate 框架处理 zonemap 过滤。PruningStatistics 是用于存储 min/max/null_count/row_count 的数据结构。

PruningPredicate 通过从 PruningStatistics 获取 min/max 信息，对表达式进行 evaluate。

PruningPredicate 支持任意表达式，包括 UDF。

1. PruningPredicate::try_new(physical_expr, schema) 基于一个 expr 和表的 schema 信息，创建 PruningPredicate。
2. build_predicate_expression() 改写 expr，部分改写规则如下：

3. LiteralGuarantee::analyze(&expr) 进行 literal 推导。比如 a = 5 AND b IN (1, 2, 3) 。推导出满足该表达式为 true 的常量是：a = [5]，b = [1, 2, 3]。a != 5 则推导为 a != [5]。a > 5 或者 a = 5 or b = 6 这种就不进行推导。
4. 基于 PruningStatistics 进行 prune：
5. Prune 先基于前面分析出来的 LiteralGuarantee 过滤掉一部分不符合的 zonemap。
6. 然后剩下的 zonemap 和 rewritten expr evaluate，在过滤一部分不符合的 zonemap。
7. 返回一个 vector，true 表示留下对应的 zonemap。false 反之亦然。

小结

大家都只支持作用在单列上的简单谓词。

StarRocks 内表和 DataFusion 的实现类似，无非就是 DataFusion 的改写更加智能点。

Orc SearchArgument 则需要我们自己构造出一棵树出来。

附录：

三值逻辑运算

ZoneMap 过滤你会遇到 TRUE、FALSE、NULL（Unknown）做 AND、OR、NOT 运算，运算规则如下：

NOT：

AND：

OR：

来源地址：https://zhuanlan.zhihu.com/p/311464296

表达式改写论文