Posted Updated Database / SQL DB6 minutes read (About 859 words)

SQL语法

基本操作

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
SELECT			<field>, DISTINCT <field>
INTO			<new_tbl> [IN <other_db>]
FROM			<tbl>
WHERE			<field> <OP> <value>/<field>
ORDER BY		<field> [ASC/DESC];

INSERT INTO		<tbl>[<field>]
VALUES			(<value>);

UPDATE			<tbl>
SET				<field> = <value>
WHERE			<field> <OP> <value>/<field>;

DELETE
FROM			<tbl>
WHERE			<field> <OP> <value>/<field>;

数据库、表、索引、视图

创建

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
!-- 创建数据库
CREATE DATABASE <db_name>;

!-- 创建表
CREATE TABLE <tbl>(
	<field>		<dtype>,
	<field>		<dtype>		<CSTRT>,					!-- MSSQL、ORACLE
	<CSTRT>		(<field>,),								!-- MySQL
	CONSTRAINT [<cstrt_name>] <cstrt> (<field>,)		!-- common
)

!-- 创建索引
CREATE INDEX <index_name>
ON <tbl> (<field>);

!-- 创建视图
CREATE VIEW <view_name> AS
<select_expr>;
自增字段
1
2
3
4
5
6
7
8
9
10
!-- MSSQL
<field> <dtype> IDENTITY
!-- MySQL
<field> <dtype> AUTO_INCREMENT
!-- ORACLE：创建自增序列，调用`.nextval`方法获取下个自增值
CREATE SEQUENCE <seq>
MINVALUE <min>
START WITH <value>
INCREMENT BY <step>
CACHE <cache>				!-- 提高性能

丢弃

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
!-- 丢弃索引
!-- MSSQL
DROP INDEX <tbl>.<index_name>;
!-- ORACLE
DROP INDEX <index_name>;
!-- MySQL
ALTER TABLE <tbl>
DROP INDEX <index_name>;

!-- 丢弃表/数据
DROP TABLE <tbl>;
TRUNCATE TABLE <tbl>;

!-- 丢弃数据库
DROP DATABASE <db_name>;

!-- 丢弃视图
DROP VIEW <view>;

修改表

1
2
3
4
5
6
7
8
9
10
11
!-- 添加列
ALTER TABLE <tbl>
ADD <field> <dtype>;

!-- 删除列
ALTER TABLE <tbl>
DROP COLUMN <field>;

!-- 修改类型
ALTER TABLE <tbl>
ALTER COLUMN <field> <dtype>;

关键字

TOP

  • MSSQL：SELECT TOP <num>/<num> PERCENT *
  • MYSQL：LIMIT <num>
  • ORACLE：WHERE ROWNUM <= <num>

Alias

  • AS：指定行、列别名

Join

  • [INNER] JOIN
  • LEFT JOIN
  • RIGHT JOIN
  • FULL JOIN

Union

  • UNION：合并SELECT结果集
    • 要求结果集中列数量、类型必须相同

NULL

  • IS [NOT] NULL：比较是否为NULL值
  • 比较符无法测试NULL值

符号

运算符

  • =：有些方言可以使用==
  • <>：有些方言可以使用!=
  • >
  • <
  • >=
  • <=
  • BETWEEN <value> AND <value>
  • [NOT] IN (<value>)
  • [NOT] LIKE <pattern>
    • %：匹配0个、多个字符
    • _：匹配一个字符
    • [<char>]：字符列中任意字符
    • ^[<char>]/[!<char>]：非字符列中任意字符

逻辑运算

  • AND
  • OR

符号

  • '：SQL中使用单引号包括文本值
    • 大部分方言也支持"双引号

数据类型

MySQL

TEXT类型 描述
CHAR([<size>])
VARCHAR([<size>])
TINYTEXT
LONGTEXT
MEDIUMITEXT
BLOB
MEDIUMBLOB
LONGBLOB
ENUM(<val_list>)
SET
NUMBER类型 描述
TINYINT([<size>])
SMALLINT([<size>])
MEDIUMINT([<size>])
INT([<size>])
BIGINT([<size>])
FLOAT([<size>])
DOUBLE([<size>])
DECIMAL([<size>])
DATE类型 描述
DATE()
DATETIME()
TIMSTAMP()
TIME()
YEAR()

MSSQL

ASCII类型 描述
CHAR([<size>])
VARCHAR([<size>])
TEXT
UNICODE类型 描述
CHAR([<size>])
VARCHAR([<size>])
text
BINARY类型 描述
bit
binary([<n>])
varbinary([<n>])
image
NUMBER类型 描述
TINYINT
SMALLINT
MEDIUMINT
INT
BIGINT
DECIMAL(p, s)
FLOAT([<n>])
REAL
SMALLMONEY
MONEY
DATE类型 描述
DATETIME
DATETIME2
SMALLDATETIME
DATE
TIME
DATETIMEOFFSET
TIMESTAMP

约束

  • 建表时添加约束

    • MSSQL、ORACLE：可直接在字段声明后添加约束
    • MySQL：需独立指定约束

  • 向已有表添加约束

    • 可以添加匿名、具名约束
    • MSSQL、ORACLE：有COLUMN关键字

  • 删除约束

    • MySQL：使用约束关键字指定
    • MSSQL、ORACLE：使用CONSTRAINT关键字指定

NOT NULL

1
<field> <dtype> NOT NULL

DEFAULT

DEFAULT

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
!-- 建表
<field> <dtype> DEFAULT <value>

!-- 已有表添加
!-- MySQL
ALTER TABLE <tbl>
ALTER <field> SET DEFAULT <value>;
!-- MSSQL、ORACLE
ALTER TABLE <tbl>
ALTER COLUMN <field> SET DEFAULT <value>;

!-- 删除
!-- MySQL
ALTER TABLE <tbl>
ALTER <field> DROP DEFAULT;
!-- MSSQL、ORACLE
ALTER TABLE <tbl>
ALTER COLUMN <field> DROP DEFAULT;

UNIQUE

UNIQUE

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
!-- 建表
!-- MySQL、MSSQL、ORACLE
CONSTRAINT [<cstrt_name>] UNIQUE (<field>,)
!-- MySQL
UNIQUE [KEY] [<cstrt_name>] (<field>)
!-- MSSQL、ORACLE
<field> <dtype> UNIQUE

!-- 已有表添加
!-- MySQL、MSSQL、ORACLE
ALTER TABLE <tbl>
ADD UNIQUE(<field>);
ALTER TABLE <tbl>
ADD CONSTRAINT <cstrt_name> UNIQUE(<field>,);

!-- 删除
!-- MySQL
ALTER TABLE <tbl>
DROP INDEX <cstrt_name>;
!-- MSSQL、ORACLE
ALTER TABlE <tbl>
DROP CONSTRAINT <cstrt_name>;

PRIMARY KEY

PRIMARY KEY

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
!-- 建表
!-- MySQL、MSSQL、ORACLE
CONSTRAINT [<cstrt_name>] PRIMARY KEY (<field>,)
!-- MYSQL
PRIMARY KEY (<field>,)
!-- MSSQL、ORACLE
<field> <dtype> PRIMARY KEY


!-- 已有表添加
!-- MySQL、MSSQL、ORACLE
ALTER TABLE <tbl>
ADD PRIMARY KEY (<field>,);
ALTER TABLE <tbl>
ADD CONSTRAINT <cstrt_name> PRIMARY KEY (<field>,);

!-- 删除
!-- MySQL
ALTER TABLE <tbl>
DROP PRIMARY KEY;
!-- MSSQL、ORACLE
ALTER TABLE <tbl>
DROP CONSTRAINT <cstrt_name>;

FOREIGN KEY

FOREIGN KEY

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
!-- 建表
!-- MySQL、MSSQL、ORACLE
CONSTRAINT [<cstrt_name>] FOREIGN KEY (<field>,)
REFERENCES <tbl>(<field>,)
!-- MYSQL
FOREIGN KEY (<field>,)
REFERENCES <tbl>(<field>,)
!-- MSSQL、ORACLE
<field> <dtype> FOREIGN KEY
REFERENCES <tbl>(<field>,)


!-- 已有表添加
!-- MySQL、MSSQL、ORACLE
ALTER TABLE <tbl>
ADD FOREIGN KEY (<field>,)
REFERENCES <tbl>(<field>,);
ALTER TABLE <tbl>
ADD CONSTRAINT <cstrt_name> FOREIGN KEY (<field>,)
REFERENCES <tbl>(<field>);

!-- 删除
!-  MySQL
ALTER TABLE <tbl>
DROP FOREIGN KEY <cstrt_name>;
!-- MSSQL、ORACLE
ALTER TABLE <tbl>
DROP CONSTRAINT <cstrt_name>;

CHECK

CHECK

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
!-- 建表
!-- MySQL、MSSQL、ORACLE
CONSTRAINT [<cstrt_name>] CHECK(<condition>)
!-- MySQL
CHECK (condition)
!-- MSSQL、ORACLE
<field> <dtype> CHECK(<condition>)

!-- 已有表添加
!-- MySQL、MSSQL、ORACLE
ALTER TABLE <tbl>
ADD CHECK (condition);
ALTER TABLE <tbl>
ADD CONSTRAINT <cstrt_name> CHECK (condition);

!-- 删除
!-- MySQL
ALTER TABLE <tbl>
DROP CHECK <cstrt_name>;
!-- MSSQL、ORACLE
ALTER TABLE <tbl>
DROP CONSTRAINT <cstrt_name>;

内建函数

Date

  • MySQL

    • NOW()
    • CURDATE()
    • CURTIME()
    • DATE()
    • EXTRACT()
    • DATE_ADD()
    • DATE_SUB()
    • DATE_DIFF()
    • DATE_FORMAT()

  • MSSQL

    • GETDATE()
    • DATEPART()
    • DATEADD()
    • DATEDIFF()
    • CONVERT()

NULL

  • MSSQL

    • ISNULL(<field>, <replacement>)

  • ORACLE

    • NVL(<field>, <repalcement>)

  • MySQL

    • IFNULL(<field>, <replacement>)
    • COALESCE(<field>, <replacement>)

Aggregate聚集函数

Scalar

Posted Updated Database / Hadoop11 minutes read (About 1679 words)

Hive

Hive简介

Hive是Hadoop平台上的数据仓库，面向结构化数据分析

  • 将结构化数据文件映射为一张数据库表

  • 提供完整的SQL查询功能，所用语言称为HiveQL

    • Hive将HiveQL转换为MapReduce作业，在hadoop平台运行
    • Hive相当于一个在hadoop平台上的SQL Shell
    • 方便用户使用HiveQL快速实现简单数据分析、统计，而不必 开发专用MapReduce程序，学习成本低

  • 相较于传统关系数据库，Hive具有如下特点

    ||Hive|传统关系型数据库| |———|———|———-| |数据存储|HDFS分布式文件系统|服务器本地文件系统| |查询处理|MapReduce计算模型|自行设计的查询处理模型| |应用场景|海量数据分析处理|高性能查询，实时性好| |数据更新|不支持对具体数据行修改，只能覆盖、追加|支持| |事务处理|不支持|支持| |索引支持|不支持，一般需要对数据进行全部扫描|支持，多种索引| |扩展能力|基于Hadoop平台，存储、计算强大的扩展能力|扩展性较差| |数据加载|Writing Time Schema：数据加载时无需进行模式检查，在读取数据时对数据以一定模式进行解释|Reading Time Schema：要求数据必须符合数据库表结构|

Hive服务端组件

Driver

负责将用户的编写的HiveQL查询语句进行解析、编译、优化、生成 执行计划，然后调用底层MapReduce计算模型执行，包括

  • Compiler：编译器
  • Optimizer：优化器
  • Executor：执行器

MetaStore

元信息管理器，对Hive正确运行举足轻重

  • MetaStore实际上就是Thrift服务

    • MetaStore客户端（hive、spark shell等）和服务端通过 thrift协议进行通信
    • 客户端通过连接metastore服务，实现对元数据的存取
    • 通过Thrift获取元数据，屏蔽了访问MetaStore Database 所需的驱动、url、用户名、密码等细节

  • 负责存储元数据在关系型数据库（称为MetaStore Database）

    • 元数据包括Hive创建的database、table等元信息
    • 支持的关系型数据库
      • Derby：Apache旗下Java数据库
      • MySQL

  • MetaStore服务可以独立运行，可以让多个客户端同时连接、 甚至安装到远程服务器集群，保持Hive运行的健壮性

Embedded Metastore Server(Database Derby)

内嵌模式：使用内嵌的Derby数据库存储元数据

  • 不需要额外起Metastore服务
  • 一次只能一个客户端连接，使用做实验，不适合生产环境
  • Derby默认会在调用hive命令所在目录的metastore_db文件中 持久化元数据

embeded_metastore_database

Local Metastore Server

本地元存储

  • 采用外部数据库，支持

    • MySQL
    • Postgres
    • Orcale
    • MSSQL

  • 数据库独立于hive部署，hive服务使用JDBC访问元数据，多个 服务可以同时进行

  • 本地元存储不需要单独起metastore服务，用的是跟hive在同一 进程metastore服务

local_metastore_server

Remote Metastore Server

远程元存储

  • 类似于本地元存储，只是需要单独启动metastore服务，和hive 运行在不同的进程（甚至主机）中

  • 需要在每个客户端配置文件配置连接到该metastore服务

    • hive通过thrift访问metastore

  • 此模式可以控制到数据库的连接

remote_metastore_server

hiveserver2

基于的Thrift RPC实现

  • 远程客户端可以通过hiveserver2执行对hive的查询并返回结果

    • 支持多客户端并发、身份验证

  • 可以使用JDBC、ODBC、Thrift连接hiveserver2（Thrift Server 特性）

  • hiveserver2也能访问元数据，不依赖于metastore服务

Hive客户端组件

CLI

Command Line Interface

  • 允许用户交互式的使用Hive

THrift Client/beeline

基于Thrift的JDBC Client

  • 包括JDBC/ODBC驱动程序

WEB GUI

允许用户通过WEB GUI图形界面访问Hive

  • 需要首先启动Hive Web Interface服务

Hive查询处理

过程

  1. 用户提交HQL至Driver
  2. Driver把查询交给Compiler，Compiler使用MetaStore中元信息 检查、编译
  3. 查询经过Optimizer优化交由Executor Engine执行，转换为 MapReduce作业后调用MapReduce执行
  4. MapReduce存取HDFS，对数据进行处理，查询结果返回Driver

数据类型

  • 基础数据类型

    • Integer
    • Float
    • Double
    • String

  • 复杂数据类型：通过嵌套表达复杂类型

    • Map
    • List
    • Struct

  • 还允许用户自定以类型、函数扩展系统

数据存储模型

使用传统数据库：Table、Row、Column、Partition等概念，易于 理解

Database

相当于关系型数据库中的Namespace

  • 将不同用户数据隔离到不同的数据库、模式中

Table

表格

  • 逻辑上由存储的数据、描述数据格式的相关元数据组成

    • 表格数据存放在分布式文件系统（HDFS）中
    • 元数据存储在MetaStore服务指定关系型数据库中

  • 创建表格、加载数据之前，表格在HDFS中就是一个目录， 表格分为两种类型

    • 托管表：数据文件存放在Hive数据仓库中，即HDFS中的一个 目录，是Hive数据文件默认存放路径
    • 外部表：数据文件可以存放在其他文件系统中

Partition

根据“分区列”的值，对表格数据进行粗略划分的极值

  • 存储上：是Hive中表格主目录的子目录，名字即为定义的分区列 名字

  • 逻辑上：分区不是表中的实际字段，是虚拟列

    • 根据虚拟列（可能包含多个实际字段）划分、存储表格数据
    • 同一虚拟列中字段通常应该经常一起被查询，这样在需要 存取部分数据字段时，可以只扫描部分表

Bucket

Table、Partition都是目录级别的数据拆分，指定Bucket的表格， 数据文件将按照规律拆分成多个文件

  • 每个桶就是table、partition目录中的文件

  • 一般使用Hash函数实现数据分桶，创建表时，需要指定桶数量、 分桶操作依据的列

  • 用户执行Sample查询时，Hive可以使用分桶信息，有效的Prune Data，如：对每个目录下单个桶文件进行查询

Posted Updated Database23 minutes read (About 3403 words)

物理查询优化

查询代价估算

代价模型

代价估计模型：基于CPU代价、IO代价

  • $P$：计划访问的页面数
  • $CPUTimePerPage$：读取每个页面的时间花费
  • $T$：访问的元组数，索引扫描应包括索引读取花费
    • 反映CPU代价，因为访问页面上的元组需要解析元组结构， 消耗CPU
  • $W$：selectivity，选择率/权重因子，表明IO、CPU的相关性

Selectivity

选择率：在关系R中，满足条件A <cond_op> a的元组数R和 所有元组数N的比值

  • 在CBO中占有重要地位
  • 其精确程度直接影响最优计划的选择

估计方法

  • Non-Parametric Method：非参方法，使用ad-hoc数据结构、 直方图维护属性值分布

  • Parametric Method：参数方法，使用预先估计的分布函数 逼近真实分布

  • Curve Fitting：曲线拟合法，使用多项式函数、最小标准差 逼近属性值分布

  • Sampling：抽样法，从数据库中抽取部分元组，针对样本进行 查询，收集统计数据

    • 需要足够多样本被测试才能达到足够精度

  • 综合法

单表扫描算法

索引

两表联接算法

todo

Nested Loop

嵌套循环联接算法：扫描外表，读取记录根据join字段上的 索引去内表中查询

  • 适合场景
    • 外表记录较少（<1w）
    • 内表已经创建索引、性能较好
    • inner、left outer、left semi、left antisemi join

嵌套循环联接算法

  • 搜索时扫描整个表、索引
1
2
3
4
for each row R1 in the outer table:
	for each row R2 in the inner table:
		if R1 join with R2:
			return (R1, R2)
  • 外部循环逐行消耗外部输入表，当其数据量很大时可以并行扫描 内表
  • 内表被外表驱动：内部循环为每个外部行执行，在内表中搜索 匹配行

基于块嵌套循环联接算法

  • 每次IO申请以“块”为单位尽量读入多个页面
  • 改进获取元组的方式
1
2
3
4
5
6
7
8
9
10
for each chunk c1 of t1
	if c1 not in memory:
		read chunk c1 to memory
	for each row r1 in chunk c1:
		for each chunk c2 of t2:
			if c2 not in memory:
				read chunk c2 into memory
			for each row r2 in c2:
				if r1 join with r2:
					return(R1, R2)
  • 内存循环最后一个块使用后作为下次循环循环使用的第一个块 可以节省一次IO

索引嵌套循环联接算法

  • 索引嵌套循环连结：在内表中搜索时使用索引，可以加快联接 速度
  • 临时索引嵌套循环连结：为查询临时生成索引作为查询计划的 一部分，查询完成后立刻将索引破坏

(Sort)Merge Join

排序归并联接算法

  • 适合场景
    • 联接字段已经排序，如B+树索引
    • inner、left outer、left semi、left anti semi、 right outer、right semi、right anti semi join、union
    • 等值、非等值联接，除!=/<>

算法

  • 确保两个关联表都是按照关联字段进行排序

    • 若关联字段已经有排序一致的可用索引，可以利用索引直接 进行merge join操作
    • 否则先对关联字段进行排序，表过大无法一次载入内存时 需要分块载入

  • 从每个表分别取记录开始匹配（升序）

    • 若符合关联条件，放入结果集
    • 否则丢关联字段较小记录，取对应表中下条记录继续 匹配，直到整个循环结束
    • 对于多对join，通常需要使用临时表进行操作

      todo

Hash Join

哈希联接：利用Hash Match联接

  • HJ处理代价非常高，是服务器内存、CPU头号杀手，需要对数据 进行分区时，还会造成大量异步磁盘I/O，避免大数据的HJ， 尽量转化为高效的SMJ、NLJ

    • 表结构设计：冗余字段
    • 索引调整设计
    • SQL优化
    • 冗余表：静态表存储统计结果

  • 类似任何hash算法，内存小、数据偏斜严重时，散列冲突会比较 严重，此时应该考虑使用NIJ

  • 适合场景

    • 两表数据量相差非常大
    • 对CPU消耗明显，需要CPU资源充足
    • 只适合（不）等值查询

In-Memory Hash Join

db_hash_join

build阶段

以操作涉及字段为hash key构造hash表

  • 从构造输入表中取记录，使用hash函数生成hash值

  • hash值对应hash表中的buckets，若一个hash值对应多个桶， 则使用链表将联接桶

  • 构造输入表处理完毕之后，其中记录都被桶关联

  • build表构建的hash表需要频繁访问，最好能全部加载在内存中 ，因此尽量选择小表，避免使用GHJ
probe阶段

  • 从探测输入中取记录，使用同样hash函数生成hash值

  • 根据hash值，在构造阶段构造的hash表中搜索对应桶

  • 为避免冲突，bucket可能会联接到其他bucket，探测操作 会搜索整个冲突链上的buckets查找匹配记录
具体操作

以下操作内部实现其实都是hash join，只是对应算符不同而已

  • join操作

    • 使用join字段计算hash值
    • 使用顶端输入构造hash表，底端输入进行探测
    • 按照联接类型规定的模式输出（不）匹配项
    • 若多个联接使用相同的联接列，这些操作将分组为一个 哈希组

  • grouby操作、unique操作

    • 使用groupby字段、所有select字段计算hash值
    • 使用输入构造hash表，删除重复项、计算聚合表达式
    • 扫描hash表输出所有项

  • union操作、需要去除重复记录操作

    • 所有select字段计算hash值
    • 第一个输入构建hash表，删除重复项
    • 第二个输入进行探测
      • 若第二个输入没有重复项，直接返回没有匹配的项， 扫描hash表返回所有项
      • 若第二个输入有重复项，则应该需要继续构建hash表， 最后统一输出整个hash表

Grace Hash Join

grace hash join：磁盘分块HJ

  • 将两表按照相同hash函数分配至不同分片中

    • 在磁盘上为各分片、表建立相应文件
    • 对表输入计算哈希值，根据哈希值写入分片、表对应文件

  • 再对不同分片进行普通in-memory hash join

    • 若分片依然不能全部加载至内存，可以继续使用 grace hash join
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
grace_hash_join(t1, t2):
	// Grace Hash Join实现
	// 输入：待join表t1、t2
	for row in t1:
		hash_val = hash_func(row)
		N = hash_val % PART_COUNT
		write row to file t1_N

	for row in t2:
		hash_val = hash_func(row)
		N = hash_val % PART_COUNT
		write row to file t2_N

	for i in range(0, PART_COUNT):
		join(t1_i, t2_i)

  • 分片数量PART_COUNT决定磁盘IO效率

    • 分片数量过小：无法起到分治效果，分片仍然需要进行 grace hash join，降低效率
    • 分片数量过大：磁盘是块设备，每次刷盘刷一定数量块才 高效，频繁刷盘不经济
    • 即分片数量在保证刷盘经济的情况下，越大越好，这需要 优化器根据表统计信息确定

  • 特点

    • 有磁盘I/O代价，会降低效率
    • 适合参与join表非常大，无法同时载入内存中

Hybrid Hash Join

hybrid hash join：GHJ基础上结合IMHJ的改进

  • 对build表分片过程中，尽量多把完整分片保留在内存中
  • 对probe表分片时，对应分片可以直接进行probe操作
  • hybrid hash join有时也被直接视为grace hash join， 不做区分

比较

  • 资源消耗

    • HJ：CPU计算、内存（磁盘）中创建临时hash表
    • SMJ：磁盘I/O（扫描表、索引）
    • NLJ：磁盘I/O

  • 性能

    • 通常情况：HJ > NPJ <> SMJ

      • 全表扫描比索引范围扫描再进行表访问更可取时，SMJ 优于NPJ？？？
      • 而表特别小、特别大时，全表扫描优于索引范围扫描

    • 但若关联字段已排序，SMJ性能最优

  • 首条搜索结果

    • NPJ能快速返回首条搜索结果
    • HJ、SMJ返回首条结果较慢

多表联接算法

多表联接算法：找到最优连接顺序（执行路径）

  • 表联接顺序对于查询结果没有影响，但是对资源消耗、性能影响 巨大

  • 随着需要联接表数目增加，可能的联接排列非常多，基本不能 对所有可能穷举分析

    • left-deep tree/linear (processing)tree：$n!$
    • bushy tree：$\frac {2(n-1)!} {(n-1)!}$ （包括left-deep tree、right-deep tree）

    left_deep_tree_bushy_tree

  • 事实上查询优化器不会穷尽搜索所有可能联接排列，而是使用 启发式算法进行搜索

Dynamic Programming

动态规划算法：依次求解各数量表最优联接顺序，直到求出最终结果

  1. 构造第一层关系：每个关系的最优路径就是关系的最优单表扫描 方式

  2. 迭代依次构造之后n-1层关系联接最优解

    • 左深联接树方式：将第k-1层每个关系同第1层关系联接
    • 紧密树联接方式：将第m(m > 2)层每个关系同第k-m层关系 联接

    left_deep_tree_bushy_tree

Heuristic Algorithm

Greedy Algorithm

贪心算法：认为每次连接表的连接方式都是最优的，即从未联接表中 选择使得下次联接代价最小者

  • 多表排序一般为

    • 常量表最前
    • 其他表按可访问元组数量升序排序

  • 贪心算法得到的联接方式都是最优的

    • 则每次联接主要求解要联接表对象的最佳访问方式
    • 即每次代价估计的重点在于单表扫描的代价

  • 求解结束后，局部最优查询计划生成

    • 得到左深树
    • 最初始表位于最左下端叶子节点处

System R

System R：对动态规划算法的改进

  • 保留子树查询最优、次优查询计划，用于上层查询计划生成， 使得查询计划整体较优

Genetic Algorithm

遗传算法：模拟自然界生物进化过程，采用人工进化的方式对目标 空间进行搜索

  • 本质是高效、并行、全局搜索方法
  • 能在搜索过程中自动获取、积累有关搜索空间的知识，并自适应 的控制搜索过程以求的最佳解

思想

  • 将问题域中可能解看作是染色体，将其编码为符号串的形式
  • 对染色体群体反复进行基于遗传学的操作：选择、交叉、变异
  • 根据预定目标适应度函数对每个个体进行评价，不断得到更优 群体，从中全局并行搜索得到优化群体中最优个体

实体

  • population：群体，GA的遗传搜索空间
  • individual：个体，搜索空间中可能解
  • chromosome：染色体，个体特征代表
    • 由若干段基因组成
    • GA中基本操作对象
  • gene：基因
    • 染色体片段
  • fitness：适应度，个体对环境的适应程度

基本操作

  • selection：选择，根据个体适应度在群体中按照一定概率 选择个体作为父本

    • 适应度大个体被选择概率高
    • 体现了适者生存、优胜劣汰的进化规则

  • crossover：交叉，将父本个体按照一定概率随机交换基因 形成新个体

  • mutate：变异，按照一定概率随机改变某个体基因值

涉及问题

  • 串编码方式

    • 把问题的各种参数用二进串进行编码构成子串
    • 把子串拼接成染色体
      • 串长度、编码方式对算法收敛影响极大

  • 适应度/对象函数确定

    • 一般可以把问题模型函数作为对象函数

  • GA超参设置

    • 群体大小$n$：过小难以求出最优解，过大难收敛，一般取 $n = 30 ~ 160$
    • 交叉概率$P_c$：太小难以前向搜索，太大容易破坏高适应 值结构，一般取$P_c = 0.25 ~ 0.75$
    • 变异概率$P_m$：太小难以产生新结构，太大则变为单纯 随机搜索，一般取$P_m = 0.01 ~ 0.2$

算法

  1. 随机初始化种群
  2. 估初始种群：为种群每个个体计算适应值、排序
  3. 若没有达到预定演化数，则继续，否则结束算法
  4. 选择父体
    • 杂交：得到新个体
    • 变异：对新个体变异
  5. 计算新个体适应值，把适应值排名插入种群，淘汰最后个体
  6. 重复3
Posted Updated Database / SQL DB17 minutes read (About 2484 words)

Postgre SQL笔记

安装

  • 交互式客户端：postgresql
  • 服务器：postgres-server
  • 额外功能：postgresql-contrib
  • 开发工具：postgresql-devel

OpenSuSe

1
2
$ sudo zypper in postgresql postgresql-server \
	postgresql-contrib postgresql-devel

CentOS

1
2
$ sudo yum install postgresql postgresql-server \
	postgresql-contrib postgresql-devel

其他版本

  • 从中选择合适版本下载：Postgres Yum repositories

    1
    $ wget https://download.postgresql.org/pub/repos/yum/9.6/redhat/rhel-7-x86_64/pgdg-centos96-9.6-3.noarch.rpm

  • 安装下载的RPM（依赖EPEL repo）

    1
    $ sudo yum install pgdg-centos96-9.6-3.noarch.rpm

  • 更新Yum、安装指定PG版本

    1
    2
    $ sudo yum update
    $ sudo yum install postgresql96-sever postgresql96-contrib
  • 安装的PG带有版本后缀，初始化、启动时注意

配置

  • postgres安装完成后，默认创建Linux用户

    • 用户密码为空，要为其设置密码以切换到其
      1
      2
      $ sudo passwd postgres
      $ su - postgres
    • 用户目录默认是/var/lib/pgsql
    • 很多命令可以切换到用户postgres直接执行
  • 初始化数据库簇后，默认创建数据库角色postgres、数据库 postgres

初始化

  • 创建新PostgreSQL数据库簇

    1
    2
    3
    $ sudo postgresql-setup initdb
    	# 或
    $ sudo inidb -D /var/lib/pgsql/data
    • 默认数据库存储路径为/var/lib/pgsql/data

  • 开启PG密码认证：修改host-based authentication设置

    1
    2
    3
    4
    # /var/lib/pgsql/data/pg_hba.conf
    # TYPE		DATABASE	USER	ADDRESS			MEHTOD
    host		all			all		127.0.0.1/32	md5
    host		all			all		::1/128			md5
    • 替换默认ident为md5开启密码认证
    • 修改之后需要重启PG

  • 修改postgres用户密码，以可以通过密码作为postgres连接 数据库

    1
    2
    3
    $ su - postgres
    $ psql -d template1 -c "ALTER USER postgres with password '<passwd>'"
    	# 也可以在数据库prompt中执行

启动数据库

  • 作为服务：start、enablePG

    1
    2
    $ sudo systemctl start postgresql
    $ sudo systemctl enable postgresql

  • 作为普通程序启动：pg_ctl

    1
    2
    $ su - postgres
    $ pg_ctl start -D /var/lib/pgsql/data

Roles

PG使用概念roles处理认证、权限问题

  • 角色相较于区分明显的用户、组概念更加灵活

  • create user和create role几乎完全相同

    • create user：创建角色默认带LOGIN属性
    • create role：创建角色默认不带LOGIN属性

权限

  • SUPERUSER/NOSUPERUSER：数据库超级用户
  • CREATEDB/NOCREATEDB：创建数据库
  • CREATEUSER/NOCREATEUSER
  • CREATEROLE/NOCREATEROLE：创建、删除普通用户角色
  • INHERIT/INHERIT：角色可以继承所属用户组权限
  • LOGIN/NONLOGIN：作连接数据库初始角色名
  • REPLICATION/NOREPLICATION：流复制时用到
  • CONNECTION LIMIT connlimit
  • [ENCRYPTED/UNENCRYPTED]PASSWORD '<passwd>'
  • VALID UNTIL '<timestamp>'
  • IN ROLE <role_name>[, ...]：角色所属用户组
  • IN GROUP <role_name>[, ...]
  • ROLE <role_name>[, ...]
  • ADMIN <role_name>[, ...]
  • USER <role_name>[, ...]
  • SYSID uid

角色赋权

1
2
3
4
5
psql> create role/user <name> [[with] <option> [...]];
	# 创建角色时直接赋权
psql> alter role/user <name> [[with] <option> [...]];
psql> grant connect on database <db_name> to <name>;
	# 修改已创建角色权限

组赋权

  • 把多个角色归为组，通过给组赋权、撤销权限实现权限管理
  • PG中角色赋权是通过inherit方式实现的
1
2
3
4
5
6
7
psql> create role father login createdb createrole;
	# 创建组角色、赋权
psql> create role son1 inherit;
psql> grant father to son1;
	# 创建有`inherit`权限的用户、赋权
psql> create role son2 inherit in role father;
	# 创建用户时直接赋组权

认证方式

Peer Authentication

peer：从内核中获取操作系统中用户名，作为数据库角色名连接

  • 默认连接同名数据库
  • 信任Linux用户身份（认证），不询问密码
    • 即使-W强制输入密码，也不会检查密码正确性
  • 只有local连接支持此方法

Trust Authentication

trust：允许任何数据库角色名的连接

  • 信任任何连接、不询问密码

    • 只应该在操作系统层面上能提供足够保护下情况下使用
      • 文件系统权限：限制对Linux域套接字文件的访问
    • 适合单用户、本地连接

  • 数据库、用户权限限制仍然存在

Ident Authentication

ident：从ident服务器中获取操作系统中用户名，用于连接数据库

  • 仅在TCP/IP连接情况下支持

    • 若被指定给local连接，将使用peer认证

  • 数据库服务器向客户端ident服务器询问“连接数据库的”用户， 据此判断连

    • 此流程依赖于客户端完整性，若客户端机器不可信，则 攻击者可以在113端口执行任何程序返回任何用户名
    • 故此认证方法只适合封闭网络，所以客户端机器都被严格 控制
    • 有些ident服务器开启非标准选项导致返回的加密用户名， 此选项应该关闭
    • 基本每个类Unix操作系统都带有ident服务器，用于监听 113端口TCP
涉及配置
  • map：运行系统、数据库用户名之间映射

Password Authentication

Password认证：基于密码的认证方式

  • password：明文传输密码验证
  • md5：MD5-hashed传输密码o

  • md5可以避免密码嗅探攻击

  • password总应该尽量避免使用

    • 启用db_user_namespace特性时无法使用md5
    • SSL加密连接下password也能安全使用

  • 每个数据库的密码存储在pg_authid系统表中

    • 若用户没有设置密码，则存储的密码为null，密码验证 也总是失败
    • 使用create user、alter role等SQL语句修改密码

GSSAPI Authentication

GSSAPI：定义在RFC 2743中的安全认证产业界标准协议

  • GSSAPI为支持其的系统自动提供认证
    • 认证本身是安全的，但是通过数据库连接的数据默认没有 加密，除非使用SSL
  • PG中GSSAPI需要编译时启用支持

SSPI Authentication

negotiate：windows的安全认证技术

  • PG将尽可能使用Kerberos，并自动回滚为NTLM
  • 仅服务器、客户端均在windows下或GSSAPI可用的情况下才能 工作
  • 使用Kerberos情况下，SSPI、GSSAPI工作方式相同
涉及配置
  • include_realm
  • map
  • krb_realm

Kerberos Authentication

Kerberos：适合公共网络上分布式计算的产业界标准安全认证系统

  • Kerberos提供不加密的语句、数据安全认证，若需要加密则使用 SSL
  • PG支持Kerberos第5版，需要在build时开启Kerberos支持
涉及配置
  • map
  • include_realm
  • krb_realm
  • krb_server_hostname

LDAP Authentication

LDAP：类似password，只是使用LDAP作为密码认证方法

涉及配置
  • ldapserver
  • ldapport
  • ldaptls
  • ldapprefix
  • ldapsuffix
  • ldapbasedn
  • ldapbinddn
  • ldapbindpasswd
  • ldapsearchattribute

RADIUS Authentication

RADIUS：类似password，只是使用RADIUS作为密码认证方法

涉及配置
  • radiusserver
  • radiussecret
  • radiusport
  • radiusidentifier

Certificate Authentication

Certificate：使用SSL客户多证书进行认证

  • 所以只在SSL连接中可用
  • 服务器要求客户端提供有效证书，不会向客户端传递密码prompt
    • cn属性（common name）将回和目标数据库的用户名 比较
    • 可通过名称映射允许cn属性和数据库用户名不同
涉及配置
  • map：允许系统、数据库用户名之间映射

PAM Authentication

PAM：类似password，只是使用 PAM(Pluggable Anthentication Modules)作为密码认证机制

涉及配置
  • parmservice：PAM服务名
    • 默认postgresql

pg_ctl

pg_ctl：用于控制PostgreSQL服务器的工具，此工具基本需要在 postgres用户下才能使用

  • 查看状态：$ pg_ctl status -D /var/lib/pgsql/data

psql

Shell

连接数据库

1
$ psql [-h <host>] [-p <port>] [-U <user_name>] [[-d] <db_name>]
  • -h：缺省为local类型连接本地数据库
    • local、host连接类型对应不同认证方式
    • -h localhost和缺省对应不同hba.conf条目
  • -p：缺省端口5432
  • -U/--user_name=：缺省linux用户名
  • [-d]/--database=：当前linux用户名
  • -W：密码，peer、trust模式下无价值

Shell命令

  • postgres不仅仅提供psql交互环境作为shell命令，还提供可以 直接在shell中运行的数据库命令

    • 当然前提是当前linux登陆用户在数据库中存在、有权限
1
2
3
4
$ createdb <db_name> [-O <user_name>]
	# 创建数据库，设置所有权为`user_name`
$ dropdb <db_name>
	# 删除数据库

元命令

元命令：反斜杠命令，\开头，由psql自己处理

  • \后：跟命令动词、参数，其间使用空白字符分割

  • 冒号:：不在引号中的冒号开头的参数会被当作psql变量

  • 反点号：参数内容被当作命令传给shell， 输出（除去换行符）作为参数值

  • 单引号'：参数包含空白时需用单引号包o，其中包含的参数 的内容会进行类C的替换

    • \n（换行）、\digits（八进制）
    • 包含单引号需要使用反斜杠转义

  • 双引号\”<\code>

    • 遵循SQL语法规则，双引号保护字符不被强制转换为 小写，且允许其中使用空白
    • 双引号内的双引号使用双双引号""转义

帮助

  • \?

    • [<commands>]：元命令帮助
    • <options>：psql命令行选项帮助
    • <variables>：特殊变量帮助

  • \h [<clauses>]：SQL命令语法帮助（*表示全部）

展示信息

  • \du：查看用户权限
  • \c <db_name> <name>：以身份name访问数据库db_name
  • \l[ist]：查看数据库
  • \dt：展示当前数据库中表

变量

  • \set foo bar：设置变量
    • 可以像php设置“变量 变量”：\set :foo bar
  • \unset foo：重置变量

数据库变量

内部变量

特殊变量

特殊变量：一些选项设置，在运行时可通过改变变量的值、应用的 表现状态改变其，不推荐改变这些变量的用途

  • AUTOCOMMIT：缺省为on，每个SQL命令完成后自行提交，此时 需要输出BEGIN、START TRANSACTION命令推迟提交
  • DBNAMW：当前所连接数据库
  • ENCODING：客户端字符集编码
  • 详情查询手册

环境变量

  • PGDATA：指定数据库簇（存放数据）目录

    1
    $export PGDATA=/var/lib/pgsql/data
    • 默认/var/lib/pgsql/data
    • -D命令行参数指定
Posted Updated Database / Spark15 minutes read (About 2177 words)

SparkSQL2.4中启用CBO时JoinReorder分析

背景

Spark Join方式

SparkSQL目前支持三种join方式

  • broadcast hash join：将小表广播分发到大表所在的结点上 ，并行在各节点上进行hash join

    • 仅适合内表非常小的场合

  • shuffle hash join：按照join key分区，每个结点独立并行 进行hash join

    • 类似分布式GHJ，不同块位于不同结点

  • sort merge join：按照join key分区，在各节点独立并行SMJ

    • spark当前shuffle算法使用sort-based shuffle算法
    • 理论上shuffle过后各分区数据已经排序完毕，无需再次 sort，效率很高

Join类型

SparkSQL支持的Join类型可以分为以下两类

  • 顺序结果无关Join

    • inner join
    • (full)outer join

  • 顺序结果相关Join

    • left(outer) join
    • right(outer) join
    • left semi join
    • right semi join

考虑到JoinReorder的结果

  • 仅支持连接重排序的连接类型只可能是inner join outer join

  • 而outer join重排序虽然不影响结果，但是处理不方便，所以 联接重排序一般仅限于inner join？？？

    • 有些情况下RBO可以将外联接等价转换为内联接
    • SparkSQL2.4中支持的连接重排序仅限于内连接

Cost-Based Opitimization/Optimizer

CBO：基于成本的优化（器）

  • 根据SQL的执行成本制定、优化查询作业执行计划，生成可能 的执行计划中代价最小的计划

    • 数据表统计数据
      • 基/势
      • 唯一值数量
      • 空值数量
      • 平均、最大长度
    • SQL执行路径I/O
    • 网络资源
    • CPU使用情况

  • 在SparkSQL Hash Join中可以用于

    • 选择正确hash建表方
    • 选择正确join类型：广播hash、全洗牌hash
    • join reorder：调整多路join顺序

  • CBO本身需要耗费一定资源，需要平衡CBO和查询计划优化程度

    • 数据表的数据统计资源耗费
    • 优化查询计划即时资源耗费
  • CBO是相较于Rule-Based Optimization的概念

CBO中的独特概念

  • cardinality：集的势，结果集的行数

    • 表示SQL执行成本值
    • SQL执行返回的结果集包含的行数越多，成本越大

  • selectivity：可选择率，施加指定谓语条件后返回结果集的 记录数占未施加任何谓语条件的原始结果记录数的比率

    • 值越小，说明可选择性越好
    • 值越大，说明可选择性越差，成本值越大

Join Reorder

Join Reorder：基于CBO的多表连接顺序重排

  • 用统计信息预估的基修正join顺序

  • 主要涉及到以下两个方面

    • 查询代价估算
    • 多表连接顺序搜索算法

查询代价估计

代价模型

  • 单个join操作成本

    • carinality：对应CPU成本
    • size：对应IO成本

  • join树的成本是所有中间join成本总和

Filter Selectivity估计

过滤选择率：估计应用谓词表达式过滤的选择率

逻辑运算符

  • AND：左侧过滤条件选择率、右侧过滤条件选择率之积

  • OR：左侧、右侧过滤条件选择率之和，减去其乘积

  • NOT：1减去原始过滤条件选择率

比较运算符

  • =：等于条件

    • 若常数取值在当前列取值范围之外，则过滤选择率为0
    • 否则根据柱状图、均匀分布得到过滤选择率

  • <：小于条件

    • 若常数取值小于当前列最小值，则过滤选择率为0
    • 否则根据柱状图、均匀分数得到过滤选择率

Join Carinality估计

联接基：估计联接操作结果的基

  • inner：其他基估计值可由inner join计算

    • num(A)：join操作前表A的有效记录数
    • distinct(A.k)：表A中列k唯一值数量

  • left-outer：取inner join、左表中基较大者

  • right-outer：取inner join、右表中基较大者

  • full-outer

多表连接顺序搜索算法

SparkSQL2.4中使用动态规划算法对可能联接顺序进行搜索，从中 选择最优的联接顺序作为执行计划

  • 最优子结构：一旦前k个表联接顺序确定，则联接前中间表和 第k+1个表方案和前k个表的联接顺序无关

  • 动态规划表：从单表代价开始，逐层向上计算各层多表联接代价 ，直到求得所有表联接最小代价

  • 减少搜索空间启发式想法：尽可能优先有谓词限制的内连接、 中间表

评价

  • 优势：动态规划算法能够求得整个搜索空间中最优解
  • 缺陷：当联接表数量增加时，算法需要搜索的空间增加的非常快 ，计算最优联接顺序代价很高

PostgreSQL

代价模型

Postgres的查询代价估计模型基于CPU开销、IO开销，另外还增加 了启动代价

动态规划算法

类似SparkSQL2.4多表连接算法（假设联接n个表）

  1. 构造第一层关系：每个关系的最优路径就是关系的最优单表扫描 方式

  2. 迭代依次构造之后n-1层关系联接最优解

    • 左深联接树方式：将第k-1层每个关系同第1层关系联接
    • 紧密树联接方式：将第m(m > 2)层每个关系同第k-m层关系 联接

    left_deep_tree_bushy_tree

遗传算法

遗传算法：模拟自然界生物进化过程，采用人工进化的方式对目标 空间进行搜索

  • 本质是高效、并行、全局搜索方法
  • 能在搜索过程中自动获取、积累有关搜索空间的知识，并自适应 的控制搜索过程以求的最佳解

思想

  • 将问题域中可能解看作是染色体，将其编码为符号串的形式
  • 对染色体群体反复进行基于遗传学的操作：选择、交叉、变异
  • 根据预定目标适应度函数对每个个体进行评价，不断得到更优 群体，从中全局并行搜索得到优化群体中最优个体

MySQL

代价模型

  • 因为多表联接顺序采用贪心算法，多个表已经按照一定规则排序 （可访问元组数量升序排序）
  • 所以MySQL认为，找到每个表的最小花费就是最终联接最小代价

贪心算法

贪心算法：认为每次连接表的连接方式都是最优的，即从未联接表中 选择使得下次联接代价最小者

  • 多表排序一般为

    • 常量表最前
    • 其他表按可访问元组数量升序排序

  • 贪心算法得到的联接方式都是最优的

    • 则每次联接主要求解要联接表对象的最佳访问方式
    • 即每次代价估计的重点在于单表扫描的代价

  • 求解结束后，局部最优查询计划生成

    • 得到左深树
    • 最初始表位于最左下端叶子节点处

优化方案

以下分别从查询代价估计、多表连接顺序搜索算法给出方案

查询代价估计

  • 考虑在现有代价模型上增加网络通信开销

  • 在现有直方图估计选择率基础上，增加选择率估计方法

    • Parametric Method：参数方法，使用预先估计分布函数 逼近真实分布

    • Curve Fitting：曲线拟合法，使用多项式函数、最小 标准差逼近属性值分布

多表连接顺序搜索算法

考虑到动态规划算法随着联接表数量增加时，计算代价过于庞大， 可以考虑引入其他算法优化多表连接顺序

  • 遗传算法
  • 退火算法
  • 贪心算法
  • 遗传算法
  • 退火算法
  • 贪心算法
Posted Updated Database12 minutes read (About 1758 words)

DBMS 查询优化

查询优化技术

查询优化技术：求解给定查询语句的高效执行计划过程

  • 目标：在数据库查询优化引擎生成执行策略的过程中，尽量减小 查询总开销

  • SQL层面上的局部优化，区别于数据库调优的全局优化

  • 广义数据库查询优化

    • 查询重用技术
    • 查询重写规则
    • 查询算法优化技术
    • 并行查询优化技术
    • 分布式查询优化技术

  • 狭义数据库查询优化

    • 查询重写规则：代数/逻辑优化，RBO
    • 查询算法优化技术：非代数/物理优化，CBO

代数/逻辑优化

代数/逻辑优化：依据关系代数的等价变换做逻辑变换

  • 语法级：查询语句层、基于语法进行优化
  • 代数级：使用形式逻辑、关系代数原理进行优化
  • 语义级：根据完整性约束，对查询语句进行语义理解，推知可 优化操作

非代数/物理优化

非代数/物理优化：根据数据读取、表连接方式、排序等技术对查询 进行优化

  • 物理级：物理优化技术，基于代价估计模型，比较得出各执行 方式中代价最小者
    • 查询算法优化：运用基于代价估算的多表连接算法求解最小 花费计算

查询重用技术

查询重用：尽可能利用先前执行的结果，以节约全过程时间、减少 资源消耗

  • 查询结果的重用：分配缓冲块存放SQL语句、最后结果集
  • 查询计划的重用：缓存查询语句执行计划、相应语法树结构
  • 优势：节约CPU、IO消耗
  • 弊端
    • 结果集很大回消耗放大内存资源
    • 同样SQL不同用户获取的结果集可能不完全相同

查询重写规则

查询重写：查询语句的等价转换

  • 基于关系代数，关系代数的等价变换规则为查询重写提供了理论 支持
  • 查询重写后，查询优化器可能生成多个连接路径，可以从候选者 中择优

目标

  • 将查询转换为等价、效率更高的形式
    • 低效率谓词转换为高效率谓词
    • 消除重复条件
  • 将查询重写为等价、简单、不受表顺序限制的形式，为 物理查询阶段提供更多选择

优化方向

  • 过程性查询转换为描述性查询：视图重写
  • 复杂查询尽可能转换为多表连接查询：嵌套子查询、外连接、 嵌套连接等
  • 低效率谓词转换为高效率谓词：等价谓词重写
  • 利用（不）等式性质简化where、having、on条件

查询算法优化技术

todo

Rule-Based Optimizer

RBO：基于规则的优化器

  • 对AST/LP进行遍历，模式匹配能够满足特定规则的结点，进行 等价转换，得到等价的另一棵树

    • 剪枝：删除一些无用计算
    • 合并：合并多个计算步骤

  • 经验式、启发式的固定transformation，手动设置（硬编码） 在数据库中规则决定SQL执行计划

经典优化规则

  • predicate pushdown：谓词下推

    sql_optimization_predicate_pushdown

  • constant folding：常量累加

    sql_optimization_constant_folding

  • column pruning：列值裁剪

    sql_optimization_column_pruning

  • combine limits：Limits合并

  • inner join只访问单表：降为semi join

特点

  • 操作简单、能快速确定连接方式

  • 规则虽然有效但不敏感

    • 数据分布发生变化时，RBO是不感知的

  • 基于RBO生成的执行计划不能确保是最优的

    • 启发式规则只能排除一些明显不好的存取路径

Cost-Base Optimizer

CBO：基于成本的优化器

  • 根据SQL的执行成本制定、优化查询作业执行计划，生成可能 的执行计划中代价最小的计划

    • 数据表统计数据
      • 基/势
      • 唯一值数量
      • 空值数量
      • 平均、最大长度
    • SQL执行路径I/O
    • 网络资源
    • CPU使用情况

  • 以上执行信息获取方式取决于不同平台、数据库

    • 执行SQL前抽样分析数据
    • 每次执行SQL都会记录统计信息

  • 特殊概念

    • cardinality：集的势，结果集的行数

      • 表示SQL执行成本值
      • SQL执行返回的结果集包含的行数越多，成本越大

    • selectivity：可选择率，施加指定谓语条件后返回 结果集的记录数占未施加任何谓语条件的原始结果集记录数 的比率

      • 值越小，说明可选择性越好
      • 值越大，说明可选择性越差，成本值越大

常见优化规则

  • hash-join
    • 选择正确hash建表方
    • 选择正确join类型：广播hash、全洗牌hash
    • join reorder：调整多路join顺序
      • 尽量减小中间shuffle数据集大小，达到最优输出

特点

  • 对各种可能情况进行量化比较，可以得到花费最小的情况
  • CBO本身需要耗费一定资源，需要平衡CBO和查询计划优化程度
    • 数据表的数据统计资源耗费
    • 优化查询计划即时资源耗费，如果组合情况比较多则花费 判断时间较多

并行查询优化技术

并行数据库系统中查询优化的目标：寻找具有最小响应时间的查询 执行计划

  • 具有最小执行代价的计划不一定具有最快相应时间，需要考虑 把查询工作分解为可以并行运行的子工作

  • 查询能否并行取决于

    • 系统中可用资源
    • CPU数目
    • 运算中特定代数运算符

  • 查询并行可以分为

    • 操作内并行：将同一操作如单表扫描、两表连接、排序操作 等分解为多个独立子操作

    • 操作间并行：一条SQL查询语句分解为多个子操作

分布式查询优化技术

分布式数据库系统：查询策略优化、局部处理优化是查询优化重点

  • 查询策略优化：主要是数据传输策略优化

    • 主要考虑因素：数据的通信开销
    • 主要目标：以减少传输次数、数据量

  • 局部处理优化：传统单结点数据库的查询优化技术

  • 代价估计模型：总代价 = IO代价 + CPU代价 + 通信代价

Posted Updated Database3 minutes read (About 432 words)

Database Parser

Parser综述

Parser：分析器，将SQL语句切分为token，根据一定语义规则解析 成AST

todo

查询计划/树

sql_parser_ast

查询计划：由一系列内部操作符组成，操作符按照一定运算关系构成 查询的一个执行方案

  • 形式上：二叉树

    • 树叶是每个单表对象
    • 两个树叶的父节点是连接操作符连接后的中间结果
    • 每个结点即临时“关系”

  • 查询的基本操作：选择、投影、连接

    • 选择、投影的优化规则适用于select-projection-join 操作和非SPY（SPY+Groupby）操作
    • 连接操作包括两表连接、多表连接

结点类型

  • 单表结点：从物理存储到内存解析称逻辑字段的过程

    • 考虑数据获取方式
      • 直接IO获取
      • 索引获取
      • 通过索引定位数据位置后再经过IO获取相应数据块

  • 两表结点：内存中元组进行连接的过程

    • 完成用户语义的局部逻辑操作，完成用户全部语义需要配合 多表连接顺序的操作
    • 不同连接算法导致连接效率不同
    • 考虑两表
      • 连接方式
      • 代价
      • 连接路径

  • 多表中间结点：多个表按照“最优”顺序连接过程

    • 考虑代价最小的“执行计划”的多表连接顺序

Schema Catalog

元数据信息：表的模式信息

  • 表的基本定义：表名、列名、数据类型
  • 表的数据格式：json、text、parquet、压缩格式
  • 表的物理位置
Posted Updated Database / Hadoop12 minutes read (About 1790 words)

HBase

HBase简介

HBase是高可靠、高性能、面向列、可伸缩的分布式数据库系统

  • 利用HBase技术可以在廉价硬件上搭建大规模非结构化数据管理 集群

  • HBase借鉴Google Bigtable技术实现的开源软件

    ||HBase|Bigtable| |——-|——-|——-| |存储系统|HDFS|GFS| |数据处理|Hadoop MapReduce|MapReduce| |协同服务|Zookeeper|Chubby| |RDBMS数据导入|Sqoop|-|

  • HBase访问接口

    • Native Java API：常用、高效的访问方式
    • HBase Shell：HBase命令行工具，适合用于管理HBase
    • Thrift Gateway：利用Thrift序列化技术，支持C++、PHP、 Python多种语言异构系统访问HBase表数据
    • REST Gateway：支持REST风格的Http API访问HBase
    • Pig：支持Pig Latin语言操作HBase中数据
      • 最终被转换为MapReduce Job处理HBase表数据
      • 适合做数据统计
    • Hive：支持用户使用HiveQL访问HBase

  • 可以在HBase系统上运行MapReduce作业，实现数据批处理 hbase_mapreduce

HBase数据结构

hbase_storage_structure

Table

HBase的表格，类似关系型数据库中的表格，但有所不同

特殊Table

HBase中有两张特殊的Table

  • .META.：记录用户表Region信息，自身可以有多个region
  • -ROOT-：记录.META.表Region信息的，自身只能有一个 region

Row Key

行键，Table行主键，Table记录按照此排序

Column、Column Family

  • Table在水平方向由一个或多个列簇组成
  • 一个列簇可以由任意多个Column组成
  • 列簇支持动态扩展，无需预先定义列数量、类型
  • 所有列均义二进制格式存储，用户需要自行进行类型转换

Timestamp

时间戳：每次数据操作对应的时间戳，可视为是数据的版本号

Region

Table记录数不断增加而变大后，逐渐分裂出的多个split

  • 每个region由[startkey, endkey)表示
  • 不同region被Master分配给相应RegionServer进行管理（存储）

HBase系统架构

hbase_structure

Client

  • HBase Client使用HBase RPC机制同HMaster、HRegionServer 进行通信
    • 对于管理类操作，通过RPC机制访问HMaster
    • 对于读写操作，通过RPC机制访问HRegionServer

Zookeeper

  • Zookeeper Quorum中记录-ROOT表的位置

    • 客户端访问数据之前首先访问zookeeper
    • 然访问-ROOT-表
    • 然后访问.META.表
    • 最后根据用户数据位置，访问具体数据

  • Zookeeper Quorum中存储有HMaster地址

  • HRegionServer把自己义Ephemeral方式注册到Zookeeper中， 使得HMaster可以随时感知各个HRegionServer健康状态

  • 引入Zookeeper，避免了HMaster单点失败问题

    • HBase中可以启动多个HMaster
    • 通过Zookeeper的Master Election机制保证总有一个Master 运行

HMaster

HMaster在功能上主要负责Table、Region管理工作

  • 管理用户对Table增、删、查、找操作？？？
  • 管理HRegionServer负载均衡，调整Region分布
  • 在Region分裂后，负责新Region分配
  • 在HRegionServer停机后，负责失效HRegionServer上region迁移

HRegionServer

HRegionServer负责响应用户I/O请求，向HDFS文件系统写数据，是 HBase中最核心的模块

hbase_hregion_server_structure

HRegion

HRegionServer内部管理一系列HRegion对象

  • HRegion对象对应Table中一个Region
  • HRegion由多个HStore组成

HStore

每个HStore对应Table中一个列簇的存储，是HBase存储核心模块

  • 由此可以看出列簇就是一个集中存储单元

    • 因此最好将具备共同IO特性的列放在同一个列簇中，可以 提高IO效率

  • HStore由两部分构成

    • MemStore
    • StoreFile：底层实现是HFile，是对HFile的轻量级包装
MemStore

Sorted memory buffer，用户写入数据首先放入MemStore中，满了 后Flush成一个StoreFile

StoreFile

  • 文件数量增长到一定阈值时会触发Compact合并操作，将多个 StoreFile合并成一个StoreFile

    • 合并过程中会进行版本合并、数据删除
    • 即HBase其实只有增加数据，所有更新、删除操作都是后续 Compact过程中进行的
    • 这使得用户写操作只要进入内存就可以立即返回，保证 HBase IO高性能

  • Compact操作会逐步形成越来越大的StoreFile，超过阈值之后 会触发Split操作

    • 当前Region分裂成2个Region
    • 父Region下线
    • 新分裂出的2个子Region会被HMaster分配到相应的 HRegionServer上，实现负载均衡

HLog

每个HRegionServer中都有一个HLog对象，避免因为分布式系统 中节点宕机导致的MemStore中内存数据丢失

  • HLog是实现WriteAheadLog的类

  • HLog作用

    • 每次用户写入MemStore时，也会写入一份数据至HLog文件中
    • HLog定时删除已持久化到StoreFile中的数据

  • HRegion意外终止后，HMaster会通过zookeeper感知到

    • HMaster首先处理遗留的HLog文件，将其中不同Region的Log 数据进行拆分，分别放到相应Region目录下
    • 然后将失效Region重新分配
    • 领取到Region的HRegionServer在Load Region过程中，会 发现有历史HLog需要处理，会Replay HLog中的数据到 MemStore中，然后flush到StoreFile中，完成数据恢复

HBase存储

HBase中所有数据存储在HDFS中

HFile

HFile是Hadoop二进制格式文件，实现HBase中Key-Value数据存储

  • HFile是不定长的，长度固定的只有：Trailer、FileInfo

hbase_hfile_storage_formation

Trailer

含有指针指向其他数据块起点

FileInfo

记录文件的一些元信息，如

  • AVG_KEY_LEN
  • AVG_VALUE_LEN
  • LAST_KEY
  • COMPARATOR
  • MAX_SEQ_ID_KEY

Data Index

记录每个Data块起始点

Meta Index

记录每个Meta块起始点

Data Block

Data Block是HBase IO基本单元

  • 为了提高效率，HRegionServer中实现了基于LRU的Block Cache 机制

  • Data块大小可以在创建Table时通过参数指定

    • 较大的块有利于顺序Scan
    • 较小的块有利于随机查询

  • Data块除了开头的Magic信息外，就是一个个<key, value> 键值对拼接而成

  • Magic内容就是一些随机数字，防止数据损坏

  • 每个键值对就是简单的byte array，但是包含很多项，且有固定 结构 hbase_hfile_datablock_kv

    • 开头是两个固定长度的数值，分别表示key、value长度
    • 然后是key部分
      • 固定长度数值表示RowKey长度
      • RowKey
      • 固定长度数值表示Column Family的长度
      • Column Family
      • Qualifier
      • 固定长度数值表示：Timestamp、KeyType（Put/Delete）
    • Value部分就是二进制数据

HLogFile

HBase中Write Ahead Log存储格式，本质上是Hadoop Sequence File

  • Sequence File的Key是HLogKey对象，记录了写入数据的归属信息

    • table
    • region
    • squecence number：起始值为0，或最近一次存入文件系统 中的squence number
    • timestamp：写入时间

  • Squence File的Value是KeyValue对象，即对应HFile中KeyValue

e

Posted Updated Database / Hadoop15 minutes read (About 2247 words)

Hadoop概述

  • Hadoop（核心）：HDFS和MapReduce/YARN
  • Hadoop家族：建立在Hadoop基础上的一系列开源工具

hadoop_relations

Hadoop

Hadoop时Apache的一个分布式计算、java语言实现的开源框架， 实现在大量计算机组成的集群中对海量数据进行分布式计算。相比于 依赖硬件的可靠性，Hadoop被设计为可以检测、处理应用层面的 failures，能够提供构建于电脑集群上的可靠服务。

Hadoop：Apache的分布式计算开源框架，提供分布式文件系统 HDFS、MapReduce/YARN分布式计算的软件架构

Hadoop Common

支持其它Hadoop模块的公用组件

Hadoop Distributed File System(HDFS)

虚拟文件系统，让整个系统表面上看起来是一个空间，实际上是很多 服务器的磁盘构成的

Hadoop YARN

Yet Another Resource Negotiator，通用任务、集群资源分配框架 ，面向Hadoop的编程模型

  • YARN将classic/MapReduce1中Jobtracker职能划分为多个独立 实体，改善了其面临的扩展瓶颈问题

  • YARN比MapReduce更具一般性，MapReduce只是YARN应用的一种 形式，可以运行Spark、Storm等其他通用计算框架

  • YARN精妙的设计可以让不同的YARN应用在同一个集群上共存， 如一个MapReduce应用可以同时作为MPI应用运行，提高可管理性 和集群利用率

Hadoop MapReduce

YARN基础上的大数据集并行处理系统（框架）

  • 包括两个阶段

    • Map：映射
    • Reduce：归一

  • 在分布式系统上进行计算操作基本都是由Map、Reduce概念步骤 组成

    • 分布式系统，不像一般的数据库、文件系统，无法从上至下 、从头到尾进行求和等操作
    • 需要由分散的节点不断向一个点聚拢的计算过程

  • 不适合实时性要求的应用，只适合大数据离线处理

Apache下Hadoop相关项目

高频

Ambari

用于部署（供应）、管理、监控Hadoop集群的Web工具

  • 支持HDFS、MapReduce、Hive、HCatalog、HBase、 Oozie、ZooKeeper、Pig、Sqoop

  • 提供dashboard用于查看集群健康程度，如：热度图

  • 能够直观的查看MapReduce、Pig、Hive应用特点，提供 易用的方式考察其执行情况

HBase

Hadoop项目子项目，高可靠、高性能、面向列、可伸缩的分布式 存储系统

  • 该技术源于Fay Chang撰写的Google论文《Bigtable：一个 结构化数据的分布式存储系统》，类似于Bigtable在Google 文件系统上提供的分布式数据存储一样，HBase在Hadoop的 基础上提供了类似于Bigtable的能力

  • 适合非结构化数据存储

  • 可用于在廉价PC Server上搭建大规模结构化存储集群，是 NoSQL数据库的两个首选项目（MongoDB）

Hive

基于Hadoop的数据仓库工具

  • 在Hive中建立表，将表映射为结构化数据文件

  • 可以通过类SQL语句直接查询数据实现简单的MapReduce统计， 而不必开发专门的MapReduce应用

    • Hive会将SQL语句转换为MapReduce任务查询Hadoop
    • 速度很慢
    • 适合数据仓库的统计分析
    • 支持SQL语法有限

Pig

基于Hadoop的大规模数据高层分析工具（类似于Hive）

  • 提供SQL-Like语言PigLatin

    • 其编译器会把类SQL的数据分析请求，转换为一系列经过 优化处理的MapReduce运算

    • 是一种过程语言，和Hive中的类SQL语句相比，更适合写 脚本，而Hive的类SQL语句适合直接在命令行执行

Zookeeper

Hadoop正式子项目，针对大型分布式应用设计的分布式、开源协调 系统

  • 提供功能：配置维护、名字服务、分布式同步、组服务

  • 封装好复杂、易出错的关键服务，提供简单易用、功能稳定、 性能高效的接口（系统），解决分布式应用中经常遇到的数据 管理问题，简化分布式应用协调及管理难度，提供高性能分布式 服务

  • 通常为HBase提供节点间的协调，部署HDFS的HA模式时是 必须的

Spark

基于内存计算的开源集群计算系统，目的是让数据分析更加快速

低频

Mahout

基于Hadoop的机器学习、数据挖掘的分布式框架

  • 使用MapReduce实现了部分数据挖掘算法，解决了并行挖掘问题

    • 包括聚类、分类、推荐过滤、频繁子项挖掘

  • 通过使用Hadoop库，Mahout可以有效扩展至云端

Cassandra

开源分布式NoSQL数据库系统，最初由Facebook开发，用于存储 简单格式数据，集Google BigTable数据模型和Amazon Dynamo 的完全分布式架构于一身

Avro

数据序列化系统，设计用于支持数据密集型、大批量数据交换应用， 是新的数据序列化格式、传输工具，将逐步取代Hadoop原有的 IPC机制

Chukwa

用于监控大型分布式系统的开源数据收集系统，可以将各种类型的 数据收集成适合Hadoop处理的文件，保存在HDFS中供MapReduce 操作

Tez

基于YARN的泛用数据流编程平台

  • 提供强力、灵活的引擎用于执行任何DAG任务，为批处理和 交互用例处理数据

Tez正逐渐被Hive、Pig等Hadoop生态框架采用，甚至被一些 商业公司用于替代MapReduce作为底层执行引擎

其他Hadoop相关项目

高频

Sqoop

用于将Hadoop和关系型数据库中数据相互转移的开源工具

  • 可以将关系型数据库（MySQL、Oracle、Postgres）中 数据转移至Hadoop的HDFS中

  • 也可以将HDFS的数据转移进关系型数据库中

Impala

由Cloudera发布的实时查询开源项目

  • 模仿Google Dremel

  • 称比基于MapReduce的Hive SQL查询速度提升3~30倍，更加 灵活易用

Phoenix

apache顶级项目，在HBase上构建了一层关系型数据库，可以用 SQL查询HBase数据库，且速度比Impala更快，还支持包括 二级索引在内的丰富特性，借鉴了很多关系型数据库优化查询方法

Oozie

工作流引擎服务器，用于管理、协调运行在Hadoop平台 （HDFS、Pig、MapReduce）的任务

Cloudera Hue

基于Web的监控、管理系统，实现对HDFS、MapReduce/YARN、 HBase、Hive、Pig的Web化操作和管理

低频

Hama

基于HDFS的BSP(Bulk Synchronous Parallel)并行 计算框架，可以用包括图、矩阵、网络算法在内的大规模、 大数据计算

Flume

分布的、可靠的、高可用的海量日志聚合系统，可用于日志数据 收集、处理、传输

Giraph

基于Hadoop的可伸缩的分布式迭代图处理系统，灵感来自于BSP和 Google Pregel

Crunch

基于Google FlumeJava库编写的Java库，用于创建MapReduce 流水线（程序）

  • 类似于Hive、Pig，提供了用于实现如连接数据、执行聚合 、排序记录等常见任务的模式库

    • 但是Crunch不强制所有输入遵循同一数据类型

    • 其使用一种定制的类型系统，非常灵活，能直接处理复杂 数据类型，如：时间序列、HDF5文件、HBase、序列化 对象（protocol buffer、Avro记录）

  • 尝试简化MapReduce的思考方式

    • MapReduce有很多优点，但是对很多问题，并不是合适的 抽象级别

    • 出于性能考虑，需要将逻辑上独立的操作（数据过滤、投影 、变换）组合为一个物理上的MapReduce操作

Whirr

运行于云服务的类库（包括Hadoop），提供高度互补性

  • 相对中立
  • 支持AmazonEC2和Rackspace的服务

Bigtop

对Hadoop及其周边生态打包、分发、测试的工具

HCatalog

基于Hadoop的数据表、存储管理，实现中央的元数据、模式管理， 跨越Hadoop和RDBMS，利用Pig、Hive提供关系视图

Llama

让外部服务器从YARN获取资源的框架

非CDH组件

Fuse

让HDFS系统看起来像普通文件系统

Hadoop Streamin

MapReduce代码其他语言支持，包括：C/C++、Perl、Python 、Bash等

Posted Updated Database / SQL DBa minute read (About 143 words)

MSSQL Puzzles

访问其他数据库服务器

SQL默认阻止对组件Ad Hoc Distributed Queries的STATEMENT OpenRowSet/OpenDatasource的访问，需要使用sp_configure 启用Ad Hoc Distributed Queries

  • 开启Ad Hoc Distributed Queries

    1
    2
    3
    4
    exec sp_configure 'show advanced options',1
    reconfigure
    exec sp_configure 'Ad Hoc Distributed Queries',1
    reconfigure

  • 关闭

    1
    2
    3
    4
    exec sp_configure 'Ad Hoc Distributed Queries',0
    reconfigure
    exec sp_configure 'show advanced options',0
    reconfigure

特殊语法

数据导入

  • mssql中换行符设置为\n表示的是\r\n，即永远无法单独 指定\n或者\r，尽量使用ASCII码0xXX表示

    1
    > bulk insert tbl_name from /path/to/file with (FILEDTERMINATOR="|", ROWTERMINATOR="0x0a");

Categories

Follow

Recents

Advertisement

follow.it

×