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!

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.

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

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!

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:

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!

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.

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

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!

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:

Using Indexes on LIKE queries on PostgreSQL

JB — Wed, 11 May 2011 15:25:00 +0000

Apparently, under some configurations (I think they are compile settings dealing with the locale), PostgreSQL will not, by default, use an index for LIKE queries. First of all, note that PostgreSQL will NEVER use an index for an ILIKE query (case-insensitive like). For that, you should use a functional index using the LOWER function. It will also not use an index if the LIKE starts with a wildcard. But, for queries that *end* in a wildcard, if you set it up right, you can get PostgreSQL to use an index.

Anyway, apparently the problem is that PostgreSQL doesn't know what locale it is in, and therefore doesn't know how to order the characters. Therefore, you have to give it some help. After your index column, you need to add text_pattern_ops. So, for my own table, I did the following:

create index entity_lower_name_idx on entities(lower(name) text_pattern_ops)

And viola! Postgres is now using the index. Since this is a functional index, it indexes queries like

select * from entities where lower(name) like 'hello%'

Hope that helps someone! I received the information here and here.

Making Reusable iPhone Widgets with Interface Builder

JB — Thu, 05 May 2011 15:10:00 +0000

One annoying thing about Interface Builder, at least for the iPhone, is that there is not a direct way of making reusable widgets that are both made *in* Interface Builder and *for* Interface Builder. I came up, though, with a set of instructions and helpers that make the process fairly painless. The class is called IBView, and should be used as the parent class for your reusable widget.

Here's how to create the widget:

Create a class for your new widget, called MyWidget. Inherit from the IBView class (code provided below). Create all of the IBOutlets you want for your widget.
Create a view with the same name as your widget class in Interface Builder. If your widget was named "MyWidget.m" then your interface should be called "MyWidget.xib". DO NOT set the class of this view or any subview to be of the MyWidget (or whatever class you are create) type. DO NOT do it.
Set the "File's Owner" of your interface in Interface Builder to be the name of the class that you are creating - MyWidget in this case.
Set up any connections you want between your IB view and File's Owner (i.e. your widget).

Now, your widget is created. You can now use the view in any IB panel by doing putting in a generic UIView, and setting the class name to your new class (MyWidget in this case).

Important caveat - one consequence of creating the view in Interface Builder is that there will be an extra view between the main view represented by your class and the rest of the elements of your class. Basically, your custom view acts as a generic view, and then *loads in* your Interface Builder file as a subview, meaning that the toplevel view in Interface Builder will sit under your MyWidget view. This is usually unimportant if you are just using IBOutlet stuff, but if you do advanced view management, it would be important to know that a view sits between you and the rest of your sub-widgets.

Okay, here is the code for IBView.m - just very simple code, with a tiny bit of Objective-C magic thrown in:

#import "IBView.h"

@implementation IBView

-(void) loadViewsFromBundle {
	NSString *class_name = NSStringFromClass([self class]);
	NSLog(@"Loading bundle: %@", class_name);
	UIView *mainSubView = [[[NSBundle mainBundle] loadNibNamed:class_name owner:self options:nil] lastObject];
	[self addSubview:mainSubView];
}

-(id) initWithCoder:(NSCoder *)coder {
	self = [super initWithCoder:coder];
	if(self) {
		[self loadViewsFromBundle];
	}
	return self;
}

- (id)initWithFrame:(CGRect)frame {
    self = [super initWithFrame:frame];
    if (self) {
		[self loadViewsFromBundle];
        // Initialization code.
    }
    return self;
}

@end

And IBView.h is super-simple:

#import <UIKit/UIKit.h>
@interface IBView : UIView {
}
@end

And that's all there is to it!

Readings around the Web

JB — Mon, 02 May 2011 04:19:00 +0000

Here's a collection of links that I have open. Just putting them here so I can close them :)

Fixing Clicking Hard Drives

Wed, 09 Feb 2011 17:10:00 +0000

All right - my wife's computer died today. It gave the Apple folder-with-a-question-mark sign which says it can't find the system software. Booting from the install disk - I found out that it couldn't even find the drive.

In addition to that, the hard drive was making clicking sounds when the computer first turned on.

I was certain that the computer was fried.

However, I dug through a bunch of forums. Most of them agreed - if your hard drive makes a clicking noises, then it is probably dead. I ran through all of Apple's troubleshooting steps - nothing. It seemed that it was truly dead.

Then, at the bottom of a forum post, a poster named "deepika" gave an amazing piece of advice. I thought it was a joke when I first read it. But, since the hard drive was probably dead anyway, I felt it couldn't hurt. The advice? It seems that the drive is having trouble spinning up. Therefore, you have to "convince" it to spin up. How?

Turn off the computer
Put the computer on a flat surface
Close the computer (it's a laptop)
Bang on it a few times

Seriously.

And guess what? When I turned on my wife's computer again - it worked!

Opening other apps from the iPhone

JB — Fri, 10 Dec 2010 22:27:00 +0000

I was looking into how to open another app from the current app today, and came across these posts which look interesting:

Anyway, an interesting list for anyone trying to do this.

Bundler is Evil

JB — Mon, 06 Dec 2010 19:55:00 +0000

If anyone is thinking about using the Bundler plugin for ruby-on-rails for *any* reason, DON'T!!!!!!!!!

I have lost probably 5-6 hours just messing around with bundler trying to get it to work consistently. Unfortunately, a fairly decent library, formtastic, requires it, for some reason I really don't understand. Anyway, I've lost hours of sleep and work time trying to mess with bundler. So, for all of you wondering if this will be worthwhile - beware!!! It just eats up your time and sanity with no real payoff.

It is especially evil if you are trying to manage dependencies for the same app running on multiple boxes, which, in theory, that's the problem it is trying to solve.

TO UNINSTALL BUNDLER

Amazingly, there is NOTHING AT ALL in the documentation to tell you how to uninstall bundler. How nice.

Here's what I found out:

1) Remove config/preinitializer.rb

2) Bundler adds a function at the bottom of config/boot.rb. It looks something like this:

class Rails::Boot
  def run
    load_initializer

    Rails::Initializer.class_eval do
      def load_gems
        @bundler_loaded ||= Bundler.require :default, Rails.env
      end
    end

    Rails::Initializer.run(:set_load_path)
  end
end

Get rid of that function.

3) Bundler should now be gone! You can remove the gem, now, too. I'll let you know if I find any other vestiges of bundler laying around.

And, it looks like formtastic still works after you remove bundler. So if you must use formtastic, maybe you should use bundler to install it, and then remove bundler to use it.

Model Rocket Stuff

JB — Fri, 03 Dec 2010 16:25:00 +0000

Playing around with model rockets this week. I found that you could use crepe paper (or even cellulose wall insulation) for recovery wadding, and that loctite at walmart was a decent substitute for plastic cement. There's also a link to make your own fire-resistant wadding here, but it looks like you have to pay for the content.

Also, while looking around, I found that someone even came up with a method of making homemade engines (also other sites here, here, and here - that last link also has info on homemade fireworks)! That's pretty cool, but I don't think I'm ready for it yet. Also a link for homemade igniters.

Anyway, I think the only part of that I'm brave enough to try is using crepe paper for recovery wadding, but the rest sure is interesting!

When XCode Won't Symbolicate your Crash Log

Wed, 06 Oct 2010 22:18:00 +0000

On the iPhone, when you get crash logs, XCode is supposed to automatically look up symbols for you. Sometimes, it doesn't. Just had a crash report from the app store. Loaded it up in the XCode organizer, and... nothing. Zilch. A lot of posts on the internet talked about "atos" but I just kept on getting the error:

atos cannot load symbols for the file

So, thankfully, I found this page on manually symbolicating your file. Yay!

Basically, you can just run gdb on your archived package, set some configs, and then do p/a on the addresses and it will give you the proper symbols, files, and line numbers. Magic!

/Developer/Platforms/iPhoneOS.platform/Developer/usr/libexec/gdb/gdb-arm-apple-darwin YOURFILE.app
set print asm-demangle on
set print symbol-filename on
p/a 0x0whatever

Thanks so much to PiC Software for pointing this out. And, of course, yay to the gcc and gdb developers who never get the credit that they should.

Why to Not Use Dreamhost for Important Sites

JB — Wed, 29 Sep 2010 05:13:00 +0000

I host one of my sites on Dreamhost. Dreamhost is very alluring, because of the number of features you get for almost no money at all. The problem is, Dreamhost has the right to pull the rug out from under you with no warning.

I had spent hours trying to get my rails app to work under Dreamhost. I had frozen Rails, specified which version of Rack to use, and a number of other tweaks. Then, today, I go there, and I get the dreaded "Passenger Error". I logged in, and tried to change some settings, and got nothing. However, I noticed that the error message continued to display the same line numbers even though I had changed the file. Wierd.

So I keep messing with it, and even start deleting files. The errors *still* pop up, no matter which files I delete - it keeps the same filenames and line numbers even though the files no longer exist. I had assumed that it just wasn't restarting, and maybe it had cached the files. So I went looking for a force-restart thingy on the Dreamhost panel.

I didn't find one, but I found something else - Dreamhost had, without so much as an email saying so, moved me to a completely different server! They left the files on the old server, but my domain was no longer pointed there. Surprise! I had been working on the wrong server altogether!

So, once I logged into the correct server, I was able to delete my frozen version of Rails, and unset my Rack preferences, and all was well with the world. But who in the world switches apps to a box with a different configuration without notifying the customer!

If you want to know why you shouldn't buy webhosting for $5/month, this is it.

I'll probably still keep my account, but I'll stick with only having very-low-profile domains there.

Change in Video Playback in iOS 4 (MPMoviePlayerController)

JB — Sat, 18 Sep 2010 00:52:00 +0000

It seems that Apple has changed the way that it handles video playback in iOS 4. In previous iPhone OS releases, you merely initialized the movie player instance and then hit play. iOS 4 is slightly more complicated because it no longer presumes that all video playback will be fullscreen, or even that there will only be one video on the screen at a time. So here is the code to get the old behavior:

MPMoviePlayerController* thePlayer = [[MPMoviePlayerController alloc] initWithContentURL: [NSURL URLWithString: trailerURL]];
thePlayer.scalingMode = MPMovieScalingModeAspectFill;
thePlayer.view.frame = self.view.bounds;
[self.view addSubview: thePlayer.view];[thePlayer setFullscreen: YES animated: YES];

Unfortunately, Apple still keeps its old documentation around. Here are the updated docs.

I ran into this when I was updating an app from 3.0 to 4.0. When you clicked on the button to play the video, rather than playing a video, nothing happened, and then a few seconds later only the audio would start playing. I had listed in my code the URL for the docs from Apple which I had used, and verified that it was correct - I had no idea that the document itself was out-of-date! It was quite a problem for me, and at first I thought it was a bug in my code. Later I learned that Apple updated their API, but not all their docs. Anyway, hope this helps someone.