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

2014-02-10  来源:本站原创  分类:数据库其它  人气:12 

这篇文章主要介绍了在PostgreSQL中实现递归查询的教程,包括在递归查询内排序等方法的介绍,需要的朋友可以参考下

介绍

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

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

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

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

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

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

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

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

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

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

Bar的order_number比Baz的小。

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

# 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是空的。

(
 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中实现递归查询的教程

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

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

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

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

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

在递归查询内排序

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

这可怎么搞呢?

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;

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

这很接近成功了。但有两个 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;

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

这看起来就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

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

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

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

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中实现递归查询的教程 2014-02-10

    这篇文章主要介绍了在PostgreSQL中实现递归查询的教程,包括在递归查询内排序等方法的介绍,需要的朋友可以参考下 介绍 在Nilenso,哥在搞一个 (开源的哦!)用来设计和发起调查的应用. 下面这个是一个调查的例子: 在内部,它是这样表示滴: 一个调查包括了许多问题(question).一系列问题可以归到(可选)一个分类(category)中.我们实际的数据结构会复杂一点(特别是子问题sub-question部分),但先当它就只有question跟category吧. 我们是这样保存que

  • 在Ruby程序中连接数据库的详细教程 2014-03-11

    这篇文章主要介绍了在Ruby程序中连接数据库的详细教程,包括介绍数据库支持Ruby的接口等,是学习Ruby on Rails的基础,需要的朋友可以参考下 本章节将向您讲解如何使用 Ruby 访问数据库.Ruby DBI 模块为 Ruby 脚本提供了类似于 Perl DBI 模块的独立于数据库的接口. DBI 即 Database independent interface,代表了 Ruby 独立于数据库的接口.DBI 在 Ruby 代码与底层数据库之间提供了一个抽象层,允许您简单地实现数据库切换

  • 使用Ruby on Rails和PostgreSQL自动生成UUID的教程 2015-01-01

    这篇文章主要介绍了使用Ruby on Rails和PostgreSQL自动生成UUID的教程,主要利用到了PostgreSQL的插件uuid-ossp,需要的朋友可以参考下 Rails 4 能原生态的支持Postgres 中的UUID(Universally Unique Identifier,可通用的唯一标识符)类型.在此,我将向你描述如何在不用手工修改任何Rails代码的情况下,用它来生成UUID. 首先,你需要激活Postgres的扩展插件'uuid-ossp': class Create

  • Python中的Numpy入门教程 2013-10-31

    这篇文章主要介绍了Python中的Numpy入门教程,着重讲解了矩阵中的数组操作,需要的朋友可以参考下 1.Numpy是什么 很简单,Numpy是Python的一个科学计算的库,提供了矩阵运算的功能,其一般与Scipy.matplotlib一起使用.其实,list已经提供了类似于矩阵的表示形式,不过numpy为我们提供了更多的函数.如果接触过matlab.scilab,那么numpy很好入手. 在以下的代码示例中,总是先导入了numpy: >>> import numpy as np &

  • 在PostgreSQL中使用日期类型时一些需要注意的地方 2013-11-09

    这篇文章主要介绍了在PostgreSQL中使用日期类型时一些需要注意的地方,包括时间戳和日期转换等方面,需要的朋友可以参考下 当我们这些使用Rails的人看到例如5.weeks.from_nowor3.days.ago + 2.hours时并不会感到惊讶.同样,PostgreSQL也可以做到,你可以通过简单调用PostgreSQL内置函数来实现相同的功能. 当前时间/日期/时间戳 获取当前时间的方式有很多种,在这之前我们需要知道以下两种类型的区别: 总是返回当前的值 (clock_timesta

  • PostgreSQL中的OID和XID 说明 2013-12-14

    在PostgreSQL中经常碰到OID和XID,刚才不明白这些东西是干什么的. oid: 行的对象标识符(对象 ID).这个字段只有在创建表的时候使用了 WITH OIDS ,或者是设置了default_with_oids 配置参数时出现. 这个字段的类型是 oid (和字段同名). 例子: CREATE TABLE pg_language ( lanname name NOT NULL, lanowner oid NOT NULL, lanispl boolean NOT NULL, lanp

  • 在PostgreSQL中使用数组时值得注意的一些地方 2014-02-20

    这篇文章主要介绍了在PostgreSQL中使用数组时值得注意的一些地方,包括如何提高输入性能,需要的朋友可以参考下 在Heap中,我们依靠PostgreSQL支撑大多数后端繁重的任务,我们存储每个事件为一个hstore blob,我们为每个跟踪的用户维护一个已完成事件的PostgreSQL数组,并将这些事件按时间排序. Hstore能够让我们以灵活的方式附加属性到事件中,而且事件数组赋予了我们强大的性能,特别是对于漏斗查询,在这些查询中我们计算不同转化渠道步骤间的输出. 在这篇文章中,我们看看那

  • PostgreSQL中的XML操作函数代码 2014-02-27

    PostgreSQL中的XML操作函数代码 XML内容生成部分 SQL数据生成XML的函数. 1. xmlcomment:生成注释函数. xmlcomment(text ) 例: SELECT xmlcomment('hello'); xmlcomment -------------- <!--hello--> 2. xmlconcat:XML连接函数 xmlconcat(xml [, ...]) 例: SELECT xmlconcat('<abc/>', '<bar>

  • 举例简单介绍PostgreSQL中的数组 2014-03-10

    这篇文章主要介绍了举例简单介绍PostgreSQL中的数组,PostgreSQL是一个高性能关系型数据库,学习PostgreSQL将成为趋势,需要的朋友可以参考下 PostgreSQL 有很多丰富的开箱即用的数据类型,从标准的数字数据类型.到几何类型,甚至网络数据类型等等.虽然很多人会忽略这些数据类 型,但却是我最喜欢的特性之一.而数组数据类型正如你所期望的,可以在 PostgreSQL 存储数组数据,有了这个特性,你可以在单个表中实现以往需要多个表才能实现的存储要求. 为什么要使用数组来存储数

  • PHP 读取Postgresql中的数组 2014-05-07

    PHP 读取Postgresql中的数组,需要的朋友可以参考一下 function getarray_postgresql($arraystr) { $regx1 = '/^{(.*)}$/'; $regx2 = "/\"((\\\\\\\\|\\\\\"|[^\"])+)\"|[^,]+/"; $regx3 = '/^[^"].*$|^"(.*)"$/'; $match = null; preg_match( $r

  • PostgreSQL中调用存储过程并返回数据集实例 2014-05-09

    这篇文章主要介绍了PostgreSQL中调用存储过程并返回数据集实例,本文给出一创建数据表.插入测试数据.创建存储过程.调用创建存储过程和运行效果完整例子,需要的朋友可以参考下 这里用一个实例来演示PostgreSQL存储过程如何返回数据集. 1.首先准备数据表 //member_category create table member_category(id serial, name text, discount_rate real, base_integral integer); alter

  • 在Docker中使用MySQL的教程 2014-06-10

    这篇文章主要介绍了在Docker中使用MySQL的教程,介绍了简单的内部搭建步骤,需要的朋友可以参考下 提及虚拟化技术,我可是linuxContainer(LXC)的热爱者.但随着Docker技术的声名鹊起,我想在这展示一下如何使用带有Docker的Mysql Docker是什么? 实际上,Docker就是LXC的封装.使用起来很有意思.Docker采用LXC来虚拟化每个应用.所以在接下来的示例中,我们会启动chroot环境中一个被封装在自己命名空间内的mysql实例(你也可以设置Cgroups

  • 介绍PostgreSQL中的Lateral类型 2014-06-29

    这篇文章主要介绍了介绍PostgreSQL中的Lateral类型,Lateral是PostgreSQL9.3版本以来加入的内置类型,需要的朋友可以参考下 PostgreSQL 9.3 用了一种新的联合类型! Lateral联合的推出比较低调,但它实现了之前需要使用编写程序才能获得的强大的新查询. 在本文中, 我将会介绍一个在 PostgreSQL 9.2 不可能被实现的渠道转换分析. 什么是 LATERAL 联合? 对此的最佳描述在文档中 可选 FROM 语句清单 的底部: LATERAL 关键

  • 在Python中处理XML的教程 2014-07-09

    这篇文章主要介绍了在Python中处理XML的教程,是Python网络编程中的基础知识,需要的朋友可以参考下 XML虽然比JSON复杂,在Web中应用也不如以前多了,不过仍有很多地方在用,所以,有必要了解如何操作XML. DOM vs SAX 操作XML有两种方法:DOM和SAX.DOM会把整个XML读入内存,解析为树,因此占用内存大,解析慢,优点是可以任意遍历树的节点.SAX是流模式,边读边解析,占用内存小,解析快,缺点是我们需要自己处理事件. 正常情况下,优先考虑SAX,因为DOM实在太占内

  • 介绍PostgreSQL中的范围类型特性 2014-08-04

    这篇文章主要介绍了介绍PostgreSQL中的范围类型特性,范围类型特性自9.2版本开始加入,需要的朋友可以参考下 PostgreSQL 9.2 的一项新特性就是范围类型 range types,通过这个名字你可以轻松猜出该类型的用途,它可让你为某列数据定义数值范围. 这个简单的特性可以让我们不需要定义两个字段来描述数值的开始值和结束值,一个最直观的例子就是: postgres# CREATE TABLE salary_grid (id int, position_name text, star

  • 在Python的Flask框架中实现单元测试的教程 2014-08-06

    这篇文章主要介绍了在Python的Flask框架中实现单元测试的教程,属于自动化部署的方面,可以给debug工作带来诸多便利,需要的朋友可以参考下 概要 在前面的章节里我们专注于在我们的小应用程序上一步步的添加功能上.到现在为止我们有了一个带有数据库的应用程序,可以注册用户,记录用户登陆退出日志以及查看修改配置文件. 在本节中,我们不为应用程序添加任何新功能,相反,我们要寻找一种方法来增加我们已写代码的稳定性,我们还将创建一个测试框架来帮助我们防止将来程序中出现的失败和回滚. 让我们来找bug

  • 介绍PostgreSQL中的jsonb数据类型 2014-08-12

    这篇文章主要介绍了介绍PostgreSQL中的jsonb数据类型,jsonb是PostgreSQL9.4中开始内置的类型,能够支持GIN索引,需要的朋友可以参考下 PostgreSQL 9.4 正在加载一项新功能叫jsonb,是一种新型资料,可以储存支援GIN索引的JSON 资料.换言之,此功能,在即将来临的更新中最重要的是,如果连这都不重要的话,那就把Postgres 置于文件为本数据库系统的推荐位置吧. 自从9.2开始,一个整合JSON 资料类型已经存在,带有一整套功能(例如资料产生和资料解

  • Oracle中手动删除数据库教程 2014-08-13

    这篇文章主要介绍了Oracle中手动删除数据库教程,本文给出了详细步骤以及清除ASM数据库的步骤,需要的朋友可以参考下 在很多情况下,或无法使用dbca工具的时候,我们需要手动来删除数据库.对此,可以借助drop database命令来实现,下面的描述中给出手动删除数据库. 的具体步骤,包含文件系统数据库以及ASM数据库.环境:Oracle Enterprise Linux 5.4 + Oracle 10g R2 . 一.手动删除文件系统数据库 1.停止监听与OEM $ lsnrctl stop

  • 简单的Ruby中的Socket编程教程 2014-12-02

    这篇文章主要介绍了简单的Ruby中的Socket编程教程,是为Ruby on Rails学习过程当中的基础知识,需要的朋友可以参考下 Ruby提供了两个级别访问网络的服务,在底层你可以访问操作系统,它可以让你实现客户端和服务器为面向连接和无连接协议的基本套接字支持. Ruby 统一支持应用程的网络协议,如FTP.HTTP等. 不管是高层的还是底层的.ruby提供了一些基本类,让你可以使用TCP,UDP,SOCKS等很多协议交互,而不必拘泥在网络层.这些类也提供了辅助类,让你可以轻松的对服务器进行

  • 在Ruby on Rails中使用AJAX的教程 2014-12-13

    这篇文章主要介绍了在Ruby on Rails中使用AJAX的教程,文章来自于IBM官方网站技术文档,需要的朋友可以参考下 如果没有听说过 Rails,那么欢迎您外星旅行归来,近几年大概只有那个地方没有听说过 Ruby on Rails 了.Rails 最吸引人的地方是能够很快地建立功能完备的应用程序并运行起来.Rails 为 Ajax 而内置集成的 Prototype.js 库可以轻松快速地创建所谓的富 Internet 应用程序. 本文将逐步引导您创建 Rails 应用程序.然后深入分析如何