2010-06-29 20 views
7

Ich habe eine recht große Anzahl von Telefonnummern (ca. 2 Millionen) in einer Datenbanktabelle. Diese Zahlen wurden in Blöcken eingefügt, so dass es viele kontinuierliche Zahlenbereiche gibt, alles von 10 bis 10 000 in einem Bereich. Einige dieser Nummern werden verwendet und sind daher als nicht verfügbar gekennzeichnet, der Rest ist verfügbar. Bei einer bestimmten Nummer brauche ich einen Weg, um kontinuierliche Zahlenbereiche zu finden, sowohl oberhalb als auch unterhalb dieser Zahl. Der Bereich sollte fortgesetzt werden, bis er eine nicht verfügbare Nummer findet oder die Grenze von zwei Bereichen erreicht.Suchen von kontinuierlichen Bereichen in einer Reihe von Zahlen

Zum Beispiel angesichts der folgenden Satz:

1000 
1001 
1002 
1010 
1011 
1012 
1013 
1020 
1021 
1022 

der Suche 1012 als Parameter sollte 1010 zurückgeben, 1011, 1012, 1013.

Was zur Ausbildung einer Abfrage, um eine gute Möglichkeit ist, Finde diese Bereiche? Wir verwenden NHibernate auf dem SQL-Server, eine Lösung, die beide verwendet, ist in Ordnung.

Antwort

18

Theoretisch haben die Elemente in einem Set keinen bestimmten Wert, daher nehme ich an, dass Sie auch eine fortlaufende ID-Spalte haben, die die Reihenfolge der Zahlen definiert.Etwas wie folgt aus:

ID Number 
1 1000 
2 1001 
3 1002 
4 1010 
5 1011 
6 1012 
7 1013 
8 1020 
9 1021 
10 1022 

Sie könnten eine zusätzliche Spalte erstellen, die das Ergebnis der Number - ID enthält:

ID Number Diff 
1 1000 999 
2 1001 999 
3 1002 999 
4 1010 1006 
5 1011 1006 
6 1012 1006 
7 1013 1006 
8 1020 1012 
9 1021 1012 
10 1022 1012 

Zahlen im gleichen Bereich das gleiche Ergebnis in der Diff-Spalte haben.

+0

Dachte irgendwo in diese Richtung, aber sah es nicht +1 – Unreason

+1

Das ist schlau, aber beantwortet nicht vollständig die Frage. Wenn eine der Zeilen entfernt wird, werden die IDs nicht neu berechnet, sodass Sie für alle Werte eine nicht kontinuierliche Menge mit demselben Unterschied haben. Ich kann möglicherweise eine generierte Zeilennummer als Teil einer Abfrage verwenden, um die Dinge zu beschleunigen. –

+4

Ja, Sie könnten die Funktion ROW_NUMBER() über die Spalte ID verwenden, um eine fortlaufende Sequenz für die Diff-Berechnung zu generieren. http://msdn.microsoft.com/en-us/library/ms186734.aspx –

1

SQL kann dies in einer einzigen Abfrage nicht wirklich tun (außer es gibt native SQL-Erweiterungen, von denen ich nichts weiß), weil SQL auf die Zeile 'vor' oder 'nach' nicht zugreifen kann.

Sie müssen die Sequenz in einer Schleife durchlaufen.

Sie können versuchen, NHibernates Enumerable, die die Entitäten nicht in Arbeitsspeicher lädt, aber nur Proxies von ihnen erstellt. Eigentlich glaube ich nicht, dass es eine gute Idee ist, denn es wird Proxies für die ganzen 2 Millionen Zahlen erzeugen.

Plan B, Paging verwenden. Grob gesagt, sieht es wie folgt aus:

List<PhoneNumber> result = new List<PhoneNumber>(); 

int input = 1012; 
int pageSize = 100; 
int currentPage = 0; 
int expectedNumber = input; 

bool carryOn = true; 

while(carryOn) 
{ 
    var numbers = session 
    .CreateQuery("from PhoneNumber pn where pn.Number > :input") 
    .SetInt("input", input) 
    .SetFirstResult(currentPage * pageSize) 
    .SetMaxResult(pageSize) 
    .List<PhoneNumbers>(); 

    foreach(var number in numbers) 
    { 
    expectNumber++; 
    if (number.Number != expectedNumber) 
    { 
     carryOn = false; 
     break; 
    } 
    result.Add(number); 
    } 

    currentPage++; 
} 

Und das gleiche gilt für den Bereich, bevor sie in die andere Richtung.

+0

Bedingung sollte sein 'where pn.Number> =: Eingabe' ist es nicht? –

+0

SQL hat Prozeduren gespeichert und unterstützt vor allem rekursive Abfragen (http://en.wikipedia.org/wiki/Hierarchical_query). – Unreason

+0

@ Péter: Warum? um zu sehen, ob die Eingangsnummer existiert? Möglicherweise liegen diese Details außerhalb meiner Antwort. –

0

Wenn Sie SQL Server verwenden, sollten Sie in der Lage sein, ein recursive query zu machen, die auf root.number = leaf.number + 1

beitreten Wenn Sie die Nummer von der Wurzel und aus der letzten Rekursion wählen, und dem Ebene der Rekursion sollten Sie eine funktionierende Anfrage haben.

Zuerst würde ich die Leistung testen und dann, wenn nicht zufriedenstellend, zum cursor/zeilenbasierten Ansatz wechseln (was in diesem Fall einen Auftrag mit einem einzigen vollständigen Scan ausführen würde, bei dem Rekursion durch Erreichen der maximalen Rekursionstiefe fehlschlagen kann).

Andernfalls besteht die Möglichkeit, Daten anders zu speichern und eine Liste von Min- und Max-Nummern zu verwalten, die einer Tabelle zugeordnet sind.

Dies könnte tatsächlich in Triggern implementiert werden, die bei Einzelzeilenupdates nicht so stark belastet werden (Aktualisierungen in der einzelnen Zeile der Basistabelle würden entweder eine Zeile in der Min-Max-Tabelle aktualisieren, löschen oder aufteilen) bestimmt durch Abfrage nur der 'vorherigen' und 'nächsten' Zeile.

+0

Was wäre, wenn die maximale Rekursion tatsächlich 2 Millionen betragen könnte? Woher bekommen Sie den Link zur vorherigen Nummer? –

+0

Wie für die Größe, OP sagt, es sollte bis zu 10k sein, die ich glaube, dass MS SQL unterstützen würde (ich notiere die Möglichkeit, Sachen in der Antwort zu brechen). Ich bekomme Ihre Frage bezüglich der vorherigen Nummer nicht - zwischen Anker und rekursiver Abfrage sehe ich kein Problem beim Beitritt. – Unreason

0

Verwenden Sie eine Hilfstabelle aller möglichen sequentiellen Werte oder materialisieren Sie eine in einem CTE, z.

WITH 
-- materialize a table of sequential integers 
l0 AS (SELECT 0 AS c UNION ALL SELECT 0), 
l1 AS (SELECT 0 AS c FROM l0 AS a, l0 AS b), 
l2 AS (SELECT 0 AS c FROM l1 AS a, l1 AS b), 
l3 AS (SELECT 0 AS c FROM l2 AS a, l2 AS b), 
l4 AS (SELECT 0 AS c FROM l2 AS a, l3 AS b), 
l5 AS (SELECT 0 AS c FROM l2 AS a, l4 AS b), 
nums AS (SELECT row_number() OVER(ORDER BY c) AS n FROM l5), 
-- materialize sample table 
MyTable (ID) AS 
(
SELECT 1000 
UNION ALL 
SELECT 1001 
UNION ALL 
SELECT 1002 
UNION ALL 
SELECT 1010 
UNION ALL 
SELECT 1011 
UNION ALL 
SELECT 1012 
UNION ALL 
SELECT 1013 
UNION ALL 
SELECT 1020 
UNION ALL 
SELECT 1021 
UNION ALL 
SELECT 1022 
), 
-- materialize parameter table 
params (param) AS (SELECT 1012) 
SELECT MIN(N1.n) - 1 AS last_in_sequence 
    FROM nums AS N1 
     CROSS JOIN params AS P1 
WHERE N1.n > P1.param 
     AND NOT EXISTS 
     (
     SELECT * 
      FROM MyTable AS T1 
     WHERE N1.n = T1.ID 
     ); 
Verwandte Themen