在PostgreSQL中实现递归查询的教程

时间:2022-06-01 20:30:17

 介绍

在nilenso,哥在搞一个 (开源的哦!)用来设计和发起调查的应用。

下面这个是一个调查的例子:

在PostgreSQL中实现递归查询的教程

在内部,它是这样表示滴: 

在PostgreSQL中实现递归查询的教程

 一个调查包括了许多问题(question)。一系列问题可以归到(可选)一个分类(category)中。我们实际的数据结构会复杂一点(特别是子问题sub-question部分),但先当它就只有question跟category吧。


我们是这样保存question跟category的。

每个question和category都有一个order_number字段。是个整型,用来指定它自己与其它兄弟的相对关系。

举个例子,比如对于上面这个调查: 

在PostgreSQL中实现递归查询的教程

 bar的order_number比baz的小。

这样一个分类下的问题就能按正确的顺序出现:
 

?
1
2
3
4
5
# in category.rb
 
def sub_questions_in_order
 questions.order('order_number')
end

实际上一开始我们就是这样fetch整个调查的。每个category会按顺序获取到全部其下的子问题,依此类推遍历整个实体树。

这就给出了整棵树的深度优先的顺序: 

在PostgreSQL中实现递归查询的教程

 对于有5层以上的内嵌、多于100个问题的调查,这样搞跑起来奇慢无比。

递归查询

哥也用过那些awesome_nested_set之类的gem,但据我所知,它们没一个是支持跨多model来fetch的。

后来哥无意中发现了一个文档说postgresql有对递归查询的支持!唔,这个可以有。

那就试下用递归查询搞搞这个问题吧(此时哥对它的了解还很水,有不到位,勿喷)。

要在postgres做递归查询,得先定义一个初始化查询,就是非递归部分。

本例里,就是最上层的question跟category。最上层的元素不会有父分类,所以它们的category_id是空的。
 

?
1
2
3
4
5
6
7
8
9
(
 select id, content, order_number, type, category_id from questions
 where questions.survey_id = 2 and questions.category_id is null
)
union
(
 select id, content, order_number, type, category_id from categories
 where categories.survey_id = 2 and categories.category_id is null
)

(这个查询和接下来的查询假定要获取的是id为2的调查)

这就获取到了最上层的元素。

在PostgreSQL中实现递归查询的教程

下面要写递归的部分了。根据下面这个postgres文档: 

在PostgreSQL中实现递归查询的教程

 递归部分就是要获取到前面初始化部分拿到的元素的全部子项。
 

?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
with recursive first_level_elements as (
 -- non-recursive term
 (
  (
   select id, content, order_number, category_id from questions
   where questions.survey_id = 2 and questions.category_id is null
  union
   select id, content, order_number, category_id from categories
   where categories.survey_id = 2 and categories.category_id is null
  )
 )
 union
 -- recursive term
 select q.id, q.content, q.order_number, q.category_id
 from first_level_elements fle, questions q
 where q.survey_id = 2 and q.category_id = fle.id
)
select * from first_level_elements;

等等,递归部分只能获取question。如果一个子项的第一个子分类是个分类呢?postgres不给引用非递归项超过一次。所以在question跟category结果集上做union是不行的。这里得搞个改造一下:

 

?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
with recursive first_level_elements as (
 (
  (
   select id, content, order_number, category_id from questions
   where questions.survey_id = 2 and questions.category_id is null
  union
   select id, content, order_number, category_id from categories
   where categories.survey_id = 2 and categories.category_id is null
  )
 )
 union
 (
   select e.id, e.content, e.order_number, e.category_id
   from
   (
    -- fetch questions and categories
    select id, content, order_number, category_id from questions where survey_id = 2
    union
    select id, content, order_number, category_id from categories where survey_id = 2
   ) e, first_level_elements fle
   where e.category_id = fle.id
 )
)
select * from first_level_elements;

在与非递归部分join之前就将category和question结果集union了。

这就产生了所有的调查元素: 

在PostgreSQL中实现递归查询的教程

 不幸的是,顺序好像不对。
 
在递归查询内排序

这问题出在虽然有效的为一级元素获取到了全部二级元素,但这做的是广度优先的查找,实际上需要的是深度优先。

这可怎么搞呢?

postgres有能在查询时建array的功能。

那就就建一个存放fetch到的元素的序号的array吧。将这array叫做path好了。一个元素的path就是:

    父分类的path(如果有的话)+自己的order_number

如果用path对结果集排序,就可以将查询变成深度优先的啦!
 

?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
with recursive first_level_elements as (
 (
  (
   select id, content, category_id, array[id] as path from questions
   where questions.survey_id = 2 and questions.category_id is null
  union
   select id, content, category_id, array[id] as path from categories
   where categories.survey_id = 2 and categories.category_id is null
  )
 )
 union
 (
   select e.id, e.content, e.category_id, (fle.path || e.id)
   from
   (
    select id, content, category_id, order_number from questions where survey_id = 2
    union
    select id, content, category_id, order_number from categories where survey_id = 2
   ) e, first_level_elements fle
   where e.category_id = fle.id
 )
)
select * from first_level_elements order by path;

在PostgreSQL中实现递归查询的教程

这很接近成功了。但有两个 what's your favourite song?

这是由比较id来查找子项引起的:
 

?
1
where e.category_id = fle.id

fle同时包含question和category。但需要的是只匹配category(因为question不会有子项)。

那就给每个这样的查询硬编码一个类型(type)吧,这样就不用试着检查question有没有子项了:

 

?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
with recursive first_level_elements as (
 (
  (
   select id, content, category_id, 'questions' as type, array[id] as path from questions
   where questions.survey_id = 2 and questions.category_id is null
  union
   select id, content, category_id, 'categories' as type, array[id] as path from categories
   where categories.survey_id = 2 and categories.category_id is null
  )
 )
 union
 (
   select e.id, e.content, e.category_id, e.type, (fle.path || e.id)
   from
   (
    select id, content, category_id, 'questions' as type, order_number from questions where survey_id = 2
    union
    select id, content, category_id, 'categories' as type, order_number from categories where survey_id = 2
   ) e, first_level_elements fle
   -- look for children only if the type is 'categories'
   where e.category_id = fle.id and fle.type = 'categories'
 )
)
select * from first_level_elements order by path;

在PostgreSQL中实现递归查询的教程

 这看起来就ok了。搞定!

下面就看看这样搞的性能如何。


用下面这个脚本(在界面上创建了一个调查之后),哥生成了10个子问题序列,每个都有6层那么深。
 

?
1
2
3
4
5
6
7
8
survey = survey.find(9)
10.times do
 category = factorygirl.create(:category, :survey => survey)
 6.times do
  category = factorygirl.create(:category, :category => category, :survey => survey)
 end
 factorygirl.create(:single_line_question, :category_id => category.id, :survey_id => survey.id)
end

每个问题序列看起来是这样滴: 

在PostgreSQL中实现递归查询的教程

 那就来看看递归查询有没有比一开始的那个快一点吧。
 

?
1
2
3
4
5
pry(main)> benchmark.ms { 5.times { survey.find(9).sub_questions_using_recursive_queries }}
=> 36.839999999999996
 
pry(main)> benchmark.ms { 5.times { survey.find(9).sub_questions_in_order } }
=> 1145.1309999999999

快了31倍以上?不错不错。