5

The obvious way for a database to store data is with each record in a contiguous chunk, and each field having a fixed size and offset in the record. Joel Spolsky praises that way of doing things:

With relational databases, the performance of moving from record to record is fixed and is, in fact, one CPU instruction. That’s very much by design.

And what he says is true, or at least traditionally was.

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.

I would like to get a feel for when this started happening.

What was the first database that started at least optionally compressing tables? That is, compressing tables in situ as opposed to in backup dumps, and commercial-grade database rather than experimental prototype, and as a capability actually used in production rather than a lab demonstration?

1
  • 2
    What kind of compression? Even in the 1960s, systems like Pick “compressed” records by truncating trailing spaces. In the 1980s, Rdb/VMS did RLL compression at the field level.
    – RonJohn
    Nov 27 '20 at 1:59
8

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.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.