Swift RESAR Project Part 5

My last blog post presented the performance results for RESAR Swift using MySQL. I will now analyze why this approach has such dismal performance results.

Poor RESAR Swift Performance Explained

You will remember that for a cloud cluster of 1 million devices, database construction time was (on average) 0.12 seconds for a single device and reliability group. It required over 34 hours to create the entire database of 1 million devices and 1 million reliability groups.

In addition, the minimum query time was 0.000272622203333 seconds and the maximum was 0.00045933403 seconds. We sincerely hoped that this database creation time was excessive and that the second RESAR Swift approach would greatly improve database performance.

We were highly motivated to pursue the second RESAR Swift approach. That is, focus on performance and thus be willing to write new code. So we needed to create a new kind of database that was optimized for database construction.

OLTP Relational Databases

OnLine Transaction Processing (OLTP) commonly uses relational databases to perform transactions. Manny relational databases are implemented as star schema databases. A star schema is optimized to minimize string space – all string attributes are stored in separate dimension tables. Each dimension table is sorted to optimize query performance. Dimension table insertion time thus depends on the table size and is O(log n) where n is the number of records in a table. Star schema insertion time then, is the sum of all dimension table insert times O(sum(log ni) for 1 << ni << l) where l is the number of attributes in the database and ni is the number of values for attribute i.
The following is the RESAR star schema:

    1. MetaData
    1. Disklet –> Device
    1. ReliabilityGroupsDisklets –> ReliabilityGroup
    1. –> Device
    1. –> Disklet

The MetaData Table is a stand alone fact table in that it does not contain external references nor is it externally referenced. The fact tables are Disklet and ReliabilityGroupsDisklets. The Disklet Table references the Device Table. The ReliabilityGroupsDisklets Table is the most complicated and thus most interesting in that it references multiple tables: ReliabilityGroup, Device, Disklet. This schema thus shows that the dimension tables in the RESAR star schema are: ReliabilityGroup, Device, Disklet. But these dimension tables are NOT typical star schema string dimensions. They are in fact complex data structures. This would seem to indicate that string manipulation was not the cause of poor dimension table performance.

The Problem Lies with Indexing

So what was causing the poor insertion performance? We theorized that the problem lies in how database attributes are indexed. Essentially all of the tables needed some of the attributes to be indexed so that query performance was reasonable. For example, a common query on the Device Table would be finding all devices supported by a given HostName. Or finding the entry for a given HostName and DeviceName. In MySQL, index tables are B-trees. Index table insertion time thus depends on the table size and is O(log n) where n is the number of entries in a table. We felt that this insertion time could be minimized by the judicious use of hashing. We thus had the theoretical motivation to persue a new type of database.

So we think that we understand why RESAR Swift MySQL has such poor performance. The next blog will present a new approach.