PostgreSQL 9.4下多表跨列高效排序方案技术问询

Great question! Let's break this down clearly #

First off: your progressive sorting idea is totally feasible, and it’s a smart way to cut down on expensive cross-table joins. Instead of joining all high-cost tables upfront for every row, you only pull in the extra data when you need it (for subsets where the previous sort field didn’t give unique ordering). This can drastically reduce the total computational overhead, especially if your early sort fields have good cardinality (i.e., they split the data into small groups quickly).

Implementing this in PostgreSQL 9.4 #

PostgreSQL 9.4 supports recursive CTEs and window functions, which are perfect for building this progressive sorting logic. Let’s walk through a concrete example, then talk about dynamic support for user-defined sort/filter rules.

Example Scenario

Suppose we have:

• A main table objects (100k+ rows, primary key id)
• Sort order: first by objects.category_id (low-cost, native field), then by high_cost_table1.score (expensive join), then by high_cost_table2.create_time (another expensive join)
• We also want to apply a filter (e.g., objects.active = true) to reduce the initial dataset.

Step-by-Step Recursive CTE Implementation

WITH RECURSIVE sorted_objects AS (
    -- Initial step: Sort by first (low-cost) field, group rows with identical values
    SELECT
        o.id,
        o.category_id AS sort_col1,
        NULL::numeric AS sort_col2,
        NULL::timestamp AS sort_col3,
        -- Assign a rank to each group of identical category_id values
        DENSE_RANK() OVER (ORDER BY o.category_id) AS current_rank,
        1 AS sort_step,
        -- Track position within the group and group size
        ROW_NUMBER() OVER (PARTITION BY o.category_id ORDER BY o.category_id) AS intra_rank,
        COUNT(*) OVER (PARTITION BY o.category_id) AS group_size
    FROM objects o
    WHERE o.active = true -- Apply your filter first to shrink the dataset!

    UNION ALL

    -- Recursive step: Refine sorting for groups that still have duplicate order
    SELECT
        so.id,
        so.sort_col1,
        -- Only pull in the next sort field if we're on the corresponding step
        CASE WHEN so.sort_step = 1 THEN hc1.score ELSE so.sort_col2 END AS sort_col2,
        CASE WHEN so.sort_step = 2 THEN hc2.create_time ELSE so.sort_col3 END AS sort_col3,
        -- Update the rank to include the new sort field
        DENSE_RANK() OVER (
            ORDER BY so.current_rank, 
            CASE WHEN so.sort_step = 1 THEN hc1.score ELSE so.sort_col2 END,
            CASE WHEN so.sort_step = 2 THEN hc2.create_time ELSE so.sort_col3 END
        ) AS current_rank,
        so.sort_step + 1 AS sort_step,
        ROW_NUMBER() OVER (
            PARTITION BY so.current_rank 
            ORDER BY 
            CASE WHEN so.sort_step = 1 THEN hc1.score ELSE so.sort_col2 END,
            CASE WHEN so.sort_step = 2 THEN hc2.create_time ELSE so.sort_col3 END
        ) AS intra_rank,
        COUNT(*) OVER (PARTITION BY so.current_rank) AS group_size
    FROM sorted_objects so
    -- Only process groups that haven't been uniquely sorted yet
    WHERE so.group_size > 1
    -- Join high-cost tables only when needed for the current sort step
    LEFT JOIN high_cost_table1 hc1 ON so.id = hc1.object_id AND so.sort_step = 1
    LEFT JOIN high_cost_table2 hc2 ON so.id = hc2.object_id AND so.sort_step = 2
)
-- Final output: Get the final sorted order for all rows
SELECT 
    id,
    current_rank AS final_rank
FROM sorted_objects
-- Stop when groups are unique OR we've used all sort fields
WHERE group_size = 1 OR sort_step = 3
ORDER BY final_rank;

Key Details of This Implementation

1. Filter Early: We apply the filter in the initial CTE step to reduce the number of rows we need to process from the start—this is one of the biggest performance wins.
2. Progressive Joins: We only join high-cost tables for groups that actually need the extra sort field, avoiding unnecessary expensive joins.
3. Recursive Termination: The recursion stops when either a group is fully sorted (only 1 row left) or we’ve exhausted all sort fields.

Supporting Dynamic User Sort/Filter Rules #

If users can pick arbitrary sort fields and filters, you can wrap this logic in a PL/pgSQL function to generate dynamic SQL. Here’s a simplified example:

CREATE OR REPLACE FUNCTION dynamic_progressive_sort(
    filter_clause text,
    sort_columns text[] -- Format: ['main_table.field', 'high_cost_table1.field', ...]
) RETURNS TABLE(id int, final_rank int) AS $$
DECLARE
    sql text;
    sort_col_defs text[];
    join_clauses text[];
    sort_order_clauses text[];
    total_sort_steps int := array_length(sort_columns, 1);
BEGIN
    -- Build definitions for sort columns in the CTE
    sort_col_defs := ARRAY['o.' || split_part(sort_columns[1], '.', 2) || ' AS sort_col1'];
    sort_order_clauses := ARRAY['sort_col1'];
    
    -- Build join clauses and additional sort column definitions
    FOR i IN 2..total_sort_steps LOOP
        sort_col_defs := sort_col_defs || format(
            'CASE WHEN so.sort_step = %s THEN hc%s.%s ELSE so.sort_col%s END AS sort_col%s',
            i-1, i-1, split_part(sort_columns[i], '.', 2), i-1, i
        );
        sort_order_clauses := sort_order_clauses || format('sort_col%s', i);
        join_clauses := join_clauses || format(
            'LEFT JOIN %s hc%s ON so.id = hc%s.object_id AND so.sort_step = %s',
            split_part(sort_columns[i], '.', 1), i-1, i-1, i-1
        );
    END LOOP;

    -- Assemble the full recursive SQL query
    sql := format('
        WITH RECURSIVE sorted_objects AS (
            SELECT
                o.id,
                %s,
                DENSE_RANK() OVER (ORDER BY o.%s) AS current_rank,
                1 AS sort_step,
                ROW_NUMBER() OVER (PARTITION BY o.%s ORDER BY o.%s) AS intra_rank,
                COUNT(*) OVER (PARTITION BY o.%s) AS group_size
            FROM objects o
            WHERE %s

            UNION ALL

            SELECT
                so.id,
                %s,
                DENSE_RANK() OVER (ORDER BY so.current_rank, %s) AS current_rank,
                so.sort_step + 1 AS sort_step,
                ROW_NUMBER() OVER (PARTITION BY so.current_rank ORDER BY %s) AS intra_rank,
                COUNT(*) OVER (PARTITION BY so.current_rank) AS group_size
            FROM sorted_objects so
            %s
            WHERE so.group_size > 1
        )
        SELECT id, current_rank AS final_rank
        FROM sorted_objects
        WHERE group_size = 1 OR sort_step = %s
        ORDER BY final_rank;',
        array_to_string(sort_col_defs, ', '),
        split_part(sort_columns[1], '.', 2),
        split_part(sort_columns[1], '.', 2),
        split_part(sort_columns[1], '.', 2),
        split_part(sort_columns[1], '.', 2),
        filter_clause,
        array_to_string(sort_col_defs, ', '),
        array_to_string(sort_order_clauses, ', '),
        array_to_string(sort_order_clauses, ', '),
        array_to_string(join_clauses, ' '),
        total_sort_steps
    );

    RETURN QUERY EXECUTE sql;
END;
$$ LANGUAGE plpgsql;

You can call this function like this:

SELECT * FROM dynamic_progressive_sort(
    'active = true AND created_at > ''2023-01-01''',
    ARRAY['objects.category_id', 'high_cost_table1.score', 'high_cost_table2.create_time']
);

Performance Tips #

• Indexing: Add indexes to your main table’s sort fields (e.g., objects.category_id) and the foreign keys in high-cost tables (e.g., high_cost_table1.object_id). This will speed up both sorting and joins.
• Cardinality Check: If your first sort field has very low cardinality (e.g., only 2-3 unique values), this approach won’t save much—you’ll still end up joining most rows. In that case, you might want to reorder your sort fields to put higher-cardinality fields first.
• Test with Real Data: Always benchmark with your actual dataset—performance can vary based on data distribution and index quality.

内容的提问来源于stack exchange，提问作者Thomas