PostgreSQL中怎么实现递归查询

103次阅读

共计 5159 个字符，预计需要花费 13 分钟才能阅读完成。

本篇文章给大家分享的是有关 PostgreSQL 中怎么实现递归查询，丸趣 TV 小编觉得挺实用的，因此分享给大家学习，希望大家阅读完这篇文章后可以有所收获，话不多说，跟着丸趣 TV 小编一起来看看吧。

在内部，它是这样表示滴：

一个调查包括了许多问题（question）。一系列问题可以归到（可?。┮桓龇掷啵╟ategory）中。我们实际的数据结构会复杂一点（特别是子问题 sub-question 部分），但先当它就只有 question 跟 category 吧。

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

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

举个例子，比如对于上面这个调查：

Bar 的 order_number 比 Baz 的小。

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

# In category.rb
 
def sub_questions_in_order
 questions.order(order_number)
end

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

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

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

递归查询

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

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

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

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

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

(
 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 的调查)

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

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

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

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 是不行的。这里得搞个改造一下：

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 了。

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

不幸的是，顺序好像不对。

在递归查询内排序

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

这可怎么搞呢？

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

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

父分类的 path（如果有的话）+ 自己的 order_number

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

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;

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

这是由比较 ID 来查找子项引起的：

WHERE e.category_id = fle.id

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

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

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;

这看起来就 ok 了。搞定！

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

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

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

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

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

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

以上就是 PostgreSQL 中怎么实现递归查询，丸趣 TV 小编相信有部分知识点可能是我们日常工作会见到或用到的。希望你能通过这篇文章学到更多知识。更多详情敬请关注丸趣 TV 行业资讯频道。

正文完