Vorherige und nachfolgende ID ermitteln

Ein relativ häufig benötigtes Feature bei Webanwendungen sind Vor- und Zurück-Links. Ich meine aber nicht die Buttons vom Browser sondern wenn man beispielsweise eine beliebige Nachricht in einem Postfach aufgerufen hat, dann gibt es einen Link zur vor dieser Mail eingetroffenen Nachricht und einen für die darauffolgende. Das ist nicht nur bei einem Posteingang so, sondern man kann das überall wiederfinden: bei Online-Shops, Blogs, Foren – überall, wo ein zeitlicher (oder zumindest sequentieller) Bezug zwischen den einzelnen Seiten besteht. In diesem Beitrag soll es nun darum gehen, wie man die ID dieser beiden Datensätze (Vorgänger und Nachfolger) am effektivsten mit SQL selektieren kann.

Wir gehen davon aus, dass die ID eine AUTO_INCREMENT-Spalte vom Typ INT ist – wir können also mit Mathematik arbeiten.

Eines vorweg: Wir können natürlich nicht davon ausgehen, dass der Vorgänger einfach AKTUELLE_ID – 1 ist, das wär dann doch ein wenig zu einfach. Es werden ja immer mal wieder Datensätze gelöscht und so entstehen Lücken. Diese zu korrigieren (bei Löschen eines Datensatzes alle größeren IDs dekrementieren) ist zwar möglich aber recht aufwändig und unnötig. Wenn man es aber macht, erspart man sich natürlich sämtliche Überlegungen, die im Folgenden angestellt werden, da dann tatsächlich einfach -1 für den Vorgänger und +1 für den Nachfolger gerechnet werden müsste. Man bräuchte also die Datenbank gar nicht zu befragen.

Wir gehen jetzt aber von einer lückenhaften Datenbank aus. Damit ist gemeint, dass nicht alle Wertmöglichkeiten zwischen 1 und MAX(ID) belegt sind. Wenn wir also eine ID x haben, kann der Vorgänger mitunter x-1 sein, bei anderem x aber vielleicht auch x-3 oder noch weiter entfernt.

Nun kommen wir mal zur Praxis. Für diese Aufgabe gibt es wie immer mehrere Lösungsansätze. Diese sollen im Folgenden vorgestellt werden. Es soll erstmal nur für die Ermittlung des Vorgängers eine Abfrage gefunden werden. Die für den Nachfolger wird recht ähnlich.

SELECT ID 
FROM tabelle 
WHERE ID<".$aktuelle_ID." 
ORDER BY ID DESC 
LIMIT 1

Dieser Ansatz sucht erstmal alle Datensätze, die eine kleinere ID als der aktuelle Datensatz haben und sortiert anschließend. Der größte Wert wird dann zurückgegeben. Ich erläutere weiter unten, warum dieser Weg der effektivste ist.

Ein zweiter mir per Mail vorgeschlagener Weg ist dieser:

SELECT ID
FROM tabelle
WHERE ID-".$aktuelle_ID."<0
ORDER BY ID-".$aktuelle_ID." ASC
LIMIT 1

Bei dieser Variante werden ebenfalls zuerst alle Datensätze mit kleinerer ID selektiert, deisemal allerdings über die Pürfung, ob die Differenz zwischen ID und aktueller ID kleiner 0 ist. Von diesen muss dann der Wert gewählt werden, der den geringsten Abstand zur aktuellen ID hat.
Einfach die WHERE-Bedingung weglassen funktioniert übrigens nicht, auch nicht, wenn man nach ABS(ID-“.$aktuelle_ID.”) sortiert, da dann nicht zwingend ein Vorgänger herauskommen muss. Und wenn man LIMIT 2 anhängt hat man auch nicht zwingend einen Vorgänger und einen Nachfolger, sondern es kann vorkommen, dass man dann 2 Vorgänger oder 2 Nachfolger bekommt.

Warum nun ist die erste Variante die bessere?
Ganz einfach: Weil Sie kein Filesort benötigt, sondern den PK bzw. den zugehörigen Index nutzen kann. Das ist so, weil für Funktionen bzw. Berechnungen kein Index möglich ist.
Außerdem kann die zweite Variante nicht verwendet werden, wenn man die Spalte ID als UNSIGNED INT definiert hat. Ich war eben selbst ein wenig erstaunt, aber wenn man da in den negativen Bereich kommt schlägt er einfach um und subtrahiert den Rest von MAX_INT.

Aus Performancesicht gibt es dementsprechend riesige Unterschiede, weil für die erste Variante der Index sowohl für die WHERE-Bedingung als auch für das Sortieren benutzt werden kann.
Die erste Variante benötigt 0,0003 Sekunden, während die zweite Variante knapp unter einer Sekunde bleibt.

Wenn man nun Vorgänger und Nachfolger selektieren möchte, muss man das nicht mit 2 Abfragen machen, sondern kann die selektierten Mengen (Vorgänger-Menge und Nachfolger-Menge) durch UNION vereinigen.

(SELECT ID 
FROM tabelle 
WHERE ID<".$aktuelle_ID." 
ORDER BY ID DESC 
LIMIT 1) UNION (
SELECT ID 
FROM tabelle 
WHERE ID>".aktuelle_ID." 
ORDER BY ID ASC
LIMIT 1
)

Das dauert bei mir jetzt 0,06 Sekunden, deshalb ist es durchaus auch überlegenswert es mit 2 einzelnen Abfragen zu versuchen.

Also ich hoffe, dass ich die effizientere Variante aufzeigen konnte, als die die mir per Mail vorgestellt wurde. Also weiß ich, dass mindestens eine Person nun seine Scripte ändern wird 😉
Alle anderen, die eine solche Funktion benötigen, wissen nun auch, wie es am performantesten geht.

Jan hat 152 Beiträge geschrieben

31 Kommentare zu “Vorherige und nachfolgende ID ermitteln

  1. Andreas sagt:

    >>>>Diese zu korrigieren (bei Löschen eines Datensatzes alle größeren IDs dekrementieren) ist zwar möglich aber recht aufwändig und unnötig.

    Verzeihung, aber das ist natürlich Blödsinn. Normalerweise sind diese Auto Imkrement Felder Primary Keys und werden zur Verknüpfung zu anderen Tabellen verwendet. Dort müßte man dann die ensprechenen Einträge auch umnummerieren. Und das sollte man lassen.

    Ein Primary Key identifiert einen Satz eindeutig und sonst nix. Er ändert sich nie. Jede Ausnahme von dieser Regel, macht nur Ärger.

    Achso, auch wenn ich mich jetzt so drastisch zu Wort melde. Natürlich ist das sonst hier geschriebene interesannt und auch mal lehrreich, je nachdem was man schon weiß. Wäre dem nicht so, würde ich nicht kommentieren, sondern ignorieren 😉

  2. ChristianS sagt:

    Na, da hat die Blogsoftware was verschluckt. Das sollte heißen:

    Braucht denn ein

    SELECT max(ID)
    FROM tabelle
    WHERE ID < aktuelleID so viel länger?

  3. René sagt:

    Ich wäre vorsichtig mit Superlativen. Wenn es um Performance geht, würde ich eher diesen Ansatz wählen: die Tabelle erhält eine Spalte Vorgänger-ID.

    Bei Manipulationsbefehlen muß man diese ID mit berücksichtigen bzw. ermitteln. Zum Beispiel beim Löschen den Vorgänger des gelöschten Eintrags als Vorgänger des darauf erscheinenden Eintrags eintragen (Stichwort: Verkettete Listen).

    Suche ich den Vorgänger, so muß ich nun lediglich diese Spalte abfragen. Will ich den Nachfolger, dann frage ich eben ab, wo die aktuelle ID als Vorgänger eingetragen ist. Erspart die Sortierfunktion.

  4. Jan sagt:

    @Andreas: Korrekt. Ich meinte damit IDs, die keine PKs sind. Aber dann sind es auch nicht mehr wirklich IDs. Ist auch egal – ich hab ja auch gesagt, dass es Quatsch wäre 😉

    @Christian: Prinzipiell ist MAX eine Aggregationsfunktion. In diesem Fall wird es aber auch einfach den B-Baum-Index des PK nutzen können. Sollte also genauso schnell sein. Ich bin nur lieber vorsichtig mit Aggregatfunktionen.

    @René: Das stimmt natürlich, widerspricht aber jeglicher Normalisierung. Kann man machen, aber die 3 Zehntausendstel-Sekunden, die die von mir genannte Abfrage braucht, werden dadurch auch nicht weniger – im Gegenteil steigt der Speicherbedarf durch die zusätzliche Spalte.

  5. wenn man wirrklich die id brauch ist das ja wirrklich eine schöne sache, aber meisten reicht es doch auch wenn man einfach den nächsten datensatz hat oder?
    (suchergebnis seiten oder sonst irgendwas mit Seitenzahlen XD)

    ich würde da vllt eher sowas versuchen:

    “SELECT ID FROM tabelle LIMIT “.$aktuelle_id.”,1″ (wenn man nur einen Datensatz anzeigen möchte)

    dann is der nächste bzw letzte datensatz +1 bzw -1
    wenn man dann mysql_num_rows>0 abfängt weiß man dann auch ob noch einer vorhanden ist oder nicht…

    so hab ich das zumindest gemacht, wenn das jetzt ganz schlecht is sagt mir das bitte 😉

    Gruß Sascha

  6. Edith würde sagen:

    $aktuelle_id wäre natürlich nicht wirrklich richtig…
    eher sowas wie hm… $aktueller_datensatz oder soetwas in der richtung…

    naja war jetzt nur schnell als beipsiel zusammengebaut… verwennde das eigentlich wenn ich 10 einträge je seite anzeigen möchte und dann mit berechnung der zeitenzahlen etc…

  7. Jan sagt:

    Öhm: Das ist ganz schlecht 😉
    Also zu Deinem ersten Kommentar: Das geht natürlich nicht, da die ID x nicht auf den x-ten Datensatz hinweist, da es ja Löscher durch gelöschte Datensätze gibt. Aber das haste ja bereits selbst bemerkt.

    Und zum zweiten: Selbst wenn das ginge, müsstest Du ja trotzdem sortieren, denn sonst gibt MySQL Dir die Datensätze so, wie sie gepseichert sind. Das ist aber in den seltensten Fällen von 1 bis n.
    Also meiner Meinung nach wird das so nix.

  8. vitali sagt:

    Hi!
    Hast du denn keine Lust das mit max(id) zu testen?
    Das war auch meine erste Idee beim lesen des Blog-Eintrags. Ich finde es eleganter und kann mir sogar vorstellen, dass es schneller ist.

  9. vitali sagt:

    — Abfrage ausführen:
    select max(id) from modules where id < 10;

    Gesamtlaufzeit der Abfrage: 32 ms.
    1 Zeilen geholt.

    — Abfrage ausführen:
    select id from modules where id < 10 order by id limit 1;

    Gesamtlaufzeit der Abfrage: 16 ms.
    1 Zeilen geholt.

    Demnach ist deine Lösung (zumindest hier bei nur 20 Datensätzen) doppelt so schnell.

    PS: Wie wäre es mit einer Vorschau-Funktion für den Blog-Kommentar? *g*

  10. So nun bin ich Zuhause und kann mal eher erläutern was ich meinte… wie gesagt um die nächste ID rauszufinden ist meine Lösung schlecht aber um den nächsten Datensatz zu bekommen funktioniert sie einwandfrei…

    Nehmen wir mal an wir sind jetzt beim Datensatz mit der ID 7, das ist der 4. Datensatz in unserer DB, durch Löschungen oder Datenverlust oder was auch immer…

    Damit wäre die Abfrage für diesen Datensatz (ohne AUTO_INCREMENT, mit wäre das ORDER BY ja überflüssig weil des ja der Reihe nach vergeben werden würde XD):

    “SELECT ID, Feld FROM Tab ORDER BY ID LIMIT 3,1”
    (3 weils 0,1,2,3)
    $letzter_datensatz_nr=$row[‘id’]; // 3

    $nachfolger= $letzter_datensatz_nr+1; // 4
    $vorgaenger= $letzter_datensatz_nr-1; // 2

    Bsp.:
    “SELECT ID, Feld FROM Tab ORDER BY ID LIMIT “.$nachfolger.”,1″

    Wie gesagt so hat man den Datensatz aber halt nicht die ID 😉 kommt aber im Prinzip das gleiche raus, wenn man nur ausgeben möchte 😉 bei Abfragen die was ändern oder Joins is das natürlich quatsch XD

    Hoffe das is jetzt verständlicher erklärt 😉

    Gruß
    Sascha

  11. GhostGambler sagt:

    Die Lösung ist trotzdem nicht sehr gut:
    http://www.mysqlperformanceblog.com/2006/09/01/order-by-limit-performance-optimization/
    “Beware of large LIMIT
    Using index to sort is efficient if you need first few rows, even if some extra filtering takes place so you need to scan more rows by index then requested by LIMIT. However if you’re dealing with LIMIT query with large offset efficiency will suffer. LIMIT 1000,10 is likely to be way slower than LIMIT 0,10. It is true most users will not go further than 10 page in results, however Search Engine Bots may very well do so. I’ve seen bots looking at 200+ page in my projects. Also for many web sites failing to take care of this provides very easy task to launch a DOS attack – request page with some large number from few connections and it is enough. If you do not do anything else make sure you block requests with too large page numbers.

    For some cases, for example if results are static it may make sense to precompute results so you can query them for positions.
    So instead of query with LIMIT 1000,10 you will have WHERE position between 1000 and 1009 which has same efficiency for any position (as long as it is indexed)”

    Das kommt bei deiner Lösung vor.

  12. Vielen Dank, so lernt man wieder was 😉 naja ok wie wäre es dann mit “… WHERE ID > “.$last_ID.” LIMIT 0,10″ das wäre dann ok? wenn man die id bei der abfrage mit ausliest würde das ja auch ohne zusätzliche abfrage gehen…

    Gruß
    Sascha

  13. GhostGambler sagt:

    Das sind zwei Zeilen im Ergebnis. (Beim obigen Code)

    Sprich
    $result = mysql_query(“…UNION…”);
    print_r(mysql_fetch_assoc($result));
    print_r(mysql_fetch_assoc($result));
    und du hast beide Ergebnisse.

  14. Dennis sagt:

    @Ghostgambler

    danke für die schnelle antwort.
    was aber wenn ich mehrere ergebnisse in variablen speichern will? beispiel, wie ich das bisher hatte:

    $higherpage = mysql_fetch_array($higherpage_data);
    $higherpage_id = $higherpage[‘id’]
    $higherpage_kat = $higherpage[‘id’]

    und genau denselben query mit lowerpage?

    wie kann ich dann den $higherpage variblen alle ergebnisse aus der 1. select anweisung zuweisen und der $lowerpage der 2. select anweisung?
    blicke da noch nicht ganz durch

  15. noox sagt:

    Normalerweise sind natürlich Operationen auf Indizes weniger ein Problem. Wenn allerdings noch viele weitere Bedingungen (z.B. Rechte) dazukommen, könnte es eins werden. Wenn’s wirklich problematisch ist, könnte man auch einen ganz anderen Ansatz wählen:

    Die Ids der Vorgänger und Nachfolger gar nicht bestimmen, sondern der Zielseite hinter dem Vorgänger/Nachfolger-Link einfach übergeben, was sie machen soll. Nämlich den Vorgänger oder Nachfolger des aktuellen Eintrag anzeigen.

    Z.B.: <a href=”page.php?prevof=25″>Vorgänger</a>, <a href=”page.php?nextof=25″>Nachfolger</a>

    Dann bräuchte man auf jeder Seite nur eine Abfrage und nicht drei. Problem ist allerdings, dass dann für gleiche Seiten verschiedene Urls existieren. Blöd für Suchmaschinen. Man könnte das umgehen, indem man weiterleitet und die gefunden Id übergibt. Dann wären es zwei Abfragen (statt drei). Wobei die zweite direkt auf die Id geht, und damit einfach ist.

    In diesem Zusammenhang noch interessant ist übrigens auch:
    mysql> SELECT SQL_CALC_FOUND_ROWS * FROM tbl_name
    -> WHERE id > 100 LIMIT 10;
    mysql> SELECT FOUND_ROWS();

    Wenn man z.B. in einem Inhaltsverzeichnis 10 Zeilen anzeigen will, aber für die Seitennummerierung wissen möchte, wieviel es insgesamt wären, wenn man kein LIMIT hinzufügt. Muss allerdings gestehen, dass ich das nur einmal kurz ausprobiert habe (schon länger her), und nicht glücklich damit geworden bin. Weiß aber nicht mehr warum.

  16. noox sagt:

    Sorry, wusste nicht, dass hier Links übersetzt werden:

    Der Link zum Vorigen Eintrag von Eintrag mit Id 25 sollte lauten: page.php?prevof=25
    Und der Nächste: page.php?nextof=25

  17. GhostGambler sagt:

    In Angesicht dessen, dass allein für die Weiterleitung die komplette Umgebung (Rechte, globale Dinge, Session, usw.) geladen und ausgeführt werden muss – anstatt einfach der paar zusätzlichen Queries zur Ermittlung des Vorgängers und Nachfolgers – wohl die denkbar schlechteste Idee…

  18. noox sagt:

    Hängt davon ab, wie aufwändig die Queries sind. Aber bei der Seitennavigation sind sie zugegebener Maßen nicht sehr hoch, als das sich Weiterleiten im Vergleich zu zusätzlichen Queries auszahlt.

    Die letzten Jahre habe ich Performance-Probleme immer nur bei Datenbanken kennengelernt. Zusätzliche Webserver sind schnell aufgestellt 😉 Das dürfte bei mir noch zu stark verankert sein.

  19. Rafioso sagt:

    Hi,

    wenn man nicht gerade darauf angewiesen ist die ID vor einem Insert rauszubekommen, kann man alternativ zur PHP-Funktion “mysql_insert_id” auch einfach die MySQL-Funktion “LAST_INSERT_ID()” verwenden.

    PS: Funktioniert aber nur bei AUTO_INCREMENT.

    MfG
    Rafioso

  20. Jan sagt:

    @Rafioso: Was hat dieser Beitrag mit mysql_insert_id() bzw. LAST_INSERT_ID() zu tun? Erläutere Deinen Kommentar mal bitte etwas genauer.

  21. Rafioso sagt:

    Gerne =)
    In dem Beitrag geht es doch darum die vorherige bzw. nachfolgende ID rauszubekommen.
    Mit der genannten Funktion geht es doch, sofern man, wie gesagt, es nach einem Insert ausführt.
    Nachfolgend natürlich LAST_INSERT_ID()+1

    MfG
    Rafioso

  22. Dennis sagt:

    @Rafioso

    nein es geht darum vorhandene Datensätze in einer Datenbank zu ermitteln ohne neue Abfrage über num_rows()…

  23. Jan sagt:

    Es geht ja nicht nur um den zuletzt eingetragenen Datensatz. Den könntest Du natürlich mit mysql_insert_id() bzw. LAST_INSERT_ID() ermitteln Und selbst da würde der Vorgänder nicht zuverlässig ermittelt werden können.
    Es geht aber viel mehr darum, von vorhandenen Datensätzen mit einer bestimmten ID die vorhergehende und nachfolgende ID zu ermitteln.

  24. Rafioso sagt:

    Hi,

    ja jetzt merke ich es auch gerade. Allerdings führte mich der Name des Artikels dazu, hier zu antworten *g*
    Aber, wenn ich so darüber nachdenke, kann man selbst mit LAST_INSERT_ID() an den Datensatz kommen (die Zuverlässigkeit sei jetzt mal nicht von Bedeutung).
    Man müsste es lediglich in ein Sub-Query intigrieren.
    In wieweit das schneller oder langsamer als die oben genannten Beispiele sind, kann ich aber nicht sagen.

    MfG
    Rafioso

  25. Jan sagt:

    Wie willst Du mit LAST_INSERT_ID() an den Vorgänger kommen?
    Stell Dir mal folgende Situation vor:
    Spalte ID: 1, 2, 3

    Datensatz mit ID=2 wird gelöscht.
    Spalte ID: 1, 3
    Und nun kannst Du eben nicht einfach -1 rechnen, um den Vorgänger von 3 zu erhalten.

    Und wie gesagt, geht es hier vor allem um IDs, die kleiner sind LAST_INSERT_ID().
    Bspw. hast Du 10000 Datensätze.
    Datensatz 5327 wird aufgerufen. Wie ermittelst Du nun von diesem Datensatz den Vorgänder und Nachfolger?

  26. Rafioso sagt:

    Hi,

    an die Situation habe ich nicht gedacht. Schade, jetzt wollte ich hier was zeigen, was ihr sicherlich kennt, aber nicht erwähnt wurde und der Schuss ging nach Hinten los.

    Egal, ich hoffe mal, ihr nehmt es mir nicht übel.

    MfG
    Rafioso

Eine Antwort schreiben

Ihre E-Mail-Adresse wird nicht veröffentlicht. Benötigte Felder sind markiert mit *

You may use these HTML tags and attributes: <a href=""> <blockquote cite=""> <pre lang=""> <b> <strong> <i> <em>