Hoe sorteer en filter je een enorme dataset?

[kanduvisla]

Ik zit samen met een collega van mij al een tijdje met de handen in het haar omtrent een lastig vraagstuk.

Een klant van ons heeft een webshop met 500.000+ producten. Op zich niets vreemds, maar er zitten een aantal haken en ogen aan:

• Onze klant werkt met meerdere toeleveranciers. Het kan daardoor dus voorkomen dat leveranciers overlap hebben in het productassortiment. In dat geval moet de prijs van de goedkoopste leverancier gebruikt worden bij het sorteren.
• De klanten van onze klant (organisaties) hebben ook een unieke eigenschap: zij krijgen speciaal toegespitste korting op bepaalde producten, maar alleen weer bij bepaalde leveranciers. Zo kan het dus zijn dat voor product X organisatie A goedkoper uit is bij leverancier M, en organisatie B voor hetzelfde product goedkoper uit is bij leverancier N. Hier moet dus ook rekening mee gehouden worden bij het sorteren op prijs.
• Bij producten komen attributen. Deze attributen worden ook uit een externe bron ingeladen (zoiets als ICECAT). Op deze attributen moet dan weer gefilterd kunnen worden. Voetnoot: het gaat hierbij dus al snel over 20.000+ verschillende attributen in totaal.

Uiteindelijk heb je dus een productcatalogus-pagina welke voor iedere klant op een andere manier gesorteerd kan worden, en welke tevens ook nog gefilterd kan worden op meerdere attributen.

Het wonderbaarlijke is dat we dit momenteel al werkend hebben, alleen we lopen tegen een probleem aan: het is tergend traag. Een simpel overzicht laden kan soms al 15 seconden duren. De meest voor de hand liggende optimalisaties zijn al gedaan: denk aan indexeren van kortingsprijzen, indexen op tabellen, etc.

De hosting is bij Amazon. 8 cores, 15 GB ram.

Mijn vraag is niet direct wat de oplossing zou zijn voor ons, maar meer hoe jullie een dergelijke situatie in zouden richten / op zouden zetten. Wat voor database structuur? Design patterns? Server instellingen?

Elke hulp is welkom!

edit:

Omdat er om meer achtergrondinformatie gevraagd werd:

Het betreft een Magento webshop.

Onze huidige oplossing is als volgt:

• We hebben een tweede database met alle attributen / values en product ID's. Het doel van deze database is louter het koppelen van attributen / waarden aan producten. Deze database wordt gevoed vanuit externe bronnen voor productverrijking (2ba, ICECAT, custom dingetjes, etc). Het resultaat is één grote bak waarmee we adhv een EAN-code alle beschikbare productinformatie uit kunnen lezen.
• De kortingsregels worden opgeslagen in de database en de juiste kortingen worden bij mutaties van tevoren berekend en opgeslagen in een geïndexeerde-kortings-prijzen-tabel. Deze tabel geeft per product een prijs aan de hand van de combinatie productID - kortingsregelID - leverancierID. We hebben ook geprobeerd de koppeling te versimpelen door met een combinatie productID - organisatieID te werken, maar dit had exponentionele groei van de tabel tot gevolg (1,5 miljoen records t.o.v. 2.5 miljard records).
• Voor het filteren en sorteren haken we in op Magento en maken een join met de geindexeerde prijs-tabel om te kunnen sorteren op de voorberekende prijs (omdat iedere organisatie een andere prijs voor een product kan hebben), en om te filteren maken we een join met de desbetreffende tabellen in de product-attributen database.

Query caching heeft voor ons niet veel toegevoegde waarde, aangezien het organisatieID een fundamenteel onderdeel is voor de query: het ID van de organisatie is bepalend voor het resultaat. Omdat het om heel veel organisaties gaat en heel veel producten, kún je wel cachen, maar iedere resultset is voor iedere organisatie weer uniek, wat caching een beetje teniet doet. Hetzelfde geld voor gegenereerde pagina's.

[ Voor 32% gewijzigd door kanduvisla op 08-01-2016 16:34 . Reden: verzoek vanuit reacties ]

[NMe]

Je noemt indexes als optimalisatie maar in gevallen als dit heb je ook heel veel aan diverse caches. Query cache natuurlijk, maar voor spul als dit kun je over het algemeen ook gewoon de uitgegenereerde pagina's cachen. Hoe heb je dat geregeld?

[BlueZero]

Als ik zelf in mijn werk datasets van die grote moet behandelen dan bouw ik een in memory database in bijvoorbeeld Java om de juiste sets te genereren. Echter zoiets zelf bouwen kan veel tijd kosten of technisch niet haalbaar zijn. Dan is het misschien slim om naar standaard oplossingen te kijken zoals Elasticsearch.

Echter je bent hier afhankelijk van een externe bron en dat is altijd een vertragende factor als je hier op wilt kunnen filteren. Verrijken in je resultaten lijst hoeft geen probleem te zijn als je bijvoorbeeld paginatie gebruikt.

Nu weet ik echter niet wat de mogelijkheden van je externe datavendor zijn.

Neem meestgebruikte filter-attributen in je eigen dataset op. Zoek dan met die producten bij je datavendor op een of meerdere attributen.

En bouw met die lijst je resultatenpagina op.

[Creepy]

Mijn vraag is niet direct wat de oplossing zou zijn voor ons, maar meer hoe jullie een dergelijke situatie in zouden richten / op zouden zetten. Wat voor database structuur? Design patterns? Server instellingen?

Misschien ook handig om dit soot zaken eerst eens te vertellen over jullie oplossing op dit moment, dat geeft ons een stuk meer informatie.

[Standeman]

De producten en attributen zijn in principe voor iedereen gelijk en die kan je dus prima eenmaal in het geheugen cachen waarmee je met binary searches vrij snel door heen loopt. Dat soort zaken zou ik niet met SQL uit een database gaan halen.

[ Voor 15% gewijzigd door Standeman op 08-01-2016 16:17 ]

[kanduvisla]

Ik heb een kleine edit gedaan aan de originele post n.a.v. jullie reacties.

V.w.b. producten en attributen: in het geheugen cachen klinkt interessant. Maar hoe pas je zoiets toe? Het is niet dat ik attributen / waarden ophaal, maar ik moet erop filteren zodat mijn resultset klopt.

[BlueZero]

Ik denk dat gezien je opzet het prima mogelijk is om dit met MySQL te doen en wel op de volgende manier.

Verklein je resultatenset op basis van filters
Oftewel zoek in de attributen tabel op key,value en return Distinct EAN Code, zoek met die code verder i.c.m. een where in. Als je dan alle gekozen filters hebt doorlopen heb je dus een lijst met EAN codes die aan alle filters voldoet. Als je op de kolommen attribuut-naam, value en EAN-code een index aanmaakt moet dit best rap kunnen.

Sorteer overgebleven resultaten
Doe een Where-In query in de prijzen tabel met je EAN-codes sorteer op prijs en return top-10 (afhankelijk van aantal resultaten op 1 pagina)

Haal productinfo op en presenteer
Met je top10 EAN codes doe je de producten ophaal en presenteer die.

[BCC]

Ik zou voor zoiets een search engine naast je product database gaan zetten. Solr of elasticsearch Moeten hiervoor prima werken. Hier doe je het zoeken, filteren etc en deze levert een lijst product ids als resultaat. Je hoeft dan alleen nog maar het product uit de database te halen en de prijs te berekenen.

En wat hierboven al aangeven is, hoeveel geheugen heeft mysql? En hoe is het met de diskio?

[ Voor 54% gewijzigd door BCC op 08-01-2016 17:08 ]

[Hydra]

What he ^^ said. Ik zou echt eens naar ElasticSearch kijken. Die is min of meer gemaakt voor dit soort toepassingen.

[BCC]

Solr is vaak eenvoudiger voor dit soort dingen omdat elasticsearch veel meer kan wat je hier niet direct nodig hebt.

[MSalters]

Full-text search engines aanraden voor gestructureerde data? Dat is niet de meest effectieve methode, en dat kun je gerust een understatement noemen.

Dit is een klassiek relationeel probleem, en je lost het relationeel op. Als dat niet werkt, check je queries. Welke hebben er een table scan nodig, en waarom?

Ik denk dat het idee "productID - organisatieID" de goede keuze was, mits je het alleen gebruikt voor afwijkende prijzen. Die 2.5 miljard entries was vermoedelijk omdat je 1500 klanten hebt, die niet overal korting krijgen. Sla in die tabel alleen de echte kortingsprijzen op, en de prijs zonder korting voor organisatieID NULL. Doe vervolgens een SELECT WHERE prijs.organisatieID = klant OR prijs.organisatieID IS NULL

[BCC]

Msalters: solr en elasticsearch kunnen toch wel ietsjes meer hoor ik gebruik solr bijvoorbeeld voor een klant om aan de hand van user agent & land een database van miljoenen Android apps realtime te filteren, zodat je alleen resultaten krijgt in jouw taal en compatibel met jouw device. Structurele data idd in een rationele database, extreme slicing en dicing -> ergens anders

Maar ik denk dat de ts eerst weer wat antwoorden moet geven

[ Voor 7% gewijzigd door BCC op 09-01-2016 08:43 ]

[Croga]

In feite is je probleem sterk vergelijkbaar met dat van ons. Het enige verschil is dat onze dimensies anders zijn (8.5 miljoen producten, 50 filters, alleen klant-specifieke prijs manipulatie).

Onze conclusie was: Dit is onmogelijk in een on-disc database systeem op te lossen. De performance gaat het gewoon, simpelweg, niet trekken (we zitten op grofweg 500'000 hits per dag, wellicht dat dat bij jullie lager ligt).

De enige manier waarop je dit gaat trekken is met een in-memory database systeem zoals Elastic. En dan zijn de systeem eisen iets hoger dan wat je nu draait (voor onze case is de huidige inschatting 4 nodes met 128GB RAM ieder).

Onze tweede conclusie was; Huur een specialist in. We praten hier niet over iets wat eenvoudig in code op te lossen is; je hebt hier database specialisatie nodig van hoog niveau. Ga eens praten met zo iemand!

[emnich]

Ik kan me haast niet voorstellen dat je met MySQL niet er een goede performance (<1s) uit kan halen door optimalisaties en de instellingen van MySQL aan te passen. Zulke enorme aantallen zijn het ook weer niet.

Begin gewoon eens met je queries te analyseren en te kijken waar de bottleneck precies zit en los dát dan op ipv alles overhoop te gooien met andere technieken.

[Zoijar]

emnich schreef op zaterdag 09 januari 2016 @ 09:31:
Ik kan me haast niet voorstellen dat je met MySQL niet er een goede performance (<1s) uit kan halen door optimalisaties en de instellingen van MySQL aan te passen. Zulke enorme aantallen zijn het ook weer niet.

Begin gewoon eens met je queries te analyseren en te kijken waar de bottleneck precies zit en los dát dan op ipv alles overhoop te gooien met andere technieken.

Kan ik me ook haast niet voorstellen eerlijk gezegd. 500k producten is geen big data. Ik kan me C++ code voorstellen die heel simpelweg een vector van producten heeft en voor elke een hashmap met attributen die zelfs zonder sorteren daar linear doorheen loopt en de goedkoopste opslaat in vrijwel geen tijd. Dus dat moet je ook naar je database kunnen vertalen, en dan moet het ook nog slimmer kunnen met wat preprocessing/sorting. Waarschijnlijk explode er iets omdat er in de huidige oplossing een kwadratisch component zit.

Doet me erg denken aan

Croga schreef op zaterdag 09 januari 2016 @ 08:55:
Onze conclusie was: Dit is onmogelijk in een on-disc database systeem op te lossen. De performance gaat het gewoon, simpelweg, niet trekken (we zitten op grofweg 500'000 hits per dag, wellicht dat dat bij jullie lager ligt).

Kijk, dat scheelt, maar volgens mij heeft TS het gewoon over 1 hit die al traag is, niet honderden tegelijk.

[ Voor 16% gewijzigd door Zoijar op 09-01-2016 11:17 ]

[emnich]

^^ dit inderdaad, er wordt veel te snel naar andere oplossingen of meer hardware gekeken terwijl er gewoon niet goed gebruik gemaakt wordt van wat je hebt.

[Otherside1982]

Heb je het execution plan van je trage query al bekeken? Je kan wel indexes toevoegen maar als die niet gebruikt worden ben je er nog niets mee.
Je spreekt van 15 seconden, het zou toch mogelijk moeten zijn om dat 1 orde-grootte te verminderen naar 1,5 seconde of nog beter terwijl je gewoon je MySQL database blijft gebruiken. Ik vind dat er nogal snel naar compleet andere oplossing wordt gekeken hier.

[SPee]

Hij heeft het over een pagina laden, niet over een enkele query.
Wat zijn de queries die gedaan worden om die enkele pagina te laden? Waar zit die vertraging? Wat kost veel tijd?
Is het in aantal queries die nodig zijn? In bepaalde filtering die pas laat plaats vindt (bv nadat er al een grotere dataset is geladen)?

Wordt er namelijk van het zoekresultaat per item een query gedaan naar de attributen, dan zou je daar naar moeten kijken. Bijvoorbeeld door in bulk op te halen, caching gebruiken, op een andere manier opslaan, views, stored procedures.
Worden eerst alle producten geladen, dan (in code) gefilterd, prijzen bepaald, weer gefilterd en dan gesorteerd?
Doet Magento nog wat rare dingen?

Van wat ik allemaal lees over Magento, is het een vrij systeembelastend systeem. Dat helpt al niet.
Verder heeft PHP (vziw) niet out-of-the-box caching mechanismes. Dus moet alles per request opgehaald worden; ook vertragend.

[pedorus]

MSalters schreef op vrijdag 08 januari 2016 @ 22:16:
Full-text search engines aanraden voor gestructureerde data? Dat is niet de meest effectieve methode, en dat kun je gerust een understatement noemen.

Oneens, zoals anderen. Ik zou het ook meer token search engines willen noemen. Funda is een voorbeeldje dat wellicht dichtbij ligt. Je zou zeggen, dat kan makkelijk in mysql, maar solr is duidelijk efficiënter gebleken.

Het probleem hier enkel is de kortingsregels die wellicht lastig zijn te implementeren. Solr doet niet echt aan joins ofzo (het model is anders, daar komt nu oa de performancewinst vandaan). Wellicht is het mogelijk om ze van te voren op te zoeken en in de query te krijgen als boosts, maar daarvoor ontbreekt wat data.

kanduvisla schreef op vrijdag 08 januari 2016 @ 14:19:
• De klanten van onze klant (organisaties) hebben ook een unieke eigenschap: zij krijgen speciaal toegespitste korting op bepaalde producten, maar alleen weer bij bepaalde leveranciers. Zo kan het dus zijn dat voor product X organisatie A goedkoper uit is bij leverancier M, en organisatie B voor hetzelfde product goedkoper uit is bij leverancier N. Hier moet dus ook rekening mee gehouden worden bij het sorteren op prijs.

De vraag is hoe deze data er preciies uit ziet. Gegeven een enkele klant, is dit een overzichtelijke set? Zo ja, dan zou deze informatie in een solr query kunnen staan.

Het wonderbaarlijke is dat we dit momenteel al werkend hebben, alleen we lopen tegen een probleem aan: het is tergend traag. Een simpel overzicht laden kan soms al 15 seconden duren. De meest voor de hand liggende optimalisaties zijn al gedaan: denk aan indexeren van kortingsprijzen, indexen op tabellen, etc

Welke querie(s) worden in die 15 seconden gedaan, wat is daar een explain op, wat zijn statistieken van de gebruikte tabellen, zijn er concurrent writes, welke databasesettings, wat is de belasting van de database-server op dat moment (geheugen, concurrent lookups, disk, cpu, etc), welke database-server?

De hosting is bij Amazon. 8 cores, 15 GB ram.

Ben al een tijd niet zo'n kleine databaseserver tegengekomen, qua geheugen. Alleen solr met 8G op een website. Werkte op zich prima.

•
Voor het filteren en sorteren haken we in op Magento en maken een join met de geindexeerde prijs-tabel om te kunnen sorteren op de voorberekende prijs (omdat iedere organisatie een andere prijs voor een product kan hebben), en om te filteren maken we een join met de desbetreffende tabellen in de product-attributen database.

De exacte query zou meer zeggen, maar dit klinkt een beetje als een database-in-database anti-pattern.

[Philip J. Dijkstra]

Hoe vaak verandert de data? Ik zit in de Business Intelligence wereld en een van de oplossingen voor performance is simpelweg het eindresultaat zoveel mogelijk voor genereren en opslaan in een nieuwe tabel. In jullie geval dus per klant of klantgroep (eigenlijk kortinggroepen, een klant valt dan in een kortinggroep).
Zet op die eindtabel de juiste indexen (dus per veelgebruikte filtercombinatie).

Heb je altijd alle attributen nodig? Waarschijnlijk niet. Door de gebruikte attributen op te nemen in de index hoeft er überhaupt niet naar de tabel te hoeven gegaan. Indexen moet je (in jullie geval) gewoon behandelen als gesorteerde subsets van je tabel.

Klant -> Klantgroep -> Index -> tabel

In het optimale geval spring je van de index op de klantgroep tabel naar de index op de product-voorberekend tabel en zullen de meeste searches dus plaats vinden op 2 indexen die vervolgens binnen no-time gecached zijn.

[Gomez12]

Croga schreef op zaterdag 09 januari 2016 @ 08:55:
Onze conclusie was: Dit is onmogelijk in een on-disc database systeem op te lossen. De performance gaat het gewoon, simpelweg, niet trekken (we zitten op grofweg 500'000 hits per dag, wellicht dat dat bij jullie lager ligt).

De enige manier waarop je dit gaat trekken is met een in-memory database systeem zoals Elastic.

In wezen denk ik wel dat je enigszins gelijk hebt en toch ook compleet weer niet...

Ja, ik vermoed dat er simpelweg meer geheugen bijmoet, je wilt met een dbms imho altijd in-memory werken voor zover mogelijk.

Maar in-memory kan ook gewoon met een mysql / ms sql etc gebeuren. Er is geen enkele reden om daarvoor elastic in te zetten. Elastic heeft gewoon een heel andere doelgroep.

[MSalters]

Alles in-memory? Nogmaals, gebruik een index. Als die maar in memory past, dan is de rest een O(1) probleem wat je kunt negeren.

[Verwijderd]

Is het een idee om alle kortingen voor een organisatie/klant op te halen en de kortingen op applicatie niveau te berekenen?

Dus een catalogus pagina krijgt iets van de volgende flow:
- Alle kortingen van de organisatie ophalen
- De gefilterde producten ophalen
- Kortingen toepassen
- Relevante leveranciers berekenen
- Je zou nu de catalogus op kunnen maken

Voor zover ik het begrijp zou je dan van de vele verschillende resultsets af moeten zijn.

[Guillome]

Ik heb met een productbestand van 60.000 producten, heel veel verschillende filters en standaard shared hosting en php en mysql voor elkaar dat elke request onder de 200 ms zit.
Dat is prima mogelijk.

Je noemt magento, daar zit sowieso een heel zware belasting.

Wat ik voornamelijk doe is redundancekolommen- en tabellen maken. En die bereken ik bijv. 1 keer per nacht, na een actie in de beheeromgeving of bijv. als een beheerder klaar is met indelen en op de knop [verwerken] klikt.

Hierdoor is alles bijzonder veel sneller aan de voorkant.

Verder goede indexes en hele slimme queries schrijven. Kleine verschillen maken soms enorme prestatieverschillen uit.