Otimizando uma pesquisa de localização de loja baseada em proximidade em um host da Web compartilhado?

11

Eu tenho um projeto em que preciso criar um localizador de lojas para um cliente.

Estou usando um tipo de postagem personalizado " restaurant-location " e escrevi o código para geocodificar os endereços armazenados em postmeta usando o Google Geocoding API (veja o link que geocodifica a Casa Branca dos EUA em JSON e eu armazeno a latitude e a longitude de volta para campos personalizados.

Eu escrevi uma função get_posts_by_geo_distance() que retorna uma lista de posts em ordem daqueles que estão mais próximos geograficamente usando a fórmula que encontrei no slideshow neste post . Você pode chamar minha função assim (estou começando com uma "fonte" fixa lat / long):

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;

Veja a função get_posts_by_geo_distance() em si:

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

Minha preocupação é que o SQL seja o mais otimizado possível. O MySQL não pode ordenar por qualquer índice disponível, pois o geo de origem é alterável e não há um conjunto finito de geos de origem para armazenar em cache. Atualmente estou perplexo quanto às formas de otimizá-lo.

Levando em consideração o que já fiz, a pergunta é: Como você faria para otimizar esse caso de uso?

Não é importante que eu mantenha qualquer coisa que eu tenha feito se uma solução melhor me permitir jogar fora. Estou aberto a considerar praticamente qualquer solução , exceto por uma que requer algo como instalar um servidor Sphinx ou qualquer coisa que exija uma configuração personalizada do MySQL. Basicamente, a solução precisa ser capaz de funcionar em qualquer instalação simples do WordPress. (Dito isso, seria ótimo se alguém quisesse listar soluções alternativas para outras pessoas que pudessem ser mais avançadas e para a posteridade.)

Recursos encontrados

FYI, eu fiz um pouco de pesquisa sobre isso, então ao invés de você fazer a pesquisa novamente ou ao invés de você postar qualquer um desses links como uma resposta, eu vou em frente e incluí-los.

Sobre a Pesquisa Sphinx

por MikeSchinkel 18.08.2010 / 01:04

4 respostas

6

Qual precisão você precisa? se for uma pesquisa nacional / estadual, talvez você possa fazer uma consulta de lat-lon para zip e ter uma distância pré-computada da área zip até a área zip do restaurante. Se você precisar de distâncias precisas, isso não será uma boa opção.

Você deve procurar em uma solução Geohash , no artigo da Wikipedia há um link para uma biblioteca PHP para codificar decode lat long para geohashs.

Aqui você tem um bom artigo explicando por que e como eles usam no Google App Engine (código Python, mas fácil de seguir). Devido à necessidade de usar o geohash no GAE, você pode encontrar algumas boas bibliotecas e exemplos python.

Como esta postagem no blog explica, a vantagem de usar geohashes é que você pode criar um índice na tabela MySQL nesse campo.

    
por Chedar 20.08.2010 / 17:45
9

Isso pode ser tarde demais para você, mas vou responder de qualquer maneira, com , para que os futuros visitantes possam se referir a ambas as perguntas.

Eu não armazenaria esses valores na tabela de postagem de metadados, ou pelo menos não somente . Você deseja uma tabela com post_id , lat , lon colunas, para poder colocar um índice de lat, lon e consultar sobre isso. Isso não deve ser muito difícil manter-se atualizado com um gancho na postagem salvar e atualizar.

Quando você consulta o banco de dados, você define uma caixa delimitadora ao redor do ponto de partida, assim você pode fazer uma consulta eficiente para todos os lat, lon pares entre as fronteiras Norte-Sul e Leste-Oeste a caixa.

Depois de obter este resultado reduzido, você pode fazer um cálculo de distância mais avançado (direções de direção circulares ou reais) para filtrar os locais que estão nos cantos da caixa delimitadora e, portanto, mais distantes do que você deseja.

Aqui você encontra um exemplo de código simples que funciona na área administrativa. Você precisa criar a tabela de banco de dados extra você mesmo. O código é ordenado do mais para o menos interessante.

<?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();
    
por Jan Fabry 07.10.2010 / 23:04
1

Estou atrasado para a festa, mas olhando para isso, o get_post_meta é realmente o problema aqui, em vez da consulta SQL que você está usando.

Recentemente tive que fazer uma pesquisa geográfica similar em um site que eu corro, e em vez de usar a meta-tabela para armazenar lat e lon (o que exige, na melhor das hipóteses, duas junções para procurar e, se você estiver usando get_post_meta, duas consultas de banco de dados adicionais por local), criei uma nova tabela com um tipo de dados POINT de geometria indexada espacialmente.

Minha consulta se parecia muito com a sua, com o MySQL fazendo muito trabalho pesado (deixei de fora as funções trigonométricas e simplifiquei tudo para o espaço bidimensional, porque estava perto o suficiente para os meus 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 );
}

em que $ client_location é um valor retornado por um serviço de pesquisa de IP geo público (usei geoio.com, mas há vários outros semelhantes.)

Pode parecer difícil, mas ao testá-lo, retornou consistentemente os 5 locais mais próximos de uma tabela de 80.000 linhas em menos de 4 seg.

Até o MySQL lançar a função DISTANCE que está sendo proposta, essa parece ser a melhor maneira que encontrei para implementar pesquisas de localização.

EDIT: Adicionando a estrutura da tabela para esta tabela em particular. É um conjunto de listagens de propriedades, portanto, pode ou não ser semelhante a qualquer outro 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))
)

A coluna geolocation é a única coisa relevante para os propósitos aqui; consiste em coordenadas x (lon), y (lat) que eu acabei de procurar a partir do endereço ao importar novos valores para o banco de dados.

    
por goldenapples 25.02.2011 / 22:49
0

Apenas pré-calcule as distâncias entre todas as entidades. Eu armazenaria isso em uma tabela de banco de dados por conta própria, com a capacidade de indexar valores.

    
por hakre 18.08.2010 / 08:40