Cookies op Tweakers

Tweakers maakt gebruik van cookies, onder andere om de website te analyseren, het gebruiksgemak te vergroten en advertenties te tonen. Door gebruik te maken van deze website, of door op 'Ga verder' te klikken, geef je toestemming voor het gebruik van cookies. Wil je meer informatie over cookies en hoe ze worden gebruikt, bekijk dan ons cookiebeleid.

Meer informatie
Toon posts:

Grote data sets efficient opslaan

Pagina: 1
Acties:

Onderwerpen


Acties:
  • 0Henk 'm!

  • Blubber
  • Registratie: mei 2000
  • Niet online
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?

Acties:
  • 0Henk 'm!

  • Blubber
  • Registratie: mei 2000
  • Niet online
quote:
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.
quote:
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.
quote:
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.

Acties:
  • 0Henk 'm!

  • Blubber
  • Registratie: mei 2000
  • Niet online
quote:
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.

Acties:
  • 0Henk 'm!

  • Blubber
  • Registratie: mei 2000
  • Niet online
quote:
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.

Acties:
  • 0Henk 'm!

  • Blubber
  • Registratie: mei 2000
  • Niet online
quote:
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.

Acties:
  • 0Henk 'm!

  • Blubber
  • Registratie: mei 2000
  • Niet online
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?

Acties:
  • 0Henk 'm!

  • Blubber
  • Registratie: mei 2000
  • Niet online
quote:
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:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
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.

Acties:
  • 0Henk 'm!

  • Blubber
  • Registratie: mei 2000
  • Niet online
quote:
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.

Acties:
  • 0Henk 'm!

  • Blubber
  • Registratie: mei 2000
  • Niet online
quote:
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?
quote:
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.

Acties:
  • 0Henk 'm!

  • Blubber
  • Registratie: mei 2000
  • Niet online
quote:
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.
quote:
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.
quote:
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 :P 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).

Acties:
  • 0Henk 'm!

  • Blubber
  • Registratie: mei 2000
  • Niet online
quote:
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]


Acties:
  • 0Henk 'm!

  • Blubber
  • Registratie: mei 2000
  • Niet online
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 :s.

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]


Acties:
  • 0Henk 'm!

  • Blubber
  • Registratie: mei 2000
  • Niet online
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.

Acties:
  • 0Henk 'm!

  • Blubber
  • Registratie: mei 2000
  • Niet online
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 :).

Acties:
  • 0Henk 'm!

  • Blubber
  • Registratie: mei 2000
  • Niet online
quote:
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.

Acties:
  • 0Henk 'm!

  • Blubber
  • Registratie: mei 2000
  • Niet online
quote:
.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.
Pagina: 1


Apple iPhone SE (2020) Microsoft Xbox Series X LG CX Google Pixel 4a CES 2020 Samsung Galaxy S20 4G Sony PlayStation 5 Nintendo Switch Lite

'14 '15 '16 '17 2018

Tweakers vormt samen met Hardware Info, AutoTrack, Gaspedaal.nl, Nationale Vacaturebank, Intermediair en Independer DPG Online Services B.V.
Alle rechten voorbehouden © 1998 - 2020 Hosting door True