How to reduce the size of an sqlite3 database for

Question

edit: many thanks for all the answers. Here are the results after applying the optimisations so far:

• Switching to sorting the characters and run length encoding - new DB size 42M
• Dropping the indexes on the booleans - new DB size 33M

The really nice part is this hasn't required any changes in the iphone code

I have an iphone application with a large dictionary held in sqlite format (read only). I'm looking for ideas to reduce the size of the DB file, which is currently very large.

Here is the number of entries and resulting size of the sqlite DB:

franks-macbook:DictionaryMaker frank$ ls -lh dictionary.db
-rw-r--r--  1 frank  staff    59M  8 Oct 23:08 dictionary.db
franks-macbook:DictionaryMaker frank$ wc -l dictionary.txt
  453154 dictionary.txt

...an average of about 135 bytes per entry.

Here is my DB schema:

create table words (word text primary key, sowpods boolean, twl boolean, signature text)
create index sowpods_idx on words(sowpods)
create index twl_idx on words(twl)
create index signature_idx on words(signature)

Here is some sample data:

photoengrave|1|1|10002011000001210101010000
photoengraved|1|1|10012011000001210101010000
photoengraver|1|1|10002011000001210201010000
photoengravers|1|1|10002011000001210211010000
photoengraves|1|1|10002011000001210111010000
photoengraving|1|1|10001021100002210101010000

The last field represents the letter frequencies for anagram retrieval (each position is in the range 0..9). The two booleans represent sub dictionaries.

I need to do queries such as:

select signature from words where word = 'foo'
select word from words where signature = '10001021100002210101010000' order by word asc
select word from words where word like 'foo' order by word asc
select word from words where word = 'foo' and (sowpods='1' or twl='1')

One idea I have is to encode the letter frequencies more efficiently, e.g. binary encode them as a blob (perhaps with RLE as there are many zeros?). Any ideas for how best to achieve this, or other ideas to reduce the size? I am building the DB in ruby, and reading it on the phone in objective C.

Also is there any way to get stats on the DB so I can see what is using the most space?

Answer 1

mhmm... an iPhone... doesn't it have a permanent data connection ? I think this is where a webapplication/webservice can jump in snugly. Move most of your business logic to the webserver (he's gonna have real SQL with FTS and looooots of memory) and fetch that info online to the client on the device.

Answer 2

Remove the indexes on sowpods and twl -- they are probably not helping your query times and are definitely taking lots of space.

You can get stats on the database using sqlite3_analyzer from the SQLite downloads page.

Answer 3

I'm not clear on all the use cases for the signature field but it seems like storing an alphabetized version of the word instead would be beneficial.

Answer 4

Your best bet is to use compression, which unfortunately SQLite does not support natively at this point. Luckily, someone took the time to develop a compression extension for it which could be what you need.

Otherwise I'd recommend storing your data mostly in compressed format and uncompressing on the fly.

Answer 5

As a totally different approach, you could try using a bloom filter instead of a comprehensive database. Basically, a bloom filter consists of a bunch of hash functions, each of which is associated with a bitfield. For each legal word, each hash function is evaluated, and the corresponding bit in the corresponding bit field is set. Drawback is it's theoretically possible to get false positives, but those can be minimized/practically eliminated with enough hashes. Plus side is a huge space savings.

Answer 6

As noted storing "Signature" more efficiently seems like a good idea.

However, it also seems like you could gain a ton of space savings by using some kind of lookup table for words - since you seem to be taking a root word and then appending "er", "ed", "es", etc why not have a column with a numeric ID that references a root word from a separate lookup table, and then a separate column with a numeric ID that references a table of common word suffixes that would be appended to the base word.

If there were any tricks around storing shorthand versions of signatures for multiple entries with a single root word, you could also employ those to reduce the size of stored signatures (not sure what algorithm is producing those values)

This also seems to make a lot of sense to me as you have the "word" column as a primary key, but do not even index it - just create a separate numeric column that is the primary ID for the table.