Design a SQL query for Reddit-style hierarchical comment threads using a recursive CTE…
- User
Design a SQL query for Reddit-style hierarchical comment threads using a recursive CTE to fetch 5 levels deep, sorted by net score at each level. No OFFSET/LIMIT - and I need help optimizing it with the right composite index.
Assistant
This is a great question about designing a SQL query for Reddit-style hierarchical comments with recursive CTEs. Let me break down what we need:
- Reddit-style hierarchical comments (can be nested)
- Recursive CTE to fetch 5 levels deep
- Sorted by net score at each level
- No OFFSET/LIMIT
- Optimization with composite index
Let me think about the schema first. A typical Reddit-style comment structure would be:
CREATE TABLE comments ( id BIGINT PRIMARY KEY, post_id BIGINT, parent_id BIGINT, -- NULL for top-level comments, points to comment_id for replies author_id BIGINT, content TEXT, net_score INT, created_at TIMESTAMP, updated_at TIMESTAMP );Now, for a Reddit-style thread, we want to:
- Start with top-level comments (parent_id IS NULL)
- For each comment, fetch its direct children
- Repeat 5 levels deep
- Sort by net_score at each level
The challenge here is that we want to sort by net_score at each level, which means:
- Level 1 (top-level comments): sorted by net_score
- Level 2 (children): each group sorted by net_score
- And so on...
Here's the approach:
WITH RECURSIVE comment_hierarchy AS ( -- Base case: top-level comments SELECT id, post_id, parent_id, author_id, content, net_score, created_at, 1 as depth, ARRAY[id] as path, id as root_id FROM comments WHERE post_id = ? AND parent_id IS NULL ORDER BY net_score DESC UNION ALL -- Recursive case: get children of current comments SELECT c.id, c.post_id, c.parent_id, c.author_id, c.content, c.net_score, c.created_at, ch.depth + 1, ch.path || c.id, ch.root_id FROM comments c INNER JOIN comment_hierarchy ch ON c.parent_id = ch.id WHERE ch.depth < 5 ORDER BY c.net_score DESC ) SELECT * FROM comment_hierarchy;There's a problem though—the ORDER BY in the recursive part doesn't actually work the way we need it to. In recursive CTEs, ORDER BY only affects the final result set, not how rows are processed during recursion. To properly sort children by score at each level, I need to handle the ordering differently, perhaps by using row_number() or by restructuring how the recursion processes the hierarchy. _id, author_id, content, net_score, created_at, 1 as depth, ARRAY[id] as path FROM comments WHERE post_id = $1 AND parent_id IS NULL ORDER BY net_score DESC
UNION ALL -- Recursive case: get children, sorted by score SELECT c.id, c.post_id, c.parent_id, c.author_id, c.content, c.net_score, c.created_at, ch.depth + 1, ch.path || c.id FROM comments c INNER JOIN comment_hierarchy ch ON c.parent_id = ch.id WHERE ch.depth < 5 ORDER BY c.net_score DESC) SELECT * FROM comment_hierarchy ORDER BY path;
The key insight is that ORDER BY within each recursive iteration sorts siblings at that level, which gives us the hierarchical ordering we need. The final ORDER BY path ensures the tree structure is preserved in the result set. I should use ARRAY to track the path through the hierarchy, allowing proper sorting of the complete result while maintaining parent-child relationships. I need to build a hierarchical sort path that preserves the scoring order at each level. The approach uses a position path constructed during recursion - at the base level, top comments are ranked by net_score, then each child is ranked within its parent using ROW_NUMBER. I'm also maintaining a sort_key array that combines net_score, depth, and id to ensure proper ordering when displaying the final result. The recursive step appends each child's position to the parent's path and extends the sort_key array accordingly. However, window functions like ROW_NUMBER can't be used directly in recursive CTEs in most databases. A cleaner solution is to use a simple path array that tracks comment IDs, then sort the final result by this path to maintain hierarchy while ordering siblings by their net_score at retrieval time. For PostgreSQL, I can build the sort order into the path itself by tracking both IDs and scores. The base case selects top-level comments, then recursively appends child comments while maintaining their score information in parallel arrays. This way, when ordering by the score path at the end, siblings naturally sort by their net_score in descending order while preserving the tree structure. I'm overcomplicating this. Let me step back and offer practical solutions tailored to the database system being used. For PostgreSQL, I can leverage its recursive CTE capabilities by applying ORDER BY within the recursive part itself. The base case selects top-level comments ordered by net_score, then builds a sort_key by concatenating IDs as we traverse down the hierarchy. The recursive portion joins child comments and maintains depth tracking while preserving the sort order through the accumulated key. However, ORDER BY in recursive CTEs has limitations—it doesn't reliably maintain sort order across different hierarchy levels the way we'd expect. A more practical approach is to fetch the complete hierarchy structure with all necessary data, then handle the sorting at the application layer where we have full control over how comments are ordered both within and across levels. || c.id FROM comments c INNER JOIN comment_hierarchy ch ON c.parent_id = ch.id WHERE ch.depth < 5 ) SELECT * FROM comment_hierarchy ORDER BY path DESC;For a Reddit-style approach where comments are ranked by score within each level:
WITH RECURSIVE comment_hierarchy AS ( -- Base case: top-level comments ranked by net_score SELECT id, post_id, parent_id, author_id, content, net_score, created_at, 1 as depth, CAST(ROW_NUMBER() OVER (ORDER BY net_score DESC) AS CHAR(10)) as sort_position, ARRAY[id] as comment_path FROM comments WHERE post_id = $1 AND parent_id IS NULL UNION ALL -- Recursive: fetch children ranked by score at each depth level SELECT c.id, c.post_id, c.parent_id, c.author_id, c.content, c.net_score, c.created_at, ch.depth + 1, ch.sort_position || CAST(ROW_NUMBER() OVER (PARTITION BY c.parent_id ORDER BY c.net_score DESC) AS CHAR(10)), ch.comment_path || c.id FROM comments c INNER JOIN comment_hierarchy ch ON c.parent_id = ch.id WHERE ch.depth < 5 ) SELECT * FROM comment_hierarchy ORDER BY sort_position;This approach uses a composite sort position that ranks comments by score within their parent, creating a hierarchical ordering that respects score at each nesting level while maintaining the tree structure. I need to reconsider the window function approach—PostgreSQL's recursive CTEs handle them unpredictably. A better strategy is using an array to track the comment path, then sorting by that path at each depth level based on scores rather than IDs.
The issue with storing just IDs in the path is that I lose score information needed for proper ordering. I should include scores in a sortable format within the path itself so that when I order by the path array, comments naturally sort by their scores at each nesting level. I see the issue—window functions don't work reliably in recursive CTEs. I need a different approach that calculates sort positions without relying on ROW_NUMBER() in the recursive part.
Instead, I can use a path-based sorting strategy. For the base case, I'll fetch top-level comments ordered by score and store their position. In the recursive step, I'll do the same for child comments, building up a sort path as I traverse the hierarchy. This way, I'm computing positions before entering the recursion rather than trying to use window functions within it.
The sort_key array stores score and ID pairs at each level, so when I order by sort_key DESC at the end, comments naturally sort by their score at the top level, then by child scores within each parent, maintaining the nested structure correctly.
For indexing, I need to optimize the two main query patterns: the base case fetching top-level comments for a post ordered by score, and the recursive joins looking up children by parent ID. A composite index on (post_id, parent_id, net_score DESC) handles both efficiently, though a filtered index on just (post_id, net_score DESC) WHERE parent_id IS NULL could be more targeted for the initial query.
The recursive lookups benefit from (parent_id, net_score DESC) to quickly find and sort child comments. If the schema includes soft deletes, adding a WHERE clause to filter active records keeps the indexes lean.
Here's the complete schema with optimized indexes:
CREATE TABLE comments ( id BIGINT PRIMARY KEY, post_id BIGINT NOT NULL, parent_id BIGINT, author_id BIGINT NOT NULL, content TEXT, net_score INT DEFAULT 0, created_at TIMESTAMP DEFAULT NOW(), updated_at TIMESTAMP DEFAULT NOW() ); CREATE INDEX idx_comments_post_parent_score ON comments(post_id, parent_id ASC NULLS FIRST, net_score DESC); CREATE INDEX idx_comments_parent_score ON comments(parent_id, net_score DESC) WHERE parent_id IS NOT NULL; CREATE INDEX idx_comments_post_id ON comments(post_id); WITH RECURSIVE comment_tree AS ( SELECT id, post_id, parent_id, author_id, content, net_score, created_at, 1 as depth, ARRAY[net_score::text, id::text] as sort_key FROM comments WHERE post_id = $1 AND parent_id IS NULL UNION ALL SELECT c.id, c.post_id, c.parent_id, c.author_id, c.content, c.net_score, c.created_at, ct.depth + 1, ct.sort_key || ARRAY[c.net_score::text, c.id::text] FROM comments c INNER JOIN comment_tree ct ON c.parent_id = ct.id WHERE ct.depth < 5 ) SELECT id, post_id, parent_id, author_id, content, net_score, created_at, depth FROM comment_tree ORDER BY sort_key DESC;The recursive query builds a hierarchical tree by starting with top-level comments, then joining child comments while tracking depth and building a composite sort key that preserves the score-based ordering at each level. The ORDER BY clause needs to sort by the accumulated sort_key array to maintain proper ranking throughout the tree structure.
When comparing arrays like ['100', '1'] versus ['50', '2'] in descending order, PostgreSQL compares element-by-element, so the higher score naturally comes first. For safety with text-based number comparison, I could pad the values using LPAD to ensure consistent sorting behavior across different score ranges.
The recursive query builds the tree by starting with top-level comments and appending sort keys as it traverses down to child comments, maintaining depth tracking up to 5 levels. Using (2147483647 - net_score) inverts the numeric comparison so higher scores appear first when sorting in ascending order. Rather than overcomplicating the approach, a cleaner PostgreSQL solution uses a recursive CTE that pre-sorts comments by score at each level, then orders the final result by the accumulated sort key array. Let me complete and refine this approach. The recursive query needs to fetch top-level comments first, then build out their children while maintaining score-based ordering at each level.
Starting with root comments where parent_id is null, I track depth and build a parent chain to preserve hierarchy. Then in the recursive step, I join on parent_id to get each comment's children, incrementing depth and appending to the chain. This way siblings get sorted by net_score while the tree structure stays intact.
The key insight is using arrays to track both the score path and id path from root to each node, allowing proper ordering across the entire hierarchy without losing the tree structure. I limit recursion to depth 5 to prevent runaway queries on deeply nested threads. array_append(ct.score_path, c.net_score), -- Append this node's score array_append(ct.id_path, c.id) FROM comments c INNER JOIN comment_thread ct ON c.parent_id = ct.id WHERE ct.depth < 5 ) SELECT id, post_id, parent_id, author_id, content, net_score, created_at, depth FROM comment_thread ORDER BY score_path DESC, id_path;
The `score_path` array tracks scores from root to leaf, so descending sort naturally orders siblings by their scores while preserving the thread structure. Using `id_path` as a tiebreaker ensures consistent ordering. For performance, I need to create indexes on the comments table. A composite index on `(post_id, parent_id, net_score)` will efficiently retrieve top-level comments sorted by score, and another index on `(parent_id, net_score)` will speed up the recursive lookups for finding children at each level. For the recursive joins, I need an index on `(parent_id, net_score DESC)` to efficiently handle the `WHERE parent_id = child_id ORDER BY net_score DESC` lookups. This single multicolumn index covers both the filter and sort in one pass, which is more efficient than separate indexes. I should finalize the index strategy with these two core indexes addressing the base case and recursive traversal patterns.</think> # Reddit-Style Hierarchical Comments with Recursive CTE ## Complete Solution with Query & Indexes ### 1. **Schema Setup** ```sql CREATE TABLE comments ( id BIGINT PRIMARY KEY, post_id BIGINT NOT NULL, parent_id BIGINT, -- NULL for top-level, points to comment id for replies author_id BIGINT NOT NULL, content TEXT, net_score INT DEFAULT 0, created_at TIMESTAMP DEFAULT NOW(), updated_at TIMESTAMP DEFAULT NOW(), CONSTRAINT fk_parent FOREIGN KEY (parent_id) REFERENCES comments(id) ON DELETE CASCADE, CONSTRAINT fk_post FOREIGN KEY (post_id) REFERENCES posts(id) ON DELETE CASCADE );
2. Optimized Recursive CTE Query
WITH RECURSIVE comment_thread AS ( -- ========== BASE CASE: Top-level comments ========== SELECT c.id, c.post_id, c.parent_id, c.author_id, c.content, c.net_score, c.created_at, 1 as depth, ARRAY[c.net_score] as score_hierarchy, ARRAY[c.id] as id_path FROM comments c WHERE c.post_id = $1 AND c.parent_id IS NULL UNION ALL -- ========== RECURSIVE CASE: Children at each level ========== SELECT c.id, c.post_id, c.parent_id, c.author_id, c.content, c.net_score, c.created_at, ct.depth + 1, ct.score_hierarchy || c.net_score, -- Build score path ct.id_path || c.id FROM comments c INNER JOIN comment_thread ct ON c.parent_id = ct.id WHERE ct.depth < 5 -- Stop at 5 levels deep ) SELECT id, post_id, parent_id, author_id, content, net_score, created_at, depth FROM comment_thread ORDER BY score_hierarchy DESC, -- Siblings sorted by score (rightmost = current level) id_path; -- Tie-breaker by insertion orderHow sorting works:
- Array
[100, 50, 30]compares element-by-element from left to right - DESC means higher scores bubble up (siblings ranked by their own score)
- Each level's children are naturally sorted by
net_scoresince it's the rightmost element
3. Composite Indexes (Critical for Performance)
-- Index 1: Base case query optimization -- Covers: WHERE post_id = ? AND parent_id IS NULL ORDER BY net_score DESC CREATE INDEX idx_comments_post_toplevel_score ON comments(post_id, net_score DESC) WHERE parent_id IS NULL; -- Index 2: Recursive join optimization -- Covers: WHERE parent_id = ? ORDER BY net_score DESC CREATE INDEX idx_comments_parent_score ON comments(parent_id, net_score DESC) WHERE parent_id IS NOT NULL; -- Index 3: Full composite (alternative, more flexible) -- Covers both patterns with one index CREATE INDEX idx_comments_post_parent_score ON comments(post_id, parent_id ASC NULLS FIRST, net_score DESC); -- Index 4: Optional - if soft deletes exist CREATE INDEX idx_comments_post_active ON comments(post_id, parent_id, net_score DESC) WHERE deleted_at IS NULL;Index selection rationale:
Pattern Best Index Why Base case: WHERE post_id AND parent_id IS NULL ORDER BY scoreIndex 1 or 3 Predicate filtering + sort order Recursive: WHERE parent_id = ? ORDER BY score DESCIndex 2 or 3 Covers join condition + ordering Covering index Index 3 Handles both with single scan
4. Query Execution Plan Analysis
-- Check efficiency with EXPLAIN EXPLAIN ANALYZE WITH RECURSIVE comment_thread AS ( SELECT c.id, c.post_id, c.parent_id, c.author_id, c.content, c.net_score, c.created_at, 1 as depth, ARRAY[c.net_score] as score_hierarchy, ARRAY[c.id] as id_path FROM comments c WHERE c.post_id = 12345 AND c.parent_id IS NULL UNION ALL SELECT c.id, c.post_id, c.parent_id, c.author_id, c.content, c.net_score, c.created_at, ct.depth + 1, ct.score_hierarchy || c.net_score, ct.id_path || c.id FROM comments c INNER JOIN comment_thread ct ON c.parent_id = ct.id WHERE ct.depth < 5 ) SELECT * FROM comment_thread ORDER BY score_hierarchy DESC, id_path;Expected plan:
CTE Scan (Rows: ~500-2000) ├─ Index Scan using idx_comments_post_toplevel_score (top-level: ~50 rows) └─ Nested Loop with Index Scan using idx_comments_parent_score (recursion: ~100-200 per level)
5. Alternative: Sorted Path Variant (if scores can be negative)
WITH RECURSIVE comment_thread AS ( SELECT c.id, c.post_id, c.parent_id, c.author_id, c.content, c.net_score, 1 as depth, -- Zero-pad scores for correct text sorting (e.g., handle negative scores) ARRAY[LPAD((9999999 - c.net_score)::text, 10, '0')] as sort_path FROM comments c WHERE c.post_id = $1 AND c.parent_id IS NULL UNION ALL SELECT c.id, c.post_id, c.parent_id, c.author_id, c.content, c.net_score, ct.depth + 1, ct.sort_path || LPAD((9999999 - c.net_score)::text, 10, '0') FROM comments c INNER JOIN comment_thread ct ON c.parent_id = ct.id WHERE ct.depth < 5 ) SELECT * FROM comment_thread ORDER BY sort_path;
6. Performance Optimization Tips
Optimization Benefit Use partial indexes (WHERE parent_id IS NULL) Smaller index size, faster lookup Denormalize score ranking Pre-calculate top comments, cache Connection pooling Reduces recursive query overhead Materialized CTE view For frequently accessed threads Pagination at application layer Show top 50, lazy-load children Example materialized view approach:
CREATE MATERIALIZED VIEW post_comment_hierarchy_5levels AS WITH RECURSIVE comment_thread AS ( -- [same CTE as above] ) SELECT * FROM comment_thread; CREATE INDEX idx_hierarchy_post_score ON post_comment_hierarchy_5levels(post_id, score_hierarchy DESC); REFRESH MATERIALIZED VIEW CONCURRENTLY post_comment_hierarchy_5levels;
7. Key Takeaways
✅ Array-based sorting:
score_hierarchy DESCnaturally handles multi-level ranking
✅ No OFFSET/LIMIT: Full hierarchy returned; pagination at application level
✅ 5-level depth: Tunable viaWHERE ct.depth < 5
✅ Composite indexes: Separate for base case and recursion = optimal performance
✅ Tree stability:id_pathtie-breaker prevents non-deterministic orderingFor large datasets (100k+ comments/post), consider: hybrid approach with top-N cache + lazy-loading of deeper levels.
Other models, same or similar prompt
Responses were produced in different, uncontrolled contexts (system prompts, settings, prior turns). This is not a benchmark.