Optimización de una ubicación de tienda basada en la proximidad ¿Buscar en un servidor web compartido?

Tengo un proyecto donde necesito construir un localizador de tiendas para un cliente.

Estoy usando un tipo de publicación personalizado " restaurant-location" y he escrito el código para geocodificar las direcciones almacenadas en postmeta usando la API de Geocodificación de Google (aquí está el enlace que geocodifica la Casa Blanca de EE. UU. En JSON y he almacenado la latitud y la longitud de nuevo a campos personalizados.

He escrito una get_posts_by_geo_distance()función que devuelve una lista de publicaciones en el orden de las más cercanas geográficamente utilizando la fórmula que encontré en la presentación de diapositivas en esta publicación . Puede llamar a mi función de esta manera (estoy comenzando con un lat / long "fuente" fijo):

include "wp-load.php";

$source_lat = 30.3935337;
$source_long = -86.4957833;

$results = get_posts_by_geo_distance(
    'restaurant-location',
    'geo_latitude',
    'geo_longitude',
    $source_lat,
    $source_long);

echo '<ul>';
foreach($results as $post) {
    $edit_url = get_edit_url($post->ID);
    echo "<li>{$post->distance}: <a href=\"{$edit_url}\" target=\"_blank\">{$post->location}</a></li>";
}
echo '</ul>';
return;

Aquí está la función en get_posts_by_geo_distance()sí:

function get_posts_by_geo_distance($post_type,$lat_key,$lng_key,$source_lat,$source_lng) {
    global $wpdb;
    $sql =<<<SQL
SELECT
    rl.ID,
    rl.post_title AS location,
    ROUND(3956*2*ASIN(SQRT(POWER(SIN(({$source_lat}-abs(lat.lat))*pi()/180/2),2)+
    COS({$source_lat}*pi()/180)*COS(abs(lat.lat)*pi()/180)*
    POWER(SIN(({$source_lng}-lng.lng)*pi()/180/2),2))),3) AS distance
FROM
    wp_posts rl
    INNER JOIN (SELECT post_id,CAST(meta_value AS DECIMAL(11,7)) AS lat FROM wp_postmeta lat WHERE lat.meta_key='{$lat_key}') lat ON lat.post_id = rl.ID
    INNER JOIN (SELECT post_id,CAST(meta_value AS DECIMAL(11,7)) AS lng FROM wp_postmeta lng WHERE lng.meta_key='{$lng_key}') lng ON lng.post_id = rl.ID
WHERE
    rl.post_type='{$post_type}' AND rl.post_name<>'auto-draft'
ORDER BY
    distance
SQL;
    $sql = $wpdb->prepare($sql,$source_lat,$source_lat,$source_lng);
    return $wpdb->get_results($sql);
}

Mi preocupación es que el SQL no está lo más optimizado posible. MySQL no puede ordenar por ningún índice disponible ya que el geo de origen es cambiante y no hay un conjunto finito de geos de origen para almacenar en caché. Actualmente estoy perplejo en cuanto a las formas de optimizarlo.

Teniendo en cuenta lo que ya he hecho, la pregunta es: ¿cómo harías para optimizar este caso de uso?

No es importante que guarde todo lo que he hecho si una mejor solución me obliga a tirarlo. Estoy abierto a considerar casi cualquier solución, excepto una que requiera hacer algo como instalar un servidor Sphinx o cualquier cosa que requiera una configuración MySQL personalizada. Básicamente, la solución debe poder funcionar en cualquier instalación simple de WordPress. (Dicho esto, sería genial si alguien quiere enumerar soluciones alternativas para otros que podrían ser más avanzados y para la posteridad).

Recursos encontrados

Para su información, investigué un poco sobre esto, así que en lugar de que haga la investigación nuevamente o que publique cualquiera de estos enlaces como respuesta, seguiré adelante y los incluiré.

• http://jebaird.com/blog/calculating-distance-miles-latitude-and-longitude
• http://wordpress.org/extend/plugins/geolocation/screenshots/
• http://code.google.com/apis/maps/articles/phpsqlsearch.html
• http://www.rooftopsolutions.nl/blog/229
• http://planet.mysql.com/entry/?id=18085
• http://blog.peoplesdns.com/archives/24
• http://www.petefreitag.com/item/622.cfm
• http://www.phpro.org/tutorials/Geo-Targetting-With-PHP-And-MySQL.html
• http://forum.geonames.org/gforum/posts/list/692.page
• http://forums.mysql.com/list.php?23
• http://www.scribd.com/doc/2569355/Geo-Distance-Search-with-MySQL
• http://developer.yahoo.com/maps/rest/V1/geocode.html
• http://geocoder.us/

Sobre la búsqueda de esfinges

• http://sphinxsearch.com/
• https://launchpad.net/wp-sphinx-plugin
• http://forums.site5.com/showthread.php?t=28981
• http://wordpress.org/extend/plugins/wordpress-sphinx-plugin/
• http://wordpress.org/extend/plugins/sphinx-search/
• http://www.mysqlperformanceblog.com/2008/02/15/mysql-performance-blog-now-uses-sphinx-for-site-search/

¿Qué precisión necesitas? Si se trata de una búsqueda en todo el estado / nacional, tal vez podría hacer una búsqueda de lat-lon a zip y tener una distancia calculada previamente desde el área zip al área zip del restaurante. Si necesita distancias precisas, esa no será una buena opción.

Debería buscar una solución Geohash , en el artículo de Wikipedia hay un enlace a una biblioteca PHP para codificar la decodificación durante mucho tiempo a geohashs.

Aquí tiene un buen artículo que explica por qué y cómo lo usan en Google App Engine (código Python pero fácil de seguir). Debido a la necesidad de usar geohash en GAE, puede encontrar algunas buenas bibliotecas y ejemplos de Python.

Como explica esta publicación de blog , la ventaja de usar geohashes es que puede crear un índice en la tabla MySQL en ese campo.

Esto podría ser demasiado tarde para usted, pero voy a responder de todos modos, con una respuesta similar a la que le di a esta pregunta relacionada , para que los futuros visitantes puedan consultar ambas preguntas.

No almacenaría estos valores en la tabla de metadatos de publicación, o al menos no solo allí. ¿Quieres una mesa con post_id, lat, loncolumnas, por lo que puede colocar un índice de lat, lonconsulta Y sobre eso. Esto no debería ser demasiado difícil de mantener actualizado con un enlace en guardar y actualizar la publicación.

Cuando consulta la base de datos, define un cuadro delimitador alrededor del punto de partida, por lo que puede realizar una consulta eficiente para todos los lat, lonpares entre los bordes Norte-Sur y Este-Oeste del cuadro.

Después de obtener este resultado reducido, puede hacer un cálculo de distancia más avanzado (direcciones de conducción reales o circulares) para filtrar las ubicaciones que se encuentran en las esquinas del cuadro delimitador y, por lo tanto, más lejos de lo que desea.

Aquí encontrará un ejemplo de código simple que funciona en el área de administración. Necesita crear la tabla de base de datos adicional usted mismo. El código está ordenado de más a menos interesante.

<?php
/*
Plugin Name: Monkeyman geo test
Plugin URI: http://www.monkeyman.be
Description: Geolocation test
Version: 1.0
Author: Jan Fabry
*/

class Monkeyman_Geo
{
    public function __construct()
    {
        add_action('init', array(&$this, 'registerPostType'));
        add_action('save_post', array(&$this, 'saveLatLon'), 10, 2);

        add_action('admin_menu', array(&$this, 'addAdminPages'));
    }

    /**
     * On post save, save the metadata in our special table
     * (post_id INT, lat DECIMAL(10,5), lon DECIMAL (10,5))
     * Index on lat, lon
     */
    public function saveLatLon($post_id, $post)
    {
        if ($post->post_type != 'monkeyman_geo') {
            return;
        }
        $lat = floatval(get_post_meta($post_id, 'lat', true));
        $lon = floatval(get_post_meta($post_id, 'lon', true));

        global $wpdb;
        $result = $wpdb->replace(
            $wpdb->prefix . 'monkeyman_geo',
            array(
                'post_id' => $post_id,
                'lat' => $lat,
                'lon' => $lon,
            ),
            array('%s', '%F', '%F')
        );
    }

    public function addAdminPages()
    {
        add_management_page( 'Quick location generator', 'Quick generator', 'edit_posts', __FILE__  . 'generator', array($this, 'doGeneratorPage'));
        add_management_page( 'Location test', 'Location test', 'edit_posts', __FILE__ . 'test', array($this, 'doTestPage'));

    }

    /**
     * Simple test page with a location and a distance
     */
    public function doTestPage()
    {
        if (!array_key_exists('search', $_REQUEST)) {
            $default_lat = ini_get('date.default_latitude');
            $default_lon = ini_get('date.default_longitude');

            echo <<<EOF
<form action="" method="post">
    <p>Center latitude: <input size="10" name="center_lat" value="{$default_lat}"/>
        <br/>Center longitude: <input size="10" name="center_lon" value="{$default_lon}"/>
        <br/>Max distance (km): <input size="5" name="max_distance" value="100"/></p>
    <p><input type="submit" name="search" value="Search!"/></p>
</form>
EOF;
            return;
        }
        $center_lon = floatval($_REQUEST['center_lon']);
        $center_lat = floatval($_REQUEST['center_lat']);
        $max_distance = floatval($_REQUEST['max_distance']);

        var_dump(self::getPostsUntilDistanceKm($center_lon, $center_lat, $max_distance));
    }

    /**
     * Get all posts that are closer than the given distance to the given location
     */
    public static function getPostsUntilDistanceKm($center_lon, $center_lat, $max_distance)
    {
        list($north_lat, $east_lon, $south_lat, $west_lon) = self::getBoundingBox($center_lat, $center_lon, $max_distance);

        $geo_posts = self::getPostsInBoundingBox($north_lat, $east_lon, $south_lat, $west_lon);

        $close_posts = array();
        foreach ($geo_posts as $geo_post) {
            $post_lat = floatval($geo_post->lat);
            $post_lon = floatval($geo_post->lon);
            $post_distance = self::calculateDistanceKm($center_lat, $center_lon, $post_lat, $post_lon);
            if ($post_distance < $max_distance) {
                $close_posts[$geo_post->post_id] = $post_distance;
            }
        }
        return $close_posts;
    }

    /**
     * Select all posts ids in a given bounding box
     */
    public static function getPostsInBoundingBox($north_lat, $east_lon, $south_lat, $west_lon)
    {
        global $wpdb;
        $sql = $wpdb->prepare('SELECT post_id, lat, lon FROM ' . $wpdb->prefix . 'monkeyman_geo WHERE lat < %F AND lat > %F AND lon < %F AND lon > %F', array($north_lat, $south_lat, $west_lon, $east_lon));
        return $wpdb->get_results($sql, OBJECT_K);
    }

    /* Geographical calculations: distance and bounding box */

    /**
     * Calculate the distance between two coordinates
     * http://stackoverflow.com/questions/365826/calculate-distance-between-2-gps-coordinates/1416950#1416950
     */
    public static function calculateDistanceKm($a_lat, $a_lon, $b_lat, $b_lon)
    {
        $d_lon = deg2rad($b_lon - $a_lon);
        $d_lat = deg2rad($b_lat - $a_lat);
        $a = pow(sin($d_lat/2.0), 2) + cos(deg2rad($a_lat)) * cos(deg2rad($b_lat)) * pow(sin($d_lon/2.0), 2);
        $c = 2 * atan2(sqrt($a), sqrt(1-$a));
        $d = 6367 * $c;

        return $d;
    }

    /**
     * Create a box around a given point that extends a certain distance in each direction
     * http://www.colorado.edu/geography/gcraft/warmup/aquifer/html/distance.html
     *
     * @todo: Mind the gap at 180 degrees!
     */
    public static function getBoundingBox($center_lat, $center_lon, $distance_km)
    {
        $one_lat_deg_in_km = 111.321543; // Fixed
        $one_lon_deg_in_km = cos(deg2rad($center_lat)) * 111.321543; // Depends on latitude

        $north_lat = $center_lat + ($distance_km / $one_lat_deg_in_km);
        $south_lat = $center_lat - ($distance_km / $one_lat_deg_in_km);

        $east_lon = $center_lon - ($distance_km / $one_lon_deg_in_km);
        $west_lon = $center_lon + ($distance_km / $one_lon_deg_in_km);

        return array($north_lat, $east_lon, $south_lat, $west_lon);
    }

    /* Below this it's not interesting anymore */

    /**
     * Generate some test data
     */
    public function doGeneratorPage()
    {
        if (!array_key_exists('generate', $_REQUEST)) {
            $default_lat = ini_get('date.default_latitude');
            $default_lon = ini_get('date.default_longitude');

            echo <<<EOF
<form action="" method="post">
    <p>Number of posts: <input size="5" name="post_count" value="10"/></p>
    <p>Center latitude: <input size="10" name="center_lat" value="{$default_lat}"/>
        <br/>Center longitude: <input size="10" name="center_lon" value="{$default_lon}"/>
        <br/>Max distance (km): <input size="5" name="max_distance" value="100"/></p>
    <p><input type="submit" name="generate" value="Generate!"/></p>
</form>
EOF;
            return;
        }
        $post_count = intval($_REQUEST['post_count']);
        $center_lon = floatval($_REQUEST['center_lon']);
        $center_lat = floatval($_REQUEST['center_lat']);
        $max_distance = floatval($_REQUEST['max_distance']);

        list($north_lat, $east_lon, $south_lat, $west_lon) = self::getBoundingBox($center_lat, $center_lon, $max_distance);


        add_action('save_post', array(&$this, 'setPostLatLon'), 5);
        $precision = 100000;
        for ($p = 0; $p < $post_count; $p++) {
            self::$currentRandomLat = mt_rand($south_lat * $precision, $north_lat * $precision) / $precision;
            self::$currentRandomLon = mt_rand($west_lon * $precision, $east_lon * $precision) / $precision;

            $location = sprintf('(%F, %F)', self::$currentRandomLat, self::$currentRandomLon);

            $post_data = array(
                'post_status' => 'publish',
                'post_type' => 'monkeyman_geo',
                'post_content' => 'Point at ' . $location,
                'post_title' => 'Point at ' . $location,
            );

            var_dump(wp_insert_post($post_data));
        }
    }

    public static $currentRandomLat = null;
    public static $currentRandomLon = null;

    /**
     * Because I didn't know how to save meta data with wp_insert_post,
     * I do it here
     */
    public function setPostLatLon($post_id)
    {
        add_post_meta($post_id, 'lat', self::$currentRandomLat);
        add_post_meta($post_id, 'lon', self::$currentRandomLon);
    }

    /**
     * Register a simple post type for us
     */
    public function registerPostType()
    {
        register_post_type(
            'monkeyman_geo',
            array(
                'label' => 'Geo Location',
                'labels' => array(
                    'name' => 'Geo Locations',
                    'singular_name' => 'Geo Location',
                    'add_new' => 'Add new',
                    'add_new_item' => 'Add new location',
                    'edit_item' => 'Edit location',
                    'new_item' => 'New location',
                    'view_item' => 'View location',
                    'search_items' => 'Search locations',
                    'not_found' => 'No locations found',
                    'not_found_in_trash' => 'No locations found in trash',
                    'parent_item_colon' => null,
                ),
                'description' => 'Geographical locations',
                'public' => true,
                'exclude_from_search' => false,
                'publicly_queryable' => true,
                'show_ui' => true,
                'menu_position' => null,
                'menu_icon' => null,
                'capability_type' => 'post',
                'capabilities' => array(),
                'hierarchical' => false,
                'supports' => array(
                    'title',
                    'editor',
                    'custom-fields',
                ),
                'register_meta_box_cb' => null,
                'taxonomies' => array(),
                'permalink_epmask' => EP_PERMALINK,
                'rewrite' => array(
                    'slug' => 'locations',
                ),
                'query_var' => true,
                'can_export' => true,
                'show_in_nav_menus' => true,
            )
        );
    }
}

$monkeyman_Geo_instance = new Monkeyman_Geo();

Llego tarde a la fiesta en este caso, pero mirando hacia atrás, este get_post_metaes realmente el problema aquí, en lugar de la consulta SQL que está utilizando.

Recientemente tuve que hacer una búsqueda geográfica similar en un sitio que ejecuto, y en lugar de usar la metatabla para almacenar lat y lon (que requiere, en el mejor de los casos, dos uniones para buscar y, si está usando get_post_meta, dos bases de datos adicionales consultas por ubicación), creé una nueva tabla con un tipo de datos POINT de geometría espacialmente indexada.

Mi consulta se parecía mucho a la suya, con MySQL haciendo mucho trabajo pesado (omití las funciones trigonométricas y simplifiqué todo al espacio bidimensional, porque estaba lo suficientemente cerca para mis propósitos):

function nearby_property_listings( $number = 5 ) {
    global $client_location, $wpdb;

    //sanitize public inputs
    $lat = (float)$client_location['lat'];  
    $lon = (float)$client_location['lon']; 

    $sql = $wpdb->prepare( "SELECT *, ROUND( SQRT( ( ( ( Y(geolocation) - $lat) * 
                                                       ( Y(geolocation) - $lat) ) *
                                                         69.1 * 69.1) +
                                                  ( ( X(geolocation) - $lon ) * 
                                                       ( X(geolocation) - $lon ) * 
                                                         53 * 53 ) ) ) as distance
                            FROM {$wpdb->properties}
                            ORDER BY distance LIMIT %d", $number );

    return $wpdb->get_results( $sql );
}

donde $ client_location es un valor devuelto por un servicio de búsqueda de IP de geo público (utilicé geoio.com, pero hay varios similares).

Puede parecer difícil de manejar, pero al probarlo, devolvió consistentemente las 5 ubicaciones más cercanas de una tabla de 80,000 filas en menos de .4 segundos.

Hasta que MySQL implemente la función DISTANCE que se propone, esta parece ser la mejor manera que encontré para implementar búsquedas de ubicación.

EDITAR: Agregar la estructura de la tabla para esta tabla en particular. Es un conjunto de listados de propiedades, por lo que puede o no ser similar a cualquier otro caso de uso.

CREATE TABLE IF NOT EXISTS `rh_properties` (
  `listingId` int(10) unsigned NOT NULL,
  `listingType` varchar(60) collate utf8_unicode_ci NOT NULL,
  `propertyType` varchar(60) collate utf8_unicode_ci NOT NULL,
  `status` varchar(20) collate utf8_unicode_ci NOT NULL,
  `street` varchar(64) collate utf8_unicode_ci NOT NULL,
  `city` varchar(24) collate utf8_unicode_ci NOT NULL,
  `state` varchar(5) collate utf8_unicode_ci NOT NULL,
  `zip` decimal(5,0) unsigned zerofill NOT NULL,
  `geolocation` point NOT NULL,
  `county` varchar(64) collate utf8_unicode_ci NOT NULL,
  `bedrooms` decimal(3,2) unsigned NOT NULL,
  `bathrooms` decimal(3,2) unsigned NOT NULL,
  `price` mediumint(8) unsigned NOT NULL,
  `image_url` varchar(255) collate utf8_unicode_ci NOT NULL,
  `description` mediumtext collate utf8_unicode_ci NOT NULL,
  `link` varchar(255) collate utf8_unicode_ci NOT NULL,
  PRIMARY KEY  (`listingId`),
  KEY `geolocation` (`geolocation`(25))
)

La geolocationcolumna es lo único relevante para los propósitos aquí; consiste en coordenadas x (lon), y (lat) que solo busco desde la dirección al importar nuevos valores a la base de datos.

Simplemente precalcule las distancias entre todas las entidades. Lo almacenaría en una tabla de base de datos propia, con la capacidad de indexar valores.