SQL Server

Artikel
06/28/2016

Benutzerdefinierte Indizierung von Daten für Breiten- und Längengrade

In diesem Artikel beschreibe ich eine Vorgehensweise zur Erstellung benutzerdefinierter Indizes für geographische Daten, die Ortsinformationen nach Längen- und Breitengraden enthalten. Benutzerdefinierte Indizes ermöglichen das schnelle Abrufen von Daten in Echtzeit. Betrachten Sie beispielsweise folgendes Szenario. Angenommen, Sie haben einen sehr großen Satz von Daten (mehrere Millionen Elemente), der etwa wie folgt aussieht:

0001 47.610 -122.330
0002 36.175 -115.136
0003 47.613 -122.332
...

Hier enthält die erste Spalte einer Benutzer-ID (oder ID eines mit einem Standort verknüpften Objekts), die zweite Spalte enthält die geographische Breite des Benutzers und die dritte Spalte seine geographische Länge. Längenwerte reichen von -90,0 bis +90,0 Grad und repräsentieren die vertikale Koordinate. Breitenwerte reichen von -180,0 bis +180,0 Grad und repräsentieren die horizontale Koordinate. Die Standorte des ersten und des zweiten Benutzers befinden sich in der Nähe von Seattle. Der Breitenwert Null ist identisch mit dem Äquator. Die Länge Null ist der "Nullmeridian", der durch Greenwich in England verläuft. Nehmen wir jetzt an, Ihre Daten befinden sich in einer SQL-Tabelle, und Sie möchten alle Benutzer finden, die sich in demselben Rechteck mit der Seitenlänge 1 Grad befinden wie Benutzer 0001. Dazu könnten Sie eine einfache SQL-Anweisung wie die folgende verwenden:

  SELECT userID
  FROM tblUsers
  WHERE latitude >= 47.0 AND latitude < 48.0
  AND longitude >= -123.0 AND longitude < -122.0

In vielen Situationen ist dies eine sehr gute Vorgehensweise. Wenn Sie jedoch Echtzeitfunktionalität (etwa eine Reaktionszeit von weniger als drei Sekunden) benötigen, oder wenn der Umfang Ihrer Daten über einem bestimmten Schwellenwert liegt (je nach Ihren Systemressourcen), nimmt dabei die Reaktionszeit jedoch dramatisch ab.

Eine Möglichkeit dafür, in solchen Situationen Echtzeitleistung zu erzielen, besteht darin, jeden Standort einer Sektor-ID zuzuweisen. Nehmen wir also an, Sie können aus den anfänglichen Daten eine Hilfstabelle erstellen, die etwa so aussieht:

Hier enthält die erste Spalte die Benutzer-ID und die zweite eine Sektor-ID. Wenn die Sektor-ID indiziert ist, funktioniert eine SQL-Anweisung wie die folgende auch dann sehr schnell, wenn Ihre Daten aus Hunderten Millionen von Elementen bestehen:

  SELECT userID
  FROM tblSectors
  WHERE sector = 49377

Die Sektor-ID fungiert als benutzerdefinierter Index für den Hauptdatensatz. Die eigentliche Herausforderung besteht also daraus, eine Funktion zu schreiben, die Längen- und Breitengraddaten annimmt und einen Sektor zurückgibt.

Sehen Sie sich zum besseren Verständnis des Konzeptes benutzerdefinierter Indizes die Windows Presentation Foundation- (WPF) Beispielanwendung in Abbildung 1 an. Die Anwendung verfügt über eine eingebettete Bing Maps-Kartensteuerung. Nach dem Zentrieren der Karte auf einen Punkt in Redmond/Washington und dem Vergrößern der Karte doppelklickte ich darauf. Das Doppelklickereignis war mit einem Ereignishandler verknüpft, der Breiten- und Längengrad des Klicks ermittelte und an dieser Stelle einen roten Markierungspunkt setzte. Anschließend berechnete die Anwendung die Sektor-ID des Klicks und durchsuchte dann eine Backend-SQL-Datenbank mit 100 Millionen zufälligen Benutzerstandortelementen, wobei acht Benutzer im gleichen Sektor gefunden wurden. Die Suchzeit betrug 0,36 Sekunden – eine sehr beeindruckende Leistung.

Custom Indexing Design Abbildung 1 Benutzerdefinierte Raumindizierung in Aktion

Microsoft SQL Server 2008 verfügt über eine ausgeklügelte Raumindexfunktion, die in solchen Situationen zum Einsatz kommen kann. Und in vielen Fällen ist die Verwendung eines SQL Server-Raumindexes die beste Lösung. Es gibt jedoch mindestens zwei Szenarien, in denen es besser ist, benutzerdefinierte Indizes zu erstellen. Zunächst können Raumindizes nur für Spalten des SQL-Typs Geometrie oder Geographie erstellt werden. Wenn Sie eine ältere Datenbank oder Datenquelle haben, in der Breiten- und Längenwerte als einfache numerische Werte gespeichert sind, kann es sein, dass die Konvertierung dieser Werte zum Typ Geographie nicht gelingt. Zweitens: Obwohl Raumindizes in SQL Server 2008 sehr leistungsstark und sehr weitgehend anpassbar sind, benötigen Sie in manchen Szenarien wahrscheinlich die vollständige Kontrolle über Ihr Indizierungsschema.

Die Erstellung benutzerdefinierter Indizes ist zwar kein neues Konzept, dennoch sind nur wenige konkrete Beispiele verfügbar. Im verbleibenden Teil dieses Artikels stelle ich ein vollständiges Beispiel für die Erstellung und Verwendung eines benutzerdefinierten Index vor. Um diesen Artikel wirklich verstehen zu können, müssen Sie über mindestens mittlere Programmierkenntnisse mit C# und T-SQL verfügen. Sie finden den zentralen C#-Code für das hier vorgestellte Beispiel unter archive.msdn.microsoft.com/mag201206Indexing.

Zuordnen von Länge und Breite zu einer Sektor-ID

Es gibt viele Möglichkeiten für die Zuordnung eines Länge-/Breite-Paars einer Sektor-ID. Hier beschreibe ich die einfachste Möglichkeit, die am besten durch das Diagramm in Abbildung 2 erläutert wird. Bei einem benutzerdefinierten Indizierungsschema ist die erste Entscheidung die, wie die Weltkugel segmentiert werden soll. In Abbildung 2 habe ich alle Breitengrade (die Zeilenwerte) und alle Längenwerte (die Spalten) in zwei Teile geteilt, wie durch die Bruchzahl 0,5 in der oberen linken Ecke der Abbildung angezeigt. Dies ergibt 360 Breitenintervalle, von [-90,0, -89,5) bis [+89,5, +90,0] und 720 Längenintervalle, von [-180,0, -179,5) bis [+179,5, +180,0]. Eckige Klammern stehen für "einschließlich" und runde Klammern für "ausschließlich". Bei einem Bruchwert von 0,5 gibt es 360 * 720 = 259.200 Sektoren, nummeriert von 0 bis 259.199. Ich ordne die Sektoren von links nach rechts und von oben nach unten an, wie in Abbildung 2 gezeigt.

Abbildung 2 Entwurf der benutzerdefinierten Indizierung

Bruchzahl = 0,5	[-180.0, -179.5) 0	[-179.5, -170.0) 1	[-170.0, -169.5) 2		[179.5, 180.0] 719
[-90,0, -89,5) -> 0	0	1	2	...	719
[-89,5, -80,0) -> 1	720	721	722	...	1439
[-80,0, -79,5) -> 2	1440	1441	1442	...
	...

[89,5, 90,0] -> 359	258,480			...	259,199

Kleinere Werte des Bruchparameters führen zu mehr Intervallen pro Grad und generieren mehr Sektoren. In diesem Beispiel verwende ich den gleichen Bruchwert für breiten- und Längenintervalle, Sie können jedoch andere Werte verwenden, wenn Ihre Datenverteilung dies verlangt. Die Sektoren haben jedoch nicht alle die gleiche Fläche, wie ich gleich erläutern werden. Wenn Sie einen Zeilen- (Breiten-) Index ri und einen Spalten- (Längen-) Index ci haben, kann die entsprechende Sektor-ID sid wie folgt berechnet werden:

sid = (ri * 360 * 1/fraction) + ci

Zum Beispiel: In Abbildung 2 ist Sektor 1441 mit dem Zeilenindex 2 und dem Spaltenindex 1 assoziiert und wird berechnet als (2 * 360 * 1/0,5) + 1 = (2 * 720) + 1 = 1441. Der Term 360 * 1/Bruchzahl legt fest, wie viele Intervalle jede Zeile enthält, und die Multiplikation mit ri ergibt die erste Sektor-ID in der jeweiligen Zeile. Durch die Hinzufügung des Terms ci werden die ci-Spalten vom Anfang der jeweiligen Zeile nach rechts verschoben, und das Ergebnis ist die schließliche Sektor-ID.

Der abschließende Teil der Aufgabe besteht in der Zuordnung eines Breitenwertes zu einem Zeilenindex und eines Längenwertes zu einem Spaltenindex. Eine etwas naive Möglichkeit wäre, eine einfache lineare Suche durchzuführen. Schmerzliche Erfahrungen mit sehr großen Datensätzen haben mich jedoch belehrt, dass in diesem Fall eine binäre Suche die bessere Möglichkeit ist. Dabei geht es darum, mit einem niedrigen Index von Null zu beginnen, wobei der mittlere und ein hoher Index dem letzten möglichen Index entsprechen. Bestimmen Sie anschließend das entsprechende Breiten- (oder Längen-) Intervall des mittleren Index. Wenn der Ziel-Breitenwert (oder Längenwert) in das Intervall fällt, ist der mittlere Index der korrekte Rückgabewert. Wenn der Ziel-Breitenwert (oder Längenwert) kleiner ist als das aktuelle Intervall, verschieben Sie den neuen mittleren Index zur Hälfte zwischen dem niedrigen und dem alten mittleren Index. Wenn der Ziel-Breitenwert (oder Längenwert) größer ist als das aktuelle Intervall, verschieben Sie den neuen mittleren Index zur Hälfte zwischen dem alten niedrigen und dem hohen Index. Wiederholen Sie dies, bis Sie den korrekten mittleren Index gefunden haben.

Eine C#-Implementierung einer Methode "LatIndex", die einen Breitenwert und einen Bruchwert annimmt und den entsprechenden Zeilenindex ausgibt, ist in Abbildung3 illustriert. Die entsprechende "LonIndex"-Methode, die einen Spaltenindex für einen Längenwert zurückgibt, ist vollständig symmetrisch, mit der Ausnahme, dass die Konstante 180 durch 360 ersetzt ist, und dass die Konstanten -90,0 und 90,0 durch -180,0 und 180,0 ersetzt werden.

Abbildung 3 Der Zeilen-/Breitenindex einer Breite

static int LatIndex(double latitude, double fraction)
{
  latitude = Math.Round(latitude, 8);
  int lastIndex = (int)(180 * (1.0 / fraction) - 1);
  double firstLat = -90.0;
  if (latitude == -90.0) return 0;
  if (latitude == 90.0) return lastIndex;
  int lo = 0;
  int hi = lastIndex;
  int mid = (lo + hi) / 2;
  int ct = 0; // To prevent infinite loop
  while (ct < 10000)
  {
    ++ct;
    double left = firstLat + (fraction * mid); // Left part interval
    left = Math.Round(left, 8);
    double right = left + fraction;         // Right part interval
    right = Math.Round(right, 8);
    if (latitude >= left && latitude < right)
      return mid;
    else if (latitude < left)
    {
      hi = mid - 1; mid = (lo + hi) / 2;
    }
    else
    {
      lo = mid + 1; mid = (lo + hi) / 2;
    }
  }
  throw new Exception("LatIndex no return for input = " + latitude);
}

Da die Methode in Abbildung 3 mit Breiten als Typ "Double" arbeitet, wird der Eingabe-Breitenparameter auf acht Dezimalstellen gerundet, um unangenehme "Equality-of-Two"-Double-Fehler zu vermeiden. Ich verwende eine etwas komplexe ct-Variable, um eine unendliche Schleife zu vermeiden. Um den Code kurz zu halten, habe ich den größten Teil der normalen Fehlerprüfung entfernt – in einem Produktionsszenario können Sie dies natürlich nicht tun. Beachten Sie, dass die Hauptschleife nach Intervallen in der Form [a,b) sucht, ich muss also explizit nach dem letzten 90,0-Wert suchen.

Wenn Sektorentwurf und Helpermethoden vorhanden sind, kann ich ein Breite/Länge-Paar mit einer Methode, die wie folgt aussieht, einem Sektor zuordnen:

static int LatLonToSector(double latitude, double longitude,
  double fraction)
{
  int latIndex = LatIndex(latitude, fraction); // row
  int lonIndex = LonIndex(longitude, fraction);  // col
  return (latIndex * 360 * (int)(1.0 / fraction)) + lonIndex;
}

Sektorgröße

Das benutzerdefinierte Indizierungsschema, das ich in diesem Artikel beschreibe, unterteilt die Erdkugel in numerisch gleiche Intervalle, basierend auf dem Bruchzahlparameter. Zum Beispiel: Bei einer Bruchzahl 0,5 ist jedes Intervall 0,5 * ein Längen- oder Breitengrad. Dies bedeutet jedoch nicht, dass alle Sektoren die gleiche geographische Fläche haben. Betrachten Sie Abbildung 4. Breitenlinien verlaufen parallel zueinander und haben den gleichen Abstand, etwa 111 Kilometer. Die von Label A in Abbildung 4 markierte Entfernung ist daher gleich der von B angezeigten Entfernung. Längenlinien zeigen jedoch geringer werdende Abstände, je näher sie einem der Pole kommen. Die von Label C angezeigte Entfernung ist daher geringer als die von Label D angezeigte.

Sectors Have Different Geographical Areas
Abbildung 4 Sektoren weisen unterschiedliche geographische Flächen auf

Die Entfernung, in Kilometern, zwischen beliebigen zwei Punkten auf der Erdkugel kann mit dem folgenden Verfahren bestimmt werden:

static double Distance(double lat1, double lon1, 
  double lat2, double lon2)
{
  double r = 6371.0; // approx. radius of earth in km
  double lat1Radians = (lat1 * Math.PI) / 180.0;
  double lon1Radians = (lon1 * Math.PI) / 180.0;
  double lat2Radians = (lat2 * Math.PI) / 180.0;
  double lon2Radians = (lon2 * Math.PI) / 180.0;
  double d = r * Math.Acos((Math.Cos(lat1Radians) *
    Math.Cos(lat2Radians) *
    Math.Cos(lon2Radians - lon1Radians) +
   (Math.Sin(lat1Radians) * Math.Sin(lat2Radians)));
  return d;
}

Wenn Sie also die Breite und Länge eines bestimmten Sektors kennen, können Sie seine ungefähre Breite und Höhe und damit seine ungefähre Fläche berechnen. Zur Bestimmung des linken Endpunktes des Sektors, der das Intervall enthält, können Sie diese Methode verwenden:

static double SectorToLat(int sector,
    double fraction)
  {
    int divisor = 360 * (int)(1.0 / fraction);
    int row = sector / divisor;
    return -90.0 + (fraction * row);
  }

Diese Methode führt den umgekehrten Prozess der Methode "LatLonToSector" durch. Zum Beispiel: Wenn der Eingabesektor 1441 ist und der Bruchzahlparameter den Wert 0,5 hat, wie in Abbildung 2 gezeigt, ist die lokale Divisorvariable 360 * 1,0 / 0,5 = 720, d. h. die Anzahl der Längenintervalle. Dann ist der Wert der Variablenzeile 1441 / 720 = 2, was dem Zeilenindex entspricht (beachten Sie die Ganzzahldivision). Schließlich gilt: -90,0 + 0,5 * 2 = -90,0 + 1,0 = -89,0, was dem linken Teil des mit Sektor 1441 assoziierten Intervalls [-89.0, -79.5) entspricht.

Die Methode zur Bestimmung des linken Teils des Längenintervalls eines Sektors ist ähnlich, jedoch nicht vollständig symmetrisch:

static double SectorToLon(int sector, double fraction)
{
  int divisor = 360 * (int)(1.0 / fraction);
  int col = sector % divisor;
  return -180.0 + (fraction * col);
}

Mit diesen beiden Helpermethoden können Sie die ungefähre Fläche, in Quadratkilometern, eines Sektors ermitteln, der von einem Bruchzahlparameter definiert wurde:

static double Area(int sector, double fraction)
{
  double lat1 = SectorToLat(sector, fraction);
  double lon1 = SectorToLon(sector, fraction);
  double lat2 = lat1 + fraction;
  double lon2 = lon1 + fraction;
  double width = Distance(lat1, lon1, lat1, lon2);
  double height = Distance(lat1, lon1, lat2, lon1);
  return width * height;
}

Benachbarte Sektoren

In einigen Entwicklungsszenarien müssen Sie möglicherweise feststellen, welche Sektoren mit einem bestimmten Sektor benachbart sind. Wenn sich beispielsweise in Abbildung 2 der Standort eines Benutzers in Sektor 721 befindet, möchten Sie möglicherweise feststellen, welche Benutzer sich in den benachbarten Sektoren 0, 1, 2, 720, 722, 1440, 1441 und 1442 befinden. beachten Sie, dass sich die Links-Rechts-Sektoren um Plus-Minus Eins unterscheiden, ausgenommen Sektoren am linken und rechten Rand der Sektorzuordnung. Und vertikale Sektoren, ausgenommen Sektoren in der obersten und untersten Zeile, unterscheiden sich um Plus-Minus Eins vom Wert der Spaltenintervalle 360 * (1/Bruchzahl). Zum Erstellen einer Methode "AdjacentSectors", die einen Sektor (und einen generierenden Bruchwert) annimmt, sollten Sie wissen, ob sich ein Sektor am linken oder rechten Zuordnungsrand oder auf der untersten oder obersten Zeile befindet. Diese vier Methoden sind in Abbildung 5 illustriert.

Abbildung 5 Helpermethoden für die Methode "AdjacentSectors"

static bool IsLeftEdge(int sector, double fraction)
{
  int numColumns = (int)(1.0 / fraction) * 360;
  if (sector % numColumns == 0) return true;
  else return false;
}
static bool IsRightEdge(int sector, double fraction)
{
  if (IsLeftEdge(sector + 1, fraction) == true) return true;
  else return false;
}
static bool IsTopRow(int sector, double fraction)
{
  int numColumns = (int)(1.0 / fraction) * 360;
  if (sector >= 0 && sector <= numColumns - 1) return true;
  else return false;
}
static bool IsBottomRow(int sector, double fraction)
{
  int numColumns = (int)(1.0 / fraction) * 360;
  int numRows = (int)(1.0 / fraction) * 180;
  int firstValueInLastRow = numColumns * (numRows - 1);
  int lastValueInLastRow = numColumns * numRows - 1;
  if (sector >= firstValueInLastRow && sector <= lastValueInLastRow)
    return true;
  else
    return false;
}

Sie können die Methode "AdjacentSectors" auf verschiedene Weise schreiben, die jeweils eine unterschiedliche Balance zwischen Klarheit und Codegröße bieten. Eine Möglichkeit ist die Rückgabe eines Arrays mit Sektorwerte, wobei der Rückgabewert [0] der oben links dem Eingabesektor benachbarte Sektor ist. [1] befindet sich direkt darüber rechts, [3] links, [4] rechts, [5] darunter links, [6] direkt darunter und [7] darunter rechts. Der Code in Abbildung 6 zeigt eine Möglichkeit zur Implementierung von "AdjacentSectors". Obwohl der allgemeine Fall, in dem sich der Eingabesektor nicht auf einem Zuordnungsrand befindet, sehr einfach ist, sind einige besondere Fälle im Zusammenhang mit den vier Ecksektoren etwas schwieriger zu handhaben. Die vollständige Implementierung finden Sie im Codebeispiel zu diesem Artikel.

Abbildung 6 Eine Implementierung der Methode "AdjacentSectors"

static int[] AdjacentSectors(int sector, double fraction)
{
  int[] result = new int[8]; // Clockwise from upper-left
  int numCols = (int)(1.0 / fraction) * 360;
  int numRows = (int)(1.0 / fraction) * 180;
  int firstValueInLastRow = numCols * (numRows - 1);
  int lastValueInLastRow = numCols * numRows - 1;
  // General case
  if (IsLeftEdge(sector, fraction) == false &&
    IsRightEdge(sector, fraction) == false &&
    IsTopRow(sector, fraction) == false &&
    IsBottomRow(sector, fraction) == false)
  {
    result[0] = sector - numCols - 1;
    result[1] = sector - numCols;
    result[2] = sector - numCols + 1; 
    result[3] = sector - 1;
    result[4] = sector + 1;
    result[5] = sector + numCols - 1;
    result[6] = sector + numCols;
    result[7] = sector + numCols + 1;
    return result;
  }
  // Deal with special cases here. See code download.
  throw new Exception("Unexpected logic path in AdjacentSectors");
}

Die Zusammenstellung eines geographischen Indizierungsschemas

Eine gute Möglichkeit zum Verständnis des in diesem Artikel beschriebenen benutzerdefinierten geographischen Indizierungsschemas ist die Untersuchung eines einfachen, aber vollständigen, durchgehenden Beispiels. Erstellen Sie zuerst eine Dummy-SQL-Datenbank mit etwa dem folgenden T-SQL-Code:

    use master
    if exists(select * from sys.sysdatabases where name='dbGeoData')
      drop database dbGeoData
    create database dbGeoData on
    (
    name=dbGeoData,
    filename='D:\SomePlace\dbGeoData.mdf'
    )

Erstellen Sie dann eine Tabelle für einige Dummydaten.

    use dbGeoData
    create table tblUsers
    (
    userID int primary key,
    latitude real not null,
    longitude real not null
    )

Schreiben Sie dann C#-Code, der Dummydaten generiert:

Random r = new Random(0);
string initialDataFile = "..\\..\\UserIDLatLon.txt";
FileStream ofs = new FileStream(initialDataFile, FileMode.Create);
StreamWriter sw = new StreamWriter(ofs);
for (int i = 0; i < 1000000; ++i)
{
  double lat = (90.0 - (-90.0)) * r.NextDouble() + (-90.0);
  double lon = (180.0 - (-180.0)) * r.NextDouble() + (-180.0);
  sw.WriteLine(i.ToString().PadLeft(6,'0') + "," +
    lat.ToString("F8") + "," + lon.ToString("F8"));
}
sw.Close(); ofs.Close();

Hier erstelle ich eine Million Zeilen durch Kommata voneinander abgetrennter Daten. Zur Generierung zufälliger Breiten und Längen im Bereich [hi,lo) verwende ich das Standardmuster (hi - lo) * random.NextDouble() + lo. Kopieren Sie dann die Dummydaten in die SQL-Tabelle mit dem Befehlszeilenprogramm bcp.exe:

> bcp.exe dbGeoData..tblUsers in UserIDLatLon.txt -c -t , -r \n -S(local) -T

Dieser Befehl bedeutet “Kopieren in die Tabelle tblUsers, die sich in der Datenbank dbGeoData befindet, der Daten in der Datei UserIDLatLon.txt, die die Zeichendatei (d.h. eine Textdatei) ist, in der jede Spalte durch das Kommazeichen getrennt/beendet wird und jede Zeile von einem Newline-Zeichen beendet wird. Der Datenbankserver befindet sich auf dem lokalen Computer, und für die Verbindung wird die Trusted- (Windows) Authentifizierung verwendet.

Erstellen Sie dann den benutzerdefinierten Hilfsindizierungssektor mit etwa folgendem C#-Code:

string initialDataFile = "..\\..\\UserIDLatLon.txt";
string sectorDataFile = "..\\..\\ UserIDSector.txt";
FileStream ifs = new FileStream(initialDataFile, FileMode.Open);
StreamReader sr = new StreamReader(ifs);
FileStream ofs = new FileStream(sectorDataFile, FileMode.Create);
StreamWriter sw = new StreamWriter(ofs);
string line = "";
string[] tokens = null;
while ((line = sr.ReadLine()) != null)
{
  tokens = line.Split(',');
  int userID = int.Parse(tokens[0]);
  double lat = double.Parse(tokens[1]);
  double lon = double.Parse(tokens[2]);
  int sector = LatLonToSector(lat, lon, 0.5);
  sw.WriteLine(userID.ToString().PadLeft(6, '0') + "," + sector);
}
sw.Close(); ofs.Close(); sr.Close(); ifs.Close();

Der Code durchläuft die Dummy-Datendatei zeilenweise, erkennt die Benutzer-ID, die Länge und die Breite, berechnet den assoziierten Sektor mit einem Bruchzahlparameter 0,5 und schreibt die Benutzer-ID und den Sektor in kommaseparierter Form in eine Textdatei.

Erstellen Sie dann eine SQL-Tabelle für die Sektordaten:

    create table tblSectors
    (
    userID int primary key,
    sector int
    )

Kopieren Sie die Sektordaten in die Tabelle:

> bcp.exe dbGeoData..tblSectors in UserIDSector.txt -c -t , -r \n -S(local) -T

Indizieren Sie abschließend die Sektordaten:

    if exists(select name from sys.sysindexes where name='ndxSector')
      drop index ndxSector on tblSectors
    create nonclustered index ndxSector on tblSectors(sector)

An diesem Punkt können Sie beginnen, zu experimentieren: So können Sie etwa mit folgendem T-SQL-Code alle Benutzer auswählen, die sich im gleichen Sektor wie Benutzer 3 befinden:

declare @userID int
set @userID = 3
declare @sector int
select @sector = sector from tblSectors where userID=@userID
print @sector
select userID from tblSectors where sector = @sector

Natürlich können Sie, wenn Sie von einer Anwendung aus auf Ihre SQL-Daten zugreifen, ADO.NET- oder LINQ-Äquivalente zu diesem SQL-Code verwenden.

Echtzeitleistung

Benutzerdefinierte Indizes können in vielen verschiedenen Anwendungsbereichen eingesetzt werden. Nehmen Sie etwa an, Sie haben eine ASP.NET-Webanwendung oder eine Silverlight-Anwendung mit Bing Maps-Kartensteuerung. Sie können dann ein System erstellen, mit dem der Benutzer auf eine Karte klicken kann. Das Klickereignis wird Code zugeordnet, der Länge und Breite des Klicks feststellt, den entsprechenden Sektor berechnet und dann aus einer Backend-SQL-Datenbank alle Benutzer in diesem Sektor abruft. Wie Abbildung 1 zeigt, erzielen Sie damit auch bei Hunderten Millionen Zeilen Echtzeitleistung.

In manchen Situationen möchten Sie wahrscheinlich auch mehrere benutzerdefinierte Indizes erstellen. Vielleicht wünschen Sie einen Index mit niedriger Granularität und dem Bruchwert = 1,0 (so das jeder Sektor 1 x 1 Grad ist), einen Index mit mittlerer Granularität und dem Bruchwert = 0,25 und einen Index mit hoher Granularität und dem Bruchwert = 0,05. Mit mehreren Indizes können Sie Ihre SQL-Daten nacheinander filtern. Stellen Sie zuerst fest, wie viele Benutzer sich in dem Sektor mit niedriger Granularität befinden. Wenn die Zahl der Benutzer für Ihre Zwecke zu groß ist, stellen Sie fest, wie viele Benutzer sich in dem Sektor mit mittlerer Granularität befinden. Wenn die Zahl der Benutzer zu klein ist, bestimmen Sie die sieben benachbarten Sektoren und die darin befindlichen Benutzer. Und so weiter.

Lassen Sie mich erneut betonen, dass SQL Server 2008 über leistungsstarke integrierte Raumindizierungsfunktionen verfügt, die Sie ausprobieren sollten, bevor Sie selbst einen benutzerdefinierten Index erstellen. Benutzerdefinierte Indizes erfordern explizite, zusätzliche SQL-Tabellen, die Ihr System mit zusätzlichen Verwaltungsaufgaben belasten. Dennoch können benutzerdefinierte Indizes in manchen Szenarien eine erstaunlich schnelle Leistung bieten. Bei der stetig zunehmenden Nutzung von GPS-fähigen Mobilgeräten wird die Nutzung sehr großer Mengen geographischer Daten sicher zunehmen. Die Fähigkeit zur Erstellung benutzerdefinierter Indizierungsschemata kann Ihnen sehr nützlich dabei sein, diese Daten zu analysieren.

Dr. James McCaffrey ist für Volt Information Sciences Inc. tätig. Er leitet technische Schulungen für Softwareentwickler, die auf dem Campus von Microsoft in Redmond, USA arbeiten. Er hat an verschiedenen Microsoft-Produkten mitgearbeitet, unter anderem an Internet Explorer und MSN Search. McCaffrey ist auch der Verfasser von ".NET Test Automation Recipes" (Apress, 2006). Sie erreichen ihn unter jammc@microsoft.com.

Unser Dank gilt den folgenden technischen Experten für die Durchsicht dieses Artikels: Isaac Kunen und Dan Liebling