本文为论文 Instance-Optimized Data Layouts for Cloud Analytics Workloads 的阅读笔记。 ABSTRACT 逐块区域映射是一种常用的通过跳过块来减少I/O的技术，但其有效性取决于如何将记录分配给块，即数据布局。 现有的优化数据布局的方法只针对单个表，在存在基于连接的查询时，它们的性能会受到影响。在本文中，我们提出了MTO(多表优化器)，目标是学习一种实例优化的布局，该布局可以最大化特定数据集和工作负载的块跳转。MTO利用连接传递的横向信息来优化所有表的布局，在基于云的商业数据分析服务上实现了高达93%的块访问减少和75%的端到端查询时间减少。 1 INTRODUCTION 区域映射对于在查询执行期间跳过不相关的块很有用，但是它们的有效性取决于块之间数据的物理布局，即排序顺序。 文章主要贡献： (1) MTO 是第一个用于优化整个数据集的实例-优化数据布局框架。（常用的优化多表数据集布局的方法是独立的优化每个表的布局，其性能并不高。） (2) 引入连接诱导谓词，在MTO中用于通过连接传递信息，更好的学习数据布局。 (3) MTO 可以扩展到更大的数据集和工作负载，并适应工作负载转移和数据变化。 2 CURRENT BLOCKING APPROACHES 【Sort Key】 按特定列对每个表的数据进行排序，但只有过滤排序键列的查询才能从块跳过中受益。 【Z-ordering】 同时对多个列上的数据进行排序，但必须仔细调整才能实现高性能。即使经过适当调整，性能也不如 instance-optimized 方法。 【Instance-optimized Layouts】 在特定数据集和工作负载上表现良好，通过有目的地过拟合特定数据集和工作负载的布局，能够在该特定实例上优于现有方法。 【Drawback of Current Approaches】 独立地优化单个表的布局，而不是联合考虑所有表的布局，不能最大限度地提高块跳转性能。 【Qd-tree】 Qd-tree结构。 qd-tree是一棵二叉决策树。每个内部节点包含一个过滤器谓词，即cut，用于将记录子集划分为两个较小的子集，一个满足cut，另一个不满足。qd-tree的叶节点对应数据块。 Qd-tree用法。 我们可以使用qd-tree进行离线块分配和在线查询处理。① 给定一个qd-tree和一个表，通过qd-tree路由表中的每条记录，将其分配到将存储在其中的数据块。② 在查询执行时，使用qd-tree来确定需要访问哪些块。 Qd-tree构造算法。 我们采用贪心方法来构建。在每次迭代中，通过cut将叶节点拆分为两个子节点。从候选cut集合中选择cut中的一个，使结果qd-tree在给定工作负载上跳过的记录数量最大。迭代直至所有叶节点都达到所需的大小。 3 MTO OVERVIEW MTO由两部分组成：① 记录到块的映射，其中每个块具有大致相同数量的记录，块只能包含来自单个表的记录。② 一个方法来确定哪些块可以被跳过。 3.1 Sideways Information Passing 现有的单表布局方法在多表情况下不是最优的，因为它们没有利用表之间的横向信息传递。 以图3为例。设块大小为1M条记录，表A有1M条记录，表B有8M条记录。表A的所有记录将落在同一个块中，因此表A的排序顺序不会影响块跳转。考虑如下工作负载： 1 SELECT COUNT(*) FROM A, B WHERE A.

greenplum服务器 1 进入服务器 1 psql username 2 创建数据库 1 2 3 4 5 # 方法1：在终端使用createdb命令 createdb databasename # 方法2：在PostgreSQL内使用命令 create database databasename 3 列出所有的数据库 1 \l 4 进入其中一个数据库 1 \c databasename 5 返回PostgreSQL主界面 1 \q

1 重复局面 🔗 题目：重复局面 将一盘局的局面表示为一个长度为64的字符串。 建立map映射，key为字符串表示的局面，value为出现的次数。 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 #include<bits/stdc++.h>using namespace std; map<string,int> mp; int n; int main(){ cin>>n; for(int i=0;i<n;i++){ string s="",tmp; for(int j=0;j<8;j++){ cin>>tmp; s = s+tmp; } mp[s] += 1; cout<<mp[s]<<endl; } } 2 矩阵运算 🔗 题目：矩阵运算 改变矩阵运算的顺序，可以减中间结果的存储空间和运行时间。 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 #include<bits/stdc++.

1 创建脚本文件 1 touch test.sh 2 编辑 1 vim test.sh 3 改变权限 1 chmod 700 test.sh 4 执行 1 ./test.sh

1 Tmux简介 Tmux 可以让会话与窗口"解绑"：窗口关闭时，会话并不终止，而是继续运行，等到以后需要的时候，再让会话"绑定"其他窗口。 它允许在单个窗口中，同时访问多个会话。这对于同时运行多个命令行程序很有用。 它可以让新窗口"接入"已经存在的会话。 它允许每个会话有多个连接窗口，因此可以多人实时共享会话。 它还支持窗口任意的垂直和水平拆分。 2 基本使用 1 安装 1 2 # Ubuntu 或 Debian $ sudo apt-get install tmux 2 新建会话 1 $ tmux new -s <session-name> 3 分离会话 在 Tmux 窗口中，按下Ctrl+b d或者输入tmux detach命令。 4 接入会话 1 2 3 4 5 # 使用会话编号 $ tmux attach -t 0 # 使用会话名称 $ tmux attach -t <session-name> 5 杀死会话

参照论文 SWIRL: Selection of Workload-aware Indexes using Reinforcement Learning 在cloudlab提供的服务器上配置代码所需环境，本地机器为 Windows。 1 本地ssh连接远程cloudlab服务器 登录cloudlab官网，注册并租一台服务器。（默认的时长为16小时，注意及时续期，不然服务器上的东西到期会被清理，一般每次续7天） 点击刚刚租好的服务器，打开终端，下面配置本地和远程服务器的ssh连接。 打开本地的.ssh目录（Windows一般是 C:\User\.ssh ），里面有个 id_rsa.pub 文件，用记事本的格式打开这个文件，并复制里面的所有内容，即ssh公钥。 接着在远程服务器终端，打开 .ssh目录，里面有个 authorized_keys 文件，将刚刚复制的公钥粘贴到 authorized_keys 里面（从文件内容最后开始粘贴）。 再打开vscode，进行远程连接（这里需要装一下远程资源管理器，就是remote development）。点击远程资源管理器的设置按钮，在配置文件中添加host、hostname、user。host可以自己随便取，hostname是远程服务器的ip地址，user是远程服务器的用户名。 接着就可以在列表看到新连接的服务器了，右键点击 “connect to host in current window”，没问题就连接成功了，可以直接使用。 2 在cloudlab上安装greenplum 和在本机上装一样，过程参照：ubuntu安装greenplum教程及踩坑记录 3 在cloudlab上安装python3环境 wget工具下载压缩包 1 2 3 4 $ wget https://www.python.org/ftp/python/3.7.9/Python-3.7.9.tgz $ tar -xzvf Python-3.7.9.tgz $ ls gpAdminLogs gpinitsystem_singlenode greenplum hostlist_singlenode Python-3.7.9 Python-3.7.9.tgz 进入解压后的python文件夹，安装python依赖库，并编译安装python 1 2 3 4 5 6 7 8 9 10 11 $ cd Python-3.

1 版本说明 在撰写本文时，Greenplum 的 Ubuntu 版本是为 Ubuntu 的 18.04 和 16.04 LTS（长期支持）发行版构建的。注意最好用 18.04 版本的ubuntu。（一开始用20及以上的，会有一些奇奇怪怪的错误） 2 安装Greenplum 将 Greenplum PPA 存储库添加到 Ubuntu 系统： 1 2 3 sudo apt update sudo apt install software-properties-common sudo add-apt-repository ppa:greenplum/db 更新 Ubuntu 系统以从最近添加的存储库中检索信息： 1 2 sudo apt update sudo apt install greenplum-db-6 上述命令将自动在系统上安装 Greenplum 数据库软件和任何所需的依赖项，并将生成的软件放在 /opt 目录中，如下所示： 将 Greenplum 数据库软件加载到环境中。注意，应该根据安装的 Greenplum 数据库版本选择 Greenplum 软件目录的确切路径。例如，这里是 greenplum-db-6.24.3 ： 1 2 3 source /opt/greenplum-db-6.

1 线性分类器 🔗 题目：线性分类器 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 #include<bits/stdc++.h>using namespace std; struct node{ int x,y; }; int main(){ int n,m,a,b,c,x,y,s; vector<node> v1,v2; char t; cin>>n>>m; for(int i=0;i<n;i++){ cin>>x>>y>>t; if(t=='A') v1.

1 称检测点查询 🔗 题目：称检测点查询 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 #include<bits/stdc++.h>using namespace std; int main(){ int n,x,y,a,b,d,ans[3][2]; scanf("%d %d %d",&n,&x,&y); ans[0][0]=ans[1][0]=ans[2][0]=100000000; for(int i=1;i<=n;i++){ scanf("%d %d",&a,&b); d=(x-a)*(x-a)+(y-b)*(y-b); if(d>=ans[0][0]) continue; else if(d>=ans[1][0]){ ans[0][0]=d,ans[0][1]=i; } else if(d>=ans[2][0]){ ans[0][0]=ans[1][0],ans[0][1]=ans[1][1]; ans[1][0]=d,ans[1][1]=i; } else{ ans[0][0]=ans[1][0],ans[0][1]=ans[1][1]; ans[1][0]=ans[2][0],ans[1][1]=ans[2][1]; ans[2][0]=d,ans[2][1]=i; } } printf("%d\n%d\n%d",ans[2][1],ans[1][1],ans[0][1]); return 0; } 2 风险人群筛查 🔗 题目：风险人群筛查

1 灰度直方图 🔗 题目：灰度直方图 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 #include<bits/stdc++.h>using namespace std; int main(){ int n,m,l,a,h[300]={0}; scanf("%d %d %d",&n,&m,&l); for(int i=0;i<n;i++){ for(int j=0;j<m;j++){ scanf("%d",&a); h[a]++; } } for(int i=0;i<l;i++) printf("%d ",h[i]); return 0; } 2 邻域均值 🔗 题目：邻域均值 🔴 求矩阵中一个框内的元素和：用二维压缩数组 🔵 判断时注意整数除法会向下取整，不能用 if(sum/t<=num) ，而应用 if(sum<=t*num) 。 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 #include<bits/stdc++.

1 期末预测之安全指数 🔗 题目：期末预测之安全指数 1 2 3 4 5 6 7 8 9 10 11 12 13 14 #include<bits/stdc++.h>using namespace std; int main(){ int n,w,s,y=0; scanf("%d",&n); for(int i=0;i<n;i++){ scanf("%d %d",&w,&s); y += w*s; } if(y>0) cout<<y; else cout<<0; return 0; } 2 期末预测之最佳阈值 🔗 题目：期末预测之最佳阈值 用 set 和 map 会方便很多。要找递推关系！！！ 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 #include<bits/stdc++.

1 数组推导 🔗 题目：数组推导 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 #include<bits/stdc++.h>using namespace std; int main(){ int n,s1=0,s2=0,b[105]={0}; scanf("%d",&n); for(int i=1;i<=n;i++) scanf("%d",&b[i]); for(int i=n;i>=1;i--){ s1+=b[i]; if(b[i]>b[i-1]) s2+=b[i]; // a[i]=b[i] } cout<<s1<<endl<<s2<<endl; return 0; } 2 非零段划分 🔗 题目：非零段划分 🔴 这个题目刚看上去有点难，需要找前后的递推关系。倒序遍历 a[n]，来确定 p 的值。用 set 和 map 会方便很多。 🔵 set 的倒序遍历： 1 2 set<int>::reverse_iterator rit; for (rit=s.rbegin();rit!=s.rend();rit++){.....} 完整代码：