Elegancija resenja, serijalizacija strukture, cuvanje bazice u memoriji...

Elegancija resenja, serijalizacija strukture, cuvanje bazice u memoriji... 22.02.2006. u 16:39 · pre 251 mesec #1

Pozdrav Javistima :o)

Pre nego što počnem sa implementacijom jedne ideje, hteo sam da prodiskutujemo o eleganciji i ispravnosti iste, pa ako neko uspe da me ubedi da nije valjana, da ne gubim vreme.

Dakle, evo o čemu se radi:

Napravio sam jednu prostu GUI aplikaciju, gde korisnik unosi query, poziva se izvesna statička metoda koja generiše rezultat i ispisuje ga korisniku. Trik je u tome što je polje za unos teksta registrovano sa DocumentListener-om i pri svakoj promeni u tekst polju se poziva pomenuta metoda. Iako sam smatrao da je korisnik relativno spor ulazni uređaj, realne su situacije kada će on agresivnije unositi tekst, a tada frekventnije pozivanje metode već predstavlja problem iz razloga koji ću sada navesti.

Naime, "baza" sa kojim barata metoda se nalazi u 3 tekstuelna fajla u CSV formatu (ne pitajte me zašto tako). Jedan od njih sadrži informacije o vezama entiteta, a druga dva same entitete sa odgovarajućim identifikatorima. Da stvar bude zamršenija, rezultat na query nije jednoznačan što implicira da se mora proći kroz cela 2 od 3 fajla pri svakom query-ju, a kroz onaj jedan samo dok se ne naleti na pogodak.

Uglavnom, već vam je jasno da je i jedno pozivanje metode relativno sporo, iako zadovoljavajuće za jedan poziv. Problem nastaje pri kucanju teksta u tekst polju i brzom pozivanju metode. Efekat je taj da je CPU poprilično opterećen u tim trenucima i ispis u tekst polju za unos malo kasni u odnosu na kucanje, dakle program radi sporije nego što bi trebalo i to je korisniku očigledno i neprijatno.

S obzirom da je sam algoritam pretraživanja nemoguće više optimizovati, nije mi preostalo ništa drugo, nego da reorganizujem strukturu podataka. Pored toga, ne želim da koristim neku gotovu bazu jer hoću da se program može izvršiti sa standardnim Javinim paketima, dakle da se zavisnost svede na minimum tj. na nulu.

Imam sledeću zamisao: napraviću klasu koja će da koristi hash tabelu čiji će ključevi biti odgovarajuća polja, a sadržaji ulančane liste sa odgovarajućim elementima koja predstavljaju izlaz na zadati upit. Zatim ću instancirati 2 objekta pomenute klase (jer imam 2 smera ulaz-izlaz), napuniti ih podacima iz CSV-a, na odgovarajući našin, a zatim ta 2 objekta serijalizovati u datoteku.

Pri startovanju aplikacije, objekti se deserijalizuju, dakle dohvate i postave odgovarajuće reference.

Mene zanima, pre svega, da li je ideja u ovom slučaju o serijalizaciji i korišćenju pomenutih struktura podataka dobra, a zatim da li je pametno držati ova dva "teška" objekta na ovaj način u memoriji za svo vreme rada programa?

Baza u tekstualnom formatu nije bog zna šta velika, sigurno ne veća od 3 mb.

Računam da će performanse tada biti odlične, da li sam u pravu?

Jedino me brine veličina pomenutih objekata.

Haug

Re: Elegancija resenja, serijalicija strukture, cuvanje bazice u memoriji... 22.02.2006. u 18:37 · pre 251 mesec #2

Pre nego krenes, cisto da znas i za HSQL.. mozda nema potrebe da izmisljas toplu vodu.

HSQLDB is the leading SQL relational database engine written in Java. It has a JDBC driver and supports a rich subset of ANSI-92 SQL (BNF tree format) plus SQL 99 and 2003 enhancements.

It offers a small (less than 100k in one version for applets), fast database engine which offers both in-memory and disk-based tables and supports embedded and server modes.

Additionally, it includes tools such as a minimal web server, in-memory query and management tools (can be run as applets) and a number of demonstration examples.

http://www.hsqldb.org/

Potpis

Commercial-Free !!!

Re: Elegancija resenja, serijalicija strukture, cuvanje bazice u memoriji... 22.02.2006. u 20:03 · pre 251 mesec #3

Iako sam napomenuo da ne bih da koristim externe alatljike, HSQLDB je skroz cool koliko sam video neke primere na brzaka i hsqldb.jar ima ~ 600 kb, pa je najbrže rešenje da ga uključim uz aplikaciju. Kad ga koriste ovi iz OpenOffice-a i Mathematic-e, što da ga ne koristim i ja

Pozdrav

Re: Elegancija resenja, serijalicija strukture, cuvanje bazice u memoriji... 24.02.2006. u 00:06 · pre 251 mesec #4

Ovo je obećavajuć projekat, naslednik HSQLDB-a:
http://www.h2database.com/html/frame.html

Potpis

Bolje džaba ležat nego džaba radit.

Re: Elegancija resenja, serijalizacija strukture, cuvanje bazice u memoriji... 26.02.2006. u 01:41 · pre 251 mesec #5

Posle implementacije baze na sledeći način, performanse su perfektne:

Code:

...
CREATE TABLE en_table ( id INTEGER, word VARCHAR(256))
...

Dakle to je situacija kada koristim "in memory" bazu, a na disku postoji plain text fajl iz koga se kreira baza i učitava u memoriju pri svakoj inicijalizaciji.

S obzirom da ne želim da podaci budu u plain text formatu, kreirao sam ovako bazu:

Code:

...
CREATE CACHED TABLE en_table ( id INTEGER, word VARCHAR(256))
...

I tada se podaci čuvaju u binarnom obliku na disku. Ono što me je strašno začudilo je da su tada performanse ZABRINJAVAJUĆE, znači 10 puta je bar gore nego prvobitno bez ikakve baze!? Kako je to moguće?

Znači sada hoću da zadržim ove performanse (in memory), ali da mi podaci budu binarni. Kako ovo da postignem?

Uglavnom, kad se čuva u memoriji, super je brzo, ali je loše što se malo sporije inicijalizuje u startu i što je plain format, a sa druge strane, na disku je super što je binarno i što se brže inicijalizuje baza jer se samo deo kešira u memoriju, ali je očajna brzina pretrage...

Ako je potrebno parče koda ili nešto, javite..

Pozdrav

Re: Elegancija resenja, serijalicija strukture, cuvanje bazice u memoriji... 26.02.2006. u 15:37 · pre 251 mesec #6

Pa verovatno zato sto je pretrazivanje brze ako su podaci u memoriji. Baza jeste baza, ali citanje sa diska vs. iz RAM.. :)

Ili: mozda mozes da drzis podatke u bazi na disku, a prilikom starta aplikacije sve prebaci u tabelu u memoriji..?

Ili: "rucno" kodiraj taj svoj tekst fajl (neki jako brz i jednostavan algoritam), a onda kada podatke prebacujes u tabelu u memoriji, jednostavno ih dekodiraj.

Dalje, ako ti je brzina tako bitna, probaj da koristis polja fiksne duzine (dakle nemoj da koristis varchar). Jesi li stavljao indeks?

Ili napravi 2 tabele u bazi, jednu koja ce da ima polja fiksne duzine (npr. char(10) ) i tu naravno stavi sve reci do 10 karaktera, a ostalo (duze reci) u drugu tabelu gde je polje varchar -- pogledaj statistiku za reci koje drzis u bazi pa vidi kolika bi bila najbolja duzina polja za prvu tabelu, da obuhvati sto vise reci. I onda pretrazujes u prvoj ili drugoj tabeli zavisno od toga koliko je slova korisnik trenutno ukucao za rec koja se pretrazuje.

Ili neka kombinacija: npr. prilikom starta samo prvu tabelu prebaci u memoriju..

Itd.. moras malo da se igras i probavas.

Potpis

Commercial-Free !!!

Re: Elegancija resenja, serijalizacija strukture, cuvanje bazice u memoriji... 26.02.2006. u 18:32 · pre 251 mesec #7

E pa to, gotovo 100% ću držati bazu na disku u binarnom formatu, a pri inicijalizaciji ću napuniti bazu u memoriju i tako ću dobiti sve dobre osobine ;o)

Tnx 4 the info

Re: Elegancija resenja, serijalizacija strukture, cuvanje bazice u memoriji... 17.03.2006. u 15:46 · pre 251 mesec #8

E degojs, bio si u pravu, nisam koristio index

Ajde pomozi još malo, sada radi polovično, a rešenje je potpuno simetrično, do 8 ujutru nisam spavao i nisam uspeo da rešim

Evo kako sam sada kreirao tabele:

Code:

CREATE CACHED TABLE en_table ( id INTEGER PRIMARY KEY, word VARCHAR(256))
CREATE CACHED TABLE sr_table ( id INTEGER PRIMARY KEY, word VARCHAR(256))
CREATE CACHED TABLE rel_table ( id1 INTEGER, id2 INTEGER )
CREATE INDEX relIndex ON rel_table(id1, id2)

Pošto prve 2 imaju primarne ključeve, automatski je napravljen index, a za relacionu sam sam napravio.

Evo kako radim query:

Code:

SELECT word FROM rel_table INNER JOIN sr_table ON rel_table.id2 = sr_table.id WHERE rel_table.id1 = ? ORDER BY word
SELECT word FROM rel_table INNER JOIN en_table ON rel_table.id1 = en_table.id WHERE rel_table.id2 = ? ORDER BY word

Dakle, potpuno simetrično, a ono što me sada prosto izluđuje je to što sa prvim SELECT-om sve radi munjevito, a sa drugim se vuče i opet CPU trokira.

Šta je sad koj moj?

Pozdrav
Vanja

Re: Elegancija resenja, serijalizacija strukture, cuvanje bazice u memoriji... 17.03.2006. u 16:27 · pre 251 mesec #9

Vanja: ja nisam radio sa HSQL ali mi izgleda da ti u ovoj liniji:

CREATE INDEX relIndex ON rel_table(id1, id2)

kreiras kombinovani index koji uvek sadrzi index za id1/id2.

Tebi ne treba kombinovani index dva polja, vec dva indexa: jedan za polje id1 a drugi za polje id2 u toj tabeli. Ajd probaj ovako:

CREATE INDEX relIndex1 ON rel_table(id1)
CREATE INDEX relIndex2 ON rel_table(id2)

Pa poteraj upite onda.

Potpis

Commercial-Free !!!

Re: Elegancija resenja, serijalizacija strukture, cuvanje bazice u memoriji... 17.03.2006. u 16:49 · pre 251 mesec #10

Već probao, neće :(

Re: Elegancija resenja, serijalizacija strukture, cuvanje bazice u memoriji... 17.03.2006. u 17:06 · pre 251 mesec #11

Cek, ja sam gore, posto sam radio copy-paste iste linije 2x imao ime indexa isto u prvoj i drugoj liniji.

Sad sam promenio pa se prvi index zove relIndex1 a drugi relIndex2. Ajd probaj tako, posto je pre izmene mozda druga linija samo prepisivala prvi index posto su se zvali isto (relIndex)?

Mislim, kako si ti prvo kreirao index (id1,id2) sam 99% siguran da nije dobro - ne verujem da je HSQL nesto drugaciji od ostalih baza, a to se tacno poklapa sa tim sto u drugom upitu koristis WHERE id2=? a to polje onda nije ni indeksirano samo za sebe.

Ja ne vidim sta drugo moze da bude s obzirom da ti prvi upit radi OK, a drugi je samo razilicit za to polje po kom se vrsi filtriranje a koje nisi imao zasebno indexirano.

Potpis

Commercial-Free !!!

Re: Elegancija resenja, serijalizacija strukture, cuvanje bazice u memoriji... 17.03.2006. u 17:14 · pre 251 mesec #12

Primetio sam, pokušao sam baš ovako kako si sad ispravio i neće!?

Definitnitvno ne treba kako sam gore uradio, ali sad i sa 2 zasebna indeksiranja polja po jednoj tabeli ne radi!

Ali najčudnije je što kad pokušam da radim samo jednosmerno i indeksiram samo jedan, smer en->sr radi, ali obrnuto ne, što je potpuno besmisleno jer je rešenje identično...

Re: Elegancija resenja, serijalizacija strukture, cuvanje bazice u memoriji... 17.03.2006. u 17:20 · pre 251 mesec #13

Ebi ga, ne znam :) Pogledaj malo HSQL dokumentaciju. Vidi ima li neki HSQL forum :-)

Iskreno, nemam pojma sta drugo.. :)

Potpis

Commercial-Free !!!

Re: Elegancija resenja, serijalizacija strukture, cuvanje bazice u memoriji... 17.03.2006. u 17:46 · pre 251 mesec #14

Hm, sad ćemo da vidimo šta kažu drugari:

http://sourceforge.net/forum/f..._id=1463825&forum_id=73674

Re: Elegancija resenja, serijalizacija strukture, cuvanje bazice u memoriji... 17.03.2006. u 19:05 · pre 251 mesec #15

I DA, DA, DA, čika Vanja je rešio problem

Znači, nećete mi verovati u čemu je bio problem!

Posle dvodnevnog drkanja počeo sam da sumnjam da je uopšte problem u relacionoj tabeli, jer sam probao sve varijante, a i jedan smer super radi.

Samo da podsetim, kada su sve tabele u memoriji onda super radi.

Zato sam uzeo pa sam prebacio samo relacionu tabelu u memoriju, a ove dve sa podacima ostavio na disku, da vidim šta se dešava.

I tada sam potvrdio da ipak nije problem u relacionoj tabeli, jer je i dalje smer sr->en bio spor!!!

I u tom trenutku je došlo do prosvetljenja!!!

U pitanju je, naime, sr<->en rečnik, i ako pogledate malo gore, rel_table.id1 i rel_table.id2 se dobijaju iz ?, koji se opet dobija na sledeći nacin:

Code:

SELECT id FROM en_table WHERE word = ?

i

SELECT id FROM sr_table WHERE word = ?

(ovde verovatno može da se uradi i optimizacija u smislu višestrukog (trostrukog) join-a)

Ja uopšte nisam indeksirao word polja jer sam smatrao da to nije krucijalno u ova 2 pomoćna query-ja.

I nije bilo za prvi pomoćni kveri jer su se pretraživale samo engleske reči, ALI drugi JE upravo predstavljao problem jer su to bile reči sa "našim slovima", UTF8 i zato je pretraga po njima bila duga!

Dakle, evo finalnog rešenja koje drži celu bazu na disku (dakle nije plain, zaštićeno je automatski) i performanse su DO JAJA:

Code:

CREATE CACHED TABLE en_table ( id INTEGER PRIMARY KEY, word VARCHAR(256))
CREATE INDEX enWord ON en_table(word)"
CREATE CACHED TABLE sr_table ( id INTEGER PRIMARY KEY, word VARCHAR(256))
CREATE INDEX srWord ON sr_table(word)
CREATE CACHED TABLE rel_table (id1 INTEGER, id2 INTEGER)
CREATE INDEX relIndex1 ON rel_table(id1)
CREATE INDEX relIndex2 ON rel_table(id2)

(nije škodilo da indeksiram i engleski word, kad sam već tu)

Code:

...
SELECT word FROM rel_table INNER JOIN sr_table ON rel_table.id2 = sr_table.id WHERE rel_table.id1 = ? ORDER BY word
...
SELECT id FROM en_table WHERE word = ?

i

...
SELECT word FROM rel_table INNER JOIN en_table ON rel_table.id1 = en_table.id WHERE rel_table.id2 = ? ORDER BY word
...
SELECT id FROM sr_table WHERE word = ?

E, kako je dobar osećaj kad provališ nešto, a dugo si se oko toga jebavao

Degojs, hvala na strpljenju

Pozdrav

Re: Elegancija resenja, serijalizacija strukture, cuvanje bazice u memoriji... 17.03.2006. u 19:23 · pre 251 mesec #16

E pa.. sad si nasao da das upit:

Citat:

SELECT id FROM XX_table WHERE word = ?

:)

Da si ga stavio odmah, odmah bi videli da ti treba index na polje word :)

No, dobro, bitno da fercera.

Potpis

Commercial-Free !!!

Re: Elegancija resenja, serijalizacija strukture, cuvanje bazice u memoriji... 18.03.2006. u 00:39 · pre 251 mesec #17

Pa dobro moglo je da se nasluti iz ORDER BY kluzule (ili gresim).

Code:

SELECT word FROM rel_table INNER JOIN sr_table ON rel_table.id2 = sr_table.id WHERE rel_table.id1 = ? ORDER BY word
SELECT word FROM rel_table INNER JOIN en_table ON rel_table.id1 = en_table.id WHERE rel_table.id2 = ? ORDER BY word

Potpis

Owl

Re: Elegancija resenja, serijalizacija strukture, cuvanje bazice u memoriji... 18.03.2006. u 02:00 · pre 251 mesec #18

Grešiš, pošto se ovde radi o drugom (zapravo prvom) wordu ;o)

Trebao sam odmah da napomenem, ali izgleda da sam mazohista :D

Forum kao aplikacija na telefonu

Srodne teme