Nejkratší forma úschovy čísla v binární podobě

[gleng]

Potrebujem uschovat cislo v najkratsej moznej podobe v db(mysql). Cislo bude uint64 generovane auto-increment klucom v db.
Bezne enkodovanie pre uint64 si vezme 8 bajtov. Ak by som ho uchoval ako string, tak cislo 12345 by malo 5 bajtov a teda by to bolo o 3 bajty uspornejsie. Avsak akonahle by cislo islo nad 12345678 tak uz tam nie je rozdiel a neskor v case bude string dlhsi. Preto som rozmyslal nad niecim ako je napriklad bijektivna funkcia. Ake najvhodnejsie riesenie vas napada?

Este ma teoreticky napada pouzivat pocet bajtov podla velkosti cisla. Cize 0-255 by malo jeden bajt, 256-65535 dva bajty. 65536-4294967295 styri bajty a 4294967296-18446744073709551615 osem bajtov. Toto by mohlo fungovat pretoze dopredu viem ake cislo chcem z db vytiahnut takze v aplikacii si vygenerujem jeho "binarnu" podobu a s tym spravim potom query na db.

Pre kontext - pridavam do systemu komentare ktore budu mat clenenie a teda najst vsetkych potomkov by vyzadovalo prejdenie kazdeho komentaru zvlast, co je samozrejme blbost. Existuje mnoho rieseni tohto znameho vykonnostneho problemu a ja som si zvolil riesenie zapisu cesty rodicov (rodic1/rodic2/rodic2/..=id) a prefix scan(select * from comments where path like "id1/d2/%" co je velmi rychle a optimalne riesenie. Avsak tym ze sa komentare clenia tak dlzka takehoto indexu moze byt dost dlha a prave tomu chcem zabranit aby sa zbytocne nemuseli nacitat dlhe hodnoty a preto ich chcem skratit co najviac.

[Reklama]

[_Jenda]

Jmenuje se to variable length encoding. Nejjednodušší řešení je třeba použít nejvyšší bit každého bajtu jako "kódování pokračuje", případně u tvých hodnot by se daly použít nejvyšší 2 bity prvního bajtu jako "kolik bajtů čísla ještě bude", případně offsetnuté o jedničku (00 → 2 bajty a tedy 14 použitelných bitů, 11 → 5 bajtů a tedy 38 bitů, přes 2**38 komentářů asi nebude). Je to úspornější než tvoje řešení se separátory, které navíc nebude fungovat pokud se separátor objeví uvnitř reprezentace čísla.

[gleng]

na koniec pouzijem uint32. 4 bajty a 4 miliardy cisiel, to nevyuzijem ani do konca zivota. ale ak by chcel niekto napisat jeho navrh na "kompresiu" tak sa podelte. moze sa niekomu zijst do buducna.

[sofa_king]

Záleží v jakým systému to budeš používat. Pokud v obyč row store databázi (mysql, postgres, apod.) tak pravděpodobně nebudeš tenhle systém používat v situaci, kde je problém storage nebo performance a tím pádem bys předčasně optimalizoval.

Pokud ti jde o výkon nebo děláš nad big daty, pravděpodobně bys sáhnul po nějakém column store systému (např. clickhouse) a tyhle otázky už za tebe budou dávno vyřešeny zabudovanými kodeky.

Kompresí jednoho čísla toho moc nezmůžeš, ale kompresí bloku třeba 1000 integerů už můžeš ušetřit mnoho. Proto nemá smysl optimalizovat row store systém, ale column store už to dávno má.

Kupř. 11 starý článek od elasticsearch pro ilustraci, čeho lze dosáhnout
https://blog.mikemccandless.com/2010/08/lucene-performance-with-pfordelta-codec.html?m=1

[anonacct]

Já bych se opravdu zeptal tazatele, jak si představuješ, že bude v DB uložený string? Ty vidíš asi jen obsah, ale string bude mít nějakou velikost a nějaké data, které buď budou přímo v řádku, pokud jsou malé, nebo tam bude reference odkazující někam jinam. Teda pokud si tam nerezervuješ nějaký fixní string, v tom případě by ale stejně musel byt dost velký, abys ten celý integer v textu do něj uložil... 64-bit int je oproti tomu fakt nic - v bitové podobě je to ta nejoptimálnější reprezentace čísla.

Asi bych doporučil si něco přečíst o databázích, a potom použít třeba DB jako postgres, která umí transparentně kompresovat celé bloky.

[Reklama]

[Filip Jirsák]

Já bych se opravdu zeptal tazatele, jak si představuješ, že bude v DB uložený string? Ty vidíš asi jen obsah, ale string bude mít nějakou velikost a nějaké data, které buď budou přímo v řádku, pokud jsou malé, nebo tam bude reference odkazující někam jinam. Teda pokud si tam nerezervuješ nějaký fixní string, v tom případě by ale stejně musel byt dost velký, abys ten celý integer v textu do něj uložil... 64-bit int je oproti tomu fakt nic - v bitové podobě je to ta nejoptimálnější reprezentace čísla.

Asi bych doporučil si něco přečíst o databázích, a potom použít třeba DB jako postgres, která umí transparentně kompresovat celé bloky.

Ono to z dotazu není hned zřejmé, ale gleng podle mne nechce ukládat do jednoho záznamu jedno číslo, ale posloupnost čísel.

Pokud jde o komentáře, očekával bych, že budou častěji provázané komentáře s podobným ID (častěji se budou komentovat nedávné komentáře než komentáře daleko v minulosti), možná by bylo nejefektivnější neukládat absolutní hodnoty ID, ale ukládat jen rozdíly.

[anonacct]

Mi to přijde jako kdyby řešil storage jednoho čísla.

Nevím jestli má cenu řešit jestli Int32 nebo Int64 (nebo nějaká další šílená reprezentace) - já bych volil Int64, protože tam stejně bude mít nějaký overhead na řádek a indexy - 4 byty navíc oproti tomu je nic.

Toto bych já označil za předčasnou optimalizaci.