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\u2019ve decided to share my approach in the hope that it will be useful to others.<\/p>\n
The application uses the following PostgreSQL table to store the author data:<\/p>\n
The author_name field represents the full name of an author. E.g. \u2018jane austen\u2019, \u2018john smith\u2019, \u2018john q. public\u2019, \u2018william shakespeare\u2019, etc.<\/p>\n On the client side, the application uses the jQuery UI Autocomplete widget.(http:\/\/jqueryui.com\/demos\/autocomplete\/<\/a>) jQuery is a great library and if you\u2019re creating dynamic web pages and not using it, you really should be. However, jQuery has been well documented so I\u2019m 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.<\/p>\n Creating the initial version of the autocomplete field was relatively straightforward. To handle the Ajax we simply added the following method to our controller:<\/p>\n 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.<\/p>\n Using an explain showed that PostgreSQL was doing a sequential scan. I.e. it was reading through the entire database table for every query:<\/p>\n I did some web searches looking for a solution. I found Nikolay Samokhvalov\u2019s slides on Using PostgresSQL In Web 2.0 Applications.(http:\/\/www.scribd.com\/doc\/4844027\/Using-PostgreSQL-In-Web-20-Applications-) and change our search query to:<\/p>\n This approach is fast but it doesn\u2019t give us the behavior that we wanted. For example, if the user typed \u2018sm\u2019, we would want \u2018john smith\u2019 to be included in the search results. However, \u201cjohn smith\u201d would only be matched if the user instead typed \u2018jo\u2019.<\/p>\n Another solution that Samkhvalov suggests is using GIN indexes with full text search. This is an interesting approach but it didn\u2019t seem like the right fit for an autocomplete service. As far as I was able to determine, PostgreSQL\u2019s full text search is only designed to match entire words so \u2018sm\u2019 would not match \u2018smith\u2019. 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\u2019s being searched. So in our case we would have an author words table that contained words such as \u2018alice\u2019,\u2019bob\u2019,\u2019brown\u2019,\u2019david\u2019,\u2019smith\u2019,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.<\/p>\n I added the following indexes to the authors table:<\/p>\n Then I changed the query to:<\/p>\n 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 \u2018joh\u2019, they\u2019ll get a list that includes the \u2018john\u2019 names. When the user starts typing \u2018smi\u2019, they\u2019ll get a list that includes the \u2018smith\u2019 names. Because we also do a prefix search on the entire string, the user could start typing \u2018john\u2019 to get a list of names starting with \u2018john\u2019 and then expand that to \u2018john sm\u2019 to get a list of \u2018john smith\u2019s and similar names.<\/p>\n (Note: it might have been safe to omit This approach does have its weakness. It won\u2019t 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 \u2018%bla%\u2019. Unfortunately, PostgreSQL does not have any index to optimize those types of searches.<\/p>\n 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\u2019ve 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\u2019d love to hear comments or suggestions for alternate approaches.<\/p>\n","protected":false},"excerpt":{"rendered":" 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\u2019ve decided to share my approach … Continue reading CREATE TABLE authors (
\nauthors_id serial PRIMARY KEY,<\/code>
\nauthor_name character varying UNIQUE NOT NULL<\/code>
\n);<\/code><\/p>\nClient Side JavaScript<\/h1>\n
Initial Implementation<\/h1>\n
use JSON;<\/code>
\nsub json_author_search : Local<\/code>
\n{<\/code>
\nmy ( $self, $c, $dashboards_id ) = @_;<\/code>
\n my $term = $c->req->param( 'term' ) || 0;<\/code>
\n $term = '%' . $term . '%';<\/code>
\nmy $terms =
\n$c->dbis->query( \"select authors_id, author_name as label from authors where author_name ilike ? \", $term )->hashes;<\/code>
\n $c->res->body( encode_json( $terms ) );<\/code>
\n return;<\/code>
\n }<\/code><\/p>\nmediacloud=# explain select authors_id, author_name as label from authors where author_name ilike '%bla%';<\/code>
\nQUERY PLAN<\/code>
\n---------------------------------------------------------<\/code>
\nSeq Scan on authors (cost=0.00..37.33 rows=1 width=22)<\/code>
\nFilter: ((author_name)::text ~~* '%bla%'::text)<\/code>
\n(2 rows)<\/code><\/p>\nPossible Solutions<\/h1>\n
\nThese 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 \u2018bla%\u2019 queries and relies on text_pattern_ops indexes for quick performance. Samokhvalov\u2019s other tip is to use lower instead of using ilike. So in our case we would add the following index:<\/p>\nCREATE INDEX author_name_prefix ON authors USING btree ( lower (author_name) text_pattern_ops);<\/code><\/p>\n$term = \u2018%\u2019 . $term;
\n$c->dbis->query( \"select authors_id, author_name as label from authors where lower(author_name) like ? \", $term )->hashes;<\/code><\/p>\nMy Solution<\/h1>\n
create index authors_name_varchar_pattern on authors(lower(author_name) varchar_pattern_ops);
\ncreate index authors_name_varchar_pattern_1 on authors(lower(split_part(author_name, ' ', 1)) varchar_pattern_ops);
\ncreate index authors_name_varchar_pattern_2 on authors(lower(split_part(author_name, ' ', 2)) varchar_pattern_ops);
\ncreate index authors_name_varchar_pattern_3 on authors(lower(split_part(author_name, ' ', 3)) varchar_pattern_ops);<\/code><\/p>\n$term = $term . '%';
\nmy $terms =
\n$c->dbis->query( \"select authors_id, author_name as label from authors where lower(author_name) like lower(?) OR \" .
\n\" lower(split_part(author_name, ' ', 1)) like lower(?) OR \" .
\n\" lower(split_part(author_name, ' ', 2)) like lower(?) OR \" .
\n\" lower(split_part(author_name, ' ', 3)) like lower(?) LIMIT 100 \",
\n$term, $term, $term, $term )->hashes<\/code><\/p>\nlower(split_part(author_name, ' ', 1)) like lower(?)<\/code> from the query since it will often be redundant with lower(author_name) like lower(?)<\/code>. 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.)<\/p>\nConclusion<\/h1>\n