Over the past, 40 years or so, relational databases have become the work horse of
most enterprise data management systems. Relational databases as you all know
comprise of tables, which are nothing but a bunch of records with attributes or
fields which are of course laid out on disk in some way.
The most common layout is that of a row oriented database, where pages of disk are
consisting of rows of records. The major problem that relational
databases is address is that of transaction processing, where multiple
clients or users are trying to insert or update different records in the same
table, and their actions have to be protected from each other so that
consistency of some form is maintained. As the result the database management
systems build in many features. Like locking and other forms of
consistency control to ensure that transactions are effectively isolated from
each other. And this is the really primary function of
the relational database. The second function of course is queries.
Where the user should be able to get access to any record based on a
combination of where clauses or a combination of conditions that the record
needs to satisfy. Sql is the main language for accessing
relational data and essentially defines the relational model.
Indexes, such as the b+3 index depicted here, are used to speed up access to
records, so that SQL queries can actually be efficient.
The b+3 is the most common form of index, which is essentially like a binary tree,
except for the fact that. The interior nodes don't actually store
data values. They only store key values.
And the leaf nodes point to blocks of disk where particular combinations of keys are
actually available to retrieve. Other types of indexes like hash indexes,
bitmap indexes are also used but B + trees are by far the most popular for indexing a
row-oriented database. Now, the other important thing about
relational database is they, that they that they don't really rely on file
systems, provided by the operating system to manage disk.
They is, do their own disk management figuring out what pages is to prefetch,
and which pages is to replace from the memory based on the traffic that they see
coming in, in the form of queries for that matter transactions coming from multiple
clients. [inaudible] For the most part when the
data was reasonably small. And queries using indexes could be
performed fairly efficiently on exactly the same data stores where transactions
would insert an update data. The row-oriented data stores were
perfectly fine for both transaction processing and answering questions about
data. As, the volume of data grew and in
particular the width of data in terms of the number of columns that one would store
per record becomes very large. And clearly the amount of storage required
grows. But at the same time, what also happens is
that a query that only requires data from, say, two columns, ends up needing to fetch
data, about maybe 100 columns, just because they happen to come along with the
disk block as it is fetched. This makes query processing extremely
inefficient, both from a storage perspective as well as performance
perspective, and for such situations, the column oriented databases have been
developed in the past decade or so. Especially to take care of situations
where the number of columns is very large and only queries need to be supported
rather than transactions. In a column-oriented database unlike a row
store, sets of columns are stored together in disk blocks.
In other words, a particular record is actually split across in multiple disk
blocks with different sets of columns occurring in different blocks.
Within each block, the data is sorted along particular sets of columns.
So, that unlike a row store where data essentially gets stored as it's inserted,
the column-oriented database can process the data from a row store into different
sort orders for different columns. Of course, by doing so, one sort of loses
the identity of an individual record and therefore a column-oriented database needs
to create extra information in the form of what is called a join index where
different rows in different disk blocks are pulled together to indicate that they
actually form the same record. Column stores are ideally used for what
are known as analytical processing queries.
Not that such queries could not be done using rows stores as well.
It's just that when you have large numbers of columns, column stores become more
efficient. Now, this is an example of a OLAP or
Online Analytical Processing query. Essentially, there's a bunch of sales
figures which are essentially the quantity and amount of some product being sold to
certain customers. Add certain addresses where the retail
outlets are on particular days. And the sales obviously are different
products. Now, each of these fields is a dimension
which describes the particular sale record.
The dimensions themselves can be hierarchical in the sense that the
product, a particular product say, a particular type of mattress may actually
be of category mattress or bed and so on. Similarly, a particular day is part of a
week, which is part of a month, which is part of a quarter, year, et cetera.
And similarly for location. The kind of queries that one tries to
answer in OLAP while you are trying to select the total sales and group them by
the category so you get results which can be shown in a report, in a pie chart of
this form in various types of reporting including different types of charts are
what OLAP queries actually pro, produce. You can figure out how the SQL actually
works, it's fairly straightforward. But as far as what constitutes business
intelligence for most of the enterprise world, it is all about OLAP queries.
Analytics is largely thought of as being OLAP for a large part of the community.
However, as we have seen, there's much more to analytics than simply queries.
So, let's reflect now on why we actually need databases.
First of all, we need to add data as it's produced, and data is added for multiple
sources in parallel like multiple people executing sales transactions, or
e-commerce transactions, or banking transactions.
And they need to be isolated from each other, so that they don't create
inconsistent data, and so you need transaction processing.
The second reason you need databases is querying efficiently and which it will
lead to indexing and a high-level language like SQL.
But the point we need to think about is whether or not you actually need
transaction processing for analytics. Clearly we don't, and that's why we
develop column-oriented databases. At the same time, there may be some
advantages in not having to move the data out of a transaction store, and still able
to perform analytical queries or all that queries on them.
If you can avoid moving it, so that you'd don't need to incur the overhead of
transferring data from one database row-oriented transaction processing to say
column-oriented analytical database. Queries are, of course, important for OLAP
queries as we have just seen. But the important point to note here is
that for other types of analytics, apart from OLAP such as large scale counting
like the programming assignment that we've seen building classifiers using say
Bayesian techniques or executing large complex joints to compute sales by cities.
As we've seen in the map for this example last week.
Large volumes of data are actually going to be touched.
In fact, the entire data set is going to be touched by such programs.
In such situations, indexes become far less relevant.
What also becomes very relevant instead, is resilience to hardware failure because
program which touch large volume of data are likely to take a lot of time, and
therefore hardware can faill during the execution, and so we need to figure out
how to achieve fall tolerance. Mapreduce essentially provides that file,
fall tolerance and therefore becomes vital.
Lastly, it's important to recognize that OLAP is also a form of analytics.
And can rarely be viewed as computing a part of the joint distribution across all
the features, which are the columns of a table, but you're using intuition to
select which set of features we want to actually look at.
So, to summarize, there are two contradictory requirements here in
analytics. If you have large volumes of data being
touched, you don't need indexes. But if you want to find out pieces of the
joint distribution using OLAP queries and human intuition, you do need indexes.
And it is this dichotomy which is driving most of the debate in big data technology
above, say, the basic distributed file system layer.