pgrouting图关系插件在存储配置管理系统的应用__作者简介：帅宇，资深DBA，从事Oracle数据库管理和SQL开发超过15年，3年+PG数据库开发经验，擅长数据库建模设计，SQL开发，SQL性能调优。现就职于平安科技数据库技术部，云数据库架构师，负责平安云数据库产品配置管理系统设计和后台SQL开发。 1.RDS的图之尴尬图是一种应用广泛但比较复杂的数据结构。但传统的关系型数据库很难处理图的一些问题，例如求最短路径。让我们看一个简单的例子：: 世界上功能最强大的开源数据库...

### 作者简介
#### 帅宇，资深DBA，从事Oracle数据库管理和SQL开发超过15年，3年+PG数据库开发经验，擅长数据库建模设计，SQL开发，SQL性能调优。现就职于平安科技数据库技术部，云数据库架构师，负责平安云数据库产品配置管理系统设计和后台SQL开发。
### 1.RDS的图之尴尬

#### 图是一种应用广泛但比较复杂的数据结构。但传统的关系型数据库很难处理图的一些问题，例如求最短路径。让我们看一个简单的例子：

![CENTER_PostgreSQL_Community]( /images/news/2019/20190614_2059_图片1.png)

#### 这是一个简单的有向图，箭头表示方向。节点名是A,B,C... 括号里是节点的id号。
#### 如果用关系型表来表示这个数据结构，可以建两张表：
#### 节点表（顶点）：
```
create table t_node (
   id_node int4 not null
        ,node_name Character varying(20)
);
alter table t_node add constraint pk_node primary key (id_node);
```

#### 关联关系表（边）：
```
create table t_edge (
         id_edge int4 not null                                                                                         
        ,source_node_id int4
        ,target_node_id int4
        ,cost float8
        ,reverse_cost float8
);
alter table t_edge add constraint pk_edge primary key (id_edge);
```
#### 对于上例，插入数据后是这样的（这个例子中我们先不考虑边长，cost和reverse_cost 先为空）：
  
![CENTER_PostgreSQL_Community]( /images/news/2019/20190614_2120_图片2.png)

![CENTER_PostgreSQL_Community]( /images/news/2019/20190614_2122_图片3.png)

#### 我们来看现在的问题：
#### 1. 求出任意两个节点的最短路径。例如求F->D的最短路径，期望的答案输类似这样：
####  F  26
#### C  23
#### A  21
#### D  24
#### 注意，本例是有向图。如果是无向图，那么输出结果直接就是
#### F  26
#### D  24

#### 大家可以想想，如果基于上述两个表的表结构设计，用传统SQL该怎么写？反正我是没写出来的 。当然，可以在存储过程里嵌套实现，但书写复杂度和执行效率，比起单个SQL来说不可同日而语

### 2.强大的PG图插件：pgrouting
#### PostgreSQL 提供了一个强大的图处理插件 pgrouting（postgis的一部分），实现了在传统关系型数据库里处理图数据。使用之前，需要先安装 postgis，再安装 pgrouting ：
```
create extension postgis;
create extension pgrouting;
```
#### 有了pgrouting 插件，求最短路径的SQL就得非常简单，语句如下：
```
select * 
from pgr_dijkstra(
                'select id_edge as id 
                ,source_node_id as source 
                ,target_node_id as target 
                ,1 as cost 
                from t_edge'
         ,26
         ,24
         ,true
);
```
#### 结果如下：

![CENTER_PostgreSQL_Community]( /images/news/2019/20190614_2125_图片4.png)

#### pgr_dijkstra 的参数说明：
#### 1.构造一个标准的图关系数据的动态SQL
#### 2. 起点的id
#### 3. 终点的id
#### 4. 是否是有向图。true是有向，false是无向。
#### 5. 是否考虑逆向边长(权重)。（本例忽略这个参数）

#### 特别需要注意，第一个参数，是一个动态SQL，返回的结果集字段必须是下面的结构（注意列别名都必须要一样）
```
select id_edge as id 
,source_node_id as source 
,target_node_id as target 
,1 as cost 
from t_edge
```

#### 动态SQL结果集各个字段的含义如下（摘自官方文档）：
| Column | Type | Default |Description|
| :------|:------ | :------ |:------ |
| id | ANY-INTEGER |  |Identifier of the edge. 关系表的id|
| source | ANY-INTEGER | |Identifier of the first end point vertex of the edge. 起点的id|
| target| ANY-INTEGER |  |Identifier of the second end point vertex of the edge. 终点的id|
| cost|ANY-NUMERICAL | |Weight of the edge (source, target)When negative: edge (source, target) does not exist, therefore it’s not part of the graph.<br>边的权重，也就是从源到目标的长度|
| reverse_cost| ANY-NUMERICAL | -1 |Weight of the edge (target, source),When negative: edge (target, source) does not exist, therefore it’s not part of the graph.<br>逆向权重。也就是从目标到源的长度|
#### 注：最后一个逆向权重字段因为有默认值，所以构造SQL时可以省略不写。

#### 所以这个动态SQL的入参，给了程序很大的灵活性，不管业务场景如何不同，表设计如何变化，只要能够用一条SQL查询出图的所有边，就可以用pgr_dijkstra()函数算出最短路径。本例中我们没有考虑边长，所以cost 给了一个常量 1。

#### 请注意查询结果要匹配上面的字段类型，如有必要，需做显式做类型转换
```
select xxx::integer as id
,xxx::integer as source 
...
from xxx, sss
where .... 
```

#### 如果不考虑方向，把本例当做无向图，那么 F->D 的最短路径是：
```
select * 
from pgr_dijkstra(
                'select id_edge as id 
                ,source_node_id as source 
                ,target_node_id as target 
                ,1 as cost 
                from t_edge'
         ,26
         ,24
         ,false
);

```
![CENTER_PostgreSQL_Community]( /images/news/2019/20190614_2127_图片5.png)

#### 除了求最短路径，还有很多基于图的分析功能。例如，无向情况下求A 到 B,F,E的距离，并且找出最近的那个节点。
#### 使用 pgr_dijkstracost 方法，用array表示多个节点：
```
select * 
from pgr_dijkstracost(
                'select id_edge as id 
                ,source_node_id as source 
                ,target_node_id as target 
                ,1 as cost 
                from t_edge'
         ,21
         ,array[22,25,26]
         ,false
);

```
![CENTER_PostgreSQL_Community]( /images/news/2019/20190614_2129_图片6.png)

#### 然后只要再 order by agg_cost limit 1 就能找出最近的那个节点了。

#### 更多细节，可以参考官方文档：http://docs.pgrouting.org/
#### 可以选择您安装的对应版本，查看详情：

![CENTER_PostgreSQL_Community]( /images/news/2019/20190614_2131_图片15.png)

### 3.案例应用：SAN存储配置管理
#### 在SAN存储配置管理系统里，记录了SAN交换机相关信息。SAN交换机分布在不同机房，各交换机之间有连接关系。表结构如下图：

![CENTER_PostgreSQL_Community]( /images/news/2019/20190614_2132_图片7.png)

#### 重点看 ccm_san_switch（交换机表）和 ccm_san_switch_conn （连接关系表）这两个表。ccm_san_switch_conn 里的 from_id 记录了源交换机id，to_id记录了目标交换机id。
#### 在应用的时候，我们往往要找出两个交换机之间的最短路径，按照最短路径接线，可以达成SAN存储的最佳性能。

#### 下面的语句是直接查询交换机级联关系（显示字段为交换机id和交换机名）
```
select 
f.id_san_switch ,
f.switch_name ,
t.id_san_switch ,
t.switch_name 
from 
ccm_san_switch f , 
ccm_san_switch t ,
ccm_san_switch_conn c 
where 
c.from_id = f.id_san_switch and c.to_id = t.id_san_switch
```

![CENTER_PostgreSQL_Community]( /images/news/2019/20190614_2133_图片8.png)

#### 我们就以第一条记录，id=432299 的交换机CI_*SW532727_1279 为例，求从它连接到 id=544873 的 NU_*SWX6_8731 的最短路径是什么：
```
select * 
from pgr_dijkstra(
'select c.id_san_switch_conn as id 
,c.from_id as source 
,c.to_id as target 
,1 as cost  
from ccm_san_switch_conn c' 
,432299
,544873 
,true 
);
```
![CENTER_PostgreSQL_Community]( /images/news/2019/20190614_2134_图片9.png)

#### 从 node 字段可以看出，最短级联路径是 432299 -> 445454 -> 544873，agg_cost(总长度)是2，即习惯上说的跳了两跳。

#### 另外，还可以分析交换机最长级联路径，比如查询最长的前三条路径：
```
select *
from (
  select seq, path_seq ,start_vid ,end_vid ,node ,edge ,cost ,agg_cost
  from pgr_dijkstra(
    'select c.id_san_switch_conn as id 
    ,c.from_id as source 
    ,c.to_id as target 
    ,1 as cost  
    from ccm_san_switch_conn c' 
    ,array(select id_san_switch from ccm_san_switch ) 
    ,array(select id_san_switch from ccm_san_switch ) 
    ,true 
  )
) a
order by agg_cost desc 
limit 3
```
#### 请注意这是 many - many 的写法，source 和 target节点都是全部交换机，用 array(select id_san_switch from ccm_san_switch ) 来表示。结果如下：

![CENTER_PostgreSQL_Community]( /images/news/2019/20190614_2135_图片10.png)

#### 看明细，从 609243 到 544873 具体是怎么关联过去的，并且把交换机名查出来：

```
select a.path_seq, a.node ,s.switch_name ,a.agg_cost
from (
  select * 
  from pgr_dijkstra(
    'select c.id_san_switch_conn as id 
    ,c.from_id as source 
    ,c.to_id as target 
    ,1 as cost  
    from ccm_san_switch_conn c' 
    ,609243
    ,544873
    ,true 
  )
) a ,ccm_san_switch s
where s.id_san_switch = a.node
```
![CENTER_PostgreSQL_Community]( /images/news/2019/20190614_2136_图片11.png)

### 4.pgrouting在平安的应用
#### 目前pgrouting在平安的应用出于刚起步阶段。但我们可以看到，pgrouting是传统RDS数据库一个强大的功能扩展。在不迁移整个系统到图数据库(例如Neo4j)的情况下，提供了基本的图数据处理方法，特别适用于只有少量图数据处理需求的传统应用系统。相信未来还会有更多的场景使用pgrouting插件。

![CENTER_PostgreSQL_Community](/images/news/2016/pg_bot_banner.jpg)