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.