SAAS Multi-tenant Databases

There are some good high level discussions on the various database architectures for implementing software as a service.  I’m on going to duplicate that.  Instead, this article is going to highlight some of the issues and tradeoffs when multiple tenants (customers of the software service provider) are put into one database.   The core of the problem is having multiple tenants in one set of database tables can make queries that select data for only one customer much slower. 

First, I’m testing on a new system, one with 32 gig of memory.  Currently,  the innodb_buffer_pool_size set to 28 gig.   I’m using the same size tables as previously, both Sale and SaleTenant have 120 million rows and are about 27 and 28 gig respectively.  This means that the tables fit into memory, so the following tests do not have an IO component.  Not perfect, but it shouldn't make a difference in the conclusions for these tests.  

For the other two tables, there are 100 tenants, and 1 million customers. 

The ddl looks like this (yeah, key and constraint names don’t make sense).   First, the non-multi-tenant table. 

 

CREATE TABLE  `test`.`Sale` (

  `orderId` int(11) NOT NULL,

  `customerId` int(11) NOT NULL,

  `productId` int(11) NOT NULL,

  `productBigId` int(11) NOT NULL,

  `unit` int(11) NOT NULL,

  `purchaseAmount` decimal(16,2) NOT NULL,

  `purchaseCost` decimal(16,2) NOT NULL,

  `purchaseDate` datetime NOT NULL,

  PRIMARY KEY  (`purchaseDate`,`orderId`),

  UNIQUE KEY `idx_sale_order` (`orderId`),

  KEY `pf_sale_product` (`productId`),

  KEY `pf_sale_customer` (`customerId`),

  CONSTRAINT `pf_sale_customer` FOREIGN KEY (`customerId`) REFERENCES `Customer` (`customerId`),

  CONSTRAINT `pf_sale_product` FOREIGN KEY (`productId`) REFERENCES `Product` (`productId`)

) ENGINE=InnoDB

 

Then the table with a tenantId in the table. 

 

CREATE TABLE  `test`.`SaleTenant` (

  `orderId` int(11) NOT NULL,

  `tenantId` int(11) NOT NULL,

  `customerId` int(11) NOT NULL,

  `productId` int(11) NOT NULL,

  `productBigId` int(11) NOT NULL,

  `unit` int(11) NOT NULL,

  `purchaseAmount` decimal(16,2) NOT NULL,

  `purchaseCost` decimal(16,2) NOT NULL,

  `purchaseDate` datetime NOT NULL,

  PRIMARY KEY  (`tenantId`,`purchaseDate`,`orderId`),

  UNIQUE KEY `idx_saletenant_order` (`orderId`),

  KEY `pf_saletenant_product` (`productId`),

  KEY `pf_saletenant_customer` (`customerId`),

  CONSTRAINT `pf_saletenant_customer` FOREIGN KEY (`customerId`) REFERENCES `Customer` (`customerId`),

  CONSTRAINT `pf_saletenant_product` FOREIGN KEY (`productId`) REFERENCES `Product` (`productId`),

  CONSTRAINT `pf_saletenant_tentant` FOREIGN KEY (`tenantId`) REFERENCES `Tenant` (`tenantId`)

) ENGINE=InnoDB

 

Now, the tenant table. 

 

CREATE TABLE  `test`.`Tenant` (

  `tenantId` int(11) NOT NULL,

  `tenantName` varchar(32) NOT NULL,

  PRIMARY KEY  (`tenantId`)

) ENGINE=InnoDB DEFAULT

 

And a customer table with a tenantId column. 

 

CREATE TABLE  `test`.`Customer` (

  `customerId` int(11) NOT NULL default '0',

  `customerName` varchar(32) NOT NULL,

  `tenantId` int(11) NOT NULL default '0',

  PRIMARY KEY  (`customerId`),

  KEY `pf_customer_tenant` (`tenantId`),

  CONSTRAINT `pf_customer_tenant` FOREIGN KEY (`tenantId`) REFERENCES `Tenant` (`tenantId`)

) ENGINE=InnoDB

 

#1) Against a table that is clustered by the TenantId, this query takes 0.5 seconds to run.  As it selects about 1/100 of the Sale Tenant database, the performance isn’t bad.

 

select sum(unit) from SaleTenant  where TenantId = 77;

 

And the query plan shows that the custered index was used to scan on the relevant rows. 

*************************** 1. row ***************************

           id: 1

  select_type: SIMPLE

        table: SaleTenant

         type: ref

possible_keys: PRIMARY

          key: PRIMARY

      key_len: 4

          ref: const

         rows: 2708904

        Extra:

#2) The query against the Sale table without the tenantId is about 5 times slow, at 2.5 seconds.

 

select sum(unit)

  from Customer c

  join Sale s

    on c.customerId = s.customerId

where c.TenantId = 77

 

The plan shows that the database drives off the customer table and joins to the sales table on the customerId column. 

 

*************************** 1. row ***************************

           id: 1

  select_type: SIMPLE

        table: c

         type: ref

possible_keys: PRIMARY,pf_customer_tenant

          key: pf_customer_tenant

      key_len: 4

          ref: const

         rows: 5040

        Extra: Using index

*************************** 2. row ***************************

           id: 1

  select_type: SIMPLE

        table: s

         type: ref

possible_keys: pf_sale_customer

          key: pf_sale_customer

      key_len: 4

          ref: test.c.customerId

         rows: 57

        Extra:

 

3) Further qualifying by date shows where adding the tentantId to the SaleTenant id column further improves performance.   This sql runs in about 0.08 seconds, and is much faster than the query #1, which doesn't have the more selective date criteria. 

 

select sum(unit) from SaleTenant

where TenantId = 77

   and purchaseDate >= '2001-06-01'

   and purchaseDate < '2001-07-01'

The query plan shows that the clustered index of (tenantId, pruchaseDate, orderId) allowed the database to quickly find the relevant rows and  sequentially the relevant rows. 

 

*************************** 1. row ***************************

           id: 1

  select_type: SIMPLE

        table: SaleTenant

         type: range

possible_keys: PRIMARY

          key: PRIMARY

      key_len: 12

          ref: NULL

         rows: 150491

        Extra: Using where

 

4) As the tenant criteria drives off of the customer table, and the date criteria drives off of the sales table, and the optimizer needs to start with one of these two tables, this sql can’t be as efficient as the query #3.  In this case, the optimizer again (like query #2) decides to drive off the customer table.  Unlike query #3, the extra date criteria doesn’t improve performance as it must join to each Sale row to determine if the date is valid, and in this case, only about 1/12 of the rows are relevant.  This means 11/12 of the joins are, in effect, tossed away.   Thus, it has to do the same amount of work as query #2 and runs in about the same time as #2 2.5 seconds, or about 31 times slower than query #3. 

 

select sum(unit)

  from Customer c

  join Sale s

    on c.customerId = s.customerId

where c.TenantId = 77

   and purchaseDate >= '2001-06-01'

   and purchaseDate < '2001-07-01'

*************************** 1. row ***************************

           id: 1

  select_type: SIMPLE

        table: c

         type: ref

possible_keys: PRIMARY,pf_customer_tenant

          key: pf_customer_tenant

      key_len: 4

          ref: const

         rows: 5040

        Extra: Using index

*************************** 2. row ***************************

           id: 1

  select_type: SIMPLE

        table: s

         type: ref

possible_keys: PRIMARY,pf_sale_customer

          key: pf_sale_customer

      key_len: 4

          ref: test.c.customerId

         rows: 57

        Extra: Using where

 

So, obviously there are cases where adding a tenantId will make the queries run much faster.  The issue with adding a tenantId to all the tables and clustering on that column is queries that are not limited to a tenant (or set of tenants) will be slower in some cases.  The next two sql statements will show such a case. 

5) In this sql a simple sum is run against the Sale table for a month, summing about 1/12 of the table.  As the table is clustered by date the query is fast and runs in about 4.4 seconds.

 

select sum(unit)

  from Sale s

where purchaseDate >= '2001-06-01'

   and purchaseDate < '2001-07-01'

 

The query plan shows the clustered index being used to scan the table. 

 

*************************** 1. row ***************************

           id: 1

  select_type: SIMPLE

        table: Sale

         type: range

possible_keys: PRIMARY

          key: PRIMARY

      key_len: 8

          ref: NULL

         rows: 26733636

        Extra: Using where

 

The equivalent query against the SaleTenant table takes 39 seconds to run.  In this case, the entire table must be scanned as there is no date oriented index.  

 

select sum(unit) from SaleTenant

where purchaseDate >= '2001-06-01'

  and purchaseDate < '2001-07-01'

The plan show the full table scan. 

 

*************************** 1. row ***************************

           id: 1

  select_type: SIMPLE

        table: SaleTenant

         type: ALL

possible_keys: NULL

          key: NULL

      key_len: NULL

          ref: NULL

         rows: 123303794

        Extra: Using where

Assuming this cross-tenant access pattern is frequent enough to be a performance problem, a potential solution to this problem is to add a covering index.  However, this might not be an issue as the only organization likely to execute such a query would be the hosting company. 

Given enough tenants in a database, adding a tenantId to a mutli-tenant database is recommended as some queries are going to be at least an order of magnitude slower if you don’t.   As denormalizations go, this is a reasonable one as how often would the tenantId (owner) of a row change?  Just be aware that queries that don’t include a tenantId in the criteria can be much slower.  

I didn’t cover this, but partitioning by tenantId also makes sense and can make moving customers from one sharded database to another much easier.  Perhaps more about that later.

Clustered indexing and query performance

Last time I showed where partitioning could negatively impact performance, with one partitioned query being four times slower than a non-partitioned one when the data was partitioned by the same column as it was clustered by.  This time I’m going to show a way to get better performance by selecting a good clustered index. With the InnoDB, the create table primary key syntax encourages one to create the clustered index the same as the primary key. For transaction systems, in many cases, this makes sense.  But there are times, particularly for reporting systems, when this isn't advisable. 

To demonstrate this two similar tables will be created where the only difference is the indexing.  The below SQL shows an one of these tables, a 20 gig, 120 million rows tables, representing one year (about 10 million per month) of data.  This table is clustered by the primary key. 

create table SaleOrderCluster (

  orderId int not null,

  customerId int not null,

  productId int not null,

  productBigId int not null,

  unit int not null,

  purchaseAmount decimal(16,2) not null,

  purchaseCost decimal(16,2) not null,

  purchaseDate datetime not null,

  primary key (orderId),

  key idx_SaleOrderCluster_purchaseDate (purchaseDate),

  key idx_SaleOrderCluster_product (productId),

  key idx_SaleOrderCluster_customer (customerId),

  constraint pf_SaleOrderCluster_customer foreign key (customerId) references Customer (customerId),

  constraint pf_SaleOrderCluster_product foreign key (productId) references Product (productId)

) ENGINE=InnoDB

 

But in other cases, it makes sense to cluster the data on another key. In this case, the primary key of purchasedate is used to cluster the data by date as many queries scan a range of dates. There is still the need for a constraint on the orderId column, so a unique index is created on this column. This SQL creates the 28 gig, 120 million row table.  Note that the larger clustered index results in a noticeably larger disk utilization than the previous table (28 vs 20 gig). This is because all the other indexes point to the clustered index, which means the large clustered index increases the size of all the other indexes.  In both cases the table is much larger than the 4 gig of memory assigned to MySQL.

 

CREATE TABLE  Sale (

  orderId int not null,

  customerId int(11) not null,

  productId int(11) not null,

  productBigId int(11) not null,

  unit int(11) not null,

  purchaseAmount decimal(16,2) not null,

  purchaseCost decimal(16,2) not null,

  purchaseDate datetime not null,

  primary key  (purchaseDate,orderId),

  unique key idx_sale_order (orderId),

  key pf_sale_product (productId),

  key pf_sale_customer (customerId),

  constraint pf_sale_customer foreign key (customerId)  references Customer (customerId),

  constraint pf_sale_product foreign key (productId)  references  Product (productId)

) ENGINE=InnoDB

 

The only difference between these two table is which column is the clustered index.  To test the performance of these two indexes this stored procedure is used to see how fast a single row lookup executed. 

 

CREATE PROCEDURE testClusterSpeed()

begin

    declare vorderId INT default 0;

    declare loopcounter INT default 0;

    declare vcustomerId INT default 0;

    repeat

        set loopcounter = loopcounter + 1;

        set vorderId  = floor(1 + (rand()*120000000));

        set vcustomerId = (select customerId from SaleOrderCluster where orderId = vorderId);

    until loopcounter > 1000000

    end repeat;

end

The execution plan show it uses the clustered index to find the data.  The procedure took 983 seconds to query the data. 

+----+-------------+------------------+-------+---------+---------+-------+------+
| id | select_type | TABLE            | type  | KEY     | key_len | ref   | rows |
+----+-------------+------------------+-------+---------+---------+-------+------+
|  1 | SIMPLE      | SaleOrderCluster | const | PRIMARY | 4       | const | 1    |  
+----+-------------+------------------+-------+---------+---------+-------+------+

 

This is the same basic stored procedure except it is against the table with the purchasedate clustered index. 

 

CREATE PROCEDURE  testNoPartitionSpeed()

begin

    declare vorderId INT default 0;

    declare loopcounter INT default 0;

    declare vcustomerId INT default 0;

    repeat

        set loopcounter = loopcounter + 1;

        set vorderId  = floor(1 + (rand()*120000000));

        set vcustomerId = (select customerId from Sale where orderId = vorderId);

    until loopcounter > 1000000

    end repeat;

 

The plan for this is the expected lookup by the unique idx_sale_order index.

 

+----+-------------+-------+-------+----------------+---------+-------+------+
| id | select_type | TABLE | type  | KEY            | key_len | ref   | rows |
+----+-------------+-------+-------+----------------+---------+-------+------+
|  1 | SIMPLE      | Sale  | const | idx_sale_order | 4       | const | 1    |  
+----+-------------+-------+-------+----------------+---------+-------+------+

 

As the unique index needs to point to the clustered index, this stored proc takes about three times longer to run – 2780 seconds.  Stated differently, MySQL first uses the idx_sale_order to find the OrderID, but as all non clustered indexes point to the clustered index, the clustered index must also be read to ultimately find the row.  This last step isn't required if the clustered index is by OrderId as the data is organized by OrderId.  If most of the queries are against OrderId then using OrderId as the clustered index makes sense.  Plus, the larger Sale table with the purchaseDate clustered index, which would result in less cache hits for queries as less of it could fit into memory, can't help performance either. 

 

However, if most of the queries are against purchaseDate the performance of the two indexes flips. The below query runs against the table with the clustered index on the purchaseDate and runs in about 335 seconds. I ran this after restarting MySQL to ensure the data wasn’t in memory. If it was in memory it ran in seconds.

 

select sum(unit) from Sale

where purchaseDate < '2002-01-01'

   and purchaseDate > '2001-12-01'

 

+----+-------------+-------+-------+----------------+---------+-------+----------+
| id | select_type | TABLE | type  | KEY            | key_len | ref   | rows     |
+----+-------------+-------+-------+----------------+---------+-------+----------+
|  1 | SIMPLE      | Sale  | const | PRIMARY        | 8       |       | 28836984 |  
+----+-------------+-------+-------+----------------+---------+-------+----------+

 

When I ran the corresponding query on the table with the clustered index OrderId, I had to kill this query after 9000 seconds, which is over 27 times longer. This is because the query plan wasn’t very good as MySQL was using the date index to find each row rather than a much faster table scan.

 

select sum(unit) from SaleOrderCluster

where purchaseDate < '2002-01-01'

   and purchaseDate > '2001-12-01'

+----+-------------+------------------+-------+-----------------------------------+---------+-------+----------+
| id | select_type | TABLE            | type  | KEY                               | key_len | ref   | rows     |
+----+-------------+------------------+-------+-----------------------------------+---------+-------+----------+
|  1 | SIMPLE      | SaleOrderCluster | range | idx_SaleOrderCluster_purchaseDate | 8       |       | 16055948 |  
+----+-------------+------------------+-------+-----------------------------------+---------+-------+----------+

 

This is an example where the MySQL query optimizer is a bit immature.  So, I hinted the query to do a table scan and it took 3000 seconds, still about nine times slower than the other index, but much faster than a indexed lookup on 10 million rows.  The reason this is being so slow is the data for a month is distributed throughout the table as the table is organized by orderId, so finding one month of data means the entire table must be scanned. 

 

select sum(unit) from SaleOrderCluster use index (primary)

where purchaseDate < '2002-01-01'

   and purchaseDate > '2001-12-01'

+----+-------------+------------------+--------+-----+---------+-------+----------+
| id | select_type | TABLE            | type   | KEY | key_len | ref   | rows     |
+----+-------------+------------------+--------+-----+---------+-------+----------+
|  1 | SIMPLE      | SaleOrderCluster | all    |     | 8       |       | 29216712 |  
+----+-------------+------------------+--------+-----+---------+-------+----------+

 

Proving this, the time to query the for one month of dates takes a long as a query against the full table, as the below sql takes 3000 seconds to run as well.

 

select sum(unit) from SaleOrderCluster

+----+-------------+------------------+--------+-----+---------+-------+-----------+
| id | select_type | TABLE            | type   | KEY | key_len | ref   | rows      |
+----+-------------+------------------+--------+-----+---------+-------+-----------+
|  1 | SIMPLE      | SaleOrderCluster | all    |     | 8       |       | 129216712 |  
+----+-------------+------------------+--------+-----+---------+-------+-----------+

 

As more months are added, assuming the older months aren’t deleted, the SaleOrderCluster table performance of this type of date range queries will degrade even further.  Against the purchaseDate clustered table the same date range queries will run in close to constant time as the table grows, assuming the amount of data for a month remains constant.  This is because, while the size of the purchase date clustered index will be growing, the number of rows for the month of date being range scanned in that index will remain constant.  Partitioning by date in this case won't provide performance benefits as the data is already organized by date. 

So it seems there are two choices, either optimize for random reads by the real primary key of OrderId, or, optimize for date range queries.  There is a third alternative of adding a covering index on the all the columns being queried, not just the purchase date, on the SaleOrderCluster table, with the first column of the index being the PurchaseDate.  In this case all the above queries will be fast as both queries will be answered fully by a index, but the downside is the inserts against a larger covering index will be slower.  Perhaps I shall investigate that next time. 

Divide and be conquered?

Over the past four articles I've demonstrated cases where a denormalized data model is faster than a normalized one, but often not by that much, and a case where a normalized data model was a bit faster than a denormalized one.  My general conclusion was with today's optimizers one should target a normalized data model and then denormalize where it makes sense, even for reporting.  I'm not as much of a fan of the star schema, a heavily denormalized data model popularized by Ralph Kimball, as I used to be.  Star schemas are costly to build and maintain and the the time spent creating them can often be spent better on more productive optimizations, such as the creation of summary tables and better indexing.  I'm not saying the denormalization doesn't make sense in some cases, just that it doesn't make sense in all cases. 

Time on move on to the topic of this article, partitioning. 

There are many good articles out there on the new MySQL 5.1 partitioning feature so I'm not going to repeat them.  One of my favorites is http://dev.mysql.com/tech-resources/articles/mysql_5.1_partitions.html.  However, I want to point out how much partitions can degrade performance as I haven't seen that highlighted enough.  The difference between my test and other tests I've seen is the below tests deal with larger data volumes and result in more physical disk reads.  As tables that are most likely to be partitioned are the larger tables, the tables that won't fit into memory, I believe these tests better represent reality.  Or at least my reality.  As I currently use InnoDB these tests will be run on it. 

Right below is the non-partitioned, 10.5 gig, 60 million row table, which is has a clustered index (primary key) of purchaseDate and orderId.  MySQL has 1 gig of memory assigned to it so the most of the table won't fit into memory. 

CREATE TABLE  sale ( 
    orderId int(11) NOT NULL, 
    customerId int(11) NOT NULL, 
    productId int(11) NOT NULL, 
    productBigId int(11) NOT NULL, 
    unit int(11) NOT NULL, 
    purchaseAmount decimal(16,2) NOT NULL, 
    purchaseCost decimal(16,2) NOT NULL, 
    purchaseDate datetime NOT NULL, 
    primary key (purchaseDate,orderId), 
    unique key idx_sale_order (orderId), 
    key pf_sale_product (productId), 
    key pf_sale_customer (customerId), 
    constraint pf_sale_product foreign key (productId) references product (productId)
) engine=InnoDB

This is partitioned version of the above table.  The numbers in the partition by range clause represent monthly partitions of '2001-01-01', '2001-02-01', '2001-03-01', etc.  Also, the unique key on orderId is no longer possible due a partitioning limitation so it was changed to a non-unique index. 

create table salepartition (
    orderId int(11) not null,
    customerId int(11) not null,
    productId int(11) not null,
    productId int(11) not null,
    unit int(11) not null,
    purchaseAmount decimal(16,2) not null,
    purchaseCost decimal(16,2) not null,
    purchaseDate datetime not null,
    primary key (purchaseDate,orderId), 
    key idx_salePartition_order (orderId),
    key pf_salePartition_product (productId),
    key pf_salePartition_customer (customerId)
) engine engine =InnoDB
  partition by range (to_days(purchaseDate)) 
   (partition p0 values less than (730882) engine = InnoDB, 
    partition p1 values less than (730910) engine = InnoDB, 
    partition p2 values less than (730941) engine = InnoDB, 
    partition p3 values less than (730971) engine = InnoDB, 
    partition p4 values less than (731002) engine = InnoDB, 
    partition p5 values less than (731032) engine = InnoDB, 
    partition p6 values less than (731063) engine = InnoDB, 
    partition p7 values less than (731094) engine = InnoDB, 
    partition p8 values less than (731124) engine = InnoDB, 
    partition p9 values less than (731155) engine = InnoDB, 
    partition p10 values less than (731185) engine = InnoDB, 
    partition p11 values less than (731216) engine = InnoDB, 
    partition p12 values less than maxvalue engine = InnoDB)
 

What I did to test was to to write two short programs that would query the same customerId column of both tables.   The below program runs against the non-partitioned table and runs in about 18 seconds.

create procedure testNoPartitionSpeed()
begin
    declare vorderId INT default 0;
    declare loopcounter INT default 0;
    declare vcustomerId INT default 0;
    repeat
        set loopcounter = loopcounter + 1;
        set vorderId  = floor(1 + (rand()*60000000));
        set vcustomerId = (select customerId from sale where orderId = vorderId);
    until loopcounter > 1000
end

The and the plan is simple. 

+----+-------------+-------+----------+----------------------+---------+------------------+----------+
| id | select_type | TABLE | type     | KEY                  | key_len | ref              | rows     |
+----+-------------+-------+----------+----------------------+---------+------------------+----------+
|  1 | SIMPLE      | sale  | const    | 'idx_sale_order'     | 4       | const            | 1        |  
+----+-------------+-------+----------+----------------------+---------+------------------+----------+

Next I ran a similar program against the partitioned table and it ran in about 77 seconds, about four times slower.

create procedure testPartitionSpeed()
begin
    declare vorderId INT default 0;
    declare loopcounter INT default 0;
    declare vcustomerId INT default 0;
    repeat
        set loopcounter = loopcounter + 1;
        set vorderId  = floor(1 + (rand()*60000000));
        set vcustomerId = (select customerId from salepartition where orderId = vorderId);
    until loopcounter > 1000
    end repeat;
end

+----+------------+---------------+----------------------+------+--------------------+--------+-------+------+
| id | selecttype | TABLE         | partitions           | type | KEY                | keylen | ref   | rows |
+----+------------+---------------+----------------------+---------------------------+--------+-------+------+
|  1 | SIMPLE     | salepartition | p0,p1,p2,p3,p4,p5,p6,| ref  | idx_salepart_order | 4      | const | 13   |
|    |            |               | p7,p8,p9,p10,p11,p12 |      |                    |        |       |      |   
+----+------------+---------------+----------------------+------+--------------------+--------+-------+------+

The reason this slow performance is the salePartition table is composed of 13 partitions, 12 with actual data, and each one of which has a separate idx_salePartition_customer index.  This means when a query needs to find a customerId it needs to probe into all 13 partitions, which shows up as the 13 in the explain rows column.  This performance hit is why some databases have global indexes that cross all partitions.  MySQL doesn't have this functionality yet, but since SQL Server just added partitioning functionality in late 2005 MySQL isn't far behind.

Querying by a non-partitioned index was a severe performance hit, but the partition by date will improve queries that limit the data by date, right?  Well, unfortunately not.  The below query runs in four seconds.

select sum(unit) from sale
where purchaseDate >= '2001-09-01'
   and purchaseDate < '2001-10-01'

+----+-------------+-------+----------+----------------------+---------+------------------+----------+
| id | select_type | TABLE | type     | KEY                  | key_len | ref              | rows     |
+----+-------------+-------+----------+----------------------+---------+------------------+----------+
|  1 | SIMPLE      | sale  | range    | PRIMARY              | 4       | null             | 9907110  |  
+----+-------------+-------+----------+----------------------+---------+------------------+----------+

And this query also runs in about four seconds.

select sum(unit) from salepartition
where purchaseDate >= '2001-09-01'
   and purchaseDate < '2001-10-01'

+----+-------------+----------------+------------+---------+---------+---------+------------------+----------+
| id | select_type | TABLE          | partitions | type    | KEY     | key_len | ref              | rows     |
+----+-------------+----------------+------------+-------------------+---------+------------------+----------+
|  1 | SIMPLE      | salepartition  | 'p8,p9'    | range   | primary | 8       | null             | 2464709  |  
+----+-------------+----------------+------------+---------+---------+---------+------------------+----------+

Both queries run in the same amount of time as the primary key already orders and therefore limits the data by date, meaning the partition doesn't have any performance benefit in this case.

For InnoDB (other databases will behave differently, I didn't test them), where the partitioning is by the leading column of the primary key, partitioning isn't going to provide performance benefits and will instead decrease performance in some cases.  This assumes if multiple disks are used to store a table all of the table, partitioned or not, is striped across all the disks (as compared to putting a partition on each disk, which is suboptimal as the load is unlikely to be evenly distributed over the disks). 

There are still solid operational reasons to implement partitioning, such as making it easier to backup seperate partitions.  But as others have said, if you aren't careful and test you can find partitioning will degrade performance.    

 

 

 

 

 

A setting star

On my second blog I stated I would demonstrate a case where a denormalized Star schema is 50 times slower than a normalized data model.  Well, while writing this I looked at the tables again and realized that I didn't have optimal indexes and my statistics weren't optimal.  Yeah, I feel a bit foolish.  Once I fixed those issues there wasn't a performance difference.  I'll go more into this during the post test discussion. 

First, these are the table that will be used to test the performance of the normalized and denormalized data models.  The ProductNormal table represents the normalized table, has 10 million rows, and is about 0.8 gig. 

 

create table ProductNormal (
     productId int(11) not null,
     productName varchar(32) not null,
     productGroupId int(11) not null,
     productBrandId int(11) not null,
     primary key (productId),
     key `idx_ProductNormal_GroupIdBrandId` (`productGroupId`,`productBrandId`),
     key `idx_ProductNormal_BrandGroup` (`productBrandId`,`productGroupId`), 
     constraint `fk_ProductNormal_productBrandId` 
         foreign key (`productBrandId`) REFERENCES     `ProductBrand` (`productBrandId`), 
     constraint `fk_ProductNormal_productGroupId` 
         foreign key (`productGroupId`) REFERENCES `ProductGroup` (`productGroupId`)
) engine=InnoDB

 

The small ProductBrand table has 11 rows.  

 

create table ProductBrand (
    productBrandId int(11) not null,
    productBrandName varchar(32) not null,
    primary key (productBrandId),
    unique key idx_ProductBrand_Name (ProductBrandName)
) engine=InnoDB

 

The ProductGroup table has 101 rows.  

 

create table ProductGroup (
    productGroupId int(11) not null,
    productGroupName varchar(32) not null,
    primary key (productGroupId),
    unique key idx_ProductGroup_Name (ProductGroupName)
) engine=InnoDB

 

The 10 million row ProductDenorm combines the previous three tables into a 1.27 gig table. 

create table ProductDenorm (
    productId int(11) not null,
    productName varchar(32) not null,
    productGroupId int(11) not null,
    productGroupName varchar(32) not null,
    productBrandId int(11) not null,
    productBrandName varchar(32) not null,
    primary key (productId),
    key idx_ProductDenorm_GroupNameBrandName (productGroupName, productBrandName),
    key idx_ProductDenorm_BrandNameGroupName (productBrandName, productGroupName)
) engine=InnoDB

 

The 120 million row Sale table is about 30 gig. 

create table Sale (
  orderId int(11) not null,
  customerId int(11) not null,
  productId int(11) not null,
  productBigId int(11) not null,
  unit int(11) not null,
  purchaseAmount decimal(16,2) not null,
  purchaseCost decimal(16,2) not null,
  purchaseDate datetime not null,
  primary key  (purchaseDate,orderId),
  unique key idx_sale_order (orderId),
  key idx_sale_product (productId),
  key idx_sale_customer (customerId),
  constraint pf_sale_customer foreign key (customerId) references Customer (customerId),
  constraint pf_sale_product foreign key  (productId) references Product (productId)
) engine=InnoDB

 

First, the below denormalized version of the query takes about 0.39 seconds, averaged over 100 executions.  The rest of the queries are also averaged over 100 runs.  What is interesting is the driving table of the plan is not the sale table, but the product table.  There are two basics query plans the optimizer can decide on.  The first is to drive off of the Sale fact table, which was covered in previous blogs.  The second is to drive off of the dimension (descriptive tables) like the ProductGroup table.  After this article, both cases will have been tested. 

 

select sum(unit) from Sale s
  join ProductDenorm p
    on s.productId = p.productId
where p.productBrandName = 'ProductBrand 1'
   and p.productGroupName = 'Group 1'
   and purchaseDate > '2001-12-30'

 

+----+-------------+-------+----------+---------------------+---------+-------------+-------+------------+
| id | select_type | table | type     | key                 | key_len | ref         | rows  | extra
+----+-------------+-------+----------+---------------------+---------+-------------+-------+------------+
|  1 | SIMPLE      | p     | ref      | idx_ProductDenorm_  | 70      | const,const | 13608 | Using where
|    |             |       |          | BrandNameGroupName  |         |             |       | 
+----+-------------+-------+----------+---------------------+---------+-------------+-------+------------+
|  1 | SIMPLE      | s     | ref      | pf_sale_product     | 4       | p.productId | 10    | Using where
+----+-------------+-------+----------+---------------------+---------+-------------+-------+------------+

 

The normalized version also takes about 0.39 seconds.  The plan is similar to the previous one, but the driving table is the normalized ProductGroup and not the denormalized ProductDenorm.   In both cases the last table in the plan is the Sale table. 

 

select sum(unit)
  from Sale s
  join ProductNormal p
    on s.productId = p.productId
  join ProductGroup pg
    on p.productGroupId = pg.productGroupId
  join ProductBrand pb
    on p.productBrandId = pb.productBrandId 
where pb.productBrandName = 'ProductBrand 1'
   and pg.productGroupName = 'Group 1'
   and purchaseDate > '2001-12-30';

 

+----+-------------+-------+------+------------------------------+---------+--------------------+------+------------+
| id | select_type | table | type | key                          | key_len | ref                | rows | extra
+----+-------------+-------+------+------------------------------+---------+--------------------+------+------------+
|  1 | SIMPLE      | pg    | ref  | idx_ProductGroup_Name        | 34      | const              | 1    | where,index 
+----+-------------+-------+------+------------------------------+---------+--------------------+------+------------+
|  1 | SIMPLE      | pb    | ref  | idx_ProductBrand_Name        | 34      | const              | 1    | where,index
+----+-------------+-------+------+------------------------------+---------+--------------------+------+------------+
|  1 | SIMPLE      | p     | ref  | idx_ProductNormal_BrandGroup | 8       | pb.productBrandId, | 3258 | where,index 
|    |             |       |      |                              |         | pg.productGroupId  |      |
+----+-------------+-------+------+------------------------------+---------+--------------------+------+------------+
|  1 | SIMPLE      | s     | ref  | pf_sale_product              | 4       | p.productId        | 10   | where,index
+----+-------------+-------+------+------------------------------+---------+--------------------+------+------------+

 

How about the same basic query, but for a month of data?  It also takes about .39 seconds. 

 

select sum(unit) from Sale s
  join ProductDenorm p
    on s.productId = p.productId
where p.productBrandName = 'ProductBrand 1'
   and p.productGroupName = 'Group 1'
   and purchaseDate > '2001-12-01'

 

+----+-------------+-------+----------+--------------------+---------+-------------+----------+-----------+
| id | select_type | table | type     | key                | key_len | ref         |          | extra
+----+-------------+-------+----------+--------------------+---------+-------------+----------+-----------+
|  1 | SIMPLE      | p     | ref      | idx_ProductDenorm_ | 70      | const,const | 13608    | where
|    |             |       |          | BrandNameGroupName |         |             |          |
+----+-------------+-------+----------+--------------------+---------+-------------+----------+-----------+
|  1 | SIMPLE      | s     | ref      | pf_sale_product    | 4       | p.productId | 10       | where
+----+-------------+-------+----------+--------------------+---------+-------------+----------+-----------+

 

The normalized version also takes about .39 seconds against a month of data.   So, at least for these simple queries the normalized data model is just as fast as the denormalized one. 

 

select sum(unit) from Sale s
  join ProductNormal p
    on s.productId = p.productId
  join ProductGroup pg
    on p.productGroupId = pg.productGroupId
  join ProductBrand pb
    on p.productBrandId = pb.productBrandId
where pb.productBrandName = 'ProductBrand 1'
   and pg.productGroupName = 'Group 1'
   and purchaseDate > '2001-12-01'

 

+----+-------------+-------+------+------------------------------+---------+--------------------+------+------------+
| id | select_type | table | type | key                          | key_len | ref                | rows | extra
+----+-------------+-------+------+------------------------------+---------+--------------------+------+------------+
|  1 | SIMPLE      | pg    | ref  | idx_ProductGroup_Name        | 34      | const              | 1    | where,index 
+----+-------------+-------+------+------------------------------+---------+--------------------+------+------------+
|  1 | SIMPLE      | pb    | ref  | idx_ProductBrand_Name        | 34      | const              | 1    | where,index
+----+-------------+-------+------+------------------------------+---------+--------------------+------+------------+
|  1 | SIMPLE      | p     | ref  | idx_ProductNormal_BrandGroup | 8       | pb.productBrandId, | 3258 | where,index
|    |             |       |      |                              |         | pg.productGroupId  |      |
+----+-------------+-------+------+------------------------------+---------+--------------------+------+------------+
|  1 | SIMPLE      | s     | ref  | pf_sale_product              | 4       | p.productId        | 10   | where,index
+----+-------------+-------+------+------------------------------+---------+--------------------+------+------------+

 

Over the course of four blog entries tests have shown that joins are expensive, but in spite of that, denormalized data isn't that much faster than a normalized data model.  The best case was when a denormalized table was a bit more than twice as fast as a few normalized tables.  Then there was the case where a normalized data model was faster than denormalized one as the normalized one used memory more efficiently.  And finally, when the optimizer drives off of the dimensional (descriptive) data and not the fact table there isn't a noticeable difference in performance.  I know there are exceptions when a normalized data model performance is worse than what I've shown; but they do appear to be exactly that, exceptions. 

I could run more complex tests, and I probably will over time, but there are enough of them start coming to tentative conclusions.   In the transactional world the general rule is to normalize and only denormalize when a specific query or set of queries warrant it.  Given that denormalization can degrade performance at times, this is wise.  The time spent denormalizing the data model would be better spent adding better indexes and getting the statistics right. 

For reporting systems I would, hesitantly, recommend the same practice - normalize first and then denormalize when required.  I believe the Star schema made sense when it was first proposed a decade ago and database optimizers were weak.  A denormalized data model has less join permutations to consider and therefore an optimizer was better able to find a fast query plan when the data model was simple.  

Over the past decade, the database optimizers have improved and are better able to handle the complexity of the normalized data model.  When I was working on this article my normalized data model was initially much slower than my denormalized version.  One of the main reasons my normalized data model was slow was because my statistics weren't that good.  With better stats, MySQL, which isn't known to have the best optimizer, was at times able to find a normal query plan just as fast as the denormalized version.  If this is true for the youthful MySQL it should be true for the more established databases like SQL Server and Oracle, which are better at creating stats. 

It takes considerable effort to develop and populate a Star Schema.  I now believe, in many cases at least, a normalized data model is best for reporting and denormalize on an exceptional basis where it makes sense.  Develop the physical data model for reporting systems just like you would a transactional physical data model.  If denormalization makes an important query much faster then denormalize. 

This may be reflective of the start up environments where I work, where we have reasonably simple data models of a hundred of so tables but some of those tables have up to a billion rows.  But based on this experience and these tests, the time spent denormalizing the data model would be better spent on creating better indexes and finding and populating summary tables.  This is where the huge, orders of magnitude, improvements are to be found.  Yes, a star schema would improve performance of that important query, but would a summary table be even better? 

I'm sure there are exceptions to this; with software as complex as a database, and some of those huge and complex databases out there, there are always exceptions.  MySQL is still young and, for example, the statistics functionality of MySQL isn't reliable enough for this to be true in all cases.  I believe a simple reporting application that has a limited number of predefined reports can get by with a normalized data model that is selectively denormalized when required, but complex reporting application with frequent ad hoc reporting needs would still do better with a Star schema.  Where the dividing line is a judgement call, but if in doubt I would start with a normalized data model and iterate to a more denormalized one. 

Yet as the capabilities of the optimizers continue to improve I suspect the development of reporting systems should shift to a more normalized data modeling approach. 

Denormalized data, not so fast?

The last article demonstrated that a denormalized data model was a bit faster than a normalized data model when all the data fit into memory, but only by 20-30 percent or so, at least for the experiments I ran.  This article deals with larger data volumes and shows a case where normalized data is faster than denormalized data and then details another case where a denormalized data model faster. 

First, this is the what the tables in question look like.  All the product tables have 10 million rows.  The denormalized ProductAll table is 5.2 gig, and as innodb_buffer_pool_size is set to 4 gig, this table won't fit into memory.  The filler column represents other product attributes without having to specify them in detail.

 

create table ProductAll (
    productAllId int(11) not null,
    productAllName varchar(32) not null,
    productGroupId int(11) not null,
    productGroupName varchar(32) not null,
    filler varchar(4000) not null,
    productBrandId int(11) not null,
    productBrandName varchar(32) not null,
    primary key (productAllId)
) engine=InnoDB

 

The normalized ProductLess table  is 4.9 gig, a bit less than the ProductAll table, but it still has the filler column.   

create table ProductLess (
    productId int(11) not null,
    productName varchar(32) not null,
    productGroupId int(11) not null,
    productBrandId int(11) not null,
    filler varchar(4000) not null,
    primary key (`productId`)
) engine=InnoDB

 

The 4.6gig productBig table will be used to explore how joining two large tables, tables that are both larger than the memory allocated to mysql, together performs. 

create table ProductBig (
    productBigId int(11) not null,
    filler` varchar(4000) default NULL,
    productBrandId int(11) not null,
    PRIMARY KEY (productBigId),
    CONSTRAINT on_ProductBig_productBigId FOREIGN KEY (productBigId) REFERENCES Product (productId)
) ENGINE=InnoDB

The 9.2 Product2Filler table is a combination of the the ProductBig and the ProductLess table.  Where the filler columns of both the ProductBig and the ProductLess tables are 384 characters, the Product2Filler filler column is twice that at 768 characters.

create table Product2Filler (
    productId int(11) not null,
    productName varchar(32) not null,
    productGroupId int(11) not null,
    productBrandId int(11) not null,
    filler varchar(4000) not null,
    primary key  (`productId`)
) engine=InnoDB; 

 

The Sale table has 120 million rows and is about 30 gig.   It, combined with the product tables, even just the one month (out of 12 months, or 1/12 of the data) I query against, don't fit into memory.

 

create table Sale (
  orderId int(11) not null,
  customerId int(11) not null,
  productId int(11) not null
  productBigId int(11) not null,
  unit int(11) not null,
  purchaseAmount decimal(16,2) not null,
  purchaseCost decimal(16,2) not null,
  purchaseDate datetime not null,
  primary key  (purchaseDate,orderId),
  unique key idx_sale_order (orderId),
  key pf_sale_product (productId),
  key pf_sale_customer (customerId),
  constraint `pf_sale_customer` foreign key (customerId) references Customer (customerId),
  constraint `pf_sale_product` foreign key (productId) references Product (productId)
) engine=InnoDB

The tiny ProductGroup table is a small 101 rows. 

create table ProductGroup (
    productGroupId int(11) not null,
    productGroupName varchar(32) not null,
    primary key  (productGroupId)
) engine=InnoDB

 

Onto the actual sql.  The below denormalized query takes about 4380 seconds.  As all the data doesn't fit into memory MySQL needs to do some serious reading, which shows up in iostat numbers, as do all the below queries.  All the below queries are read bound.  The buffer pool hit rate of 950 /1000 (or so - I averaged a few samples) verifies the heavy io.  This is a huge performance difference from the Blog of December 5, where the equivalent sql running against product tables that fit into memory, where the product table don't have the filler column, ran in 25 seconds. 

 

select productGroupName, sum(unit)
  from Sale s
  join ProductAll p
    on s.productId = p.productAllId
where purchaseDate >= '2001-12-01'
group by productGroupName;

+----+-------------+-------+----------+----------+---------+------------------+----------+-------------------+

| id | select_type | TABLE | type     | KEY      | key_len | ref              | rows     | Extra             |

+----+-------------+-------+----------+----------+---------+------------------+----------+-------------------+

|  1 | SIMPLE      | s     | range    | PRIMARY  | 8       | null             | 30931362 | Using filesort... |

+----+-------------+-------+----------+----------+---------+------------------+----------+-------------------+

|  1 | SIMPLE      | p     | eq_ref   | PRIMARY  | 4       | s.productId      | 1        | null              |

+----+-------------+-------+----------+----------+---------+------------------+----------+-------------------+

 

At 3790 seconds, the normalized sql runs a bit faster than the above denormalized version.  Like the previous query, It also is disk bound, but it has a better buffer hit rate of 972 / 1000 (or so).  As the data is smaller it is better able to fit into memory, which explains the higher buffer hit rate and the better performance?  I'm not convinced this is true as it needs to do more reads the get the small productGroup data, which is likely to be in memory all the time even with the MySQL least recently used caching - does anyone have insight into this?

 

select productGroupName, sum(unit)
  from Sale s
  join ProductLess p
    on s.productId = p.productId
  join ProductGroup pg
    on p.productGroupId = pg.productGroupId
where purchaseDate >= '2001-12-01'
group by productGroupName

+----+-------------+-------+----------+----------+---------+------------------+----------+-------------------+

| id | select_type | TABLE | type     | KEY      | key_len | ref              | rows     | Extra             |

+----+-------------+-------+----------+----------+---------+------------------+----------+-------------------+

|  1 | SIMPLE      | s     | range    | PRIMARY  | 8       | null             | 30931362 | Using filesort... |

+----+-------------+-------+----------+----------+---------+------------------+----------+-------------------+

|  1 | SIMPLE      | p     | eq_ref   | PRIMARY  | 4       | s.productId      | 1        | null              |

+----+-------------+-------+----------+----------+---------+------------------+----------+-------------------+

  1 | SIMPLE       | pg    | eq_ref   | PRIMARY  | 4       | p.productGroupId | 1        | null              |

+----+-------------+-------+----------+----------+---------+------------------+----------+-------------------+

 

From this one might expect that a normalized data model is faster in all cases when dealing with large data volumes.  But how about joining a large table, not only to a small table in memory table, but also to another large table.  The below join of the ProductLess table to the ProductBig table takes 20,429 seconds.   

select productGroupName, sum(unit)
  from Sale s
  join ProductLess p
    on s.productId = p.productId
  join ProductGroup pg
    on p.productGroupId = pg.productGroupId
  join ProductBig pb
    on p.productId = pb.productBigId
where purchaseDate >= '2001-12-01'
group by productGroupName

 

+----+-------------+-------+----------+----------+---------+------------------+----------+-------------------+

| id | select_type | TABLE | type     | KEY      | key_len | ref              | rows     | Extra             |

+----+-------------+-------+----------+----------+---------+------------------+----------+-------------------+

|  1 | SIMPLE      | s     | range    | PRIMARY  | 8       | null             | 30931362 | Using filesort... |

+----+-------------+-------+----------+----------+---------+------------------+----------+-------------------+

|  1 | SIMPLE      | pb    | eq_ref   | PRIMARY  | 4       | s.productId      | 1        | Using index       |

+----+-------------+-------+----------+----------+---------+------------------+----------+-------------------+

|  1 | SIMPLE      | p     | eq_ref   | PRIMARY  | 4       | pb.productBigId  | 1        | Using where       |

+----+-------------+-------+----------+----------+---------+------------------+----------+-------------------+

  1 | SIMPLE       | pg    | eq_ref   | PRIMARY  | 4       | p.productGroupId | 1        |                   |

+----+-------------+-------+----------+----------+---------+------------------+----------+-------------------+

 

When the ProductLess table and the ProductBig tables are combined into the Product2Filler table similar SQL takes 9219 seconds, about half as long.  In at least in some cases, joining two large tables, tables that can't fully fit into memory, a combined data model is faster.  I know this isn't really a denormalization as both are keyed by productId, but I believe it has the same performance characteristics as a denormalized data model.  At least it shows an example of what happens when two large tables are combined into one even larger one. 

 

select productGroupName, sum(unit)
  from Sale s
  join Product2Filler p
    on s.productId = p.productId
  join ProductGroup pg
    on p.productGroupId = pg.productGroupId
where purchaseDate >= '2001-12-01'
group by productGroupName

+----+-------------+-------+----------+----------+---------+------------------+----------+-------------------+

| id | select_type | TABLE | type     | KEY      | key_len | ref              | rows     | Extra             |

+----+-------------+-------+----------+----------+---------+------------------+----------+-------------------+

|  1 | SIMPLE      | s     | range    | PRIMARY  | 8       | null             | 30931362 | Using filesort... |

+----+-------------+-------+----------+----------+---------+------------------+----------+-------------------+

|  1 | SIMPLE      | p     | eq_ref   | PRIMARY  | 4       | s.productId      | 1        |                   |

+----+-------------+-------+----------+----------+---------+------------------+----------+-------------------+

  1 | SIMPLE       | pg    | eq_ref   | PRIMARY  | 4       | p.productGroupId | 1        |                   |

+----+-------------+-------+----------+----------+---------+------------------+----------+-------------------+

 

As a side note, the below query against data that is not cached (different dates than the other queries), the query runs in 340 seconds.  It looks like the cost of a sequential table (range) scan is insignificant compared to a random index read of another table that can't fit into memory.  Stated differently, joins are at times costly.

 

select count(*) from Sale
where purchaseDate >= '2001-03-01'
   and purchaseDate < '2001-04-01'

 

What has been shown is normalized data is sometimes faster than denormalized data, and sometimes combined data is faster.   So far the case for the denormalized data model isn't that persuasive.  This is true both when all the data can fit into memory and when it can't and many reads are required.  Why, then, do so many people use star schemas for reporting systems?  In the next article there will be a case where a denormalized data model is a bit faster than what has been shown so far. 

Denormalized data is a bit faster than normalized data (but by enough?)

In the last article the performance impact of joins was shown.  This one will demonstrate cases where denormalized joins are a bit faster, as will the third article with larger data volumes.  The fourth article, the most interesting one, will show where a denormalized data model can be 50 times faster than a normalized data model. 

Here are the tables that will be involved in the sql.  The normalized ProductSmall table has a 100 million rows and is about 0.67 gig. 

 

create table ProductSmall (

    productSmallId int(11) not null,

    productSmallName varchar(32) not null,

    productGroupId int(11) not null,

    primary key (productSmallId),

    key idx_ProductSmall_productGroup (productGroupId),

    constraint con_ProductSmall_productGroup

        foreign key (productGroupId) references ProductGroup (productGroupId)

) ENGINE=InnoDB;

 

This 101 row table has the product group text and joins to the ProductSmall table.   

 

create table ProductGroup (

    productGroupId int(11) not null,

    productGroupName varchar(32) not null,

    primary key (productGroupId)

) ENGINE=InnoDB;

 

This is the 100 million rows denormalized combination of the previous two tables.  It is 1.2 gig and is about twice the size of the normalized version. 

  

create table Product (

    productId int(11) not null,

    productName varchar(32) not null,

    productGroupId int(11) not null,

    productGroupName varchar(32) not null,

    primary key (productId)

) ENGINE=InnoDB;

 

First, how fast does it take to do a sequential scan of 652,637 rows of the 120 million rows Sale table?  At 0.3 seconds it is fast as it is cached is memory.  This is the same Sale table from the previous article.  Purchase date is the leading edge of the primary key, which explains the range scan on the primary key. 

 

select sum(unit) from Sale

where purchaseDate >= '2001-12-30'

 

+----+-------------+-------+-------+---------------+----------+---------+------+----------+-------------+

| id | select_type | TABLE | type  | possible_keys | KEY      | key_len | ref  | rows     | Extra       |

+----+-------------+-------+-------+---------------+----------+---------+------+----------+-------------+

|  1 | SIMPLE      | Sale  | range | PRIMARY       | PRIMARY  | 8       | null | 1882540  | USING WHERE |

+----+-------------+-------+-------+---------------+----------+---------+------+----------+-------------+

 

Adding a join to a small table (that also fits into memory) is bit slower than the previous simple table scan, but the the below sql runs in a about 1.1 seconds.  Still reasonably fast and less than four times slower than a sequential scan of the data.  This is great performance as btree lookup can be much more expensive than a sequential table scans.  This is a sign that the innodb adaptive hash indexing is working well for reads.  And running "show engine innodb status" shows "18617.95 hash searches/s, 5.00 non-hash searches/s".  Show engine also shows "Buffer pool hit rate 1000 / 1000", indicating that all the data does fit into memory.  I won't show it, but the rest of the queries in this article have similar numbers.

 

select sum(unit) from Sale s

  join ProductSmall p

    on s.productId = p.productSmallId

where purchaseDate >= '2001-12-30';

 

+----+-------------+-------+----------+----------+---------+-------------+----------+-------------+

| id | select_type | TABLE | type     |  KEY     | key_len | ref         | rows     | Extra       |

+----+-------------+-------+----------+----------+---------+-------------+----------+-------------+

|  1 | SIMPLE      | s     | range    |  PRIMARY |8        | null        |  1882540 | Using where |

+----+-------------+-------+----------+----------+---------+-------------+----------+-------------+

|  1 | SIMPLE      | p     |  eq_ref  |  PRIMARY | 4       | s.productId | 1        | Using index |

+----+-------------+-------+----------+----------+---------+-------------+----------+-------------+

 

Using this normalized data model, where product group names are in a different tables, the extra join slows down performance but only by a bit.  This sql runs in about 1.4 seconds.  

 

select sum(unit) from Sale s

  join ProductSmall p

    on s.productId = p.productSmallId

  join ProductGroup pg

    on p.productGroupId = pg.productGroupId

where purchaseDate >= '2001-12-30';

 

The plan looks similar to the previous one, with the addition of one more join. 

 

+----+-------------+-------+----------+----------+---------+------------------+----------+-------------+

| id | select_type | TABLE | type     | KEY      | key_len | ref              | rows     | Extra       |

+----+-------------+-------+----------+----------+---------+------------------+----------+-------------+

|  1 | SIMPLE      | s     | range    | PRIMARY  | 8       | null             | 1882540  | Using where |

+----+-------------+-------+----------+----------+---------+------------------+----------+-------------+

|  1 | SIMPLE      | p     |  eq_ref  | PRIMARY  | 4       | s.productIdn     | 1        | Using index |

+----+-------------+-------+----------+----------+---------+------------------+----------+-------------+

|  1 | SIMPLE      | pg    |  eq_ref  | PRIMARY  | 4       | p.productGroupId | 1        | Using index |

+----+-------------+-------+----------+----------+---------+------------------+----------+-------------+

 

Ok, the denormalized Product table is a larger than the normalized ProductSmall table, but has the productGroupName of the ProductGroup table, removing one of the joins and making the below query a bit faster at 1.1 seconds.  Nothing is substantially different here, but if everything can fit into memory, which this data does, the denormalized data model performs better. 

 

select sum(unit) from Sale s

  join Product p

    on s.productId = p.productId

where purchaseDate >= '2001-12-30';

 

+----+-------------+-------+----------+----------+---------+-------------+----------+-------------+

| id | select_type | TABLE | type     | KEY      | key_len | ref         | rows     | Extra       |

+----+-------------+-------+----------+----------+---------+-------------+----------+-------------+

|  1 | SIMPLE      | s     | range    | PRIMARY  |8        | null        |  1882540 | Using where |

+----+-------------+-------+----------+----------+---------+-------------+----------+-------------+

|  1 | SIMPLE      | p     |  eq_ref  | PRIMARY  | 4       | s.productId | 1        | Using index |

+----+-------------+-------+----------+----------+---------+-------------+----------+-------------+

 

Now to run the same series of tests but with a summary of the productGroupName just to verify the above pattern holds.  In summary, it does. 

Ok, now we know the simple cost of a join, grouping by a value on the joined to table does slow down the sql, but again, this is reasonably fast as 2.2 seconds. 

 

select productGroupName, sum(unit)

  from Sale s

  join ProductSmall p

    on s.productId = p.productSmallId

  join ProductGroup pg

    on p.productGroupId = pg.productGroupId

where purchaseDate >= '2001-12-30'

group by productGroupName

 

+----+-------------+-------+----------+----------+---------+------------------+----------+-------------------+

| id | select_type | TABLE | type     | KEY      | key_len | ref              | rows     | Extra             |

+----+-------------+-------+----------+----------+---------+------------------+----------+-------------------+

|  1 | SIMPLE      | s     | range    | PRIMARY  |8        | null             | 1882540  | Using filesort ...

+----+-------------+-------+----------+----------+---------+------------------+----------+-------------------+

|  1 | SIMPLE      | p     |  eq_ref  | PRIMARY  | 4       | s.productId      | 1        | Using index       |

+----+-------------+-------+----------+----------+---------+------------------+----------+-------------------+

|  1 | SIMPLE      | pg    |  eq_ref  | PRIMARY  | 4       | p.productGroupId | 1        | Using index       |

+----+-------------+-------+----------+----------+---------+------------------+----------+-------------------+

 

The denormalized data model is faster again, but not by much, as 1.8 seconds. 

 

select productGroupName, sum(unit)

  from Sale s

  join Product p

    on s.productId = p.productId

where purchaseDate >= '2001-12-30'

group by productGroupName

 

+----+-------------+-------+----------+----------+---------+-------------+----------+------------------------+

| id | select_type | TABLE | type     | KEY      | key_len | ref         | rows     | Extra                  |

+----+-------------+-------+----------+----------+---------+-------------+----------+------------------------+

|  1 | SIMPLE      | s     | range    | PRIMARY  |8        | null        | 1882540  | Using filesort ... 

+----+-------------+-------+----------+----------+---------+-------------+----------+------------------------+

|  1 | SIMPLE      | p     |  eq_ref  | PRIMARY  | 4       | s.productId | 1        | Using index            |

+----+-------------+-------+----------+----------+---------+-------------+----------+------------------------+

 

Ok, what occurs when the same sql is run against 10,182,566 rows?  If cached, the simple range scan query takes about 4 seconds.

 

select sum(unit)

  from Sale s

where purchaseDate >= '2001-12-01'

 

+----+-------------+-------+-------+----------+---------+------+----------+-------------+

| id | select_type | TABLE | type  | KEY      | key_len | ref  | rows     | Extra       |

+----+-------------+-------+-------+----------+---------+------+----------+-------------+

|  1 | SIMPLE      | s     | range | PRIMARY  | 8       | null | 30931362 | USING WHERE |

+----+-------------+-------+-------+----------+---------+------+----------+-------------+

 

Now, what about a join to the denormalized product table?  This takes 25 seconds, which shows the cost of a table join and a group by over a sequential table scan.  But as all the data can fit into memory the execution times are still reasonably fast. 

 

select productGroupName, sum(unit)

  from Sale s

  join Product p

    on s.productId = p.productId

where purchaseDate >= '2001-12-01'

group by productGroupName

 

+----+-------------+-------+----------+----------+---------+-------------+----------+------------------------+

| id | select_type | TABLE | type     | KEY      | key_len | ref         | rows     | Extra                  |

+----+-------------+-------+----------+----------+---------+-------------+----------+------------------------+

|  1 | SIMPLE      | s     | range    | PRIMARY  |8        | null        | 30931362 | Using filesort ... 

+----+-------------+-------+----------+----------+---------+-------------+----------+------------------------+

|  1 | SIMPLE      | p     |  eq_ref  | PRIMARY  | 4       | s.productId | 1        |                        |

+----+-------------+-------+----------+----------+---------+-------------+----------+------------------------+

 

Once again, the below normalized data is slower than the above normalized version and runs in 33 seconds.

 

select productGroupName, sum(unit)

  from Sale s

  join ProductSmall p

    on s.productId = p.productSmallId

  join ProductGroup pg

    on p.productGroupId = pg.productGroupId

where purchaseDate >= '2001-12-01'

group by productGroupName

 

+----+-------------+-------+----------+----------+---------+------------------+----------+-------------------+

| id | select_type | TABLE | type     | KEY      | key_len | ref              | rows     | Extra             |

+----+-------------+-------+----------+----------+---------+------------------+----------+-------------------+

|  1 | SIMPLE      | s     | range    | PRIMARY  | 8       | null             | 30931362 | Using filesort ...

+----+-------------+-------+----------+----------+---------+------------------+----------+-------------------+

|  1 | SIMPLE      | p     |  eq_ref  | PRIMARY  | 4       | s.productId      | 1        |                   |

+----+-------------+-------+----------+----------+---------+------------------+----------+-------------------+

|  1 | SIMPLE      | pg    |  eq_ref  | PRIMARY  | 4       | p.productGroupId | 1        |                   |

+----+-------------+-------+----------+----------+---------+------------------+----------+-------------------+

 

So far, the case for a denormalized data model, such as a star schema, isn't that robust.  Yes, the performance is better, by only by about 20-30 percent.

But this series of articles isn't finished yet.   In the next blog I’ll show what happens when both the normalized and the denormalized data model struggle to fit into memory.