Shulou(Shulou.com)05/31 Report--

This article to share with you is about how to achieve recursive query in PostgreSQL, Xiaobian think it is very practical, so share it with you to learn, I hope you can gain something after reading this article, not much to say, follow Xiaobian to see it.

Internally, it is represented as a drop:

A survey consists of many questions. A series of questions can be grouped (optionally) into a category. Our actual data structure will be a bit more complicated (especially the sub-question part of the sub-question), but let's just say it's just questions and categories.

This is how we save questions and categories.

Each question and category has an order_number field. Is an integer that specifies its relative relationship to other siblings.

For example, for the above survey:

Bar's order_number is smaller than Baz's.

The problems under such a category can appear in the correct order:

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

in fact, this is how we fetched the entire investigation from the very beginning. Each category gets all its children in order, and so on through the entity tree.

This gives us the depth-first order of the whole tree:

For surveys with more than 100 questions embedded in more than five layers, this is extremely slow.

recursive query

I have also used gems like awesome_nested_set, but as far as I know, none of them support fetch across multiple models.

Later, I stumbled upon a document that said PostgreSQL has support for recursive queries! Well, that's possible.

Then try to use recursive query to do this problem bar (at this time brother to its understanding is still very water, there is not in place, do not spray).

To do recursive queries in Postgres, you must first define an initialization query that is non-recursive.

In this case, it is the top-level question and category. The topmost elements do not have a parent category, so their category_id is empty.

( 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)

(This query and subsequent queries assume that the survey with id 2 is to be retrieved.)

This brings us to the topmost element.

The next part is about recursion. According to this Postgres document:

The recursion part is to get all the children of the element you got in the initialization part.

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;

And so on, recursion only gets questions. What if the first subcategory of a subterm is a category? Postgres does not give references to non-recursive items more than once. So UNION on question and category result sets doesn't work. Here's what needs to be done:

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 category and question result sets before joining with non-recursive parts.

This produces all the elements of investigation:

Unfortunately, the order doesn't seem right.

Sort within recursive queries

The problem is that although it is valid to get all the second level elements for the first level elements, this is a breadth-first search, and what is actually required is depth-first.

How could this be done?

Postgres has the ability to create arrays during queries.

Then create an array that stores the serial numbers of the elements fetched. Let's call this array path. The path of an element is:

path of parent category (if any)+ own order_number

If you use path to sort the result set, you can make the query depth-first!

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;

This is close. What's your favorite song?

This is caused by comparing IDs to find children:

WHERE e.category_id = fle.id

Fle contains both question and category. But what is needed is to match only category (because question has no children).

Then hardcode a type for each such query, so you don't have to try to check whether the question has children:

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;

That seems OK. Done!

Let's see how this works.

Using the script below (after creating a survey on the interface), I generated 10 sub-question sequences, each six layers deep.

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

Each question sequence looks like this:

Let's see if recursive queries are any faster than the first one.

pry(main)> Benchmark.ms { 5.times { Survey.find(9).sub_questions_using_recursive_queries }}=> 36.83999999996 pry(main)> Benchmark.ms { 5.times { Survey.find(9).sub_questions_in_order } }=> 1145.1309999999 The above is how to implement recursive queries in PostgreSQL. Xiaobian believes that some knowledge points may be seen or used in our daily work. I hope you can learn more from this article. For more details, please follow the industry information channel.

Welcome to subscribe "Shulou Technology Information " to get latest news, interesting things and hot topics in the IT industry, and controls the hottest and latest Internet news, technology news and IT industry trends.