高阶魔方与数据编排 - 数据库存储优化之路

标签

PostgreSQL , cluster , 预排 , 一维数据 , 多维数据 , 视觉编排 , 数据编排 , IO优化

背景

中华文化源远流长，比如这句古语“远水不救近火，远亲不如近邻”，在数据库的优化中亦有体现。接下来我们来揭示这个道理。

大多数数据库的存储为块存储，一个块里面可能涉及到多条记录，当用户输入查询条件进行数据检索时，即使返回的结果集较小，也可能需要扫描多个数据块，因为你不知道你要的记录落在哪些数据块里面。

例子

随机写入一批数据

create table tbl(id int, info text default repeat(random()::text,10), crt_time timestamp default now());
insert into tbl (id) select random()*10000 from generate_series(1,1000000);

查询ID<100的记录，这些记录落在哪些数据块里面？

postgres=# select ctid from tbl where id<100;
    ctid
------------
 (4,10)
 (6,32)
 (7,33)
 (17,14)
 (22,15)
 (22,16)
 (25,2)
 (29,21)
 (41,13)
 (42,27)
 (43,27)
 (54,11)
 (54,33)
 (56,1)
 (60,13)
。。。。。。

可以看到，数据散落在不同的数据块里面。也就是说访问了很多数据块。

很多用户遇到了类似的问题，我做了一些总结和优化之道，请参考下面的文章。

《索引顺序扫描引发的堆扫描IO放大背后的统计学原理与解决办法》

《懒人推动社会进步 - 多列聚合, gin与数据分布(选择性)》

《索引扫描优化之 - GIN数据重组优化(按元素聚合) 想象在玩多阶魔方》

以上文章提到了优化的方法：数据重新编排存储。让数据尽量的根据搜索条件进行聚集，减少扫描成本。

数据存储优化 - 编排

数据存储编排的目的很简单，让数据尽量的根据搜索条件进行聚集，减少扫描成本。

但是数据种类不一样，编排优化也不太一样。前面提到的例子针对的都是一维的数据，一维数据的操作很简单，=, >, <, >=, <=, in等。

如果数据类型不是一维类型，而是多值类型或者异构类型呢？例如数组、空间类型、全文检索类型等。数据的编排还有这么简单吗？

一维数据编排

一维类型的编排，按搜索列排序是最简单有效的编排方法。业界也叫预排序，PostgreSQL术语叫cluster，通过cluster命令即可完成编排。

https://www.postgresql.org/docs/9.6/static/sql-cluster.html

多维数据编排

一位编排比较简单，但是多维编排会更加复杂。我通过一个游戏来说明编排的目的。

我们来玩一个游戏，假设全球有10000个国家，每个国家挑选若干人（每个国家挑选的人数可以不一样，例如A国家挑选了1000人，B国家挑选了10人，假设总共挑选了100万人）进行混合分组，每个分组包含了若干不同国家的人（每个分组每个国家仅限1人）。下面进行排队，横坐标为分组ID，纵坐标为国家ID。接下来要进行搬运游戏，从左导游，每个国家的人，需要将它手里的球搬运给右边的相同国家的人，如果他们相邻，则不计成本。如果他们之间隔了其他分组，则计算成本（相隔的分组个数）。最终计算每个国家的搬运成本，某些国家的搬运成本，或者所有国家相加的总搬运成本。

如何降低总成本，如何降低某些国家的成本，如何降低某个国家的成本？

例如第一种排列方式，1号国家的搬运成本为2， 6号，7号国家的搬运成本为1，其他国家的搬运成本为0。

第二种排列方式如下，所有国家的搬运成本都为0。

这就是数组类型编排要取得的目的，由于数组类型通常是按数组的元素进行检索的，因此我们需要根据元素来进行编排。数组类型的编排方式同样适用于全文检索类型，TOKEN类型。

其他类型的编排则根据数据类型来定，例如空间类型，可以根据GEOHASH的值进行排序编排。

下面我们讲一下数组类型编排的实现过程。

生成测试数据

生成随机数组的方法

postgres=# create or replace function gen_array(range int, cnt int) returns int[] as $$
select array(select (random()*range)::int from generate_series(1,cnt) group by 1);
$$ language sql strict volatile;
CREATE FUNCTION  

postgres=# select gen_array(10,5);
 gen_array
-----------
 {9,1,5,8}
(1 row)  

postgres=# select gen_array(10, 20);
       gen_array
------------------------
 {9,3,1,4,5,2,7,6,8,10}
(1 row)  

postgres=# select gen_array(100,10) from generate_series(1,100);
            gen_array
----------------------------------
 {9,16,51,72,31,27,20,63,41,65}
 {88,1,59,39,87,28,24,32,21}
 {69,78,34,11,84,79,97,80,85,56}
 {3,90,42,81,83,41,76,99,65,25}
 {14,4,42,50,37,13,72,75,29,74}
 {23,92,53,74,77,71,93,82}
 {1,16,81,51,79,76,62,94,77}
 {48,64,18,35,43,36,54,41,29,98}
 {100,84,28,99,80,8,85,77,10,33}
 {96,31,39,7,87,53,36,54,30,77}
 {70,49,90,91,13,40,31,54,97,94}
 {58,55,35,75,29,6,65,56,98}
......

建立测试表，写入随机数组

postgres=# create table tbl2(id int, arr int[]);
CREATE TABLE  

postgres=# insert into tbl2 select id, gen_array(10,10) from generate_series(1,10) t(id);
INSERT 0 10  

postgres=# select * from tbl2 limit 10;
 id |         arr
----+---------------------
  1 | {1,5,2,6,8}
  2 | {1,4,5,2,7,6,8,0}
  3 | {9,1,5,2,7,6,8}
  4 | {3,1,4,5,2,7,6}
  5 | {9,1,5,2,7,8,10}
  6 | {9,3,1,2,7,6,8}
  7 | {9,3,1,5,2,7,8}
  8 | {3,1,4,5,2,6,10}
  9 | {9,3,1,4,5,2,7,6,8}
 10 | {3,1,5,7,6,10,0}
(10 rows)

10条记录，有多少种排列组合的可能呢？

PostgreSQL有排列组合函数可以支持，如下。

postgres=# \df *.*fac*
                             List of functions
   Schema   |    Name     | Result data type | Argument data types |  Type
------------+-------------+------------------+---------------------+--------
 pg_catalog | factorial   | numeric          | bigint              | normal
 pg_catalog | numeric_fac | numeric          | bigint              | normal
(2 rows)  

postgres=# select factorial(10);
 factorial
-----------
   3628800
(1 row)  

postgres=# select numeric_fac(10);
 numeric_fac
-------------
     3628800
(1 row)  

postgres=# select 10*9*8*7*6*5*4*3*2;
 ?column?
----------
  3628800
(1 row)  

postgres=# select 10!;
 ?column?
----------
  3628800
(1 row)  

postgres=# \do+ !
                                      List of operators
   Schema   | Name | Left arg type | Right arg type | Result type |  Function   | Description
------------+------+---------------+----------------+-------------+-------------+-------------
 pg_catalog | !    | bigint        |                | numeric     | numeric_fac | factorial
(1 row)

排列组合

排列组合，指行的排列顺序。下面两篇文档中也涉及排列组合的例子。

《PostgreSQL n阶乘计算, 排列组合计算 - 如何计算可变参数中有没有重复参数》

《为什么啤酒和纸尿裤最搭 - 用HybridDB/PostgreSQL查询商品营销最佳组合》

通过行号的顺序，得到排列组合，验证通过。

postgres=#  WITH RECURSIVE cte AS (
     SELECT array[ctid] AS combo, ctid, 1 AS ct
     FROM tbl2
   UNION ALL
     SELECT array_append(cte.combo, t.ctid), t.ctid, ct + 1
     FROM cte, tbl2 t
     WHERE ct <= 10  -- 10是 tbl2的count(*)，即自关联10次，得到所有排列组合
       AND array_position(cte.combo, t.ctid) is null  -- 元素去重
)
SELECT count(combo) FROM cte where ct=10;  -- 10是 tbl2的count(*)  

  count
---------
 3628800
(1 row)

排列组合示例：

postgres=#  WITH RECURSIVE cte AS (
     SELECT array[ctid] AS combo, ctid, 1 AS ct
     FROM tbl2
   UNION ALL
     SELECT array_append(cte.combo, t.ctid), t.ctid, ct + 1
     FROM cte, tbl2 t
     WHERE ct <= (select count(*) from tbl2)
       AND array_position(cte.combo, t.ctid) is null
)
SELECT combo FROM cte where ct=10 limit 10;
                                       combo
------------------------------------------------------------------------------------
 {"(0,1)","(0,2)","(0,3)","(0,4)","(0,5)","(0,6)","(0,7)","(0,8)","(0,9)","(0,10)"}
 {"(0,1)","(0,2)","(0,3)","(0,4)","(0,5)","(0,6)","(0,7)","(0,8)","(0,10)","(0,9)"}
 {"(0,1)","(0,2)","(0,3)","(0,4)","(0,5)","(0,6)","(0,7)","(0,9)","(0,8)","(0,10)"}
 {"(0,1)","(0,2)","(0,3)","(0,4)","(0,5)","(0,6)","(0,7)","(0,9)","(0,10)","(0,8)"}
 {"(0,1)","(0,2)","(0,3)","(0,4)","(0,5)","(0,6)","(0,7)","(0,10)","(0,8)","(0,9)"}
 {"(0,1)","(0,2)","(0,3)","(0,4)","(0,5)","(0,6)","(0,7)","(0,10)","(0,9)","(0,8)"}
 {"(0,1)","(0,2)","(0,3)","(0,4)","(0,5)","(0,6)","(0,8)","(0,7)","(0,9)","(0,10)"}
 {"(0,1)","(0,2)","(0,3)","(0,4)","(0,5)","(0,6)","(0,8)","(0,7)","(0,10)","(0,9)"}
 {"(0,1)","(0,2)","(0,3)","(0,4)","(0,5)","(0,6)","(0,8)","(0,9)","(0,7)","(0,10)"}
 {"(0,1)","(0,2)","(0,3)","(0,4)","(0,5)","(0,6)","(0,8)","(0,9)","(0,10)","(0,7)"}
(10 rows)

统计每一种排列组合，各个元素的检索成本

计算每一种排列组合，对应数组元素的聚合度（越靠近0(越小)，越聚合）

根据前面的聚合度算法，使用如下函数实现。

create or replace function cal_affinity(OUT o_combo tid[], OUT affinity int8) returns setof record as $$
declare
  ccc int8;     -- tbl2总共多少条记录
  v_tid tid[];  -- 行号组合
  vv_tid tid;   -- 行号
  i1 int := 1;  -- 正处于第几行
  i2 int[];     -- 与tbl2.arr同类型的数组，存储所有元素
  i3 int[];     -- 上一次元素出现在第几行，下标=i2 中元素的位置
  i4 int[];     -- 每个元素的聚合度累计值
  v_i4 int;     -- 每个元素单独的聚合度
  sum_i4 int8;  -- i4的sum
  x int;        -- 第几个循环
  v_arr int[];  -- tbl2 数组
  i_arr int;    -- tbl2 数组元素
begin
  select count(*) into ccc from tbl2;
  select array(select distinct(unnest(arr)) from tbl2) into i2;  

-- 排列组合循环
for v_tid in
  WITH RECURSIVE cte AS (
       SELECT array[ctid] AS combo, ctid, 1 AS ct
       FROM tbl2
     UNION ALL
       SELECT array_append(cte.combo, t.ctid), t.ctid, ct + 1
       FROM cte, tbl2 t
       WHERE ct <= ccc
         AND array_position(cte.combo, t.ctid) is null
  )
  SELECT combo FROM cte where ct=ccc limit 10   --  只计算10种组合
  -- 3628800种组合实在太多了，我挑选一些进行计算，验证聚合度结果。
loop  

  -- 按行号循环
  foreach vv_tid in array v_tid
  loop  

    -- 生成tbl2当前行的数组
    select arr into v_arr from tbl2 where ctid=vv_tid;  

    -- 按tbl2数组元素循环，计算每个元素的聚合度累加
    foreach i_arr in array v_arr
    loop
      -- 获取元素下标 array_position(i2, i_arr)
      -- i1=1，处于第一行  

      -- 计算聚合度，真实场景应该改成数据块是否相邻，而不是行号
      if i1=1 then
	-- 第一行
	i4[array_position(i2, i_arr)] := 0;
      else
        -- 不是第一行
	if i4[array_position(i2, i_arr)] is null then
          -- 该元素第一次出现
	  i4[array_position(i2, i_arr)] := 0;
	else
	  -- 该元素不是第一次出现
	  i4[array_position(i2, i_arr)] := i4[array_position(i2, i_arr)] + greatest((i1 - i3[array_position(i2, i_arr)] - 1), 0);  -- 防止单行元素重复计算错误
	end if;
      end if;  

      -- 元素最后一次出现在第几行
      i3[array_position(i2, i_arr)] := i1;
    end loop;  

    -- 行号+1
    i1 := i1 + 1;
  end loop;  

  -- 输出该排列组合的所有元素的聚合度，总聚合度
  select sum(unnest) into sum_i4 from (select unnest(i4)) t;
  raise notice 'combo: %, sum(affinity): %', v_tid, sum_i4;
  x := 1;
  foreach v_i4 in array i4
  loop
    raise notice 'elements: %, affinity: %', i2[x], v_i4;
    x := x+1;
  end loop;  

  -- 初始化变量
  i1 := 1;
  i3 := '{}';
  i4 := '{}';
end loop;
-- 行号循环
end;
$$ language plpgsql strict;

调用函数计算聚合度

select * from cal_affinity();  

NOTICE:  combo: {"(0,1)","(0,2)","(0,3)","(0,4)","(0,5)","(0,6)","(0,7)","(0,8)","(0,9)","(0,10)"}, sum(affinity): 23
NOTICE:  elements: 7, affinity: 1
NOTICE:  elements: 9, affinity: 2
NOTICE:  elements: 3, affinity: 1
NOTICE:  elements: 1, affinity: 0
NOTICE:  elements: 4, affinity: 4
NOTICE:  elements: 6, affinity: 2
NOTICE:  elements: 8, affinity: 2
NOTICE:  elements: 5, affinity: 1
NOTICE:  elements: 2, affinity: 0
NOTICE:  elements: 10, affinity: 3
NOTICE:  elements: 0, affinity: 7
NOTICE:  combo: {"(0,1)","(0,2)","(0,3)","(0,4)","(0,5)","(0,6)","(0,7)","(0,8)","(0,10)","(0,9)"}, sum(affinity): 25
NOTICE:  elements: 7, affinity: 1
NOTICE:  elements: 9, affinity: 3
NOTICE:  elements: 3, affinity: 1
NOTICE:  elements: 1, affinity: 0
NOTICE:  elements: 4, affinity: 5
NOTICE:  elements: 6, affinity: 2
NOTICE:  elements: 8, affinity: 3
NOTICE:  elements: 5, affinity: 1
NOTICE:  elements: 2, affinity: 1
NOTICE:  elements: 10, affinity: 2
NOTICE:  elements: 0, affinity: 6  

.....

选择sum(affinity)最小的combo，就是最优的排列组合。将数据按这个顺序调整，即可最大的优化性能。

存储

数据编排是存储层面的优化，所以存储本身的属性也决定了应该如何进行数据编排。

平面存储

平面存储，数据按顺序在一个或多个平面上存储，当从数据库中顺序搜索一批数据时，在物理存储层面也可能是相邻的介质。

所以前面提到的编排优化是非常有效的。

SSD、3D存储

硬件特性是SSD或者3D存储结构时，当从数据库中顺序搜索一批数据时，在物理存储层面也可能是相邻的介质，也可能不是，这个需要根据硬件厂商的写特性。

前面的编排对硬件的优化效果可能就没那么好。编排算法应该充分考虑硬件的数据访问特性，才能达到最好的优化效果。

但是对内存的优化效果一定是有的。

GPU - 视觉编排

从前面的例子来看，数据编排的方法会耗费大量的计算量，10条记录就可能有300多万种排列组合，使用CPU运算，计算每种组合的聚合度并不是最好的选择。

对于此类编排聚合度的计算，视觉处理可能是更好的方法。

小结

1、数据编排的目的和好处：让数据更加紧凑，降低访问成本，节约内存。

2、编排应该考虑到多个方面：

数据的访问需求，比如是顺序访问，还是随机访问，是访问等值数据，还是访问范文数据，是访问标量，还是访问多值类型、异构类型等。优化是需要针对访问需求的。

数据存储的硬件特性，硬件是如何处理数据存储和搜索的。也决定了应该如何优化。

内存的硬件特性，同上。

软硬件一体化。

3、PostgreSQL不仅支持简单的标量类型，还支持复杂的多值类型，例如array, range, json, hstore, gis, xml等。在数据编排优化层面更加的复杂。

一维类型的编排就好像只需要完成魔方的一面

多维类型的编排需要完成所有面

随着多维类型元素的增加，记录数的增加，编排难度也会呈指数上升

多维数据的编排，运算量非常庞大，使用GPU处理可能是一种更好的方法。

PostgreSQL UDF支持pl/cuda编程，可以很好的与GPU进行结合，提高计算能力。

时间： 2025-01-20 13:17:44

高阶魔方与数据编排 - 数据库存储优化之路的相关文章

如何使用重复数据删除技术实施主存储优化

主要文件系统存储优化(也就是在同样的空间塞进更多的数据)继续在日益普及.这里的挑战是主存储的重复数据删除并不是没有规则的.你不能删除这个重复的数据,也不能删除那个重复的数据,你必须要认识到删除重复数据之后对设备性能的影响. EMC已经宣布了在自己的Celerra平台上删除重复数据的功能.NetApp使用这个功能已经有一段时间了.其它厂商也以积极的方式增加这个功能,其方法是在数据不流动之后对数据进行压缩和删除重复数据.然后,Storwize等公司一直以在线实时压缩的方式提供这种功能. 正如存储虚拟

任意列搜索之 列存储优化

标签 PostgreSQL , 列存储 , shard , 切片 , 大块 , 小块 , sort , 块级索引 , bitmap scan , 索引延迟 , 归整 背景 数据分析系统,决策系统的数据量通常非常庞大,属性(列)非常多,可能涉及到任意列的组合条件查询,筛选结果.聚合结果.多维分析等. 这种场景如何优化能满足实时的响应需求呢? PostgreSQL中有一些技术,可以满足此类场景. 1. 内置bitmapAnd bitmapOr,使用任意字段的索引搜索时,可以快速跳过不满足条件的块,快

类似12306账号中的常用联系人这种不定长的数据是怎么存储的？数据库是如何建的？求指教

问题描述 类似12306账号中的常用联系人这种不定长的数据是怎么存储的?数据库是如何建的?求指教 类似12306账号中的常用联系人.论坛回复 这种不定长的数据是怎么存储的 解决方案 就这个网站来说,应该很少存在Unicode类型的数据,如果你真担心会有多语言的数据,比如维语.繁体中文等,可以用nvarchar类型存储.一般如果仅展示,那么以逗号或者其他符号分割每个联系人,然后以一列的形式存储即可,如果还需要做互动操作,建议创建一个关系表,存放当前人员和联系人的关系,通常是两列,一列是当前人员的主

mysql数据库存储路径更改 数据文件位置

mysql数据库存储路径更改  使用了VPS一段时间之后发现磁盘空间快满了.本人的VPS在购买的时候买了500gb的磁盘,提供商赠送了20GB的高性能系统磁盘.这样系统就有两个磁盘空间了.在初次安装mysql 的时候将数据库目录安装在了系统盘.(第一个磁盘)使用了一段时间之后数据库存储量变大,快将20GB的存放空间占满了.因此必须将存放数据空间换地方了.嘿嘿下面是简单的操作了,不合理之处还请大侠们指点. 操作步骤:     1.检查mysql数据库存放目录     mysql -u root -

android SQLite数据库存储数据

简介 SQLite是轻量级嵌入式数据库引擎,它支持 SQL 语言,并且只利用很少的内存就有很好的性能.Android 集成了 SQLite 数据库 Android 在运行时(run-time)集成了 SQLite,所以每个 Android 应用程序都可以使用 SQLite 数据库. 对于熟悉 SQL 的开发人员来时,在 Android 开发中使用 SQLite 相当简单.但是,由于 JDBC 会消耗太多的系统资源,所以 JDBC 对于手机这种内存受限设备来说并不合适.因此,Android 提供了

大数据存储-SOS上百万的数据插入数据库问题

问题描述 SOS上百万的数据插入数据库问题 每天定时从FTP上下载一份上百万数据量的压缩文件到服务器,然后解压,再然后读取这批文件,一个文件可能就1KB,可能一个文件夹里有上百万个文件,怎样快速的读取这批文件的信息,然后插入数据库呢,读完一个文件要同时把这个文件备份到另一个目录下,同时原目录下这个文件也要删除,请问各位大神,有什方法可以快速的写入数据,有没有demo参考一下,本人是菜鸟中菜鸟来的! 解决方案 这个基本上选取一个你熟悉的脚本语言来做,就比较简单 比如python 你用urllib库

hbase-Titan1.0.0图数据库如何批量加载大规模数据，后端存储是Hbase？

问题描述 Titan1.0.0图数据库如何批量加载大规模数据,后端存储是Hbase? 我有1亿的顶点和几十亿的边,如何通过BLVP加载到Titan 中,我后端的存储平台用的是Hbase. 解决方案 我也在用titan+hbase,但使用Gremlin-Server的REST api一直出问题,请问你有自己的安装笔记吗? 解决方案二: fragment中数据库的数据加载批量从数据库是提取数据,并显示出来.批量加载数据到SQL数据表 解决方案三: 有安装的详细笔记吧,你私信我吧.

实时大数据存储-实时大数据写入数据库

问题描述 实时大数据写入数据库 项目:IOCP的多线程(工作线程)解析大量客户端发送过来的数据:这个数据量是非常大的,上千个客户端,每50MS发送一个数据包过来,要把他们写入数据库.以下是我做的两种设计,均不能成功. 1.简单地通过程序一条一条地执行SQL语句写入数据库,失败,效率极低,淘汰. 2.我目前的处理是把这个SQL语句做一个拼接(...+SQL语句+;+SQL 语句+:+...),然后一并执行,写入数据库,但是这么设计的话,内存会一直涨,因为写入数据库的速率小于IOCP解析出来的数据所

[Asp.net]常见数据导入Excel，Excel数据导入数据库解决方案，总有一款适合你！

原文:[Asp.net]常见数据导入Excel,Excel数据导入数据库解决方案,总有一款适合你! 引言 项目中常用到将数据导入Excel,将Excel中的数据导入数据库的功能,曾经也查找过相关的内容,将曾经用过的方案总结一下. 方案一 NPOI NPOI 是 POI 项目的 .NET 版本.POI是一个开源的Java读写Excel.WORD等微软OLE2组件文档的项目.使用 NPOI 你就可以在没有安装 Office 或者相应环境的机器上对 WORD/EXCEL 文档进行读写.NPOI是构建在