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

数据库 2024/11/23 佚名

3 2 1

介绍

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

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

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

一个调查包括了许多问题（question）。一系列问题可以归到（可选）一个分类（category）中。我们实际的数据结构会复杂一点（特别是子问题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"htmlcode">

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

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

PostgreSQL

标签：

PostgreSQL

免责声明：本站文章均来自网站采集或用户投稿，网站不提供任何软件下载或自行开发的软件！如有用户或公司发现本站内容信息存在侵权行为，请邮件告知！ 858582#qq.com

评论“在PostgreSQL中实现递归查询的教程”

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

暂无“在PostgreSQL中实现递归查询的教程”评论...

www.imxmx.com 杰晶网络

8,675无损音乐

1,324高清电影

213破解软件

120,141站长资源

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

PostgreSQL

telnet连接操作memcache服务器详解

mysql、mssql及oracle分页查询方法详解

评论“在PostgreSQL中实现递归查询的教程”

RTX 5090要首发性能要翻倍！三星展示GDDR7显存

更新动态

友情链接

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

PostgreSQL

telnet连接操作memcache服务器详解

mysql、mssql及oracle分页查询方法详解

评论“在PostgreSQL中实现递归查询的教程”

RTX 5090要首发 性能要翻倍！三星展示GDDR7显存

更新动态

友情链接

RTX 5090要首发性能要翻倍！三星展示GDDR7显存