SQL Server

Собственная индексация данных по широте и долготе

Джеймс Маккаффри

Продукты и технологии:

SQL Server 2008, Bing Maps

В статье рассматриваются:

• создание собственных индексов для географических данных;
• сопоставление пары «долгота-широта» с идентификатором сектора (sector ID);
• определение размера сектора;
• поиск смежных секторов;
• пример схемы индексации географических данных.

Исходный код можно скачать по ссылке code.msdn.microsoft.com/mag201206Indexing.

В этой статье я опишу способ создания собственных индексов для географических данных, содержащих информацию о местонахождении по широте и долготе. Собственные индексы (custom indexes) обеспечивают быструю выборку данных в реальном времени. Возьмем следующий сценарий. Допустим, у вас есть очень большой набор данных (несколько миллионов элементов), который выглядит примерно так:

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

Здесь первый столбец — идентификатор пользователя (или идентификатор любого объекта, сопоставленного с координатами), второй — широта точки местонахождения пользователя, а третий — долгота. Широты варьируются в диапазоне от –90.0 градусов до +90.0 и представляют координату по высоте (up-down coordinate). Значения долготы имеют диапазон от –180.0 градусов до +180.0 и представляют координату по горизонтали (left-right coordinate). Первый и третий пользователи находятся неподалеку от Сиэтла. Нулевое значение широты — это экватор, а нулевое значение долготы — осевой (нулевой) меридиан (Prime Meridian), который проходит через Гринвич в Англии. Теперь предположим, что ваши данные хранятся в SQL-таблице и вы хотите найти всех пользователей, находящихся в прямоугольнике с широтой от 47.0 до 48.0 градусов и долготой от –123.0 до –122.0 градусов. Вы могли бы сделать это с помощью простого SQL-выражения вроде этого:

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

Этот подход во многих ситуациях работает отлично. Однако, если вам нужна работа в реальном времени (время ответа менее трех секунд), когда размер ваших данных превышает некий порог (в зависимости от системных ресурсов), то скорость ответа начинает катастрофически падать.

Один из подходов к работе в реальном времени в подобных ситуациях — назначать каждому месту идентификатор сектора. Поэтому допустим, что вы можете сгенерировать вспомогательную таблицу на основе исходных данных и что она выглядит примерно так:

0001 49377 0002 45424 0003 49377 ...

Здесь в первом столбце хранятся идентификаторы пользователей, а во втором — идентификаторы секторов. Теперь, если идентификатор сектора проиндексирован, SQL-выражение наподобие следующего будет выполняться очень быстро, даже если ваш набор данных имеет сотни миллионов элементов:

SELECT userID FROM tblSectors WHERE sector = 49377

Идентификатор сектора выступает в роли собственного индекса для основного набора данных. Поэтому реальная задача заключается в том, чтобы написать функцию, которая принимает широту и долготу и возвращает сектор.

Чтобы лучше понять концепцию собственных индексов, взгляните на приложение-пример для Windows Presentation Foundation (WPF) на рис. 1. В него встроен элемент управления Bing Maps. После центрирования карты на каком-либо месте в Редмонде (штат Вашингтон) и его увеличения я дважды щелкнул карту. Событие двойного щелчка было связано с обработчиком, который определил широту и долготу точки щелчка и поместил на это место маркер в виде красной точки. Затем приложение вычислило идентификатор сектора для места щелчка, выполнило поиск по внутренней базе данных SQL со 100 миллионами случайных местонахождений пользователей и нашло восемь пользователей в том же секторе. Время поиска составило 0,36 секунды — весьма впечатляющая скорость работы.

Рис. 1. Собственная пространственная индексация в действии

В Microsoft SQL Server 2008 имеется весьма изощренная функциональность пространственных индексов, которую вы можете использовать в только что описанной ситуации. И во многих случаях применение пространственного индекса SQL Server — лучший вариант. Но минимум в двух сценариях предпочтительнее создание собственных индексов. Во-первых, пространственные индексы можно создавать только в поле SQL-типа geometry или geography. Если у вас есть устаревшая база данных или источник данных, где широты и долготы хранятся как чисто числовые значения, то преобразование этих значений в тип geography может оказаться неосуществимым. Во-вторых, хотя пространственные индексы в SQL Server 2008 чрезвычайно мощная и достаточно настраиваемая функциональность, в некоторых сценариях вам может понадобится полный контроль над схемой индексации.

Хотя создание собственных индексов не является новой концепцией, конкретных примеров слишком мало. В оставшейся части статьи я представлю полный пример того, как создать и использовать собственные индексы. Чтобы полностью понять эту статью, вы должны знать C# и T-SQL, как минимум, на среднем уровне. Вы можете получить основной код на C# для примера, представленного здесь, по ссылке code.msdn.microsoft.com/mag201206Indexing.

Сопоставление пары «широта-долгота» с идентификатором сектора

Существует много способов сопоставления пары «широта-долгота» с идентификатором сектора. Мой подход самый простой, и его лучше всего поясняет схема на рис. 2. Первое решение в собственной схеме индексации — выбор того, как сегментировать земной шар. На рис. 2 я разделил каждый градус широты (значения в строке) и каждый градус долготы (столбцы) на две части, на что указывает коэффициент fraction = 0.5 в верхнем левом углу схемы. Это дает мне 360 интервалов широты от [–90.0, –89.5) до [+89.5, +90.0] и 720 интервалов долготы от [–180.0, –179.5) до [+179.5, +180.0]. Квадратная скобка означает включение, а круглая — исключение. При коэффициенте, равном 0.5, мы получаем 360 * 720 = 259 200 секторов с нумерацией от 0 до 259 199. Я располагаю сектора слева направо и сверху вниз, как показано на рис. 2.

Рис. 2. Схема собственной индексации

При меньших значениях параметра fraction вы получаете больше интервалов на каждый градус и создаете больше секторов. В этом примере я использую одно и то же значение fraction для интервалов широты и долготы, но вы можете применить разные значения, если это лучше подходит для ваших данных. (Однако не у всех секторов один и тот же размер, как я вскоре поясню.) Если у вас есть индекс строки (широты) ri (row index) и индекс столбца (долготы) ci (column index), то соответствующий sid (sector ID) можно вычислить следующим образом:

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

Например, на рис. 2 сектор 1441 сопоставлен с индексом строки 2 и индексом столбца 1 и вычисляется как (2 * 360 * 1/0.5) + 1 = (2 * 720) + 1 = 1441. Член 360 * 1/fraction определяет, сколько интервалов столбца в каждой строке; последующее умножение на ri дает идентификатор первого сектора в соответствующей строке. Добавление члена ci, по сути, сдвигает столбцы ci вправо от начала соответствующей строки и дает в результате идентификатор последнего сектора.

Последняя часть головоломки — сопоставление значения широты с индексом строки и значения долготы с индексом столбца. Наивный подход заключался бы в выполнении простого линейного поиска. Прошлый опыт работы с очень большими наборами данных научил меня, что в таком случае более эффективен двоичный поиск. Идея в том, чтобы начать с нижним индексом, равным 0, средним индексом и верхним индексом, равным последнему возможному индексу. Далее определяется соответствующий интервал широты (или долготы) среднего индекса. Если целевая широта (или долгота) попадает в этот интервал, средний индекс содержит правильное возвращаемое значение. Если целевая широта (или долгота) меньше, чем текущий интервал, смещаем новый средний индекс на половину расстояния между нижним и предыдущим средним индексами. Если целевая широта (или долгота) больше, чем текущий интервал, смещаем новый средний индекс на половину расстояния между предыдущим средним и верхним индексами. Повторяем процедуру, пока не будет найден правильный средний индекс.

Реализация на C# метода LatIndex, который принимает значение широты (latitude) и fraction и возвращает индекс соответствующей строки, представлена на рис. 3. Парный ему метод LonIndex, возвращающий индекс столбца для долготы, совершенно симметричен с тем исключением, что константа 180 заменяется на 360, а константы –90.0 и 90.0 — на –180.0 и 180.0.

Рис. 3. Индекс строки для широты

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; // чтобы предотвратить бесконечный цикл while (ct < 10000) { ++ct; // Интервал левой части double left = firstLat + (fraction * mid); left = Math.Round(left, 8); // Интервал правой части double right = left + fraction; 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); }

Поскольку метод на рис. 3 работает с широтами как со значениями типа double, входной параметр latitude округляется до восьми десятичных разрядов, чтобы избежать неприятных ошибок равенства двух типов double (equality-of-two-type-double errors). Я использую переменную ct для предотвращения бесконечного цикла. Чтобы не засорять основной код, я удалил большую часть стандартной проверки на ошибки, например проверку допустимости входных параметров, которую нужно обязательно использовать в производственном коде. Заметьте, что основной цикл делает проверки на интервалы в виде [a,b), поэтому я должен явным образом проверять последнее значение на 90.0.

Спроектировав секторы и подготовив вспомогательные методы, можно сопоставить пару «широта-долгота» с сектором, вызывая метод наподобие следующего:

static int LatLonToSector(double latitude, double longitude, double fraction) { int latIndex = LatIndex(latitude, fraction); // строка int lonIndex = LonIndex(longitude, fraction); // столбец return (latIndex * 360 * (int)(1.0 / fraction)) + lonIndex; }

Размер сектора

В схеме собственной индексации, которую я описываю в этой статье, глобус делится на численно равные интервалы на основе значения параметра fraction. Например, если fraction равен 0.5, каждый интервал представляет собой 0.5 градуса широты или долготы. Однако это не означает, что все секторы имеют одинаковую географическую площадь. Взгляните на рис. 4. Линии широт проходят параллельно друг другу, и все они отстоят друг от друга на одинаковое расстояние — примерно 111 км. Поэтому расстояние A на рис. 4 идентично расстоянию B. Но линии долготы сближаются друг с другом по мере того, как они приближаются к каждому полюсу. Поэтому расстояние C меньше расстояния D.

Рис. 4. Секторы имеют разные географические площади

Расстояние (в км) между любыми двумя точками на глобусе можно оценить, используя следующий метод:

static double Distance(double lat1, double lon1, double lat2, double lon2) { double r = 6371.0; // примерный радиус Земли в км 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; }

Поэтому, если вам известны широта и долгота данного сектора, вы можете вычислить его приблизительную ширину и высоту, а затем примерную площадь. Чтобы определить левую конечную точку интервала, содержащего сектор, можно применить такой метод:

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

Этот метод выполняет, по сути, процесс, обратный тому, который осуществляется методом LatLonToSector. Например, если входной сектор — 1441 и параметр fraction имеет значение 0.5, как показано на рис. 2, локальная переменная divisor равна 360 * 1.0 / 0.5 = 720, что соответствует количеству интервалов долготы. А значит, значение переменной row составляет 1441 / 720 = 2 — это индекс строки (обратите внимание на целочисленное деление). Наконец, –90.0 + 0.5 * 2 = –90.0 + 1.0 = –89.0 — это левая часть интервала [–89.0, –79.5), сопоставленного с сектором 1441.

Метод для определения левой части интервала долготы сектора аналогичен, но не полностью симметричен:

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

Используя эти два вспомогательных метода, можно определить приблизительную площадь сектора (в квадратных километрах), определенного параметром fraction:

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; }

Смежные секторы

В некоторых сценариях разработки вам, возможно, потребуется определять, какие секторы являются смежными для данного сектора. Возьмем рис. 2 и предположим, что местоположение пользователя находится в секторе 721. Тогда вам может понадобиться определить, какие пользователи находятся в смежных секторах 0, 1, 2, 720, 722, 1440, 1441 и 1442. Заметьте, что сектора слева и справа отличаются на +1 и –1 соответственно, кроме секторов на левой и правой границах. А сектора сверху вниз, кроме секторов в верхней и нижней строках, отличаются соответственно на плюс и минус количество интервалов столбцов, которое равно 360 * (1 / fraction). Чтобы написать метод AdjacentSectors, принимающий сектор (и генерирующий fraction), полезно знать, находится ли сектор на левой или правой границе сопоставления либо в верхней или нижней строке. Эти четыре метода представлены на рис. 5.

Рис. 5. Вспомогательные методы для метода 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; }

Вы можете написать метод AdjacentSectors разными способами, при которых четкость и размер кода приносятся в жертву. Один из подходов — возвращать массив значений секторов, где возвращаемое значение [0] является смежным сектором, который граничит с верхним левым углом входного сектора, [1] — смежный сектор располагается непосредственно над ним, [2] — выше и правее, [3] — слева, [4] — справа, [5] — ниже и левее, [6] — прямо под ним и [7] — ниже и правее. Код на рис. 6 дает представление об одном из способов реализации AdjacentSectors. Хотя общий случай, где входной сектор не находится на границе сопоставления, весьма прямолинеен, некоторые особые случаи, включая четырехугольные секторы, довольно запутанны. Полную реализацию см. в исходном коде, который прилагается к этой статье.

Рис. 6. Реализация метода AdjacentSectors

static int[] AdjacentSectors(int sector, double fraction) { // По часовой стрелке от верхнего левого int[] result = new int[8]; int numCols = (int)(1.0 / fraction) * 360; int numRows = (int)(1.0 / fraction) * 180; int firstValueInLastRow = numCols * (numRows - 1); int lastValueInLastRow = numCols * numRows - 1; // Общий случай 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; } // Здесь обрабатываются особые случаи; // см. полный исходный код throw new Exception("Unexpected logic path in AdjacentSectors"); }

Пример схемы индексации географических данных

Хороший способ понять собственную схему индексации географических данных, описанную в этой статье, — изучить простой, но полный пример. Для начала создадим базу данных SQL, используя код на T-SQL:

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' )

Затем создадим таблицу для хранения образцов данных:

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

Далее напишем на C# код, генерирующий эти образцы данных:

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();

В схеме собственной индексации глобус делится на численно равные интервалы.

Здесь я создаю один миллион строк данных, разделяемых запятыми. Чтобы сгенерировать случайные широты и долготы в диапазоне [hi,lo), я использую стандартный шаблон (hi – lo) * random.NextDouble() + lo. Затем копирую образцы данных в SQL-таблицу, используя программу командной строки bcp.exe:

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

Эта команда означает: «Скопировать в таблицу tblUsers, находящуюся в базе данных dbGeoData, данные из файла UserIDLatLon.txt, которые представляют собой символьные данные (т. е. простой текст), где каждое поле разделяется запятой и каждая строка завершается символом начала новой строки. Сервер базы данных расположен на локальной машине, и для подключения используется аутентификация Trusted (Windows)».

Потом создаем вспомогательные данные секторов для собственной индексации, используя следующий код на C#:

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();

Этот код перебирает файл образцов данных по одной строке за раз, извлекает идентификатор пользователя, широту и долготу, вычисляет сопоставленный сектор с параметром fraction, равным 0.5, и записывает идентификатор пользователя и сектор, разделенные запятой, в текстовый файл.

Теперь создаем SQL-таблицу для хранения данных секторов:

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

Копируем данные секторов в таблицу:

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

Наконец, индексируем данные секторов:

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

В этом месте вы можете поэкспериментировать. Например, можно выбирать всех пользователей, находящихся в том же секторе, что пользователь номер 3, с помощью такого кода на T-SQL:

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

Конечно, если вы обращаетесь к SQL-данным из какого-либо приложения, то можете использовать эквиваленты этой разновидности SQL-кода на ADO.NET или LINQ.

Достижение скорости работы реального времени

Вы можете применять собственную индексацию во многих прикладных сценариях. Например, у вас есть веб-приложение ASP.NET или Silverlight с элементом управления Bing Maps. Вы могли бы создать систему, которая дает возможность пользователю щелкать по карте. Событие click сопоставляется с кодом, который определяет широту и долготу точки щелчка, вычисляет соответствующий сектор, а затем извлекает из внутренней базы данных SQL всех пользователей в этом секторе. Как показано на рис. 1, даже при нескольких сотнях миллионов строк можно добиться быстродействия реального времени.

В некоторых ситуациях вам может понадобиться создание нескольких собственных индексов. Например, вам может потребоваться индекс низкого разрешения с fraction = 1.0 (чтобы каждый сектор был размером 1×1 градус), индекс среднего разрешения с fraction = 0.25 и индекс высокого разрешения с fraction = 0.05. При наличии нескольких индексов вы можете успешно фильтровать свои SQL-данные. Сначала определяете, сколько пользователей в крупном секторе. Если для ваших целей это количество слишком велико, определяете, сколько пользователей в секторе среднего размера. Если и это значение чрезмерно большое, определяете семь смежных секторов и пользователей в них. И так далее.

В некоторых сценариях применение собственных индексов может обеспечить молниеносную скорость работы. 

Позвольте мне еще раз напомнить, что SQL Server 2008 обладает мощной встроенной функциональностью пространственной индексации, применение которой следует рассматривать в первую очередь, а не браться сразу за создание собственных индексов. Собственные индексы требуют явного использования дополнительных SQL-таблиц, которые усложняют управление в вашей системе. Предупредив вас об этом, замечу, что в некоторых сценариях применение собственных индексов может обеспечить молниеносную скорость работы. По мере распространения мобильных устройств с поддержкой GPS возможности сбора гигантских объемов географических данных будут только расширяться. Так что умение создавать собственные схемы индексации может оказаться важным для анализа этих данных.

Джеймс Маккаффри (Dr. James McCaffrey) — руководит в компании Volt Information Sciences Inc. повышением квалификации инженеров ПО из Microsoft, работающих в Редмонде (штат Вашингтон). Принимал участие в создании нескольких продуктов Microsoft, в том числе Internet Explorer и MSN Search. Автор книги «.NET Test Automation Recipes» (Apress, 2006). С ним можно связаться по адресу jammc@microsoft.com.

Выражаю благодарность за рецензирование статьи экспертам Айзеку Кьюнену (Isaac Kunen) и Дэну Либлингу (Dan Liebling).