Similarly, storing tables using an inverted organization
is well known. Here, every attribute is stored using some
sort of indexing, and record identifiers are used to find
corresponding attributes in other columns. C-Store uses
this sort of organization in WS but extends the architecture
with RS and a tuple mover.
There has been substantial work on using compressed
data in databases; Roth and Van Horn [ROTH93] provide
an excellent summary of many of the techniques that have
been developed. Our coding schemes are similar to some
of these techniques, all of which are derived from a long
history of work on the topic in the broader field of
computer science [WITT87]. Our observation that it is
possible to operate directly on compressed data has been
made before [GRAE91, WESM00].
Lastly, materialized views, snapshot isolation,
transaction management, and high availability have also
been extensively studied. The contribution of C-Store is
an innovative combination of these techniques that
simultaneously provides improved performance, K-safety,
efficient retrieval, and high performance transactions.