DE68927743T2 - Sortier-/Mischausgabe - Google Patents

Description

• Die Erfindung bezieht sich auf eine Sortier-/Mischausgabe in computerunterstützten Datenbanken.
• Eine Datenbank dient zum Speichern großer Mengen von Daten, die von einem Benutzer auf Anfrage abgerufen werden können. Ein Benutzer kann entweder ein Anwendungsprogramm oder ein Endbenutzer sein, der über eine Eingabeeinrichtung mit dem Datenbanksystem kommuniziert. Zusammengehörende Datengruppen werden gewöhnlich als Datendateien oder Tabellen bezeichnet, wie sie normalerweise in relationalen Datenbanken verwendet werden. Die Datenreihen in einer Tabelle werden als logische Datensätze und die Datenspalten werden als Felder bezeichnet. In einem relationalen Datenbanksystem nimmt der Benutzer die Daten nur als Tabellen und nicht in einer anderen Gliederungsform, z.B. als hierarchische Datenstruktur, wahr.
• Diese Datenbanksysteme enthalten gewöhnlich ein Computerprogramm, das als Datenbankmanager bezeichnet wird und das als Reaktion auf verschiedene Befehle, die über eine Benutzerschnittstelle eingegeben werden, Daten speichert, editiert, aktualisiert, einfügt, löscht und abfragt. Ein Datenbankmanager verarbeitet sämtliche Anforderungen von Benutzern an die Datenbank, um die oben genannten verschiedenen Funktionen durchzuführen.
• Insbesondere für die Datenabfrage wurden zahlreiche Computersprachen entwickelt, um Suchbefehle oder "Abfragen" zu formulieren, auf die der Datenbankmanager reagiert, um die angeforderten Daten bereitzustellen. Bei diesen Abfragen handelte es sich im wesentlichen um codierte Suchbefehle, um einen Computer und den zugeordneten Datenbankmanager zu veranlassen, die gewünschte Suche durchzuführen.
• Im Zusammenhang mit den Sprachen zur Formulierung von Datenbankabfragen ergaben sich verschiedene Probleme. Erstens unterschieden sich zahlreiche Abfragesprachen von herkömmlichen Programmiersprachen. Der Datenbankbenutzer mit Programmiererfahrung mußte daher einen völlig neuen Befehlssatz lernen, nur um sinnvolle Daten aus einer Datenbank zu erhalten. Benutzer ohne Erfahrung, beispielsweise zahlreiche Terminal-Bediener, die auch über keine Computererfahrung verfügten, waren gezwungen, eine Form von Computerprogrammierung zu lernen - und das nur um eine Datenbank abzufragen. Darüber hinaus waren bei diesen Abfragesprachen Kenntnisse hochkomplexer Syntax- und Semantikregeln erforderlich, wodurch die Zahl derjenigen, die Daten erfolgreich abfragen konnten, auf einige wenige hoch- und teuerqualifizierte Benutzer beschränkt blieb. Das beeinträchtigte natürlich die Benutzung dieser Computersysteme und verhinderte maßgeblich ihre Nutzung durch zahlreiche Anwender.
• Die Standardabfragesprache (SQL, Structured Query Language) ist eine interaktive Abfragesprache für Endbenutzer, die als Schnittstelle dient, um mit dem Datenbankmanager Informationen abzurufen, sowie eine Datenbankprogrammiersprache, die in ein Anwendungsprogramm integriert werden kann, um über den Datenbankmanager auf die Daten in der Datenbank zuzugreifen. Mit SQL läßt sich der benötigte Informationstyp leicht spezifizieren.
• Ein Beispiel einer solchen Abfragesprache ist die Standardabfragesprache oder "SQL", die im Entwurfsvorschlag ANA Database Language SQL, Standard X3.135-1986, American National Standard Institute, Inc., 1430 Broadway, New York 10018, beschrieben ist. Des weiteren wird die SQL in "IBM Database 2 SQL Reference", Dokumentnummer SC26-4346-3, IBM Corporation, im einzelnen beschrieben.
• Ein wesentlicher Vorteil eines relationalen Datenbanksystems ist, daß die Datenbank unabhängig vom Benutzer Eingaben erhält, anstatt eine ausdrückliche Operation durch Benutzersteuerung durchzuführen, wodurch die Leistung des Datenabrufs erhöht wird. Der Benutzer muß lediglich den Informationstyp angeben, den er von der Datenbank abrufen möchte. Wenn ein Benutzer beispielsweise Informationen aus zwei unterschiedlichen Datentabellen will, stellt ein relationales Datenbanksystem fest, wie die Informationen am besten aus beiden Tabellen zu holen sind.
• In den vor den relationalen Datenbanksystemen üblichen Datenbanksystemen steuerte der Programmierer, wie die Informationen abgerufen werden. Bei einem relationalen Datenbanksystem entscheidet das System über die Art des Datenabrufs.
• In vielen Datenbankverarbeitungssystemen ist die Sortierfunktion ein wichtiger Bestandteil des Systems. In einigen Fällen wird die Hälfte der Rechnerleistung eines Datenbankverarbeitungssystems nur für die Sortierfunktion verwendet. Bei einer relationalen Datenbank verwendet der Benutzer einen Sortierbefehl, wenn er die Ausgabe nach einem bestimmten Muster geordnet haben will. Daneben gibt es einen internen Sortiervorgang, der vom Datenbanksystem eingesetzt wird, wenn das System entscheidet, daß eine Sortierfunktion zum Abrufen von Informationen für einen Benutzer benötigt wird. Ein relationales Datenbanksystem verwendet zum Beispiel dann einen Sortiervorgang, wenn zwei Tabellen wirksamer miteinander verbunden werden sollen.
• Eine Sortierfunktion ist eine teure Funktion in einem Verarbeitungssystem, da viel Verarbeitungszeit benötigt wird, um die zum Sortieren erforderlichen Vergleichsbefehle durchzuführen. Wenn darüber hinaus zahlreiche Daten sortiert werden sollen, schreibt das Datenbanksystem einen Teil der zu sortierenden Daten auf Diskette oder Festplatte. Dieser Datenteil wird rückgelesen und weiter sortiert.
• Wenn sämtliche zu sortierenden Daten auf einmal im Speicher der CPU gespeichert werden können, ist eine externe Sortierung mit Hilfe einer I/O-Operation nicht notwendig. Wenn nicht alle Daten auf einmal im Speicher der CPU gespeichert werden können, wird ein Teil der Daten sortiert, das Ergebnis auf Platte gespeichert, und ein Teil der sortierten Daten auf einer Festplatte wird in den Speicher zurückgelesen, um mit einem anderen Teil unsortierter Daten weiter sortiert zu werden.
• Das Schreiben und Rücklesen von einer Platte kann während einer Sortieroperation häufig auftreten. Die zur Durchführung einer I/O-Operation benötigte Zeit kann bei einer Sortieroperation sehr kostspielig sein.
• Die Sortierzeitleistung ist aus verschiedenen Gründen ein wichtiges Wettbewerbsargument von relationalen Datenbankprodukten. Erstens ist der Sortiervorgang eine der häufigsten Operationen in einem relationalen Datenbanksystem. Zweitens machen sich Verbesserungen der Abfrageleistung, z.B. bei Abfragen, die eine Sortieroperation verwenden, für den Endbenutzer sehr schnell anhand der Zeit bemerkbar, die er auf das Ergebnis der Abfrage warten muß. Die Sortierleistung einer relationalen Datenbank ist daher ein wichtiger Wettbewerbseckwert von Datenbankprodukten.
• Nähere Einzelheiten über relationale Datenbanken und die SQL- Sprache finden sich auch in folgender Veröffentlichung: Date, C.J. An Introduction to Database Systems, The Systems Programming Series, Volume 1, Fourth Edition, Addison-Wesley Publishing Company, 1986.
• In 11th Annual International Symposium on Computer Architecture, 5 June 1984, Ann Arbor, USA, Seiten 134-141 wird ein Datenbanksystem und insbesondere eine Architektur für die Verarbeitung von SQL-Abfragen vorgestellt. In diesem Zusammenhang werden Platten-I/O verringert, um die Abfrage zu verbessern. Die Verwendung verschiedener Modi wird nicht beschrieben, d.h. die Weiterleitung des Ergebnisses zum Benutzer oder in den Speicher.
• In l2th Annual International Symposium on Computer Architecture, 17 June 1985, Boston, USA, Seiten 250-257 wird eine dieser Erfindung am nächsten kommende herkömmliche Technik beschrieben, nämlich ein Datenbanksystem mit einem Sortierer und einem Mischer. Ergebnisse, die noch benötigt werden, kommen über den Speicher automatisch in den Prozeß.
• Die vorliegende Erfindung stellt ein Verfahren zur Verarbeitung einer Abfrageanweisung in einer relationalen Datenbank vor, um ein sortiertes Abfrageergebnis zu erhalten, wobei das Verfahren die Durchführungsschritte einer Sortieroperation umfaßt, das dadurch gekennzeichnet ist, daß die Sortieroperation folgende Schritte beinhaltet: die Ordnung zahlreicher Reihen in der relationalen Datenbank in zahlreiche geordnete Folgezeichenketten; und das Mischen der geordneten Folgezeichenketten in zahlreiche gemischte Folgezeichenketten während mindestens eines Zwischenmischdurchlaufs; und wobei das Verfahren weiterhin folgende Schritte umfaßt: die Erstellung eines Plans durch einen Datenbankmanager zur Verarbeitung der Abfrageanweisung; die Festlegung eines ersten Modus durch den Datenbankmanager zur Weiterleitung einer Sortierausgabe der Sortieroperation, wenn die Ausgabe weniger oder gleich oft wie eine festgelegte Anzahl von Zeiten verwendet wird, und eines zweiten Modus zur Weiterleitung einer Sortierausgabe der Sortieroperation, wenn die Ausgabe öfter als die festgelegte Anzahl von Zeiten verwendet wird, wobei in diesem ersten Modus zahlreiche endgültig sortierte Reihen, die sich aus einem endgültigen Mischdurchlauf der gemischten Folgezeichenketten bei der Ordnung der endgültig sortierten Reihen ergeben haben, sequentiell und direkt an den Benutzer einer relationalen Datenbank weitergeleitet werden, und im zweiten Modus die endgültig sortierten Reihen auf Platte geschrieben werden.
• Die vorliegende Erfindung stellt des weiteren ein Gegenstück in Form eines Durchführungssystems dieses Verfahrens vor.
• Beim Sortieren zahlreicher Daten, z.B. von mehr Daten als im Speicher der CPU gleichzeitig gespeichert werden können, wird nur die Datenmenge verwendet, die im Speicher gespeichert werden kann und die anschließend auf einer Festplatte gespeichert wird. Auf Platte wird die Datenmenge gewöhnlich in sortierter Reihenfolge gespeichert. Im Speicher der CPU wird als nächstes eine weitere Datengruppe gespeichert, sortiert und auf Platte gespeichert. Dieser Vorgang wird wiederholt, bis alle Daten separat gruppiert, sortiert und getrennt auf Platte gespeichert wurden.
• Die Gruppen sortierter Daten auf Platte werden anschließend gemischt. Ein erster Teil aller Gruppen wird zusammengebracht, sortiert und wieder auf Platte gespeichert. Dieser Vorgang wird wiederholt, so daß die restlichen Teile der Datengruppen zusammen sortiert und auf Platte zurückgespeichert werden.
• Diese Vorgehensweise erhöht die Leistung einer relationalen Datenbank aus Sicht des Benutzers, da die I/O-Operationen zum Ausschreiben der endgültig sortierten Daten von Platte wegfallen. Die Ergebnisse der sortierten Daten werden dem Benutzer stattdessen in der endgültigen Sortierreihenfolge der Daten vorgestellt. Der Zusatzaufwand für das Schreiben der endgültig sortierten Daten auf Platte und das Zurücklesen in den Speicher entfällt. Da die geordneten Daten zum Anforderer in der Form, wie sie ursprünglich geordnet wurden, weitergeleitet werden, muß der Anforderer nicht warten, bis der gesamte Datensatz geordnet ist.
• Ein Sortierservice, der Teil eines relationalen Datenbankmanagers mit dieser Technik ist, ermöglicht es, Datenreihen zu empfangen und diese in der angeforderten steigenden oder fallenden Reihenfolge zu ordnen. Ein Sortiervorgang besteht aus zwei Hauptteilen. Zuerst kommt die Einfügephase, wo die Datenreihen vom relationalen Datenbankservice (RDS) empfangen und in geordnete Folgezeichenketten plaziert werden. Als nächstes kommt die Mischphase, die nach dem Empfang sämtlicher Datenreihen erfolgt. In der Mischphase werden die Folgezeichenketten zu einer Zeichenkette geordneter Daten zusammengemischt. Vorangegangene Datenbankverwaltungssysteme speicherten diese endgültige Datenzeichenkette in einer temporären Datei auf Platte. Das Schreiben auf Platte wird in der weiteren Beschreibung als Plattenausgabemodus bezeichnet. In der vorliegenden Anordnung kann der relationale Datenbankservice diese Daten nach Bedarf in einem schnellen direkten Ausgabemodus lesen.
• Eine Optimierungsroutine legt fest, welcher Modus, d.h. Plattenausgabemodus oder schneller Direktausgabemodus, am geeignesten für eine gegebene Abfrageanweisung ist. Der ausgewählte Modus hängt davon ab, ob die Abfrageanweisung die sortierten Daten nur einmal oder häufig verwendet.
• In den Fällen einiger SQL-Operationen, wie Order By (Sortiere nach), Group By (Gruppiere nach) oder den Außendurchlauf eines Merge/Join (Mischen/Verbinden), ist der Direktausgabemodus wirksamer als der Plattenausgabemodus, da viel Aufwand der Mischphase entfällt. Die Einfügephase bleibt gleich, unabhängig davon, ob die Ausgabe eine Ausgabedatei sein wird oder direkt zum relationalen Datenservice geht.
• Zu Beginn der Mischphase prüft der Sortierservice, ob die Optimierungsroutine des relationalen Datenbankservice anzeigte, daß die endgültig sortierten Daten nicht in Form einer geordneten, temporären Datei auf Platte gespeichert werden müssen. Wenn die Daten nicht auf Platte gespeichert werden müssen, fährt der Sortierservice mit dem Mischen fort, bis der endgültige Durchlauf erreicht ist.
• Der endgültige Durchlauf wird erkannt, indem die Anzahl der verbleibenden Folgezeichenketten mit der Anzahl der Mischpuffer verglichen wird. Wenn die Anzahl der Mischpuffer gleich oder größer als die Anzahl der Folgezeichenketten ist, handelt es sich um den letzten Durchlauf. Das bedeutet, daß jede von den oberen Einträgen aller Folgezeichenketten ausgewählte Reihe der nächste Eintrag in der endgültigen Sortierausgabe ist. Wenn der Sortierservice erkennt, daß er für den Beginn des endgültigen Mischdurchlaufs bereit ist und eine schnelle Direktausgabe durchführt, kehrt er zum relationalen Datenbankservice zurück und zeigt an, daß er zur Annahme der Sortierzugriffe vom relationalen Datenbankservice bereit ist. Wenn der relationale Datenbankservice einen Sortierzugriff durchführt, wählt der Sortierservice die richtige nächste Reihe von den verbleibenden Folgezeichenketten aus und meldet sie zum relationalen Datenbankservice zurück. Dieser Prozeß wird wiederholt, bis alle Reihen zum relationalen Datenbankservice zurückgemeldet sind.
• Im folgenden wird ein Ausführungsbeispiel der Erfindung vorgestellt, das ein Mittel in einem relationalen Datenbankmanager zur Festlegung eines ersten oder zweiten Modus für die Weiterleitung einer endgültigen Sortierausgabe der Sortieroperation und zwar durch Analyse einer Abfrageanweisung und/oder der Ausführung davon enthält; sowie ein Mittel zur Gliederung zahlreicher Reihen in einer relationalen Datenbank in zahlreiche geordnete Folgezeichenketten; ein Mittel zum Mischen der geordneten Folgezeichenketten in zahlreiche gemischte Folgezeichenketten während mindestens eines Zwischenmischdurchlaufs; ein Mittel zur sequentiellen Auswahl einer der Reihen aus einem oberen Eintrag jeder gemischten Folgezeichenkette als nächsten Eintrag in einer endgültig geordneten Zeichenkette während eines endgültigen Mischdurchlaufs; ein Mittel zur sequentiellen Rückmeldung der Reihe, die als nächster Eintrag in der endgültig geordneten Zeichenkette ausgewählt wurde, an den Benutzer im ersten Modus; und ein Mittel zum Schreiben der endgültig geordneten Zeichenkette auf Platte im zweiten Modus zusammen mit dem Gegenverfahren.
• Bei diesem System und diesem Verfahren gibt es zwei Hauptbereiche, in denen die Leistung verbessert wird. Zuerst einmal wird die End-to-End-Sortierzeit insgesamt reduziert, indem das Schreiben und Lesen aller sortierten Daten auf Platte vermieden wird. Zweitens wird die Reaktionszeit für jede sortierte Reihe verbessert, da die Datensätze über den relationalen Datenbankservice dem Benutzer zurückgemeldet werden, wenn sie sich in der endgültigen Sortierordnung befinden, und nicht gewartet wird, bis alle Datensätze sortiert sind, bevor sie über den relationalen Datenservice zum Benutzer zurückgemeldet werden.
• Die vorliegende Erfindung wird im folgenden anhand eines Ausführungsbeispiels mit Begleitzeichnungen beschrieben.
• Die Figuren 1A und 1B sind allgemeine Ansichten des relationalen Datenbankverarbeitungssystems der Erfindung.
• Die Figuren 2A und 2B zeigen Beispieltabellen zur Benutzung in der relationalen Datenbank.
• Fig. 3 ist ein Fließdiagramm der gesamten Datenbankoperation.
• Fig. 4 ist ein Fließdiagramm der Sortiereinfügephase.
• Fig. 5 ist ein Fließdiagramm der Sortieröffnungsphase.
• Fig. 6 ist ein Fließdiagramm der Sortierholphase.
• Fig. 7 ist ein Fließdiagramm des Optimierers zur Bestimmung des Ausgabemodus.
• Fig. 8 zeigt die Daten in internen Puffern im Speicher und die sich ergebenden zahlreichen Folgezeichenketten auf Platte.
• Fig. 9 zeigt das Mischen zahlreicher Folgezeichenketten zu einer endgültig sortieren Zeichenkette für die Platte oder einen Benutzer über einen relationalen Datenbankservice, je nach Ausgabemodus.
• Wir beginnen mit dem Blockdiagramm der Figuren 1A und 1B, die eine allgemeine Ansicht der Verarbeitungsvorrichtung zeigen, welche zur Ausführung der vorliegenden Erfindung verwendet werden kann.
• Fig. 1A zeigt eine typische Personal-Computer-Architektur, wie beispielsweise die beim IBM Personal System/2 verwendete Konfiguration. Das Herzstück der Architektur ist ein Mikroprozessor 1, bei dem es sich z.B. um einen Intel 80286 oder 80386 oder ähnlichen Mikroprozessor handeln kann. Der Mikroprozessor 1 ist mit einem Bus 2 verbunden, der über eine Reihe von Datenleitungen, eine Reihe von Adreßleitungen und eine Reihe von Steuerleitungen verfügt. Über die separaten Adapter 9-14 sind zahlreiche I/O-Geräte, der Speicher oder die Speichereinrichtungen 3-8 mit dem Bus 2 verbunden. Die Anzeige 4 kann zum Beispiel der Farbbildschirm 8514 des IBM Personal System sein, bei dem der Adapter 10 in der Systemplatine enthalten ist. Die anderen Einrichtungen 3 sowie 5-8, die Adapter 9 sowie 11-14 sind entweder als Teil eines IBM Personal System/2 bereits vorhanden oder sind als Einsteckoptionen von der IBM Corporation erhältlich. Der Direktzugriffsspeicher 6 und der Nur-Lese-Speicher 7 sowie ihre entsprechenden Adapter 12 und 13 sind beispielsweise standardmäßig im IBM Personal System/2 enthalten, wobei über eine Einsteck-Speichererweiterungsoption noch ein zusätzlicher Direktzugriffsspeicher zur Ergänzung des Speichers 6 hinzugefügt werden kann.
• Im Nur-Lese-Speicher 7 sind zahlreiche Befehle gespeichert, die als grundlegendes Ein-/Ausgabesystem oder BIOS bekannt sind und vom Mikroprozessor 1 ausgeführt werden. Das BIOS steuert die Hauptfunktionen des Computers. Ein Betriebssystem 15, z.B. OS/2, wird in den Speicher 6 geladen und läuft zusammen mit dem im ROM 7 gespeicherten BIOS. Fachleuten ist ersichtlich, daß das Personal-Computer-System so konfiguriert werden kann, daß das BIOS ganz oder teilweise anstatt im ROM 7 im Speicher 6 gespeichert wird, um die grundlegenden Systemoperationen durch Modifizierungen im BIOS-Programm zu ändern, die dann einfach in den Direktzugriffsspeicher 6 geladen werden.
• Für weitere Informationen über das Personal System/2 und das Betriebssystem OS/2 werden folgende Veröffentlichungen vorgeschlagen: Technical Reference Manual, Personal System/2 (Model 50, 60 systems), IBM Corporation, part number 68X2224, order number S68X2224. Technical Reference Manual, Personal System/2 (Model 80), IBM Corporation, part number 68X2256, order number S68X-2256. IBM Operating System/2 version 1.0 Standard Edition Technical Reference, IBM Corporation, part number 6280201, order number 5871-AAA. Iacobucci, Ed, OS/2 Programmer's Guide, McGraw Hill, 1988.
• Bei der Vorrichtung der Erfindung kann auch ein Anwendungsprogramm 18, z.B. ein relationaler Datenbankmanager 20, in den Speicher 6 geladen werden oder sich auf den Medien 5 befinden. Die Medien 5 können eine Diskette oder eine Festplatte umfassen, müssen jedoch nicht darauf beschränkt sein. Der relationale Datenbankmanager 20 kann auch als Erweiterung des Betriebssystems 15 angesehen werden. Der relationale Datenbankmanager 20 umfaßt eine Reihe von relationalen Datenbankmanager-Aufgaben, zu der eine Sortieraufgabe 23, eine relationale Datenbankservice-Aufgabe 25 und eine Optimiereraufgabe 27 gehört, jedoch nicht darauf beschränkt ist. Die relationalen Datenbankmanager-Aufgaben senden dem Mikroprozessor 1 Befehle, damit das in den Figuren 1A und 1B gezeigte Verarbeitungssystem relationale Datenbankfunktionen ausführen kann. Ein in den Speicher 6 geladenes Anwendungsprogramm 18 läuft zusammen mit dem zuvor in den Speicher 6 geladenen Betriebssystem.
• Bei dem Verarbeitungssystem der Figuren 1A und 1B greift der Benutzer 19 über die Benutzersteuertasten auf der Tastatur 3 auf den relationalen Datenbankmanager 20 zu. Die Tastatur treibt den Prozessor 1, der über den Bus 2 mit der Anzeige 4 sowie mit dem Medienspeicher 5 und dem Speicher 6 verbunden ist. Wenn der Benutzer über die Tastatur 3 mit dem relationalen Datenbankmanager 20 interagiert, werden dem Benutzer der relationale Datenbankmanager 20 und seine Daten über die Anzeige 4 angezeigt. Zusätzlich zu einem Benutzer, der mit dem relationalen Datenbankmanager 20 kommuniziert, kann auch eine Anwendung 18 über SQL-Befehle in der Anwendung 18 mit dem Datenbankmanager 20 in Interaktion treten.
• Die vorliegende Erfindung wird anhand der in den Figuren 2A und 2B gezeigten Datenbanktabellen beschrieben. In SQL-Sprache würde die Datenbanktabelle 22, Fig. 2A, von einem Benutzer wie folgt beschrieben:
• CREATE TABLE STAFF
• ( ID INTEGER,
• NAME VARCHAR(10))
• CREATE TABLE ist ein Beispiel für eine SQL-Datendefinitionsanweisung. Jede CREATE TABLE-Anweisung nennt den Namen 24 der zu erzeugenden Tabelle 22, die Namen ihrer Spalten 26 und 28 sowie die Datentypen dieser Spalten. Wenn der Benutzer die CREATE TABLE-Anweisung ausführt, ist die Tabelle zu Beginn leer, d.h. die Tabelle enthält beispielsweise keine Datenreihen 202. Der Benutzer kann jedoch die Datenreihen 202 sofort mit der SQL- INSERT-Anweisung einfügen, um die Tabelle von Fig. 2A zu erhalten. Der Benutzer kann nun mit dieser Tabelle und zusammen mit anderen Tabellen, die erzeugt wurden (siehe Fig. 2B), sinnvolle Operationen durchführen. Der Benutzer könnte beispielsweise die Daten in der Tabelle 22 nach ID-Nummern ordnen, er könnte die Tabelle 22 mit einer anderen Tabelle verbinden, z.B. mit Tabelle 21, die ähnliche Gehälter für jede ID-Nummer aufweist, oder eine GROUP BY- Operation durchführen, wie die Auswahl der höchsten Gehälter und die Gruppierung nach Abteilung. Wenn die Operation MERGE JOIN verwendet wird, um zahlreiche Tabellen jeweils in Paaren miteinander zu verbinden, führt der relationale Datenbankmanager eine Sortieroperation durch, wenn keine Indexe vorhanden sind, um die Reihen sequentiell von den Tabellen zu ordnen.
• Bei Fig. 3 gibt der Benutzer 19 oder eine Anwendung 18 die Anweisung für die gewünschte Operation ein (Schritt 31). Der Benutzer/die Anwendung kann zum Beispiel folgende Anweisung eingeben: SELECT * FROM STAFF ORDER BY ID. Der Befehl SELECT * wird verwendet, um sämtliche Spalten einer Reihe zu erhalten.
• Der Optimierer 27 (Figuren 1A, 1B) legt dann den Ausgabemodus für die vom Benutzer/der Anwendung eingegebene Operationsanweisung fest (Schritt 32, Fig. 3). Der Standardmodus ist der Plattenausgabemodus (Schritt 34), der für bestimmte Sortierpläne von der Optimiererroutine 32 auf schnellen Direktausgabemodus geändert werden kann. Der Optimierer 27 ist ein Bestandteil des relationalen Datenbankservice 25, der festlegt, welches Datenzugriffsverfahren, z.B. Plan, für eine bestimmte Abfrageanweisung angewendet werden soll. Er bestimmt beispielsweise, ob ein Index oder eine sequentielle Abfrage verwendet werden soll, oder ob eine Sortieroperation durchgeführt werden soll. Die Optimiererroutine (Schritt 32, Fig. 3) wird in Fig. 7 noch näher gezeigt und erläutert; es handelt sich dabei um eine Routine, die aufgerufen wird, nachdem der Optimierer 27 alle zur Verarbeitung einer Abfrageanweisung benötigten Pläne erzeugt hat. Ein Plan ist eine Operation bei einer Tabelle, wie z.B. ein Tabellenzugriff oder eine Verbindung, die zur Erzeugung eines Abfrageergebnisses verwendet wird. Ein Verbindungsplan hat beispielsweise zwei Eingabepläne: einen für die äußere Tabelle und einen für die innere Tabelle. Es wird zuerst auf die äußere Tabelle zugegriffen, wobei übereinstimmende Reihen der inneren Tabelle mit jeder Reihe der äußeren Tabelle verbunden werden. Die Optimiererroutine 32 wird für jeden Plan der Abfrage aufgerufen. Wenn Sortierpläne zuerst erzeugt werden, haben sie die Plattenausgabeoption. Die folgende Optimiererroutine 32 kann die Plattenausgabeoption bestimmter Sortierpläne auf die schnelle Direktausgabeoption ändern.
• Die Optimiererroutine 32 (Fig. 7) stellt zuerst fest, ob es sich bei dem Plan um einen Tabellenzugriffsplan handelt (Schritt 121, Fig. 7). Ein Tabellenzugriffsplan ist eine Anforderung, die Reihen einer Tabelle nacheinander zu lesen. Wenn der Plan ein Tabellenzugriffsplan ist, bestimmt Schritt 23, ob der Plan der Stammplan einer Abfrage ist. Ein Stammplan erzeugt das Endergebnis der Abfrage. Ist dies nicht der Fall, kehrt die Routine wieder zurück, ohne die schnelle Direktausgabe zu aktivieren. Ist dies der Fall, bestimmt Schritt 125, ob der Tabellenzugriffsplan einen Sortiereingabeplan hat. Wenn ja, wird der Sortierplan für die schnelle Direktausgabe aktiviert (Schritt 127). Andernfalls wird die schnelle Direktausgabe nicht aktiviert, und die Routine endet.
• Wenn der Plan laut Feststellung von Schritt 121 kein Tabellenzugriffsplan ist, bestimmt Schritt 129, ob der Plan ein Verbindungsplan ist. Bei einem Verbindungsplan wird auf zwei Tabellen zugegriffen und diese werden verbunden. Handelt es sich nicht um einen Verbindungsplan, wird die schnelle Direktausgabe nicht aktiviert, und die Routine endet. Handelt es sich dagegen um einen Verbindungsplan, legt Schritt 131 fest, ob der äußere Plan des Verbindungsplans ein Tabellenzugriffsplan ist. Ist dies nicht der Fall, wird die schnelle Direktausgabe nicht aktiviert und die Routine endet. Ist dies der Fall, legt Schritt 133 fest, ob der Tabellenzugriffsplan einen Eingabesortierplan hat. Wenn ja, wird die schnelle Direktausgabe für diesen Sortierplan aktiviert, und die Routine endet. Andernfalls wird die schnelle Direktausgabe nicht aktiviert, und die Routine endet.
• Zurück zu Fig. 3: Nachdem der Benutzer/die Anwendung die Abfrageanweisung eingegeben hat (Schritt 31), und der Optimierer den passenden Ausgabemodus für diese Operation bestimmt hat (Schritt 32), holt der relationale Datenbankservice 25 des relationalen Datenbankmanagers 20 jeweils eine Reihe 211-218 aus der Tabelle 22 (Fig. 2A), die auf Platte 5 gespeichert ist (Schritt 33, Fig. 3). Bei mehreren Abfrageanweisungen, einschließlich der ORDER BY-Anweisung, muß der relationale Datenbankmanager (Fig. 1A, 1B) eine Sortieroperation durchführen, um die Datenreihen 202 (Fig. 2A) in der angeforderten Reihenfolge zu erhalten.
• Aus dem Fließdiagramm von Fig. 3 geht hervor, daß die Sortierfunktion 23 aus drei Hauptphasen besteht. In der Einfügephase 41 werden die Reihen von der Sortierfunktion 23 in unbekannter Reihenfolge empfangen. Die Einfügephase 41 wird im weiteren Verlauf anhand von Fig. 4 noch näher beschrieben. In der Öffnungsphase 45 der Sortierfunktion 23 bereitet die Sortierfunktion 23 die Daten zur Rückmeldung in sortierter Reihenfolge vor. Die Öffnungsphase 45 wird im weiteren Verlauf anhand von Fig. 5 noch näher beschrieben. In der Holphase 51 der Sortierfunktion 23 werden die Daten über den relationalen Datenbankservice 25 in sortierter Reihenfolge zum Anforderer rückgemeldet. Die Holphase wird im weiteren Verlauf anhand von Figur 6 noch näher erläutert.
• Wenn der relationale Datenbankservice 25 eine Reihe 211 aus der Tabelle 22 empfängt (Schritt 33, Fig. 3), leitet der relationale Datenbankservice 25 diese Reihe 211 in der Sortiereinfügephase zur Sortierfunktion 23 weiter (Schritt 41). Während der Sortiereinfügephase empfängt der relationale Datenbankserviceteil 25 des Datenbankmanagers 20 Datenreihen. Die Daten gehen ungeordnet ein, und es gibt keinen Hinweis, wieviele Daten empfangen werden.
• Die Sortiereinfügephase wird anhand von Fig. 4 und Fig. 8 noch näher beschrieben. Die Sortierfunktion empfängt während der Sortiereinfügephase 41 eine Datenreihe bei jeder Anforderung vom relationalen Datenbankservice 25. Bei Schritt 61 wird geprüft, ob in den internen Puffern 62 genügend Platz für die Daten vorhanden ist. Wenn Platz vorhanden ist, setzt die Sortierfunktion 23 die Daten 211-218 (Fig. 2A) in sequentieller Reihenfolge, so wie sie empfangen werden, in die internen Puffer 62 (Fig. 8) (Schritt 65, Fig. 4). Die Sortierfunktion 23 erzeugt einen Eintrag für einen ausgeglichenen Binärbaum 64, um auf die Datenreihe im Puffer 62 zu zeigen (Schritt 67). Der Binärbaum wird dazu verwendet, die sortierte Reihenfolge der Daten mitzuverfolgen.
• Wenn die internen Puffer 62 belegt sind (Schritt 61), werden die Daten als geordnete Folgezeichenkette 66 (Fig. 8) auf Platte geschrieben (Schritt 63, Fig. 4), und zwar von allen Daten sämtlicher Puffer 62 zusammen. Werden weitere Reihen vom relationalen Datenbankservice 25 empfangen, werden die internen Puffer 62 erneut gefüllt, und der Prozeß wird so oft wie nötig wiederholt, um sämtliche empfangenen Daten zu verarbeiten. Wenn die internen Puffer 62 auf Platte 5 geschrieben werden (Schritt 63, Fig. 4), wird jedesmal eine neue Folgezeichenkette 66 sämtlicher Daten aus allen neu gefüllten Puffern 62 gebildet.
• Wenn in Fig. 3 alle Reihen aus der Tabelle vom relationalen Datenbankservice 25 geholt und zur Sortiereinfügephase gesendet werden (Schritt 37), signalisiert der relationale Datenbankservice 25 das Ende der zu sortierenden Daten (Schritt 43). Die zweite Phase der Sortierfunktion 23, nämlich Sortieröffnen 45, wird durch eine Anforderung vom relationalen Datenbankservice 25 aufgerufen und zeigt an, daß keine weiteren Datenreihen zur Sortierfunktion 23 weitergeleitet werden.
• Diese Anordnung ermöglicht es, daß die sortierten Reihen in einem von zwei Modi zum relationalen Datenbankservice 25 zurückgesendet werden. Ein Modus, der Plattenausgabemodus, führt dazu, daß alle sortierten Daten in Form einer geordneten temporären Datei auf die Platte geschrieben werden. Im anderen Modus, der als schneller Direktausgabemodus bezeichnet wird, da jede Reihe in die endgültig sortierte Reihenfolge gesetzt wird, können die Daten auf Anforderung direkt über den relationalen Datenbankservice 25 zum Benutzer/zur Anwendung zurückgesendet werden. Jedes Verfahren hat Leistungsvorteile, die von der Verwendung der Ergebnisse abhängen. Wenn die sortierten Daten nur einmal verwendet werden (laut Feststellung der Optimiererroutine 32 in Fig. 7), ist es am besten, sie direkt zurückzuschicken, um keine Zeit zum Schreiben der Daten in eine Datei und zum späteren Abrufen zu vergeuden. Wenn die Daten jedoch mehr als einmal verwendet werden sollen, ist es am besten, sie auf Platte zu schreiben, so daß sie nur einmal vor der Verwendung sortiert werden. Wenn die Optimiererroutine 32 in Fig. 7 zum Beispiel feststellt, daß der Plan ein Stammplan ist, werden die Daten nur einmal verwendet, und der schnelle Direktausgabemodus wird aktiviert. Auch wenn die äußere Tabelle verbunden wird, werden die sortierten Daten nur einmal verwendet, und der schnelle Direktausgabemodus wird aktiviert. Ist dies nicht der Fall, wurde die innere Tabelle verbunden, d.h. die sortierten Daten werden mehr als einmal verwendet. In diesem Fall wurde der schnelle Direktausgabemodus nicht aktiviert.
• Der relationale Datenbankservice 25 kompiliert die SQL-Anweisungen, die die Sortierfunktion 23 benötigen, zuvor. Der relationale Datenbankservice 25 durchläuft einen Entscheidungsprozeß, um festzustellen, ob es besser ist, die Daten direkt zum relationalen Datenbankservice 25 zurückzuschicken oder sie auf Platte zu schreiben. Der entscheidende Faktor dabei ist, ob die Daten nur einmal oder mehrfach genutzt werden. Der relationale Datenbankservice 25 erkennt dies, indem er den angeforderten Operationstyp prüft. Wenn allgemein eine ORDER BY- oder GROUP BY-Operation angefordert wird, kann die direkte Rückmeldung der Daten zum relationalen Datenbankservice 25 implementiert werden. Bei einer MERGE/JOIN-Operation hängt der Ausgabemodus vom verarbeiteten Datenteil ab. Wenn ein äußerer Durchlauf eines MERGE/JOIN durchgeführt wird, kann der Direktausgabemodus für eine bessere Leistung verwendet werden. Bei allen anderen, während einer MERGE/JOIN-Operation benötigten Sortierungen ist der Plattenausgabemodus vorzuziehen. Der Optimierer 27 des relationalen Datenbankservice 25 wählt das beste Verfahren für die Sortierausgabe aus, ohne dabei die Maßnahme des Benutzers/der Anwendung im einzelnen zu kennen.
• Die Sortierausgabephase 45 wird im folgenden anhand der Figuren 5, 8 und 9 beschrieben. Wenn der Optimierer 27 des relationalen Datenbankservice 25 den Plattenausgabemodus auswählt, werden folgende Schritte durchgeführt.
• Zuerst schreibt die Sortierfunktion 23 sämtliche restlichen Daten in den internen Puffern 62 (Fig. 8) als geordnete Folgezeichenkette 66 auf die Platte 5 (Schritt 77). Wenn nur eine Folgezeichenkette auf der Platte ist (Schritt 84), befinden sich die Daten in ihrer endgültigen Sortierreihenfolge. Die Sortierfunktion 23 liest anschließend die erste Seite der Folgezeichenkette 66 (Schritt 89). Die Sortieröffnungsphase 45 ist damit abgeschlossen. Wenn mehrere Folgezeichenketten auf Platte sind, muß die Sortierfunktion 23 diese in einer Mischoperation zu einer einzigen Folgezeichenkette zusammenfassen (Schritt 81). Bei der Mischoperation (Fig. 9) werden die oberen Reihen 221 jeder Folgezeichenkette 66 verglichen, die nächste Reihe in der gesamten geordneten Folge von den Folgezeichenketten ausgewählt und in die gemischte Folgezeichenkette 68 gesetzt. Dieser Prozeß wird fortgesetzt, bis nur noch eine letzte Folgezeichenkette 68 mit allen sortierten Daten auf Platte ist.
• Während des Plattenausgabemodus von Fig. 3 wird die dritte Phase der Sortierfunktion 23, die Holphase 51, vom relationalen Datenbankservice aufgerufen, nachdem die Einfügephase 41 und die Öffnungsphase 45 beendet sind. Die Holphase 51 bedeutet, daß der relationale Datenbankservice eine Holanforderung für jede Reihe der sortierten Daten ausgibt (Schritt 44). Als Reaktion auf jede Holoperation ruft die Sortierfunktion 23 eine Datenreihe von der letzten Folgezeichenkette auf Platte ab und leitet sie zum relationalen Datenbankservice weiter.
• Der oben beschriebene Plattenausgabemodus wird dann verwendet, wenn die sortierten Daten wiederholt genutzt werden sollen. In diesem Fall wird der schnelle Direktausgabemodus nicht aktiviert, und die Sortierfunktion 23 arbeitet wie oben beschrieben. Der schnelle Direktausgabemodus wird in den Fällen aktiviert, in denen der relationale Datenbankservice 25 nur einmal auf die sortierten Daten zugreift. Der relationale Datenbankservice aktiviert den schnellen Direktausgabemodus für die SQL-Operationen, wie zum Beispiel ORDER BY und GROUP BY, oder den äußeren Durchlauf eines MERGE/JOIN.
• Während des Direktausgabemodus verfügt die Sortierfunktion 23 über dieselben drei Phasen wie oben beschrieben. Die Einfügephase 41 (Fig. 4) wird auf dieselbe Art und Weise verwendet, unabhängig davon, ob Plattenausgabemodus oder Direktausgabemodus gewählt wird. Wenn der Direktausgabemodus gewählt wird, sind die Öffnungsphase 45 (Fig. 5) und die Holphase 51 (Fig. 6) anders.
• Wenn die Sortierfunktion 23 vom relationalen Datenbankservice 25 in Fig. 3 zum Öffnen aufgerufen wird (Schritt 41), wird das Datenende (Schritt 43) signalisiert und die Holoperation vorbereitet. In Fig. 5 prüft die Sortieröffnungsphase 45, ob der relationale Datenbankservice den schnellen Direktausgabemodus aktiviert hat (Schritt 73). Wenn der schnelle Direktausgabemodus aktiviert wurde, werden die endgültig sortierten Daten nicht in Form einer geordneten temporären Datei auf Platte gespeichert.
• Die Sortierfunktion 23 prüft, ob alle Daten sich im Speicher befinden (Schritt 71, Fig. 5). Wenn alle Daten im Speicher sind, erzeugt die Sortierfunktion 23 ein Zeigerfeld auf die Datenreihen in den Puffern (Schritt 75). Die Sortierfunktion 23 kehrt anschließend zum relationalen Datenbankservice 25 zurück und zeigt an, daß sie bereit ist, Sortierholoperationen vom relationalen Datenbankservice 25 anzunehmen (Schritt 91). Wenn mehr Daten als in den Speicher passen vorhanden sind, und der schnelle Direktausgabemodus gewählt wurde, durchläuft die Sortierfunktion wie oben beschrieben die Schritte 77, 79 und 81 (Fig. 5). Wenn mehrere Folgezeichenketten vorhanden sind, mischt die Sortierfunktion sie weiterhin, bis sie für den letzten Durchlauf bereit ist. Der letzte Durchlauf wird erkannt, indem die Anzahl der verbleibenden Folgezeichenketten mit der Anzahl der Mischpuffer verglichen wird (Schritt 79). Wenn die Anzahl der Mischpuffer gleich oder größer als die Anzahl der Folgezeichenketten ist, handelt es sich um den letzten Durchlauf. Danach ist jede von den oberen Einträgen aller Folgezeichenketten ausgewählte Reihe der nächste Eintrag in der letzten sortierten Ausgabe (Schritt 89). Wenn die Sortierfunktion erkennt, daß sie zum Start eines letzten Mischdurchlaufs bereit ist (oder nur ein oder kein Mischdurchlauf erforderlich war), kehrt sie zum relationalen Datenbankservice zurück und zeigt an, daß sie bereit ist, Sortierholoperationen vom relationalen Datenbankservice anzunehmen (Schritt 91).
• Nach der Beendigung des Öffnungsphasenschritts 45 in Fig. 3 kann der relationale Datenbankservice 25 sortierte Datenreihen von der Sortierfunktion 23 holen. Die Sortierholphase 51 wird im folgenden in Fig. 6 beschrieben. Wenn der relationale Datenbankservice eine Sortierholoperation anfordert, legt die Sortierholoperation jedesmal fest, ob eine nächste Reihe vorhanden ist (Schritt 101). Wenn keine nächste Reihe vorhanden ist, setzt die Sortierholoperation einen Datenendezeiger für den relationalen Datenbankservice (Schritt 103) und kehrt zum relationalen Datenbankservice zurück (Schritt 117). Wenn eine nächste Reihe vorhanden ist, und der schnelle Direktausgabemodus ausgewählt wurde, wird geprüft, ob die Daten von der Platte oder aus dem Speicher kommen (Schritt 107). Wenn sich alle Daten im Speicher befinden, wählt die Sortierholoperation die nächste Reihe von den Puffern und sendet die Reihe zum relationalen Datenbankservice zurück (Schritte 113, 115). Wenn die Daten von Folgezeichenketten auf Platte kommen, wählt die Sortierholphase die nächste Reihe vom oberen Teil aller Zeichenketten aus (Schritt 109). Siehe hierzu auch Fig. 9. Die Datenreihe wird dann zum relationalen Datenbankservice weitergeleitet (Schritt 115). Bei mehreren Folgezeichenketten sendet die Sortierfunktion mit Direktausgabe eine Datenreihe zurück, bevor die restlichen Reihen in einer geordneten Zeichenkette zusammengefaßt werden. Der relationale Datenbankservice setzt die Holanforderungen fort, bis alle Reihen zum relationalen Datenbankservice zurückgekehrt sind. Der relationale Datenbankservice kann erkennen, ob die Daten im schnellen Direktausgabemodus zurückgesendet wurden oder nicht.
• Diese Anordnung verringert die Kosten im Zusammenhang mit einem Sortiervorgang, und sendet sortierte Daten so schnell wie möglich zum Anforderer zurück. Zwei weitere Vorteile sind die geringere Belastung des Systems, die es noch für andere Funktionen verfügbar macht, und eine bessere Reaktionszeit sowie einen höheren Durchsatz für den Benutzer der Sortierfunktion.
• Beim schnellen Direktausgabeverfahren dieser Anordnung schreibt die Sortierfunktion die endgültig sortierten Daten nicht in eine temporäre Datei auf Platte, wie dies bei Datenbanksystemen herkömmlicher Technik der Fall war. Die Daten werden stattdessen direkt zum Anforderer zurückgesendet. Diese Technik wartet nicht, bis sich alle Daten in der endgültig sortierten Reihenfolge befinden, bevor sortierte Daten zum Anforderer zurückgemeldet werden. Wenn die Sortierfunktion bei diesem schnellen Direktausgabeverfahren feststellt, daß sie die Daten in der endgültig sortierten Reihenfolge erhält, leitet sie jede Reihe direkt zum Anforderer weiter, sobald die Reihe als nächste Reihe in der sortierten Folge ausgewählt wird.
• Diese Technik bringt mehrere Vorteile. Da die endgültig sortierten Daten nicht in eine temporäre Datei auf Platte geschrieben und anschließend auf Anforderung vom Benutzer zurückgelesen werden, verringert sich die Sortierzeit insgesamt. Da das Schreiben auf Platte und das Lesen wegfällt, ist das System weniger belastet und steht für andere Benutzer zur Verfügung. Ein weiterer Vorteil ist die Reaktionszeit für jede sortierte Reihe. Da die Reihen sofort zurückgemeldet werden, so wie sie in die endgültig sortierte Reihenfolge gesetzt werden, anstatt wie bisher alle Reihen zu sortieren, bevor sie zum Anforderer zurückgemeldet werden, wird die Reaktionszeit für jede sortierte Reihe verbessert. Wenn der Anforderer sortierte Daten zurückbekommt, können diese entweder direkt dem Benutzer angezeigt oder in einem anderen Schritt einer Operation verwendet werden. In jedem Fall ist eine Verbesserung der einzelnen Reaktionszeit nützlich.
• Obgleich in der Beschreibung oben verschiedene Aspekte der vorliegenden Erfindung im einzelnen vorgestellt und anhand bevorzugter Ausführungsbeispiele erläutert wurden, ist Fachleuten klar, daß andere Formänderungen vorgenommen werden können, ohne dadurch vom Anwendungsbereich der Ansprüche abzuweichen.

Claims (7)

1. Ein Verfahren zur Verarbeitung einer Abfrageanweisung in einer relationalen Datenbank, um ein sortiertes Abfrageergebnis zu erhalten, wobei das Verfahren folgende Schritte umfaßt:

die Durchführung (41, 45, 51) einer Sortieroperation;

und das Verfahren dadurch gekennzeichnet ist, daß die Sortieroperation folgende Schritte beinhaltet:

die Ordnung (67) zahlreicher Reihen in der relationalen Datenbank in zahlreiche geordnete Folgezeichenketten; und das Mischen (81, 85) der geordneten Folgezeichenketten in zahlreiche gemischte Folgezeichenketten während mindestens eines Zwischenmischdurchlaufs;

und das Verfahren weiterhin folgende Schritte umfaßt:

die Erzeugung eines Plans durch einen Datenbankmanager zur Verarbeitung der Abfrageanweisung;

die Bestimmung (32) durch den Datenbankmanager eines ersten Modus zum Weiterleiten einer Sortierausgabe der Sortieroperation, wenn die Ausgabe weniger oder gleich oft wie eine festgelegte Anzahl von Zeiten verwendet wird, oder eines zweiten Modus zum Weiterleiten einer Sortierausgabe der Sortieroperation, wenn die Ausgabe öfter als die festgelegte Anzahl von Zeiten verwendet wird;

die sequentielle und direkte Rückmeldung (53) zahlreicher endgültig sortierter Reihen, die sich aus einem endgültigen Mischdurchlauf der gemischten Folgezeichenketten bei der Ordnung jeder endgültig sortierten Reihe ergeben haben, und zwar im ersten Modus an einen Benutzer der relationalen Datenbank; und

das Schreiben (45, 51) der endgültig sortierten Reihen auf Platte im zweiten Modus.

2. Ein Verfahren nach Anspruch 1, bei dem die Anzahl der festgelegten Zeiten eins beträgt.

3. Ein Verfahren nach Anspruch 2, bei dem der Plan über einen Sortiereingabeplan zu einem Stammplan eines Tabellenzugriffsplans verfügt, oder der Plan über einen Sortiereingabeplan zu einem äußeren Plan eines Verbindungsplans verfügt.

4. Ein Verfahren nach Anspruch 1 oder Anspruch 2, bei dem der Datenbankmanager bestimmt, ob die Ausgabe öfter als die festgelegte Anzahl von Zeiten benutzt wird, indem er die Abfrageanweisung an sich analysiert.

5. Ein Verfahren nach Anspruch 4, bei dem der erste Modus gewählt wird, wenn die Abfrageanweisung eine ORDER BY-Anweisung oder eine GROUP BY-Anweisung ist.

6. Ein relationales Datenbanksystem zur Verarbeitung einer Abfrageanweisung, um ein sortiertes Abfrageergebnis zu erhalten, wobei das System folgendes umfaßt:

ein Mittel (23) zur Durchführung einer Sortieroperation;

und das System dadurch gekennzeichnet ist, daß das Mittel (23) zur Durchführung einer Sortieroperation folgendes beinhaltet:

ein Mittel (67) zur Ordnung zahlreicher Reihen in der relationalen Datenbank in zahlreiche geordnete Folgezeichenketten; und

Mittel (81, 85) zum Mischen der geordneten Folgezeichenketten in zahlreiche gemischte Folgezeichenketten während mindestens eines Zwischenmischdurchlaufs;

und das System weiterhin folgendes umfaßt:

ein Mittel (31) zur Erzeugung eines Plans zur Verarbeitung der Abfrageanweisung;

ein Mittel (32) zur Auswahl eines zu benutzenden ersten oder zweiten Ausgabemodus, wobei der erste Modus eine Sortierausgabe der Sortieroperation weiterleitet, wenn die Ausgabe weniger oder gleich oft wie eine festgelegte Anzahl von Zeiten verwendet wird, oder der zweite Modus eine Sortierausgabe der Sortieroperation weiterleitet, wenn die Ausgabe öfter als die festgelegte Anzahl von Zeiten verwendet wird;

ein Mittel (53), das auf die Auswahl des ersten Modus reagiert, um zahlreiche endgültig sortierte Reihen, die sich aus einem endgültigen Mischdurchlauf der gemischten Folgezeichenketten bei der Ordnung jeder endgültig sortierten Reihe ergeben haben, an einen Benutzer der relationalen Datenbank direkt und sequentiell zurückzumelden; und

Mittel (45, 51), die auf die Auswahl des zweiten Modus reagieren, um die endgültig sortierten Reihen auf Platte zu schreiben.

7. Ein System nach Anspruch 6, bei dem die Anzahl der festgelegten Zeiten eins beträgt.