Optimisation d'une recherche d'emplacement de magasin basée sur la proximité sur un hôte Web partagé?

11

J'ai un projet où j'ai besoin de construire un localisateur de magasin pour un client.

J'utilise un type de publication personnalisé " restaurant-location" et j'ai écrit le code pour géocoder les adresses stockées dans postmeta à l'aide de l' API Google Geocoding (voici le lien qui géocode la US White House en JSON et j'ai stocké la latitude et la longitude en arrière aux champs personnalisés.

J'ai écrit une get_posts_by_geo_distance()fonction qui renvoie une liste de messages dans l'ordre de ceux qui sont les plus proches géographiquement en utilisant la formule que j'ai trouvée dans le diaporama de ce message . Vous pourriez appeler ma fonction comme ça (je commence avec une "source" fixe 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;

Voici la fonction get_posts_by_geo_distance()elle-même:

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

Ma préoccupation est que le SQL n'est pas aussi optimisé que possible. MySQL ne peut pas trier par aucun index disponible car la géo source est modifiable et il n'y a pas un ensemble fini de géos source à mettre en cache. Actuellement, je suis perplexe quant aux moyens de l'optimiser.

En tenant compte de ce que j'ai déjà fait, la question est: comment feriez-vous pour optimiser ce cas d'utilisation?

Ce n'est pas important que je garde tout ce que j'ai fait si une meilleure solution m'oblige à le jeter. Je suis ouvert à envisager presque toutes les solutions, à l' exception de celle qui nécessite de faire quelque chose comme l'installation d'un serveur Sphinx ou tout ce qui nécessite une configuration MySQL personnalisée. Fondamentalement, la solution doit pouvoir fonctionner sur n'importe quelle installation WordPress ordinaire. (Cela dit, ce serait formidable si quelqu'un voulait énumérer des solutions alternatives pour d'autres qui pourraient être plus avancés et pour la postérité.)

Ressources trouvées

Pour info, j'ai fait un peu de recherche à ce sujet, donc plutôt que de faire à nouveau la recherche ou plutôt que de poster l'un de ces liens comme réponse, je vais aller de l'avant et les inclure.

Concernant Sphinx Search

MikeSchinkel
la source

Réponses:

6

De quelle précision avez-vous besoin? s'il s'agit d'une recherche à l'échelle nationale / nationale, vous pouvez peut-être effectuer une recherche lat-lon à zip et avoir une distance précalculée de la zone zip à la zone zip du restaurant. Si vous avez besoin de distances précises, ce ne sera pas une bonne option.

Vous devriez chercher une solution Geohash , dans l'article Wikipédia, il y a un lien vers une bibliothèque PHP pour encoder le décodage lat en geohashs.

Ici, vous avez un bon article expliquant pourquoi et comment ils l'utilisent dans Google App Engine (code Python mais facile à suivre.) En raison de la nécessité d'utiliser geohash dans GAE, vous pouvez trouver de bonnes bibliothèques et exemples python.

Comme l' explique ce billet de blog , l'avantage d'utiliser les geohashes est que vous pouvez créer un index sur la table MySQL sur ce champ.

MikeSchinkel
la source
Merci pour la suggestion sur GeoHash! Je vais certainement le vérifier, mais je pars pour WordCamp Savannah dans une heure, donc je ne peux pas pour le moment. C'est un localisateur de restaurant pour les touristes visitant une ville, donc 0,1 mile serait probablement la précision minimale. Idéalement, ce serait mieux que ça. Je modifierai vos liens!
MikeSchinkel
Si vous souhaitez afficher les résultats dans une carte Google, vous pouvez utiliser leur API pour effectuer le tri code.google.com/apis/maps/documentation/mapsdata/…
Puisque c'est la réponse la plus intéressante, je vais l'accepter même si je n'ai pas eu le temps de faire des recherches et de l'essayer.
MikeSchinkel
9

C'est peut-être trop tard pour vous, mais je vais quand même répondre, avec une réponse similaire à celle que j'ai donnée à cette question connexe , afin que les futurs visiteurs puissent se référer aux deux questions.

Je ne stockerais pas ces valeurs dans la table des métadonnées post, ou du moins pas seulement là-bas. Vous voulez une table avec post_id, lat, loncolonnes, vous pouvez donc placer un index lat, lonet d' interrogation sur ce point . Cela ne devrait pas être trop difficile à maintenir à jour avec un crochet sur la sauvegarde et la mise à jour des publications.

Lorsque vous interrogez la base de données, vous définissez un cadre de délimitation autour du point de départ, afin de pouvoir effectuer une requête efficace pour toutes les lat, lonpaires entre les bordures Nord-Sud et Est-Ouest du cadre.

Après avoir obtenu ce résultat réduit, vous pouvez effectuer un calcul de distance plus avancé (directions circulaires ou réelles) pour filtrer les emplacements qui se trouvent dans les coins de la zone de délimitation et donc plus loin que vous le souhaitez.

Vous trouverez ici un exemple de code simple qui fonctionne dans la zone d'administration. Vous devez créer vous-même la table de base de données supplémentaire. Le code est ordonné du plus intéressant au moins intéressant.

<?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();
Jan Fabry
la source
@Jan : Merci pour la réponse. Pensez-vous que vous pouvez fournir un code réel montrant ces implémentations?
MikeSchinkel
@Mike: C'était un défi intéressant, mais voici un code qui devrait fonctionner.
Jan Fabry
@Jan Fabry: Cool! Je vais vérifier quand je reviendrai sur ce projet.
MikeSchinkel
1

Je suis en retard à la fête sur celui-ci, mais en y repensant, get_post_metac'est vraiment le problème ici, plutôt que la requête SQL que vous utilisez.

J'ai récemment dû faire une recherche géographique similaire sur un site que j'exécute, et plutôt que d'utiliser la méta-table pour stocker lat et lon (ce qui nécessite au mieux deux jointures pour rechercher et, si vous utilisez get_post_meta, deux bases de données supplémentaires requêtes par emplacement), j'ai créé une nouvelle table avec un type de données POINT de géométrie indexée spatialement.

Ma requête ressemblait beaucoup à la vôtre, MySQL effectuant une grande partie du travail lourd (j'ai laissé de côté les fonctions trigonométriques et j'ai tout simplifié en un espace à deux dimensions, car il était suffisamment proche pour mes besoins):

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

où $ client_location est une valeur renvoyée par un service de recherche IP géo public (j'ai utilisé geoio.com, mais il y en a plusieurs similaires).

Cela peut sembler compliqué, mais en le testant, il a systématiquement renvoyé les 5 emplacements les plus proches d'une table de 80 000 lignes en moins de 0,4 sec.

Jusqu'à ce que MySQL déploie la fonction DISTANCE qui est proposée, cela semble être le meilleur moyen que j'ai trouvé pour implémenter les recherches d'emplacement.

EDIT: Ajout de la structure de table pour cette table particulière. C'est un ensemble de listes de propriétés, il peut donc être similaire ou non à tout autre cas d'utilisation.

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 geolocationcolonne est la seule chose pertinente aux fins ici; il se compose de coordonnées x (lon), y (lat) que je viens de rechercher à partir de l'adresse lors de l'importation de nouvelles valeurs dans la base de données.

pommes dorées
la source
Merci pour le suivi. J'ai vraiment essayé d'éviter d'ajouter une table mais j'ai fini par ajouter une table aussi, bien que j'aie essayé de la rendre plus générique que le cas d'utilisation spécifique. De plus, je n'ai pas utilisé le type de données POINT parce que je voulais m'en tenir aux types de données standard les plus connus; Les extensions géographiques de MySQL nécessitent un bon apprentissage pour être à l'aise. Cela dit, pouvez-vous mettre à jour votre réponse avec le DDL de votre table que vous avez utilisée? Je pense que ce serait instructif pour les autres qui liront ceci à l'avenir.
MikeSchinkel
0

Pré-calculez simplement les distances entre toutes les entités. Je stockerais cela dans une table de base de données seule, avec la possibilité d'indexer des valeurs.

hakre
la source
C'est un nombre pratiquement infini d'enregistrements ...
MikeSchinkel
Infinte? Je ne vois que n ^ 2 ici, ce n'est pas infini. Surtout avec de plus en plus d'entrées, la précalcultation devrait être de plus en plus envisagée.
hakre
Pratiquement infini. Étant donné Lat / Long avec une précision de 7 décimales, cela donnerait 6,41977E + 17 enregistrements. Oui, nous n'en avons pas autant, mais nous en aurions beaucoup plus que ce qui serait raisonnable.
MikeSchinkel
Infini est un terme bien défini et y ajouter des adjectifs ne change pas grand-chose. Mais je sais ce que vous voulez dire, vous pensez que c'est tout simplement trop à calculer. Si vous n'ajoutez pas couramment une quantité massive de nouveaux emplacements au fil du temps, ce pré-calcul peut être effectué étape par étape par un travail exécuté en dehors de votre application en arrière-plan. La précision ne change pas le nombre de calculs. Le nombre d'emplacements le fait. Mais j'ai peut-être mal lu cette partie de votre commentaire. Par exemple, 64 emplacements entraîneront 4 096 (ou 4 032 pour n * (n-1)) calculs et donc des enregistrements.
hakre