当前位置: 首页 > 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;在中 低端还有…...

微信小程序 - 手机震动

一、界面 <button type"primary" bindtap"shortVibrate">短震动</button> <button type"primary" bindtap"longVibrate">长震动</button> 二、js逻辑代码 注&#xff1a;文档 https://developers.weixin.qq…...

工业自动化时代的精准装配革新:迁移科技3D视觉系统如何重塑机器人定位装配

AI3D视觉的工业赋能者 迁移科技成立于2017年&#xff0c;作为行业领先的3D工业相机及视觉系统供应商&#xff0c;累计完成数亿元融资。其核心技术覆盖硬件设计、算法优化及软件集成&#xff0c;通过稳定、易用、高回报的AI3D视觉系统&#xff0c;为汽车、新能源、金属制造等行…...

全志A40i android7.1 调试信息打印串口由uart0改为uart3

一&#xff0c;概述 1. 目的 将调试信息打印串口由uart0改为uart3。 2. 版本信息 Uboot版本&#xff1a;2014.07&#xff1b; Kernel版本&#xff1a;Linux-3.10&#xff1b; 二&#xff0c;Uboot 1. sys_config.fex改动 使能uart3(TX:PH00 RX:PH01)&#xff0c;并让boo…...

深度学习习题2

1.如果增加神经网络的宽度&#xff0c;精确度会增加到一个特定阈值后&#xff0c;便开始降低。造成这一现象的可能原因是什么&#xff1f; A、即使增加卷积核的数量&#xff0c;只有少部分的核会被用作预测 B、当卷积核数量增加时&#xff0c;神经网络的预测能力会降低 C、当卷…...

JVM 内存结构 详解

内存结构 运行时数据区&#xff1a; Java虚拟机在运行Java程序过程中管理的内存区域。 程序计数器&#xff1a; ​ 线程私有&#xff0c;程序控制流的指示器&#xff0c;分支、循环、跳转、异常处理、线程恢复等基础功能都依赖这个计数器完成。 ​ 每个线程都有一个程序计数…...

Mysql8 忘记密码重置,以及问题解决

1.使用免密登录 找到配置MySQL文件&#xff0c;我的文件路径是/etc/mysql/my.cnf&#xff0c;有的人的是/etc/mysql/mysql.cnf 在里最后加入 skip-grant-tables重启MySQL服务 service mysql restartShutting down MySQL… SUCCESS! Starting MySQL… SUCCESS! 重启成功 2.登…...

Kafka主题运维全指南:从基础配置到故障处理

#作者&#xff1a;张桐瑞 文章目录 主题日常管理1. 修改主题分区。2. 修改主题级别参数。3. 变更副本数。4. 修改主题限速。5.主题分区迁移。6. 常见主题错误处理常见错误1&#xff1a;主题删除失败。常见错误2&#xff1a;__consumer_offsets占用太多的磁盘。 主题日常管理 …...

Xela矩阵三轴触觉传感器的工作原理解析与应用场景

Xela矩阵三轴触觉传感器通过先进技术模拟人类触觉感知&#xff0c;帮助设备实现精确的力测量与位移监测。其核心功能基于磁性三维力测量与空间位移测量&#xff0c;能够捕捉多维触觉信息。该传感器的设计不仅提升了触觉感知的精度&#xff0c;还为机器人、医疗设备和制造业的智…...

高考志愿填报管理系统---开发介绍

高考志愿填报管理系统是一款专为教育机构、学校和教师设计的学生信息管理和志愿填报辅助平台。系统基于Django框架开发&#xff0c;采用现代化的Web技术&#xff0c;为教育工作者提供高效、安全、便捷的学生管理解决方案。 ## &#x1f4cb; 系统概述 ### &#x1f3af; 系统定…...

在Zenodo下载文件 用到googlecolab googledrive

方法&#xff1a;Figshare/Zenodo上的数据/文件下载不下来&#xff1f;尝试利用Google Colab &#xff1a;https://zhuanlan.zhihu.com/p/1898503078782674027 参考&#xff1a; 通过Colab&谷歌云下载Figshare数据&#xff0c;超级实用&#xff01;&#xff01;&#xff0…...