Valsts noteikšana pēc ip adreses, optimizēta pieeja.

[Maris-S]

Tātad sakarā ar šo: http://php.lv/f/topic/17678-ko-jus-sakat-par-sadu-lietu nolēmu pa saviem seniem materiāliem atrast valsts noteikšanas pēc ip adreses optimizāciju. Uzreiz jāpiebilst ka šādu lietu taisīt ir aktuāli kad valsti jānosaka ļoti bieži vai uzreiz jānosaka valsti vairākām ip adresēm, tad optimizācija būs jūtama ar neapbruņotu aci. Principā optimizācija paātrina vaicājumu izpildi pat vairākus desmitus reizes, bet nu tas protams atkarīgs arī no procesora ātruma utt. Vēl varētu piebilst ka šī optimizācija nebūs tik ātra kā taisīt dll/so MySqlam ar funkciju kas no sakārtota masīva meklēs valsti pēc binārās meklēšanas algoritma, bet tomēr šo optimizāciju var izmantot uz jebkura servera, jo nevajadzēs neko papildus instalēt, jo būs izmantotas tikai MySql iespējas. Vēl viena lieta, kas ir uzreiz jāpiezīmē, tā ir datubāzes izmēra palielināšanās, tabula iptocountry būs lielāka, bet ņemot vērā mūsdienu datu nesēju ietilpības un serveru nomas cenas, to diez vai kāds pamanīs.

 

Ideja ņemta šķiet no šejienes (jau neatceros): http://ip-to-country.webhosting.info/node/view/384 un pārtaisīta, lai varētu ģenerēt jaunu tabulu tikai ar sql.

 

Uzreiz atvainojos ka viss kods ir šeit un sanāk diezgan garš rakstiņš.

 

Tātad sāksim ar iptocountry datubāzi. To neaprakstīšu kā dabūt un kā csv ieimportēt pašā datubāzes tabulā, to domāju katrs varēs paveikt paša spēkiem. Vienīgi piebildīšu ka es šo tabulu nosaucu par iptocountry un tai ir sekojoši lauki:

 

CREATE TABLE `iptocountry` (
 `fromip` varchar(15) COLLATE utf8_bin NOT NULL,
 `toip` varchar(15) COLLATE utf8_bin NOT NULL,
 `fromaddr` int(10) unsigned NOT NULL,
 `toaddr` int(10) unsigned NOT NULL,
 `code` varchar(2) COLLATE utf8_bin NOT NULL,
 `name` varchar(128) COLLATE utf8_bin NOT NULL
) ENGINE=MyISAM DEFAULT CHARSET=utf8 COLLATE=utf8_bin

 

Tātad šajā tabulā arī importējam visus ip un valstu datus.

 

Galvenā ideja ir ļaut MySql izmantot indeksus, ko man šķiet viņš nevar izdarīt ar operācijām lielāks mazāks (>, <). Tādai optimizācijai mums būs nepieciešama klāt vēl viena kolona, es to nosaukšu bit, kas saturēs pirmos bitus ip adreses skaitliskajām vērtībām. Šajā piemērā es ņēmu tieši 15 bitus. Ko vairāk bitu to ātrāk būtu jāstrādā, bet būs lielāka tabula, jo būs vairāk papildus ieraksti. Tātad šajā gadījumā tabulai jābūt datiem saliktiem tā, lai viena apgabala (vienas rindiņas) fromaddr un toaddr pirmie 15 biti būtu vienādi, t.i. kur šis apgabals ir pārāk liels un toaddr pirmie 15 biti atšķirsies no fromaddr būs jādala divās vai vairākās rindiņās.

 

Koloniņai bit obligāti jātaisa indekss. Kā jau no šī visa var noprast tad meklēšana sākumā tiks veikta bit koloniņā, izmantojot indeksu, tad tiks salīdzināti fromaddr un toaddr ar parasto lielāks un mazāks (>= un <=) vai arī between, kā kuram patīk.

 

Tātad sākumā izveidosim tabulu, kurā ievietosim iptocountry tabulas vērtībām, sadalot lielos apgabalus mazākos, kur nepieciešams, nosaukšu šo tabulu par iptocountry_15:

 

CREATE TABLE `iptocountry_15` (
 `bit` int(10) unsigned NOT NULL,
 `fromip` varchar(15) COLLATE utf8_bin NOT NULL,
 `toip` varchar(15) COLLATE utf8_bin NOT NULL,
 `fromaddr` int(10) unsigned NOT NULL,
 `toaddr` int(10) unsigned NOT NULL,
 `code` varchar(2) COLLATE utf8_bin NOT NULL,
 `name` varchar(128) COLLATE utf8_bin NOT NULL,
 KEY `I_bit` (`bit`)
) ENGINE=MyISAM DEFAULT CHARSET=utf8 COLLATE=utf8_bin

 

Tagad, lai sadalītu lielākos apgabalus būs nepieciešama vēl viena tabuliņa, kas saturēs vienu koloniņu un tiks aizpildīta vienkārši ar veseliem skaitļiem, tabula numbers_15:

 

CREATE TABLE `numbers_15` (
 `number` int(10) unsigned NOT NULL,
 PRIMARY KEY (`number`)
) ENGINE=MyISAM AUTO_INCREMENT=113665 DEFAULT CHARSET=utf8 COLLATE=utf8_bin

 

Izveidojam procedūru, kas aizpildīs tabulu ar veseliem skaitļiem, procedūra arī noteiks mazāko un lielāko vērtību, ko tur ir jāieliek.

 

CREATE PROCEDURE generate_numbers()
BEGIN
declare F int;
declare T int;
declare nr int;

 set F = (SELECT MIN(fromaddr>>15) FROM iptocountry);
 set T = (SELECT MAX(toaddr>>15) FROM iptocountry);
set nr = F;

 WHILE (nr >= F) and (nr <= T) DO
   INSERT into numbers_15 VALUES (nr);
   SET nr = nr + 1;
 END WHILE;
END

 

Palaižam procedūru un tā aizpildīs tabulu numbers_15 ar vajadzīgām vērtībām. Ņemiet vērā ka sākumā man procedūras palaišana izdeva dīvainu kļūdu, nekur viņu nepierakstīju, bet līdzēja thread_stack mainīgā palielināšana uz 180K my.ini failā. Man liekās ka šī vērtība atkarīga instalācijas sākotnējās konfigurācijas laikā.

 

Tagad kad ir aizpildīta tabula ar numuriem, mēs varam izveidot jauno iptocountry_15 tabulu, izmantojot numbers_15.

 

insert into iptocountry_15
select
 fromaddr>>15 bit,
 fromip,
 toip,
 fromaddr,
 toaddr,
 code,
 `name`
from
 iptocountry
where
 fromaddr>>15 = toaddr>>15
union
select
 b.number bit,
 if (a.fromaddr>b.number<<15, inet_ntoa(a.fromaddr), inet_ntoa(b.number<<15)) fromip,
 if (a.toaddr<((b.number+1)<<15)-1, inet_ntoa(a.toaddr), inet_ntoa(((b.number+1)<<15)-1)) toip,
 if (a.fromaddr>b.number<<15, a.fromaddr, b.number<<15) fromaddr,
 if (a.toaddr<((b.number+1)<<15)-1, a.toaddr, ((b.number+1)<<15)-1) toaddr,
 a.code,
 a.`name`
from
 iptocountry a, numbers_15 b
where
 fromaddr>>15 <> toaddr>>15 and
 b.number between (a.fromaddr>>15) and (a.toaddr>>15)
order by
 fromaddr

 

 

Šīs lietas izpildās ne visai ātri uz lēnākiem datoriem.

 

Tagad mums ir jauna tabula iptocountry_15, kurai pirmā kolona bit noderēs, lai izmantotu indeksu vaicājumos. Pārbaudei izveidosim jaunu tabulu ar vienu kolonu, kas saturēs dažādas ip adreses. Es tās paņēmu no šīs lapas: http://www.ipspotting.com un saliku tās tabulā, kopā 50 ip adreses.

 

CREATE TABLE `ip_addresses` (
 `ip` varchar(15) COLLATE utf8_bin NOT NULL
) ENGINE=MyISAM DEFAULT CHARSET=utf8 COLLATE=utf8_bin

 

Sākumā izmantosim standarta vaicājumu ar tabulu iptocountry, bez optimizēšanas. Tātad veidojam vaicājumu, kas nosaka valsti, visām tabulā ievietotajām ip adresēm, tātad jānosaka 50 valstis.

 

select sql_no_cache
a.ip,
b.name
from
ip_addresses a
left join iptocountry b on
inet_aton(a.ip) between b.fromaddr and b.toaddr

 

Vaicājuma izpildes laiks 17.902 sekundes. Diezgan ilgi. Tagad darām to pašu, tikai izmantojot bit tabulā iptocountry_15.

 

select sql_no_cache
a.ip,
b.name
from
ip_addresses a
left join iptocountry_15 b on
b.bit = inet_aton(a.ip) >> 15 and
inet_aton(a.ip) between b.fromaddr and b.toaddr

 

Vaicājuma izpildes laiks 0.001 sekunde. Principā par ātru sanāca, cik atceros pirmo reizi kad šo izmēģināju uz mazāk jaudīga datora panāk izpildes laiku sekundes desmit tūkstošajās daļās nesanāca.

 

Visu šo sarakstīju pēc materiāliem, kurus labu laiku nepētīju, tāpēc ceru ka nekur nekļūdījos, bet pēc abu vaicājumu rezultātiem izskatās ka strādā pareizi, tāpēc ja pamanāt kļūdas, kam būs pacietība pētīt, rakstiet.

Edited November 24, 2010 by Maris-S

[Martiny]

Par šo pašu tēmu kaut ko līdzīgu atradu šeit:

http://www.hotscripts.com/listing/hazard-ip-country-detection/

un

http://joejacobs.org/software/hazard-ip-country-detection/

Lai Jums izdodas!

[marrtins]

Ideja par MySQL laba. Praktiski tādu pašu ideju (Uzparsēti IP apgabali no whois-data no visiem reģistriem, sasortēti, samergoti un binary search pa virsu) izmantoju ip2country.hackers.lv, tiesa gan, taisīju ar C un uztaisīju arī PHP extension (counter.hackers.lv vajadzībām vajag ļooooti labu performanci). Augstāk aprakstītais varētu ļoti labi derēt parastām lapām vai kur nav iespēja likt savus extensionus. Citādi tā defaultā ip->country datubāze ir izsmiekls, ja vajag sameklēt vairāk pa 10 IP :D

 

Te mēs biki mērījāmies:

http://php.lv/f/topic/12005-kadus-darba-efektivitates-tulus-izmantojat/page__view__findpost__p__96078

[Maris-S]

Es arī pamēģināju noteikt valstis lielajam ip adrešu sarakstam, ar optimizēto pieeju izpildijās ~1.07 sekundēs, bez optimizācijas jau kādu pus stundu vaicājums notiek, vēl nav izpildījies.

[Maris-S]

Nu arī neoptimizētais variants izpildījās. Ar to sanāca 6720.030 sekundes.

[marrtins]

Labs! :)

[codez]

Galvenā ideja ir ļaut MySql izmantot indeksus, ko man šķiet viņš nevar izdarīt ar operācijām lielāks mazāks (>, <).

 

Tabula:

ips

---

from

to

country

 

 

Mysql māk izmanto indeksus uz operācijām > un <. Problēma rodas, tad, ka ieraksta kveriju

SELECT * FROM ips WHERE `from`<=$ip AND `to`>=$ip;

Ja ir uzlikts BTREE indekss uz from,to, tad izvēloties mazu ip vērtību, mysql no visiem, kur from<=$ip (un to ir daudz) jāatrod visi, kuram to>=$ip, tas nozīmē, ka jāpārskannē visa tabula.

 

Mysql nezin, ka tie ir intervāli un nezin, ka tikai pirmais, kuram from<$ip, var būt derīgs.

Tāpēc vienkārši pasakam, dod mums pirmo

SELECT * FROM ips WHERE `from`<=$ip and `to`>=$ip ORDER BY `from` LIMIT 1.

Šis kverijs pilnā tabulā izpildās zem 1ms.

Izņemot gadījumu, kad dotā ip adrese neatbilst nevienam intervālam. Šādā gadījumā mysql serverim jāparmeklē visi from<$ip varianti (pils tabulas skans).

 

To mēs apejam šādi:

SELECT * FROM ips WHERE `from`<=$ip ORDER BY `from` LIMIT 1.

šijā gadījumā mysql atgriež pirmo intervālu, kuram from<$ip. Pēc kverija pārbaudam, ja to>=$ip, tad atbilstošais intervāls der, ja nav, tad ip adrese neatbilst nevienam no intervāliem.

 

Piemēram, ja ir intervāli

from to

10 20

30 40

50 60

 

Ja mēs izvēlamies 45, tad tiek atrast ieraksts 30-40, tā kā 45>40, tad ip adrese neatbilst nevienam intervālam.

Ja izvēlamies 15, tad tiek atrast ieraksts 10-20, tā kā 15<=20, tad ip adrese atbilst šim intervālam.

 

Visa māksla un nav nekas jāsarežģī.

[Maris-S]

Codez, paldies par skaidrojumiem. Vienīgi nesanāk izprast līdz galam. Nav gadījumā kļūda šajā vaicājumā?

 

SELECT * FROM ips WHERE `from`<=$ip ORDER BY `from` LIMIT 1

 

Vai nevajadzētu zīmei <= būt uz otru pusi?

 

SELECT * FROM ips WHERE `from`>=$ip ORDER BY `from` LIMIT 1

 

It kā loģiku es sapratu, ja neskaita to zīmi uz kuru pusi viņu likt. Ar joinu manējo vaicājumu nesanāca sataisīt, tāpēc sataisīju to šādā veidā:

 

select sql_no_cache
a.ip,
(select `name` from iptocountry where fromaddr >= inet_aton(a.ip) order by fromaddr limit 1)
from
ip_addresses a

 

Te zīme ir jau pamainīta, ja ieliek tur <= tad protams viņš momentā izpildās (ja ir indekss), bet rezultāts ir nepareizs, jo katru reizi tiek atgriezts pirmais ieraksts, kā tam arī jābūt.

 

Vaicājums izpildās ļoti lēnu, jau kādas 30 minūtes un rezultāta nav. Apstādināju vaicājumu un paskatījos kādi ir pirmie rezultāti, izrādījās ka nav pareizi. Parunāju par šo lietu ar kolēģi un pēc viņa domām šādam vaicājumam sākumā izpildīsies where un tikai tad tiks veikta kārtošana, būtībā pēc iegūtiem rezultātiem tā tas patiešām arī varētu būt.

 

Sataisīju arī atsevišķu vaicājumu lai pārbaudītu cik pareizi strādā:

 

select `name` from iptocountry where fromaddr >= inet_aton('24.100.14.0') order by fromaddr limit 1

 

Rezultāts tomēr nav pareizs, protams arī ar <= nestrādā pareizi, bet nu tas ir saprotami. Atgriež Kanādu, bet jābūt United States.

 

Ko es īsti neesmu sapratis?

[Maris-S]

Jā un indeksus MySql patiešām var izmantot arī ar < un >

[codez]

indeks ir uzlikts uz from lauka?

Ja ir indeks uz from lauka un order ir pēc from, tad viņš neko nekārto, jo indeksā šis lauks ir sakārtots. Atliek tikai pateikt LIMIT 1 - atgriezt pirmo ierakstu, kur from<=meklejamais_ip

Būtībā šo pirmo ierakstu mysql atrod O(log2(n)) laikā.

[Gints Plivna]

Jā un indeksus MySql patiešām var izmantot arī ar < un >

AFAIK visas saprātīgas datubāzes spēj izmantot indeksus ar =, >, >=, <, <=, bet parasti nespēj ar <>.

 

Protams, ir jautājums par to vai indeksa izmantošana vispār ir izdevīga, t.i., vai labāk nav izmantot pilnu tabulas pārlasi. Katrā DBVS ir lieta, kas saucās apmēram vaicājumu optimizators, kas redzot SQL teikumu, ievērtējot datu sadalījumu un vides konfigurāciju nolemj, kas katrā gadījumā ir izdevīgāks, vai ir vērts indeksu lietot vai nē.

Protams, ka:

1) optimizators skatās uz tādām vai citādām tabulu statistikām, kas ne vienmēr ir up to date, tāpēc lēmums var būt nekorekts dēļ tā

2) optimizators ir cilvēka rakstīts algoritms, kas nav perfekts un var pieņemt ne to pašu labāko lēmumu

3) cilvēkiem parasti ir tendence domāt, ka lietot indexus ir labi un izmantot pilnu tabulas pārlasi slikti, bet ne vienmēr tā ir, pareizāk sakot, itin bieži ir tā, ka indekss->tabula tikai traucē. Tas ir atkarīgs no vairākiem faktoriem, atlasāmo ierakstu skaita vs kopējais ierakstu skaits tabulā, ierakstu fiziskais novietojums datu blokos (vai visi ieraksti ar vienu un to pašu meklējamo kolonas vērtību ir novietoti kompakti kopā, vai arī izmētāti pa visiem datu blokiem tabulā) utml.

 

Gints Plivna

http://datubazes.wordpress.com

[Maris-S]

Codez, indekss ir pielikts. Reku tabulas DDL:

 

CREATE TABLE `iptocountry` (
 `fromip` varchar(15) COLLATE utf8_bin NOT NULL,
 `toip` varchar(15) COLLATE utf8_bin NOT NULL,
 `fromaddr` int(10) unsigned NOT NULL,
 `toaddr` int(10) unsigned NOT NULL,
 `code` varchar(2) COLLATE utf8_bin NOT NULL,
 `name` varchar(128) COLLATE utf8_bin NOT NULL,
 KEY `i_fromaddr` (`fromaddr`)
) ENGINE=MyISAM DEFAULT CHARSET=utf8 COLLATE=utf8_bin

 

Jā un patiešām ja rakstīt kā Tu minēji ar <= nevis >= tad nostrādā ļoti ātri, ja ir indekss. Vaicājums ir sekojošs:

 

select sql_no_cache
a.ip,
(select `name` from iptocountry where fromaddr <= inet_aton(a.ip) order by fromaddr limit 1)
from
ip_addresses a

 

Nostrādā ļoti ātri, bet nepareizi. Visām ip adresēm tiek atgriezta pirmā vērtībā no tabulas iptocoutnry, kas ir ja tabulu sakārto pēc fromaddr. Pēc loģikas tā arī jābūt, ja Tu paņem <=, tad pilnīgi jebkurai ip adresei izpildīsies nosacījums pie paša pirmā ieraksta un, ta kā ir limit 1, neko vairāk arī nemeklēs.

 

Savukārt ja uzliek zīmi pretēji, t.i. >=, pēc loģikas jābūt pareizi, jo sakārtotam sarakstam viņš atradīs tieši pirmo pareizo fromaddr, kas ir lielāks vai arī vienāds ar pirmo intervāla skaitli, bet, to izpildot, praktiskais rezultāts tomēr nav pareizs, nezinu kāpēc, bet izskatās ka patiešām sākumā tiek izpildīts where un tikai pēc tam tiek veikta sakārtošana.

 

Arī viens atsevišķs vaicājums nestrādā pareizi:

 

select `name` from iptocountry where fromaddr >= inet_aton('24.100.14.0') order by fromaddr limit 1

 

Šis vaicājums izdod Kanādu, kaut gan jābūt ASV. Nomainot zīmi uz <=, tātad:

 

select `name` from iptocountry where fromaddr <= inet_aton('24.100.14.0') order by fromaddr limit 1

 

tiek atgriezta Asia/Pacific Region, kas ir pirmais rezultāts, ja tabulu iptocountry sakārtot pēc fromaddr, nu šis ir ļoti loģiski, šajā gadījumā to arī tā kā būtu jāatgriež.

 

Protams ja šim vaicājumam pieliek vēl klāt otru nosacījumu, kas pārbauda intervāla lielāko skaitli, tad protams rezultātu rādīs pareizi, neatkarīgi no tā vai ir limit vai nav, sanāk standarta pieeja, bet tas jau ir bez jebkādas optimizācijas un strādā protams ļoti lēni:

 

select sql_no_cache
a.ip,
(select `name` from iptocountry where inet_aton(a.ip) >= fromaddr and inet_aton(a.ip) <= toaddr order by fromaddr limit 1)
from
ip_addresses a

[codez]

yep, tev taisnība, rakstot no galvas, nokļūdījos.

 

Vajag meklēt, nevis pirmo, bet pēdējo, kuram afrom<=ip, tāpēc rakstām:

 

SELECT * FROM a WHERE afrom<=65 ORDER BY ato DESC LIMIT 1

Edited November 25, 2010 by codez

[Maris-S]

Jā, tagad darbojas. Tātad vaicājums ir tāds:

 

select sql_no_cache
a.ip,
(select `name` from iptocountry where fromaddr <= inet_aton(a.ip) order by toaddr desc limit 1)
from
ip_addresses a

 

Rezultāti ir pareizi, arī notiek daudz ātrāk nekā ar neoptimizētu vaicājumu, bet tomēr salīdzinot ar bitiem nav ātri. Izpildes laiks 595.995 sekundes.

[codez]

Domāju vienu, ierakstīju, ko citu.

Jākārto pēc tās paša from lauka:

 

SELECT * FROM ips WHERE fromaddr<=ip ORDER BY fromaddr  DESC LIMIT 1

Edited November 25, 2010 by codez