ugrás a tartalomhoz

Nagy mennyiségű adat szűrése + lapozgatás?

mind1 valami név · Jan. 8. (Szo), 13.14
Próbálom röviden, de így is hosszú lesz :)

Nagy tömegű adatból kell lekérdezést csinálni, lapokra osztva az eredményt.
A gond ott kezdődik, hogy regex alapú szűrést akarok végezni az adatokon.
Postgres esetében ez nem gond, de ha az a vágyam, hogy a program ne legyen driver függő, akkor azt hiszem, az adatbázis szerverek spéci szolgáltatásaira nem számíthatok.
Amíg mindent intézhetek adatbázis oldalon, addig no problem, a megcélzott keretrendszer (flask+sqlachemy) nyújt lapozós szolgáltatást egy paginate nevű függvény formájában.
De mi a bánatot lehet csinálni, ha olyan válogatást kell végezni, amire az adatbázis nem képes? A meglévő 5-6 millió sor betöltése kifekteti a szervert és a klienst is, részben timeout, részben out of memory képében.
Van erre valami megszokott, elfogadott algoritmus, hogy lehessen könnyen, gyorsan lapozgatni a találatok közt és ne bolonduljon meg az oldalszámozás?
Mert az még O.K., hogy az első lapot megjelenítem úgy, hogy addig olvasom a sorokat, amíg be nem jön egy oldalnyi a szűrésre illeszkedő sor.
De az utolsó (tehát nem a 123. oldalra, hanem általánosságban az utolsó) oldalra csak úgy tudnék lépni, ha végigolvasom a teljes táblát, ami iszonyat lassú.
Caching nem igazán jöhet szóba, mert ahhoz is kellene előbb egy teljes olvasás és ugyanott tartok.
De akkor hogy?
 
1

Adatbázisnál erre van

inf · Jan. 8. (Szo), 17.16
Adatbázisnál erre van indexelés, view-ok, stb. Úgy kéne felindexelned, hogy az meggyorsítsa a keresést, és lehetőleg SQL-ben megoldható legyen.
2

Egyszer én is kellett ilyent

kuka · Jan. 9. (V), 08.31
Egyszer én is kellett ilyent műveljek, úgyhogy átnyálaztam kissé a témát, de olyant, hogy indexelés gyorsítson a reguláris kifejezéses keresésen, olyant nem találtam.
3

Nem így értettem, hanem

inf · Jan. 9. (V), 09.21
Nem így értettem, hanem indexelés, mint alapelv. Jelen esetben ismerni kéne a regexet ahhoz, hogy meg lehessen mondani hogyan lehet felindexelni rá az adatbázist. Egy viszonylag egyszerű példa, ha két egymás utáni szót keresel a szövegekben és a regexed valami ilyesmi, hogy "/\bkakaós\scsiga\b/". Olyankor a meggyorsítására csinálhatsz olyan indexet, hogy egy konkrét szó előfordulásai a tárolt szövegekben "\b(\w+)\b". Itt érdemes észrevenni, hogy a fenti "kakaós" és "csiga" szavakra - az ó miatt némi sarkítással - általánosan illő mintát találtunk "\w+", amivel fel tudtuk darabolni a fenti kifejezést két általánosabb részre. Utána megnézed, hogy milyen szövegek azok, ahol mindkét szó előfordul. És utána csak azokra a szövegekre nézed meg a regexet, ami ezen felül az egymásutániságot vizsgálja. Nem tudom, hogy az ilyen jellegű indexelésnek mik az elvi korlátai, de valszeg minden regex így általánosítható és szétdarabolható és utána a darabkákra lehet indexelni. Regex minta függő, de vannak más motorok is, amik sokkal gyorsabbak a hagyományosnál, mert nincs backtracking vagy ilyesmi.
4

Asszem,félreértesz: nincs fix

mind1 valami név · Jan. 9. (V), 20.05
Asszem,félreértesz: nincs fix keresőfeltétel, feljön egy 50-100 tételből álló lista, a user meg erre enged rá egy tetszőleges regex alapú válogatást.
Az indexen láttam egy durva negatív példát: a törölt kommentek is ott vannak az adatbázisban, csak nem jelennek meg.
Ennek eredménye, hogy régi topic-ok, rengeteg törölt hozzászólással úgy jelennek meg, hogy az utolsó oldalak üresek, de sorszámot azért kapnak. :)
5

Ha a regex user input, akkor

inf · Jan. 10. (H), 03.20
Ha a regex user input, akkor esélytelen. Maximum azt lehet csinálni, hogy kiírod, hogy elkezdtük a munkát a feladaton, majd értesítjük, ha elkészült. A cache az jó ötlet, mert ha kétszer kérik ugyanazt, akkor legalább nem kell egy csomó erőforrást elfecsérelni rá.
11

A kulturált megoldás

mind1 valami név · Jan. 10. (H), 19.18
A kulturált megoldás esélytelen ;)

Megtehetem, hogy letöltöm az eredményt memóriába, és attól kezdve már van miből lapszámot generálni.
Csak annyi memória a világon nincs rossz esetben :)
Végső megoldás lehet az is, hogy ha elég a session indulásakor rendelkezésre álló adat, hogy elküldöm háttérbe a lekérdezést és készítek belőle egy ideiglenes táblát.
Mondjuk ez már valahol a cache kategória.

A kérdés egyébként onnan jött, hogy a logjaimon ismerkedtem az ORM csodáival és sikerült ráengedni egy SyslogTable.query.all() lekérdezést, amitől pár percre lefagyott a notebookom :D Ebből kiindulva találtam rá a paginate()-re, és akkor kezdtem töprengeni, hogy egy komolyabb adatbázisból hogy lehetne normális, lapozós lekérdezést elkövetni egy előre nem rögzíthető lekérdezés esetén (pl usertől érkező regex).

ui: a korábbi hozzászólásomat kissé elírtam... nem 50-100 tételre gondoltam, hanem arra, hogy ennyit kap elsőre az arcába a sokmillióból, aztán ebből válogathat pl. regex mintával.
6

Lapozás

Pepita · Jan. 10. (H), 12.26
Alapesetben ugye (fatengelyes megoldás) lehetne kétszer futtatni a kereső / szűrő query-t, először csak COUNT-ra, másodszorra SELECT-elt oszlopokkal, de limittel.

Ez is szerverfüggő, de ha azonosak a szűrési feltételek, akkor pontosan meghatározható a lapok száma (ezt rontja el az index az üres lapoknál), és tudod, hogy hányadik lap az utolsó.

Hátránya, hogy kétszer futtatod majdnem ugyanazt a query-t, viszont ez akár előny is lehet: a modernebb adatbázisok ezt már elég jól cache-elik kvázi automatikusan.

Teljesítmény szempontjából jobb megoldás, amit megpedzettél már, hogy előzetes lekérés alapján bizonyos részeket temp táblába tolsz, lehetőleg memóriában.
Ha szét tudod bontani kisebb részekre a regex-et, akkor pl az egyes részeknek megfelelő Id-kat szóród így ki kis táblákba, végül ezekkel egy ügyes JOIN a fő táblán.
Ilyenkor mindig érdemes mérni a teljesítményt, hogy melyik megoldás a gyorsabb / jobb, mert (db szervertől függően) bele lehet futni még az eredetinél rosszabb / lassabb teljesítménybe is.
(Regex-el még nem csináltam ilyet, de nagy db-n, usertől érkező szűrőfeltételekkel igen, hogy a rengeteg JOIN miatt milliárdos nagyságrendű rekord keletkezett _volna_, ha nem bontjuk szét és nem csinálunk temp táblát hozzá.)
7

Kicsit összezavarodtam (nem

mind1 valami név · Jan. 10. (H), 14.17
Kicsit összezavarodtam (nem miattad ;) )
Végülis az említett paginate() függvény megteszi ezt (select count(), majd select) helyettem valahogyan, ráadásul adatbázis típustól függetlenül. Franc a szenilitásba... Megint nem jut eszembe, hogy ez hol és miért nem volt jó.
Szerintem valamit nagyon túlgondoltam: ha valahol mélyen a listában járok és a user átírja, szűkíti a keresést, akkor egyszerűen visszadobom az első oldalra, oszt jónapot.
8

Nekem kicsit úgy tűnik, hogy

inf · Jan. 10. (H), 14.54
Nekem kicsit úgy tűnik, hogy valami halálcsillagot próbálsz építeni teljesen feleslegesen. De persze nem látok bele, és magamból indulok ki. :D

Egyébként ha már szóba került, cloudon kívül van bármi, ahol tudnék nodejs-t futtatni anélkül, hogy a rendszergazdai tevékenységet el kéne látnom? Néztem a dotrollt, de az CGI, ami rohadtul nem nodejs. Átgondoltam, és soha többet nem akarok én már PHP-zni vagy ilyen thread based architecture-t használni. Egyszerűen nem szeretem.
9

Nem, ez nem az "építéshez"

mind1 valami név · Jan. 10. (H), 17.48
Nem, ez nem az "építéshez" kell, csak elméláztam rajta, hogy ha komolyabb rendszerben gondolkodnék, akkor ez a lapozgatós része helyenként (ahogy korábban írtad is) mintha a fizikai képtelenség határát súrolná. :)
10

Ja hát vannak korlátai az

inf · Jan. 10. (H), 18.56
Ja hát vannak korlátai az informatikának is, nem is kevés.
12

Logikus

Pepita · Jan. 11. (K), 13.02
ha valahol mélyen a listában járok és a user átírja, szűkíti a keresést, akkor egyszerűen visszadobom az első oldalra, oszt jónapot.
Ez teljesen logikus, hiszen változik a találatok száma is.
13

Annyira nem. (csak példa)

mind1 valami név · Jan. 11. (K), 13.18
Annyira nem. (csak példa) Turkálok egy webáruházban, sokezer áru közt, 20 tétel/lap bontásban. Nézegetek valamit, észreveszek rajta egy tulajdonságot, amivel szűkíteni tudom az áruk listáját, beixszelem, erre kapok egy új listát ami nulláról indul és eltűnik előlem amit épp bámultam. Nem biztos, hogy heppi leszek. :)
14

Végülis, ha a rendezés ár

inf · Jan. 11. (K), 15.35
Végülis, ha a rendezés ár szerint megy és szűkül a lista, akkor logikus ugyanattól az árutól folytatni, de ez nem lehet általános szabály. Mondjuk ha törölsz egy feltételt, akkor bővül a lista, és akkor ha nem elölről kezded a nézegetését, akkor kimaradhatnak termékek.
15

Ez csak egy példa volt, ami

mind1 valami név · Jan. 12. (Sze), 10.34
Ez csak egy példa volt, ami miatt a napokban anyáztam egy sort. :)