So when we do a column organization then
we come, instantly, to the fact that we see how we can minimize
the access to memory and access to memory can be minimized
by, first I only access the columns I need
and second when we look at individual columns
then we can do something with columns we can't do or
couldn't do in a normal disk based database.
We couldn't do a attribute based compression in a row
database on disk, but we can do a column based compression
in an column based database in memory and this is what we
will look at one example now in go through the example and
then you can get a feeling
what we can achieve and why this column concept
then becomes so superior. We learned already main memory access
is the bottleneck and we want to reduce the overall
main memory access and one way is to reduce the amount
of bits we need to store the information which is
which is in a table.
So we want to introduce data compression
and we want to introduce data compression in a way that the
operators, the operations we perform on a table can be performed
in compressed form.
For the ones who know row based compressions,
the row based compressions at least the ones SAP
has used in the last 40 years, all did not allow execution
in compressed form. So before anything could happen
on a tuple, on an attribute of a tuple, the tuple had to be decompressed.
Our example is the world population, eight billion humans
and we have attributes like first name, last name, gender, country,
city, birth date, probably we have 200 bytes per person.
In the old days I hit
the total number of bytes we need, so what is eight billion by two
hundred, that's 1.6 terra.
Now we want to see how this comes down
when we start working on the data. We have here our simple table
tuple has a record ID, this is the relative position
in the table and then we have in character
the attributes here, the instances john, mary, jane etc.
We have a gender male female, female male male
etc.
Now we start a concept which is called dictionary
encoding, we take now an individual column
let's take the first name column and re-organize the data in
a vector, which is pointing
it to a dictionary and the dictionary we keep the name the
actual instance Mary, John, Mary, Jane, Peter
and in this dictionary we have a relative position of the name
which is which is an integer and use the integer then
in the actual column. So we replace the character string
John as a name by integer pointing to a character string
"John." So we have eight billion people we have only five million first names
so for five million first names we, here, we need
only 23 bits to encode this.
We do little design assessment here and how many
need bytes do we need for first names? 10 is not enough.
You have probably up to 20, there are some countries where
the first names are pretty extended.
We have no nobody from India here but there are others
in the world, so let us take 20 bytes instead of 20
bytes we can encode the same information by using 23
bits and a dictionary. So we get to take all the
distinct values of the first name, into a dictionary.
We sort the dictionary, then every name has a position.
John is on position 23, Mary on 24.
This is an integer of the length of 23 bit
and we store now this integer value called value ID
in the attribute-vector for first name.
The compression is now 24 bits, now probably we take
23 bits, we take 24 bits. This is
three bytes and we had twenty bytes before, so we have a compression
from 20 to 3.
Plus the dictionary.
So we save 17 bytes,
we save 17 bytes and the times a billion,
this is quite a lot and always remember if we reduce that,
that amount of space we need to store the information
we increase the speed with which we go through all this information.
In this case, it is, we increase the scan
of first names already by a factor of 70, 20 divided
by three this is seven, roughly.
Without doing anything the skin speed of first names is now
full table, full column scan speed is seven times faster than in
a database which stores the character.
When we do this with gender then it becomes even more obvious,
for gender we need only one bit
instead of n and f which is a character we can compressed now
from 8 bits to 1 bit so it's a factor 8.
We have a bit vector which is
8 billion bits long,
that's one billion characters.
When we want to scan through the vector
male female, so the gender vector, we just check for bit on and
off, then we can achieve a very fast scan speed.
So the dictionary, there is a design decision very early on
to keep the dictionaries sorted
this is good for inserts, this is good what we later will learn,
for joins. If the dictionaries are sorted we can have
binary search on top of the dictionary so with
a log we can find the distinct value
and we need this for speed of
creating or transferring incoming character-based tuples
into these dictionary encoding tuples. The dictionary
entries themselves can be compressed and we will see at least one compression
technology, or technique, it's not a technology, a technique later.
So the compression rate depends on the cardinality
of a column, how many different values
are in a column. If we have only two different values
like male and female in a column then I
can compress this down to one bit
and if I use the byte before, as I said, this is 8 to 1
in the case of first names
probably something like 7 to 1 or
less if we have a shorter first name field.
There are there two definitions here for cardinality
the, when we talk about the cardinality of table
then it is just the number of tuples in the relation because
every single tuple is, I still discuss
this, if the tuples are all distinct
and then the cardinality is equal to the number of tuples,
if we don't have duplicates.
A column cardinality is defined as the number
of distinct values in a column. So the column cardinality of
the gender column is very low, the column cardinality which
one is probably the highest one here, that's a
trick question
countries it's only 200, currencies is even less,
cities is a good one
one million only.
So you get a feeling how the actual character description
of objects in a world collapses. The
cardinality of those objects is relatively small
and when we use this for encoding we can achieve
significant compression rates. By the way, this
was done in the old days. in building
our enterprise systems a lot when you look at a
SAP system, an older SAP system or still carry forward, there's
a lot of coding. So there is not, country, a text
field in in a customer record, there is a country code pointing
to a country. So this type of dictionary encoding was introduced
many years ago in enterprise computing.
Sometimes painful, because the you always have
to re-translate it back and when you want to show
where 007 lives then you have to go
into 007's country code and from the country
code in the country table and then you find out he comes from
Great Britain. Systems which were developed later very often
didn't do this, systems which came from the PC world mainly
work on the original value strings. So the country is a field
and there is a country coded,
negative as you might have
the same countries several times misspelled in
the system. So there are all kinds of application issues
what we do here is we automatically code all columns
and compress them as much as we can down to bits. The nice thing
is we don't have to work on byte level anymore
because with the modern CPU's,
the modern input CPUs and I think other CPUs are
all following. We got new instructions
well we can shift the 64 bits back and
forth and can do all kinds of operations, bit oriented operations
with a very very high speed. So we have a sorted dictionary, we
have this, we have a compression rate
and then here are our size. Now the first names
5 million, last names 8 million, gender 2,
city 1, country 2 hundred, birthday 40,000, this is
just to get a feeling and the then we have the
entropy and we can,
we have item size we even have here 49 bytes so
I should have looked through this first here.
And with the dictionary we can compress this
significantly, here are the compression rates
on the between plain and with dictionary compression
on the right-hand side. When we look at the
compression, at this point we can already say
when we have a large table, one of these enterprise tables
coming from an SAP system. I have in mind now
a table with 500 attributes and as from sales and
we have learned already that probably only 20 % of
the attributes are being used in one single installation.
That means that 400 fields
on a populated 400 columns are
all empty and what does the database do if a column
is completely empty? There is no column.
So the first compression we get is columns which are not being
populated are being stored. They are known to the system
in the metadata. There is probably, technically
a little management information that the column
is empty but there is no column and we can
use that in the system, definitely it doesn't cost
space and definitely we can avoid processing columns which
are not being populated.
The second is the remaining columns we compressed
and the compression rates we can see here.
If the compression, the average compression is a factor 5
this is probably a good rule of thumb.
So compression of a factor 5 for populated data
and the compression of 100% or close to
a 100%, let's take 100% for non populated
data. If you find out the the amount of population
for a given table, this is just a mini program running
should be, by the way, a feature of the
system management tool, I think it is
somebody could check then we can already predict
what the compression will be before we ever do something
with a table. So knowing the distinct values and the size of
the table we can calculate the populated ones and the un-populated
ones, we don't have to calculate if we want to compare with
the x, the plane table, how it probably comes
into the system so all fields are populated even with default
values, then we have the compression factor.
Compression factor varies between, five is typically minimum
these are tables where all attributes are populated
to factor 50, these are tables in SAP financial
and it varies in between taking any type of tables,
some companies have set up a factor 10, is probably
pretty good as a compression factor. So if somebody says we have
today a 10 terrabyte table space
and we do not compress the data, this is for example in
maxDB or, in most cases, in DB2.
Then we need in this database only one.
Did I say terabyte or gigabyte? The equivalent.
So it's a factor 10.