Sometimes replace MYSQL 5.0 "Inner Join" with PHP Array
21 Mar, 2011
The idea begins when I see hash index is only for MEMORY/HEAP/NDB, and PHP array is a simple hash table.
Sometimes, we use MYSQL to store enumerable values. However, it is not that easy to change available values for these fields. Instead, we create another table to store those availables values, assign an index for each, store their indexes in the previously described data table, and create foreign key for them.
As a result, when we are using the data, we may write something like:
select `otherValues`,`choice_value` from `table_data` inner join `table_choice` on `table_data`.`choice_id`=`table_choice`.`id`;
Here we are using "Inner Join". According to the description of available index type in MYSQL (can be found at http://dev.mysql.com/doc/refman/5.0/en/create-index.html), hash index is only for MEMORY/HEAP/NDB! Assume the size of table_data is N, and size of table_choice is L, the complexity should be O(N*Log(L)), and the data transfered should be O(N).
And here is another idea: replace "Inner Join" with PHP Array. In this way, we send the whole table_choice to PHP to create array. The complexity should be O(L), and the data transfered should be O(L). Then the required data from table_data is transfered to PHP. The complexity should be O(N), and the data transfered should be O(N). After that, PHP will search for each choice_value from the created array according to `table_data`.`choice_id`. Each search will cost O(1) operations since PHP array performs as a hash table, so the total complexity of search is O(N).
In conclusion, if we replace "Inner Join" with PHP Array, the total data transfer will increase from O(N) to O(N+L), but the total operations will decrease from O(N*Log(L)) to O(N+L). The prerequest is that MYSQL does NOT provide hash index for table_choice.