sąsiednie rekordy
Paweł - 13-11-2006 00:45
sąsiednie rekordy
Witam !
Na serwerze znajduje się baza MySQL 3.23.
W niej jest tabela mająca wielkość 400 MB składająca się z kilkudziesięciu
tysięcy rekordów.
Załóżmy dla uproszczenia, że tabela ma dwie kolumny "Id" (autoinkrement,
klucz podstawowy) i "ABC"
Do bazy danych wysyłane są ze skryptu PHP tylko dwa rodzaje zapytań:
Np.
SELECT * FROM `TABELA' WHERE Id > 30000 AND ABC != 'NULL' LIMIT 0 , 1
i
SELECT * FROM `TABELA' WHERE Id < 30000 AND ABC != 'NULL' ORDER BY Id
DESC LIMIT 0 , 1
Jak łatwo się zorientować chodzi o znalezienie najbliższego rekordu względem
danego ( w przykładzie o numerze 30000) zawierającego jakieś dane kolumnie
ABC. W pierwszym przypadku szukane są rekordy o Id większym a w drugim o Id
mniejszym.
Problem polega na tym, że pierwsze zapytanie wykonuje się 0.002 sek. a
drugie 10 sek.
Zastąpiłem więc to drugie zapytanie dwoma:
SELECT MAX(Id) FROM `TABELA' WHERE Id < 30000 AND ABC != 'NULL'
SELECT * FROM `TABELA' WHERE Id =.....
Teraz wykonuje się to około 1 sek. Jednak to dla mnie nadal za długo.
Czy jest jakiś sposób aby przyspieszyć wyszukiwanie sąsiednich rekordów ?
Paweł
Grzegorz Danowski - 13-11-2006 00:45
Użytkownik "Paweł" <pawel.neo@neostrada.pl> napisał w wiadomości
news:ehqo41$i28$1@nemesis.news.tpi.pl...
> Witam !
>
> Na serwerze znajduje się baza MySQL 3.23.
> W niej jest tabela mająca wielkość 400 MB składająca się z kilkudziesięciu
> tysięcy rekordów.
> Załóżmy dla uproszczenia, że tabela ma dwie kolumny "Id" (autoinkrement,
> klucz podstawowy) i "ABC"
> Do bazy danych wysyłane są ze skryptu PHP tylko dwa rodzaje zapytań:
> Np.
> SELECT * FROM `TABELA' WHERE Id > 30000 AND ABC != 'NULL' LIMIT 0 , 1
> i
> SELECT * FROM `TABELA' WHERE Id < 30000 AND ABC != 'NULL' ORDER BY
> Id DESC LIMIT 0 , 1
>
> Jak łatwo się zorientować chodzi o znalezienie najbliższego rekordu
> względem danego ( w przykładzie o numerze 30000) zawierającego jakieś dane
> kolumnie ABC. W pierwszym przypadku szukane są rekordy o Id większym a w
> drugim o Id mniejszym.
> Problem polega na tym, że pierwsze zapytanie wykonuje się 0.002 sek. a
> drugie 10 sek.
>
> Zastąpiłem więc to drugie zapytanie dwoma:
> SELECT MAX(Id) FROM `TABELA' WHERE Id < 30000 AND ABC != 'NULL'
> SELECT * FROM `TABELA' WHERE Id =.....
>
> Teraz wykonuje się to około 1 sek. Jednak to dla mnie nadal za długo.
> Czy jest jakiś sposób aby przyspieszyć wyszukiwanie sąsiednich rekordów ?
Może użyj nieco zmodyfikowanego wyszukiwania binarnego? Oczywiście po
stronie php. Coś w stylu:
<pseudo kod>
int myValue = 30000
int currId = 0
int step = myValue / 2
Loop
currId = currId + step
record = Select Id From 'Tabela' Where Id < currId And Id >= myValue
Limit 0, 1
if step = 1 And record Is Not Null
return currId
else
step = step / 2
if record Is Null
currId = currId - step
else
currId = currId + step
End Loop
</pseudo kod>
Jak Ci się uda zaimplementować, to podziel się wynikami na grupie. Wg mojej
oceny, dla 30 tys. rekordów wykona się nie więcej niż 15 przebiegów pętli,
czyli czas całkowity będzie mniejszy od 15 * 0.002 = 0.03, plus wymiana
danych z php, ale trudno mi ocenić jaki jest jego narzut.
Aczkolwiek nie wiem czy nie wystarczy dodać dodatkowego indeksu na Id
posortowanego malejącą, wówczas ten Twój drugi selekt będzie szybszy.
Pozdrawiam
Grzegorz
Michał Kuratczyk - 13-11-2006 00:45
Grzegorz Danowski wrote:
> Może użyj nieco zmodyfikowanego wyszukiwania binarnego? Oczywiście po
> stronie php.
Mam ochotę coś odpisać, ale jeszcze nie doszedłem do siebie. To jest chyba
najbardziej absurdalny pomysł jaki widziałem w odniesieniu do baz danych.
--
Michał Kuratczyk
Grzegorz Danowski - 13-11-2006 00:45
Użytkownik "Michał Kuratczyk" <kura@lj.pl> napisał w wiadomości
news:ehsoou$2o2d$2@news2.ipartners.pl...
>> Może użyj nieco zmodyfikowanego wyszukiwania binarnego? Oczywiście po
>> stronie php.
> Mam ochotę coś odpisać, ale jeszcze nie doszedłem do siebie. To jest chyba
> najbardziej absurdalny pomysł jaki widziałem w odniesieniu do baz danych.
Zgadzam się, że moja propozycja jest nieco niekonwencjonalna (mało sql-owa),
bo i oczekiwany wynik jest mało sql-owy (jedna liczba a nie zbiór rekordów),
ale wg mojej oceny jest bardzo wydajna. Zaproponuj coś w czystym sql-u, co
będzie bardziej wydajne i wówczas Paweł porówna oba rozwiązania i zamieści
na grupie z korzyścią dla kolejnych pytaczy. Być może wystarczy dodać indeks
posortowany malejącą, ale taki pomysł też zapodałem pytaczowi.
Pozdrawiam
Grzegorz
Michał Kuratczyk - 13-11-2006 00:45
Grzegorz Danowski wrote:
> Zgadzam się, że moja propozycja jest nieco niekonwencjonalna (mało
> sql-owa), bo i oczekiwany wynik jest mało sql-owy (jedna liczba a nie
> zbiór rekordów), ale wg mojej oceny jest bardzo wydajna. Zaproponuj coś w
> czystym sql-u, co będzie bardziej wydajne i wówczas Paweł porówna oba
> rozwiązania i zamieści na grupie z korzyścią dla kolejnych pytaczy. Być
> może wystarczy dodać indeks posortowany malejącą, ale taki pomysł też
> zapodałem pytaczowi.
Nie zaproponuję rozwiązania, bo nie znam dobrze MySQLa (w Oracle można to
zrobić funkcjami analitycznymi LEAD/LAG, które służą dokładnie do
zaglądania w poprzedni/następny rekord), ale to jeszcze nie powód, żeby
ludzi namawiać do robienia takich rzeczy.
To mniej więcej tak, jakby na pytanie "czemu mój samochód nie jest w stanie
rozpędzić się powyżej 100km/h" odpowiedzieć "kup sobie lawetę, bo ona nawet
z tym samochodem na pace więcej wyciągnie". No niby jest to jakieś
rozwiązanie, ale jednak bardzo specyficzne... :->
PS Podejrzewam, że indeks malejący załatwi sprawę.
--
Michał Kuratczyk
Grzegorz Danowski - 13-11-2006 00:45
Użytkownik "Michał Kuratczyk" <kura@lj.pl> napisał w wiadomości
news:ehsst9$2r79$1@news2.ipartners.pl...
>> Zgadzam się, że moja propozycja jest nieco niekonwencjonalna (..)
>> Zaproponuj coś w
>> czystym sql-u, co będzie bardziej wydajne i wówczas Paweł porówna oba
>> rozwiązania i zamieści na grupie z korzyścią dla kolejnych pytaczy. Być
>> może wystarczy dodać indeks posortowany malejącą, ale taki pomysł też
>> zapodałem pytaczowi.
> Nie zaproponuję rozwiązania, bo nie znam dobrze MySQLa (w Oracle można to
> zrobić funkcjami analitycznymi LEAD/LAG, które służą dokładnie do
> zaglądania w poprzedni/następny rekord),
Znam MySQL 3.3 tylko z opowiadań, ale nie sądzę by znajdowały się tam takowe
funkcje.
> ale to jeszcze nie powód, żeby
> ludzi namawiać do robienia takich rzeczy.
Ja nikogo nie namawiam, zresztą zrobienie bezbłędnego wyszukiwania binarnego
nie jest takie proste - badania wskazują, że większość programistów nie
potrafi od razu poprawnie zaimplementować algorytmu wyszukiwania binarnego
(na pewno i ja w swym pseudo kodzie, np. to nie napisałem, że wynik step / 2
powinien być zaokrąglany w górę :-).
> To mniej więcej tak, jakby na pytanie "czemu mój samochód nie jest w
> stanie
> rozpędzić się powyżej 100km/h" odpowiedzieć "kup sobie lawetę, bo ona
> nawet
> z tym samochodem na pace więcej wyciągnie". No niby jest to jakieś
> rozwiązanie, ale jednak bardzo specyficzne... :->
Ok. Ale w sytuacji gdy za pomocą czystego sql-a mamy wynik po 1 sekundzie, a
w mojej propozycji będzie pewnie po 0,03 to korzyść jest istotna. Czyli jak
klientowi zależy na czasie i będzie chciał się dostarczyć samochód z
Warszawy do Pekinu, to lepiej zaproponować mu transport drogą lotniczą, bo w
ten sposób transport będzie trwał kilkadziesiąt razy krócej niż gdyby
samochód przemieszczał się w sposób
najbardziej naturalny dla niego, czyli na własnych kołach :-).
> PS Podejrzewam, że indeks malejący załatwi sprawę.
Z tym podejrzeniem jesteśmy zgodni, czekamy więc na wyniki Pawła.
Pozdrawiam
Grzegorz
Paweł - 13-11-2006 00:45
> Jak Ci się uda zaimplementować, to podziel się wynikami na grupie. Wg
> mojej
> oceny, dla 30 tys. rekordów wykona się nie więcej niż 15 przebiegów pętli,
> czyli czas całkowity będzie mniejszy od 15 * 0.002 = 0.03, plus wymiana
> danych z php, ale trudno mi ocenić jaki jest jego narzut.
>
Wydaje mi się, że to co napisałeś nic nie da. Zwróć uwagę, że chce znaleźć
sąsiedni rekord ale taki, w którym a kolumnie ABC będą jakieś dane.
W praktyce udało mi się jakoś obejść problem uwzględniając pewne
statystyczne zależności w mojej tabeli.
W 99% przypadków poszukiwany rekord znajduje się bardzo blisko danego
rekordu (np. o wartości 30000).
Zapytanie SELECT MAX(Id) WHERE Id<30000 AND Id>29950 AND ABC!='NULL'
wykonuje się kilka tysięcy razy szybciej niż:
SELECT MAX(Id) WHERE Id<30000 AND AND ABC!='NULL'
Zupełnie mnie zaskoczyło, że na czas wykonywania zapytania do bazy MySQL ma
duży wpływ czas w jakim wykonywało się poprzednie zapytanie.
Paweł
Grzegorz Danowski - 13-11-2006 00:46
Użytkownik "Paweł" <pawel.neo@neostrada.pl> napisał w wiadomości
news:ehtc3l$pji$1@atlantis.news.tpi.pl...
>
>> Jak Ci się uda zaimplementować, to podziel się wynikami na grupie. Wg
>> mojej
>> oceny, dla 30 tys. rekordów wykona się nie więcej niż 15 przebiegów
>> pętli, czyli czas całkowity będzie mniejszy od 15 * 0.002 = 0.03, plus
>> wymiana danych z php, ale trudno mi ocenić jaki jest jego narzut.
>>
>
> Wydaje mi się, że to co napisałeś nic nie da. Zwróć uwagę, że chce znaleźć
> sąsiedni rekord ale taki, w którym a kolumnie ABC będą jakieś dane.
Hmm, a co to ma do rzeczy, wystarczy przecież drobna modyfikacja:
record = Select Id From 'Tabela' Where Id < currId
And Id >= myValue AND ABC!='NULL' Limit 0, 1
A prawidła statystyczne mógłbyś wykorzystać zachowując dalej algorytm
wyszukiwania binarnego przez startowanie z punktu 0,99 razy szukana wartość,
trzeba byłoby jednak zmodyfikować sposób znajdowania kolejnego punktu (bo
nie można byłoby korzystać z step = step / 2).
Ale fajnie, że udało Ci się znaleźć lepszy sposób.
Pozdrawiam
Grzegorz
Paweł - 13-11-2006 00:46
>> Wydaje mi się, że to co napisałeś nic nie da. Zwróć uwagę, że chce
>> znaleźć sąsiedni rekord ale taki, w którym a kolumnie ABC będą jakieś
>> dane.
>
> Hmm, a co to ma do rzeczy, wystarczy przecież drobna modyfikacja:
>
> record = Select Id From 'Tabela' Where Id < currId
> And Id >= myValue AND ABC!='NULL' Limit 0, 1
>
Faktycznie masz rację. Chyba sprawdzę w praktyce ten algorytm.
Paweł
zanotowane.pldoc.pisz.plpdf.pisz.pleffulla.pev.pl
|
[ms sql] =?ISO-8859-2?Q?wy=B6wietlenie_pierwszych_5_rekord?==?ISO-8859-2?Q?=F3w_z_zapytania_=3F_odpowiednik_ROWNUM_w_o?== ?ISO-8859-2?Q?raclu_dla_MS_SQL=27a?=
[MySQL] =?ISO-8859-2?Q?Wy=B6wietlenie_kolejnej_pozycji=2C_?==?ISO-8859-2?Q?jak=B1_mia=B3by_dany_rekord=2C_gdybym_czyta=B3 _?==?ISO-8859-2?Q?wg_konkretnych_kryteri=F3w=2E_Da_si=EA_=3F?=
Jak =?ISO-8859-2?Q?zamieni=E6_dwa_pola_jednej_kolumny_?==?ISO-8859-2?Q?w_dw=F3ch_rekordach_za_pomoc=B1_jednego_zapyt? ==?ISO-8859-2?Q?ania=3F?=
[mysql/php] jak =?ISO-8859-2?Q?zliczy=E6_ilo=B6=E6_unikalnyc?==?ISO-8859-2?Q?h_rekord=F3w_w_jednym_zapytaniu=3F?=
=?ISO-8859-2?Q?WY=B6wietlenie_rekord=F3w_pocz=B1wszy_od_?==?I SO-8859-2?Q?danej_litery=2E=2E=2E?=
=?iso-8859-2?Q?=5BMySQL=5D_Wy=B6wietlenie_wszystkich_rekordow _zawierajacy?==?iso-8859-2?Q?ch_duplikat_a__moze_inna_struktura_bazy_danych ?=
[pgsql] Akcja w =?iso-8859-2?b?emFsZb9ub7ZjaQ==?= od liczby zmienionych =?iso-8859-1?q?rekord=F3w?=
[postgresql] kilka =?ISO-8859-2?Q?rekord=F3w_subquery_jako_?==?ISO-8859-2?Q?string?=
[mysql] Wyszukanie =?ISO-8859-2?Q?rekord=F3w=28powiazane_tabel?==?ISO-8859-2?Q?e=29?=
[MySQL]: Dodanie zliczania =?ISO-8859-2?Q?rekord=F3w_do_rozb?==?ISO-8859-2?Q?udowanego_zapytania?=
zanotowane.pldoc.pisz.plpdf.pisz.plmelooonka.opx.pl
Cytat
Decede mihi sole - nie zasłaniaj mi słonca.
Gdy kogoś kochasz, jesteś jak stworzyciel świata - na cokolwiek spojrzysz, nabiera to kształtu, wypełnia się barwą, światłem. Powietrze przytula się do ciebie, choćby był mróz, a ty masz w sobie tyle radości, że musisz ją rozdawać wokoło, bo się w tobie nie mieści
Hoc fac - tak czyń.
A tergo - od tyłu; z tyłu.
I czarne włosy posiwieją. Safona |
|
