mozStorage uses sqlite as the database backend. It has generally good performance for a small embedded database. However, many things case various database operations to be slow.
Many times careful reordering of the SQL statement or creating the proper indices can give much better performance. See the
See the sqlite optimizer overview on the sqlite web site for information on how sqlite uses indices and executes statements.
You might also want to try to analyze your sql commands to see if they are using the indices you expect.