50000

Оптимизиране на MySQL заявки при геолокализирано приложение

Навярно повечето от вас знаят, че се занимавам със сайта fuelo.net и на мен се стоварват всички технически проблеми. В този пост искам да споделя два от основните проблемите пред подобен род приложения – силно зависими от местоположението на потребителите, и как съм ги разрешил.

1. Намиране на най-близките N обекта (в нашия случай бензиностанции).

Във fuelo използваме MySQL за основен database и една от първите ми оптимизации беше да upgrade-нем до версия 5.7, където има доста подобрения и готови функции, свързани с геолокацията. Първоначално всички заявки свързани с определяне на бензиностанции наблизо бяха нещо от рода на :

$sql = "SELECT *, (6371 * acos( cos( radians(".$lat.") ) * cos( radians(`lat`) ) * cos( radians(`lon`) - radians(".$lon.") ) + sin( radians(".$lat.") ) * sin( radians(`lat`) ) ) ) AS `distance` FROM `gasstations` HAVING `distance` < ".$distance." ORDER BY `distance` ASC";

забележка: всички примери ще бъдат на PHP, а заявките са опростени (без WHERE и LIMIT клаузи) с цел прегледност.

Както виждате тук дори не се използва stored procedure, а цялата haversine формула се изчислява при всяка заявка. Това при малък ненатоварен сайт с неголяма база данни (напр. до 1000 обекта) на практика работи и се използва доста често. Повечето tutorials в интернет препоръчват именно тази формула. Първата ми идея за MySQL 5.7 беше именно да заменим тази формула с вградената (от версия 5.7.6) функция ST_Distance_Sphere. Така горната заявка се свива до:

$sql = "SELECT *, ST_Distance_Sphere(POINT(`lon`, `lat`), POINT(".$lon.", ".$lat."), 6371) AS `distance` FROM `gasstations` HAVING `distance` < ".$distance." ORDER BY `distance` ASC";

Така изчислението на теория (и на практика) става много по-бързо. Забележете, добавения трети параметър на функцията ST_Distance_Sphere, който преобразува изчислението в km, а не в метри както е по подразбиране. Това ни се наложи, за да запазим съвместимостта със функциите, които извикваха тази заявка, а те очакват резултата в километри.
На пръв поглед всичко изглежда супер, но на практика не е. Тази функция наистина изчислява възможно най-бързо разстоянието между две точки, но не използва индекси и затова все пак трябва да обходи всички редове в таблицата, за да подреди резултатите по разстояние. При все по-голяма база (при нас като наближихме 50000 бензиностанции), тази заявка също започна да става бавна. Започнах да мисля как да огранича резултатите, за които се изчислява разстоянието. Както се вижда от заявките (почти) винаги има ограничение в разстоянието (HAVING `distance` <  X) и се зачудих как мога да превърна това X в координати и така да огранича резултатите още преди да започне изчислението и сортирането. Така намерих тази статия (Finding Points Within a Distance of a Latitude/Longitude Using Bounding Coordinates by Jan Philip Matuschek), в която на теория много добре е описан точно моя проблем. Има и source код на Java, както и линкове за други програмни езици, включително и PHP. Това беше точно каквото ми трябваше. Като използвам тази библиотека кода придобива следния вид:

$edison = Geolocation::fromDegrees($lat, $lon);
$coordinates = $edison->boundingCoordinates($distance, 'km');
$lat_min = $coordinates[0]->getLatitudeInDegrees();
$lon_min = $coordinates[0]->getLongitudeInDegrees();
$lat_max = $coordinates[1]->getLatitudeInDegrees();
$lon_max = $coordinates[1]->getLongitudeInDegrees();

$sql = "SELECT *, ST_Distance_Sphere(POINT(`lon`, `lat`), POINT(".$lon.", ".$lat."), 6371) AS `distance` FROM `gasstations` WHERE `lat` > '".$lat_min."' AND `lat` < '".$lat_max."' AND `lon` > '".$lon_min."' AND `lon` < '".$lon_max."' HAVING `distance` < ".$distance." ORDER BY `distance` ASC";

Така вече заявката беше доста по-бърза, обхождаше доста по-малко редове, което подобри работата на MySQL и сървъра като цяло. Аз обаче не се спрях до тук. Хрумна ми как да се възползвам от spatial индекса на MySQL. Първо направих ново поле в таблицата gasstations с име coords и тип POINT. Попълних новото поле от другите две полета, които вече имах, lat и lon , чрез заявката UPDATE `gasstations` SET coords = Point(lon, lat); и след това направих полето spatial index. След тази промяна бях готов за последната ми (за сега) SQL заявка за намиране на най-близките бензиностанции:

$edison = Geolocation::fromDegrees($lat, $lon);
$coordinates = $edison->boundingCoordinates($distance, 'km');
$lat_min = $coordinates[0]->getLatitudeInDegrees();
$lon_min = $coordinates[0]->getLongitudeInDegrees();
$lat_max = $coordinates[1]->getLatitudeInDegrees();
$lon_max = $coordinates[1]->getLongitudeInDegrees();

$sql = "SELECT *, ST_Distance_Sphere(`coords`, POINT(".$lon.", ".$lat."), 6371) AS `distance` FROM `gasstations` WHERE ST_Within(`coords`, ST_MakeEnvelope(Point(".$lon_min.", ".$lat_min."), Point(".$lon_max.", ".$lat_max."))) HAVING `distance` < ".$distance." ORDER BY `distance` ASC;

Същността тук е функцията ST_Within(), която се възползва от spatial index-а на coords и филтрира резултатите още по-бързо. Функцията ST_MakeEnvelope създава “квадрат”, по две крайни точки, в който се ограничава търсенето.

За сега това ми е решението за намиране на най-близките бензиностанции. Не мога да дам сравнителни стойности, защото междувременно условията много се променяха, но на практика нещата вървят много по-добре. Бавните заявки намаляха и натоварването на сървъра спадна.

2. Изобразяване на голям брой обекти на карта

Във fuelo използваме Google Maps за визуално представяне на бензиностанциите на карта. В началото беше лесно – малко обекти – просто показвай всички на картата. След време, както всички, започнахме да използваме js marker clusterer. Така обаче прехвърляме тежките изчисления върху клиента и когато той реши да unzoom-не за да види всички бензиностанции в Европа, може направо да му забие browser-а и/или компютъра. Започнах да търся сървърно решение за clustering на обекти. Решението, което използваме в момента, се нарича geohash. MySQL поддържа geohash функции и с тяхна помощ заявката за server-side clustering става нещо подобно:

$sql = "SELECT `id`, `brand_id`, AVG(lat) as avglat, AVG(lon) as avglon, substring(`geohash`, 1, ".$precise.") as cluster_hash, count(*) as cluster_count
FROM `gasstations`
WHERE ST_Within(`coords`, ST_MakeEnvelope(Point('.$lon_min.', '.$lat_min.'), Point('.$lon_max.', '.$lat_max.')))
GROUP BY `cluster_hash`";

За целта Ви трябват няколко неща:

  • поле geohash (при мен VARCHAR(9) ) в таблицата gasstations, което предварително е попълнено със ST_GeoHash() функцията (и не забравяйте да го update-вате винаги, когато промените координатите на обекта ! )
  • $lon_min, $lat_min, $lon_max и $lat_max , които лесно може да вземете за видимата част на картата от google maps API-то
  • $precise – колко прецизно да е клъстерирането. Основно зависи от zoom level-а на картата и може да си го нагласите според вашите нужди

При изпълнение на заявката получавате всичко необходимо за визуализиране на картата и не е необходимо на използвате client-side clustering:

  • cluster_count е броя обекти в клъстера – ако е 1, значи е само една бензиностанция и може да покажете пинче в зависимост от нейната brand_id. Ако е повече от 1 значи има повече от една бензиностанция в района и показвате клъстерна иконка с цифричка cluster_count, която показва броя.
  • avglat и avglon са средноаритметично от координатите на бензиностанциите и така може да позиционирате клъстерната иконка на “по-правилно” място. Иначе, от самата специфика на geohash алгоритъма, Земята се разделя на правоъгълници и клъстерите Ви ще се наредят като в решетка. Разбира се ако cluster_count e 1, avglat и avglon са координатите на самата бензиностанция.

 

Това са решенията и заключенията до които стигнах за тези два проблема и ще се радвам, ако съм полезен на някой.

25070316529_68b9315cfe_k

Божидар на две

Вчера Божидар стана на две години. Да, наистина – две. За мен също е невероятно колко бързо минаха две години. Особено втората.
За втория рожден ден много се чудихме какво да правим и в крайна сметка решихме да го измислим на момента. Добре се случи, че вчера беше доста слънчев ден в Пловдив. Аз си бях взел почивен ден и с Божидар и една негова приятелка от блока (Йоанка), заедно с майките отидохме на главната. Там малките тичаха, караха колички, возеха се на въртележка, играха на детска площадка, гониха гълъби … въобще мисля, че много добре се получи. Радваха се и бяха навън. Вечерта бяхме поканили баба, дядо и леля и си направихме семейно празнуване. Ето малко снимки във flickr:

Рожден ден Божидар

p.s. лопатата му е новата играчка и никъде не излиза без нея. Може да видите разликата в настроението му преди и след като му я подариха 🙂

новогодишно сърце

Нова година

Честита нова година ! Макар и с голяма закъснение 🙂 Вилито само ме пита защо не пиша в блога и ето пиша! След две годишно прекъсване отново посрещнахме новата година на Мандрица. Събрахме се с Вени и Ники и другия Ники (на който Божидар казва не-не-не) и си изкарахме много добре. То беше някакъв невиждан студ за Мандрица, та повече си стояхме вкъщи. А на самата нова година едвам отидохме до Букор Щепи и веднага бързахме да се върнем. Не знам минус колко беше, но се усещаше наистина много студено. Единия ден имаше дори малко сняг, а накрая (като си тръгвахме) и доста повече. От баницата ми се падна берекет, на Вили здраве, а на Божидар хармония, така че мисля, че ще сме добре и тази година 🙂 Иначе си е хубаво на Мандрица! Тази година повече, а пък ако прекараме и интернет, направо … 🙂

А снимки може да видите в (изненада!) нашите снимки.

malkata kniga

Малката книга

Вчера завърших Малката книга на Георги Мерджанов (или просто Жоро) и бързам да споделя впечатленията си. А те хич не са малко. В началото тръгнах леко скептично към книга, която се рекламира че “в нея има от всичко”. Започва съвсем нормално като почти любовна история на младежи в съвременна София. Постепенно Жоро е вкарал много религия, митология, история (много история) … а романа придобива форма на истински екшън с много обрати и разкриване на истинската самоличност на героите (която ще Ви изненада). На моменти започваш да се луташ във времето и пространството. В същия момент осъзнаваш, че се намираш тук и сега из уличките на София. В края на книгата разбираш, че всички митове и легенди не са някаква измислица, а реалност и нищо чудно ти самия да си станал част от тях без дори да го осъзнаваш. Всичко е чудесно вплетено в нашето ежедневие и звучи много реално. Особено за хората от София всички места, където се развива действието, ще им се струват още по-близки и познати. На мен това малко ми убягна, защото не познавам добре София. Като цяло препоръчвам да намерите и прочетете Малката книга, която хич не е малка! Браво, Жоро ! Много успехи и с още много книги да ни зарадваш !

п.с. книгата си има и страхотен трейлър:

XI Толкин фест

Събитието на Вили за тази година беше Толкин феста, който може би нямаше да се състои, ако тя не беше се захванала. В крайна сметка той се състоя на 20-22 септември в почивна база Металик (в местността Студенец). Неделната сутрин на 20-ти оставихме Божидар на баба му в Кричим и с Вили тръгнахме към хижата. По пътя разбрахме, че останалите от феста имат среща на Билата на гарата, и ние решихме да отидем за да вземем някои с колата, да не се качваме само двамата. Общо взето целия Толкин фест се събрахме в 3 коли. Както отбеляза Асен, поне бройката на хората беше повече от номера на феста (с един) 🙂 Отидохме, настанихме се, хижата беше стара, но ремонтирана и стоите бяха чисти с нови дограми и бани. Заедно с нас имаше и събиране на Менса, но за тях нищо няма да кажа. Както казах хижата беше реновирана, но хижарите – не. Държаха се меко казано отвратително ! Първо почти ни изнудиха да си платим пълен пансион, а тези които не искаха храна (например вегетарианци) трябваше да изчакат на всички да се сервира и десерта и чак тогава въобще да им вземат поръчките (а менюто беше на необосновано завишени цени!). Отделно ни се накарах, че нямаме никаква организация, нямаме списък … дори не ни дадоха зала, където да си проведем феста, защото не сме били сигурни, а на Менса им взимал пари за залата. Въобще такива соц дребно тарикати, които само мислят да не се минат за нищо, не бях срещал отдавна ! Впоследствие дори разбрах, че бил казал да не сме момчета и момичета в една стая.
На фона на проблемите с хижара, феста премина повече от добре. Липсата на зала ни изпрати на близка поляна, където се изнесоха лекциите, а какво по-хубаво от това да слушаш за Толкин под дърветата! Най яката част за мен, въпреки че аз не участвах, беше ролевата игра, която се игра (по план трябваше дори да са 3, но времето и за една не стигна). Отделно който искаше имаше дуели с мечове и стрелби с лък. Единствено не можаха да се състоят заниманията, които изискваха стая, като например прожектиране на филми, за което аз дори мъкнах проектор и колонки.
Аз съм най доволен, че Вили най-накрая се забавляваше истински и успя за един ден да се откъсне напълно от (мислите за) Божидар. Изкарахме си хубаво. Направихме и една разходка из гората.

XI Толкин фест

Tsarevo2015

Царево 2015

За втора поредна година изкарахме семейната отпуска на Царево. Миналата седмица отново бяхме в Царево с Божидар. Тази година вече гледаше морето по-малко стреснато и дори последните дни се отпусна да отива към водата и да ходи спокойно по пясъка (което му беше малко неприятно в началото). Първите три дни дори ни бяха “на гости” Софи и Жоро и се видяхме и с тях. Като цяло вече две години сме доволни от комплекс Bay View, където в големите апартаменти спокойно могат да се настанят 4 възрастни и дете.
Добре си изкарахме – времето беше слънчево, морето се поуспокои последните (въпреки че плажа на Царево беше почти изяден от морето), хапнахме разни риби … но все пак си беше градско преживяване. С малко дете няма как – търсим все още разни удобства на града. Догодина вече се надявам да отидем и някъде на къмпинг.

Снимки във flickr:

Царево 2015

Промени

Как се променят нещата само. Всъщност не е изненада, че се променят а скоростта с която се променят. Само до преди година и няколко месеца Божидар все още го нямаше, а от както се появи веднага приоритетите се променят. Вече дори като сме на почивка (или планираме такава), не се интересуваме дали ни е харесало, а на него дали му е добре (справка седмицата в Мандрица от предишния пост). Дори като съм плажа преди си мислех че е пълно с topless мадами, а сега гледам че е пълно с деца. Само ги гледам и си мисля – колко си са големи, какво правят, сравнявам ги с нашия … или дори гледам с какви колички са. Просто до толкова Божидар и всичко около него ни е влезнало в главата.
От няколко поста си мисля да вмъкна тези мисли, но все нещо става и ги оставям по-сухи. Сега просто си дойде времето и мястото и то в отделен пост. Всичко си идва на време.

Промените са хубаво нещо.

п.с. откакто се е родил Божидар не съм си включил алармата за събуждане нито веднъж и дори съм спокоен, че няма да закъснея за работа. А преди спях до много късно.

Седмица на Мандрица

Днес се върнахме след една седмица отпуска, която изкарах като истинска почивка, на Мандрица. Беше много хубаво, особено за Божидар, който направо не можехме да го приберем от всички животни, които искаше да гледа на село. Постоянно искаше навън и ние му го дадохме. Мисля, че много се забавляваше. Ние с Вили също успяхме да си починем добре. Добре ни се получи тази почивка в края на май. Имаше и големи жеги и по-прохладни дни.

17154275373_01564d900b_k

Християнче

Днес кръстихме Божидар. Като цяло, бях много притеснен за този ден, но всичко мина много по-добре отколкото очаквах. Посрещнахме много гости, и не на шега си казвахме, че кръщенето си е половин сватба. Естествено, бях най-притеснен за това как ще се държи Божидар, особено след многото драматично-ревливи истории, които бях чул. За голяма радост той беше много послушен. Дори, когато го потопиха във водата на купела, той по-скоро беше доволен – усмихваше се и риташе. Единствено нададе глас когато му режеха от косата, но само толкова, колкото да покаже, че все още е бебе. Всъщност, най-голямото ми притеснение беше как Божидар ще стои при Ники (кръстника му), но това не се наложи. Попът разреши детето да бъде в майка си през цялото време. Така Божидар стоеше сравнително кротко.
Кръщенката направихме в църквата “Св. св. Кирил и Методий“, която е много хубава, а и попът ни направи добро впечатление още когато заведохме Божидар на 40 дена. След официалната част отидохме на почерпка в ресторант “Хитър Петър”, където пък беше и нашата сватба. Както написах и в началото – всичко се получи много добре. Ето и няколко снимки:

17154275373_01564d900b_k

17774645095_5852325f79_k

17152044504_4b2501cb0d_k

17154181393_1173df5be2_k