ClickHouse源码笔记4:FilterBlockInputStream, 探寻where，having的实现

书接上文，本篇继续分享ClickHouse源码中一个重要的流，FilterBlockInputStream的实现，重点在于分析Clickhouse是如何在执行引擎实现向量化的Filter操作符，而利用这个Filter操作符的，就可以实现where, having的数据过滤。
话不多说，准备发车~~ 本文的源码分析基于ClickHouse v19.16.2.2的版本。

1.Selection的实现

Selection是关系代数之中重要的一个的一个运算，通常也会用σ符合来selection的实现。

而在SQL语句之中，实现Selection运算的便是：where与having。而本文就要从一个简单的SQL语句出发，带领大家一同梳理Clickhouse的源码，来探究它是如何实现选择运算的。

先看如下的查询
SELECT * FROM test where a > 3 and b < 1;

这里扫描了test表，并且需要筛选出了a列大于3且b列小于1的行。老规矩，咱们先尝试打开ClickHouse的Debug日志看一下具体的执行的pipeline。(ClickHouse 20.6之后的版本，终于支持了使用Explain语句来查看执行计划，真是千呼万唤始出来啊~~）

ClickHouse执行的Pipeline

这里分为了4个流，而咱们需要关注的流就是Filter流，它实现了从存储引擎的数据读取数据，并且执行函数运算，并最终实现数据过滤的逻辑。

所以Clickhouse的表达式计算并不单单只由ExpressionBlockInputStream来完成的，而FilterBlockInputStream同样也需要包含Expression进行表达式的向量化的计算与过滤。
吐槽时间：私以为这样的实现并不优雅，如果在Filter上层再套一层ExpressionBlockinputStream结构上会更加清晰。不过这样的实现可能会导致额外的性能损耗，Clickhouse为了实现查询的高效执行可谓是『丧心病狂』, 后续分析聚合函数的实现时，我们会见到更为Dirty的代码。

2. FilterBlockInputStream的源码剖析

  • FilterBlockInputStream readImpl()的实现
    直接上代码看一下FilterBlockInputStream的数据读取方法吧，这部分代码比较多。我们拆解出来梳理
 /// Determine position of filter column. header = input->getHeader(); expression->execute(header); filter_column = header.getPositionByName(filter_column_name); auto & column_elem = header.safeGetByPosition(filter_column); /// Isn't the filter already constant? if (column_elem.column)  constant_filter_description = ConstantFilterDescription(*column_elem.column);

首先，构造FilterBlockInputStream时会首先读取下一级流的Block Header。通过Header来分析是否有常量列满足always true或always false的逻辑，来设置ConstantFilterDescription。比如存在全部是null列的过滤列，无论进行什么表达式计算，结果都是false。如果这样的话，就直接放回空的block给上层流就ok了。

if (expression->checkColumnIsAlwaysFalse(filter_column_name))  return {};// Function: checkColumnIsAlwaysFalsefor (auto & action : actions) {  if (action.type == action.APPLY_FUNCTION && action.function_base)  {   auto name = action.function_base->getName();   if ((name == "in" || name == "globalIn")    && action.result_name == column_name    && action.argument_names.size() > 1)   {    set_to_check = action.argument_names[1];   }  } }

接下来解析FilterBlockInputStream之中所有的表达式，查询是否有in或globalin的函数调用，并且其第二个参数set为空，那么同样表示表达式alwaysFalse也可以直接返回为空的Block。

比如说有如下查询：select * from test2 where a in (select a from test2 where a > 10)
而这个子查询select a from test2 where a > 10返回的是空集的话，那么就会被直接过滤了，返回空的block。

接下来进入一个while循环,不断从底层的流读取数据，并进行对应的表达式计算。这里我删去了一些冗余的代码:

while (1) {  res = children.back()->read();  expression->execute(res);  size_t columns = res.columns();  ColumnPtr column = res.safeGetByPosition(filter_column).column;

这里的实现很简单，就是不停从底层的流读取数据Block，通过表达式计算生成filter_column列。这个列是一组bool列，标识了对应的行是否还应该存在。

举个栗子，如果有如下查询select * from test where a > 10 and b < 2。ClickHouse的表达式会生成如下执行流程如下(注意：ClickHouse遵从函数式编程的逻辑，任意函数调用都会生成新的一列)：

1. add const column : 102. function call : a > 10 (生成一组新生成的bool列，列名为`a > 10`)3. remove const column : 104. add const column : 25. function call : b < 2 (生成一组新生成的bool列，列名为`b < 2`)6. remove const column : 2 7. call function : a > 10 and b < 2 (生成一组新生成的bool列，列名为`a > 10 and b < 2`)8. remove column : a > 109. remove column : b < 2

而最终新生成的这列就是我们后续需要用到过滤最终结果的filter_column列了。

接下来就进入最核心的一部分代码了，遍历Block之中除了const column与filter_column列的所有列，进行实际的数据过滤。IColumn接口中实现了一个接口为filter，也就是说，每一个列类型都需要实现一个过滤方法，用一组bool数组来过滤列数据。

  /** Removes elements that don't match the filter.  * Is used in WHERE and HAVING operations.  * If result_size_hint > 0, then makes advance reserve(result_size_hint) for the result column;  * if 0, then don't makes reserve(),  * otherwise (i.e. < 0), makes reserve() using size of source column.  */ using Filter = PaddedPODArray<UInt8>; virtual Ptr filter(const Filter & filt, ssize_t result_size_hint) const = 0;

我们直接跳到子类的实现中来看一下：

template <typename T>ColumnPtr ColumnVector<T>::filter(const IColumn::Filter & filt, ssize_t result_size_hint) const{ const UInt8 * filt_pos = filt.data(); const UInt8 * filt_end = filt_pos + size; const T * data_pos = data.data(); while (filt_pos < filt_end) {  if (*filt_pos)   res_data.push_back(*data_pos);  ++filt_pos;  ++data_pos; } return res;}

这之中最为核心的就是这个while循环，遍历bool数组，然后将合法数据塞进一个新的列之中，最终新的列替换旧的列，就完成了一列数据的过滤。之后对于剩余的列依次按照上述流程过一遍就完成了整个block的过滤。这里也可以看到，这个while循环也是一组很简单，没有control flow break的一段代码，能够给予编译器向量化优化的空间很大。当然，ClickHouse还提供了一个手工调用向量化API的过滤版本代码：

#ifdef __SSE2__ /** A slightly more optimized version.  * Based on the assumption that often pieces of consecutive values  * completely pass or do not pass the filter.  * Therefore, we will optimistically check the parts of `SIMD_BYTES` values.  */ static constexpr size_t SIMD_BYTES = 16; const __m128i zero16 = _mm_setzero_si128(); const UInt8 * filt_end_sse = filt_pos + size / SIMD_BYTES * SIMD_BYTES; while (filt_pos < filt_end_sse) {  int mask = _mm_movemask_epi8(_mm_cmpgt_epi8(_mm_loadu_si128(reinterpret_cast<const __m128i *>(filt_pos)), zero16));  if (0 == mask)  {   /// Nothing is inserted.  }  else if (0xFFFF == mask)  {   res_data.insert(data_pos, data_pos + SIMD_BYTES);  }  else  {   for (size_t i = 0; i < SIMD_BYTES; ++i)    if (filt_pos[i])     res_data.push_back(data_pos[i]);  }  filt_pos += SIMD_BYTES;  data_pos += SIMD_BYTES; }

Comments

Post a Comment

Popular posts from this blog

指纹浏览器定制开发全面助力企业安全与智能升级

在数字化时代，企业信息安全和智能化管理愈发成为商务发展的两大支柱。为适应这一趋势，指纹浏览器定制开发成为了企业安全和智能升级的最佳选择。让我们一同探索，如何通过指纹浏览器的二次开发、私有部署和AI智能等关键功能，助力企业迎接未来的挑战。 指纹浏览器二次开发：保障身份识别的极致体验 随着科技的不断进步，传统身份验证方式显得越来越脆弱。指纹浏览器的二次开发为企业带来了身份识别的极致体验，通过精准的生物特征验证，极大地提高了安全性。企业无需担忧密码泄漏或仿冒风险，真正实现了信息安全的无忧管理。 私有部署：数据安全掌握在自己手中 数据是企业最重要的资产之一，而私有部署则是最为可靠的数据保护手段之一。通过将指纹浏览器定制开发系统私有部署，企业能够完全掌握对敏感数据的访问和存储。这一层级的掌控，不仅提升了数据的安全性，同时也避免了因为云服务的共享带来的潜在风险。 原文转载： https://fashion.shaoqun.com/a/1585172.html 深圳巴厘岛海景酒店 ：https://www.vstour.cn/t/深圳巴厘岛海景酒店.html 深圳巴厘岛旅行团 ：https://www.vstour.cn/t/深圳巴厘岛旅行团.html 深圳巴厘岛旅游 ：https://www.vstour.cn/t/深圳巴厘岛旅游.html 深圳巴厘岛旅游报价 ：https://www.vstour.cn/t/深圳巴厘岛旅游报价.html 深圳巴厘岛旅游价格 ：https://www.vstour.cn/t/深圳巴厘岛旅游价格.html 深圳巴厘岛旅游团 ：https://www.vstour.cn/t/深圳巴厘岛旅游团.html 红海堵塞，海湾受益？ ：https://www.kjdsnews.com/a/1743053.html 一篇文章带你了解商标注册：尼加拉瓜 ：https://www.kjdsnews.com/a/1743054.html
Read more

跨境电商资讯：一文带你走进亚马逊19大海

Image
随着全球电商行业的迅速发展，许多品牌逐渐将目光投向海外市场，寻找新的业务增长点。亚马逊作为全球最大的电商平台之一，拥有众多海外站点，为卖家提供了广阔的发展空间和优质的服务。然而，当卖家们面对海外众多不同的站点，它们的区别是什么？该选红海站点还是蓝海站点？如何才能选择适合自己的平台？这些都让许多卖家感到非常迷惑，不知所措。 别着急！接下来就让小编带大家一起了解亚马逊各大海外站点的机会优势，并分享几位卖家的实战经验，助您选好出海站点，赢在起跑线！ 目前，亚马逊在全球拥有19大海外站点，覆盖北美、拉丁美洲、欧洲、亚洲、大洋洲等多个地区，帮助卖家触达数亿消费者。这些站点各有"特长"，您可以结合自身业务、资金情况和发展需求等因素，Pick适合自己的出海站点，及时把握海外商机！ 01老牌成熟站点，新手出海首选！ 目前，亚马逊在北美地区拥有美国站和加拿大站两大站点。北美站的整体成熟度和服务完善性让许多卖家将它作为开拓生意的首站。 从宏观环境来看，北美站可谓实力超群： ●体量庞大，消费潜力高 作为亚马逊全球最大海外站点，消费实力强劲，两大站点囊括3.7亿+人口，人红利充足，Prime会员占比高； ●品类齐全，细分赛道机会多 加拿大站选品文化接近美国，选品空间广阔，有利于卖家挖掘不同品类商机! 对于新手来说，亚马逊北美站拥有多重优势助力启航： ●配套完善，服务齐全 作为最早开设的站点，亚马逊服务支持齐全，新卖家上手更轻松 ●物流便捷，配送无阻 您可使用亚马逊远程物流配送计划(NARF)，将美国站FBA库存直接配送给加拿大买家，无需将库存事先运送到加拿大，助您轻松拓展北美地区商业版图! 该计划具有以下4大优势： ●利用美国FBA库存，为加拿大的Prime买家提供免费配送服务； ●由亚马逊处理跨境配送事宜，让配送流程更简单便捷； ●进口税费和相关费用由买家支付，无需卖家承担； ●退货直接退回美国，省心省力。 如果您想坐拥巨大流量，触达更多、更广泛的消费者；如果您的选品种类丰富齐全，希望同时布局多种品类赛道……那么北美站是您不该犹豫的首选! 02高潜消费增长能力，业务拓展不二之选！ 在拉丁美洲，除了已对卖家开放的墨西哥站之外，亚马逊巴西站也于2023年12月正式对中国卖家开放，不少北美站卖家已抢先拓展生意版图，吃到了"第一只螃蟹"! 结合宏观发展趋势...
Read more

利用 Google 购物广告促进销量的初学者指南

您需要更多客户。 并且，您需要 以可接受的成本获取它们 。因为，如果你不能做这两件事呢？ ……好吧， 我们别去那里了 。 首先，如何获得更多客户？ 嗯，一种行之有效的方法是 Google Shopping 。 这一领先的电子商务流量来源 占 电子商务 网站整体销售额的 16% 以上。 那是 巨大的。 但是，当您考虑到Google每秒处理超过 40,000 个搜索查询 时，这也就不足为奇了。 不过，这还不是全部…… 2018 年，在美国电子商务领域，Google 购物广告占 零售搜索广告支出的 76.4% ，占所有付费搜索点击次数的 85.3%。 另一方面，文字广告仅吸引了 23.6% 的零售搜索广告支出和 14.7% 的付费搜索点击次数。 由于 Google 努力通过富媒体广告格式提高知名度，投资 Google Shopping 广告系列已成为零售搜索行业的主要趋势。 但是，您能否使用 Google 购物以可接受的成本获取客户，从而为您带来利润？ 一言以蔽之？ 是的 。 OMG Commerce首席执行官 Brett Curry 去年 管理的广告活动平均 广告支出回报率 (ROAS) 为 300-600% 。 您愿意花 1美元获得 3 至 6 美元的销售额吗？ 我愿意打赌你会的。 你是怎么做到的？ 在本文中，您将准确了解 Google 购物是什么、它的工作原理以及如何开始您的第一个广告系列。 好吧，系好安全带 。 Fansgurus是一个社交媒体营销在线平包含了Facebook，Instagram，Twitter，Pinterest，YouTube，Tiktok，telegram，虾皮等等海外社交媒体，并提供增粉、点赞、转发、评论浏览量直播间在线，网站引流等数据服务。快速体验： zllp.myyfrs.ciwi._okgyw?fyuokfj 什么是谷歌购物？ Google 购物广告也称为产品详情广告或 PLA。而且，当用户在 Google 上搜索产品时，它们就会显示。 它们出现 在搜索结果的顶部或页面的右上角： Google 购物广告也可以 在"购物"标签下找到。 这些广告如此有效的 部分原因 是它们位于搜索结果顶部的显着位置。 那么，Google 购物广告包含哪些内容？ 简而言之， 消费者熟悉的5 个关键组件： 产品图片 产品名称 价格 卖家姓...
Read more