当前位置: 首页 > news >正文

聊聊ClickHouse向量化执行引擎-过滤操作

俄罗斯Yandex开发的ClickHouse是一款性能黑马的OLAP数据库,其对SIMD的灵活运用给其带来了难以置信的性能。本文我们聊聊它如何对过滤操作进行SIMD优化。

基本思想

1、有一个数组data,即ColumnVector::data,存放数据

2、使用uint8类型,即1个字节类型的filter数组:ICloumn::Filter。他的大小是data数组大小,里面存放布尔值,标记data数组里面哪些数据满足过滤条件,应该筛选出来

3、最终生成一个新的数组res,根据filter数组,对data数组进行筛选,满足条件的拷贝到res数组中。标量逻辑的简单伪码:

let res = []
for (let i = 0; i < data.size(); i ++) {if (filter[i] != 0) {res.append(data[i])}
}

Clickhouse如何实现的呢?

4、上面代码耗时因素在于循环次数非常多,等于data数组的大小

5、如果可以降低循环次数,同时保证单次循环耗时变化不大,总体执行效率更高。要满足上面条件,需要在同一个指令周期做更多运算,SIMD指令可以做这样的运算。

6、SIMD指令目前最大支持512位数据,而filter本身一个值为8位,单词循环处理数据量为512 / 8 = 64个

7、每次取出来64个filter数组项(64字节),将其组成一个64位无符号整数值mask,这样每个filter数组项占用一个比特位

8、有两种特殊情况:1)mask 64位比特位都是1,本次循环中,64个data项都应该拷贝到res中。2)mask 64位比特位都是0,可以直接跳过循环。当然,这两种特殊情况经常出现在业务常见中

9、第三中情况是有一部分满足条件,此时是否需要循环64次?有没有进一步的优化方法?看看clickhouse咋处理

10、有多少项需要拷贝到新数组,取决于mask中比特位为1的个数,通过__builtin_clzll内置函数得到入参(64位)二进制表示形式中开头0的个数,从而得到最高比特位为1的索引,继而知道哪项数据需要拷贝。

11、最高1比特位的数据项拷贝后,需要将它置成0,这里有2个比较高效的方法blsr函数:一个是_blsr_u64指令,另一个是mask & (mask-1)

12、循环设置最高1的比特位,直到mask中所有比特位都为0

ColumnVector<T>::filter函数

5c3f99b1e8e69987c0267faf17c846c5.png

过滤函数主要是filter函数。其实分为3部分,AVX512VBMI2指令集、默认的操作和尾部数据处理。其中尾部数据处理是指处理数据不够64个时,剩余的部分处理方式,这种方式无法使用SIMD,沿用标量处理方式。

先看下默认操作方式:doFilterAligned即:模板函数

55d5309fd685b0b74293159ff71467b2.png

b6e51b52b8be5c6db0c52f72ce9b83c9.png 

这部分其实是对有一部分值满足条件场景的优化,主要有3个方面:

1)前导0个数,即data数组data[0]--data[i]都满足条件,需要拷贝到结果中

2)后导0个数,即data数组data[i]--data[63]都满足条件,需要拷贝到结果中

3)其他场景,比如0011 1100的场景,即两边都有不满足条件的,那就需要特殊处理了:计算出最低位起0的个数index,然后将data_pos[index]拷贝到结果中,即该数组满足条件,最后将index位置为0。

前缀和后缀拷贝的判断:

a07b2c33ba508a3991f45ff4d80385cf.png

蓝色框表示的意义:其实是去除前导0后,剩余的都是1,即mask值。也就是从0的索引开始,到64 - leading_zeroes都需要拷贝到结果中。蓝框计算效果,以2个字节大小为例,前导5个0:

4e22202c5a402b73a42f5ece6aa75a59.png

后导0的处理:其实可以调用__buitlin_ctzll函数

uint8_t suffixToCopy(UInt64 mask)
{const auto prefix_to_copy = prefixToCopy(~mask);//mask值取反return prefix_to_copy >= 64 ? prefix_to_copy : 64 - prefix_to_copy;//需要拷贝个数
}

效果如下图所示:

c27c4e56c4e0665b7119649ab032018b.png

64字节值转换成64位掩码值的计算函数Bytes64MaskToBits64Mask实现也很有讲究:

/// Transform 64-byte mask to 64-bit mask
inline UInt64 bytes64MaskToBits64Mask(const UInt8 * bytes64)
{
#if defined(__AVX512F__) && defined(__AVX512BW__)const __m512i vbytes = _mm512_loadu_si512(reinterpret_cast<const void *>(bytes64));UInt64 res = _mm512_testn_epi8_mask(vbytes, vbytes);
#elif defined(__AVX__) && defined(__AVX2__)const __m256i zero32 = _mm256_setzero_si256();UInt64 res =(static_cast<UInt64>(_mm256_movemask_epi8(_mm256_cmpeq_epi8(_mm256_loadu_si256(reinterpret_cast<const __m256i *>(bytes64)), zero32))) & 0xffffffff)| (static_cast<UInt64>(_mm256_movemask_epi8(_mm256_cmpeq_epi8(_mm256_loadu_si256(reinterpret_cast<const __m256i *>(bytes64+32)), zero32))) << 32);
#elif defined(__SSE2__)const __m128i zero16 = _mm_setzero_si128();UInt64 res =(static_cast<UInt64>(_mm_movemask_epi8(_mm_cmpeq_epi8(_mm_loadu_si128(reinterpret_cast<const __m128i *>(bytes64)), zero16))) & 0xffff)| ((static_cast<UInt64>(_mm_movemask_epi8(_mm_cmpeq_epi8(_mm_loadu_si128(reinterpret_cast<const __m128i *>(bytes64 + 16)), zero16))) << 16) & 0xffff0000)| ((static_cast<UInt64>(_mm_movemask_epi8(_mm_cmpeq_epi8(_mm_loadu_si128(reinterpret_cast<const __m128i *>(bytes64 + 32)), zero16))) << 32) & 0xffff00000000)| ((static_cast<UInt64>(_mm_movemask_epi8(_mm_cmpeq_epi8(_mm_loadu_si128(reinterpret_cast<const __m128i *>(bytes64 + 48)), zero16))) << 48) & 0xffff000000000000);
#elif defined(__aarch64__) && defined(__ARM_NEON)const uint8x16_t bitmask = {0x01, 0x02, 0x4, 0x8, 0x10, 0x20, 0x40, 0x80, 0x01, 0x02, 0x4, 0x8, 0x10, 0x20, 0x40, 0x80};const auto * src = reinterpret_cast<const unsigned char *>(bytes64);const uint8x16_t p0 = vceqzq_u8(vld1q_u8(src));const uint8x16_t p1 = vceqzq_u8(vld1q_u8(src + 16));const uint8x16_t p2 = vceqzq_u8(vld1q_u8(src + 32));const uint8x16_t p3 = vceqzq_u8(vld1q_u8(src + 48));uint8x16_t t0 = vandq_u8(p0, bitmask);uint8x16_t t1 = vandq_u8(p1, bitmask);uint8x16_t t2 = vandq_u8(p2, bitmask);uint8x16_t t3 = vandq_u8(p3, bitmask);uint8x16_t sum0 = vpaddq_u8(t0, t1);uint8x16_t sum1 = vpaddq_u8(t2, t3);sum0 = vpaddq_u8(sum0, sum1);sum0 = vpaddq_u8(sum0, sum0);UInt64 res = vgetq_lane_u64(vreinterpretq_u64_u8(sum0), 0);
#elseUInt64 res = 0;for (size_t i = 0; i < 64; ++i)res |= static_cast<UInt64>(0 == bytes64[i]) << i;
#endifreturn ~res;
}

我们看到,按照优先级尽可能利用位数多的指令集进行计算,同时在所有指令集都不可用及未64字节对齐(align)的部分进行了保底处理。其利用了以下指令集:

    AVX512F / AVX512BW

    AVX/AVX2

    SSE2

其中,_mm512_testn_epi8_mask函数功能:计算a和b两个入参值按8位整数逐位与(AND),产生中间8位值,如果中间值为0,则在结果掩码k中设置相应位:

FOR j := 0 to 63

  i := j*8

  k[j] := ((a[i+7:i] AND b[i+7:i]) == 0) ? 1 : 0

ENDFOR

所以,bytes64MaskToBits64Mask最终计算出的值需要取反。另外,其他指令集,比如AVX下,_mm256_cmpeq_epi8比较32位是否等于0,等于0表示不满足条件,当然等于零时该函数返回0xFF,所以同样最终结果需要取反。

另外一种操作方式:doFilterAligned即:模板函数

ccc5bcb83e9300ca8ff890cec96a54cf.png

主要是通过_mm512_mask_compressstoreu_epi8类似函数分别对1、2、4、8字节长度类型针对掩码进行数据拷贝,这里不再赘述。

参考

https://zhuanlan.zhihu.com/p/454657709

https://blog.csdn.net/u010002184/article/details/113977586

https://blog.51cto.com/u_15103025/2643507

https://zhuanlan.zhihu.com/p/449154820

https://www.zhihu.com/question/450069375/answer/1813516193

https://www.intel.com/content/www/us/en/docs/intrinsics-guide/index.html

相关文章:

聊聊ClickHouse向量化执行引擎-过滤操作

俄罗斯Yandex开发的ClickHouse是一款性能黑马的OLAP数据库&#xff0c;其对SIMD的灵活运用给其带来了难以置信的性能。本文我们聊聊它如何对过滤操作进行SIMD优化。 基本思想 1、有一个数组data&#xff0c;即ColumnVector::data&#xff0c;存放数据 2、使用uint8类型&#xf…...

数据可视化第二版-拓展-网约车分析案例

文章目录 数据可视化第二版-拓展-网约车分析案例竞赛介绍 1等奖作品-IT从业者张某某的作品结论过程数据和思考数据处理数据探索数据分析方法选择数据分析相关性分析转化率分析分析结论 完单数量分析分析结论 司机数量分析分析结论 时间分析每日订单分析 工作日各时段分析周六日…...

pytest - Getting Start

前言 项目开发中有很多的功能&#xff0c;通常开发人员需要对自己编写的代码进行自测&#xff0c;除了借助postman等工具进行测试外&#xff0c;还需要编写单元测试对开发的代码进行测试&#xff0c;通过单元测试来判断代码是否能够实现需求&#xff0c;本文介绍的pytest模块是…...

( 字符串) 205. 同构字符串 ——【Leetcode每日一题】

❓205. 同构字符串 难度&#xff1a;简单 给定两个字符串 s 和 t &#xff0c;判断它们是否是同构的。 如果 s 中的字符可以按某种映射关系替换得到 t &#xff0c;那么这两个字符串是同构的。 每个出现的字符都应当映射到另一个字符&#xff0c;同时不改变字符的顺序。不同…...

python+django+vue消防知识宣传网站

开发语言&#xff1a;Python 框架&#xff1a;django Python版本&#xff1a;python3.7.7 数据库&#xff1a;mysql 数据库工具&#xff1a;Navicat 开发软件&#xff1a;PyCharm 层随着移动应用技术的发展&#xff0c;越来越多的消防单位借助于移动手机、电脑完成生活中的事…...

彻底告别手动配置任务,魔改xxl-job!

分析 改造 1、接口调用 2、创建新注解 3、自动注册核心 4、自动装配 测试 测试后 XXL-Job是一款非常优秀的任务调度中间件&#xff0c;其轻量级、使用简单、支持分布式等优点&#xff0c;被广泛应用在我们的项目中&#xff0c;解决了不少定时任务的调度问题。不仅如此&a…...

【五一创作】Springboot+多环境+多数据源(MySQL+Phoenix)配置及查询(多知识点)

文章目录 1. 背景2. 技术点3 子模块依赖SpringBoot设置4. 多环境配置4.1 application.yml4.2 application-pro.yml 5. 多数据源配置5.1 yml配置5.2 自定义数据源在Java中配置5.2.1 PhoenixDataSourceConfig5.2.2 MysqlDataSourceConfig 6. 完整的Pom6. 测试6.1 Mapper配置6.2 方…...

Python小姿势 - 线程和进程:

线程和进程&#xff1a; Python里面线程是真正的并行执行&#xff0c;进程是可以并行执行的。 所谓进程&#xff0c;就是操作系统中执行一个程序的独立单元&#xff0c;它是系统进行资源分配和调度的基本单位。一个进程可以创建和撤销另一个进程&#xff0c;同一个进程内可以并…...

Mysql 锁

目录 0 课程视频 1 概述 1.1 多用户 并发访问 -> 为了数据一致性(多用户) 1.2 全局锁 数据库所有表 1.3 表级锁 每次操作 锁整张表 1.4 行级锁 每次操作 锁对应行 2 全局锁 ->锁后只读 -> 全库逻辑备份 2.1 阻塞DML /DDL 可DQL读 2.2 语法 2.2.1 加锁 flush…...

基于ssm的论坛系统的设计与实现【附源码】

基于ssm的论坛系统的设计与实现 摘 要 早期的网络论坛系统已经诞生一段时间&#xff0c;随着互联网技术的发展&#xff0c;它已经从最初的简单电子公告板系统变成了一种丰富的论坛系统社区模型。人们通过论坛系统进行信息的获取、发布和交流已经成为一种普遍的社交方式&#x…...

Vue中的事件修饰符

Vue中的事件修饰符: 1.prevent: 阻止默认事件 (常用) : 2.stop: 阻止事件冒泡 (常用) : 3.once: 事件只触发一次(常用) : 4.capture:使用事件的捕获模式: 5.self: 只有event.target是当前操作的元素是才触发事件; 6.passive:事件的默认行为立即执行&#xff0c;无需等待事件回调…...

如何保证Redis和数据库的一致性

关注我&#xff0c;升职加薪就是你&#xff01; 当我们对数据进行修改的时候&#xff0c;到底是先删缓存&#xff0c;还是先写数据库&#xff1f; 1、如果先删缓存&#xff0c;再写数据库&#xff1a;在高并发场景下&#xff0c;当第一个线程删除了缓存&#xff0c;还没来得及写…...

Ubantu docker学习笔记(八)私有仓库

文章目录 一、建立HTTPS链接1.在仓库服务器上获取TLS证书1.1 生成证书颁发机构证书1.2 生成服务器证书1.3 利用证书运行仓库容器 2.让私有仓库支持HTTPS3.客户端端配置 二、基本身份验证三、对外隐藏仓库服务器3.1 在服务器端3.2 在客户端进行 四、仓库可视化 在前面的学习中&a…...

【五一创作】网络协议与攻击模拟-01-wireshark使用-捕获过滤器

协议 TCP/IP协议簇 网络接口层(没有特定的协议)PPPOE 物理层 数据链路层 网络层:IP (v4/v6) ARP (地址解析协议) RARP ICMP (Internet控制报文协议) IGMP 传输层:TCP(传输控制协议) UDP(用户数据报协议) 应用层:都是基于传输层协议的端口,总共端口0~65535 0~1023 HTTP—t…...

网络-IP地址(嵌入式学习)

IP地址 基本概念IPv4 五类&#xff1a;A B C D E特殊地址子网掩码子网号概念IPv6优势举个栗子 基本概念 IP地址是Internet中主机的标识 IP地址&#xff08;Internet Protocol Address 互联网国际地址&#xff09;是一种在Internet上的给主机编址的方式&#xff0c;它主要是为…...

一文介绍Linux EAS

能量感知调度&#xff08;Energy Aware Scheduling&#xff0c;简称EAS&#xff09;是目前Android手机中Linux线程调度器的基础功能&#xff0c;它使调度器能预测其决策对CPU能耗的影响。依靠CPU的能量模型&#xff08;Energy Model&#xff0c;简称EM&#xff09;&#xff0c;…...

【五一创作】【Midjourney】Midjourney 连续性人物创作 ① ( 通过垫图方式生成类似图像 )

文章目录 一、Midjourney 生成图像二、通过垫图方式生成类似图像 一、Midjourney 生成图像 Midjourney 可以生成高质量的图像 , 但是 生成过程有很大的随机性 , 输入同样的提示词指令 , 其输出结果也存在很大的不同 ; 如果要 生成稳定的人物角色 , 场景 , 描述连贯的内容 , 这…...

牛客刷题错题记录【03】

链接&#xff1a;https://www.nowcoder.com/questionTerminal/8242fbf4b3a241219989b3e1d0ee82db 来源&#xff1a;牛客网 下列关于Vue和React的描述错误的是&#xff08; Vue进行数据拦截/代理&#xff0c;对数据更敏感&#xff0c;数据驱动视图自更新&#xff0c;而React需…...

maven-gpg-plugin gpg禁用交互式输入密码 免密码输入 设置默认密码 关闭pinentry-qt输入 passphrase

一、问题描述 在使用maven-gpg-plugin打包jar时,默认情况下&#xff0c;每次都会弹出对话框要你输入密码&#xff1a; 这就有点烦&#xff0c;有啥办法可以设置默认方法没&#xff1f;网上找了一圈&#xff0c;通过搜索关键词“passphrase”&#xff0c;找到了一些教程&#x…...

急需国产化替代的重要的工程软件有哪些?

急需国产化替代的重要的工程软件有哪些&#xff1f; 软件一&#xff1a;AutoCAD等领域常用设计软件 AutoCAD由Autodesk公司开发的工程辅助设计软件&#xff0c;目前是设计领域 最重要的工程软件。在高端3D的CAD领域&#xff0c;国产软件几乎全军覆没&#xff0c;在中 低端还有…...

云原生核心技术 (7/12): K8s 核心概念白话解读(上):Pod 和 Deployment 究竟是什么?

大家好&#xff0c;欢迎来到《云原生核心技术》系列的第七篇&#xff01; 在上一篇&#xff0c;我们成功地使用 Minikube 或 kind 在自己的电脑上搭建起了一个迷你但功能完备的 Kubernetes 集群。现在&#xff0c;我们就像一个拥有了一块崭新数字土地的农场主&#xff0c;是时…...

STM32F4基本定时器使用和原理详解

STM32F4基本定时器使用和原理详解 前言如何确定定时器挂载在哪条时钟线上配置及使用方法参数配置PrescalerCounter ModeCounter Periodauto-reload preloadTrigger Event Selection 中断配置生成的代码及使用方法初始化代码基本定时器触发DCA或者ADC的代码讲解中断代码定时启动…...

服务器硬防的应用场景都有哪些?

服务器硬防是指一种通过硬件设备层面的安全措施来防御服务器系统受到网络攻击的方式&#xff0c;避免服务器受到各种恶意攻击和网络威胁&#xff0c;那么&#xff0c;服务器硬防通常都会应用在哪些场景当中呢&#xff1f; 硬防服务器中一般会配备入侵检测系统和预防系统&#x…...

质量体系的重要

质量体系是为确保产品、服务或过程质量满足规定要求&#xff0c;由相互关联的要素构成的有机整体。其核心内容可归纳为以下五个方面&#xff1a; &#x1f3db;️ 一、组织架构与职责 质量体系明确组织内各部门、岗位的职责与权限&#xff0c;形成层级清晰的管理网络&#xf…...

cf2117E

原题链接&#xff1a;https://codeforces.com/contest/2117/problem/E 题目背景&#xff1a; 给定两个数组a,b&#xff0c;可以执行多次以下操作&#xff1a;选择 i (1 < i < n - 1)&#xff0c;并设置 或&#xff0c;也可以在执行上述操作前执行一次删除任意 和 。求…...

[10-3]软件I2C读写MPU6050 江协科技学习笔记(16个知识点)

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16...

什么是Ansible Jinja2

理解 Ansible Jinja2 模板 Ansible 是一款功能强大的开源自动化工具&#xff0c;可让您无缝地管理和配置系统。Ansible 的一大亮点是它使用 Jinja2 模板&#xff0c;允许您根据变量数据动态生成文件、配置设置和脚本。本文将向您介绍 Ansible 中的 Jinja2 模板&#xff0c;并通…...

智能分布式爬虫的数据处理流水线优化:基于深度强化学习的数据质量控制

在数字化浪潮席卷全球的今天&#xff0c;数据已成为企业和研究机构的核心资产。智能分布式爬虫作为高效的数据采集工具&#xff0c;在大规模数据获取中发挥着关键作用。然而&#xff0c;传统的数据处理流水线在面对复杂多变的网络环境和海量异构数据时&#xff0c;常出现数据质…...

SiFli 52把Imagie图片,Font字体资源放在指定位置,编译成指定img.bin和font.bin的问题

分区配置 (ptab.json) img 属性介绍&#xff1a; img 属性指定分区存放的 image 名称&#xff0c;指定的 image 名称必须是当前工程生成的 binary 。 如果 binary 有多个文件&#xff0c;则以 proj_name:binary_name 格式指定文件名&#xff0c; proj_name 为工程 名&…...

Java + Spring Boot + Mybatis 实现批量插入

在 Java 中使用 Spring Boot 和 MyBatis 实现批量插入可以通过以下步骤完成。这里提供两种常用方法&#xff1a;使用 MyBatis 的 <foreach> 标签和批处理模式&#xff08;ExecutorType.BATCH&#xff09;。 方法一&#xff1a;使用 XML 的 <foreach> 标签&#xff…...