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

当然 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,部分改写规则如下:
Original PredicateRewritten Predicate
x = 5CASE WHEN x_null_count = x_row_count THEN false ELSE x_min <= 5 AND 5 <= x_max END
x < 5CASE WHEN x_null_count = x_row_count THEN false ELSE x_max < 5 END
x = 5 AND y = 10CASE WHEN x_null_count = x_row_count THEN false ELSE x_min <= 5 AND 5 <= x_max END AND CASE WHEN y_null_count = y_row_count THEN false ELSE y_min <= 10 AND 10 <= y_max END
x IS NULLx_null_count > 0
x IS NOT NULLx_null_count != row_count
CAST(x as int) = 5CASE WHEN x_null_count = x_row_count THEN false ELSE CAST(x_min as int) <= 5 AND 5 <= CAST(x_max as int) END
  1. 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 这种就不进行推导。
  2. 基于 PruningStatistics 进行 prune:
  3. Prune 先基于前面分析出来的 LiteralGuarantee 过滤掉一部分不符合的 zonemap。
  4. 然后剩下的 zonemap 和 rewritten expr evaluate,在过滤一部分不符合的 zonemap。
  5. 返回一个 vector,true 表示留下对应的 zonemap。false 反之亦然。

小结

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

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

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

附录:

三值逻辑运算

ZoneMap 过滤你会遇到 TRUE、FALSE、NULL(Unknown)做 AND、OR、NOT 运算,运算规则如下:

NOT:

NOT

AND:

AND

OR:

OR

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

表达式改写论文

https://vldb.org/pvldb/vol14/p3083-edara.pdf

原创文章,作者:Smith,如若转载,请注明出处:https://www.inlighting.org/archives/apache-parquet-zonemap-filter

打赏 微信扫一扫 微信扫一扫
SmithSmith
上一篇 2024年10月29日 上午11:01
下一篇 2024年11月23日 下午11:06

相关推荐

  • 浅谈 Apache ORC 之 Decimal 存储

    Decimal 在 Apache ORC 存储主要是依赖 zigzag 编码,zigzag 编码能有效的压缩绝对值小的数字。

    2024年5月5日
    3161
  • Spark-SQL 有用的 SQL

    我发现自己每次用 Spark 造 Iceberg 表都要耗费老大的劲,官方文档总是没有一个现成的 Demo,网上也搜索不到,全靠自己琢磨。故在这里记录一下,顺带帮助一下可能需要的人…

    2023年11月12日
    1.3K3
  • ORC vs Parquet,孰强孰弱?

    本文深入探讨了 ORC 和 Parquet 这两种主流数据湖文件格式的异同。从文件结构、类型系统、NULL处理到复杂类型存储,文章全面比较了两种格式的设计理念和实现细节。特别关注了统计信息的存储、随机 IO 性能、Footer 大小以及 Schema Evolution 支持等关键方面。虽然Parquet 在当前市场占据优势,但文章指出两种格式各有千秋,选择应基于具体使用场景。通过这篇深度分析,读者可以更好地理解这两种格式的优缺点,为数据湖存储方案的选择提供有价值的参考。

    2024年8月10日
    9422

发表回复

您的邮箱地址不会被公开。 必填项已用 * 标注