Re: Recursive CTE trees + Sorting by votes

Hello Martijn,

Thanks for the reply, my responses are inline below.

On Wed, Aug 6, 2014 at 5:38 PM, Martijn van Oosterhout <kleptog(at)svana(dot)org>
wrote:

> On Wed, Aug 06, 2014 at 05:28:09PM -0400, Gregory Taylor wrote:
> > We are working on a threaded comment system, and found this post by
> Disqus
> > to be super helpful:
> >
> >
> http://cramer.io/2010/05/30/scaling-threaded-comments-on-django-at-disqus/
> >
> > The CTE works wonderfully, and we're really happy with the results. The
> > last obstacle is figuring out how to sort by a "votes" field, meanwhile
> > preserving the tree structure.
>
> What do you mean exactly? Do you mean that want everything at the same
> level to be sorted by vote?
>

Each level of the tree should be sorted by vote, while retaining the
correct hierarchy. So the top level entry with the most votes should be at
the top, plus all of the items beneath it (with each level of the tree
under that row being sorted correctly).

>
> > If we "ORDER BY path, votes" (assuming we have the same structure as in
> the
> > article), we never need tie-breaking on "path", so the "votes" part of
> this
> > doesn't even come into the equation.
> >
> > I suspect we need to do some path manipulation, but I'm not too sure of
> > where to begin with this. I attempted incorporating "votes" into the
> path,
> > but I failed pretty badly with this. It's probably way off, but here's my
> > last (failed) attempt:
> >
> > https://gist.github.com/gtaylor/e3926a90fe108d52a4c8
>
> I think what you need to do is do the ordering withing the CTE itself.
> Something like:
>
> WITH RECUSIVE cte () AS (
> SELECT ... ORDER BY vote DESC
> UNION ALL
> SELECT ... JOIN cte ... ORDER BY vote DESC
> ) SELECT * from cte;
>

It looks like you can't order within a CTE.

>
> Or another idea, add a column that is the path of the parent:
>
> WITH RECUSIVE cte () AS (
> SELECT array[] as path_parent, array[id] as path, ... ORDER BY vote DESC
> UNION ALL
> SELECT cte.path as path_parent, cte.path || comments.id as path, ...
> JOIN cte ... ORDER BY vote DESC
> ) SELECT * from cte order by path, votes desc;
>

I got this recommendation from someone else, and think that it's probably
the way to go. I've been playing with it unsuccessfully so far, though.
Most certainly because I've got something weirded up. Here's what I have:

WITH RECURSIVE cte (
id, discussion_id, body, num_votes,
class_section_id, modified_time,
author_id, reply_parent_id,
path, votes_path, depth
) AS (
SELECT discussion_response.id, discussion_response.discussion_id,
discussion_response.body, discussion_response.num_votes,
discussion_response.last_edited_time,
discussion_response.class_section_id,
discussion_response.author_id,
discussion_response.reply_parent_id,
array[id] AS path,
array[num_votes, id] AS votes_path,
1 AS depth
FROM discussion_response
WHERE reply_parent_id IS NULL AND discussion_id=2763

UNION ALL

SELECT discussion_response.id, discussion_response.discussion_id,
discussion_response.body, discussion_response.num_votes,
discussion_response.last_edited_time,
discussion_response.class_section_id,
discussion_response.author_id,
discussion_response.reply_parent_id,
cte.path || discussion_response.id,
cte.votes_path || discussion_response.num_votes ||
discussion_response.id,
cte.depth + 1 AS depth
FROM discussion_response
JOIN cte ON discussion_response.reply_parent_id = cte.id
WHERE discussion_response.discussion_id=2763
)
SELECT * FROM cte ORDER BY votes_path DESC, path DESC LIMIT 50 OFFSET 0;

The problem with this is that non-root level (depth > 1) rows end up at the
top because of the ordering by votes_path. For example:

id=292839, num_votes=0, reply_parent_id=211957,
votes_path={2,211957,0,292839}, path={211957,292839}, depth=2
id=211957, num_votes=2, reply_parent_id=NULL, votes_path={2,211957},
path={211957}, depth=1

I understand why it is ordered this way, it's just not what I was hoping
for. Ideally this ends up like this:

id=211957, num_votes=2, reply_parent_id=NULL, votes_path={2,211957},
path={211957}, depth=1
id=292839, num_votes=0, reply_parent_id=211957,
votes_path={2,211957,0,292839}, path={211957,292839}, depth=2

Sorting by path causes the correct "tree" structure to be returned and in
the right order, but obviously it's not
sorted at all by votes.

--
Greg Taylor
http://gc-taylor.com