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

简介

在Nilenso中，兄弟正在开发（开源！）应用程序，用于设计和启动调查.

以下是调查示例:

在里面，它意味着像这样的液滴:

一项调查包含许多问题. 一系列问题可以分为（可选）类别. 我们的实际数据结构会稍微复杂一些（尤其是子问题部分），但首先，它仅包含问题和类别.

这是我们保存问题和类别的方式.

每个问题和类别都有一个order_number字段. 它是一个整数，用于指定其与其他兄弟的相对关系.

例如，对于上述调查:

Bar的order_number小于Baz的.

这种分类下的问题可以按正确的顺序出现:

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

这就是我们从一开始就获取整个调查的方式. 每个类别将按顺序获得所有子问题，依此类推，直到整个实体树都如此.

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

对于包含5个以上嵌入式问题和100多个问题的调查，这非常慢.

递归查询

兄弟还使用了像awesome_nested_set这样的宝石，但据我所知递归查询递归查询，它们都不支持跨多个模型进行提取.

后来，我不小心找到了一个文档，说PostgreSQL支持递归查询！好吧，这可以在那里.

然后尝试使用递归查询来解决此问题（目前，兄弟对它的理解仍然很清淡，如果没有放置，请不要喷洒. ）

要在Postgres中进行递归查询，必须首先定义一个初始化查询，这是非递归部分.

在此示例中，它是顶级问题和类别. 顶级元素没有父类别，因此它们的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;

等等，递归部分只能得到问题. 如项目的第一个子类别是类别怎么办？ Postgres多次引用非递归项. 因此，对问题和类别结果集执行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;

在与非递归部分结合之前，类别和问题结果集是UNION.

这将产生所有调查元素:

不幸的是，顺序似乎不正确.

在递归查询中排序

问题是，尽管对于第一级元素都有效地获得了所有第二级元素，但这会进行广度优先搜索. 实际上，它需要深度优先.

这怎么办？

Postgres可以在查询期间构建数组.

然后构建一个数组，该数组存储所获取元素的序列号. 调用此数组路径. 元素的路径为:

父类别的路径（如果有）+自己的订单号

如果使用路径对结果集进行排序，则可以将查询转换为深度优先！

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;

这非常接近成功. 但是有两首您最喜欢的歌曲是什么？

这是通过比较ID来查找子项目引起的:

WHERE e.category_id = fle.id

文件同时包含问题和类别. 但是所需的是仅匹配类别（因为该问题将不会有孩子）.

然后为每个此类查询硬编码一个类型，因此您不必尝试检查问题是否包含子项:

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;

这看起来还可以. 完成它！

让我们看一下表演.

使用以下脚本（在界面上创建调查后），兄弟生成了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倍以上？不错.

本文来自电脑杂谈，转载请注明本文网址：
https://www.pc-fly.com/a/jisuanjixue/article-174052-1.html