New Text Search Goodies in Postgresql 8.4

Postgresql has a full text search engine built into it. Teodor Siagev and Oleg Bartunov, who started a text search engine called OpenFTS, merged their code base into Postgresql 7.4 as a separate contrib module called tsearch2.

Tsearch2 is highly extensible and sophisticated code base for text search. It is flexible in the sense that you can write your own stemmer and parser, or even use the default one for any new language. Tsearch2 keeping up with the tradition of extensibility in Postgres provides users to define their own ranking function or headline generation. Besides that it provides people to use two text indexes namely GIST and GIN both with different performance curves for initial indexing and index updates. Tsearch2 was merged in the core of Postgres last year in the 8.3 release.

Postgres 8.4 is being released after more than a year of development and testing. A few patches that many people wanted like a default replication scheme in the core and a SELinux in Postgres called SE-Postgrresql were punted for 8.5. The main reasons being that these patches were too big for people to review in the last months.

Postgres 8.4 brings a number of improvements in text search. Here are the list of new text features that you may look out for and may force you to upgrade:

1. Optimizer selectivity function for @@ text search operations (Jan Urbanski)

This was a Google Summer of Code (GSoC) project taken up by Jan Urbanski and it is great that the project was successful. Though it took a lot of time for this patch to be accepted, it provides a quite accurate selectivity measure for text search. This will enable the Postgres planner to produce better plans for SQL queries when text search matching operator is combined with other equally complicated operators.

2. Fast prefix matching in full text searches (Teodor Sigaev, Oleg Bartunov)

Earlier prefix matching was used to be done using LIKE operator. For example, for searching all documents that have have the beginning few words "sush", the WHERE clause needs to contain LIKE 'sush%'. However, LIKE operator does not use the text index and is very slow. This patch introduces fast prefix matching in Postgres. Now the where clause can be something like:

xt_tsvector @@ to_tsquery('sush:*')


3. Support multi-column GIN indexes (Teodor Sigaev)

Earlier if you have to index two separate text columns like "documents" and "comments", then you could only have separate indexes for each column. And then a query has to be matched with each column (q @ document and q @ comments). With this patch, such queries can take advantage of multi-column indexes if the developer has used one. Here is the performance improvement of multi-column index over single index as observed by Teodor:

Multicolumn index vs. 2 single column indexes

Size: 539 Mb 538 Mb
Speed: *1.885* ms 4.994 ms
Index: ~340 s ~200 s
Insert: 72 s/10000 66 s/10000

4. Improve full text search headline() function to allow extracting several fragments of text (Sushant Sinha)

This patch was contributed back by me. Headline generation is the identification of text fragment in a document where query terms appear. The default headline generation function shows only one text fragment for a set of query terms. Further, the existing headline generation function did not show good headlines (it is a more subjective judgment as there is no way to identify a good fragment.

My patch allowed more than one non-overlapping fragment to be displayed for a set of query terms. Further, the text fragments that were chosen in such a way that those fragments contained query items in the most compact way. A lot of databases will be envious of production quality headline generation in postgres now.


5. Improve support for Nepali language and Devanagari alphabet (Teodor)

I do not know much about this but looking at the CVS log, here was the bug that was fixed:

"Some languages have symbols with zero display's width or/and vowels/signs which
are not an alphabetic character although they are not word-breakers too.
So, treat them as part of word."

Setting up Streaming Replication and Hot-Standby features of Postgres 9.0 on Indian Kanoon

Postgres is a database software that powers a large number of production databases around the world including Indian Kanoon. Postgres 9.0 was recently released after more than a year and half of development. The version number was jumped from 8.4 (the previous release) to 9.0 considering the inclusion of two important features namely Streaming Replication and Hot Standby.

Streaming replication, as the name implies, allows a database administer to replicate a primary database on multiple secondary nodes. So when the primary database dies due to hardware failure or software error, one of the secondary nodes can become the primary database to serve production queries. Previously, to replicate a postgres database, one has to copy the base directoy and then periodically copy the Write-Ahead-Log (WAL) of the database. Then the secondary node would run in a continuous recovery process reading the WAL. As the secondary database was still recovering, it could not be used for querying. As such previous standby nodes were called "Warm-Standby".

The WAL shipping happened at time outs or when a WAL segment was full. And so the secondary database could be significantly behind the master in seeing the WAL. Streaming replication fills that gap now. It does not wait anymore for the filling of WAL segments as it "streams them directly" to the secondary server on a TCP connection. Note that currently streaming replication only allows asynchronous transaction, which means that a database transaction need not wait for the replication to finish. So there is a small window of time in which a transaction committed on primary database is not replicated on the secondary and the primary crashes.


The Hot-Standby feature allows read-only queries on a standby node. Previously, a standby was not good for anything other than waiting for the primary to crash. Now the standby can serve production queries as well while keeping the secondary database up to date with the primary. This is tremendously useful as read-only database queries can be load balanced on primary as well as secondary.

I had lot of fun trying to play around with making these two features work for Indian Kanoon databases. I followed the wiki doggedly for setting up streaming replication. However, unable to replicate a dog, I would miss something or the other and the thing will not turn up. In the end the Indian Kanoon database was successfully replicated in a hot-standby mode on an another server in the same data center. It has to be noted that data transfer with in the data-center was clocking close to half a gigabit per second that reminds me of the old 100Mbps networking cards that are obsolete now.

Here are the final steps I took:

1. Modified postgresql.conf on the primary node with following changes:
a. wal_level = hot_standby # sets up wal replaying on a TCP socket
b. max_wal_senders = 1 # max number of walsender processes
c. wal_keep_segments = 128 # in logfile segments, 16MB each
d. listen_addresses = '*' # opens up port 5432 for postgres database server

2. Modify pg_hba.conf to include the ACL for secondary node. Add the following line:

host replication postgres secondary_node/32 trust

3. Copying the base database. On the primary node:
a. psql -c "SELECT pg_start_backup('label', true)"
b. rsync -avz --progress ${PGDATA} secondary:/home/postgres/
c. psql -c "SELECT pg_stop_backup()"

4. Setting the secondary node:
a. Modify postgresql.conf to include "hot_standby = on"
b. Created a recovery.conf on the secondary node with following changes:
i) standby_mode = 'on'
ii) primary_conninfo = 'host=indiankanoon.org'
iii) trigger_file = '/path_to/trigger'
c. Start the database and check the server log

Indian Kanoon - The road so far and the road ahead

I was quite pleased to find law information publicly available on the judis and
the indiacode. However, it was too difficult to look for anything on these
websites and so I started building tool sets to play with law data. At a
certain point I felt that integration of these small software pieces will be
very interesting. I was still skeptic as to whether search on law documents
meant anything to common people who do not know the law jargon. In any case I
integrated the tool sets into a search engine and got pleasantly surprised when
many of my common queries were well answered. So I deployed it as a publicly
available service, called it Indian Kanoon and fortunately many people have
found it useful over time.

When actual people start using a service (whether free or fee-based), the
demand for correctness and usability increases significantly. The need to
understand the problems, think about the issues and fix them have kept me in
tight grip. Indian Kanoon was announced last January in a very crude form and a
number of changes have gone in the past year. So this post is mostly to
highlight what all work has gone into indian kanoon in the last year, what the
challenges were and what features are planned in future.

Integrating more legal documents

Indian Kanoon started only with supreme court judgments and central laws.
Clearly this was not sufficient to many people who wanted to search in high
court judgments, law commission reports and law journals. Over last year, a
number of other legal documents have been added. Firstly, the law commission reports
and a law journal was added. The law journal "Central India Law Quarterly" has been
digitized and was put up on Internet by Devaranjan. The only problem in their integration
was that the many of these documents were images scanned from the books. So I used tesseract,
a free OCR software supported by google, for extracting text from these images.
However, the text extraction quality was just 90% and I am skeptical if google
uses tesseract for its own google books project. Tarunabh pointed out the availability
of constituent assembly debates that can be integrated. He pointed out two main
problems in integrating them. First, the article numbers in the debates were different
than in the constitution. Secondly, debates are cited in the court judgments using
page numbers in the official books. But both of these numbers were not available in
the digital copy provided by the government. So the only way out was to go back to
the actual books. We did not want to give away the digital route yet. So we went to books.google.com that had a scanned copy of the debates. Tarunabh emailed Google
to release those books in public domain as the copyright on them has expired the
previous year. Google replied saying that they are not sure about the copyright
expiration and will be conservative in making books publicly available. Finally,
I loaned the books from a library, manually copied the page numbers and the
association list between the article numbers in the debates and the article numbers
in the Constitution and integrated the constituent assembly debates.

Indian Kanoon was highly deficient in terms of high court judgments and even in
Supreme court judgments as Dilip earlier pointed out on my blog. So I
integrated the high court judgments and made Indian Kanoon more comprehensive.

Features

Beside making Indian Kanoon comprehensive in terms of legal documents, a number
of features to make searching easier have been added. The most common problem
was the mis-spelling of Indian names and so I I first added the most critical
feature for
spelling suggestions. Ability to search and order documents by date was added next. The search and forums were redesigned to look aesthetically appealing. In order to provide notifications for new judgments, RSS feed for court judgments was recently added. Finally, people may like to monitor documents related to certain words or phrases. So on Tarunabh's suggestion I added the
RSS feed for any arbitrary query.

Contributing code back

Developing indian kanoon software has been possible because of the availability
of large amount of free software. As a result I was able to modify these
software and customize it for law search. Indian Kanoon uses a feature rich
open source database - Postgresql as the
backend. When users submit a query, matching documents are found, ordered and
the top few are shown. For each document, the search engine also displays a
small text excerpt where the query terms appear. The text excerpt allows people
to quickly evaluate whether the document is relevant to the query. The
headline function developed for indian kanoon was contributed back to postgres
and has been
added to the postgres CVS head. Beside that a bug in postgres was fixed as well. I also sent the
phrase search function to the postgres list. But, Teodor Sigaev, who merged OpenFTS in the Postgresql, wants a generic operator that can check for arbitrary distance between the lexemes. I have not yet got time to work on this operator.

Beside development on the database, the Indian Kanoon forums has been released
as djangobb - Django Bulletin board that uses the django web application framework. The judis recently moved to a really obfuscated website where the judgment did not have a
stable URL. Prashant Iyengar pointed out that we are not getting the live feed from the judis. So I reverse engineered the website and released the judis reverse engineering code.

Future works

Even after so much of work a number of things need to be improved on indian
kanoon. Here is a list of changes that I think are required to make indian
kanoon more comprehensive, more rich and better in search. Please feel free to
suggest more.

1. Reverse engineering different court and tribunal websites so that indian
kanoon can provide a live feed of all Indian court and tribunal judgments.

2. Currently indian kanoon cannot answer questions like "list of judgments in
which a particular law section was held" and "search only in family law
judgments". The problem is that we do not have enough semantic information
about judgments. So I want to enable common users to start tagging documents.
There will be two kinds of tagging: categorizing court judgments and laws into
broad categories like family law, constitutional law, right to equality etc and
secondly, tag whether a judgment explains, bolsters, or overturns a given law
or judgment. The tags generated by the users will be available to everyone
with the Creative Commons-Attribution-Share Alike license 3.0.

3. A number of people type in natural language in the search box. For example,
someone will type "recent judgments from delhi high court". Even though we can
answer these questions, we directly search the query to the documents. For
example, the above query could have been reduced to "doctypes: delhi sortby:
mostrecent". So what we need is a small natural language processor that can
automatically convert such natural language queries to a more precise query
that the engine can evaluate.

4. I only support searching for a set of words in the documents. Roy wanted a
more sophisticated
query langauge that supports boolean queries. This will enable people to
issue more complicated queries like (freedom OR speech) AND (NOT expression).

5. With the addition of more data over time, Indian Kanoon takes more than a
second to evaluate some queries. A number of software changes (or possible
hardware upgrade) are required to bring back the evaluation time to sub-second.