作者简介

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

1.RDS的图之尴尬

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

这是一个简单的有向图，箭头表示方向。节点名是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 先为空）：

我们来看现在的问题：

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
);

结果如下：

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结果集各个字段的含义如下（摘自官方文档）：

注：最后一个逆向权重字段因为有默认值，所以构造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
);

除了求最短路径，还有很多基于图的分析功能。例如，无向情况下求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
);

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

更多细节，可以参考官方文档：http://docs.pgrouting.org/

可以选择您安装的对应版本，查看详情：

3.案例应用：SAN存储配置管理

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

重点看 ccmsanswitch（交换机表）和 ccmsanswitchconn （连接关系表）这两个表。ccmsanswitchconn 里的 fromid 记录了源交换机id，toid记录了目标交换机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

我们就以第一条记录，id=432299 的交换机CISW5327271279 为例，求从它连接到 id=544873 的 NUSWX68731 的最短路径是什么：

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 
);

从 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 idsanswitch from ccmsanswitch ) 来表示。结果如下：

看明细，从 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

4.pgrouting在平安的应用

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