Desculpe, mas esta não é uma resposta SQL, mas uma maneira de obter um desempenho previsível, assumindo certas restrições em seus dados.

Com que frequência os dados mudam? Se possível, você poderia pré-calcular um gráfico de cada entidade 5 vizinhos mais próximos e usar isso para acelerar sua seleção?

Se esses dados são principalmente somente leitura, então...

Quão uniformemente esses pontos são distribuídos? Se a distribuição for bastante uniforme e bem conhecida, você poderia criar seu próprio mapeamento espacial agrupando cada coordenada e índice em uma tabela de hash.

Se você não precisar ter os dados no banco de dados, mova-os para um arquivo mapeado na memória para pesquisas rápidas de hash. (os registros de 70m devem caber facilmente na memória).

Eu usei essa arquitetura para gerar pesquisas de sub-milissegundos para publicidade de exibição e relevância do mecanismo de pesquisa.

==Elaboração==

Você simplesmente cria uma grade de quadrados de tamanho fixo (como um tabuleiro de xadrez), e mapeia cada ponto na grade, e cria uma lista dos objetos que pertencem a cada uma das caixas de grade -- se você ajustar o tamanho de cada caixa corretamente, você deve ter, em média, 5-50 pontos em cada quadrado -- Esta é, em princípio, uma árvore quádrupla, mas sem a árvore por simplicidade.

Para cada bucket vazio após você ter espalhado todos os dados em buckets, você adiciona informações de quais buckets mais próximos contêm dados.

Agora você pode numerar cada bucket da esquerda para a direita-line-ny-line para que cada bucket tenha um número único que pode ser calculado a partir das coordenadas -- e você insere cada bucket em uma tabela de hash, ou se o espaço permitir apenas uma tabela de consulta direta.

Agora, quando você tiver sua consulta, basta calcular para qual bucket será mapeado e obterá uma lista de objetos nesse bucket ou obterá um bucket 'vazio' que contém os ponteiros para o bucket mais próximo que tem conteúdo .

Isso lhe dará a primeira lista de candidatos de objetos que você está procurando, e agora você só precisa correr e ver qual é o mais próximo.

Em 99% dos casos, seria isso - mas se você está preocupado com isso, (a) há alguns condidados nos baldes próximos que estão realmente mais próximos, basta verificar os 8 baldes ao redor e ver se você pode encontrar mais perto lá.

Se agora você também deseja obter uma lista de todos os objetos que estão mais próximos, calcule também uma rede simples de 5 vizinhos mais próximos para cada objeto, então você terminará com uma estrutura de dados como A->{B,C,D ,E,F}, B->{A,D,G,H,I}, C->{A,J,K,G,M}....

Isso formará uma rede simples que agora você pode percorrer com uma variação de Dijkstra aqui para obter todos os pontos adjacentes ao ponto mais próximo.

Construir as estruturas de dados levará tempo, mas uma vez feito, a pesquisa correta e o retorno de um conjunto de dados podem ser feitos em menos de milissegundos (sem incluir qualquer comunicação http ou off-box de causa)

Espero que isto ajude.