Lukas.: mysql: Erste freie Zahl finden

Hallo Forum,

ich habe eine Tabelle "nummern", die eine Spalte beinhaltet, die einen Integer zwischen 100 und 100000 haben darf. Jeder Integer darf nur 1 x mal verwendet werden. Damit sich die Tabelle (wenn vom User nicht anders gewünscht) von unten her auffüllen soll, möchte kich ihm gerne den ersten freien Platz in dieser Spalte vorschlagen.

Das geht auch soweit, mit dieser Query:

SELECT MIN( Zahl ) FROM tabelle_nummern t1 WHERE NOT EXISTS ( SELECT Zahl FROM tabelle_nummern t2 WHERE t2.Zahl = t1.Zahl +1 ) AND t1.Zahl > 100 AND t1.Zahl < 100000

Leider ist diese Query meist sehr, sehr lahm. Zeiten von über 15 Sekunden sind bei etwa 2000-3000 belegten Nummern in der Tabelle keine Seltenheit.

Hat jemand eine Idee, wie ich das schneller lösen kann?

Lukas

  1. Hallo Lukas.,

    Jeder Integer darf nur 1 x mal verwendet werden.

    Das klingt nach einer Identifikationsmöglichkeit für den entsprechenden Datensatz. Warum verwendest du dann keine ID (Primärschlüssel) dafür?

    Hat diese Zahl eine wirkliche Bedeutung?

    Leider ist diese Query meist sehr, sehr lahm. Zeiten von über 15 Sekunden sind bei etwa 2000-3000 belegten Nummern in der Tabelle keine Seltenheit.

    Hat jemand eine Idee, wie ich das schneller lösen kann?

    Miss einer ID keine Bedeutung zu, die sie nicht hat. Es ist völlig wurscht, in welcher Reihenfolge die Daten in der Datenbank stehen. Lass das DBMS entscheiden, wo es den Datensatz hinschreibt.

    Ausgewählte Datensätze kannst du schnell und in jeder beliebigen Sortierung auf dem Client anzeigen. Zur Sortierung sollte allerdings nicht die ID herangezogen werden. Wenn du beispielsweise die Daten nach Eintragungszeitpunkt geordnet anzeigen möchtest, speichere den Eintragungszeitpunt mit ab.

    Bis demnächst
    Matthias

    --
    Dieses Forum nutzt Markdown. Im Wiki erhalten Sie Hilfe bei der Formatierung Ihrer Beiträge.
    1. Hallo Matthias,

      Das klingt nach einer Identifikationsmöglichkeit für den entsprechenden Datensatz. Warum verwendest du dann keine ID (Primärschlüssel) dafür?

      Hat diese Zahl eine wirkliche Bedeutung?

      Hat sie (so eine Art Kundennummer). Ich habe übrigens zusätzlich eine ID inkl. Primärschlüssel.

      Gruß, Lukas

      1. Hallo Lukas.,

        Hat sie (so eine Art Kundennummer). Ich habe übrigens zusätzlich eine ID inkl. Primärschlüssel.

        Wie wäre es, wenn du beim Anlegen eines neuen Kunden die nächste(n) freie(n) Kundennummern ermittelst und diese in einer eigenen Tabelle speicherst?

        Bis demnächst
        Matthias

        --
        Dieses Forum nutzt Markdown. Im Wiki erhalten Sie Hilfe bei der Formatierung Ihrer Beiträge.
        1. Hi Matthias,

          Wie wäre es, wenn du beim Anlegen eines neuen Kunden die nächste(n) freie(n) Kundennummern ermittelst und diese in einer eigenen Tabelle speicherst?

          Ja, gute Idee. Bringt sicher nicht den Durchbruch, aber genauso sicher ne ganze Menge. Das Problem ist ja, dass ich die Tabelle nicht selber gestalte, d.h., ich übernehme

          1. fertige Daten, auf die ich keinen Einfluss habe
          2. ist meine "freie Kundennummer" nur ein Vorschlag, den mein Uyser annimmt oder auch nicht.

          Das bedeutet, Dein Vorschlag schließt (nach unten hin) einige Nummer aus der Ergebnismenge aus, was vorteilhaft ist. Aber den Rest der Ergebnismenge bleibt in gleicher Weise erhalten, wie zuvor.

          Lukas

          1. Hallo Lukas.,

            Wie wäre es, wenn du beim Anlegen eines neuen Kunden die nächste(n) freie(n) Kundennummern ermittelst und diese in einer eigenen Tabelle speicherst?

            Ja, gute Idee. Bringt sicher nicht den Durchbruch, aber genauso sicher ne ganze Menge.

            d.h., ich übernehme 1. fertige Daten, auf die ich keinen Einfluss habe

            Aber doch nur einmalig? oder auch jeden Tag neu?

            Alternativ könntest du auch irgendwann in der Nacht ausreichend viele freie Kundennummern ermitteln.

            1. ist meine "freie Kundennummer" nur ein Vorschlag, den mein Uyser annimmt oder auch nicht.

            Die Tabelle "freie Kundennummer" musst du natürlich auch pflegen. Dazu könnte gehören, dass du freiwerdende Kundennummern gleich in die Tabelle einträgst.

            Das bedeutet, Dein Vorschlag schließt (nach unten hin) einige Nummer aus der Ergebnismenge aus, was vorteilhaft ist. Aber den Rest der Ergebnismenge bleibt in gleicher Weise erhalten, wie zuvor.

            Alternativ kannst du auch einfach alle freien Kundennummern ermitteln und in der DB speichern. Eine Tabelle mit einer Spalte/Primärschlüssel sollte deutlich performter sein. Die maximal 100000 Datensätze darin spielen zeitlich keine Rolle. DBMS sind für große Datenmengen gemacht.

            Bis demnächst
            Matthias

            --
            Dieses Forum nutzt Markdown. Im Wiki erhalten Sie Hilfe bei der Formatierung Ihrer Beiträge.
            1. Hallo Matthoias,

              Aber doch nur einmalig? oder auch jeden Tag neu?

              Auch jeden Tag neu.

              Alternativ könntest du auch irgendwann in der Nacht ausreichend viele freie Kundennummern ermitteln.

              Auch eine clevere Idee, gefällt mir.

              Ich mach es jetzt vorerst mal so. Wenn das in der Praxis Probleme machen sollte, werde ich einen Deiner beiden Tips anwenden.

              Danke für Deine Hilfe.

              Lukas

              1. Hallo und guten Tag,

                Alternativ könntest du auch irgendwann in der Nacht ausreichend viele freie Kundennummern ermitteln.

                Auch eine clevere Idee, gefällt mir.

                Nein, wenn es Kundennummern sind, dann unterliegen die auch der jeweiligen nationalen oder ggf. europäischen Steuergesetzgebung. In DE dürften sie mindestens 10 Jahre lang nicht wiedervergeben werden, nachdem ein Kunde "gestorben" ist.

                Und dann muss man sich eben über das Datenmodell Gedanken machen. Wenn man "direkt gestreute"[1] Nummernkreise will, muss man die auch von Anfang an so einrichten, sonst gibt es Durcheinander!

                Also bitte erst einmal unten rum klarschiff machen :-)

                Grüße
                TS

                --
                es wachse der Freifunk
                http://freifunk-oberharz.de

                1. Der Begriff "direkt gestreut" ist klassische Informatik. Ulkigerweise kann ich in Google noch nichts darüber finden. Die scheinen erst ca. 20 Jahre später mit ihrem "Wissen" begonnen zu haben. ↩︎

                1. Hallo TS,

                  Alternativ könntest du auch irgendwann in der Nacht ausreichend viele freie Kundennummern ermitteln.

                  Auch eine clevere Idee, gefällt mir.

                  Nein, wenn es Kundennummern sind, dann unterliegen die auch der jeweiligen nationalen oder ggf. europäischen Steuergesetzgebung. In DE dürften sie mindestens 10 Jahre lang nicht wiedervergeben werden, nachdem ein Kunde "gestorben" ist.

                  Lukas schrieb: „so eine Art Kundennummer“

                  Also bitte erst einmal unten rum klarschiff machen :-)

                  Hab ich gemacht, indem ich die Fußnote auch als Fußnote ausgezeichnet habe ;-)

                  Der Begriff "direkt gestreut" ist klassische Informatik. Ulkigerweise kann ich in Google noch nichts darüber finden. Die scheinen erst ca. 20 Jahre später mit ihrem "Wissen" begonnen zu haben.

                  Da frag doch mal den pl. ;-)

                  Bis demnächst
                  Matthias

                  --
                  Dieses Forum nutzt Markdown. Im Wiki erhalten Sie Hilfe bei der Formatierung Ihrer Beiträge.
                  1. Hallo Matthias,

                    Der Begriff "direkt gestreut" ist klassische Informatik. Ulkigerweise kann ich in Google noch nichts darüber finden. Die scheinen erst ca. 20 Jahre später mit ihrem "Wissen" begonnen zu haben.

                    Da frag doch mal den pl. ;-)

                    I lol'd iRL.

                    LG,
                    CK

                  2. Hallo und guten Tag,

                    Der Begriff "direkt gestreut" ist klassische Informatik. Ulkigerweise kann ich in Google noch nichts darüber finden. Die scheinen erst ca. 20 Jahre später mit ihrem "Wissen" begonnen zu haben.

                    Da frag doch mal den pl. ;-)

                    Meinst Du, dass der noch ältere oder deutschere Fachbücher zur Informatik im Schrank hat, als ich? ;-P

                    Meine ältesten sind von meinem Vater. Und der musste sich ca. zu Zeiten der Umstellung von Holerith Lochkartensystemen auf Bandsysteme damit beschäftigen. Und auch ich habe ca. 1990 bei der Einführung in die Programmierung unter UNIX noch von "Extents" und "direkt gestreuten Dateien" lernen müssen.

                    In den modernen Datenbankphilosphien stecken diese alten Gedanken durchaus alle noch drin, da sie teilweise immer noch absoluten Performancegewinn bedeuten.

                    Grüße
                    TS

                    --
                    es wachse der Freifunk
                    http://freifunk-oberharz.de
                2. Hi TS,

                  Nein, wenn es Kundennummern sind, dann unterliegen die auch der jeweiligen nationalen oder ggf. europäischen Steuergesetzgebung. In DE dürften sie mindestens 10 Jahre lang nicht wiedervergeben werden, nachdem ein Kunde "gestorben" ist.

                  Ich würde Kundennummern gar nicht mehr vergeben. Aber es sind keine Kundennummern... Davon ab, vergebe ich sie aber ebenfalls nicht mehr.

                  Gruß, Lukas

                3. Hallo TS,

                  Ich kann da durchaus etwas zu finden, aber mir erschliesst sich nicht, was damit gemeint ist. Wenn ich raten müsste, würde ich „sequentiell“ vermuten; ich unterstelle hier zwanghafte Eindeutschung von Fachbegriffen. Wobei „cellar memory“ für „stack“ immer noch der Gipfel ist. ;-)

                  LG,
                  CK

  2. Lukas, du hast an der Stelle zwei Probleme.

    Zum einen die Laufzeit der Frei-Suche. Die kannst Du vielleicht noch mit einem Index auf die "Zahl" Spalte runterbringen, wenn Dir die Einwände von Matthias nicht stichhaltig erscheinen. Und der "MIN" riecht irgendwie danach, als ob diese Query alle denkbaren freien Zahlen ermittelt und DANN deren Minimum bestimmt. Wäre es möglich, dass Du eine Tabelle mit 99900 Zeilen vorbereitest, mit Spalten "Zahl" und "Verwendet"? Dann kannst Du SELECT MIN(ZAHL) FROM ZAHLEN WHERE Verwendet=0 machen. Das ist ein linearer Tablescan und kein kartesisches Produkt (bzw. ein Index-Scan wenn Du einen anlegst).

    Aber dann kommt das Nächste: Du hast eine potentielle Race-Condition. Du schlägst dem User eine Zahl vor, der sagt OK und ups - dann musst Du eine Fehlermeldung ausgeben "Sorry, diese Zahl wurde mittlerweile von jemand anderem kassiert". Weil nämlich dummerweise gleichzeitig ein anderer User unterwegs war und schneller OK geklickt hat. Dieses Problem kannst Du in der entkoppelten Multiuser-Umgebung namens "Web" nie ausschließen. Deshalb: überlege gut, ob Du dir mit dieser Nummer ein geeignetes Konstrukt ausgedacht hast.

    Rolf

    1. Hi Rolf,

      Wäre es möglich, dass Du eine Tabelle mit 99900 Zeilen vorbereitest, mit Spalten "Zahl" und "Verwendet"? Dann kannst Du SELECT MIN(ZAHL) FROM ZAHLEN WHERE Verwendet=0 machen. Das ist ein linearer Tablescan und kein kartesisches Produkt (bzw. ein Index-Scan wenn Du einen anlegst).

      Klar ist das möglich.

      Aber dann kommt das Nächste: Du hast eine potentielle Race-Condition. Du schlägst dem User eine Zahl vor, der sagt OK und ups - dann musst Du eine Fehlermeldung ausgeben "Sorry, diese Zahl wurde mittlerweile von jemand anderem kassiert". Weil nämlich dummerweise gleichzeitig ein anderer User unterwegs war und schneller OK geklickt hat. Dieses Problem kannst Du in der entkoppelten Multiuser-Umgebung namens "Web" nie ausschließen. Deshalb: überlege gut, ob Du dir mit dieser Nummer ein geeignetes Konstrukt ausgedacht hast.

      Ok, die Race-Kondition ist nicht so dramatisch, weil die Chance, dass überhaupt eine Nummer gesucht wird, vielleicht 1-2 mal Täglich gegeben ist. Insofern wärs schon großes Pech, aber Du hast recht, ich muß dann tatsächlich eine Fehlermeldung ausgeben oder (ohne den User zu fragen) die nächst höhere freie Nummer vergeben. Beides unschön, aber vertretbar.

      Lukas

  3. Hallo und guten Tag,

    Das geht auch soweit, mit dieser Query:

    SELECT MIN( Zahl ) FROM tabelle_nummern t1 WHERE NOT EXISTS ( SELECT Zahl FROM tabelle_nummern t2 WHERE t2.Zahl = t1.Zahl +1 ) AND t1.Zahl > 100 AND t1.Zahl < 100000
    

    Leider ist diese Query meist sehr, sehr lahm. Zeiten von über 15 Sekunden sind bei etwa 2000-3000 belegten Nummern in der Tabelle keine Seltenheit.

    Hat jemand eine Idee, wie ich das schneller lösen kann?

    Versuch es anstelle von min() mal mit dem self-join und einer limit-clause.

    Grüße
    TS

    --
    es wachse der Freifunk
    http://freifunk-oberharz.de
    1. Hi TS,

      Versuch es anstelle von min() mal mit dem self-join und einer limit-clause.

      Kannst Du etwas genauer werden?

      Lukas

      1. SELF JOIN deshalb, weil deine Query äquivalent ist zu dieser hier:

        SELECT MIN(x.zahl)
        FROM numbers x LEFT JOIN numbers y ON x.zahl+1 = y.zahl
        WHERE y.zahl is null
        

        Ich habe jetzt mal ein paar SQL Performance-Messungen für deine Nummern gemacht. Um sie nicht durch den Servercache zu verfälschen, habe ich SQL_NO_CACHE hinzugefügt - was Du im Produktionsbetrieb NICHT machen solltest.

        SELECT zahl
        FROM number x
        WHERE NOT EXISTS (SELECT zahl FROM number y WHERE  y.zahl = x.zahl+1)
        

        braucht auf dem von mir genutzten MySQL ca 1,3 Sekunden - weil er ALLE freien Zahlen bestimmt. Meine Tabelle hatte 2560 Einträge mit 10 Lücken. Die Abfrage ist allerdings immer gleich lahm, egal wieviele Lücken ich drin habe.

        SELECT MIN(zahl) FROM ...

        ist genauso langsam, weil das die gleiche Query ist wie oben, mit einer draufgesetzten MIN() Folgeverarbeitung.

        SELECT zahl
        FROM number x
        WHERE NOT EXISTS (SELECT zahl FROM number y WHERE  y.zahl = x.zahl+1)
        LIMIT 1
        

        ist dagegen etwas anderes, weil er jetzt nämlich nach dem ersten Treffer aufhört. Wenn Du einige Lücken hast und die halbwegs verteilt liegen, bist Du deutlich schneller fertig. Dumm nur, dass diese Variante entarten kann. Wenn nämlich keine Lücke existiert, muss er wieder alle durchprobieren und braucht die volle Laufzeit.

        Was dagegen richtig hilft, ist ein Primary Index auf die Spalte Zahl. Selbst bei lückenloser Zahlenreihe läuft die Query bei mir dann in 0,006 statt 1,4 Sekunden durch.

        Trotzdem ist es ein Index-Scan pro Zahl in der Tabelle. Ob MySQL spezielle Tricks für Satzabgleiche hat, weiß ich nicht. Ich gucke noch.

        Rolf

        1. Hi Rolf,

          mein Primary Index liegt bereits auf einer anderen Spalte.

          Aber ich habe soeben auch mal beide Queries miteinander verglichen.

          17,79 Sek. zu 0,17 Sek.

          Ich galube, so versuche ich es erstmal und warte ab, ob sich das in der Praxis bewähren wird. Danke für Deine Hilfe und auch an TS für den Tip.

          Lukas

          1. Hi Rolf, Hi Matthias,

            17,79 Sek. zu 0,17 Sek.

            Ich galube, so versuche ich es erstmal und warte ab, ob sich das in der Praxis bewähren wird. Danke für Deine Hilfe und auch an TS für den Tip.

            Ich befürchte, ich bin dem mysql_cache irgendwie auf den leim gegangen. In der Praxis wars dann leider doch nahezu identisch lahm. Jetzt habe ich Matthias Idee umgesetzt und führe eine tabelle freier Nummern. Jetzt gehts natürlich rasend schenll. Dank nochmal Lukas

  4. Hallo und guten Tag Lukas,

    noch als kleine Ergänzung:

    die Suche im Archiv funktioniert immer noch, bzw. wieder hervorragend. Wenn Du im Suchfeld also "Lücken finden" eingeben würdest oder in der Spezialsuche "tag:mysql Lücken finden", dann würdest Du noch eine Menge Tipps zum Thema finden.

    @Forumsgeister:

    Wie wurden denn die "cathegories" aus dem alten Archiv in die Suchoptionen des neuen übernommen? Es wäre schön, wenn das in der Suchseite kurz erwähnt würde, ob da nun tags daraus geworden sind, oder nicht. :-)

    Danke

    Grüße
    TS

    --
    es wachse der Freifunk
    http://freifunk-oberharz.de
    1. Hallo

      @Forumsgeister:

      Nicht, dass ich einer wäre …

      Wie wurden denn die "cathegories" aus dem alten Archiv in die Suchoptionen des neuen übernommen? Es wäre schön, wenn das in der Suchseite kurz erwähnt würde, ob da nun tags daraus geworden sind, oder nicht. :-)

      Es wurden Tags daraus. Da die Suche aber erst mehrere Monate nach der Umstellung auf cforum4 angepasst wurde und weil dieser Umstand nur für Stammposter relevant war/ist, die die alte Version kannten und die die Umstellung vorwiegend live mitgemacht haben, wurde das wohl nicht extra erwähnt.

      Tschö, Auge

      --
      Wo wir Mängel selbst aufdecken, kann sich kein Gegner einnisten.
      Wolfgang Schneidewind *prust*