精华内容
下载资源
问答
  • 如果使用了其他数据类型,查询将不会使用向量化执行,而是每次只会查询一行数据。 可以通过explain来查看查询是否使用了向量化,如果输出信息中Execution mode的值为vectorized,则使用了向量化查询: explain ...

    什么是向量化查询执行

    在标准的查询执行系统中,每次只处理一行数据,每次处理都要走过较长的代码路径和元数据解释,从而导致CPU使用率非常低。

    而在向量化查询执行中,每次处理包含多行记录的一批数据,每一批数据中的每一列都会被存储为一个向量(一个原始数据类型的数组),这就极大地减少了执行过程中的方法调用、反序列化和不必要的if-else操作,大大减少CPU的使用时间。

    如下图所示:
    vector array
    上图中可以看出,数据加载出来之后,每批数据中的每一列都会转成一个向量,在后续的执行过程中,数据是一批批的从一个操作符流经另一个操作符,而不是一行行的。
    batch
    但是,向量化查询执行有一个限制,就是我们必须把要查询的数据存储为列式格式。比如

    • 磁盘列式存储格式:ORC、Parquet
    • 内存列式存储格式:Arrow

    列式存储

    列式存储与行式存储将数据按行进行存储不同的是,它将数据以每列进行组织。如下图:
    在这里插入图片描述
    列式存储的优势:

    1. 相同类型的数据放在一起进行存储,可以有更高的压缩率,减少了磁盘占用。
    2. 只返回指定查询的列,而不用返回整行记录之后再取出指定查询的列,最小化了I/O操作。

    了解了列式存储的存储格式,我们就很容易明白,在使用列式存储格式的情况下,向量化查询才能方便地将每批数据中的每列值进行向量化。

    Spark向量化查询执行

    Spark支持三种形式的向量化查询:

    1. 内存列式存储
      spark.sql.inMemoryColumnarStorage.enableVectorizedReader:为内存列式存储(比如前面提到的Apache Arrow)启用向量化读取,默认为true,从Spark 2.3.1开始支持此配置。
    2. Parquet格式
      spark.sql.parquet.enableVectorizedReader:为parquet格式启用向量化查询,默认为true,从Spark 2.0.0开始支持此配置。
    3. ORC格式
      spark.sql.orc.enableVectorizedReader:为ORC格式启用向量化查询,默认为true,从Spark 2.3.0开始支持此配置。

    Hive向量化查询执行

    Hive中,向量化查询执行在Hive 0.13.0及以后版本可用,默认情况下是关闭的,可通过下面配置启用:

    set hive.vectorized.execution.enabled = true;
    

    Hive向量化执行支持数据类型有:tinyint、smallint、int、bigint、boolean、float、double、decimal、date、timestamp、string。

    如果使用了其他数据类型,查询将不会使用向量化执行,而是每次只会查询一行数据。

    可以通过explain来查看查询是否使用了向量化,如果输出信息中Execution mode的值为vectorized,则使用了向量化查询:

    explain select count(*) from vectorizedtable;
    
    // explain输出信息
    STAGE PLANS:
      Stage: Stage-1
        Map Reduce
          Alias -> Map Operator Tree:
          ...
          Execution mode: vectorized
          Reduce Operator Tree
          ... 
    ... 
    

    参考

    展开全文
  • ClickHouse在计算层做了非常细致的工作,竭尽所能榨干硬件能力,提升查询速度。它实现了单机多核并行、分布式计算、向量化执行与SIMD指令、代码生成等多种重要技术。多核并行ClickH...

    ClickHouse在计算层做了非常细致的工作,竭尽所能榨干硬件能力,提升查询速度。它实现了单机多核并行、分布式计算、向量化执行与SIMD指令、代码生成等多种重要技术。

    多核并行

    ClickHouse将数据划分为多个partition,每个partition再进一步划分为多个index granularity,然后通过多个CPU核心分别处理其中的一部分来实现并行数据处理。

    在这种设计下,单条Query就能利用整机所有CPU。极致的并行处理能力,极大的降低了查询延时。

    分布式计算

    除了优秀的单机并行处理能力,ClickHouse还提供了可线性拓展的分布式计算能力。ClickHouse会自动将查询拆解为多个task下发到集群中,然后进行多机并行处理,最后把结果汇聚到一起。

    向量化执行与SIMD

    ClickHouse不仅将数据按列存储,而且按列进行计算。传统OLTP数据库通常采用按行计算,原因是事务处理中以点查为主,SQL计算量小,实现这些技术的收益不够明显。但是在分析场景下,单个SQL所涉及计算量可能极大,将每行作为一个基本单元进行处理会带来严重的性能损耗:

    •对每一行数据都要调用相应的函数,函数调用开销占比高;

    •存储层按列存储数据,在内存中也按列组织,但是计算层按行处理,无法充分利用CPU cache的预读能力,造成CPU Cache miss严重;•按行处理,无法利用高效的SIMD指令;

    ClickHouse实现了向量执行引擎(Vectorized execution engine),对内存中的列式数据,一个batch调用一次SIMD指令(而非每一行调用一次),不仅减少了函数调用次数、降低了cache miss,而且可以充分发挥SIMD指令的并行能力,大幅缩短了计算耗时。向量执行引擎,通常能够带来数倍的性能提升。

    What IS SIMD ?

    SIMD

    即 single instruction multiple data 英文首字母缩写,单指令流多数据流,也就是说一次运算指令可以执行多个数据流,一个简单的例子就是向量的加减。

    SSE 与 SMID 关系

    SSE(为Streaming SIMD Extensions的缩写)是由 Intel公司在1999年推出Pentium III处理器时,同时推出的新指令集。如同其名称所表示的,SSE是一种SIMD指令集。SSE有8个128位寄存器,XMM0 ~XMM7。可以用来存放四个32位的单精确度浮点数。可以看出,SSE 是一套专门为 SIMD(单指令多数据)架构设计的指令集。通过它,用户可以同时在多个数据片段上执行运算,实现数据并行(aka:矢量处理)。

    SSE2是SSE指令的升级版,寄存器与指令格式都和SSE一致,不同之处在于其能够处理双精度浮点数等更多数据类。SSE3增加了13条新的指令。

    参考:https://www.cnblogs.com/xidian-wws/p/11023762.html

    C++使用SIMD编程的3种方法

    SIMD指令集的使用,有如下三种方式:

    编译器优化 即使用C/C++编写程序之后,带有SIMD优化选项编译,在CPU支持的情况下,编译器按照自己的规则去优化。•使用intrinsic指令 参考Intel手册,针对SIMD指令,可以在编程时直接使用其内置的某些库函数,编译的时候在cpu和编译器的支持下会生成对应的SIMD指令。比如:double _mm_cvtsd_f64 (__m128d a) 该函数编译时就会翻译成指令:movsd•嵌入式汇编 内联汇编直接在程序中嵌入对应的SIMD指令。

    Intrinsics头文件与SIMD指令集、Visual Studio版本对应表

    VS和GCC都支持SSE指令的Intrinsic,SSE有多个不同的版本,其对应的Intrinsic也包含在不同的头文件中,如果确定只使用某个版本的SSE指令则只包含相应的头文件即可。

    例如,要使用SSE3,则

    #include <tmmintrin.h>
    

    如果不关心使用那个版本的SSE指令,则可以包含所有

    #include <intrin.h>
    

    参考资料:https://www.cnblogs.com/huaping-audio/p/4115890.html

    简单运算的Intrinsic和SSE指令对比 使用Intrinsic函数的代码:

      __m128 a1, b2;
      __m128 c1;
     for (int i = 0; i < count; i++)
     {
          a1 = _mm_load_ps(a);
          b2 = _mm_load_ps(b);
          c1 = _mm_add_ps(a1,  b2);
      }
    

    对应汇编指令代码:

       for(int i = 0; i < count; i ++)
        _asm
        {
            movaps  xmm0, [a];
            movaps  xmm1, [b];
            addps  xmm0, xmm1;
        }
    

    简要说明其中一种操作:

    addps XMM,XMM/m128 源存储器内容按双字对齐,共4个单精度浮点数与目的寄存器相加,结果送入目的寄存器

    计算机硬件支持与编译器支持

    要能够使用 Intel 的 SIMD 指令集,不仅需要当前 Intel 处理器的硬件支持,还需要编译器的支持。

    $ grep -q sse4_2 /proc/cpuinfo && echo "SSE 4.2 supported" || echo "SSE 4.2 not supported"
    

    如果你的机器支持SSE4.2,那么,将打印:

    SSE 4.2 supported
    

    使用SIMD考量

    利用优点: 频繁调用的基础函数,大量的可并行计算•尽量避免: SSE指令集对分支处理能力非常的差,而且从128位的数据中提取某些元素数据的代价又非常的大,因此不适合有复杂逻辑的运算。

    How Clickhouse USE SIMD ?

    大家在搜索CLICKHOUSE为什么快的文章中,都提到了CH使用到的技术列式存储,压缩,向量引擎。

    CH在所有能够提高CPU计算效率的地方,都大量的使用了SIMD。

    本文以clickhouse其中的一个简单的LowerUpperImpl函数为例(这个函数完成大小写转换)。

    测试产出SIMD模式与非SIMD模式下benchmark的效率对比。

    code如下,关键节点已加注释:

      template <char not_case_lower_bound, char not_case_upper_bound>
    struct LowerUpperImpl
    {
    public:
       static void array( char * src, char * src_end, char * dst)
       {
           //32
           const auto flip_case_mask = 'A' ^ 'a';
    #ifdef __SSE2__
           const auto bytes_sse = sizeof(__m128i);
           const auto src_end_sse = src_end - (src_end - src) % bytes_sse;
           const auto v_not_case_lower_bound = _mm_set1_epi8(not_case_lower_bound - 1);
           const auto v_not_case_upper_bound = _mm_set1_epi8(not_case_upper_bound + 1);
           const auto v_flip_case_mask = _mm_set1_epi8(flip_case_mask);
           for (; src < src_end_sse; src += bytes_sse, dst += bytes_sse)
           {
               //_mm_loadu_si128表示:Loads 128-bit value;即加载128位值。
               //一次性加载16个连续的8-bit字符
               const auto chars = _mm_loadu_si128(reinterpret_cast<const __m128i *>(src));
               //_mm_and_si128(a,b)表示:将a和b进行与运算,即r=a&b
               //_mm_cmpgt_epi8(a,b)表示:分别比较a的每个8bits整数是否大于b的对应位置的8bits整数,若大于,则返回0xff,否则返回0x00。
               //_mm_cmplt_epi8(a,b)表示:分别比较a的每个8bits整数是否小于b的对应位置的8bits整数,若小于,则返回0xff,否则返回0x00。
               //下面的一行代码对这128位的寄存器并行操作了3遍,最后得到一个128位数,对应位置上是0xff的,表示
               //那个8-bit数在 [case_lower_bound, case_upper_bound]范围之内的,其余的被0占据的位置,是不在操作范围内的数。
               const auto is_not_case
                   = _mm_and_si128(_mm_cmpgt_epi8(chars, v_not_case_lower_bound), _mm_cmplt_epi8(chars, v_not_case_upper_bound));
               //每个0xff位置与32进行与操作,原来的oxff位置变成32,也就是说,每个在 [case_lower_bound, case_upper_bound]范围区间的数,现在变成了32,其他的位置是0
               const auto xor_mask = _mm_and_si128(v_flip_case_mask, is_not_case);
               //将源chars内容与xor_mask进行异或,符合条件的字节可能从uppercase转为lowercase,也可能从lowercase转为uppercase,不符合区间的仍保留原样。
               const auto cased_chars = _mm_xor_si128(chars, xor_mask);
               //将结果集存到dst中
               _mm_storeu_si128(reinterpret_cast<__m128i *>(dst), cased_chars);
           }
    #endif
    #ifndef __SSE2__
           for (; src < src_end; ++src, ++dst)
               if (*src >= not_case_lower_bound && *src <= not_case_upper_bound)
                   *dst = *src ^ flip_case_mask;
               else
                   *dst = *src;
    #endif
       }
    };
    

    完整代码参考 这里[1]

    测试结果如下:

    32位输入:

    root@2458d1317fc8:/var/tmp# g++ -std=c++11 -Wall -pedantic -pthread sse.cpp && ./a.out
    new des is abcdefghabcdefghabcdefghabcdefgh
    花费了6.8059秒
    root@2458d1317fc8:/var/tmp# g++ -std=c++11 -Wall -pedantic -pthread nosse.cpp && ./a.out
    new des is abcdefghabcdefghabcdefghabcdefgh
    花费了9.39051秒
    

    64位输入:

    root@2458d1317fc8:/var/tmp# g++ -std=c++11 -Wall -pedantic -pthread sse.cpp && ./a.out
    new des is abcdefghabcdefghabcdefghabcdefghabcdefghabcdefghabcdefghabcdefgh
    花费了9.26642秒
    root@2458d1317fc8:/var/tmp# g++ -std=c++11 -Wall -pedantic -pthread nosse.cpp && ./a.out
    new des is abcdefghabcdefghabcdefghabcdefghabcdefghabcdefghabcdefghabcdefgh
    花费了17.3588秒
    

    128位输入:

    root@2458d1317fc8:/var/tmp# g++ -std=c++11 -Wall  -pedantic -pthread sse.cpp && ./a.out
    new des is abcdefghabcdefghabcdefghabcdefghabcdefghabcdefghabcdefghabcdefghabcdefghabcdefghabcdefghabcdefghabcdefghabcdefghabcdefghabcdefgh
    花费了10.2672秒
    root@2458d1317fc8:/var/tmp# g++ -std=c++11 -Wall  -pedantic -pthread nosse.cpp && ./a.out
    new des is abcdefghabcdefghabcdefghabcdefghabcdefghabcdefghabcdefghabcdefghabcdefghabcdefghabcdefghabcdefghabcdefghabcdefghabcdefghabcdefgh
    花费了31.7568秒
    

    这只是其中一个简单的函数。但,为什么Clickhouse快?管中窥豹,可见一斑。

    Clickhouse 仅短短几年在OLAP领域横空出世,这和Clickhouse在设计和细节上追求极致密不可分。

    对于俄罗斯人,开源一款产品可是大事。但不开源还则罢了。一旦开源,必是行业大事。一如nginx。

    本文转载自:https://www.jianshu.com/p/fc384f18ff1a,作者:金科_

    引用链接

    [1] 这里: https://github.com/Johnny-Three/clickhousedive/blob/master/main.cpp

    展开全文
  • 前言 ClickHouse之所以会像闪电一样快("blazing ...另外,ClickHouse为了最大限度地压榨硬件——尤其是CPU——的性能,实现了向量化查询执行(vectorized query execution)机制。这个名词相对于上面的那些可能没...

    前言

    ClickHouse之所以会像闪电一样快("blazing fast"),是多方面优化的结果,包括且不限于:高效且磁盘友好的列式存储,高效的数据压缩,精心设计的各类索引,并行分布式查询,运行时代码生成等。

    另外,ClickHouse为了最大限度地压榨硬件——尤其是CPU——的性能,实现了向量化查询执行(vectorized query execution)机制。这个名词相对于上面的那些可能没那么平易近人,但它毫无疑问是CK相对于传统OLAP引擎的大杀器。鉴于现有资料中讲解CK向量化执行的内容很少,本文就来试图探究一下,先从基础知识SIMD说起。

    SIMD

    其实在之前讲解二进制位计数的SWAR算法时,SIMD这个词就已经出现过一次了,这里多说两句。

    SIMD即"single instruction, multiple data"(单指令流多数据流),是Flynn分类法对计算机的四大分类之一。它本质上是采用一个控制器来控制多个处理器,同时对一组数据中的每一条分别执行相同的操作,从而实现空间上的并行性的技术。

    可见,“单指令流”指的是同时只能执行一种操作,“多数据流”则指的是在一组同构的数据(通常称为vector,即向量)上进行操作,如下图所示,PU=processing unit。

    SIMD在现代计算机的应用甚广泛,最典型的则是在GPU的像素处理流水线中。举个例子,如果要更改一整幅图像的亮度,只需要取出各像素的RGB值存入向量单元(向量单元很宽,可以存储多个像素的数据),再同时将它们做相同的加减操作即可,效率很高。SIMD和MIMD流水线是GPU微架构的基础,就不再展开聊了。

    话说回来,CPU是如何实现SIMD的呢?答案是扩展指令集。Intel的第一版SIMD扩展指令集称为MMX,于1997年发布。后来至今的改进版本有SSE(Streaming SIMD Extensions)、AVX(Advanced Vector Extensions),以及AMD的3DNow!等。ClickHouse的向量化执行机制主要依赖于SSE指令集,下面简要介绍之。

    SSE指令集

    SSE指令集是MMX的继任者,其第一版早在Pentium III时代就被引入了。随着新指令的扩充,又有了SSE2、SSE3、SSSE3、SSE4(包含4.1和4.2)等新版本。我们可以通过cpuid类软件获得处理器对SSE指令集的支持信息,下图以笔者自用MacBook Pro中的Intel Core i9-9880H为例。

    并不仅有Intel的处理器才支持SSE指令集,AMD的同样也支持。下图以笔者游戏PC中的AMD Ryzen 5 3600为例。

    ClickHouse提供的检查CPU是否支持SSE4.2的命令如下。

    grep -q sse4_2 /proc/cpuinfo && echo "SSE 4.2 supported" || echo "SSE 4.2 not supported"

    SSE指令集以8个128位寄存器为基础,命名为XMM0~XMM7。在AMD64(即64位扩展)指令集中,又新增了XMM8~XMM15。一个XMM寄存器原本只能存储一种数据类型:

    • 4个32位单精度浮点数

    SSE2又扩展到能够存储以下类型:

    • 2个64位双精度浮点数
    • 2个64位/4个32位/8个16位整数
    • 16个字节或字符

    SSE的指令分为两大类,一是标量(scalar)指令,二是打包(packed)指令。标量指令只对XMM寄存器中的最低位数据进行计算,打包指令则是对所有数据进行计算。下图示出SSE1中,单精度浮点数乘法的标量和打包运算。

    图来自http://www.songho.ca/misc/sse/sse.html,是一篇很好的SSE入门

    观察指令名称,mul表示乘法,接下来的s表示标量,p表示打包,最后一个s则表示类型为单精度浮点数(single-precision)。由图也可以发现,打包指令才是真正SIMD的,而标量指令是SISD的。

    再举个小栗子,如果我们要实现两个4维向量v1和v2的加法,只需要三条SSE指令就够了。

    movaps xmm0, [v1] ;xmm0 = v1.w | v1.z | v1.y | v1.x 
     addps xmm0, [v2]  ;xmm0 = v1.w+v2.w | v1.z+v2.z | v1.y+v2.y | v1.x+v2.x
     movaps [vec_res]  ;xmm0

    注意数据移动指令movaps中的a表示对齐(align)。第一条指令的意思就是通过[v1]直接寻址得到向量的起点,并分别按照0、4、8、16字节的偏移量写入XMM0寄存器的低到高四个域。在数据本身已经按照16字节对齐的情况下,调用这种指令效率非常高。从寄存器写入内存也是同理的,如下图。

    那么如何利用SSE指令集呢?主要有以下3种方法:

    • 直接编写(内嵌)汇编语句;
    • 利用厂商提供的扩展库函数。Intel将这类指令和函数统称为intrinsics,官方提供的速查手册见这里
    • 开启编译器的优化(-msse-msse2等等),编译器会自动将符合条件的情景(如数组相加、矩阵相乘等)编译为intrinsic指令。

    需要注意的是,SIMD和SSE虽然强大,但是对于那些严重依赖流程控制(flow-control-heavy)的任务,即有大量分支、跳转和条件判断的任务明显不太适用。也就是说,它们主要被用来优化可并行计算的简单场景,以及可能被频繁调用的基础逻辑。

    说了这么多,可以进入ClickHouse的世界了。

    ClickHouse向量化执行示例

    编译器优化对笔者这种水平不高的人来说显然太难,所以还是去ClickHouse源码中寻找向量化执行的蛛丝马迹比较好。我们可以查找形如#ifdef __SSE2__的宏定义,或者根据手册查找intrinsic函数对应的头文件,如SSE4.1的头文件是<smmintrin.h>,以此类推。

    为简单起见,选取两段应用了SSE2 intrinsics函数的示例来作分析。

    计算Filter中1的数量

    在ClickHouse的底层,过滤器(Filter)是一个预分配空间的、无符号8位整形数的数组,用于表示WHERE和HAVING子句的条件及真值,每一位的取值为0或1,即表示条件为假或真。Filter和列(IColumn)是共生的,在ColumnsCommon.cpp中,提供了通用的计算Filter中1的数量的方法,代码如下。

    size_t countBytesInFilter(const IColumn::Filter & filt)
    {
        size_t count = 0;
    
        /** NOTE: In theory, `filt` should only contain zeros and ones.
          * But, just in case, here the condition > 0 (to signed bytes) is used.
          * It would be better to use != 0, then this does not allow SSE2.
          */
    
        const Int8 * pos = reinterpret_cast<const Int8 *>(filt.data());
        const Int8 * end = pos + filt.size();
    
    #if defined(__SSE2__) && defined(__POPCNT__)
        const __m128i zero16 = _mm_setzero_si128();
        const Int8 * end64 = pos + filt.size() / 64 * 64;
    
        for (; pos < end64; pos += 64)
            count += __builtin_popcountll(
                static_cast<UInt64>(_mm_movemask_epi8(_mm_cmpgt_epi8(
                    _mm_loadu_si128(reinterpret_cast<const __m128i *>(pos)),
                    zero16)))
                | (static_cast<UInt64>(_mm_movemask_epi8(_mm_cmpgt_epi8(
                    _mm_loadu_si128(reinterpret_cast<const __m128i *>(pos + 16)),
                    zero16))) << 16)
                | (static_cast<UInt64>(_mm_movemask_epi8(_mm_cmpgt_epi8(
                    _mm_loadu_si128(reinterpret_cast<const __m128i *>(pos + 32)),
                    zero16))) << 32)
                | (static_cast<UInt64>(_mm_movemask_epi8(_mm_cmpgt_epi8(
                    _mm_loadu_si128(reinterpret_cast<const __m128i *>(pos + 48)),
                    zero16))) << 48));
    
        /// TODO Add duff device for tail?
    #endif
    
        for (; pos < end; ++pos)
            count += *pos > 0;
    
        return count;
    }

    defined(__SSE2__)说明当前环境支持SSE2指令集,而defined(__POPCNT__)说明支持硬件级位计数的POPCNT指令。下面根据手册简要介绍一下代码中涉及到的intrinsic函数:

    • _mm_setzero_si128():初始化128位(16字节)的全0位图,即一个XMM寄存器。
    • _mm_loadu_si128(mem_addr):从内存地址mem_addr处加载128位的整形数据。
    • _mm_cmpgt_epi8(a, b):按8位比较a和b两个128位整形数,若a的对应8位比b的对应8位大,则填充对应位为全1,否则填充全0。
    • _mm_movemask_epi8(a):根据128位整形数a的每个8位组的最高位创建掩码,一共16位长,返回int结果(高16位用0填充)。

    最后,__builtin_popcountll()函数相当于直接调用POPCNT指令算出64位数的汉明权重。

    由上可见,这个函数的每次循环都将连续64个Filter的真值数据(即Int8类型)压缩到一个UInt64中一起做位计数。其中每次调用上述指令都会处理16个Int8,正好是128位,SIMD的思想就是这样体现出来的。由于SSE指令集中没有真正的位运算指令,所以压缩的过程略显繁琐,但是仍然比笨方法(逐个遍历判断)效率高很多。

    字符串大小写转换

    ClickHouse的函数中也充分应用了SSE指令集,特别是字符串函数。以ASCII拉丁字符大小写转换函数(即toLower()toUpper())为例,其源码如下,位于LowerUpperImpl.h文件中。

    template <char not_case_lower_bound, char not_case_upper_bound>
    struct LowerUpperImpl
    {
    // 略去
    private:
        static void array(const UInt8 * src, const UInt8 * src_end, UInt8 * dst)
        {
            const auto flip_case_mask = 'A' ^ 'a';
    
    #ifdef __SSE2__
            const auto bytes_sse = sizeof(__m128i);
            const auto src_end_sse = src_end - (src_end - src) % bytes_sse;
    
            const auto v_not_case_lower_bound = _mm_set1_epi8(not_case_lower_bound - 1);
            const auto v_not_case_upper_bound = _mm_set1_epi8(not_case_upper_bound + 1);
            const auto v_flip_case_mask = _mm_set1_epi8(flip_case_mask);
    
            for (; src < src_end_sse; src += bytes_sse, dst += bytes_sse)
            {
                /// load 16 sequential 8-bit characters
                const auto chars = _mm_loadu_si128(reinterpret_cast<const __m128i *>(src));
    
                /// find which 8-bit sequences belong to range [case_lower_bound, case_upper_bound]
                const auto is_not_case
                    = _mm_and_si128(_mm_cmpgt_epi8(chars, v_not_case_lower_bound), _mm_cmplt_epi8(chars, v_not_case_upper_bound));
    
                /// keep `flip_case_mask` only where necessary, zero out elsewhere
                const auto xor_mask = _mm_and_si128(v_flip_case_mask, is_not_case);
    
                /// flip case by applying calculated mask
                const auto cased_chars = _mm_xor_si128(chars, xor_mask);
    
                /// store result back to destination
                _mm_storeu_si128(reinterpret_cast<__m128i *>(dst), cased_chars);
            }
    #endif
    
            for (; src < src_end; ++src, ++dst)
                if (*src >= not_case_lower_bound && *src <= not_case_upper_bound)
                    *dst = *src ^ flip_case_mask;
                else
                    *dst = *src;
        }
    };

    原理比较简单,就是利用flip_case_mask这个掩码来翻转字符的大小写(大小写字母的ASCII码值相差32)。not_case_lower_bound和not_case_lower_bound则用来标定转换的字符范围,比如a~z或A~Z。不过在SSE2的加持下,就可以一次性加载16个字符进行转换,同样是SIMD的思想,效率自然比普通的遍历高。由于每句话都有官方注释,就不再多废话了。

    测试一下

    将上面的LowerUpperImpl结构体拆出来,测试代码如下。

    #include <iostream>
    #include <string>
    #include <vector>
    #include <chrono>
    using namespace std;
    using namespace std::chrono;
    
    #ifdef __SSE2__
    #include <emmintrin.h>
    #endif
    
    template <char not_case_lower_bound, char not_case_upper_bound>
    struct LowerUpperImpl {
      public:
      static void arraySSE(const char * src, const char * src_end, char * dst) {
        const auto flip_case_mask = 'A' ^ 'a';
    
    #ifdef __SSE2__
        const auto bytes_sse = sizeof(__m128i);
        const auto src_end_sse = src_end - (src_end - src) % bytes_sse;
    
        const auto v_not_case_lower_bound = _mm_set1_epi8(not_case_lower_bound - 1);
        const auto v_not_case_upper_bound = _mm_set1_epi8(not_case_upper_bound + 1);
        const auto v_flip_case_mask = _mm_set1_epi8(flip_case_mask);
    
        for (; src < src_end_sse; src += bytes_sse, dst += bytes_sse) {
          const auto chars = _mm_loadu_si128(reinterpret_cast<const __m128i *>(src));
    
          const auto is_not_case
                  = _mm_and_si128(_mm_cmpgt_epi8(chars, v_not_case_lower_bound), _mm_cmplt_epi8(chars, v_not_case_upper_bound));
    
          const auto xor_mask = _mm_and_si128(v_flip_case_mask, is_not_case);
    
          const auto cased_chars = _mm_xor_si128(chars, xor_mask);
    
          _mm_storeu_si128(reinterpret_cast<__m128i *>(dst), cased_chars);
        }
    #endif
    
        for (; src < src_end; ++src, ++dst)
          if (*src >= not_case_lower_bound && *src <= not_case_upper_bound)
            *dst = *src ^ flip_case_mask;
          else
            *dst = *src;
      }
    
      static void arrayNoSSE(const char * src, const char * src_end, char * dst) {
        const auto flip_case_mask = 'A' ^ 'a';
        for (; src < src_end; ++src, ++dst)
          if (*src >= not_case_lower_bound && *src <= not_case_upper_bound)
            *dst = *src ^ flip_case_mask;
          else
            *dst = *src;
      }
    };
    
    int main() {
      char src[261] = {'\0'};
      char dst[261] = {'\0'};
    
      for (int i = 0; i < 10; i++) {
        for (int j = 0; j < 26; j++) {
          src[i * 26 + j] = 'a' + j;
        }
      }
    
      LowerUpperImpl<'a', 'z'> lowerUpper;
    
      auto start1 = system_clock::now();
      for (int i = 0; i < 100; i++) {
        lowerUpper.arraySSE(&src[0], &src[261], &dst[0]);
      }
      auto end1 = system_clock::now();
      cout << dst << endl;
      auto duration1 = duration_cast<nanoseconds>(end1 - start1);
      cout << "Time cost: " << duration1.count() << " ns" << endl;
    
      auto start2 = system_clock::now();
      for (int i = 0; i < 100; i++) {
        lowerUpper.arrayNoSSE(&src[0], &src[261], &dst[0]);
      }
      auto end2 = system_clock::now();
      cout << dst << endl;
      auto duration2 = duration_cast<nanoseconds>(end2 - start2);
      cout << "Time cost: " << duration2.count() << " ns" << endl;
    }

    很简单,就是将a~z重复10遍作为源字符串,将其分别用SSE和普通方式转换成大写100次,结果如下。

    /Users/lmagic/workspace/CLionProjects/ssetest/cmake-build-debug/ssetest
    ABCDEFGHIJKLMNOPQRSTUVWXYZABCDEFGHIJKLMNOPQRSTUVWXYZABCDEFGHIJKLMNOPQRSTUVWXYZABCDEFGHIJKLMNOPQRSTUVWXYZABCDEFGHIJKLMNOPQRSTUVWXYZABCDEFGHIJKLMNOPQRSTUVWXYZABCDEFGHIJKLMNOPQRSTUVWXYZABCDEFGHIJKLMNOPQRSTUVWXYZABCDEFGHIJKLMNOPQRSTUVWXYZABCDEFGHIJKLMNOPQRSTUVWXYZ
    Time cost: 18000 ns
    ABCDEFGHIJKLMNOPQRSTUVWXYZABCDEFGHIJKLMNOPQRSTUVWXYZABCDEFGHIJKLMNOPQRSTUVWXYZABCDEFGHIJKLMNOPQRSTUVWXYZABCDEFGHIJKLMNOPQRSTUVWXYZABCDEFGHIJKLMNOPQRSTUVWXYZABCDEFGHIJKLMNOPQRSTUVWXYZABCDEFGHIJKLMNOPQRSTUVWXYZABCDEFGHIJKLMNOPQRSTUVWXYZABCDEFGHIJKLMNOPQRSTUVWXYZ
    Time cost: 59000 ns

    经过多次测试,不使用SSE的版本的耗时总是使用SSE的版本的3倍多。鉴于ClickHouse在很多地方都渗透了SIMD和SSE,积少成多,效率提升自然就非常可观了。

    The End

    笔者并非精通C++和微处理器方面,写这篇文章只是觉得很有意思而已,看官随意看看就行了。

    民那晚安晚安。

    展开全文
  • 本文为大家介绍一下向量化执行引擎的引入原因,前提条件,架构实现以及它能够带来哪些收益。 希望读者能够通过对这篇文章阅读能够对向量化执行引擎的应用特征与架构有一个概要的认识。 关键字 向量化执行引擎, ...

    摘要

    本文为大家介绍一下向量化执行引擎的引入原因,前提条件,架构实现以及它能够带来哪些收益。 希望读者能够通过对这篇文章阅读能够对向量化执行引擎的应用特征与架构有一个概要的认识。

    关键字

    向量化执行引擎, MonetDB,Tuple, 顺序访问,随机访问, OLAP, MPP,火山模型,列存表,编译执行

    背景介绍

    过去的20-30年计算机硬件能力的持续发展,使得计算机的计算能力飞速提升。然后,我们很多的应用却没有做到足够的调整到与硬件能力配套的程度,因此也就不能够充分的将计算机强大的计算能力转换为软件的生产力。这样的问题在今天的通用数据库系统中也是一个比较突出的问题,因为这些通用数据库系统往往都已经有十数年或者几十年的历史了,它们也存在着不能够充分利用现在硬件能力的情况。

    为什么会出现向量化执行引擎

    制约数据库系统利用硬件能力的因素

    • 查询执行模型 传统的数据库查询执行都是采用一次一tuple的pipleline执行模式。这样CPU的大部分处理时不是用来真正的处理数据,而是在遍历查询操作树,这样CPU的有效利用率不高。同时这也会导致低指令缓存性能和频繁跳转。更加糟糕的是,这种方式的执行,不能够利用到现在新硬件的新的能力来加速查询的执行。 关于执行引擎这块,当前有一另外一个解决方案就是改变一次一tuple 为一次一列的模式。这也是我们向量化执行引擎的一个基础。在本文后面的部分会为大家详细介绍。

    • 存储 从存储层面上来看,磁盘读写能力的提升并没有CPU硬件计算能力提升的那么迅速,加上通常数据库在对于随机访问的支持,对于数据的存放位置没有做特殊的要求。目前对于磁盘来说,顺序读取的效率是比随机读取的效率要高的。但是通常数据库很多数据存储都更倾向(或者说在运行了一段时间以后)数据是处于随机存放的状态。 另一方面,目前磁盘读写能力已经远远的跟不上CPU数据执行的速度了。这种状况有一种解决方案就是使用列存储方案。因为列存储能够最大化的利用磁盘的读写能力,来提升IO带宽。

    • 列存简介 这里我们也顺便给大家简单介绍一下列存储的一些特点以及优势,方便大家理解为什么向量化执行引擎必须要构架在列存储的表上才能够发挥出最大的优势。近年来,使用列存来实现存储的数据库这一技术成为,大型分析型数据越来越青睐的一种OLAP数据库的存储选型方案。 使用列存技术能够为查询的执行带来下列潜在的优势:

    1. 压缩能力的提升: 因为列存储技术在数据表的存储上使用数据表的列(记录的一个属性)为单位存储数据,这样类型一致的数据被放在一起,这样类似的数据在进行压缩的时候,能够达到一个比较好的压缩比。
    2. 减少I/O的读入总量: 因为列存按列为单位,这样,我们在读取数据的时候仅需要读入需要的列,相对于行存将所有数据读取上来再提取对应的属性,减少了I/O总量。
    3. 减少查询执行过程中的节点函数调用次数: 以Greenplum 为例,如果当前列存的每次以一个数据块(segment,通常一个数据块包含某列1024行值)返回给上层节点的话,会极大的减少函数调用次数,达到提升查询执行性能的效果。
    4. 向量化执行: 因为列存每列的各行数据存储在一起,可以认为这些数据是以数组的方式存储的,基于这样的特征,当该列数据需要进行某一同样操作,可以使用SIMD进一步提升计算效率,即便运算的机器上不支持SIMD, 也可以通过一个循环来高效完成对这个数据块各个值的计算。
    5. 延迟物化: 延迟物化是在整个查询的计算过程中,尽量使用列存储,这样可以进一步减少在各个查询计划树节点之间传递数据的总量。

    向量化执行引擎能够发挥效率的前提

    那么向量化执行引擎是不是针对所有的数据库场景都能够达到很好的效果呢?答案是否定的。要获得到向量化执行引擎的收益,是需要有一定的条件支持的:首先向量化执行引擎效率的发挥需要数据库能够提供列存表的支持。 对于传统的行存表来说,谈向量化执行是不可能的。通常向量化执行引擎都是用在OLAP数仓类系统,因为通常分析型系统通常都是数据处理密集型负载,基本上都是采用顺序方式来访问表中大部分的数据,然后进行计算,最后将计算结果输出给终端用户。对于典型的OLTP点查询,这种类型的查询执行,使用行存表反而比列存表更好。那么读到这里是不是觉得向量化执行引擎似乎本身限制也挺多的!没有它我是不是一样可以满足数据库用户的需要呢? 如果跟按照现在OLAP数仓系统数据容量动辄T 级别甚至P 级别,一条复杂报表查询的执行可能会用几千秒,如果使用向量化执行引擎能可以比原来的行存提升3-5倍的执行效率的话,也许原来不能被接受的查询时长,现在可以被接受了。 其次,向量化引擎本身应该如何实现呢? 目前主要有两种关于向量化执行引擎的实现方法,

    1. 仍然使用火山模型,只不过一次返回一组列。这种模型的优势是仍然使用(火山模型),这个优化器于执行器模型已经很成熟,剩下需要的工作量就在于如何将一次一tuple的处理模式,修改为一次向上返回一组列存行值(例如:100-1000行)处理方式,难度相对较小;
    2. 将整个模型改造成为层次型的执行模式,这种模式需要将优化好的执行计划树,最终转换为编译执行,即,一次调用下来之后,每一层都完成后才向上返回数据,这样能够最大程度的减少各层次节点间的调用次数。提高CPU的有效计算效率。这里我们称这种模型为编译执行模型。 后续会给大家对这两种模型进行更加详细的介绍

    向量化执行引擎的架构

    接下来我们将就之前讲的两种执行引擎来给大家在架构原理上来深入一些的了解向量化执行引擎。

    2017-01-15-yamin-pic1.png

    图1中描述的就是火山模型实现的行存执行引擎与列存执行引擎,其中左边代表的是当前比较流行的传统行存火山模型,右边代表的是列存实现的火山模型,从上图我们可以看到火山模式是从执行计划树的根节点开始向叶子节点递归调用,然后有叶子节点,通常是各种的扫描节点返回一条符合过滤条件的tuple 给上层节点处理,每一层节点在处理完该tuple之后继续网上层节点传递记录(Agg节点不是立刻往上层节点返回数据,它需要计算完所有的Tuple,才能继续往上层节点返回,所以这里AGG算子在处理好这个Tuple之后,又会往下调用扫描算子返回下一条符合过滤条件的记录)。这样处理完整个表的记录之后,AGG算子会把数据返回到上一层节点继续处理,在整个过程中需要AGG算子缓存中间结果。 右边列存执行引擎,执行逻辑基本上与左边行存执行引擎一致,但是每次扫描处理的是一组组以col组织的列数据集合,这样我们最为直观的观察就是从上层节点向下层节点的调用次数少了。相应的CPU的利用率得到了提高,另外数据被组织在一起。可以利用硬件发展带来的一些收益;如SIMD, 循环优化,将所有数据加载到CPU的缓存当中去,提高缓存命中率,提升效率。在列存储与向量化执行引擎的双重优化下,查询执行的速度会有一个非常巨大的飞跃大约3-5倍。后续我们会在技术实现的过程中给出更为详细的性能测试对比报告,敬请期待。

    2017-01-15-yamin-pic2.png

    图2 给我们现实的是火山模型的向量化执行引擎与编译执行的向量化执行引擎之间执行方式的对比。鉴于在图1部分已经介绍过了火山模型,在这里我们讲一下编译执行模型,这个模型也是从根节点开始往叶子节点调用,但是只调用一次,从叶子节点开始每一层都是执行完所有的操作之后,才向上返回结果。这样整颗执行计划树从跟节点到叶子节点只需要调用一次,彻底消除了因节点间函数调用而导致的CPU利用率不高的这个问题。 同样列存执行引擎所能够拿到的好处也是可以被编译执行模型使用。 但是这种模型有一个缺点就是每一个节点都需要将数据进行缓存,在数据量比较大的情况下,内存可能放不下这些数据,需要写盘,这样会造成额外的开销。

    向量化执行引擎的优势与需要注意的方面

    这部分我们主要给大家提一下向量化执行引擎的优势与需要注意的地方。

    优势:

    • 向量化执行引擎可以减少节点间的调度,提高CPU的利用率。
    • 因为列存数据,同一列的数据放在一起,导致向量化执行引擎在执行的时候拥有了更多的机会能够利用的当前硬件与编译的新优化特征。
    • 因为列存数据存储将同类型的类似数据放在一起使得压缩比能够达到更高,这样可以拉近一些磁盘IO能力与计算能力的差距。

    需要注意的问题:

    • 通信库效率问题 当前比较主流的OLAP类型的数据库架构,通常首选是MPP架构的数据库,因为MPP架构上是share nothing架构的,所以它的集群各执行节点是有通信需要的,通信效率的高低也是决定了查询执行效率。另外就是大集群情况下,如果使用tcp方式连接,连接数会受限。
    • 数据读写争抢问题 这个问题本身不是向量化执行引擎的,而是列存带来的,因为列存储表每一列单独存储为一个文件,这样在写盘的时候有优化与没有优化的差距还是非常明显的。
    • 列存数据过滤效率问题 列存数据过滤率问题,这个问题是源于,列存数据中的一个处理单元是由连续的N个值放在一起组成的一个Col(数组),然后再由多个Col的数组组成了一个处理单元。在进行过率的时候如何能够更加紧凑的放置数据是需要我们考虑列存在过滤掉效率和存放之间如何优化的问题。
    • 表达式计算问题(LLVM) LLVM优化可以将表达式计算由遍历树多层调用模式变为,只调用一个函数的扁平式执行方式。这样可以极大的提高表达式的执行性能。值得一提的是LLVM技术的优势也可以应用在执行计划编译执行模型的构建上面。

    总结

    本文旨在给大家一个向量化执行引擎的概要介绍,给大家有一个初步印象,在我们阿里云自己的向量化执行引擎设计开发的过程中,会在很多方面遇到不少问题, 后续我们也尽量给大家分享这些细节的实现。

    展开全文
  • 使用向量化(Vectorization)计算,速度是非向量化(non-Vectorization)计算(即循环)的300倍,因为向量化计算使用了python的内建函数,调用了CPU/GPU的SIMD指令集进行计算,大大减少了因为python高级语言执行损耗的...
  • Spark的Parquet向量化读取原理

    千次阅读 2018-08-14 22:17:15
    到达CPU指令集层面,一般运算需要调用10次指令集,控制寄存器执行“+”操作,而向量化运算,可能只需要一次将arr加载到CPU cache,然后使用多个寄存器并行执行“+”操作。显然,这是一个时间和空间都节约的方式...
  • 深度学习入门笔记(四):向量化

    千次阅读 多人点赞 2019-09-14 21:02:45
    在上面的代码中,使用两个方法——向量化和非向量化,计算了相同的值,其中向量化版本花费了0.968毫秒,而非向量化版本的 for 循环花费了327.997毫秒,大概是300多倍,准确倍数是 338.840 倍。仅仅在这个自己举的...
  • 神经网络向量化

    千次阅读 2016-04-23 11:55:23
    神经网络向量化 在本节,我们将引入神经网络的向量化版本。在前面关于神经网络介绍的章节中,我们已经给出了一个部分向量化的实现,它在一次输入一个训练样本时是非常有效率的。下边我们看看如何实现同时处理多个...
  • # 2 调用fit_transform方法,执行向量化 data = dic.fit_transform([ {'city': '北京', 'pos': '北方', 'temperature': 100}, {'city': '上海', 'pos': '东方', 'temperature': 60}, {'city': '深圳', 'pos': '...
  • python笔记5:向量化运算

    千次阅读 2018-01-22 16:34:05
    #定义:向量化计算是一种特殊的并行计算的方式,它可以在同一时间执行多次操作,通常是对不同的数据执行同样的一个或一批指令,或者说把指令应用于一个数组/向量。 #1. 四则运算 #规则:相同位置的数据进行运算...
  • hive 向量化执行的设计说明。通过在单个操作中获取 1024 行,而不是每次只获取单行来改善 scans、aggregations、filters 和 join 这类操作的性能。
  • 编译优化之 - 向量化优化入门

    千次阅读 2020-03-30 16:52:25
    3. GCC中向量化 4. ICC中向量化 5. AOCC/LLVM中向量化 1. 介绍 什么是自动向量化?   自动向量化(automatic vectorization)是自动并行化(automatic parallelization)的一种特殊情况,它将一次处理一对的标量...
  • GCC中的自动向量化(1)

    千次阅读 2016-08-18 17:00:07
    GCC中的自动向量化(1) 本文是阅读Dorit Naishlos的文章“Autovectorization in GCC”时做的笔记。 在使用了语法树上的静态单赋值(tree SSA)优化框架之后,GCC已经具备了支持自动向量化的能力。目前对向量化的一...
  • 向量化:指的是使用同一条指令同时操作多个数据; 多核技术:在同一个芯片上集成多个核心的技术; 多路技术:在同一个主板上集成多个CPU处理器
  • 使用向量化(Vectorization)计算,速度是非向量化(non-Vectorization)计算的300倍,因为向量化计算使用了python的内建函数,调用了CPU/GPU的SIMD指令集进行计算,大大减少了因为python高级语言执行损耗的时间。...
  • 1. 向量化循环: MATLAB会自动处理索引h。当坐标中涉及0时,会有混乱之源,因为本书和手册中反复强调MATLAB数组不能有0索引。 import time import numpy as np a = np.random.rand(100000...
  • 神经网络向量化实现

    千次阅读 2017-04-06 23:16:45
    矢量编程 当使用学习算法时,一段更快的代码通常意味着项目进展更快。例如,如果你的学习算法需要花费20分钟运行完成,这意味着你每个小时能“尝试”3个新主意。但是假如你的程序需要20个小时来运行,这意味着...
  • NLP | 文本特征向量化方法

    千次阅读 2018-09-23 00:53:16
    TfidfVectorizer在执行时,需要先将词袋矩阵放入内存,再计算各位置单词的TFIDF值,如果词袋维度大,将占用过多内存,效率低,此时可以使用哈希向量化。 哈希向量化可以缓解TfidfVectorizer在处理高维文本时内存...
  • 向量化编程

    千次阅读 2015-07-24 21:25:12
    Matlab向量化编程,是matlab语言的精髓所在,向量化编程运用好了,可以从代码的运行效率明显改善中获得成功的快乐。 传统的流行观点大致如下: 1. 尽管避免循环的使用,多使用Matlab的内置函数; ----如果...
  • 通过堆叠对角线上和下方的 x 元素来创建列向量; 每一列都放入一个矩阵中。 它按列顺序执行此操作。 创建是因为我无法让 Mike Cliff 的 vech 函数处理多维数组。
  • 逻辑回归的向量化实现样例

    千次阅读 2016-04-23 11:50:16
    逻辑回归的向量化实现样例 我们想用批量梯度上升法对logistic回归分析模型进行训练,其模型如下: 让我们遵从公开课程视频与CS229教学讲义的符号规范,设 ,于是 ,, 为截距。假设我们有m个训练样本{...
  • matlab程序向量化理解

    千次阅读 2016-09-14 18:10:56
    matlab程序向量化理解   matlab程序中引入程序向量化的概念,使用向量化的程序代码和语句来可以用来替代循环结构;在程序设计和执行效率方面较有优势。   简单的程序向量化示例: 如对数组的每个元素进行相同运算...
  • 支持向量机SVM、支持向量回归SVR详细推导

    万次阅读 多人点赞 2019-06-30 09:31:52
    文章详细介绍了支持向量机SVM及其拓展,支持向量回归SVR.并从线性分类和非线性分类的角度出发,详细推导了硬间隔、软间隔和核函数的支持向量机。
  • 下面我们通过一个图来比较一下向量化和非向量化的区别 上图是m个样本的逻辑回归的向量化和非向量化,单单从代码量和简洁程度上来看,向量化做的要比非向量化好得多,而且在执行效率上向量化要更高。这一切都要归功于...
  • 向量化

    万次阅读 2018-02-20 22:21:17
    653.000116348ms c =250202.521816 从执行结果来看向量化的程序运行速度要比非向量化的程序块250倍左右,为什么是向量化的程序运行速度会快很多呢? 可扩展深度学习是在GPU上做的,但是GPU和CPU都含有并行化指令有时...
  • 为什么向量化可以大幅度加快速度? 仿照吴恩达老师课堂中的示例: import numpy as np import time a = np.random.rand(1000000) b = np.random.rand(1000000) tic = time.time() c1 = np.dot(a,b) toc = ...
  • 向量化的简短定义是,所有标量实际上都是长度为1的向量。此外,函数是向量感知的,因此加法之类的操作本身就执行元素加法,而max之类的操作本身就知道如何对数组进行操作。 类型和数据结构 与R一样,arb
  • 1.2.3 使用向量化进行加速计算

    千次阅读 2018-03-10 21:12:56
    向量化 向量化通常是消除你代码中显式for循环语句的艺术。那么具体什么是向量化呢? 我们以 `z=wTx+bz=wTx+b z=w^Tx+b 为例,在这个例子中,如果有很多的数据,那么w和x以及b都是n维列向量。 如所示,左侧是...
  • 向量化矩阵转置算法

    千次阅读 2016-08-22 17:55:52
    在不少高性能计算中,矩阵转置扮演了一个使用比较频繁的角色。因此如果在某个处理过程中,矩阵转置占的比重比较大,且算法没设计好的话就可能会成为该处理过程的计算瓶颈。这里我将介绍向量化矩阵转置的算法过程。

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 126,086
精华内容 50,434
关键字:

向量化查询执行