Technology Musings

My Beef with Model Validators in Rails

JB — Thu, 09 May 2013 15:06:00 +0000

When I first started using Rails, it was a dream come true. I estimate that I reduced the amount of code I was writing by 60-75%. This is probably still true. However, as I've gotten to know the platform better, there are some philosophical issues that I have with Rails. Sometimes it is more the Rails community and its conventions rather than rails itself, but nonetheless, it continually manifests itself.

My current beef - validators! Having written lots and lots of code that interacts with lots and lots of systems, I have to say that you should never, ever, ever put in model validators. Ever. Validation is a process issue, not a data one. In theory it should be a data issue, but it never ever works out that way.

Here's what happens. Let's say I have a telephone number validator for a model. It makes sure the numbers are in the format (918) 245-2234. If not, it gives a nice error message. However, now let's connect that same model to an external system. Let's now say that the author of the external system was not as picky about phone number formats. What happens now? Well, every record that gets migrated from that system that isn't formatted according to your desires will now get kicked out! And it might not even show up during testing! In addition, your pretty error messages mean practically nothing on system->system communication. So, what you have is the system randomly breaking down.

This causes even more problems in long-term maintenance. I've had many bugs pop up because someone added a validator that broke several processes. It worked in all of their tests, but they weren't thinking about all of the ways the system was used. For instance, we decided to lock down the characters used in our usernames a little more. The programmer decided to implement it as a validator. Well, the problem is that several users already had usernames that didn't match the validator. So what happened? Those records just stopped saving. Not just when there was someone who was at the terminal, where they could see the error message, but every job started erroring out because of users who had faulty names.

Because of these issues, I *always* do validation in my controller, and *never* in the model. It is true that there are probably workarounds for all of these issues, but the point is that they are *not* that exceptional! They are everywhere! What would be nice is to have validators which could be run optionally, in specific situations. So, a controller could declare that it was using :data_entry validations, and then the model would only run those validators. So, it would look something like this:

In the model:

validates_presence_of :email, :for => [:data_entry]

In the controller:

uses_validators :data_entry

One of the issues I have found with dynamic languages such as ruby is that errors arise when "magic" is sprinkled in unexpected places. Ruby magic is awesome, but when I do something simple and it won't save, it is sometimes hard to even locate where the error is. Explicitly declaring which validator set you are using allows programmers to more easily see what they are doing, and only apply magic code where it goes.

Someday I'll write a package like this --- when I get extra time :)

Tue, 07 May 2013 20:02:00 +0000

Why the tabs-vs-spaces debate matters:

Inconsistent indentation: 2 spaces were used for indentation, but the rest of the document was indented using 1 tab.

Everyone - indent with tabs. Then you can control the indentation using your editor's settings. DO NOT indent with spaces. And DO NOT use any programming language or configuration system that cares about indentation.

A Review of Several Nerf and Nerf-Like Guns

JB — Sun, 07 Oct 2012 02:23:00 +0000

Usually I don't splurge on things like Nurf guns, but our family was challenged to a dual, and I decided we needed to load up. The kids had been saving money, so they all got to purchase their own gun, and so my only purchase was for my own. Anyway, I thought I'd post what everyone bought and a short review of each of them. Here's what we bought:

Buzz Bee RADS 12 (amazon) (top left)
Buzz Bee Double-Barrel Shotgun (amazon) (middle)
Nerf Vortex Proton (here is a similar gun on amazon) (top right)
Buzz Bee Tek-3 (3-pack) (amazon) (bottom middle left)
Nerf N-Strike Elite Retaliator (amazon) (bottom)

Below is a picture of all of the guns:

We bought these at Target, and none of them cost more than $25. In fact, most of them were $10 or less.

The gun with the most "cool factor" was the Nerf Retaliator. This gun is modular and therefore can actually be transformed into four different styles below:

If you remove the stock and the barrel, you get a very nice basic gun similar to a Skorpion (bottom right). If you have a stock without a barrel, you get a gun very reminiscent of a UMP45. If you have a barrel but no stock, it looks a bit like an MP5. With all of the attachments, it could be really any assault rifle, but it most reminds me of an M4 or FAL. Now, I should point out, this is pretty much all for show - I didn't detect any advantage of having a barrel attached - but it looks pretty intimidating nonetheless.

The Retaliator fires well, and with a long range , but is *very* erratic. In our battle with our friends, I'm not sure I hit *anyone* with this gun. It is mega-cool, and shoots pretty far, but don't count on actually hitting anything.

The gun that actually shot the best was the Vortex Proton - and I think it only cost $9. The Proton is one of Nerf's new disc-firing guns. The disks are Nerf disks so they don't hurt. However, the disks are *very* aerodynamic, so they actually fly straight! The Vortex is a single shot, and it takes a little bit to load, but nonetheless I had the best success with it because it was so accurate! I could be sure to know that the disk would fly exactly to where I aimed it! The only drawback, as I said, was that it was a single-shot, and didn't even have a spot to hold additional ammo. So, reloading was problematic because it took time, and fumbling around with ammo was difficult. I think if you got a multi-shot version of this you would have an amazing gun!

Another good gun is the Buzz Bee RADS 12. This is a twelve-shot gun that you pull back on a lever to cock it. It shoots decently and doesn't cost very much. Overall I would say that it is a decent purchase, but my 5-year-old was the one to purchase it, and it took too much hand strength to cock the gun. He could do it, but only if he held it on the ground with one hand and pulled with the other - not very helpful in a gun battle.

The worst gun was the Buzz Bee double-barrel shotgun. This was not worth buying. Here are the problems with the gun:

It takes a *lot* of effor to load the gun. You have to pull it apart really hard, and it is not always clear when it is fully cocked (pulling it apart is what cocks it)
The bullets have to be loaded into "shells" (to make it more realistic). This is just a hassle. My son likes this, but it is unhelpful.
The shells eject when you pull apart the gun. Again, this aims for realism, but doesn't help during a battle, and is just more pieces to get lost. In fact, in this case, they actually seem to be actively trying to get lost.
It only holds two shots. This seems pretty obvious for a double-barrel shotgun, but the fact that it takes so long to load makes this really problematic.
It doesn't shoot very far. It's moderately accurate, but, really, it has an effective range of about 6-12 feet.

Anyway, my 6-year-old likes it because of the "realism", but I think that if we do too many more battles, he will realize the problems with the gun.

The next gun is the Buzz Bee Tek-3. This is a tiny gun with three shots. However, it does not auto-rotate the barrel. Between shots, you must BOTH cock the gun AND rotate the barrel. However, for a tiny gun, it packs a decent punch and is relatively easy to use. At Target, they had a 3-pack for $6. That's right, 3 guns for $6. It makes a good backup weapon (like a boot gun).

Also in the picture is an older Nerf gun that we already had - I believe it is a Nerf Dart Tag Strikefire. This is an old gun, but still shoots decently. It is a single-shot, muzzle-loaded pistol, but also has holding spots for five additional rounds. This original came with Nerf Dart Tag darts, but I think it can fire most anything. It works really well as a simple, basic gun.

Anyway, if you are looking for Nurf or Nurf-like guns, I hope this review was helpful to you!

Rails, CoffeeScript, and Java

JB — Mon, 01 Oct 2012 20:32:00 +0000

I *hate* the direction that Rails is moving. It is becoming a bloated piece of garbage. I got into Rails precisely because Rails got out of my way most of the time, but was easy to use right where I needed it. ActiveRecord was a thin shell over SQL. Therefore, if there was a problem, I could easily diagnose it, because I knew SQL. It added a few bits of magic, but those were usually pretty understandable. Likewise with the javascript helpers and the like. If you needed something done, just pop into Javascript and patch it up.

This contrasted heavily with J2EE. I used J2EE for a while, but it turns out that if you want to use J2EE you have to commit to it like it's a religion. If you don't know 20 different platform libraries, you can't even do a hello world in J2EE. When you finally get it working, you don't know what the heck is even going on. Some magic is happening somewhere, but it is beyond what is plainly visible. This, and the fact that Ruby is very metaprogramming-ish, was the reason I chose Rails.

However, starting with Rails 3, the Rails team decided that it was simply going to do everything for you, and everything was going to be done in domain-specific languages. Thus, instead of the required list of languages/platforms being Ruby/Rails/SQL/Javascript, it has balooned out to Ruby/Rails/SQL/Javascript/Coffeescript/SASS/ECO/Node.js, and probably a few others I'm forgetting. The asset pipeline is kind of cool, but it's yet another place for things to go wrong. I think the anti-CSS measure of auto-h()ing code is terrible. If you wanted to go that way, instead you should use Perl's taint feature, and just give errors if you display tainted values. The idea that random code should transform my strings is horrible.

Finally, I understand the reason for getting rid of the javascripty stuff from rails core, but some of those were really what made the platform really rock. I think they have missed the mark - they put the ease-of-use in the wrong places, and instead have made sure that no one that doesn't have a relgious commitment to the software stack will ever find it usable. It has basically gone the way of J2EE, and I am now looking for a new platform to love.

Today's Thoughts on Algorithmic Information Theory

JB — Sun, 23 Sep 2012 04:55:00 +0000

I know this won't make a lot of sense to most people, but I thought I needed to store these thoughts in a more permanent place before I forget them. I've been reading a paper today on Algorithmic Information Theory, and it make me think these thoughts (most of which are probably ill-founded):

Is the Chaitin halting probability really a probability? In other words, if I have the first 5 bits of omega, does this mean that a random sampling of all programs will really match this value to some extent?
To what extent is self-delimiting programs an intrinsic part of AIT, vs just a cheap trick to get the math right? It makes sense simply because you need the program length. But on the other hand, if omega is a probability, it seems like having the program length pre-coded would do a number on its interpretation as a probability.
If log2(2^w) is w, is perhaps log2(w) = c? Is c the complexity number I'm looking for for my axioms?
Is it possible to express the idea of a formal relationship to be the relationship between the algorithmic specification and its logical depth? I.e. we should expect a material cause when logical depth is low, but a formal one when logical depth is high? Could this be expressed as a ratio?
Algorithmic complexity on partial specifications. The word "red", as implemented in 12 pt font or written in the clouds. Perhaps the partial specification is something that can be detected non-algorithmically, via an Oracle machine? In other words, instead of "give me the Xth object that matches specification X, you say, give me *an* object that matches specification X. It does not require an iteration over the whole of infinity, but a potentially large part of it very quickly. Or, perhaps, it drops it a level of Cantorian infinity.
Recognizers vs generators = P/NP problem = logical depth vs algorithmic complexity
What is the relationship between the constant given in AIT vs expressibility of language? In other words, if C is small, then it is easier to express random strings, at the penalty of having no easily expressible strings. A larger C will permit more compressibility. This might also be usable, at least in theory, to determine the total number of "special" strings available.
How can algorithmic information theory be expanded for programs that take arguments? (note - number of arguments shouldn't matter, only whether one of them is itself a program, perhaps? or if the result is a program? Maybe what the Wolfram class of the argument is?)
Might semantics and apobetics be higher Turing degrees?
Might ethical norms be an expression of compressibility across Turing degrees?
What about bad plans? Is it possible to state, even in abstract, non-determinable terms, what a bad plan is?

Autoreleased with No Pool in Place

JB — Wed, 15 Aug 2012 18:54:00 +0000

Before Apple's ARC, you would often have to manage memory semi-manually. Before operation queues, you would also have to manage setting up autorelease pools on new threads. If you didn't, you would get an error such as:

autoreleased with no pool in place - just leaking - break on objc_autoreleaseNoPool() to debug

However, the other day, I started getting these myself! I was a little shocked - what on earth was I doing that required an autorelease pool? Well, eventually I figured it out. It turns out that if you have custom +load() functions on your classes (these get called whenever the classes load - I use them for registering handlers and such), this is another situation in which you have to set up your own autorelease pool if you do any object creation.

So, in your +load() function (or, depending on what you are doing, in functions that +load calls), just wrap it with

@autoreleasepool {
     Your Code Here
}

And it works!

Simple Sage Plots for Teaching Functions

JB — Sun, 05 Aug 2012 02:09:00 +0000

I'm teaching calculus to some homeschool students this year, and I wanted to have a bunch of function plots printed out to show them. Therefore, I turned to Sage, which I have never used. It is great! You have to know a few other math software pieces to really understand it, but it's not that bad. Someone needs to do a general "how to use sage", and some day I might.

Anyway, here's my quick function for plotting graphs for students that some of you might like.

In one of the evaluation boxes, type the following:

def simpleplot(f, range=(-5,5,-5,5)):
  p = plot(f, (x, range[0], range[1]))
  p += text("$" + latex(f) + "$", (0, range[2] - (range[3] - range[2]) * 0.1), fontsize=30, rgbcolor=(1,0,0))
  p.axes_range(range[0], range[1], range[2], range[3])
  show(p, figsize=12)

What this does is create a function called "simpleplot" which will do the following:

Plot the given function on a default domain of -5, 5
Typeset the function using LaTeX, and insert the function slightly below the graph (I calculated it at 10% of the graph size). It prints in red at 30 point size.
Set the axes to be -5, 5, -5, 5 (I used uniform axes on all the functions so they can compare the differences between graphs easier)
Draw the whole thing at 3x the normal size (figsize=12 - default is 4).

Now, I can just do:

simpleplot(1/x)

And it gives me my output!

DVD Rescue! Getting files off of an unfinalized DVD

JB — Mon, 23 Jul 2012 02:44:00 +0000

Just wanted to shout out and say thanks to Flay for saving me! I had a DVD that I forgot to finalize, but Flay had a nice set of instructions for how to manually copy off the files from the DVD drive.

Now I can finish editing and posting the videos for the Engineering and Metaphysics conference.

iOS Bug - insertNewObjectForEntityName: deleteObject and rollback

JB — Fri, 13 Jul 2012 16:39:00 +0000

I've been chasing down a wierd bug where, on an NSManagedObjectContext, the hasChanges method keeps returning YES even after a rollback. It turns out, if you do the following sequence, hasChanges will *never* be cleared:

MyClass *c = [NSEntityDescription insertNewObjectForEntityName:@"MyClass" inContext:ctx];
//Do other stuff
[ctx deleteObject:c];
// Do other stuff
[ctx rollback];
[ctx hasChanges]; // Returns YES!

In my own case, I got around it by not deleting the object, and just rolling back if I wanted it gone, but that won't work for everyone. So, I did:

MyClass *c = [NSEntityDescription insertNewObjectForEntityName:@"MyClass" inContext:ctx];
//Do other stuff
[ctx rollback]; // Don't delete! just roll back
//Do other stuff
[ctx rollback]; // Now it works
[ctx hasChanges]; // Returns NO like it should

Why I Won't Be Participating in StackOverflow.com Anymore

JB — Sat, 12 May 2012 03:56:00 +0000

I have historically been grateful for stackoverflow.com, but I think that perhaps they may be getting overly full of themselves and self-conscious.

I have long used their site to get answers, especially to iOS questions. It always seems that someone answers any question I might have. I've always wanted to give back, but found that nearly every questions someone else has already answered.

So the other day I was trying to figure something out, and the answer on StackOverflow was that it was not possible. I spent a day messing around, and actually figured out how to do it (read about it here). So, having spent most of the morning trying to find if anyone had accomplished this, I actually found three different StackOverflow.com questions pertaining to it, as well as several sites on the Internet. So what did I do? I decided the best way to let people know about the answer was to write a blog post about it, and then point people to the blog to find the answer in each question. This was going to be my way of giving back.

So what happened? Well, two of my comments got deleted from StackOverflow, and one had a comment from a moderator attached accusing me of self-promotion!!!! Because I solved a problem that had been outstanding for a year, and told people the answer!!!!

So, in the future, I will just post to my blog, and leave StackOverflow out of it. You can come here for the answers. I don't have enough brain space to deal with that kind of junk.

Engineering and Metaphysics 2012 Conference

JB — Thu, 10 May 2012 21:16:00 +0000

For those interested in engineering and theology and philosophy, this conference is for you! I've got two talks slated for the conference - come and listen! Lots of fascinating stuff from a number of disciplines:

www.eandm2012.com

You can see the abstract list here and the conference flyer here.

iOS - using storyboard relationships for custom view controller containment

JB — Thu, 10 May 2012 20:51:00 +0000

One thing that iOS forgot to do with the release of storyboards and iOS 5 is support for custom "relationship" segues. In addition to normal segues, UINavigationController and UITabBarController have what are called "relationships", which allow you to define containment information for these controllers. So, for the navigation controller, you define the root view controller, and for the tab bar controller, you define the list of view controllers. This is all done in a neat interface in the storyboard editor (which is the replacement for interface builder).

Another cool feature in iOS is "containment", which is basically a way of letting you write view controllers which contain other view controllers. This was not really allowed in iOS 4, but they've added some basic support for it. Unfortunately, the way that you might want to use containment with storyboarding is through relationships, but iOS doesn't provide a way to do custom relationships in storyboards - or even their default ones on custom view controllers.

My own task was to create a tab bar controller with the tabs at the *top*. I had a few ideas on how I might approach this problem. Subclassing UITabBarController didn't seem like a good idea. So I tried several others.

One possible way was duck typing. I thought that perhaps I could pull a fast on on the storyboard editor. What I would do is define my own class that mimicked UITabBarController without actually inheriting from it. Then, I could create my relationships with the storyboard editor, and then substitute my own non-tab-bar controller at the last minute. This failed miserably.

Firts of all, the storyboard editor doesn't like you to substitute non-subclasses for the class that it wants. If you try to set it to a non-subclass of UITabBarController, it won't give you an error, but it won't save the change, either.

I tried to work around this by making my class inherit from UITabBarController while I was editing the storyboard, and then change it back for the compile. This worked momentarily, but in the end, it turns out that the "relationship" segues aren't set via getters and setters. I imagine there is an internal API that is being used.

Therefore, I next tried overriding initWithCoder and reading the nib values myself. Unfortunately, I was not successful at guessing the keys for decoding.

Then, it hit me. What I need to do is to mix subclassing UITabBarController with not mixing UITabBarController. So here's what I did:

class 1: MyTabBarController

This is just a shell class, but it inherits from UITabBarController.

class 2: MyTabBarControllerImplementation

This is your real implementation class, and only needs to inherit from UIViewController. Make it work like you want it to.

What you are going to do is designate your tab bar controllers to be of type MyTabBarController in the storyboard editor. Then, when viewDidLoad is called on MyTabBarController, the view controller de-registers the view controllers from itself, creates an instance of MyTabBarControllerImplementation, moves the view controllers over there, and then replaces itself with MyTabBarControllerImplementation.

Anyway, here's the code. It's really rough, but works at the moment. I'm open to improvements:

MyTabBarController.h:

#import <UIKit/UIKit.h>
@interface MyTabBarController : UITabBarController
@end

MyTabBarController.m:

#import "MyTabBarController.h"
#import "MyTabBarControllerImplementation.h"
@implementation JBTabController
- (void)viewDidLoad
{
    [super viewDidLoad];
    JBTestContainerViewController *vc = [[JBTestContainerViewController alloc] init];
    NSArray *vclist = self.viewControllers;
    [self setViewControllers:[NSArray array] animated:NO];
    vc.viewControllers = vclist;
    NSMutableArray *navlist = [self.navigationController.viewControllers mutableCopy];
    [navlist replaceObjectAtIndex:(navlist.count - 1) withObject:vc];    
    [self.navigationController setViewControllers:navlist animated:NO];
}
@end

MyTabBarControllerImplementation.h:

#import <UIKit/UIKit.h>
@interface MyTabBarControllerImplementation : UIViewController<UITabBarDelegate>
@property (nonatomic) int selectedIndex;
@property (strong, nonatomic) NSArray *viewControllers;
@property (strong, nonatomic) UITabBar *bar;
@end

MyTabBarControllerImplementation.m:

#import "MyTabBarControllerImplementation.h"
@implementation MyTabBarControllerImplementation
@synthesize viewControllers = _viewControllers;
@synthesize selectedIndex = _selectedIndex;
@synthesize bar = _bar;
-(CGRect) subviewFrame {
    CGRect f = self.view.frame;
    return CGRectMake(0, 30, f.size.width, f.size.height - 30);
}
-(void) reloadBarInfo {
    NSMutableArray *itms = [NSMutableArray arrayWithCapacity:_viewControllers.count];
    for(UIViewController *vc in _viewControllers) {
        UITabBarItem *itm = [[UITabBarItem alloc] initWithTitle:vc.title image:nil tag:0];
        [itms addObject:itm];
        [vc didMoveToParentViewController:self];
    }
    _bar.items = itms;    
    _bar.selectedItem = [itms objectAtIndex:0];
    _bar.autoresizingMask = UIViewAutoresizingFlexibleWidth;
    UIViewController *firstVC = [_viewControllers objectAtIndex:0];
    firstVC.view.frame = [self subviewFrame];
    firstVC.view.autoresizingMask = UIViewAutoresizingFlexibleWidth | UIViewAutoresizingFlexibleHeight;
    [self.view addSubview:firstVC.view];
}
-(void) viewDidLoad {
    self.bar = [[UITabBar alloc] initWithFrame:CGRectMake(0, 0, self.view.frame.size.width, 30) ];
    for(UIViewController *vc in _viewControllers) {
        [self addChildViewController:vc];
    }
    _bar.delegate = self;
    [self.view addSubview:_bar];
    [self reloadBarInfo];
}
-(void) tabBar:(UITabBar *)tabBar didSelectItem:(UITabBarItem *)item {
    int idx = [_bar.items indexOfObject:item];
    UIViewController *newVC = [_viewControllers objectAtIndex:idx];
    UIViewController *curVC = [_viewControllers objectAtIndex:_selectedIndex];
    if(newVC == curVC) {
        return; // Don't switch - same one selected!
    }
    [curVC.view removeFromSuperview];
    newVC.view.frame = [self subviewFrame];
    newVC.view.autoresizingMask = UIViewAutoresizingFlexibleWidth | UIViewAutoresizingFlexibleHeight;
    [self.view addSubview:newVC.view];
    [self transitionFromViewController:curVC toViewController:newVC duration:0 options:0 animations:nil completion:nil];
     self.selectedIndex = idx;
}
@end

And there you have it!

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