Lo sentimos, pero esta no es una respuesta de SQL, sino una forma de obtener un rendimiento predecible asumiendo ciertas restricciones en sus datos.
¿Con qué frecuencia cambian los datos? Si es posible, ¿podría precalcular un gráfico de cada entidad 5 vecinos más cercanos y usarlo para acelerar su selección?
Si la mayoría de estos datos son de solo lectura, entonces...
¿Qué tan uniformemente se distribuyen estos puntos? Si la distribución es bastante uniforme y bien conocida, entonces podría generar su propio mapeo espacial agrupando cada coordenada e índice en una tabla hash.
Si no necesita tener los datos en la base de datos, muévalos a un archivo asignado a la memoria para realizar búsquedas rápidas de hash. (70 millones de registros deberían caber fácilmente en la memoria).
Utilicé esta arquitectura para generar búsquedas de submilisegundos para publicidad gráfica y relevancia para motores de búsqueda.
==Elaboración==
Simplemente crea una cuadrícula de cuadrados de tamaño fijo (como un tablero de ajedrez), asigna cada punto a la cuadrícula y crea una lista de los objetos que pertenecen a cada una de las casillas de la cuadrícula, si ajusta el tamaño de cada uno. correctamente, debe tener en promedio de 5 a 50 puntos en cada cuadrado:en principio, este es un árbol cuádruple pero sin el árbol por simplicidad.
Para cada cubo que está vacío después de haber dispersado todos los datos en cubos, agrega información de los cubos más cercanos que contienen datos.
Ahora puede numerar cada cubo de izquierda a derecha-línea-ny-línea para que cada cubo tenga un número único que se pueda calcular a partir de las coordenadas, e inserte cada cubo en una tabla hash, o si el espacio lo permite de la misma manera una tabla de búsqueda directa.
Ahora, cuando tenga su consulta, simplemente calcule a qué depósito se asignará y obtendrá una lista de objetos en ese depósito, o obtendrá un depósito 'vacío' que contiene los punteros al depósito más cercano que tiene contenido. .
Eso le dará la primera lista de candidatos de objetos que está buscando, y ahora simplemente tiene que correr y ver cuál es el más cercano.
En el 99% de los casos, eso sería todo, pero si le preocupa que (a) haya algunos candidatos en los cubos siguientes que en realidad están más cerca, entonces simplemente verifique los 8 cubos circundantes y vea si puede encontrar más cerca de allí.
Si ahora también desea obtener una lista de todos los objetos que están más cerca, también calcule una red simple de 5 vecinos más cercanos para cada objeto, por lo que terminará con una estructura de datos como A-> {B, C, D ,E,F}, B->{A,D,G,H,I}, C->{A,J,K,G,M}....
Eso formará una red simple que ahora puede atravesar con una variación de Dijkstra aquí para obtener todos los puntos adyacentes a su punto más cercano.
La construcción de las estructuras de datos llevará tiempo, pero una vez hecho, y hecho correctamente, la búsqueda y la devolución de un conjunto de datos se pueden hacer en submilisegundos (sin incluir ninguna comunicación http o fuera de la caja por causa)
Espero que esto ayude.
