[MySQL] Unique zonder (volledige) index?

[Olaf van der Spek]

In MySQL (5) heb ik de volgende tabel:

code:

CREATE TABLE `xwi_serials_valid` (
  `serial` binary(16) NOT NULL,
  KEY `serial` (`serial`(4))
);

Is het nu mogelijk de key te veranderen in primary/unique zonder het hele veld te gebruiken in de index?
In dit geval is het veld nog redelijk kort, maar het kan natuurlijk ook veel langer zijn.

[Creepy]

Het zal wel aan mij liggen maar ik snap niet wat je nu precies wilt bereiken.
Een veld UNIQUE maken zonder index moet kunnen lijkt me (daar is het UNIQUE keyword nu eenmaal voor ). Op een primary key zit altijd een index.

[JeRa]

Ik neem aan dat de indices die MySQL gebruikt gebaseerd zijn op B-trees die proberen het kleinst mogelijke minimale bereik te vinden voor de items voor de index. Ik denk dus dat je niet bang hoeft te zijn dat je index gruwelijk groot wordt als het veld dat je indexeert ook gruwelijk groot is.

Een primary key moet uniek zijn, dus zo'n index gaat altijd over het hele veld. Limiteren tot een bepaald aantal karakters zou ervoor zorgen dat MySQL bij elke INSERT na een keyscan ook een table scan moet doen om te achterhalen of een nieuwe primary key daadwerkelijk uniek is.

[ Voor 33% gewijzigd door JeRa op 28-03-2006 20:30 ]

[Olaf van der Spek]

Creepy schreef op dinsdag 28 maart 2006 @ 20:25:
Het zal wel aan mij liggen maar ik snap niet wat je nu precies wilt bereiken.
Een veld UNIQUE maken zonder index moet kunnen lijkt me (daar is het UNIQUE keyword nu eenmaal voor ). Op een primary key zit altijd een index.

Ik krijg dat (unique zonder index) niet voor elkaar in MySQL.

[B-Man]

UNIQUE is toch per definitie ook een index in MySQL? Anders is er bij iedere INSERT een table scan nodig om te controleren of een bepaalde nieuwe waarden uniek is.

Volgens mij kun je gewoon werken met een lengte-beperkte UNIQUE index, omdat MySQL bij een INSERT en UPDATE gewoon die index zal nalopen om te zien of de betreffende waarde er al in voorkomt.

[JeRa]

OlafvdSpek schreef op dinsdag 28 maart 2006 @ 20:30:
[...]

Ik krijg dat (unique zonder index) niet voor elkaar in MySQL.

Een UNIQUE veld zonder index zou dan ook oertraag zijn. Maar het is niet alsof de grootte van een veld uitmaakt voor de grootte van een index.

[Olaf van der Spek]

JeRa schreef op dinsdag 28 maart 2006 @ 20:33:
Maar het is niet alsof de grootte van een veld uitmaakt voor de grootte van een index.

Ah, dat wist ik niet.

[JeRa]

OlafvdSpek schreef op dinsdag 28 maart 2006 @ 20:44:
[...]

Ah, dat wist ik niet.

Een index probeert zo klein mogelijk te blijven. Stel je een binaire index voor. Als je twee records wilt indexeren en je vergelijkt alleen de eerste bit, dan zou het zo kunnen zijn dat het ene record '1' heeft en het andere record '0'. Dan hoef je alleen die vertakking op te slaan in je index. Als er nu een record bij komt, dan vergelijk je weer de eerste bit. Stel dat deze '1' is, dan zul je die vertakking moeten uitbreiden zodat je de twee mogelijkheden '10' en '11' krijgt (of zodra er zich een verschil voordoet in de bits).

Voor zover ik weet maakt MySQL gebruik van B-trees (MyISAM tenminste) die ervoor zorgen dat je een gebalanceerde index hebt die vrijwel altijd van minimale grootte is.

[Olaf van der Spek]

JeRa schreef op dinsdag 28 maart 2006 @ 20:49:
Een index probeert zo klein mogelijk te blijven.

Dat is leuk, maar het creeeren van de index lijkt wel veel en veel langer te duren. Hij is al bijna vijf dagen bezig.

[JKVA]

En om hoeveel records praten we dan? 5 dagen is namelijk wel erg veel. Dat heb ik bij lange nog nooit gehaald. Een paar uur vin ik al veel.

[Olaf van der Spek]

JKVA schreef op dinsdag 04 april 2006 @ 21:32:
En om hoeveel records praten we dan? 5 dagen is namelijk wel erg veel. Dat heb ik bij lange nog nooit gehaald. Een paar uur vin ik al veel.

56 miljoen, binary(16).
De index met lengte 4 ging wel snel.

[Varienaja]

Creepy schreef op dinsdag 28 maart 2006 @ 20:25:
Op een primary key zit altijd een index.

JeRa schreef op dinsdag 28 maart 2006 @ 20:29:
Ik neem aan dat de indices die MySQL gebruikt gebaseerd zijn op B-trees die proberen het kleinst mogelijke minimale bereik te vinden voor de items voor de index.

Ik heb in Postgres wel meegemaakt dat een primary key een hash was. Sorteren op de PK (of de max oprvagen) was daarmee nog niet erg vlot te noemen. Prikken op PK ging natuurlijk wel heel vlot. Pas nadat ik een echte index maakte op de PK kon ik ook fatsoenlijk sorteren en de max vlot ophalen.

_{Niet gezegd dat mySQL dat precies zo doet natuurlijk!}

[JeRa]

OlafvdSpek schreef op dinsdag 04 april 2006 @ 18:41:
[...]

Dat is leuk, maar het creeeren van de index lijkt wel veel en veel langer te duren. Hij is al bijna vijf dagen bezig.

Als je hashes hebt in hexadecimale vorm dan lijkt me dat logisch ja. Vier tekens levert 65536 combinaties op, 56 miljoen verschillende hashes passen daar natuurlijk niet in en dan wordt de index groter en dus ook trager om te maken (maar voor lookups van hashes dus sneller).

Dat een index kleiner probeert te blijven zegt niets over de tijd dat het duurt om 't te genereren.

[JeRa]

Varienaja schreef op dinsdag 04 april 2006 @ 21:49:
[...]

[...]
Ik heb in Postgres wel meegemaakt dat een primary key een hash was. Sorteren op de PK (of de max oprvagen) was daarmee nog niet erg vlot te noemen. Prikken op PK ging natuurlijk wel heel vlot. Pas nadat ik een echte index maakte op de PK kon ik ook fatsoenlijk sorteren en de max vlot ophalen.

_{Niet gezegd dat mySQL dat precies zo doet natuurlijk!}

Voor zover ik weet maakt MySQL op de PK ook een 'echte' index aan waar je loeisnel mee kunt sorteren

[JKVA]

OlafvdSpek schreef op dinsdag 04 april 2006 @ 21:37:
[...]

56 miljoen, binary(16).
De index met lengte 4 ging wel snel.

Omfg, dan heb je wel erg veel duplicates als ik goed reken. 2^16 = 65000

Het lijkt me dat een create index ofzo binnen de seconde een error zou moeten geven.

offtopic:
Kun je de boel niet truncaten en opnieuw vullen? (Misschien overdreven. )

[Olaf van der Spek]

JeRa schreef op dinsdag 04 april 2006 @ 21:56:
Als je hashes hebt in hexadecimale vorm dan lijkt me dat logisch ja. Vier tekens levert 65536

Ik heb de binaire vorm genomen natuurlijk, dat scheelt 900 mbyte.
Ik heb ook een index genomen, niet een unique key.

[ Voor 14% gewijzigd door Olaf van der Spek op 04-04-2006 22:18 ]

[JeRa]

OlafvdSpek schreef op dinsdag 04 april 2006 @ 22:09:
[...]

Ik heb de binaire vorm genomen natuurlijk, dat scheelt 900 mbyte.
Ik heb ook een index genomen, niet een unique key.

De binaire vorm levert genoeg variatie (~4,2 miljard combinaties voor 4 bytes) om geen probleem voor het indexeren te zijn. Dan weet ik niet waarom hij er zo lang over doet, sorry

[ACM]

OlafvdSpek schreef op dinsdag 28 maart 2006 @ 20:20:
Is het nu mogelijk de key te veranderen in primary/unique zonder het hele veld te gebruiken in de index?
In dit geval is het veld nog redelijk kort, maar het kan natuurlijk ook veel langer zijn.

Nee, MySQL kan niet een unique "constraint" afdwingen zonder een bijbehorende index. En die index is dan (natuurlijk) alleen mogelijk op de volledige lengte, anders zou je alsnog niet kunnen bepalen of waarden uniek zijn.
Als je per se een soort-van unique constraint wilt met een index van beperkte lengte, zal je op mysql 5.1 moeten wachten voor (before insert) triggers en/of het voorlopig in je applicatie-laag moeten regelen.

Varienaja schreef op dinsdag 04 april 2006 @ 21:49:
Ik heb in Postgres wel meegemaakt dat een primary key een hash was. Sorteren op de PK (of de max oprvagen) was daarmee nog niet erg vlot te noemen. Prikken op PK ging natuurlijk wel heel vlot. Pas nadat ik een echte index maakte op de PK kon ik ook fatsoenlijk sorteren en de max vlot ophalen.

De hash-index in Postgres is absoluut niet de standaard en ik meen zelfs reeds afgeschaft als mogelijkheid. Sorteren erop is per definitie onmogelijk, de hash hoeft helemaal niet dezelfde sortering als de originele waarde te hebben. Alleen equi-look-ups gingen er (iets) sneller mee dan de standaard B+-trees die PostgreSQL standaard gebruikt.
PostgreSQL gebruikt dus net als MySQL standaard B+-trees voor indexen en die sorteren prima voor- en achteruit.

_{Niet gezegd dat mySQL dat precies zo doet natuurlijk!}

MySQL kent sowieso maar een indextype, dus die kan het niet eens zo doen.

OlafvdSpek schreef op dinsdag 04 april 2006 @ 18:41:
Dat is leuk, maar het creeeren van de index lijkt wel veel en veel langer te duren. Hij is al bijna vijf dagen bezig.

5 dagen voor 900MB/56M kleine records indexeren? Dat is wel heel erg lang, of is het niet zo'n snelle server?

OlafvdSpek schreef op dinsdag 04 april 2006 @ 21:37:
56 miljoen, binary(16).
De index met lengte 4 ging wel snel.

Wat is "wel snel" ? Het is natuurlijk tamelijk logisch dat je significant meer tree-operaties nodig hebt met je volledige lengte index dan met je verkorte lengte index. Dat kunnen vrij dure operaties zijn, maar om er dan gelijk maar meerdere factoren langer over te doen?
Waar is je doos mee bezig? Vooral i/o? Vooral cpu?
Je doet toch niet ook ondertussen operaties op die tabel he?

JKVA schreef op dinsdag 04 april 2006 @ 21:58:
Omfg, dan heb je wel erg veel duplicates als ik goed reken. 2^16 = 65000

binary is een 8bits-formaat dus 8^16 en daar passen er wel een paar miljoen in.

offtopic:
Kun je de boel niet truncaten en opnieuw vullen? (Misschien overdreven. )

Sja... dat is dan ook precies de manier hoe MySQL uberhaupt alle tabel-wijzigingen doet... dus je voorstel is tamelijk onzinnig

[JeRa]

ACM schreef op dinsdag 04 april 2006 @ 23:15:
Waar is je doos mee bezig? Vooral i/o?

Helemaal overheen gekeken, je hebt gelijk ACM.

Op het moment dat je een gigantische index hebt (met ~56 miljoen hashes heb je toch wel een vrij grote index nodig) dan zal een willekeurige nieuwe insert veel vereisen van de schijf qua schrijfwerk, vanwege de opbouw van de B+-tree. Ik heb meegemaakt dat een systeem volledig platgelegd kan worden door MySQL met de indexfiles op een te trage disk.

[Olaf van der Spek]

ACM schreef op dinsdag 04 april 2006 @ 23:15:
5 dagen voor 900MB/56M kleine records indexeren? Dat is wel heel erg lang, of is het niet zo'n snelle server?

Met een 20 gbyte PATA drive is die redelijk langzaam. De server heeft een 256 mbyte key buffer. Misschien had ik daar beter 600 mbyte van kunnen maken. Hmm, kan MySQL dat niet zonder restart?

mysqld-nt heeft ondertussen ongeveer 20 gbyte gelezen en 20 gbyte geschreven volgens Task Manager.

Wat is "wel snel" ? Het is natuurlijk tamelijk logisch dat je significant meer tree-operaties nodig hebt met je volledige lengte index dan met je verkorte lengte index. Dat kunnen vrij dure operaties zijn, maar om er dan gelijk maar meerdere factoren langer over te doen?
Waar is je doos mee bezig? Vooral i/o? Vooral cpu?
Je doet toch niet ook ondertussen operaties op die tabel he?

Toen duurde het niet meer dan vier uur.
CPU is idle, disk zal wel op 100% zitten.
Nee, maar die tabel is toch gelocked? Dus het zou uberhaupt niet kunnen. Verder is de hele server ook idle.

binary is een 8bits-formaat dus 8^16 en daar passen er wel een paar miljoen in.

Eh, 2^32, 16^8 of 256^4, maar geen 8^16 volgens mij.

[ Voor 7% gewijzigd door Olaf van der Spek op 04-04-2006 23:33 ]

[ACM]

OlafvdSpek schreef op dinsdag 04 april 2006 @ 23:29:
Met een 20 gbyte PATA drive is die redelijk langzaam. De server heeft een 256 mbyte key buffer. Misschien had ik daar beter 600 mbyte van kunnen maken. Hmm, kan MySQL dat niet zonder restart?

Nee? Er zijn maar weinig applicaties die dat soort dingen zonder (een vorm van) restart kunnen. MySQL is er iig geen van.

Toen duurde het niet meer dan vier uur.
CPU is idle, disk zal wel op 100% zitten.

Dat zou ik toch even checken. Als ook de disk min of meer idle is, dan zal je wel met locking perikelen zitten. MySQL is in mijn ervaring niet bijster goed in het afwerken van meerdere processen op een tabel die in een altering procedure zit.

Nee, maar die tabel is toch gelocked? Dus het zou uberhaupt niet kunnen. Verder is de hele server ook idle.

Ik heb genoeg rare dingen met mysql meegemaakt om het allemaal zwaar te zien vertragen zonder dat er nou echt een logische reden voor is. Het kan zomaar zijn dat je bijv phpmyadmin of een vergelijkbare admin tool opende die er voor het gemak even een count(*) op uitvoerde voor de interface. En echt geweldig werkt het allemaal niet altijd samen dan.

Als het goed is maakt mysql ergens een temporary file (in de table-dir meen ik), kijk eerst eens hoe groot die ondertussen is?

Mocht je systeem eigenlijk ook niet met 100% disk zitten, dan zou je het proces afschieten, zeker maken dat er niks aan je mysql kan komen en het nog eens proberen als je per se die unique-index nodig hebt.

Eh, 2^32, 16^8 of 256^4, maar geen 8^16 volgens mij.

Je hebt 8 bits per positie en 16 elementen ervan? 8^16 is dan inderdaad fout, was iets te snel getikt Dat zijn dan natuurlijk 8*16 = 128 bits, levert je 2^128 mogelijkheden op.

[Olaf van der Spek]

ACM schreef op woensdag 05 april 2006 @ 07:37:
Dat zou ik toch even checken. Als ook de disk min of meer idle is, dan zal je wel met locking perikelen zitten. MySQL is in mijn ervaring niet bijster goed in het afwerken van meerdere processen op een tabel die in een altering procedure zit.

De disk zit ook op 100% 'usage'. Een show processlist laat zien dat er geen andere processen zijn.

Als het goed is maakt mysql ergens een temporary file (in de table-dir meen ik), kijk eerst eens hoe groot die ondertussen is?

Je hebt 8 bits per positie en 16 elementen ervan? 8^16 is dan inderdaad fout, was iets te snel getikt Dat zijn dan natuurlijk 8*16 = 128 bits, levert je 2^128 mogelijkheden op.

Klopt, ik dacht dat je het over de 4 posities had van de index die ik eerst had.

De tijdelijke tabel is 600 mb data en 1 gb index.
De normale tabel is 933 mb data.

Dit is trouwens wel MySQL 5.1.7 beta, dus een bug is ook niet uit te sluiten.

[ACM]

Je zou het dus anders op kunnen lossen dan, met 5.1 kan je before-insert-triggers (toch?) maken die met je partiele index alsnog een unique kunnen garanderen. Efficienter zal het niet zijn voor de duplicate-look-up, maar het bespaart je wel weer bij de index-insert-performance vanwege het verlaagde aantal tree-operaties. Daarnaast zal je index wat kleiner zijn.

Anderzijds is als die unique index eenmaal klaar is je gewone select er op ook iets sneller. Maar als ie 5 dagen over 600/933e van je data doet kan je uitrekenen hoe lang ie er nog over gaat doen toch nog ruim anderhalve dag als het tegen zit
Puur hardwarematig kan je hier waarschijnlijk al behoorlijk wat aan verbeteren door ervoor te zorgen dat je i/o sneller (je disk is wel heel sloom tov nieuwe varianten) wordt en dat je meer geheugen ter beschikking hebt voor zowel MySQL als disk cache.

[JeRa]

ACM schreef op woensdag 05 april 2006 @ 07:37:
[...]

Nee? Er zijn maar weinig applicaties die dat soort dingen zonder (een vorm van) restart kunnen. MySQL is er iig geen van.

offtopic:
Een buffer resizen terwijl een programma draait? Ik ken genoeg programma's die dat kunnen - het is immers niets anders dan het opnieuw instellen van een buffersize en (indien de bestaande buffer verkleind moet worden) een OOM-policy toepassen op de data die er dan nog in staat.

[Olaf van der Spek]

ACM schreef op woensdag 05 april 2006 @ 10:06:
Je zou het dus anders op kunnen lossen dan

Dit is slechts een test server en de 'production' servers draaien geen 5.1.
De production servers zijn bij toeval wel gelijk uitgerust en ik had blijkbaar 'geluk' dat ik een korte index koos.

600/933

Als de voortgang inderdaad lineair is qua tijd, want waarschijnlijk niet het geval is.

[ Voor 17% gewijzigd door Olaf van der Spek op 05-04-2006 19:07 ]

[Olaf van der Spek]

Vandaag is de herindexering eindelijk afgerond.
De index (PRIMARY KEY (`serial`)) is nu echter 1.69 gb.
Dit is significant meer dan de korte index (KEY `serial` (`serial`(4))) van 0.560 gb.

Ergens klopt de uitleg van JeRa dus niet.

[JeRa]

OlafvdSpek schreef op dinsdag 11 april 2006 @ 13:58:
Ergens klopt de uitleg van JeRa dus niet.

Ik zei dat de lengte van een veld niet uitmaakt voor de grootte van een index. Iets genuanceerder, als je je velden korter gaat maken en dus duplicate entries krijgt ('olafvdspek' en 'olafjansen' geven allebei 'olaf' als eerste vier tekens) dan is je index stukken kleiner ja. Echter moet je DBMS dan meer zoekopdrachten uitvoeren om de goede rows terug te vinden aan de hand van die index

[Olaf van der Spek]

JeRa schreef op dinsdag 11 april 2006 @ 14:10:
Ik zei dat de lengte van een veld niet uitmaakt voor de grootte van een index. Iets genuanceerder, als je je velden korter gaat maken en dus duplicate entries krijgt ('olafvdspek' en 'olafjansen' geven allebei 'olaf' als eerste vier tekens) dan is je index stukken kleiner ja. Echter moet je DBMS dan meer zoekopdrachten uitvoeren om de goede rows terug te vinden aan de hand van die index

Ik heb de veldlengte toch ook niet aangepast? Ik heb alleen de indexlengte aangepast. In beide gevallen is de veldlengte gewoon 16.

[ Voor 8% gewijzigd door Olaf van der Spek op 11-04-2006 14:25 ]

[JeRa]

OlafvdSpek schreef op dinsdag 11 april 2006 @ 14:24:
[...]

Ik heb de veldlengte toch ook niet aangepast? Ik heb alleen de indexlengte aangepast. In beide gevallen is de veldlengte gewoon 16.

Wat klopt er dan niet aan mijn uitleg? Ik zei dat de grootte van je veld niet uitmaakt voor de grootte van je index de indexlengte vanzelfsprekend wél.

[ Voor 5% gewijzigd door JeRa op 11-04-2006 14:27 ]

[Olaf van der Spek]

JeRa schreef op dinsdag 11 april 2006 @ 14:26:
Wat klopt er dan niet aan mijn uitleg? Ik zei dat de grootte van je veld niet uitmaakt voor de grootte van je index de indexlengte vanzelfsprekend wél.

Jij had het over het korter maken van mijn velden, maar dat heb ik dus niet gedaan.
Ook zijn het md5 hashes, dus het aantal duplicates (ook als je alleen naar de eerste 32 bits kijkt) zou te verwaarlozen moeten zijn.
En je zei ook:

Ik denk dus dat je niet bang hoeft te zijn dat je index gruwelijk groot wordt als het veld dat je indexeert ook gruwelijk groot is.

Een index probeert zo klein mogelijk te blijven. Stel je een binaire index voor. Als je twee records wilt indexeren en je vergelijkt alleen de eerste bit, dan zou het zo kunnen zijn dat het ene record '1' heeft en het andere record '0'. Dan hoef je alleen die vertakking op te slaan in je index.

Blijkbaar moest ik dus wel bang zijn.

[ Voor 16% gewijzigd door Olaf van der Spek op 11-04-2006 14:42 ]

[JeRa]

OlafvdSpek schreef op dinsdag 11 april 2006 @ 14:39:
Blijkbaar moest ik dus wel bang zijn.

Als je een index legt op 4 bytes dan zal die index kleiner zijn dan een index op álle bytes. Maar die grotere index is nog altijd zo klein mogelijk en kun je gebruiken om in één keer de juiste rows te vinden, terwijl dat met de kleinere index niet van toepassing is (al handelt MySQL dat met meer reads intern alsnog af)

Maar wat is nu het probleem? Dat de totale indextijd zo lang duurde vanwege disk I/O of dat de index nu 3x zo groot is geworden omdat je de input niet hebt afgekapt?

Ook zijn het md5 hashes, dus het aantal duplicates (ook als je alleen naar de eerste 32 bits kijkt) zou te verwaarlozen moeten zijn.

En dit is dus weer wél vreemd maar dat heeft waarschijnlijk te maken met de birthday paradox.

[ Voor 17% gewijzigd door JeRa op 11-04-2006 14:48 ]

[Olaf van der Spek]

JeRa schreef op dinsdag 11 april 2006 @ 14:47:
Als je een index legt op 4 bytes dan zal die index kleiner zijn dan een index op álle bytes.

Maar alleen als die eerste 4 bytes niet uniek zijn toch?
En datzelfde geldt voor grotere velden natuurlijk, dus de veldgrootte heeft wel invloed op de index.

Maar die grotere index is nog altijd zo klein mogelijk en kun je gebruiken om in één keer de juiste rows te vinden, terwijl dat met de kleinere index niet van toepassing is (al handelt MySQL dat met meer reads intern alsnog af)

Maar wat is nu het probleem? Dat de totale indextijd zo lang duurde vanwege disk I/O of dat de index nu 3x zo groot is geworden omdat je de input niet hebt afgekapt?

Beide.
De veel grotere index is waarschijnlijk ook nadelig voor de index/key cache.

En dit is dus weer wél vreemd maar dat heeft waarschijnlijk te maken met de birthday paradox.

Dat betwijfel ik.

[ Voor 5% gewijzigd door Olaf van der Spek op 11-04-2006 15:08 ]

[JeRa]

OlafvdSpek schreef op dinsdag 11 april 2006 @ 15:07:
[...]

Maar alleen als die eerste 4 bytes niet uniek zijn toch?

Klopt

En datzelfde geldt voor grotere velden natuurlijk, dus de veldgrootte heeft wel invloed op de index.

Een index zal alleen de relevante bits vergelijken en opslaan, op het moment dat jouw data niet meer interessant is (omdat bijvoorbeeld bij een hash vanaf 6 bytes toch al blijkt dat de hash uniek is) zal hij stoppen met vergelijken. Dat maakt het dat de index altijd zo klein mogelijk is. Op de birthday paradox kom ik zo terug.

[JeRa]

Over de birthday paradox. Ik heb een testje gedraaid op een zelfontworpen index-systeem. Deze doet in principe hetzelfde als wat ik in dit topic heb beschreven.

Ik genereer unieke, random data (vele random bytes) en maak daar een md5 van. De eerste 4 bytes (32 bits) van deze md5 sla ik telkens op in de index, en wacht todat ik een duplicate krijg. Dan krijg ik deze melding na luttele minuten:

code:

Duplicate found after adding 117506 hashes (32-bit).

Na 120.000 random data-MD5-hashes toe te hebben gevoegd vindt hij al een duplicate. Kennelijk is het dus wel van toepassing

[Olaf van der Spek]

JeRa schreef op dinsdag 11 april 2006 @ 16:01:
Na 120.000 random data-MD5-hashes toe te hebben gevoegd vindt hij al een duplicate. Kennelijk is het dus wel van toepassing

Uiteraard is het van toepassing, maar volgens mij is het aantal duplicaties wel zo klein dat het niet significant zou moeten zijn.

Ik ben nu duplicates aan het tellen, maar dat zal ook wel even duren:
select substring(serial, 1, 4) s, count(*) c from xwi_serials_valid group by s having c > 1;

[ Voor 19% gewijzigd door Olaf van der Spek op 11-04-2006 16:54 ]

[ACM]

OlafvdSpek schreef op dinsdag 11 april 2006 @ 13:58:
Vandaag is de herindexering eindelijk afgerond.
De index (PRIMARY KEY (`serial`)) is nu echter 1.69 gb.
Dit is significant meer dan de korte index (KEY `serial` (`serial`(4))) van 0.560 gb.

Vergeet niet dat zowel met meer data als met langere index-keys je een diepere boom zult krijgen, met als gevolg dat er sowieso buiten de data zelf meer "index" is.

Ergens klopt de uitleg van JeRa dus niet.

Ik weet ook niet zo zeker of zijn uitleg wel helemaal klopt. Er hoeft inderdaad maar een deel van de data op elk niveau van de binaire boom gebruikt te worden, bij de eerste vertakking is alleen de eerste bit ofzo interessant. Maar om uiteindelijk bij de gezochte elementen uit te komen heb je toch wel aardig wat lagen nodig en daardoor een behoorlijk groot deel van je waarden zelf op de eennallaagste laag. Buiten de overhead van de boomstructuur zelf.
Sterker nog, vziw wordt zelfs gehele waarde in de index opgeslagen is omdat je op zich anders alleen maar weet dat er een mogelijk pad in je boom naartoe is, niet of het gezochte element uberhaupt wel bestaat. Of daar dan weer slimme vormen van compressie op losgelaten worden weet ik niet, je hebt via dat pad van je boom de eerste tig bits natuurlijk al dus hoef je die niet meer in het "leaf element" op te slaan.
Daarbij moet er ook nog eens een of meerdere verwijzingen naar records van je tabel geplaatst worden om te daarop te kunnen werken. En die referenties kosten ook ruimte natuurlijk.

Zeker voor tabellen met relatief weinig en/of kleine velden gebeurd het zomaar dat je meer diskspace aan een enkele index kwijt bent, dan aan de tabel zelf.

[JeRa]

OlafvdSpek schreef op dinsdag 11 april 2006 @ 16:46:
[...]

Uiteraard is het van toepassing, maar volgens mij is het aantal duplicaties wel zo klein dat het niet significant zou moeten zijn.

Ik krijg daarna om de ~7000 toevoegingen een nieuwe duplicate, dus in die 50 miljoen zullen er toch wel aardig wat zitten (zeker als je weet dat er steeds sneller meer duplicates zijn )

[JeRa]

ACM schreef op dinsdag 11 april 2006 @ 17:12:
Sterker nog, vziw wordt zelfs gehele waarde in de index opgeslagen is omdat je op zich anders alleen maar weet dat er een mogelijk pad in je boom naartoe is, niet of het gezochte element uberhaupt wel bestaat. Of daar dan weer slimme vormen van compressie op losgelaten worden weet ik niet, je hebt via dat pad van je boom de eerste tig bits natuurlijk al dus hoef je die niet meer in het "leaf element" op te slaan.

Hier noem je wel iets interessants - ik ben er van uit gegaan dat de hashes opnieuw worden gegenereerd bij een split (als er dus een duplicate wordt gevonden voor zover er bits in de index aanwezig zijn). Als dat niet zo is zou de index gigántisch veel ruimte innemen, dus ik neem aan dat ze er iets slims mee hebben gedaan

[ACM]

JeRa schreef op dinsdag 11 april 2006 @ 17:18:
Hier noem je wel iets interessants - ik ben er van uit gegaan dat de hashes opnieuw worden gegenereerd bij een split (als er dus een duplicate wordt gevonden voor zover er bits in de index aanwezig zijn). Als dat niet zo is zou de index gigántisch veel ruimte innemen, dus ik neem aan dat ze er iets slims mee hebben gedaan

Bij een standaard boom wordt er dan een splitsing ingebouwd en volgt er eventueel een herbalancering. Dat zal sowieso vrij pittig zijn om te doen als je 50M records in een index wilt mikken.
Hoe dat bij MySQL's binary tree gebeurd weet ik niet en bovendien is mijn kennis daarover toch wat ingezakt sinds ik niet meer studeer

[Olaf van der Spek]

365705 rows in set (7 hours 42 min 31.74 sec)

Dus 366k duplicates op 56m rows. Dat is toch niet significant?