As time goes by, CPU power becomes cheaper and more plentiful, to the point where it makes sense to start spending some of it using more complex storage formats that save disk space and bandwidth, and indeed modern databases can do this.
Oh, the situation was rather the other way around. There was never enough disk space. If one got to store several tables of each holding >100,000 records on disks of only 72 MiB, storage is a bigger problem than any CPU ever can become. So various kinds of compression were used early on.
The methods go along a continuous vector from optimized data types and data storage all the way to deduplication (*1)
- The most basic way of compression is simply storing data more compactly - like using an integer or a BCD instead of character based data.
- In addition, data was stored wherever there was some space - think of using the high bit of the first character of a name holding a male/female flag (*2)
- Use of variable-length records allowed databases to simply not store what doesn't need to be stored.
- This became especially useful with variable-length fields. Here storage on disk was done much like one knows from later mini/micro computers. When writing a record, each field was only transferred until the last used character, followed by a delimiter (*3). When reading, the fields were again filled into a virtual fixed size record.
All of this not only saved valuable disk space, but also sped up many operations. Access operations are, more often than not, local to each other. Having more records in a single block increases chances of not needing another disk access - which is aeons in CPU time, no matter how fast the disk and how slow the CPU is.
Of course most of these mechanisms were application-specific. But already the field-level compression can be done by a more generic layer inside a database - as soon as it had an idea about field location and size.
In the mid 1970s, which is about the time when generic databases started to become a thing, some implemented these methods - such as IBM's System R, close tied to later Ingres.
From Grampa's Vault
On an application-specific database, designed ca. 1976/77, we used a somewhat similar mechanism, albeit without a field dictionary. Records were structured as follows:
- total length of record
- unique key (fixed Length)
- version number
- write race detection
- a binary chunk, preceded by a length field
- a character chunk
The savings came within the character chunk. It can only hold, as the name implies, characters, which in EBCDIC occupy the range of X'40'..X'FF'. The compression routine simply walked along and replaced every occurrence of more than two (and less than 64) blanks (spaces) by its length in binary. E.g. three blanks became X'03' and so on.
If, for whatever reason, bytes with values of less than x'40' were encountered, they were stored as-is, preceded by x'00' and its length. Of course such were to be avoided.
When reading, a function provided a buffer and what it would expect as binary and total length - this was meant to allow upward (and strictly for reading, downward) compatibility, so record definitions could be extended (new fields) without the need to convert the all data including archive and/or recompile all accessing programs.
Depending on the data stored, savings of more than 90%, with an average of over 50%, were realized in real-world applications.
At some point we also added a simple RLE for other characters beside space (by using the X'01' prefix), but found that this would result in next to no savings. I think it stayed in the code until today, but I'm not sure.
Compared to field-based compression, this method had not only the advantage of not needing any knowledge about the record structure (beside where to begin compression), but more importantly, it didn't add any data for delimiters. Its worst-case storage size was the uncompressed record, where delimiter based systems add one byte per field - including for empty ones, where our method only used one in worst case.
Back to today ...
Long story short: While modern compression tools can deliver great results independent of the data to be compressed, simple methods, tailored to the data to be stored, can come quite close.
*1 - In fact, the request for deduplication in databases never was just a theoretical way toward 'cleaner' structures.
*2 - Believe me, that's one of the most simple examples. If there are only 28 bytes to store a complete transaction record, one gets very creative.
*3 - It's useful to remember that IBM already introduced specific control characters to be used as separators to ASCII.
