gistfile1.txt

select d_year, s_nation, p_category,
sum(lo_revenue - lo_supplycost) as profit
from lineorder
join dim_date 
  on lo_orderdatekey = d_datekey
join customer
  on lo_custkey = c_customerkey
join supplier
  on lo_suppkey = s_suppkey
join part
  on lo_partkey = p_partkey
where
c_region = 'AMERICA'

and s_region = 'AMERICA'
and (d_year = 1997 or d_year = 1998)
and (p_mfgr = 'MFGR#1'
or p_mfgr = 'MFGR#2')
group by d_year, s_nation, p_category
order by d_year, s_nation, p_category;


+--------+---------------+------------+------------+
| d_year | s_nation      | p_category | profit     |
+--------+---------------+------------+------------+
|   1997 | ARGENTINA     | MFGR#11    | 3404867729 |
|   1997 | ARGENTINA     | MFGR#12    | 3133294310 |
|   1997 | ARGENTINA     | MFGR#13    | 3485519168 |
|   1997 | ARGENTINA     | MFGR#14    | 3450867059 |
|   1997 | ARGENTINA     | MFGR#15    | 3250284809 |
|   1997 | ARGENTINA     | MFGR#21    | 3548212901 |
...
+--------+---------------+------------+------------+
100 rows in set (1 min 2.16 sec)




--------------------------------


<p>About one year ago, I started a project on GitHub called <a href="http://github.com/greenlion/Fastbit_UDF" target="_blank">FastBit_UDF</a> to add a mechanism for creating/manipulating/querying <a href="https://en.wikipedia.org/wiki/Bitmap_index" target="_blank">bitmap indexes</a> in MySQL. MySQL doesn&#39;t have an extensible index mechanism, so it isn&#39;t possible to just simply add bitmap indexes to any of the available storage engines. I worked around this limitation by creating UDF functions that wrap around the FastBit embedded database, making FastBit tables available through functions rather than through a storage engine.

This post details using my FastBit UDFs to manually execute the &quot;star join optimization&quot; process using queries from the <a href="http://www.cs.umb.edu/~poneil/StarSchemaB.PDF" target="_blank">Star Schema Benchmark</a> at scale factor 20 (19.5 million rows in the largest table).


<span style="font-size:1.4em;"><b>Star schema optimization</b></span></p><hr />A star schema is a reporting/BI schema layout <span style="line-height: 19.6px;">(it is a representation of an OLAP cube)</span><span style="line-height: 1.4;"> which is easy to write queries against, but which the database often has difficulties executing in an optimal way. &nbsp;Queries over a star schema because filtering is most often done in the dimension tables and rarely in the fact table. &nbsp;This means that joins have to be processed before filtering. &nbsp;MySQL only supports nested loops, and only supports single threaded queries, two factors which limit the performance of a star schema in MySQL.

<b>What is the star schema optimization strategy?</b>
The most common form of star schema optimization is to <i>scan<b> dimension tables</b> first, </i>accumulating a list of <i>primary key values</i> from the dimension tables which can then be used to filter the keys against a <i>bitmap index</i> on the <b><i>fact </i></b>table. &nbsp;Of course, the MySQL optimizer can&#39;t do these things because it doesn&#39;t have optimizer support for such an execution strategy, or bitmap indexes to support the strategy. &nbsp;But with an external bitmap index the end user can manually perform these steps for vastly improved query performance.</span><p>You can find the DDL for the <i>star schema benchmark</i> <a href="https://raw.githubusercontent.com/greenlion/swanhart-tools/master/shard-query/tools/ssb/ssb_schema.sql" target="_blank">here</a>.

I am going to use <b>query 4.1 </b>of the SSB to demonstrate star schema optimization:</p>
<pre>
<b>select </b>d_year, s_nation, p_category,
<b>sum</b>(lo_revenue - lo_supplycost) as profit
<b>from </b>lineorder
<b>join </b>dim_date 
  <b>on </b>lo_orderdatekey = d_datekey
<b>join </b>customer
  <b>o</b>n lo_custkey = c_customerkey
<b>join </b>supplier
  <b>on </b>lo_suppkey = s_suppkey
<b>join </b>part
  <b>on </b>lo_partkey = p_partkey
<b>where</b>
c_region = &#39;AMERICA&#39;
<b>and </b>s_region = &#39;AMERICA&#39;
<b>and </b>(d_year = 1997 or d_year = 1998)
<b>and </b>(p_mfgr = &#39;MFGR#1&#39;
<b>or </b>p_mfgr = &#39;MFGR#2&#39;)
<b>group by</b> d_year, s_nation, p_category
<b>order by</b> d_year, s_nation, p_category;
</pre>


The query uses the fact table and all four dimension tables of the benchmark. &nbsp;The query executes in just over 1 minute on my test machine:
<pre>
+--------+---------------+------------+------------+
| d_year | s_nation      | p_category | profit     |
+--------+---------------+------------+------------+
|   1997 | ARGENTINA     | MFGR#11    | 3404867729 |
|   1997 | ARGENTINA     | MFGR#12    | 3133294310 |
|   1997 | ARGENTINA     | MFGR#13    | 3485519168 |
|   1997 | ARGENTINA     | MFGR#14    | 3450867059 |
|   1997 | ARGENTINA     | MFGR#15    | 3250284809 |
|   1997 | ARGENTINA     | MFGR#21    | 3548212901 |
...
+--------+---------------+------------+------------+
100 rows in set (1 min 2.16 sec)
</pre>


<p><b style="font-size: 1.4em; line-height: 1.4;">Setting up the Fastbit UDFs</b></p><hr /><p><span style="line-height: 1.4;">Setting up the Fastbit UDF functions is fairly straightforward. &nbsp;You will need a C++ 11 compatible compiler (I test with GCC 5.3), and the MySQL C headers. &nbsp;After you clone the repository simply use run </span><b style="line-height: 1.4;">make</b><span style="line-height: 1.4;">. &nbsp;FastBit will automatically download and compile, and the UDF will be built after that. &nbsp;Use </span><b style="line-height: 1.4;">make install</b><span style="line-height: 1.4;"> to copy the shared libraries to the mysql plugin directory.

Finally run </span><b style="line-height: 1.4;">install.sql </b><span style="line-height: 1.4;">to install the UDF functions into the database.

<b>Create a &quot;data directory&quot; for FastBit:</b>
The FastBit indexes should must be maintained somewhere on disk. &nbsp;I generally choose to use <b>/var/lib/fastbit </b>for the FastBit indexes.</span></p>
<pre>
<i>sudo mkdir /var/lib/fastbit
sudo chown -R mysql:mysql /var/lib/fastbit
</i>
</pre>


<span style="font-size:1.4em;"><b>Using the UDF to index data</b></span><hr />
<b>Create a FastBit index to support the query:</b>
For this demonstration, I added a AUTO_INCREMENT primary key column to the <i>LINEORDER </i>table. &nbsp;This column will be used to fetch rows from the fact table quickly, after dimension table filtering is done.

The <b>fb_create </b>UDF is used to create FastBit indexes. &nbsp;The first column is the full path to the index on disk. &nbsp;It should be created in the FastBit data directory created above. &nbsp;The second option are five columns from the fact table, the primary key of the fact table , and the primary keys from each of the other four tables:

&nbsp;&nbsp;select<b> fb_create</b>(<i>&#39;/var/lib/fastbit/lo_idx&#39;</i>, <i>&#39;lo_id:int,custkey:int,partkey:int,suppkey:int,orderdatekey int&#39;</i>);

The above command should return <i>zero</i>. &nbsp;This means that the index creation was successful.

<b>Populate the index with the data from the fact table:</b>
<pre>

select fb_insert2(&#39;/var/lib/fastbit/lo_idx&#39;, lo_id, lo_custkey, lo_partkey, lo_suppkey, lo_orderdatekey) 
| 1 | 19526339 |
1 row in set (1 min 15.58 sec)
</pre>

<b>fb_insert </b>is an aggregate function for high performance loading of data into a fastbit index without using an intermediary table.  The first argument is the path to the index, and each additional argument is a column of data to load into the index, of course in the order of columns as they are are found in the index.  The COUNT(*) provides a count of records loaded into the index.

<b>Verify the count of rows in the index:</b>
<pre>
call fastbit.fb_helper('/var/lib/fastbit/lo_idx','test','tmp','select count(*)',1,1);
+----------+
| count(*) |
+----------+
| 19526339 |
+----------+
1 row in set (0.01 sec)

Query OK, 0 rows affected (0.02 sec)
</pre>

The fb_helper stored routine is a wrapper around the query functions for FastBit.  It automates the creation and usage of a temporary file and temporary table to hold the results.  The first option is the index to use, the second the schema in which to store the temporary table, the third the temporary table name to use, the fourth the actual query to fastbit (note that a FROM clause is not used), the fifth is one to drop the temporary table when completed, and the sixth determines if a resultset is returned.