用HTTP服务的方式集成learned cardinality estimate方法进 Postgresql
2024-09-08 16:59:45
代码地址:postgresql-13.1-ml: Integration of CardEst Methods into PostgreSQL by HTTP Server (github.com)
当前进度:可以支持单表查询的基数估计模块的替换。至于多表join的基数估计模块替换还在开发中
注意:本文的重点在于PG的修改。记录一下我的修改思路。
整体流程
PG作为http客户端,向基数估计服务端发送http请求。内容为需要基数估计的sql语句。
基数估计服务端返回该语句的selectivity。
PG收到该查询的selectivity后乘以当前表的大小,即得到rows
PG原版基数估计调用逻辑
make_one_rel // allpath.c
|-set_base_rel_sizes
|-set_rel_size
|-set_plain_rel_size // allpath.c
|-set_baserel_size_estimates // costsize.c // [单表]
|-clauselist_selectivity // clausesel.c // [单表/JOIN] 接受 CNF 形式的谓词数组(由 AND 连接数组中的各个谓词)
|-statext_clauselist_selectivity // extended_stats.c // [单表/JOIN] 多列统计信息(最优MCV+函数依赖关系),对谓词进行估算
|-dependencies_clauselist_selectivity // dependencies.c // [单表/JOIN] P(a, b) = P(a) * (f + (1-f) * P(b)) 这里 f 即是 (a, b) 之间的函数依赖程度。
|-clauselist_selectivity_simple // clausesel.c // [单表/JOIN] 对剩下的谓词使用单列统计信息进行估算,wrapper,维护区间信息
|-clause_selectivity // clausesel.c // [单表/JOIN] 处理 DNF(由 OR 连接各个谓词),NOT表达式,CNF回到clauselist_selectivity
|-restriction_selectivity // plancat.c // [单表] 当需要为某个操作符计算某类操作的选择率的时候,PostgreSQL通过调用函数管理器,执行存储在过程函数系统表(pg_proc.h)中登记的选择率计算函数。
|-scalarltsel... // selfuncs.c // [单表] 选择率计算函数主要存在selfuncs.c
|-scalarineqsel_wrapper // selfuncs.c // [单表] 判断expr是否是 var op sth. 或者是 sth. op var
|-scalarineqsel // selfuncs.c // [单表] 处理"<", "<=", ">", ">=" 的选择率估计
|-mcv_selectivity // selfuncs.c // [单表] MCV 估计
|-histogram_selectivity // selfuncs.c // [单表] 直方图估计
|-make_rel_from_joinlist // allpath.c // [JOIN] 动态规划
|-standard_join_search // allpath.c // [JOIN] 创建RelOptInfo链表数组存储在root中。root->join_rel_level[1] 存储所有初始表的rel,root->join_rel_level[2]存储所有两张表join的rel...
|-join_search_one_level // joinrel.c // [JOIN] 生成当前level的RelOptInfo, level表示考虑当前的join有level张表。
遍历join_rel_level[level-1](old_rel), 与join_rel_level[1]【左深树】,
优先连接有连接关系的rels或者有连接顺序限制的rels,进入make_rels_by_clause_joins;
对没有连接关系的表或连接顺序限制的表也尝试make, 进入make_rels_by_clauseless_joins
建立【浓密树】。浓密树抛开基表,连接(2, N-2),(3, N-3),(4, N-4)等多种情况。但建立浓密树的rel需要满足两个条件。
两个rel需要有相关的连接条件或者有连接顺序的限制;两个rel代表的表不能有交集。 还有最后的尝试【卡氏积】。
|-make_join_rel // joinrel.c // [JOIN] if 满足建浓密树的条件
|-make_rels_by_clause_joins // joinrel.c // [JOIN] 判断是否可以连接(要求两个连接rel的relids没有重叠),可以连接便make
|-make_join_rel // joinrel.c // [JOIN]
|-make_rels_by_clauseless_joins // joinrel.c // [JOIN] 对没有连接关系的表或连接顺序限制的表也尝试make
|-make_join_rel // joinrel.c //
|-build_join_rel // relnode.c // [JOIN]
|-set_joinrel_size_estimates // costsize.c // [JOIN]
|-calc_joinrel_size_estimate // costsize.c // [JOIN]
|-clauselist_selectivity // clausesel.c // 同上
|-clause_selectivity // clausesel.c // [单表/JOIN] 处理 DNF(由 OR 连接各个谓词),NOT表达式,CNF回到clauselist_selectivity
|-join_selectivity // plancat.c // [JOIN] 当需要为某个操作符计算某类操作的选择率的时候,PostgreSQL通过调用函数管理器,执行存储在过程函数系统表(pg_proc.h)中登记的选择率计算函数。
|-eqjoinsel_inner... // selfuncs.c // [JOIN] 主要是用MCV对join结果集进行估算
|-populate_joinrel_with_paths // joinrel.c // [JOIN] add paths to joinrel (交换rel1和rel2算两个path)
|-try_partitionwise_join // joinrel.c // if enable_partitionwise_join==True; 智能分区联表
|-build_child_join_rel // relnode.c
|-set_joinrel_size_estimates // costsize.c // [JOIN] 同上
修改源码
主要修改代码costsize.c
单表修改set_baserel_size_estimates函数
修改逻辑
其中get_expr函数的逻辑可参考print.c文件中print_expr函数
多表修改set_joinrel_size_estimates函数
待续
添加第三方库
该项目需要其它两个第三方库
- C语言的HTTP服务的client端的库,参考项目:linux下socket(C)构造HTTP客户端
- C语言解析json格式的库,参考项目:cJSON
将第三方库的头文件和实现文件加入到PG中:
- 把http.h 添加到 /src/include/utils/下
- costsize.c 添加 #include "utils/http.h”
- 把cJSON.h 添加到 /src/include/utils/下
- 把cJSON.c 添加到 /src/backend/utils/adt/下
- cJSON.c 把#include "cJSON.h”修改成#include "utils/cJSON.h”
- 在/src/backend/utils/adt/Makefile添加 cJSON.o \
- costsize.c 添加 #include "utils/cJSON.h”
效果
单表查询的效果
测试数据集:imdb.title
PG原版计划
imdb=# explain analyze select * from title where kind_id>1 and kind_id<10;
QUERY PLAN
--------------------------------------------------------------------------------------------------------------------------------------
Bitmap Heap Scan on title (cost=174.01..25746.20 rows=12642 width=306) (actual time=163.325..646.420 rows=1865487 loops=1)
Recheck Cond: ((kind_id > 1) AND (kind_id < 10))
Heap Blocks: exact=35995
-> Bitmap Index Scan on kind_id_title (cost=0.00..170.85 rows=12642 width=0) (actual time=156.207..156.208 rows=1865487 loops=1)
Index Cond: ((kind_id > 1) AND (kind_id < 10))
Planning Time: 1.313 ms
Execution Time: 710.562 ms
(7 rows)
集成learned方法的计划
imdb=# explain analyze select * from title where kind_id>1 and kind_id<10;
QUERY PLAN
------------------------------------------------------------------------------------------------------------------
Seq Scan on title (cost=0.00..73920.58 rows=1242940 width=94) (actual time=0.037..586.408 rows=1865487 loops=1)
Filter: ((kind_id > 1) AND (kind_id < 10))
Rows Removed by Filter: 662825
Planning Time: 32.463 ms
Execution Time: 656.291 ms
(5 rows)
最优计划
imdb=# explain analyze select * from title where kind_id>1 and kind_id<10;
QUERY PLAN
------------------------------------------------------------------------------------------------------------------
Seq Scan on title (cost=0.00..73920.58 rows=1865384 width=94) (actual time=0.084..548.721 rows=1865487 loops=1)
Filter: ((kind_id > 1) AND (kind_id < 10))
Rows Removed by Filter: 662825
Planning Time: 4.067 ms
Execution Time: 614.774 ms
(5 rows)
多表查询的效果
待续
待完善
- 多表查询的基数估计部分还在开发中
- 当前版本只适用于实验环境。尚未对不支持的查询进行过滤。
参考资料
- End-to-End-CardEst-Benchmark
- VLDBSS2022实验
- PostgreSQL 在内核增加一个配置参数
- linux下socket(C)构造HTTP客户端
- cJSON使用详细教程 | 一个轻量级C语言JSON解析器
- cJSON
最新文章
- PHP build notes - WARNING: This bison version is not supported for regeneration of the Zend/PHP parsers (found: 3.0, min: 204, excluded: 3.0).
- Maven学习(五)-- 聚合与继承
- POI中getLastRowNum() 和getLastCellNum()的区别
- [3D跑酷] AudioManager
- eval() 函数
- java中不带package和带package的编译运行方式
- 笔记本显示器坏了,从硬盘安装win7系统
- 利用radio实现纯css选项卡切换
- 将vim作为QT开发的IDE
- dom入门
- 好程序员web前端分享如何理解JS的单线程
- Ubuntu 18.04搭建Git服务器
- BZOJ3502PA2012Tanie linie&;BZOJ2288[POJ Challenge]生日礼物——模拟费用流+链表+堆
- Spring.Net 简单实例-01(IOC)
- LeetCode 237 Delete Node in a Linked List 解题报告
- 超恶心的TP模版取值
- delphi获取文件的创建/修改时间、按时间删除指定文件下的文件
- 利用JQuery Mobile开发web app
- 框架:Spring IoC
- ";类工厂模式";改写SqlHelper