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

本文涉及的产品
云数据库 RDS MySQL,集群系列 2核4GB
推荐场景:
搭建个人博客
RDS SQL Server Serverless,2-4RCU 50GB 3个月
推荐场景:
RDS MySQL Serverless 基础系列,0.5-2RCU 50GB
简介: 标签 PostgreSQL , cluster , 预排 , 一维数据 , 多维数据 , 视觉编排 , 数据编排 , IO优化 背景 中华文化源远流长,比如这句古语“远水不救近火,远亲不如近邻”,在数据库的优化中亦有体现。

标签

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。

pic

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

pic

这就是数组类型编排要取得的目的,由于数组类型通常是按数组的元素进行检索的,因此我们需要根据元素来进行编排。数组类型的编排方式同样适用于全文检索类型,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查询商品营销最佳组合》

pic

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

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运算,计算每种组合的聚合度并不是最好的选择。

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

pic

小结

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

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

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

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

内存的硬件特性,同上。

软硬件一体化。

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

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

pic

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

pic

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

pic

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

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

相关实践学习
使用PolarDB和ECS搭建门户网站
本场景主要介绍基于PolarDB和ECS实现搭建门户网站。
阿里云数据库产品家族及特性
阿里云智能数据库产品团队一直致力于不断健全产品体系,提升产品性能,打磨产品功能,从而帮助客户实现更加极致的弹性能力、具备更强的扩展能力、并利用云设施进一步降低企业成本。以云原生+分布式为核心技术抓手,打造以自研的在线事务型(OLTP)数据库Polar DB和在线分析型(OLAP)数据库Analytic DB为代表的新一代企业级云原生数据库产品体系, 结合NoSQL数据库、数据库生态工具、云原生智能化数据库管控平台,为阿里巴巴经济体以及各个行业的企业客户和开发者提供从公共云到混合云再到私有云的完整解决方案,提供基于云基础设施进行数据从处理、到存储、再到计算与分析的一体化解决方案。本节课带你了解阿里云数据库产品家族及特性。
目录
相关文章
|
20天前
|
关系型数据库 MySQL 数据库
ORM对mysql数据库中数据进行操作报错解决
ORM对mysql数据库中数据进行操作报错解决
64 2
|
28天前
|
消息中间件 缓存 监控
优化微服务架构中的数据库访问:策略与最佳实践
在微服务架构中,数据库访问的效率直接影响到系统的性能和可扩展性。本文探讨了优化微服务架构中数据库访问的策略与最佳实践,包括数据分片、缓存策略、异步处理和服务间通信优化。通过具体的技术方案和实例分析,提供了一系列实用的建议,以帮助开发团队提升微服务系统的响应速度和稳定性。
|
19天前
|
JavaScript Java 关系型数据库
毕设项目&课程设计&毕设项目:基于springboot+vue实现的在线考试系统(含教程&源码&数据库数据)
本文介绍了一个基于Spring Boot和Vue.js实现的在线考试系统。随着在线教育的发展,在线考试系统的重要性日益凸显。该系统不仅能提高教学效率,减轻教师负担,还为学生提供了灵活便捷的考试方式。技术栈包括Spring Boot、Vue.js、Element-UI等,支持多种角色登录,具备考试管理、题库管理、成绩查询等功能。系统采用前后端分离架构,具备高性能和扩展性,未来可进一步优化并引入AI技术提升智能化水平。
毕设项目&课程设计&毕设项目:基于springboot+vue实现的在线考试系统(含教程&源码&数据库数据)
|
21天前
|
Java 关系型数据库 MySQL
毕设项目&课程设计&毕设项目:springboot+jsp实现的房屋租租赁系统(含教程&源码&数据库数据)
本文介绍了一款基于Spring Boot和JSP技术的房屋租赁系统,旨在通过自动化和信息化手段提升房屋管理效率,优化租户体验。系统采用JDK 1.8、Maven 3.6、MySQL 8.0、JSP、Layui和Spring Boot 2.0等技术栈,实现了高效的房源管理和便捷的租户服务。通过该系统,房东可以轻松管理房源,租户可以快速找到合适的住所,双方都能享受数字化带来的便利。未来,系统将持续优化升级,提供更多完善的服务。
毕设项目&课程设计&毕设项目:springboot+jsp实现的房屋租租赁系统(含教程&源码&数据库数据)
|
2天前
|
SQL 监控 数据处理
SQL数据库数据修改操作详解
数据库是现代信息系统的重要组成部分,其中SQL(StructuredQueryLanguage)是管理和处理数据库的重要工具之一。在日常的业务运营过程中,数据的准确性和及时性对企业来说至关重要,这就需要掌握如何在数据库中正确地进行数据修改操作。本文将详细介绍在SQL数据库中如何修改数据,帮助读者更好
19 4
|
3天前
|
存储 人工智能 Cloud Native
云栖重磅|从数据到智能:Data+AI驱动的云原生数据库
阿里云瑶池在2024云栖大会上重磅发布由Data+AI驱动的多模数据管理平台DMS:OneMeta+OneOps,通过统一、开放、多模的元数据服务实现跨环境、跨引擎、跨实例的统一治理,可支持高达40+种数据源,实现自建、他云数据源的无缝对接,助力业务决策效率提升10倍。
|
4天前
|
关系型数据库 MySQL 数据库
使用Docker部署的MySQL数据库,数据表里的中文读取之后变成问号,如何处理?
【10月更文挑战第1天】使用Docker部署的MySQL数据库,数据表里的中文读取之后变成问号,如何处理?
22 3
|
3天前
|
测试技术 API 数据库
云数据库之添加数据
云数据库之添加数据
12 1
|
4天前
|
存储 关系型数据库 MySQL
MySQL数据库数据块大小
MySQL数据库数据块大小
19 1
|
15天前
|
缓存 关系型数据库 MySQL
MySQL数据库优化:提升性能和扩展性的关键技巧
MySQL数据库优化:提升性能和扩展性的关键技巧
43 2