[ORACLE] Lückenlose Generierung von ID`s ?

[Exceptionfault]

In meinem Blog habe ich einen Artikel zur Generierung von ID`s geschrieben. Da dort aber wohl niemand ausser mir was nachliesst, ich aber gerne ein paar andere Meinungen zu dem Thema hätte, erlaube ich mir das Thema hier nochmal zu posten.

--- Lückenfüller ---

Sequences sind eine wunderbare und eine performante Lösung bei der Generierung von eindeutigen Schlüsseln. Leider helfen Sie uns nicht unbedingt weiter, wenn in einer Zahlenreihe keine Lücken existieren dürfen, oder falls doch, diese zuerst gefüllt werden sollen. Sequences arbeiten quasi als autonome Transaktion, d.h. einmal einen Wert von der Sequence gelesen ist dieser vergeben und die Sequence wird incrementiert. Auch ein Rollback bringt den vergebenen Wert nicht mehr zurück, was das folgende Beispiel zeigt:

CREATE SEQUENCE TESTSEQ
    START WITH 1
    INCREMENT BY 1
    NOCACHE
    ORDER;
    
CREATE TABLE SEQ_TEST (
  ID NUMBER
);

INSERT INTO SEQ_TEST VALUES ( TESTSEQ.NEXTVAL );

SELECT * FROM SEQ_TEST;

        ID
----------
         1
         
ROLLBACK;

INSERT INTO SEQ_TEST VALUES ( TESTSEQ.NEXTVAL );

        ID
----------
         2

Wie schaffe ich es aber nun (performant!) meine Tabelle lückenlos zu füllen, wenn wir davon ausgehen, dass durch Löschoperationen auch Lücken innerhalb meiner Zahlenreihe auftreten können?



Der klassische Ansatz ist einfach und logisch. In einer Schleife werden alle sortierten Werte durchlaufen und die erste freie ID zurückgegeben:

CREATE OR REPLACE FUNCTION GET_NEXT_ID RETURN NUMBER
is
    TYPE idtab  IS TABLE OF FBITEST.PKID%TYPE;
    ids     idtab;
begin
    SELECT  PKID
    BULK    COLLECT INTO ids
    FROM    FBITEST
    ORDER   BY PKID;
    
    FOR i IN ids.FIRST .. ids.LAST LOOP
        IF i <> ids(i) THEN
            RETURN i;
        END IF;
    END LOOP;
    RETURN i + 1;
end;
/

Großer Nachteil ist hier, dass die Performance theoretisch linear zur Anzahl der Datensätze abnimmt. Zudem bietet diese Funktion keinerlei Transaktionssicherheit. Es wäre also durchaus möglich, dass mir die Funktion eine Zahl zurückliefert, die gerade von einer anderen Transaktion ebenso genutzt wird. Wirkliche Vorteile sehe ich in dieser Funktion keine, ausser möglicherweise, dass der Algorithmus am einfachsten ist?!

Mit Hilfe der Analytischen Funktionen bietet sich folgende Möglichkeit zur Ermittlung von Lücken innerhalb einer Zahlenreihe. Die Zahlenreihe wird sortiert und jeder Wert mit der Zeilennummer versehen. Ab dem Datensatz, wo Wert der Zeile, und Nummer der Zeile auseinander laufen, ist eine Lücke in der Zahlenreihe. Das Beispiel funktioniert bei gleicher Performance auch mit der Pseudospalte ROWNUM.

SELECT  MIN( rn )
FROM    (
    SELECT  ROW_NUMBER() OVER ( ORDER BY PKID ) AS RN,
            PKID
    FROM    FBITEST    
)    
WHERE   RN <> PKID;

----------------------------------------------------------------------
| Id  | Operation          | Name       | Rows  | Bytes | Cost (%CPU)|
----------------------------------------------------------------------
|   0 | SELECT STATEMENT   |            |     1 |    26 |  2104   (1)|
|   1 |  SORT AGGREGATE    |            |     1 |    26 |            |
|*  2 |   VIEW             |            |  1000K|    24M|  2104   (1)|
|   3 |    WINDOW NOSORT   |            |  1000K|  4882K|  2104   (1)|
|   4 |     INDEX FULL SCAN| PK_FBITEST |  1000K|  4882K|  2104   (1)|
----------------------------------------------------------------------

Auch bei dieser Funktion wird bei steigender Anzahl Datensätze die Performance nachlassen, wenn vielleicht auch nicht unbedingt linear. Der Explain Plan zeigt jedoch einen erheblichen Aufwand für die Datenbank bei der Ermittlung. Obwohl die Lücke in meinem Beispiel schon bei Datensatz 40.000 von insgesammt 1.000.000 Datensätze war mussten alle Sätze gelesen werden. Die ermittelten Kosten und der Speicherbedarf sind immens. Auch hier ist - wenn nicht gerade als Subselect in einem INSERT benutzt - keine Transaktionssicherheit gewährleistet.

Den letzten Ansatz möchte ich nur theoretisch beschreiben da er etwas umfangreicher ist. Die Idee ist eine Art Freelist zu halten, die freie Nummern kennt, und eine Sequence die neue Nummern generiert, falls die Freelist leer ist. Wir benötigen also eine zusätzliche Tabelle in der alle Nummern abgelegt werden, die aus der Haupttabelle gelöscht werden (z.B. per Trigger), und in der alle Nummern abgelegt werden die zwar von der Sequence generiert wurden, aber durch ein ROLLBACK nicht verwendet werden. Um nun eine freie Nummer zu erhalten muss geprüft werden ob ein Eintrag in der Freelist vorhanden ist und der kleinste selektiert werden. (SELECT FOR UPDATE für Transaktionssicherheit!). Wird die freie Nummer genutzt verschwindet sie logischerweise wieder aus der Freelist. Ist diese leer werden neue Zahlen durch die Sequence generiert.

Auch bei steigender Anzahl an Datensätzen bleibt das Auffinden freier Nummern konstant. Relevant für die Performance ist in diesem Fall die Häufigkeit von Löschoperationen in der Haupttabelle. Offen ist die Frage: Welche Fälle können auftreten, bei denen inkosistenzen zw. der Freelist und der Haupttabelle auftreten? Und wie kann ich sie verhindern? Nachteilig finde ich zudem die zahlreichen unterschiedlichen Objekte: Freelist Tabelle, Trigger für Löschoperationen, Sequence für neue ID`s, Prozedur zum kapseln...

Fazit:
Von den 3 Verfahren nutze ich i.d.R. nur das 3. Es ist zwar recht komplex, hat sich aber bis jetzt bewährt. Das 2. Verfahren mit den Analytischen Funktionen eignet sich meiner Meinung nach sehr gut für adhoc Abfragen. Ich bin mir sicher, dass die gezeigten Lösungen nicht die einzigen Möglichkeiten sind, deshalb wäre ich über Feedback sehr glücklich.

 

[MPr]

die Lösungen gefallen mir gut, allerdings sehe ich nicht ganz den Sinn einer (weitgehend) lückenlosen Nummernfolge (aber ich glaube, die Diskussion über diese Anforderung ist auch nicht mehr ganz neu).

Bei Fall 2 könnte man neben ROW_NUMBER wahrscheinlich auch LEAD oder LAG in Betracht ziehen, aber ich vermute, das hätte keinen entscheidenden Einfluss auf die Performance (zum Testen dieser Annahme bin ich leider nicht gekommen).

Gruß

MP

 

[tkeuk]

Hi zusammen
ich habe es auf folgende Art gelöst

select seq from (select rownum seq from tabelle1) rn
left join tabelle1 sq on rn.seq=sq.seq
where sq.seq is null order by rn.seq

das setzt natürlich voraus dass die tabelle1 schon nach der sequence sortiert ist.

Sollte eigentlich so stimmen na ja sicher ist man natürlich nie ......

Mfg