在PostgreSQL中实现递归查询的教程_数据库其它

 介绍

在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?

这是由比较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

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

以上是小编为您精心准备的的内容,在的博客、问答、公众号、人物、课程等栏目也有的相关内容,欢迎继续使用右上角搜索按钮进行搜索postgresql
postgresql递归查询、postgresql 递归、postgresql with 递归、postgresql递归更新、postgresql恢复数据库,以便于您获取更多的相关知识。

时间: 2024-11-03 22:16:39

在PostgreSQL中实现递归查询的教程_数据库其它的相关文章

介绍PostgreSQL中的范围类型特性_数据库其它

 PostgreSQL 9.2 的一项新特性就是范围类型 range types,通过这个名字你可以轻松猜出该类型的用途,它可让你为某列数据定义数值范围. 这个简单的特性可以让我们不需要定义两个字段来描述数值的开始值和结束值,一个最直观的例子就是:   postgres# CREATE TABLE salary_grid (id int, position_name text, start_salary int, end_salary int); CREATE TABLE postgres# I

在Windows下自动备份PostgreSQL的教程_数据库其它

背景在我工作上一个使用PostgreSQL数据库的项目上需要一个自动化系统来每天执行备份.经过一番研究决定通过创建一个Windows批处理文件并添加到Windows计划任务中来实现. 下面是具体步骤: 怎样配置第一步: 下载批处理文件. 第二步: 你可以通过一个简单的命令(schtasks /?查看帮助)或者使用图形界面(开始-控制面板-系统和安全-管理工具-任务计划程序)运行任务计划管理工具,还可以在%SYSTEMROOT%\System32目录下双击Taskschd.msc来启动它.   第

在PostgreSQL上安装并使用扩展模块的教程_数据库其它

安装模块 注意: 我的运行环境是 Ubuntu 10.04 和 PostgreSQL 8.4 首先安装 postgresql-contrib 包并重启数据库服务器,然后检查 contrib 目录看是否包含一些可用模块:   sudo apt-get install postgresql-contrib sudo /etc/init.d/postgresql-8.4 restart cd /usr/share/postgresql/8.4/contrib/ ls 然后我们创建一个名为 module

设置CA证书来强化PostgreSQL的安全性的教程_数据库其它

在经历了多次的摸索实验后我终于成功地实现了SSL证书认证的功能,因此我想这次我要把这些步骤记录下来供日后查阅. 出于安全和方便的原因,我要在一台单独的专用机器上签署客户的证书,这台机器也称为 证书授证中心(CA). 这让我们在授权新的客户端时不必先登录到PostgreSQL服务器然后再签署证书或者修改pg_hba.conf. 我们要创建一个特殊的数据库组,叫sslcertusers.这个组里的所有用户都可以通过由CA签署的证书进行连接. 在下面的例子中,请将"trustly"替换成你的

php中安全模式safe_mode配置教程_服务器其它

(1) 打开php的安全模式 php的安全模式是个非常重要的内嵌的安全机制,能够控制一些php中的函数,比如system(), 同时把很多文件操作函数进行了权限控制,也不允许对某些关键文件的文件,比如/etc/passwd, 但是默认的php.ini是没有打开安全模式的,我们把它打开: safe_mode = on (2) 用户组安全 当safe_mode打开时,safe_mode_gid被关闭,那么php脚本能够对文件进行访问,而且相同 组的用户也能够对文件进行访问. 建议设置为: safe_

PostgreSQL数据库服务端监听设置及客户端连接方法教程_数据库其它

众所周知,PostgreSQL 是一个自由的对象-关系数据库服务器(数据库管理系统),是一个可以免费使用的开放源代码数据库系统.本文详细介绍了PostgreSQL数据库服务端监听设置及客户端连接方法,具体如下: 一.背景介绍: 本文所述PostgreSQL服务端运行在RedHat Linux上,IP为:192.168.230.128 客户端安装在Windows XP上, IP为:192.168.230.1 二.配置方法: 1.修改服务端/opt/postgresql/data/postgresq

Instagram提升PostgreSQL性能的五个技巧_数据库其它

 随着Instagram的规模日益扩大,Postgres继续充当着Instagram的坚实基础,并存储着绝大部分的用户数据.不到一年之前,我们还曾在博客上说Instagram"存储着大量数据",每秒增加90条数据,现在,这个数据已经增长到了峰值的10000条.而我们的基础存储技术依然保持不变. 在过去的两年半中,我们有一些关于Postgres扩展的经验和工具,想要分享出来.真希望在当初启动Instagram的时候就能有这些经验和工具呀.其中有些是Postgres独有的,有些是其它数据库

redis安装、配置、使用和redis php扩展安装教程_数据库其它

redis是一个内存数据库,比memcache支持更丰富的value类型,新浪微博就使用redis来做缓存. redis的源码安装 复制代码 代码如下: wget http://download.redis.io/redis-stable.tar.gztar -zxvf redis-stable.tar.gzcd redis-stablemakemake testmake install 1.make时可能会报如下错误: 复制代码 代码如下: zmalloc.o: In function `zm

hadoop map-reduce中的文件并发操作_数据库其它

这样的操作在map端或者reduce端均可.下面以一个实际业务场景中的例子来简要说明. 问题简要描述: 假如reduce输入的key是Text(String),value是BytesWritable(byte[]),不同key的种类为100万个,value的大小平均为30k左右,每个key大概对应 100个value,要求对每一个key建立两个文件,一个用来不断添加value中的二进制数据,一个用来记录各个value在文件中的位置索引.(大量的小文件会影响HDFS的性能,所以最好对这些小文件进行