PL/SQL最长公共子序列（LCS）算法的性能优化问询

Looking at your current implementation, the core bottlenecks are the nested loops populating a bidimensional associative array and repeated SUBSTR calls inside those loops—both of which are costly in PL/SQL when dealing with tens of thousands of string pairs. Let’s break down actionable optimizations to get your runtime down to millisecond levels:

1. Reduce Space Complexity from 2D to 1D Array #

The standard LCS algorithm only requires the previous row of the matrix to compute the current row. Ditching the 2D array for two 1D arrays cuts memory usage drastically and eliminates the overhead of nested associative array access.

Optimized Function with 1D Arrays #

CREATE OR REPLACE FUNCTION GET_LCS_LENGTH(
    table1_string IN NVARCHAR2,
    table2_string IN NVARCHAR2
) RETURN NUMBER
AS
    TYPE t_number_array IS TABLE OF NUMBER INDEX BY BINARY_INTEGER;
    prev_row t_number_array;
    curr_row t_number_array;
    len_str1 NUMBER := LENGTH(table1_string);
    len_str2 NUMBER := LENGTH(table2_string);
    ch1 NVARCHAR2(1);
    ch2 NVARCHAR2(1);
BEGIN
    -- Initialize first row (all zeros)
    FOR j IN 1..len_str1 + 1 LOOP
        prev_row(j) := 0;
    END LOOP;

    FOR i IN 2..len_str2 + 1 LOOP
        ch1 := SUBSTR(table2_string, i-1, 1);
        curr_row(1) := 0; -- First column is always 0
        
        FOR j IN 2..len_str1 + 1 LOOP
            ch2 := SUBSTR(table1_string, j-1, 1);
            IF ch1 = ch2 THEN
                curr_row(j) := prev_row(j - 1) + 1;
            ELSE
                curr_row(j) := GREATEST(curr_row(j - 1), prev_row(j));
            END IF;
        END LOOP;
        
        -- Swap rows for next iteration
        prev_row := curr_row;
        curr_row.DELETE; -- Clear current row to save memory
    END LOOP;

    RETURN prev_row(len_str1 + 1);
END;
/

2. Pre-Extract Characters to Avoid Repeated SUBSTR Calls #

SUBSTR is a relatively expensive operation when called thousands of times in loops. Pre-extract all characters of both strings into arrays once, then access elements directly in loops.

Enhanced Version with Pre-Extracted Characters #

CREATE OR REPLACE FUNCTION GET_LCS_LENGTH(
    table1_string IN NVARCHAR2,
    table2_string IN NVARCHAR2
) RETURN NUMBER
AS
    TYPE t_char_array IS TABLE OF NVARCHAR2(1) INDEX BY BINARY_INTEGER;
    TYPE t_number_array IS TABLE OF NUMBER INDEX BY BINARY_INTEGER;
    
    str1_chars t_char_array;
    str2_chars t_char_array;
    prev_row t_number_array;
    curr_row t_number_array;
    len_str1 NUMBER := LENGTH(table1_string);
    len_str2 NUMBER := LENGTH(table2_string);
BEGIN
    -- Pre-extract all characters from both strings
    FOR j IN 1..len_str1 LOOP
        str1_chars(j) := SUBSTR(table1_string, j, 1);
    END LOOP;
    FOR i IN 1..len_str2 LOOP
        str2_chars(i) := SUBSTR(table2_string, i, 1);
    END LOOP;

    -- Initialize first row
    FOR j IN 1..len_str1 + 1 LOOP
        prev_row(j) := 0;
    END LOOP;

    FOR i IN 1..len_str2 LOOP
        curr_row(1) := 0;
        
        FOR j IN 1..len_str1 LOOP
            IF str2_chars(i) = str1_chars(j) THEN
                curr_row(j + 1) := prev_row(j) + 1;
            ELSE
                curr_row(j + 1) := GREATEST(curr_row(j), prev_row(j + 1));
            END IF;
        END LOOP;
        
        prev_row := curr_row;
        curr_row.DELETE;
    END LOOP;

    RETURN prev_row(len_str1 + 1);
END;
/

3. Batch Processing with Bulk Operations #

Instead of processing each table1 record against table2 one-by-one, use BULK COLLECT to fetch all table2 strings into a collection first. This minimizes SQL-PL/SQL context switches, which are a major performance drain for large datasets.

Example Batch Processing Wrapper #

DECLARE
    TYPE t_string_table IS TABLE OF NVARCHAR2(4000);
    table2_strings t_string_table;
    table1_str NVARCHAR2(4000);
    TYPE t_number_array IS TABLE OF NUMBER INDEX BY BINARY_INTEGER;
    lcs_results t_number_array;
    -- Assume you have a way to get table2 IDs alongside strings
    TYPE t_id_table IS TABLE OF NUMBER;
    table2_ids t_id_table;
BEGIN
    -- Fetch all table2 strings and IDs in one go
    SELECT your_string_column, id BULK COLLECT INTO table2_strings, table2_ids FROM table2;

    -- Process a single table1 record against all table2 strings
    table1_str := (SELECT your_string_column FROM table1 WHERE id = :some_table1_id);
    lcs_results.EXTEND(table2_strings.COUNT);
    
    FOR i IN 1..table2_strings.COUNT LOOP
        lcs_results(i) := GET_LCS_LENGTH(table1_str, table2_strings(i));
    END LOOP;

    -- Insert results into a target table in bulk (far faster than single inserts)
    FORALL i IN 1..lcs_results.COUNT
        INSERT INTO lcs_matching_results (table1_id, table2_id, lcs_length)
        VALUES (:some_table1_id, table2_ids(i), lcs_results(i));
END;
/

4. Additional PL/SQL Performance Tweaks #

• Use NOCOPY for large string parameters: Add NOCOPY to the function parameters (e.g., table1_string IN NOCOPY NVARCHAR2) to avoid copying large strings into the function stack.
• Limit string lengths: If business logic allows, truncate long strings to a reasonable maximum length to reduce loop iterations.
• Enable compiler optimizations: Run ALTER SESSION SET PLSQL_OPTIMIZE_LEVEL = 3; to let the PL/SQL compiler apply advanced optimizations like loop unrolling.

These changes combined should drastically reduce your runtime—moving from 5 seconds per table1 record to milliseconds by cutting memory overhead, reducing expensive function calls, and minimizing context switches.

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