Grote data sets efficient opslaan

[Blubber]

Ik zit met het volgende probleem, ik ben een zoek machine aan het maken die naar bestanden zoekt. Deze bestanden worden aangeboden door meerdere servers, via enkele protocollen (SMB en FTP hoofdzakkelijk).

Het probleem zit 'em in de opslag van deze data. Het is de bedoeling dat files met dezelfde naam maar een keer worden opgeslagen met een lijst van paden waar deze files staan. Ik werkte eerst met een Mysql database (tevens Postgres geprobeerd), maar beide voldoen niet aan mijn eisen wat betreft het zoeken. Ze bieden namelijk beide fulltext search aan (Postgress met behulp van Tsearch2), maar zijn niet in staat een gedeeltelijke match te doen. Zoek je bijvoorbeeld op "abc" dan zal een bestand met de aan abcd.zip niet gevonden worden. Ik heb die opgelost door de gehele DB te dumpen in een bestand, en vervolgens in het geheugen te laden. Momenteel zoek ik daar in met het Boyer Moore algoritme, dit gaat prima.

Anyway, ik zit nu dus met de opslag van de gegevens. Ze moeten namelijk makkelijk in te lezen zijn, maar ook makkelijk up te daten. Een database is het eerste waar ik aan dacht, maar dat maakt het indexeren vrij zwaar vanwege de eis dat elke bestandsnaam er maar een keer in voor mag komen. Ik kan ook alles in een of meerdere bestanden opslaan, maar dat is weer vrij moeilijk met onderhoud. Het verwijderen van een computer uit de index wordt dan bijvoorbeeld virj lastig.

Dus, wat zijn jullie gedachten hierover?

[mark platvoet]

Blubber schreef op zondag 01 juli 2007 @ 00:40:
Dus, wat zijn jullie gedachten hierover?

Mijn gedachte hierover is dat je de twee databases net even te snel aan de kan hebt geschoven, want uiteraard kan een dergelijke search wel. Dus nog even daar naar kijken

[ACM]

Ik snap niet heel goed wat je precies probeert te bereiken en vooral niet waarom je daar full text search voor nodig denkt te hebben. Alle unieke filenamen in een database opslaan is natuurlijk triviaal, gewoon met zo'n soort tabelschema:

filenames: filenameid (pk), filename (unique)
files: fileid (pk), filenameid (fk), fileextention, computerid (fk), filepath (of filepathid en een losse paths-tabel).

Zoeken naar de file abcd doe je dan met "where filename like 'abcd'" en naar abc* met "where filename like 'abc%'"

Als je ook nog netjes op je filepath wilt kunnen filteren zou je dat in postgresql in een 'ltree' (contrib-package) op kunnen slaan en daar een index over leggen, hoewel een varchar met een index op zich ook een heel eind komt.

Kortom, ik sluit me bij Mark aan en denk dat je de database te snel aan de kant geschoven hebt en/of te moeilijk denkt, of dat je ons te weinig meedeelt

[Voor 4% gewijzigd door ACM op 01-07-2007 11:58]

[Blubber]

ACM schreef op zondag 01 juli 2007 @ 11:57:
Ik snap niet heel goed wat je precies probeert te bereiken en vooral niet waarom je daar full text search voor nodig denkt te hebben. Alle unieke filenamen in een database opslaan is natuurlijk triviaal, gewoon met zo'n soort tabelschema:

filenames: filenameid (pk), filename (unique)
files: fileid (pk), filenameid (fk), fileextention, computerid (fk), filepath (of filepathid en een losse paths-tabel).

Yep, dat is het allereerste wat ik probeerde, maarja, als je een filename gaat inserten in een DB met 1.500.000 records, dan gaat dat nogal traag.

ACM schreef op zondag 01 juli 2007 @ 11:57:
Zoeken naar de file abcd doe je dan met "where filename like 'abcd'" en naar abc* met "where filename like 'abc%'"

Ook dat geprobeerd, uiteraard, maar dat gaat ook extreem traag.

ACM schreef op zondag 01 juli 2007 @ 11:57:
Als je ook nog netjes op je filepath wilt kunnen filteren zou je dat in postgresql in een 'ltree' (contrib-package) op kunnen slaan en daar een index over leggen, hoewel een varchar met een index op zich ook een heel eind komt.

Kortom, ik sluit me bij Mark aan en denk dat je de database te snel aan de kant geschoven hebt en/of te moeilijk denkt, of dat je ons te weinig meedeelt

Die tree heb ik nog niet geprobeerd, dat zal ik zo eens doen.

[LauPro]

Blubber schreef op zondag 01 juli 2007 @ 13:25:
Yep, dat is het allereerste wat ik probeerde, maarja, als je een filename gaat inserten in een DB met 1.500.000 records, dan gaat dat nogal traag.

Dat ligt geheel aan de indeling, ik heb hier een tabel met 10M+ records, inserten van een nieuwe row is milisecondenwerk, staan je indices wel goed?

[Motrax]

Heb je ook de indexen goed gezet op de kolommen waar je op wil zoeken?

1.5 mil records is niks Gisteren een join gedaan van 2.4 mil records tegen 64k. 0.16 seconden, het duurde langer om de query te versturen over de trage lijn die ik gebruikte, dan de uitvoer er van.

Full text search is wel relatief langzaam, maar zou niet extreem langzaam moeten zijn. Maar wat is traag in jouw geval?

Een record inserten zou binnen een seconde moeten gebeuren, tenzij je ook recursieve relaties erbij wil updaten. Maar zelfs dan nog zou het niet langer dan 5s moeten duren.

Sterker nog, databases zijn de enige manier om enorme datasets efficient op te slaan. Ik zou geen ander alternatief weten voor 1.5 mil records. De enige vraag is welke database en met welke inrichting.

[Blubber]

Motrax schreef op zondag 01 juli 2007 @ 13:33:
Heb je ook de indexen goed gezet op de kolommen waar je op wil zoeken?

1.5 mil records is niks Gisteren een join gedaan van 2.4 mil records tegen 64k. 0.16 seconden, het duurde langer om de query te versturen over de trage lijn die ik gebruikte, dan de uitvoer er van.

Full text search is wel relatief langzaam, maar zou niet extreem langzaam moeten zijn. Maar wat is traag in jouw geval?

Een record inserten zou binnen een seconde moeten gebeuren, tenzij je ook recursieve relaties erbij wil updaten. Maar zelfs dan nog zou het niet langer dan 5s moeten duren.

Sterker nog, databases zijn de enige manier om enorme datasets efficient op te slaan. Ik zou geen ander alternatief weten voor 1.5 mil records. De enige vraag is welke database en met welke inrichting.

Bij het inserten moet hij dus eerst uitvogellen of die filename al in de DB aanwezig is, zo niet dan moet hij hem inserten, anders hoeft hij enkel het path te inserten met de juiste fileid. Als dit alles 1 seconde duurt dan is dat een enorm probleem, met 2.4 milliioen inserts (~2.4M files, waarvan 1.5M met een unieke naam), zou dit meer dan een dag duren.

[LauPro]

Dat is gewoon onzin, als er echt per dag 2,4 miljoen unieke files aan die DB worden toegevoegd dan heb je het over ongeveer 30 inserts per seconden. Dat lijkt me nogal veel.

Als je bedoelt dat het er nu 2,4 miljoen zijn dan zou ook dat geen probleem moeten uitmaken, een dergelijke index wordt in het geheugen gezet (wat natuurlijk wel wat geheugen kost) en lookups zouden dan ook zeker maximaal 100ms moeten duren. Overigens stel dat elke file gemiddeld 250KB is dan heb je het bijna over een TB storage dat eraan zou hangen, lijkt me dat je daar ook wel een hele goede DB servers bij hebt.

[Blubber]

LauPro schreef op zondag 01 juli 2007 @ 14:30:
Dat is gewoon onzin, als er echt per dag 2,4 miljoen unieke files aan die DB worden toegevoegd dan heb je het over ongeveer 30 inserts per seconden. Dat lijkt me nogal veel.

Als je bedoelt dat het er nu 2,4 miljoen zijn dan zou ook dat geen probleem moeten uitmaken, een dergelijke index wordt in het geheugen gezet (wat natuurlijk wel wat geheugen kost) en lookups zouden dan ook zeker maximaal 100ms moeten duren. Overigens stel dat elke file gemiddeld 250KB is dan heb je het bijna over een TB storage dat eraan zou hangen, lijkt me dat je daar ook wel een hele goede DB servers bij hebt.

Misschien is een beetje uitleg wel op zijn plaats hier. Het betreft een netwerk van een 2000 tal computers. Waarvan een aantal als servers dienen. De totale capaciteit is ongeveer 82 TB. Een gemiddelde server heeft ongeveer 60.000 bestanden. Het gaat hier dus niet over DB servers, het gaat om machines die via SMB of FTP files aanbieden.

[Sv3n]

Blubber schreef op zondag 01 juli 2007 @ 14:35:
[...]


Misschien is een beetje uitleg wel op zijn plaats hier. Het betreft een netwerk van een 2000 tal computers. Waarvan een aantal als servers dienen. De totale capaciteit is ongeveer 82 TB. Een gemiddelde server heeft ongeveer 60.000 bestanden. Het gaat hier dus niet over DB servers, het gaat om machines die via SMB of FTP files aanbieden.

Maar er komen toch niet elke dag 2.4 mil. files bij ? het is een dus een kwestie van 1 keer inserten

[Blubber]

Sv3n schreef op zondag 01 juli 2007 @ 14:38:
[...]

Maar er komen toch niet elke dag 2.4 mil. files bij ? het is een dus een kwestie van 1 keer inserten

Er komen niet elke dag bestanden bij, maar, er zijn wel elke dag toevoegingen. Dus de index moet minimaal 1 keer per dag geupdate worden, wat een virj zware bewerking is als je van 60.000 bestanden (een typische server) moet nagaan of die reeds in de DB staan.

[RobIII]

Met de juiste (unique) constraints en indexes op de juiste kolommen moet het inserten van een 2.5m records echt geen dag duren; ik denk eerder in de orde van max. 1 uur (op een rete-trage server that is). Ergens doe je dus iets niet goed

[LauPro]

Kan je niet beter zo'n Google Enterprice Search server kopen? Waar jij naar op zoek bent is netwerk indexatie. Daar zijn echt al heel veel tools voor bedacht. Meestal werken ze met een spider die bijvoorbeeld een keer per dag alle servers langs gaan, je hebt ze ook die via een service werken die wijzingen monitort per server/pc.

[Blubber]

Maar stel dat ik het zo doe als ACM suggereerde:

filenames: filenameid (pk), filename (unique)
files: fileid (pk), filenameid (fk), fileextention, computerid (fk), filepath

Iets in die geest, dan moet ik dus voor elke insert in de files tabel, na gaan of die bestandsnaam reeds in de filenames tabel zit. Word dat niet onzettend traag als je voor leke insert 1.5M records moet nagaan?

[momania]

Blubber schreef op zondag 01 juli 2007 @ 14:51:


Iets in die geest, dan moet ik dus voor elke insert in de files tabel, na gaan of die bestandsnaam reeds in de filenames tabel zit. Word dat niet onzettend traag als je voor leke insert 1.5M records moet nagaan?

Dat is al een paar keer gezegd: nee. Zolang je je indices maar goed plaatst.

Is er geen dba aanwezig voor deze klus? Want ik heb nou niet echt het idee dat je weet waar je mee bezig bent (op database gebied dan)

[LauPro]

Je hoeft niets na te gaan, dat doet de DBMS voor je . Maar je checkt alleen op bestandsnaam? Zijn er geen dubbele bestanden in het netwerk? Of is het bestandnaam inclusief bestandspad? Je hebt het in je startpost over het voorkomen van dubbele bestanden, maar dan wil je dus eigenlijk een filesysteem gaan ontwerpen?

Is het fileid hetzelfde als een 'inode'? Of is dit een incredimenteel gegenereerd? Volgens mij kan je veel beter gebruik maken van een hash om te kijken of de bestanden al zijn opgeslagen.

Maar je hebt het nu telkens over een implementatie, wat wil je bereiken met je tool?

[_JGC_]

Daarvoor hebben ze een index uitgevonden. Als jij een tabel hebt met 100 miljoen records en je indexeert die dingen goed, hoeft er helemaal niet 100 miljoen records doorgescand te worden, maar heeft je databaseserver gewoon in het geheugen een boomstructuur opgebouwd waarmee in een paar operaties gevonden kan worden of wat jij zoekt ook aanwezig is. Op het moment dat zoiets traag wordt kunnen er twee problemen zijn: of je index staat niet goed ingesteld voor waar jij op wilt zoeken, of je index is zo groot dat deze niet meer in het geheugen past. Optie 1 zal heel vaak voorkomen, optie 2 komt eigenlijk alleen voor bij brakke servers of slecht ingestelde mysql servers.

[RobIII]

_JGC_ schreef op zondag 01 juli 2007 @ 15:00:
Op het moment dat zoiets traag wordt kunnen er twee problemen zijn: of je index staat niet goed ingesteld voor waar jij op wilt zoeken, of je index is zo groot dat deze niet meer in het geheugen past. Optie 1 zal heel vaak voorkomen, optie 2 komt eigenlijk alleen voor bij brakke servers of slecht ingestelde mysql servers.

Optie 2 is sowieso beter op te lossen: stoemp er wat geheugen bij, neem een heftigere server of verander iets anders aan de hardware. Dat is in 99% van de gevallen goedkoper dan software (her)schrijven. (En tuurlijk dien je een beetje netjes de devven; het is geen excuus om daarom maar lompe bakken code te gaan schrijven, maar als je ontwerp een beetje deugt is het vaak beter/goedkoper om de hardware wat aan te passen waar nodig).

edit:

En nu ik het teruglees: optie 1 is natuurlijk ook 'maar' een kwestie van je index wél goed zetten

[Voor 6% gewijzigd door RobIII op 01-07-2007 15:39]

[_JGC_]

Je kunt nog 8GB geheugen in je server stampen en 4 cores hebben, maar als je een beetje dikke database hebt en je queries niet goed doet of je indices niet goed hebt staan, trekt een enkele query je hele mysql op de knietjes.

[LauPro]

Kwestie van streng zijn, je kan de maximale query tijd op 5 seconden zetten bijvoorbeeld.

[ACM]

Blubber schreef op zondag 01 juli 2007 @ 13:25:
Yep, dat is het allereerste wat ik probeerde, maarja, als je een filename gaat inserten in een DB met 1.500.000 records, dan gaat dat nogal traag.

't Is al gezegd, maarreuh, als het inserten 'nogal traag' gaat bij 1.5M records doe je toch echt iets verkeerd. Ik ben in ieder geval benieuwd naar je precieze tabeldefinitie en de handelingen die je daarop uitvoert. Met een unique index op die filename zou je toch vrij rap er achter moeten komen dat je record al bestaat.

Ook dat geprobeerd, uiteraard, maar dat gaat ook extreem traag.

Met extreem traag heb je het over secondenwerk neem ik aan? En je hebt wel de unique index die nodig is om uberhaupt te voorkomen dat je dubbele records insert? Want ook hier geldt dat zolang je geen wildcard aan het begin zet je gewoon een index kunt gebruiken.

Die tree heb ik nog niet geprobeerd, dat zal ik zo eens doen.

Willekeurig van alles gebruiken zonder een analyze van de performance (dus verder gaand dan 'extreem traag') lijkt me weinig zinvol. Ik neem aan dat je weet dat je in postgresql na het vullen van een tabel met data het commando 'analyze' moet draaien, iig zodra de tabelinhoud sterk afwijkt van de vorige keer dat je het deed?
Om welke postgresql gaat het trouwens, 8.2.4? En wat komt er uit 'explain analyze' voor die extreem trage select?

[Confusion]

Blubber schreef op zondag 01 juli 2007 @ 14:40:
Er komen niet elke dag bestanden bij, maar, er zijn wel elke dag toevoegingen. Dus de index moet minimaal 1 keer per dag geupdate worden, wat een virj zware bewerking is als je van 60.000 bestanden (een typische server) moet nagaan of die reeds in de DB staan.

60000 Simpele selects op een tabel met 2.4 miljoen records met goede indices kost (hier) hooguit een minuut of 3 en het kan absoluut sneller dan dat. Voor 40 servers dus een uur of twee.

[Voor 4% gewijzigd door Confusion op 02-07-2007 07:52]

[Blubber]

ACM schreef op maandag 02 juli 2007 @ 07:32:
Willekeurig van alles gebruiken zonder een analyze van de performance (dus verder gaand dan 'extreem traag') lijkt me weinig zinvol. Ik neem aan dat je weet dat je in postgresql na het vullen van een tabel met data het commando 'analyze' moet draaien, iig zodra de tabelinhoud sterk afwijkt van de vorige keer dat je het deed?
Om welke postgresql gaat het trouwens, 8.2.4? En wat komt er uit 'explain analyze' voor die extreem trage select?

Ik gebruik momenteel 8.0.13. En ik doe na die grote inserts altijd een analyze.

code:

blubber=> EXPLAIN analyze SELECT * FROM filenames WHERE filename_name LIKE '%linux';
                                                   QUERY PLAN
----------------------------------------------------------------------------------------------------------------
 Seq Scan on filenames  (cost=0.00..29950.22 rows=446 width=35) (actual time=926.585..2693.578 rows=12 loops=1)
   Filter: ((filename_name)::text ~~ '%linux'::text)
 Total runtime: 2693.725 ms
(3 rows)

blubber=> EXPLAIN analyze SELECT * FROM filenames WHERE filename_name LIKE 'linux%';
                                                           QUERY PLAN                                                    
--------------------------------------------------------------------------------------------------------------------------------
 Index Scan using filename_name_key on filenames  (cost=0.00..5.92 rows=1 width=35) (actual time=0.258..1.965 rows=65 loops=1)
   Index Cond: (((filename_name)::text >= 'linux'::character varying) AND ((filename_name)::text < 'linuy'::character varying))
   Filter: ((filename_name)::text ~~ 'linux%'::text)
 Total runtime: 2.136 ms
(4 rows)

Voor %abc% en %abc gebruikt hji de index niet, voor abc% wel.

[momania]

Je hoeft toch ook nooit met '%abc' te zoeken? Je weet de naam van een nieuwe file, dus zoeken met 'abc' zou genoeg moeten zijn en gebruikt dus altijd de index.

[Blubber]

momania schreef op maandag 02 juli 2007 @ 11:26:
Je hoeft toch ook nooit met '%abc' te zoeken? Je weet de naam van een nieuwe file, dus zoeken met 'abc' zou genoeg moeten zijn en gebruikt dus altijd de index.

Je moet zeker wel in staat zijn om %abc% te zoeken. De meeste queries die worden uitgevoerd zullen het 'midden' van een filename matchen.

[momania]

Blubber schreef op maandag 02 juli 2007 @ 11:32:
[...]


Je moet zeker wel in staat zijn om %abc% te zoeken. De meeste queries die worden uitgevoerd zullen het 'midden' van een filename matchen.

Het gaat toch om indexatie van files op een netwerk? Dan heeft iedere file toch een unieke naam?

Leg eens uit waarom je dan toch files wilt zoeken middels '%abc%' ?

[mark platvoet]

Blubber schreef op maandag 02 juli 2007 @ 11:32:
Je moet zeker wel in staat zijn om %abc% te zoeken. De meeste queries die worden uitgevoerd zullen het 'midden' van een filename matchen.

Een 'LIKE' query is niet hetzelfde als een Index based full text search.

[Blubber]

momania schreef op maandag 02 juli 2007 @ 11:39:
[...]

Het gaat toch om indexatie van files op een netwerk? Dan heeft iedere file toch een unieke naam?

Leg eens uit waarom je dan toch files wilt zoeken middels '%abc%' ?

Omdat je bijvoorbeeld naar een bestand zoekt waarvan je alleen maar 1 deel van de naam kent, en niet kunt garanderen dat de naam daarme begint, wat heeft de uniekheid hier mee te maken?

mark platvoet schreef op maandag 02 juli 2007 @ 11:40:
[...]
Een 'LIKE' query is niet hetzelfde als een Index based full text search.

Daarom had ik een fulltext index gemaakt met TSearch2, maar die kan enkel gehele tokens matchen.

[mark platvoet]

Blubber schreef op maandag 02 juli 2007 @ 11:49:
Daarom had ik een fulltext index gemaakt met TSearch2, maar die kan enkel gehele tokens matchen.

Ik vraag me echt af hoe je tot die conlusie komt wat volgens mij kun je er zelfs regex in kwijt...

[user109731]

Blubber schreef op maandag 02 juli 2007 @ 11:22:
[...]
Ik gebruik momenteel 8.0.13.

Heb je nog een reden waarom je die versie gebruikt ipv 8.2.4? Als ik me goed herinner is de performance met 8.1 en 8.2 behoorlijk vooruit gegaan. Dat lijkt me dus wel interessant, zeker omdat je daar over in zit. Misschien interessant om eens te vergelijken?

[eghie]

JanDM schreef op maandag 02 juli 2007 @ 11:58:
[...]

Heb je nog een reden waarom je die versie gebruikt ipv 8.2.4? Als ik me goed herinner is de performance met 8.1 en 8.2 behoorlijk vooruit gegaan. Dat lijkt me dus wel interessant, zeker omdat je daar over in zit. Misschien interessant om eens te vergelijken?

Ik zou ook voor PostgreSQL 8.2 gaan met OpenFTS (Full Text Search). Die heeft ook nog de mogelijkheid voor ranking adv zoektermen. Was LIKE ook niet heel erg traag? (ah, dat heeft de TS al genoemd (iets met %zoekterm en zoekterm%)).
En inderdaad in 8.2 is er een hoop aan performance winst bijgekomen.

[Voor 11% gewijzigd door eghie op 02-07-2007 12:22]

[RobIII]

Blubber schreef op maandag 02 juli 2007 @ 11:22:
Voor %abc% en %abc gebruikt hji de index niet, voor abc% wel.

Nogal wiedes lijkt me. Probeer eens in het telefoonboek een '%boer%' te vinden? Een 'boer%' is dan heel wat makkelijker he?

Blubber schreef op maandag 02 juli 2007 @ 11:32:
Je moet zeker wel in staat zijn om %abc% te zoeken. De meeste queries die worden uitgevoerd zullen het 'midden' van een filename matchen.

Dat is voor het front-end (?) interessant, maar toch niet voor je file-indexer?

Blubber schreef op maandag 02 juli 2007 @ 11:49:
Omdat je bijvoorbeeld naar een bestand zoekt waarvan je alleen maar 1 deel van de naam kent, en niet kunt garanderen dat de naam daarme begint, wat heeft de uniekheid hier mee te maken?

Maar again; wat heeft dat te maken met het inserten van je records, of het afdwingen van de unique constraint En daar kan dan prima gebruik worden gemaakt van indices.

Blubber schreef op maandag 02 juli 2007 @ 11:49:
Daarom had ik een fulltext index gemaakt met TSearch2, maar die kan enkel gehele tokens matchen.

Ik heb een beetje het idee dat je gewoon als een dolle vanalles en nog wat probeert zonder je echt in de documentatie te verdiepen; van dik hout zaagt met planken zeg maar Als je nou eens even rustig de tijd neemt om je er in te verdiepen dan zul je bij het teruglezen van dit topic ook zien waar wij ons allemaal over zitten te verbazen

[Blubber]

RobIII schreef op maandag 02 juli 2007 @ 12:21:
Nogal wiedes lijkt me. Probeer eens in het telefoonboek een '%boer%' te vinden? Een 'boer%' is dan heel wat makkelijker he?

Dat is inderdaad een stuk makkelijker, maar niet waar ik naar op zoek ben.

Dat is voor het front-end (?) interessant, maar toch niet voor je file-indexer?\

Maar again; wat heeft dat te maken met het inserten van je records, of het afdwingen van de unique constraint En daar kan dan prima gebruik worden gemaakt van indices.

Ik had het over het frontend, misschien was dat niet geheel duidelijk. En inderdaad, voor het indexeren werkt die index perfect.

Ik heb een beetje het idee dat je gewoon als een dolle vanalles en nog wat probeert zonder je echt in de documentatie te verdiepen; van dik hout zaagt met planken zeg maar Als je nou eens even rustig de tijd neemt om je er in te verdiepen dan zul je bij het teruglezen van dit topic ook zien waar wij ons allemaal over zitten te verbazen

Het gebruik van TSearch2 was wel overwogen. Destijds ging ik er vanuit dat je altijd 1 token van het bestand wat je zoekt volledig kent. (TSearch2 tokenized o.a. op spaties, dus dat leek logisch) Echter, het komt vrij vaak voor dat je het volledige woord wel kent, maar dat de file toch een iets andere schrijfwijze heeft, waardoor je hem dus niet vind. (Volgens de documentatie ondersteund TSearch2 geen pre- of suffix search).

[Confusion]

Blubber schreef op maandag 02 juli 2007 @ 11:49:
Omdat je bijvoorbeeld naar een bestand zoekt waarvan je alleen maar 1 deel van de naam kent, en niet kunt garanderen dat de naam daarme begint, wat heeft de uniekheid hier mee te maken?

Je had het net over het vergelijken van de volledige unieke naam, om de database te kunnen updaten. Daarvoor heb je geen LIKE '%abc%' nodig. De query die jij nu als 'te traag' benoemd, waarbij gebruikers blijkbaar een bestand zoeken, die wordt veel minder vaak uitgevoerd mag ik hopen.

[Blubber]

Confusion schreef op maandag 02 juli 2007 @ 13:03:
[...]

Je had het net over het vergelijken van de volledige unieke naam, om de database te kunnen updaten. Daarvoor heb je geen LIKE '%abc%' nodig. De query die jij nu als 'te traag' benoemd, waarbij gebruikers blijkbaar een bestand zoeken, die wordt veel minder vaak uitgevoerd mag ik hopen.

Dat updaten gaat nu wel goed, en daar heb je die %abc% uiteraard niet voor nodig. De query die te traag is, is het zoeken. De snelheid van het zoeken (de essentie van het programma), is het aller belangrijkst.

[Voor 7% gewijzigd door Blubber op 02-07-2007 13:46]

[eghie]

Blubber schreef op maandag 02 juli 2007 @ 13:33:
[...]


Dat updaten gaat nu wel goed, en daar heb je die %abc% uiteraard niet voor nodig. De query die te traag is, is het zoeken. De snelheid van het zoeken (de essentie van het programma), is het aller belangrijkst.

Ook openFTS al geprobeerd?

[ACM]

Ik heb nog even de proef op de som genomen: alle files op mijn gentoo-linux servertje (een goedkoop sempron-doosje met 512MB ram) geindexeerd in een nauwelijks geoptimaliseerde postgresql 8.2.4, in deze triviale structuur:

                                       Table "public.files"
    Column     |          Type           |                       Modifiers
---------------+-------------------------+--------------------------------------------------------
 fileid        | integer                 | not null default nextval('files_fileid_seq'::regclass)
 filenameid    | bigint                  | not null
 filepath      | character varying(4080) | not null
 fileextension | character varying(230)  | not null
Indexes:
    "files_pkey" PRIMARY KEY, btree (fileid)
    "files_filenameid_idx" btree (filenameid)
    "files_filepath_idx" btree (filepath)

                                       Table "public.filenames"
   Column   |          Type          |                           Modifiers
------------+------------------------+----------------------------------------------------------------
 filenameid | integer                | not null default nextval('filenames_filenameid_seq'::regclass)
 filename   | character varying(255) | not null
Indexes:
    "filenames_pkey" PRIMARY KEY, btree (filenameid)
    "filenames_filename_key" UNIQUE, btree (filename)

Het inserten van alle 557.913 files met 126.956 unieke namen duurde in totaal iets van 12 minuten. Maar daar was je zelf ook al achter dat het vrij snel kan.

Het tellen van alle files die in /usr zitten (318.078) kost hem minder dan een halve seconde. Het tellen welke files er allemaal zijn met de term 'abc' erin met een triviale like '%abc%' kost 'm in eerste instantie 1.5 seconde met een naive aanpak. Toen ik postgresql een handje hielp door eerst een temporary table aan te leggen met de filenameids kostte het ongeveer 0.08 seconde.

Daarna bedacht ik me dat de standaard statistics target van 10 op filename.filenames en files.filenameid mogelijk niet zo goed is en heb ik die verhoogd van 10 naar 1000. Een nieuwe analyze, en ook de naive aanpak gaat binnen 0.08 seconde:

acm=# select count(*) from files where filenameid in (select filenameid from filenames where filename like '%abc%');
count
-------
63
(1 row)

Time: 74.256 ms

of:

acm=# select count(*) from files natural join filenames where filename like '%abc%';
count
-------
63
(1 row)

Time: 73.541 ms

Of een filenaam die wat vaker voorkomt:
acm=# select count(*) from files natural join filenames where filename like '%linux%';
count
-------
2552
(1 row)

Time: 129.338 ms


Kortom, er is een hoop mogelijk met postgresql, voor je het serieus als te traag kan bestempelen, imho. Maar de tip om over te gaan naar postgresql 8.2.4 lijkt me sowieso de eerste om na te gaan, de performance is o.a. bij like-queries sterk verbeterd.

Daarnaast vraag ik me af hoe groot jouw filenames-tabel (is ie recentelijk nog gevacuumed?) is als ie er 2.6 seconde over doet om alles met linux erin te vinden. Ook is het mogelijk dat jouw databasemachine gewoon niet genoeg geheugen heeft om die tabel in zijn geheugen te houden en hij hem steeds van trage disks in moet lezen, in dat geval kan postgres sowieso maar weinig beginnen, hoewel ook daar postgresql 8.2 beter mee is dan 8.0 vziw. Want mijn systeem is dus slechts een single core single socket 1.8Ghz cputje met slechts 512MB non-dedicated geheugen (er zit ook nog een apache2, mysql, e.a. in) en met slechts 1 simpele sata disk. Als dat zoeken zo cruciaal is mag ik hopen dat je minstens die filenamestabel compleet in je geheugen kwijt kan en anders wordt het tijd met de managers te gaan praten

[Blubber]

blubber=# select relname, reltuples, pg_size_pretty(pg_relation_size(oid)) from pg_class where relname ~~ 'filenames%';
relname | reltuples | pg_size_pretty
----------------+-------------+----------------
filenames | 1.37917e+06 | 178 MB
filenames_fti | 1.37917e+06 | 63 MB
filenames_pkey | 1.37917e+06 | 152 MB
(3 rows)

Die fti is een TSearch2 fulltext index die ik heb gemaakt om even mee te experimenteren.

blubber=# EXPLAIN ANALYZE SELECT COUNT(*) FROM filenames WHERE filename LIKE '%linux%';
QUERY PLAN
-----------------------------------------------------------------------------------------------------------------------
Aggregate (cost=40007.17..40007.18 rows=1 width=0) (actual time=2230.620..2230.621 rows=1 loops=1)
-> Seq Scan on filenames (cost=0.00..40001.65 rows=2207 width=0) (actual time=180.970..2229.866 rows=196 loops=1)
Filter: ((filename)::text ~~ '%linux%'::text)
Total runtime: 2230.744 ms
(4 rows)

Dit volgende is na dat ik de statistics target op 1000 heb gezet, en na een ANALYZE:

blubber=# EXPLAIN ANALYZE SELECT COUNT(*) FROM filenames WHERE filename LIKE '%l inux%';
QUERY PLAN
-------------------------------------------------------------------------------- --------------------------------------
Aggregate (cost=40083.80..40083.81 rows=1 width=0) (actual time=2235.371..2235 .372 rows=1 loops=1)
-> Seq Scan on filenames (cost=0.00..40083.45 rows=139 width=0) (actual tim e=181.207..2234.610 rows=196 loops=1)
Filter: ((filename)::text ~~ '%linux%'::text)
Total runtime: 2235.523 ms
(4 rows)

En dat is na een verse VACUUM, in de tabel die enkel unieke filenames bevat. Er zit 1 gb ram in dat ding. Het is hier ook een single core P3 1.3Ghz Het betreft hier overigens geen commercieel project, dus er is geen management aanwezig om bij te klagen .

Voor ik het vergeet, ik heb inmiddels naar 8.2.4 geupgrade, bovestaande resultaten zijn met 8.2.4.

Overigens denk ik dat het niet aan postgres ligt, als ik dit zo zie. Text matchen met LIKE, hoe traag het ook is, moet veel sneller kunnen dan 2 seconden. Het lijkt er wel op of hij de tabel niet in het geheugen houdt.

[Voor 6% gewijzigd door Blubber op 03-07-2007 01:23]

[Confusion]

Hoeveel geheugen heb je aan postgres toegewezen in de config? Meer dan dat zal hij niet gebruiken.

[ACM]

Blubber schreef op dinsdag 03 juli 2007 @ 01:10:
blubber=# select relname, reltuples, pg_size_pretty(pg_relation_size(oid)) from pg_class where relname ~~ 'filenames%';
relname | reltuples | pg_size_pretty
----------------+-------------+----------------
filenames | 1.37917e+06 | 178 MB
filenames_fti | 1.37917e+06 | 63 MB
filenames_pkey | 1.37917e+06 | 152 MB
(3 rows)

Wat sla je er allemaal in op? Hoe lang is jouw gemiddelde filename. Met name het kleine verschil in grootte tussen de tabel zelf en je PK vind ik erg curieus, heb je de naam van de file zelf als PK gebruikt?

Dit is de mijne, een factor 10 minder records en een factor 24 kleiner in opslag:

         relname          | reltuples | pg_size_pretty
--------------------------+-----------+----------------
 filenames                |    126956 | 7568 kB
 filenames_filename_key   |    126956 | 6296 kB
 filenames_filenameid_seq |         1 | 8192 bytes
 filenames_pkey           |    126956 | 2792 kB

Dit volgende is na dat ik de statistics target op 1000 heb gezet, en na een ANALYZE:

Dat heeft helemaal geen effect op deze query Alleen op queries waarbij de schatting van het verwachte aantal records iets uit maakt voor de manier waarop ie uitgevoerd wordt (bijv als je deze query als join of subselect in een groter geheel opneemt en er gekozen moet worden tussen een merge/hash join of nested loop), in dit geval is er gewoon niets anders mogelijk dan sequential scan.

Er zit 1 gb ram in dat ding. Het is hier ook een single core P3 1.3Ghz Het betreft hier overigens geen commercieel project, dus er is geen management aanwezig om bij te klagen .

Je tabel bevat 10x zoveel records en is 24x groter in fysieke grootte dan de mijne, terwijl je processor langzamer is en die het ook nog eens met langzamer geheugen moet doen. Dus dan verbaast het me niet dat je 20-30x langer over je query doet.

Overigens denk ik dat het niet aan postgres ligt, als ik dit zo zie. Text matchen met LIKE, hoe traag het ook is, moet veel sneller kunnen dan 2 seconden. Het lijkt er wel op of hij de tabel niet in het geheugen houdt.

Wat voor werk doet deze PC nog meer? En als je filenames-tabel al deze maat heeft, hoe groot is dan je files-tabel zelf? Maar zoals ik al zeg, aangezien mijn (blijkbaar) snellere servertje het slechts een factor 20-30x sneller kan weet ik niet of dit wel sneller kan in postgresql. Niet zolang je vast zit aan die sequential scan of je de grootte van je tabel niet kan verminderen.

[Blubber]

Die filenames tabel heeft alleen de naam van het bestand, de extensie en de datum dat hij voor het eerst voor kwam. Filename is de pkey.

Die sequential scan is inderdaad brak, maargoed, hij zou de hele DB moeten kunnen cachen in het geheugen. Die bak doet verder niets namelijk.

[DataGhost]

Dan vergeet je denk ik ook nog het verschil tussen SDR- en DDR-geheugen, ik kan namelijk met redelijke zekerheid zeggen dat die P3 het met SDR-geheugen moet stellen en die Sempron DDR-geheugen heeft. Daarbij komt ook het verschil in bussnelheid, 133 vs 166 MHz. Ik denk dat dit ook een flink stuk bijdraagt aan de sneltraagheid.

[ACM]

Blubber schreef op dinsdag 03 juli 2007 @ 10:18:
Die sequential scan is inderdaad brak,

Sja, je ontkomt er bijna niet aan. Je zou eventueel nog triplets (combinaties van drie tekens uit de naam) kunnen indexeren, maar je hebt kans dat dat een dusdanig forse overhead heeft dat dat niet sneller is.

hij zou de hele DB moeten kunnen cachen in het geheugen. Die bak doet verder niets namelijk.

De kans is groot dat ie dat ook doet. Als het een linux-doos is met recente kernel kan je zoiets triviaal als root de file-cache leeg maken "echo 1 > /proc/sys/vm/drop_caches" en zien hoe lang het dan duurt.

[Blubber]

blubber=# EXPLAIN ANALYZE SELECT COUNT(*) FROM filenames WHERE filename LIKE '%linux%';
QUERY PLAN
---------------------------------------------------------------------------------------------------------------------
Aggregate (cost=28443.99..28444.01 rows=1 width=0) (actual time=732.042..732.042 rows=1 loops=1)
-> Seq Scan on filenames (cost=0.00..28438.45 rows=2217 width=0) (actual time=24.001..732.042 rows=196 loops=1)
Filter: ((filename)::text ~~ '%linux%'::text)
Total runtime: 732.042 ms
(4 rows)

Dat is op een Dual Core AMD 3000+, met 2gb ram. Postgres 8.2.4. Exact dezelfde DB. Ik vraag me erg af hoe postgres die LIKE query afhandeld. Anyway, ik zal dus een andere oplossing moeten zoeken, of me bij TSearch2's beperkingen neerleggen, maar in ieder geval bedankt voor de hulp .

[dawuss]

Aangezien ik zie in je profiel dat je aan de Universiteit Twente studeert, gok ik dat je een campusnet zoekmachine probeert te maken. Heb je al contact opgenomen met de makers van dance, swing, infofind e.d. die dit soort problemen eerder al tegengekomen zouden kunnen zijn?

[MeatLoaf]

Blubber schreef op dinsdag 03 juli 2007 @ 10:18:
Die filenames tabel heeft alleen de naam van het bestand, de extensie en de datum dat hij voor het eerst voor kwam. Filename is de pkey.
[..]

Voor een goede database structuur is het sowieso niet verstandig om een varchar als primary key te gebruiken. Het joinen over dit soort primary keys, wil nog wel eens een table scan opleveren wat je query dan super traag maakt.
Dus gewoon in elke tabel een extra kolom op nemen met een integer en deze als primary key gebruiken.

[Niemand_Anders]

De reden dat hij bij abc% wel de index gebruik is omdat je een slimme database server gebruikt! Je database maakt er dan een left(filename, 3) = 'abc' van en dan kan ie supersnel door de indexen lopen. Een index is een soort inhouds opgave. Zolang hij de eerste x letters kan gebruiken kan de index worden gebruikt. Moet hij iets in het midden of einde vinden, dan zal een sequence scan plaats vinden, ofwel worden alle velden 1 voor 1 nagelopen. Denk maar eens aan een telefoonboek. Jij kunt wel erg eenvoudig alle nummer vinden van namen die beginnen met 'Smi'. Maar namen die eindigen op 'it' is dan ineens een stuk lastiger..

Je moet zeker wel in staat zijn om %abc% te zoeken. De meeste queries die worden uitgevoerd zullen het 'midden' van een filename matchen.

maar niet bij het INSERTEN/UPDATEN van bestanden in je database. Heb je eigenlijk wel enig idee waar je mee bezig bent? Je haal zoek opdrachten en indexering door elkaar!

[Blubber]

Niemand_Anders schreef op dinsdag 03 juli 2007 @ 11:30:
De reden dat hij bij abc% wel de index gebruik is omdat je een slimme database server gebruikt! Je database maakt er dan een left(filename, 3) = 'abc' van en dan kan ie supersnel door de indexen lopen. Een index is een soort inhouds opgave. Zolang hij de eerste x letters kan gebruiken kan de index worden gebruikt. Moet hij iets in het midden of einde vinden, dan zal een sequence scan plaats vinden, ofwel worden alle velden 1 voor 1 nagelopen. Denk maar eens aan een telefoonboek. Jij kunt wel erg eenvoudig alle nummer vinden van namen die beginnen met 'Smi'. Maar namen die eindigen op 'it' is dan ineens een stuk lastiger..


[...]

maar niet bij het INSERTEN/UPDATEN van bestanden in je database. Heb je eigenlijk wel enig idee waar je mee bezig bent? Je haal zoek opdrachten en indexering door elkaar!

Ik weet ook wel dat hij bij een INSERT/UPDATE die %abc% niet gebruikt, maar gewoon een exact match op de boom van die index. Ik haal het zoeken en indexeren absoluut niet door mekaar, tenminste niet in mijn hoofd. Wel een beetje qua tekst hier misschien . Feit blijft, dat ik hierboven ook al gezegd heb dat het inserten het probleem niet meer is.

[.oisyn]

Even afgezien van het feit dat databases hier op zich prima voor bruikbaar zijn zou ik zelf voor een custom implementatie gaan omdat je usecase nogal specifiek is. Hierdoor kun je ook eigen datastructuren aanbrengen die het zoeken naar willekeurige patronen veel efficienter maken.

[Blubber]

.oisyn schreef op dinsdag 03 juli 2007 @ 12:04:
Even afgezien van het feit dat databases hier op zich prima voor bruikbaar zijn zou ik zelf voor een custom implementatie gaan omdat je usecase nogal specifiek is. Hierdoor kun je ook eigen datastructuren aanbrengen die het zoeken naar willekeurige patronen veel efficienter maken.

Dat is precies wat ik dacht toen ik naar zoek algoritmen op zoek ging. Boyer-Moore lijkt een goed algoritme om patronen efficient te zoeken, triplets is ook een optie. Postgres blijft wel een goede optie om meta informatie op te slaan lijkt mij.

[.oisyn]

Boyer-Moore is handig als je een substring zoekt in een grote tekst. Hier zoek je ook wel naar substrings, maar niet in een grote tekst - om te matchen zul je nog altijd alle filenames af moeten wandelen, en dat is in principe niet wat je wilt. Ik zat eerder te denken aan een grote suffix array van alle filenames, zodat je in O(log N) een selectie kunt maken van alle files waar een bepaalde substring in voorkomt.

Een erg naïeve C++ implementatie die teveel mem gebruikt:

C++:

typedef std::vector<std::string> file_vec;
typedef std::map<std::string, file_vec> suffix_map;

suffix_map myMap;

void insertFilename(const std::string & filename)
{
    for (size_t i = 0; i < filename.size(); i++)
        myMap[filename.substr(i)].push_back(filename);
}

void search(const std::string & substring, file_vec & results)
{
    results.clear();

    suffix_map::iterator it = myMap.lower_bound(substring);
    while (it != myMap.end() && !it->first.compare(0, substring.size(), substring))
    {
        results.insert(results.end(), it->second.begin(), it->second.end());
        ++it;
    }
}

[Voor 45% gewijzigd door .oisyn op 03-07-2007 13:56]