Bartlett Publishing

Technology Musings / Super Fuzzy Searching on PostgreSQL

JB — Thu, 12 Jan 2012 16:58:00 +0000

I have been working on doing some fuzzy searching on PostgreSQL for a while, and thought I'd share some of my experiences here. Many people are not yet aware of the incredible fuzzy search capabilities of PostgreSQL, especially that were added in the 9.1 release.

Most people use an external engine such as Lucene to do fuzzy searches. While, as you will see, there are still reasons to do so, they are much fewer now than they used to be.

Fuzzy Search Using Trigrams

While PostgreSQL has lots of different fuzzy search options (soundex, levenshtein, etc.), the one which has the most support is trigram searching. What is a trigram? Trigrams break a word up into 3-letter sequences, which can then be used to do similarity matches. Think of the word "hello". It has the following trigrams: "h", "he", "hel", "ell", "llo", "lo", and "o". Now look at the word "hallo". It has the following trigrams: "h", "ha", "hal", "all", "llo", "lo", and "o". You can see that there are several trigrams that match, and several that don't match. Similarity is computed via cosine similarity (which I don't totally understand), but, basically, the more trigrams you have in common the closer the match. In the present case, 'hallo' and 'hello' have a similarity of 0.333333. You can see this in PostgreSQL by saying:

select similarity('hello', 'hallo')

PostgreSQL also has two other relevant operators that use similarity - the "<->" operator and the "%" operator. "<->" is the "distance" operator, which is simply one minus the similarity (i.e. if the similarity is 0.2 the distance will be 0.8). For text searching, "%" is the "similar" operator, which returns true if two strings are similar, or false if they are not. Two strings are defined as "similar" if their similarity is 0.3 or greater. This can be set with set_limit(), but it is not usually useful to do so (we will deal with custom similarities later). The "%" operator is important, because of its heavy use in indexing.

Installing Trigrams

The trigram module (pg_trgm) is not installed by default in PostgreSQL, but is one of their standard (and supported!) extensions. To install, you need to make sure you build the module in the source code. To do this, go into the contrib/pg_trgm directory of the source code and do a "make; make install". This will install the plugin, but will not activate it. Then, in any database you want to use this plugin, put in the command:

CREATE EXTENSION pg_trgm;

This will load the necessary SQL to install the functions and operators needed to make trigrams work. If you type that command in the template1 database, then all future databases created on that system will have the extension installed.

Using Trigrams Without an Index

The simplest use of trigrams would be to have a table with a name column, and do a search like this:

SELECT * FROM people WHERE lastname % 'Schmoe'

This will return a list of people where the trigram similarity is greater than the default threshold. If you want to specify the similarity you are looking for, you can change that to:

SELECT * FROM people WHERE similarity(lastname, 'Schmoe') > 0.5

This will give a less-tolerant match than the default.

The problem with doing this is that it takes a lot of processing power. The reason people usually use databases is because they have a huge number of records and need to be able to search them quickly. If we have 10,000 records, manually doing trigram matches will take quite a bit of time.

So, one of the best features of PostgreSQL 9.1 is the ability for PostgreSQL to incorporate trigrams into an index. So, to make an index to speed up our search, do:

CREATE INDEX people_lastname_trigram_idx ON people USING gist(lastname gist_trgm_ops);

This will create a "gist" index, which is a special type of index which is often used in spacial and other vector-oriented matching. The "gist_trgm_ops" is a little bit of magic that tells gist how to use a text field as a vector of trigrams.

Now, your query will use the index, provided you have enough rows to make it worthwhile. HOWEVER, it is not yet using the index efficiently. While PostgreSQL can (and will) use the index for this query, it doesn't actually check the condition until a later step (I believe, but am not sure, that it is using the index to get everything in the right order, and then at a later stage doing filtering). For large tables, this can still be several orders of magnitude worse than you want. To fix this, you MUST use the "%" operator. This will cause the index to have an "index condition", which it will use to limit the results that it puts out. So, if you have:

SELECT * FROM people WHERE lastname % 'Schmoe';

This will use the index AND the index condition, and will be super-fast (except in extremely large datasets - see next section). However, this uses the built-in cutoff point of 0.3 similarity. What if I want my results to be tighter than that? The best way is to combine % with similarity(), like this:

SELECT * FROM people WHERE lastname % 'Schmoe' AND similarity(lastname, 'Schmoe') > 0.5;

In this case, the database will use the "%" condition for the index, which will be incredibly fast, and the "similarity()" call as a post-index filter, which, since there is a much smaller dataset, will still be pretty fast.

Working With Larger Datasets

I had trouble working with trigrams because my main dataset is about 14 million titles. At this size, trigram searching is really slow. With the whole database loaded in-memory (either in PG's cache or in the filesystem cache - I have many, many gigs of memory), a trigram search of the database USING THE INDEX took between 3 and 12 seconds, depending on the string. Poking around, I came out with the following basic results for a database on an Amazon EC2 4XL instance without any other load:

100,000 records: 40 milliseconds
1,000,000 records: 0.4 seconds
14,000,000 records: 7 seconds

So, as you can see, the useful limit to these queries is about 1 million records. Therefore, if you have more than 14 million rows, if you want to do trigrams, you need to find a way to boost performance. I've found there are two basic methods you can use to speed up trigrams on large datasets:

Create specialized indexes with subsets of your data
Create a separate wordlist table with unique words

#1 is much preferred if you can do it, because it is an entirely database-oriented method. Basically, what I did, is I figured out that on my queries I only needed to trigram search on about 1 million of my 14 million records. Therefore, I specialized the index by adding a "WHERE" clause to the index itself. On my database, I have a "type" field, and I'm only searching certain types of records. Therefore, I changed my index to the following:

CREATE INDEX people_lastname_restricted_trigram_idx ON people USING gist(lastname gist_trgm_ops) WHERE type IN ('my_type1', 'my_type2');

This meant that only about a million records were being stored in the index, which brought down my search time considerably. Another search that I was doing was based on the person's "popularity", in which case, I added another index for popularity being greater than 20. This restricted the set down to about 100,000 records, which made it blazingly fast.

The other alternative (#2) I mentioned is to create a separate table of words which is searched. The idea is that while you may have 14 million records, there probably aren't 14 million words. Therefore, you create a table using unique words from the database, and then add a trigram index on that. The problem, though, is that this takes either (a) a lot of manual work, or (b) a lot of triggers, none of which is the way I like to administer databases. Nonetheless, it can work if you are merely wanting to use trigrams to fuzzy-match individual words. It can be especially helpful in conjunction with PostgreSQL's full-text search (previously known as tsearch2), which still operates blazingly-fast on 14 million records. Fuzzy string matching on words can be combined with full-text search on records to present a powerful and fast method of searching. The wordlist can be fuzzy-matched to provide better hints at what words are in the fulltext.

To create a wordlist, do something like this:

CREATE TABLE search_words (word text);
CREATE INDEX search_words_word_trigram_idx ON search_words USING gist(word gist_trgm_ops);

Then, every time you need to regenerate your wordlist, do the following:

DELETE FROM search_words;
INSERT INTO search_words (word) SELECT DISTINCT lower(word) FROM (SELECT unnest(regexp_split_to_array(lastname, E'\\\\W+')) AS word FROM people) words WHERE word IS NOT NULL AND length(word) > 3;

What that does is explode the lastname field out into words (in case a lastname is multi-word), where each word is its own record. It also filters out excessively short words (optional). It then inserts these into the search_words table, which has a trigram index. So, now, if you want to fuzzy-match individual words, you can use the search_words table!

Anyway, additional fun can be had by using unaccent to remove accents before all of this processing, or other fun to massage your data however you feel is best. The important thing is that, for all but the most strenuous data sets, we can now keep all of the searching located within the database itself, managed by database tools, without having to rely on external search engines such as Lucene, which take time, management, machine power, and their own sets of headaches. Lucene itself often has to be hand-rigged for large datasets even. I am a big believer in pushing as much data work to the database as possible, and PostgreSQL keeps pushing the bar higher!

Technology Musings / Enjoy Skyrim's Alchemy? Check Out Nature's Own Alchemy System

JB — Thu, 22 Dec 2011 23:55:00 +0000

If you have played The Elder Scrolls V: Skyrim, you have probably made use of their "alchemy" system. What you may not have known is that this is based, in some degree, on the real-life practices of both ancient and modern herbalists, who combine herbs and herbal actions to produce desired effects on the body and the body's health.

If you are interested in learning more, you should check out The Herbalist, a new iPhone/iPad/iPod/iOS app which describes a number of herbs and the actions that herbalists use them for. In addition, you can even search the herbal database by the action you are looking for or by the specific malady for which it is often used. It also includes information on different ways of preparing herbs for usage in tinctures, oils, infusions, lotions, and other preparations.

Anyway, if you enjoy Skyrim's alchemy, you'll love seeing how practicing herbalists make use of the same basic ideas.

Notes from the Publisher / New App Available - The Herbalist

JB — Thu, 22 Dec 2011 23:53:00 +0000

Bartlett Publishing just released our first iOS app, called The Herbalist. This app provides information about herbs and how they are used by modern herbalists. It allows searching the herbal database by malady and herbal action. Check it out today!

Simpler Living / Season in Review

Mon, 05 Sep 2011 10:52:00 +0000

This was a bad year for the garden. The heat killed most of my plants, and also prevented me from going outside and weeding.

Here are the results:

Failures:

Tomato (may get a few in the fall - we'll see)
Squash
Cucumber
Rosemary (one potted Rosemary is left, and it doesn't look like it is growing)
Worms - I had a nice worm bin going, but the heat killed them, too!

Almost Failures:

Canteloupe (had 3 good ones, ants took the rest)
Carrots (never got long)
Oregano - have some growing in pots and should do something with it

Successes:

Peas (early in the season)
Green Beans (early in the season)
Sweet Potatoes (I think - haven't dug any up yet)
Lettuce (3 varieties - Romaine, Webb's Wonderful, and Simpson Elite) - had several cuts from each, and now saving the seeds!
Leeks (saved seeds)
Garlic
Mustard Greens
Radishes (though seed-saving was a failure)

Now it's time for fall planting. Planning to plant:

Replanting lettuce from gathered seeds
Kale (Red Winter and Siberian)
Swiss Chard (white and red)
Broccoli (Early Fall Rapini)

I noticed that Amazon sells seeds really cheap ($8/lb for most seeds!) It amazes me that anyone can make money at that price! Seed production simply takes a *lot* of garden time. I wish I had a bigger plot of land to do this on!

I'm also trying growing wheatgrasss without special equipment *or* soil. We'll see how that works.

By the way - my favorite lettuce so far is the first cutting of Simpson Elite. The lettuce seems to get more bitter with each cutting.

Interesting web articles about fall planting:

Researching Creation / Special Creation Research Society Discount for Students

JB — Sat, 03 Sep 2011 04:39:00 +0000

For those interested in joining the Creation Research Society, they are running a special membership drive at a steeply discounted price:

See here

Conservative Theology / A Sermonette in Celebration of Marriage

JB — Sun, 10 Jul 2011 02:29:00 +0000

In this day and age, we often forget what marriage is about. Is it about children? Sex? Loneliness? What? It is this lack of understanding of marriage that leads to so many problems in the family. Therefore, when my brother-in-law asked me to give a sermonette in his wedding to introduce the scripture reading (1 Corinthians 13), I decided to celebrate his marriage by reminding them and everyone about just how important marriage is, and what it is for in the first place. So, here is my sermon. Feel free to use it for your own weddings if you like it:

We are here today to celebrate the marriage of Billy and Stasia. It is worthwhile to take a moment and reflect on this mystical union between man and woman. Aristotle noted that all civilization starts with the natural attraction between husband and wife, which brings them together to form a family, and from the interactions of families, we get towns and cities. Thus we see in Billy and Stasia not only the beginning of their lives together, but the very roots of society spreading further.

Not only is marriage the foundation of society, but it is also the foundation of unity in humanity. The divide between man and woman is the ultimate divide. Races can be mixed. Religions can be syncretized. Cultures can be influenced. But man and woman have been split from the beginning, more distant than any two tribes or nations, and no amount of breeding can ever remove the boundary. It is only through marriage that the two parts of humanity are reunited back into one. And it is marriage as a symbol of unity that gives us all hope for any peace among anyone else.

However, since men and women are so different, sometimes maintaining unity is difficult. God gives us some help in nature by giving us attractions to each other. As Garth Brooks said, "Some times we fight just so we can make up"! While attraction brings us together, it doesn't bond. For that, we need love. Some days choosing to love is easy, and other days it is harder. But we must choose it each and every day, for it is the highest Christian virtue.

Researching Creation / The Doctrine of Creation and the Making of Modern Biology

JB — Tue, 28 Jun 2011 04:24:00 +0000

I just posted a new article on the Classical Conversations website - check it out!

Technology Musings / Misc stuff I found out

JB — Sun, 26 Jun 2011 19:56:00 +0000

Objective-C PostgreSQL stuff:

ObjectivePQ
PostgreSQL For Mac
Postgres-Kit (includes a solution for embedding a PostgreSQL database *in* your app)
pgsqlcocoa
BaseTen

Misc:

Building a shared library on OSX: (see here):

gcc -dynamiclib -install_name /usr/local/lib/libfoo.2.dylib  -compatibility_version 2.4 -current_version 2.4.5 -o libfoo.2.4.5.dylib source.o code.o

I have also seen the options -undefined suppress -flat_namespace here

Another dylib link

Caution mixing shared and archive libs

Seth Godin - how to run a useless conference

Technology Musings / Introducing Newm: An Objective-C Framework for Web Applications

JB — Tue, 21 Jun 2011 11:48:00 +0000

I am working on starting a web application framework called Newm. It is kind of like an Objective-C-on-Rails. Check it out!

Technology Musings / Objective-C Hackery

JB — Sat, 18 Jun 2011 17:55:00 +0000

Been working on several objective-c projects. I love to get into the fun tricks you can do with languages and stuff. Here's some interesting tidbits I found:

Technology Musings / Miscellaneous RFID Links

JB — Tue, 07 Jun 2011 02:47:00 +0000

Learning RFID for a project I'm going to work on soon. Here are some handy dandy links!

Conservative Theology / Dennis Prager vs Perez Hilton on Gay Marriage

JB — Sun, 05 Jun 2011 22:26:00 +0000

A very good and insightful debate. Prager managed to get in some key philosophical points in a short discussion. Most important was the discussion about whether the differences between men and women was a matter of body parts alone, or if there were deeper differences. If there are deeper differences, then there are things which a mother/father can provide which is different not just in degree but in kind which a mother/mother or father/father cannot provide.

Watch Video

Another good, interesting vide:

Watch video

Technology Musings / Ideas 2011-05-25

JB — Wed, 25 May 2011 19:18:00 +0000

Had some thoughts today, thought I'd write them down:

Been looking at Google refine. Some of this is pretty obvious, but I'm thinking it would be pretty awesome to port this to use on a database backend. Basically, do the transforms on the data in the database, and, if you want, it will serialize it back out to a new table, or replace the existing one.

What would also be cool is a generalized report generator for Rails, possibly using AREL. You could do security by defining mandatory filters for tables, limiting the tables/columns, and other things. It could predict the time the report will take to run by using PostgreSQL's "explain" command.

Technology Musings / Database Scaling with PostgreSQL

JB — Tue, 24 May 2011 02:35:00 +0000

I've been digging around on various database scaling options for PostgreSQL. Here's some interesting links I've stumbled upon:

Runtime selection of databases (for selecting between readonly and readwrite databases)
Hot standby in PostgreSQL and log-shipping/streaming (and a tutorial)
A Rails mechanism for sending write requests to a separate server than read requests
Sharding Links:
Gluster

Technology Musings / Getting EC2 Instances to Talk to Each Other

JB — Mon, 23 May 2011 02:02:00 +0000

I am getting started with EC2, and I noticed a problem - I was unable to get my instances to talk to each other - specifically, mounting an NFS drive. After searching through my forums, I found my answer - I was using a custom Security Group.

In the default security group, instances within that security group can talk freely to each other. What is surprising is that the default mode for a custom security group is to prevent all communication between the instances. Therefore, you have to add permissions for the security group to be able to receive incoming traffic from the security group itself. In the "host" line, rather than put an IP address, you can put in a security group ID (i.e. sg-abc123), and then specify 0-65535 for the port range.

Then, viola! It works!

Conservative Theology / Spirituality and Physics

JB — Thu, 19 May 2011 13:07:00 +0000

Some of you might be interested in my new article on physics and faith at Classical Conversations.

Simpler Living / Random (2011-05-18)

Wed, 18 May 2011 18:54:00 +0000

Here's some random stuff open on my browser today:

Technology Musings / Blocks in Objective C

JB — Wed, 18 May 2011 18:51:00 +0000

Blocks is a new feature of Objective C that was announced roughly at the same time as Apple announced Grand Central Dispatch. I haven't had the time to look into it thoroughly, so I'm sticking my bookmarks here for future reference:

Researching Creation / On Being an Amateur

JB — Wed, 18 May 2011 12:54:00 +0000

I'm posting this mainly because I was thinking about it today, and it took me over an hour to find it. So I'm saving it here for future reference. Biblo at Telic Thoughts put up some excellent thoughts about being an amateur ID proponent. I also added the following comment:

I think it is dangerous for any discipline to reject the criticisms of amateurs out-of-hand. I have been programming computers for 25 years, have a book on programming that is used at Princeton University, have taught programming, and have numerous papers and articles on programming published by IBM and others.

Nonetheless, I still, often, have customers who come up with ways of doing things that I don't think of – customers who have never programmed a day in their life. I know many people who dismiss their customers ideas out-of-hand because they don't believe that non-programmers have valid input. That is total B.S. The fact is, being a non-programmer gives someone an outside look at the issues that aren't obscured with all the things us programmers normally worry about that, and sometimes that opens their minds up to possibilities that we don't see.

It doesn't mean that I take their ideas without criticism – there are more bad ones than good ones (which is expected, because they are outside the field, and aren't familiar with the issues). But nonetheless, I would be a lesser developer if I used the fact that these people are non-experts as a reason to dismiss what they had to say.

This also often requires translating what the have to say. Non-experts often use terms wrong, have a bad understanding of the way certain concepts work together, and the like. But *my* job is not to use my expertise as a way of beating their ignorance over their heads, but rather to *translate* their conceptualizations of their ideas into full-fledged, implementable ideas. So, rather than using my expertise to knock down, I use it to build up – to find a way to understand the non-experts in the most gracious light, and find a way for them to be right.

Doing so improves us both.

Simpler Living / Notes from the Garden - 2011/05/14

JB — Sat, 14 May 2011 18:33:00 +0000

I learned several things this year. First, the "days to harvest" on a seed packet seems to be *after* sprouting, but it never explicitly says that. Second, at least in my garden, I need to give the plants another week or two or three after that. Apparently seed packet writers are optimists.

Very little of the tomatoes that I intentionally planted have done anything, except the Silvery Fir Tree tomatoes. A few of them are doing well. We went ahead and bought some tomatoes from The Tomato Man's Daughter. We also have lots of volunteer tomatoes, though I have no idea what variety they are.

The Mizuna lettuce has *already* bolted and gone to flower. It did not get nearly as thick as the package indicated. The package made it look like it might somewhat make a head, but before any major leaf growth we got flowers.

We also got bok choi flowers already. I think that's because the bok choi is supposed to be in a cooler zone. I harvested the non-flowering ones and left the flowering ones for seeds, and planted our purchased tomato plants around them.

The turnips that we planted in the late fall and kept covered with milk jugs through winter are flowering. This might be an easy way to get turnip seeds, and I'm not sure I even need the coverings. This is my first year harvesting turnip seeds (and it was an accident at that), so I'm not quite sure how long I should wait until I harvest the seed pods.

The peas are doing well. They did well unstaked, except that in a high-wind situation, they fell over. I might just add a single stake or two next year so they can grab onto that instead of getting blown over. It doesn't seem to be hindering production, but who knows.

The beans are doing very little.

The leeks from the winter garden look good. I can probably harvest them anytime as I have need for them. I also tasted one of the leaves - yummy!

I pulled up one of our last four garlics from the winter planting. I think they are ready.

The lettuce has been going gangbuster this year. We are eating very well from a variety of lettuces. I have Simpson Elite, which is doing well, a green Romaine lettuce that is doing well, and a mixed Romaine that is doing well. It seems to only take a few days from when you cut the lettuce to when it grows back!

The lettuce I ate over winter has bolted and is about to flower. Yay! Not the best-tasting lettuce, but if you can harvest lettuce three times over the winter, I'd say that the lettuce is worth keeping, no matter what it takes.

I have several sweet potatoes in the ground, and they seem to be doing well, and several more that I need to get in the ground.

I want to do some guerilla-gardening this year, but need to figure out what to plant. Maybe my sweet potatoes would be a good way to guerilla garden.

I've been trying my hand at propagation techniques. I tried to propagate a whole bunch of bush/tree type plants using a rooting hormone. The only ones that successfully rooted were the Rosemary bushes.

My carrots seem to be doing okay, though they are growing very slowly.

When I harvested my radishes, they were kind of small - I think I need to give them a few more weeks. I left three out for seeds, and they got *huge*. We'll see what next year's stuff looks like.

My beets were beautiful in the backyard, so I transplanted them to the front yard. Now they are ugly. Go figure.

My cabbage has started to actually do some growing. It was basically dormant for a while.

I need to get some pepper seeds and see if germinating them late will give me a decent crop at the proper time.

It's looking like I'll need to plant a bunch of stuff in three weeks - I should have my peas and beans in, my lettuce will probably have run its course, and my turnip seeds should be harvested. That will open up more than half the garden for new planting. And, I might have gotten my Leeks harvested, too.