聊聊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函数
过滤函数主要是filter函数。其实分为3部分,AVX512VBMI2指令集、默认的操作和尾部数据处理。其中尾部数据处理是指处理数据不够64个时,剩余的部分处理方式,这种方式无法使用SIMD,沿用标量处理方式。
先看下默认操作方式:doFilterAligned即:模板函数
这部分其实是对有一部分值满足条件场景的优化,主要有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。
前缀和后缀拷贝的判断:
蓝色框表示的意义:其实是去除前导0后,剩余的都是1,即mask值。也就是从0的索引开始,到64 - leading_zeroes都需要拷贝到结果中。蓝框计算效果,以2个字节大小为例,前导5个0:
后导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;//需要拷贝个数
}
效果如下图所示:
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即:模板函数
主要是通过_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数据库,其对SIMD的灵活运用给其带来了难以置信的性能。本文我们聊聊它如何对过滤操作进行SIMD优化。 基本思想 1、有一个数组data,即ColumnVector::data,存放数据 2、使用uint8类型…...
数据可视化第二版-拓展-网约车分析案例
文章目录 数据可视化第二版-拓展-网约车分析案例竞赛介绍 1等奖作品-IT从业者张某某的作品结论过程数据和思考数据处理数据探索数据分析方法选择数据分析相关性分析转化率分析分析结论 完单数量分析分析结论 司机数量分析分析结论 时间分析每日订单分析 工作日各时段分析周六日…...
pytest - Getting Start
前言 项目开发中有很多的功能,通常开发人员需要对自己编写的代码进行自测,除了借助postman等工具进行测试外,还需要编写单元测试对开发的代码进行测试,通过单元测试来判断代码是否能够实现需求,本文介绍的pytest模块是…...
( 字符串) 205. 同构字符串 ——【Leetcode每日一题】
❓205. 同构字符串 难度:简单 给定两个字符串 s 和 t ,判断它们是否是同构的。 如果 s 中的字符可以按某种映射关系替换得到 t ,那么这两个字符串是同构的。 每个出现的字符都应当映射到另一个字符,同时不改变字符的顺序。不同…...
python+django+vue消防知识宣传网站
开发语言:Python 框架:django Python版本:python3.7.7 数据库:mysql 数据库工具:Navicat 开发软件:PyCharm 层随着移动应用技术的发展,越来越多的消防单位借助于移动手机、电脑完成生活中的事…...
彻底告别手动配置任务,魔改xxl-job!
分析 改造 1、接口调用 2、创建新注解 3、自动注册核心 4、自动装配 测试 测试后 XXL-Job是一款非常优秀的任务调度中间件,其轻量级、使用简单、支持分布式等优点,被广泛应用在我们的项目中,解决了不少定时任务的调度问题。不仅如此&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小姿势 - 线程和进程:
线程和进程: Python里面线程是真正的并行执行,进程是可以并行执行的。 所谓进程,就是操作系统中执行一个程序的独立单元,它是系统进行资源分配和调度的基本单位。一个进程可以创建和撤销另一个进程,同一个进程内可以并…...
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的论坛系统的设计与实现 摘 要 早期的网络论坛系统已经诞生一段时间,随着互联网技术的发展,它已经从最初的简单电子公告板系统变成了一种丰富的论坛系统社区模型。人们通过论坛系统进行信息的获取、发布和交流已经成为一种普遍的社交方式&#x…...
Vue中的事件修饰符
Vue中的事件修饰符: 1.prevent: 阻止默认事件 (常用) : 2.stop: 阻止事件冒泡 (常用) : 3.once: 事件只触发一次(常用) : 4.capture:使用事件的捕获模式: 5.self: 只有event.target是当前操作的元素是才触发事件; 6.passive:事件的默认行为立即执行,无需等待事件回调…...
如何保证Redis和数据库的一致性
关注我,升职加薪就是你! 当我们对数据进行修改的时候,到底是先删缓存,还是先写数据库? 1、如果先删缓存,再写数据库:在高并发场景下,当第一个线程删除了缓存,还没来得及写…...
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 五类:A B C D E特殊地址子网掩码子网号概念IPv6优势举个栗子 基本概念 IP地址是Internet中主机的标识 IP地址(Internet Protocol Address 互联网国际地址)是一种在Internet上的给主机编址的方式,它主要是为…...
一文介绍Linux EAS
能量感知调度(Energy Aware Scheduling,简称EAS)是目前Android手机中Linux线程调度器的基础功能,它使调度器能预测其决策对CPU能耗的影响。依靠CPU的能量模型(Energy Model,简称EM),…...
【五一创作】【Midjourney】Midjourney 连续性人物创作 ① ( 通过垫图方式生成类似图像 )
文章目录 一、Midjourney 生成图像二、通过垫图方式生成类似图像 一、Midjourney 生成图像 Midjourney 可以生成高质量的图像 , 但是 生成过程有很大的随机性 , 输入同样的提示词指令 , 其输出结果也存在很大的不同 ; 如果要 生成稳定的人物角色 , 场景 , 描述连贯的内容 , 这…...
牛客刷题错题记录【03】
链接:https://www.nowcoder.com/questionTerminal/8242fbf4b3a241219989b3e1d0ee82db 来源:牛客网 下列关于Vue和React的描述错误的是( Vue进行数据拦截/代理,对数据更敏感,数据驱动视图自更新,而React需…...
maven-gpg-plugin gpg禁用交互式输入密码 免密码输入 设置默认密码 关闭pinentry-qt输入 passphrase
一、问题描述 在使用maven-gpg-plugin打包jar时,默认情况下,每次都会弹出对话框要你输入密码: 这就有点烦,有啥办法可以设置默认方法没?网上找了一圈,通过搜索关键词“passphrase”,找到了一些教程&#x…...
急需国产化替代的重要的工程软件有哪些?
急需国产化替代的重要的工程软件有哪些? 软件一:AutoCAD等领域常用设计软件 AutoCAD由Autodesk公司开发的工程辅助设计软件,目前是设计领域 最重要的工程软件。在高端3D的CAD领域,国产软件几乎全军覆没,在中 低端还有…...
计算机组成原理 4.2.1存储芯片连接
连接原理 主存储器 通过数据总线、地址总线和控制总线和CPU相连数据总线的位数正比于数据传输率地址总线的位数决定可寻址的最大地址空间控制总线(读/写)指出总线周期的类型和本次输入/输出完成的时刻 但是实际中存储芯片往往很小难以满足地址和数据的位数需求,此…...
这份【互联网项目全流程表】,实在是泰裤辣!!!
互联网行业是一个快速变化的行业,作为半个互联网人。太明白用户和环境每天都在不停地变化是什么感受了。 从项目开始到项目结束,要经历立项、计划、执行、结项,项目一周一个,一周一个。(**的)为了省时间…...
JAVA医院管理云HIS统计报表子系统、系统管理字系统功能实现
一、统计报表子系统 统计报表子系统功能模块:包括门诊收入汇总、住院收入汇总、收费统计报表、收费明细报表、 缴款日报、门诊收费汇总、住院科室日志、住院结算汇总、医疗项目统计、检查项目统计、 检验项目统计、月末收支汇总、药品进销存统计。 (1…...
5.Java中抽象类和接口
抽象类与接口 相同不同先从抽象类说起再从接口说起 相同 1.两者都不能实例化,因为他们都不全。(例如可以实例化一个苹果,但是不能实例化水果) 2.一个类可以实现多个接口,但是只能继承一个抽象类 3.如果这个类实现了接…...
中国平安将在2023年出现转机,复苏才刚刚开始
来源:猛兽财经 作者:猛兽财经 在解封后股价出现短暂反弹之后,由于市场担忧中国平安(02318)人寿保险部门新业务NBV(用于衡量寿险公司新业务价值的一个重要指标,当一家保险公司的NBV指标越高,那么说明每新增…...
CUDA编程(六):代码分析与调试
CUDA编程(六):代码分析与调试 代码分析与调试方法使用printf打印变量信息使用CUDA的错误检查功能使用CUDA-GDB进行调试使用Nsight进行调试使用nvprof / nvvp工具 参考文献 代码分析与调试方法 CUDA代码的运行时可能会遇到内存溢出、内存非法…...
身份鉴别解读与技术实现分析(1)
6.1.4.1 身份鉴别 本项要求包括: a) 应对登录的用户进行身份标识和鉴别,身份标识具有唯一性,身份鉴别信息具有复杂度要求并定期更换; b) 应具有登录失败处理功能,应配置并启用结束会话、限制非法登录次数和当登录连接超时自动退出等相关措施 在等级保护体系中,级别越高…...
为什么说7.38万的比亚迪海鸥比仰望更重要
出品 | 何玺 排版 | 叶媛 售价7.38万元起步、速度却能上130迈。注意看,这就是A0级轿车中的“新皇”—比亚迪海鸥。 出乎车圈事前的意料,海鸥这款A0级车型,在上海车展里获得的人气和追捧并不逊色于百万豪车仰望。 01 比亚迪海鸥࿰…...
【LLM】低成本部署大语言模型, 并且还能达到部署在GPU上差不多的效果
目录 前言 部署 效果 问题1:人类为什么需要睡觉? 问题2:世界上最高的山峰是什么? 前言 点进来看本文的应该都知道模型对硬件的要求很高, 那我也不废话了, 直接安排最近发现的一个开源项目, 它可以帮助我们降低部署模型的成…...
Doris(25):Doris的函数—Bitmap函数
1 BITMAP_AND(BITMAP lhs, BITMAP rhs) 计算两个输入bitmap的交集,返回新的bitmap. select bitmap_count(bitmap_and(to_bitmap(1), to_bitmap(2))) cnt; select bitmap_count(bitmap_and(to_bitmap(1), to_bitmap(1))) cnt; 2 BITMAP_CONTAINS(BITMAP bitmap, BIGINT input…...
现在帮别人做网站赚钱不/免费seo技术教程
点击上方 “ 程序IT圈 ”,选择“置顶公众号”工作日每天早晨7点半准点推文打卡签到本文来源于公号:Java后端技术大家周末好!每到周末,就想跟大家分享一些干货,知道大家周末都很有时间,所以今天想跟你推荐来…...
慈溪网站建设哪家好/广州网站营销seo
首先需要声明,本文纯属一个毫无远见和真才实学的小小散户的愚昧见解,仅供参考。 上交所 http://www.sse.com.cn/ A股全市场行业市盈率(A股市场主要板块市盈率) http://www.csindex.com.cn/sseportal/csiportal/hy_syl/syl.jsp 上海市场A股市盈率 h…...
东莞微信网站建设怎样/百度知道合伙人答题兼职
作为过来人这个报错之前出现过好多次,但还是记录一下怎么解决这个问题 删除node-modules(快速删除node-modules之前有做记录),然后在重新instll 一遍就好了...
网站设计原则的第三要素/公司网站首页设计
在异步清除中,利用vue 中data存放setTimeout的标识进行清除时,无法清除。则需要在函数前加上window.即可如window.setTimeout与window.clearTimeout具体代码如下精简后的代码。环境为electron-vue 渲染进程异步获取主进程上html并渲染到页面、过程中需要…...
网站界面设计说明/站牛网是做什么的
构建这里搜集了用来构建应用程序的工具。Apache Maven:Maven使用声明进行构建并进行依赖管理,偏向于使用约定而不是配置进行构建。Maven优于Apache Ant。后者采用了一种过程化的方式进行配置,所以维护起来相当困难。Gradle:Gradle…...
网络开发语言的有哪些/湛江seo推广公司
前言在实际开发中分页查询是最常用的场景之一,但也通常也是最容易出问题的地方。DBA的同事给出的解决方法就是加“索引/组合索引”,例如在name,create_time,status等字段上加组合索引,这样根据这些条件查询的时候能够有效的利用索引ÿ…...