Using PostgreSQL for an Ajax Autocomplete Field

I recently implemented an Ajax based autocomplete field for a web application using a PostgreSQL database on the back-end. I had trouble finding appropriate PostgreSQL queries, so I’ve decided to share my approach in the hope that it will be useful to others.

Data Format

The application uses the following PostgreSQL table to store the author data:

CREATE TABLE authors (
authors_id serial PRIMARY KEY,
author_name character varying UNIQUE NOT NULL
);

The author_name field represents the full name of an author. E.g. ‘jane austen’, ‘john smith’, ‘john q. public’, ‘william shakespeare’, etc.

Client Side JavaScript

On the client side, the application uses the jQuery UI Autocomplete widget.(http://jqueryui.com/demos/autocomplete/) jQuery is a great library and if you’re creating dynamic web pages and not using it, you really should be. However, jQuery has been well documented so I’m not going to discuss the details of the client side implementation. Additionally, the back-end code is general enough that it should work with other JavaScript libraries with minimal modifications. Essentially, when the user begins typing, the jQuery UI Autocomplete widget makes a get request to the server with the text the user entered and expects the server to respond with a json object containing the results to show the user.

Initial Implementation

Creating the initial version of the autocomplete field was relatively straightforward. To handle the Ajax we simply added the following method to our controller:

use JSON;
sub json_author_search : Local
{
my ( $self, $c, $dashboards_id ) = @_;
my $term = $c->req->param( 'term' ) || 0;
$term = '%' . $term . '%';
my $terms =
$c->dbis->query( "select authors_id, author_name as label from authors where author_name ilike ? ", $term )->hashes;
$c->res->body( encode_json( $terms ) );
return;
}

This code was fully functional and worked with small data sets on a development machine. However, once we started testing on our production machine with a large dataset, it became clear that there were performance problems.

Using an explain showed that PostgreSQL was doing a sequential scan. I.e. it was reading through the entire database table for every query:

mediacloud=# explain select authors_id, author_name as label from authors where author_name ilike '%bla%';
QUERY PLAN
---------------------------------------------------------
Seq Scan on authors (cost=0.00..37.33 rows=1 width=22)
Filter: ((author_name)::text ~~* '%bla%'::text)
(2 rows)

Possible Solutions

I did some web searches looking for a solution. I found Nikolay Samokhvalov’s slides on Using PostgresSQL In Web 2.0 Applications. http://www.scribd.com/doc/4844027/Using-…)
These slides have useful information and are worth reading. However, their suggested approaches focus on key word search rather than autocomplete. The first approach that Samokhvalov gives is to use prefix search. This solution uses like ‘bla%’ queries and relies on text_pattern_ops indexes for quick performance. Samokhvalov’s other tip is to use lower instead of using ilike. So in our case we would add the following index:

CREATE INDEX author_name_prefix ON authors USING btree ( lower (author_name) text_pattern_ops);

and change our search query to:

$term = ‘%’ . $term;
$c->dbis->query( "select authors_id, author_name as label from authors where lower(author_name) like ? ", $term )->hashes;

This approach is fast but it doesn’t give us the behavior that we wanted. For example, if the user typed ‘sm’, we would want ‘john smith’ to be included in the search results. However, “john smith” would only be matched if the user instead typed ‘jo’.

Another solution that Samkhvalov suggests is using GIN indexes with full text search. This is an interesting approach but it didn’t seem like the right fit for an autocomplete service. As far as I was able to determine, PostgreSQL’s full text search is only designed to match entire words so ‘sm’ would not match ‘smith’. Finally Samkhvalov suggests an interesting hybrid approach that uses both prefix search and full text search with GIN indexes. This approach relies on having a separate table that contains all the distinct words in every string in the table that’s being searched. So in our case we would have an author words table that contained words such as ‘alice’,’bob’,’brown’,’david’,’smith’,etc. This approach might work well for relatively static data — creating the initial table of distinct words is easy. However, in our data set we are constantly adding new author strings. I wanted to avoid the additional complexity of managing and updating an author words table.

My Solution

I added the following indexes to the authors table:

create index authors_name_varchar_pattern on authors(lower(author_name) varchar_pattern_ops);
create index authors_name_varchar_pattern_1 on authors(lower(split_part(author_name, ' ', 1)) varchar_pattern_ops);
create index authors_name_varchar_pattern_2 on authors(lower(split_part(author_name, ' ', 2)) varchar_pattern_ops);
create index authors_name_varchar_pattern_3 on authors(lower(split_part(author_name, ' ', 3)) varchar_pattern_ops);

Then I changed the query to:

$term = $term . '%';
my $terms =
$c->dbis->query( "select authors_id, author_name as label from authors where lower(author_name) like lower(?) OR " .
" lower(split_part(author_name, ' ', 1)) like lower(?) OR " .
" lower(split_part(author_name, ' ', 2)) like lower(?) OR " .
" lower(split_part(author_name, ' ', 3)) like lower(?) LIMIT 100 ",
$term, $term, $term, $term )->hashes

The above query performs prefix searches on each of the first three words within the author name string. Additionally, it performs a prefix search on the entire author name string. We OR these prefix searches so that we return the results that match any of the prefix searches. The nice thing about this search is that the user can start typing either the first name or the last name (or the middle name). For example, when the user starts typing ‘joh’, they’ll get a list that includes the ‘john’ names. When the user starts typing ‘smi’, they’ll get a list that includes the ‘smith’ names. Because we also do a prefix search on the entire string, the user could start typing ‘john’ to get a list of names starting with ‘john’ and then expand that to ‘john sm’ to get a list of ‘john smith’s and similar names.

(Note: it might have been safe to omit lower(split_part(author_name, ' ', 1)) like lower(?) from the query since it will often be redundant with lower(author_name) like lower(?). We decided to leave it in place to enhance readability and out of concern that it may be necessary to handle improperly formatted author strings.)

Conclusion

This approach does have its weakness. It won’t work for names involving more than 3 words. Fortunately those names are rare. It would also have been nice to be able to do full wild card searches such as like ‘%bla%’. Unfortunately, PostgreSQL does not have any index to optimize those types of searches.

In an ideal world, the database would have a set of indexes and operators that would perfectly handle the search queries necessary for autocomplete and abstract them away from the programmer. However, I’ve presented a solution that has performed well for me and has added only a minimal amount of complexity to the code and the database schema. I’d love to hear comments or suggestions for alternate approaches.

Why I left Windows Mobile

A Personal Perspective on Microsoft’s Mobile Phone Failure

Microsoft’s Windows Mobile (WM) was an early leader in smart phone and mobile devices but has largely been eclipsed by other players. For the last two years, it has been all but irrelevant in the mobile phone space. The iPhone, Android, RIM, and Palm have all generated significantly more excitement in the press and user communities. Largely because of legacy installs, WM does more respectably when you look at the percentage of phones running each OS. However, it is clearly being overtaken by others as shown by new phone sales. In terms of mind share, the press has been more focused on iPhone, Android, and to a lesser extent RIM and Palm’s webOS. Among my friends and colleagues, I see a similar trend: the technoliterati and technophobes alike are ignoring WM as they happily flash their new iPhones and Androids. In October of this year, Microsoft released Windows 7 Mobile in an attempt to recapture its lead.

I have not used or studied Windows 7 Mobile. So I won’t try to evaluate it. (Note: If anyone wants to give me a Windows 7 phone, I’ll happily test it and review it in this blog.)  However, products as complicated as operating systems are often difficult to accurately evaluate before sufficient time has passed from their initial release. For example, although Windows Vista is now nearly universally considered junk, it initially received many positive reviews. So rather than talk about the Windows 7 Mobile, I hope to provide a personal historical perspective on why WM has been a failure so far. I’m going to describe my experiences as someone who used earlier versions of Windows Mobile for nearly 5 years and finally became disillusioned enough to leave the platform.

Note: This post is based on a series of notes that I took in late 2009 after I switched away from Windows Mobile. I intended to blog my experience then but various events intervened. I feel that the recent release of Windows Mobile 7 provides an interesting opportunity for a look back on prior versions and decided to update and finish this post. While flushing out and expanding my original notes, I’ve tried to maintain the flavor and freshness of the original where possible.

About myself

I’m a software professional and largely a Linux user. I used Windows Mobile for nearly 5 years and owned two separate phones. I still believe that at the time I bought the phones they were the best choices for me but they were clearly flawed devices. Those who defend Windows Mobile often point out that there are tweaks and work arounds for many of its shortcomings. I spent days if not weeks of my life fiddling with these phones. I read howardforum.com and xda-developers.  I tweaked registry settings and installed custom roms.  This certainly helped but at the end of the day, these phones were still deeply unsatisfactory.

Motorola MPx220: My first Windows Mobile Device

I bought the Motorola MPx220 in January of 2005. I paid $300+ before rebate.  Prior to that phone I had a simple Samsung monochrome phone.

Why I chose the phone

I wanted a phone that still felt like a phone. The MPx220 had a small form factor as a flip phone. Price was also a consideration. Touch screen PDA phones were around $600 in those days. The phone ran Windows Mobile 5 for Smart Phones(WM5).

Advantages

Compared to standard cell phones of the time, the MPx220 was relatively open.  It had a mini SD slot for storage expansion and could be connected to a computer through USB. This meant that I didn’t have to pay what I would call “sucker” fees.  For example, I still can’t believe people used to pay to get pictures off their phones. With the MPx220, it was possible to extract pictures simply by hooking it up to a computer through USB.  It was also possible to add ring tones simply by copying an mp3 or midi file into the appropriate directory.

Overall Opinion

The MPx220 showed me the promise of an open mobile computing device but utterly failed to achieve it.  The software included with the phone was frustratingly limited. For example, the voice recorder did not have a pause function – something that would have been trivial to add. The UI felt unnecessarily complex.  It seemed designed to mimic Windows XP rather than to provide the best user experience. Indeed the UI on my old Samsung felt much more intuitive. There were few third party applications available and they were pricey. Finding and installing apps was a hassle. Much to my annoyance, I found out that Windows Mobile and Windows Mobile for Smart Phone were different and incompatible OSs. Though I’m sure there was an acceptable technical justification for having two separate OSs, there is no justification for such confusingly similar names.

Other limitations resulted from the hardware.  Since the phone only had a number pad, entering text was a hassle. This effectively made it a read only phone. Also the camera wasn’t great (around 1.3 MP). The MPx220 could play music and there was even a third part application that could play OGG files.  However, because the phone didn’t have a standard head phone jack an adaptor was required. I occasionally used the MPx220 for pod casts but much to my disappointment it did not become an MP3 player replacement for me.

My next phone: the HTC Tilt

I used the MPx220 until 2008. My contract had expired but the phone worked and I didn’t find anything else that was super exciting so I hung onto the MPx220.  Then the phone started having problems.  The hinge for the flip top had come loose. I jerry-rigged the phone back together using a plastic pen cap and kept using it.  Then the screen stopped working.  It was finally time to get a new phone.  There had been news stories about the Openmoko phone. I was intrigued by it but a usable version still wasn’t available. A release date had been set for fall of 2007, then pushed back to December 2007, then pushed back again.  It was spring of 2008 and I needed a phone and Openmoko was starting to seem like vaporware.  The original iPhone had come out the previous summer but I decided against it.  At the time there were no third party apps on the iPhone. Since I had music in OGG format, this meant there was no way to play it. Also the 1st gen iPhone hardware seemed limited — it was only 2G and it didn’t have a keyboard.  The iPhone was also pricey $399  http://blogs.law.harvard.edu/dlarochelle…). So I went with the HTC Tilt also called the HTC Kaiser. Hardware-wise the Tilt was superior to the iPhone.  Among other things, it had 3G and GPS. Several of my coworkers had the phone and they were happy with it.  I was able to find a refurbished Tilt that was free after rebate with a two year contract.

My experience with the Tilt.

The Tilt ran Windows Mobile 6(WM6) and had a touch screen and slide out keyboard. The phone initially came pre-loaded with a bunch of crap-ware.  But early on I reflashed the phone with a custom rom from XDA developers.  This got rid of the pre-installed junk and greatly improved the interface.  The Tilt did a great job syncing with the Exchange server at work.

One annoyance was that interfacing with the phone required Microsoft products.  Rather than allowing the phone to appear as a mass storage device, you needed to use ActiveSync to access it. Not only did this mean that you needed to have ActiveSync installed, but that copying files to the device was somewhat convoluted.  Though the phone’s file system shows up in My Computer and Explorer, it wasn’t a real directory.  There is no drive letter and copying to and from the phone is slower than with a real file system.  Also even when the phone is attached to a computer, you can only copy files back and forth. There is no way to use the computer to directly edit a file stored on the phone. For example, suppose that you have a text file on your phone that you want to edit and you’d like to use a computer because, well, editing on a computer is easier. Instead of just connecting the phone to the computer, finding the file, and then opening and editing it, you would need to copy the file from the phone to the computer, make your edits, and then copy the file back.

Additionally, you need Outlook to sync your contacts and calendar. I happened to have Outlook because it was included with the MPx220.  But the Tilt did not include Outlook. Without Outlook the phone would have been nearly useless. Existing contacts would have needed to have been  re-entered into the phone manually — a tedious process even on a phone with a qwerty keyboard. Furthermore, Outlook was necessary to backup calendar and contact data.  With a smart phone backups are vital and not just because they will protect you in disaster. If you don’t have backups, you won’t trust the phone. If you don’t trust the phone, you won’t put your data on it. And the whole point of a smart phone is to have access to all your important data at anytime.

Email

Although the phone worked beautifully with Exchange, it was less useful for POP3 and IMAP. POP3 wasn’t designed for mobile devices so I don’t fault the phone. However, the IMAP support was inexcusably buggy. In the fall of 2008, I begun using IMAP for both home and work email. I noticed that while the phone could receive messages, it couldn’t send them. Sometimes, I could get around the problem by deleting and re-adding email accounts, but the problem would soon return. As you might imagine being able to receive messages but not send them was frustrating to put it mildly. (There were a few times when I actually used the phone’s browser to send very urgent emails but that was tedious.) Finally, Microsoft released a fix for the bug. I don’t know exactly how long the bug existed but it was at least months. This issue would have been obvious to anyone who used IMAP for a significant period of time. IMAP seems to have been viewed by Microsoft as a check box feature rather than something they actually cared about enough to get right. It also speaks very poorly of Microsoft’s QA practices that the bug was not caught prior to release and existed so long in the wild.

Other Thoughts

The Tilt was my first Internet connected mobile device and it definitely enhanced my life. In addition to email, it was nice being able to see the weather report and to Google something when I was out to lunch. Google Maps was a great feature and although it didn’t do turn-by-turn voice guided car navigation, it was great for getting basic directions or finding places on foot.

The Internet connection made installing apps easier since no computer was required but it was still a hassle. The process of finding apps using the phone was painful enough that you were probably better off just using a computer to at least find the application if not to download it. A number of vendors would actually text links that you could open on your phone to download the application. There was no app store so finding apps from the phone involved using the mobile version of Internet Explorer to Google for the app.

Microsoft makes some improvements

In mid-2009, Window Mobile 6.5 became available. The update helped somewhat but didn’t really address the limitations mentioned above.  Then in the fall of 2009 Microsoft finally announced its own app store. However, the app store while long overdue was fairly limited.

Google and Windows Mobile

Looking back it is ironic that Google of all people did the most to add value to the Windows Mobile experience. As mentioned above, Google Maps is one of the killer applications.  (In fairness the same could be said about the iPhone.) Another very useful app from Google was the YouTube player.

Windows Mobile’s email support for anything other than Microsoft Exchange is abysmal. Google eventually added sync support for Windows Mobile using the exchange protocol and suddenly users of Gmail were able to get significantly more value from their phones. (However, WM only supported a single Exchange account.  So if you needed to use Exchange for work email, you won’t be able to also take advantage of Gmail’s Exchange support.)

Android

I’d been curious about Android for a while. The Tilt is very similar to the G1. Both phones are made by HTC and have essentially the same form factor. Since Android is Open Source, people had been trying to port it to the Tilt since before Android was released. Their efforts reached some fruition in the fall of 2009 and I was able to get Android running. The result was usable but not stable.  It required a hard reset about once a day. Still it gave me a chance to try Android and I concluded that it was better than Windows Mobile.

Why I liked Android Better

The Android interface and UI just felt cleaner and more polished. Among other things, the Chrome browser on Android was better than IE on WM. The Gmail integration on Android was much better — in particular, archive worked. The app store on Android had more and better apps than WM.  Adding an app store to WM was a huge improvement, however the WM app store was new while Android’s had been around for over a year and the WM store just didn’t have the breadth of apps that Android did. Additionally, there were apps such as Google Voice apps that weren’t available on Windows mobile.

Android also didn’t require anything like ActiveSync. You simply connected the phone to the computer, and then you could mount the file system like a flash drive. Indeed, I’ve used the phone as a flash drive to exchange files. The nice thing is this will work on any computer not just those few that have ActiveSync installed. Imagine the different between saying to someone  “Just hook my phone up to your computer and then we’ll copy the file onto it” vs. “I need you to download and install ActiveSync. Then we’ll hook up the phone but we need to make sure the phone doesn’t sync with your Outlook. Then we can copy the files to the phone. After that you’ll probably want to uninstall ActiveSync since you won’t need it anymore.”

Dropping WM

After tasting Android, I didn’t want to go back to Windows Mobile. At the same time, the hacked port of Android running on the Tilt was not stable enough to rely on. I could have tried to tweak Android so that it would run better on the Tilt but I decided that I didn’t have the time. Instead, I sold the Tilt on Craigslist and used the money to partially purchase a used G1. The G1 cost more than I sold the Tilt for and I also had to pay to unlock the Tilt. So my out of pocket cost was around $50 but it was well worth it.

Since switching to Android, I haven’t looked back. Shortly after switching to Android, I wrote that although I had used Windows Mobile for nearly 5 years “the Windows Mobile is dead to me and is essentially dead in the market place.”  I have no idea whether the recent release of Windows 7 Mobile will somehow enable the OS to magically rise again like a phoenix (or a zombie).  However, I have attempted to convey my experience as a user who gave Windows Mobile a fair try but found it wanting. In so doing, I hope I have provided some insight into what Microsoft could have done differently to maintain its lead in the mobile space.