Inverse Lookup in Key-Value Storage: avoid disk seeks

[Luiz Gonzales]

Dear all,

I wanted to implement a very simple key-value store on top of mysql, from String to Integer, *with* somehow efficient inverse lookup capabilities.

My (naive) approach was to use a simple table with two columns (KEY, VALUE), a uniqueness contraint on KEY, an index on VALUE (and a REPLACE INTO as an update function for loading the data).

I have several millions of strings and a inverse lookup from VALUES to KEYS takes a long time (order of 100 seconds), i.e. a simple "SELECT KEY FROM TABLE WHERE VALUE=?". Since I have an index, I assume that most of the time is spent on disk seeks. And actually, I think that my data is "well distributed" over the values, so that might be one supporting explanation.

I also tried to create one table for each possible value (0 ... 1000) .. but then the loading time totally goes beyond all repair (create file, open file, close file etc..).

Do you have any suggestion on how to find a MySQL-specific solution for my problem? I really think that I am dealing with a very fundamental problem, but I could not find anything using search.

Best regards,
Luiz



Edited 2 time(s). Last edit at 07/13/2011 07:16AM by Luiz Gonzales.