SQL Server

Artigo
06/23/2015

Indexação personalizada para dados de latitude-longitude

Neste artigo descrevo uma técnica para criar índices personalizados de dados geográficos que contém informações de localização de latitude e longitude. Os índices personalizados permitem a recuperação de dados rápida e em tempo real. Por exemplo, considere o seguinte cenário: Suponha que você tenha um conjunto de dados muito grande (milhões de itens) semelhante a isso:

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

Aqui, a primeira coluna é uma ID de usuário (ou a ID de qualquer objeto associado a um local), a segunda coluna é a latitude do usuário e a terceira coluna é a longitude do usuário. As latitudes vão de -90.0 graus a +90.0 graus e representam a coordenada acima-abaixo. As longitudes vão de -180.0 graus a +180.0 graus e representam a coordenada à esquerda-à direita. Os locais do primeiro e do terceiro usuários são próximos de Seattle. Um valor de latitude zero é o equador. Uma longitude zero é o Meridiano de referência, que passa por Greenwich, Inglaterra. Suponha agora que seus dados estão armazenados em uma tabela SQL e que deseja encontrar todos os usuários que estão localizados no mesmo retângulo de 1 grau por 1 grau como o usuário 0001. Você poderia fazê-lo com uma simples instrução SQL como essa:

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

Em muitas situações essa abordagem funciona bem. Se precisar de desempenho em tempo real (talvez um tempo de resposta menor que 3 segundos) quando o tamanho de seus dados exceder algum limite (dependendo dos recursos do sistema), no entanto, o tempo de resposta começa a degradar drasticamente.

Uma abordagem para se obter desempenho em tempo real em situações como essa é atribuir cada local a uma ID de setor. Assim, suponha que possa gerar uma tabela auxiliar a partir dos dados iniciais semelhante a isso:

Aqui, a primeira coluna é a ID do usuário e a segunda coluna é uma ID do setor. Agora, se a ID do setor estiver indexada, uma instrução SQL como a seguinte será muito rápida mesmo que o conjunto de dados tenha centenas de milhões de itens.

    SELECT userID
    FROM tblSectors
    WHERE sector = 49377

A ID do setor está atuando como um índice personalizado no conjunto de dados principal. Portanto, o desafio real é escrever uma função que aceite uma latitude e longitude e retorne um setor.

Para entender melhor o conceito de índices personalizados, dê uma olhada no aplicativo Windows Presentation Foundation (WPF) de exemplo na Figura 1. O aplicativo tem um controle de mapa Bing Maps inserido. Depois de centralizar o mapa em um local em Redmond, Wash., e ampliar, cliquei duas vezes no mapa. O evento de clique duplo foi vinculado a um manipulador de eventos que determinou a latitude e longitude do clique e colocou um ponto de marcação vermelho no local do clique. Em seguida, o aplicativo computou a ID do setor do clique e pesquisou um banco de dados SQL back-end com 100 milhões de itens usuário-local aleatórios e encontrou oito usuários no mesmo setor. O tempo da pesquisa foi 0,36 segundos, desempenho bastante impressionante.

Custom Indexing Design
Figura 1 Indexação espacial personalizada em ação

O Microsoft SQL Server 2008 tem um sofisticado recurso de índice espacial que pode ser usado na situação que acabou de ser descrita. E, em muitos casos, usar um índice espacial do SQL Server é a melhor opção. Em pelo menos dois cenários, no entanto, criar índices personalizados é uma melhor abordagem. Primeiro, índices espaciais podem ser criados apenas em uma coluna de SQL tipo geometry ou geography. Se você tiver um banco de dados ou uma fonte de dados herdados em que as latitudes e longitudes são armazenadas como valores numéricos simples, converter esses valores em tipo geography pode não ser viável. Segundo, mesmo que os índices espaciais no SQL Server 2008 sejam extremamente poderosos e bastante personalizáveis, em alguns cenários talvez você precise de controle total sobre seu esquema de indexação.

Embora criar índices personalizados não seja um novo conceito, poucos exemplos concretos estão disponíveis. No restante deste artigo, apresentarei um exemplo completo de como criar e usar indexação personalizada. Para entender completamente este artigo, é necessário ter pelo menos habilidades de codificação de C# e T-SQL em nível intermediário. O código C# principal para o exemplo apresentado aqui pode ser obtido em archive.msdn.microsoft.com/mag201206Indexing.

Mapeando latitude-longitude para uma ID de setor

Há muitas maneiras de mapear um par latitude-longitude para uma ID de setor. A abordagem que descrevi aqui é a mais simples, e é explicada de melhor forma com o diagrama mostrado na Figura 2. A primeira decisão em um esquema de indexação personalizada é escolher como segmentar o globo. Na Figura 2 dividi cada grau de latitude (os valores de linha) e cada grau de longitude (as colunas) em duas partes, conforme indicado pela fração = 0,5 no canto esquerdo superior da figura. Isso resulta em 360 intervalos de latitude, de [-90,0, -89,5) a [+89,5, +90,0], e 720 intervalos de longitude, de [-180,0, -179,5) a [+179,5, +180,0]. Uso um colchete para significar inclusivo e um parêntese para significar exclusivo. Com um valor de fração de 0,5, há 360 * 720 = 259.200 setores numerados de 0 a 259.199. Ordeno os setores da esquerda para a direita e de cima para baixo, conforme mostrado na Figura 2

Figure 2 Projeto da indexação personalizada

fração = 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

Valores menores do parâmetro de fração criam mais intervalos por grau e geram mais setores. Neste exemplo, uso o mesmo valor de fração para ambos os intervalos de latitude e longitude, mas você pode usar valores diferentes se for mais adequado para sua distribuição de dados. No entanto, os setores não têm a mesma área, como explicarei em breve. Se você tiver um índice de linha (latitude) ri e um índice de coluna (longitude) ci, a ID de setor correspondente sid pode ser computada como a seguir:

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

Por exemplo, na Figura 2, o setor 1441 está associado com o índice de linha 2 e o índice de coluna 1 e é computado como (2 * 360 * 1/0,5) + 1 = (2 * 720) + 1 = 1441. O termo 360 * 1/fração determina quantos intervalos de coluna estão em cada linha, e então multiplicando por ri dá a primeira ID de setor na linha apropriada. Adicionar o termo ci essencialmente move as colunas ci para a direita do início da linha apropriada e dá o resultado da ID de setor final.

A parte final do quebra-cabeça é mapear um valor de latitude para um índice de linha e um valor de longitude para um índice de coluna. Uma abordagem ingênua seria fazer uma simples pesquisa linear. Experiências dolorosas do passado com conjunto de dados muito grandes me ensinaram que, nesse caso, uma pesquisa binária é uma melhor abordagem. A ideia é começar com um índice baixo de zero, o índice médio e um índice alto igual ao último índice possível. A seguir, determine o intervalo de latitude correspondente (ou longitude) do índice médio. Se a latitude de destino (ou longitude) cair no intervalo, o índice médio será o valor de retorno correto. Se a latitude de destino (ou longitude) for menor que o intervalo atual, mova o novo índice médio para meio caminho entre o índice baixo e o índice médio antigo. Se a latitude de destino (ou longitude) for maior que o intervalo atual, mova o novo índice médio para meio caminho entre o índice médio antigo e o índice alto. Repita o processo até o índice médio correto ser encontrado.

Uma implementação em C# de um método LatIndex que aceita um valor de latitude e uma fração e retorna o índice de linha correspondente é apresentado na Figura3. O método LonIndex parceiro que retorna um índice de coluna para uma longitude é completamente simétrico exceto que a constante 180 é substituída por 360, e as constantes -90,0 e 90,0 são substituídas por -180,0 e 180,0.

Figura 3 O índice linha/latitude de uma latitude

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

Como o método na Figura 3 funciona com latitudes como tipo double, o parâmetro latitude de entrada é arredondado para oito casas decimais para evitar erros desagradáveis de igualdade de dois tipos double. Eu uso uma variável ct um pouco alternativa para evitar um loop infinito. Para manter o código curto, removi a maior parte da verificação de erro normal, como validar os parâmetros de entrada, que seria usado em um cenário de produção. Observe que o loop principal verifica intervalos na forma [a,b), então, devo verificar explicitamente o último valor 90,0.

Com o projeto de setor e os métodos auxiliares em funcionamento, posso mapear um par latitude-longitude para um setor com um método como este:

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

Tamanho do setor

O esquema de indexação personalizada que descrevi neste artigo divide o globo em intervalos numericamente iguais com base no valor do parâmetro de fração. Por exemplo, se a fração for 0,5, cada intervalo é 0,5 grau de latitude ou longitude. No entanto, isso não significa que todos os setores tenham a mesma área geográfica. Examine a Figura 4. As linhas de latitude correm paralelas umas às outras e estão todas separadas da mesma distância, cerca de 111 quilômetros. Assim, a distância indicada por A na Figura 4 é a mesma que a distância indicada por B. Mas as linhas de longitude ficam mais próximas à medida que se aproximam de cada polo. Portanto, a distância indicada por C é menor que a distância indicada por D.

Sectors Have Different Geographical Areas
Figura 4 Os setores têm áreas geográficas diferentes

A distância em quilômetros entre quaisquer dois pontos no globo pode ser estimada usando o seguinte método:

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

Assim, se você souber a latitude e a longitude correspondentes de um determinado setor, poderá computar sua largura e altura aproximadas, e daí sua área aproximada. Para determinar o ponto de extremidade esquerdo do intervalo que contém um setor, você pode usar este método:

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

Esse método essencialmente executa o processo reverso do método LatLonToSector. Por exemplo, se o setor de entrada for 1441 e o parâmetro de fração tiver o valor 0,5, como mostrado na Figura 2, a variável do divisor local será 360 * 1,0 / 0,5 = 720, que é o número de intervalos de longitude. Então o valor da variável linha é 1441 / 720 = 2, que é o índice de linha (observe a divisão de inteiro). Finalmente, -90,0 + 0,5 * 2 = -90,0 + 1,0 = -89,0, que é a parte esquerda do intervalo [-89,0, -79,5) associado ao setor 1441.

O método para determinar a parte esquerda no intervalo de longitude de um setor é similar, mas não completamente simétrico:

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

Com esses dois métodos auxiliares, é possível determinar a área aproximada, em quilômetros quadrados, de um setor que foi definido por um parâmetro de fração:

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

Setores adjacentes

Em alguns cenários de desenvolvimento, talvez você precise determinar quais setores são adjacentes a um determinado setor. Por exemplo, na Figura 2, se o local de um usuário estiver no setor 721, talvez você queira determinar quais usuários estão em setores adjacentes 0, 1, 2, 720, 722, 1440, 1441 e 1442. Observe que setores esquerdo-direito diferem de mais ou menos um, exceto para setores nas bordas esquerda e direita do mapeamento do setor. E setores acima-abaixo, exceto setores nas linhas superior e inferior, diferem de mais ou menos o número de intervalos de coluna, que é 360 * (1 / fração). Para escrever um método AdjacentSectors que aceita um setor (e uma fração geradora), é útil saber se um setor está na borda de mapeamento esquerda ou direita, ou na linha superior ou inferior. Esses quatro métodos estão apresentados na Figura 5.

Figura 5 Métodos auxiliares para o método 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;
}

É possível escrever o método AdjacentSectors de muitas maneiras que equilibram clareza e tamanho do código. Uma abordagem é retornar uma matriz de valores de setor em que o valor de retorno [0] é o setor adjacente que está à esquerda superior do setor de entrada, [1] está diretamente acima, [2] está acima e à direita, [3] está à esquerda, [4] está à direita, [5] está abaixo e à esquerda, [6] está diretamente abaixo e [7] está abaixo e à direita. O código na Figura 6 descreve uma maneira de implementar AdjacentSectors. Embora o caso geral em que o setor de entrada não está em uma borda de mapeamento seja direto, alguns dos casos especiais, incluindo os setores de quatro cantos, são complicados. Consulte o código para download que acompanha este artigo para a implementação completa.

Figure 6 Uma implementação do método 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");
}

Criando um esquema de indexação geográfica

Uma boa maneira de entender o esquema de indexação geográfica personalizado descrito neste artigo é examinar um exemplo de ponta a ponta simples, mas completo. Primeiro, crio um banco de dados SQL fictício usando código T-SQL semelhante a isso:

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

Em seguida, crio uma tabela para conter alguns dados fictícios:

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

Escrevo então um código em C# para gerar dados fictícios:

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

Aqui estou criando 1 milhão de linhas de dados separados por vírgula. Para gerar latitudes e longitudes aleatórias no intervalo [hi,lo), estou usando o padrão (hi - lo) * random.NextDouble() + lo. Em seguida, copio os dados fictícios para a tabela SQL usando o programa bcp.exe de linha de comando:

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

Esse comando significa, “Copiar para a tabela tblUsers, que está no banco de dados dbGeoData, os dados no arquivo UserIDLatLon.txt, que são dados de caracteres (isso é, arquivo de texto) em que cada coluna é separada-finalizada pelo caractere vírgula e cada linha é finalizada de retorno por um caractere de nova linha. O servidor de banco de dados está no computador local, e autenticação Confiável (Windows) é usada para se conectar.”

Então, crio os dados do setor de indexação personalizada auxiliar usando código em C# como a seguir:

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

O código passa em loop pelo arquivo de dados fictícios uma linha de cada vez; analisa a ID do usuário, latitude e longitude; computa o setor associado com um parâmetro de fração de 0,5; e grava a ID do usuário e o setor separados por vírgula em um arquivo de texto.

Em seguida, crio uma tabela SQL para conter os dados de setor:

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

Então, copio os dados de setor para a tabela:

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

Finalmente, indexo os dados de setor:

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

Nesse ponto, você pode experimentar de várias maneiras. Por exemplo, é possível selecionar todos os usuários que estão no mesmo setor que o usuário 3 com código T-SQL, como a seguir:

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

Certamente, se estiver acessando seus dados SQL de um aplicativo, poderá usar equivalentes ADO.NET ou LINQ para esse tipo de código SQL.

Obtenha desempenho em tempo real

É possível usar indexação personalizada em muitos cenários de aplicativos. Por exemplo, suponha que você tenha um aplicativo Web ASP.NET ou um aplicativo do Silverlight com um controle de mapa Bing Maps. Você poderia criar um sistema que permite ao usuário clicar no mapa. O evento de clique está associado a um código que determina a latitude e a longitude do clique, computa o setor associado e então recupera de um banco de dados SQL back-end todos os usuários do setor. Como ilustrado na Figura 1, mesmo com várias centenas de milhões de linhas é possível obter desempenho em tempo real.

Em algumas situações talvez você queira criar vários índices personalizados. Por exemplo, você pode querer um índice de baixa granularidade com uma fração = 1,0 (de modo que cada setor seja 1 grau por 1 grau), um índice de média granularidade com fração = 0,25 e um índice de alta granularidade com fração = 0,05. Com diversos índices você pode filtrar seus dados SQL com êxito. Primeiro, determine quantos usuários estão no setor de baixa granularidade. Se tiver usuários demais para seus objetivos, determine quantos usuários estão no setor de média granularidade. Se tiver muito poucos usuários, determine os sete setores adjacentes e os usuários nesses setores. e assim por diante.

Deixe-me repetir que o SQL Server 2008 tem uma poderosa indexação espacial interna que você deve considerar o uso antes de criar índices personalizados. Índices personalizados exigem tabelas SQL adicionais e explícitas que impõem um aumento na carga de gerenciamento em seu sistema. Dito isso, no entanto, em alguns cenários os índices personalizados podem levar a desempenho muitíssimo rápido. Com o uso crescente de dispositivos móveis habilitados para GPS, a capacidade de reunir enormes quantidades de dados geográficos só irá se expandir. Poder criar esquemas de indexação personalizada pode ser uma habilidade importante para ajudá-lo a analisar esses dados.

Dr. James McCaffrey trabalha para a Volt Information Sciences, onde gerencia o treinamento técnico de engenheiros de software que trabalham no campus da Microsoft Redmond, Wash. Ele trabalhou em vários produtos da Microsoft, incluindo o Internet Explorer e o MSN Search. McCaffrey é também autor do livro “.NET Test Automation Recipes” (Apress, 2006). Entre em contato com ele pelo email jammc@microsoft.com.

Agradecemos aos seguintes especialistas técnicos pela revisão deste artigo: Isaac Kunen e Dan Liebling