How to Simulate a Minheap in PL/SQL with a Global Temporary Table

PL/SQL doesn't have a minheap data structure.

It can be simulated with an associative array, which is sensible when you don't want to use a global temporary table and when the values in your minheap can fit within a 32bit PLS_INTEGER.

If you can use a global temporary table, a minheap is quite easy to implement and the code is very intuitive.

create global temporary table minheap(
    value number
);

create index minheap_n1 on minheap (value);

DECLARE
    v_value NUMBER;

    FUNCTION heap_pop
    RETURN PLS_INTEGER
    IS
        v_value PLS_INTEGER;
    BEGIN
        DELETE FROM minheap
        WHERE 1=1
            AND value = (
                SELECT MIN(value)
                FROM minheap
            )
            AND rownum = 1
        RETURNING value INTO v_value
        ;

        RETURN v_value;
    END heap_pop;

    PROCEDURE heap_push(
        p_value PLS_INTEGER
    )
    IS
    BEGIN
        INSERT INTO minheap (
            value
        ) VALUES (
            p_value
        );
    END heap_push;

    PROCEDURE heap_print
    IS
    BEGIN
        FOR i IN (
            SELECT value
            FROM minheap
            ORDER BY value
        ) LOOP
            DBMS_OUTPUT.PUT_LINE(i.value);
        END LOOP;

        DBMS_OUTPUT.PUT_LINE('');
    END heap_print;
BEGIN
    FOR i IN 1 .. 5 LOOP
        heap_push(1);
    END LOOP;
    heap_push(10);

    heap_print();


    FOR i IN 1 .. 5 LOOP
        v_value := heap_pop();

        v_value := v_value + i;

        heap_push(v_value);

        heap_print();
    END LOOP;


END;
/

The query used for heap_pop is pretty good:

DELETE FROM minheap
WHERE 1=1
    AND value = (
        SELECT MIN(value)
        FROM minheap
    )
    AND rownum = 1
;

Here is the execute_plan:

-------------------------------------------------------------
| Id  | Operation                     | Name       | E-Rows |
-------------------------------------------------------------
|   0 | DELETE STATEMENT              |            |        |
|   1 |  DELETE                       | MINHEAP    |        |
|*  2 |   COUNT STOPKEY               |            |        |
|*  3 |    INDEX RANGE SCAN           | MINHEAP_N1 |      1 |
|   4 |     SORT AGGREGATE            |            |      1 |
|   5 |      INDEX FULL SCAN (MIN/MAX)| MINHEAP_N1 |      1 |
-------------------------------------------------------------

Predicate Information (identified by operation id):
---------------------------------------------------

   2 - filter(ROWNUM=1)
   3 - access("VALUE"=)

The INDEX FULL SCAN(MIN/MAX) retrieves the minimum value from this table in about as fast any any SQL operation. It then makes a second index range scan with this value to get the rowid, and then finally performs the delete. It would be better if it could retrieve the max value and the rowid in one shot, but this is fast enough.


Comments

Add Comment

Name

Email

Comment

Are you human? + eight = 12