Thomas Kejser, den ich hier inzwischen recht regelmäßig verlinke, hat eine kompakte (RDBMS-unabhängige) Erklärung der Arbeitsweise von column stores veröffentlicht. Deren entscheidender Trick ist es offenbar, die Anzahl der aufeinanderfolgenden Wiederholungen pro Schlüssel zu erfassen, und dadurch eine massive Komprimierung zu erreichen (was mich an die compression in bitmap indizes erinnert):
Because the typical case for large tables is that they DO have a lot of repetitions, column stores can often achieve significant compression benefits. The quoted compression rates from different vendors (as compared with the raw format) is typically in the range of 5-50x – depending on what data you store of course.
Das Entpacken einer solchen Struktur ist dabei dann relativ einfach:
because of the way data is stored (with duplicates added in the right places), this “join” can proceed in a linear, O ( n ), highly parallelised manner, no matter which column we select. This data structure also has the property of making it easy to sequentially access memory.
Weitere Zitate spare ich mir, weil ich den Artikel dann gleich komplett kopieren könnte.
Keine Kommentare:
Kommentar veröffentlichen