Xapian and Open Source
Xapian’s official website is http://www.xapian.org, home to an outstanding open-source search engine project. “Search engine” is actually a colloquial term; the formal name is an IR (Information Retrieval) system. Xapian is licensed under the GPL, meaning users are free to modify its source code and distribute it. Chinese-language resources for Xapian are extremely scarce鈥攜ou could say there isn’t even a single complete or detailed introductory document in Chinese on the internet right now, let alone a Chinese API reference. In fact, English-language resources for Xapian are also limited. Apart from the Docs and Wiki on the official site, information is mainly scattered across mailing lists on a few other websites. In this respect, it cannot compare to Lucene. Of course, Lucene has now evolved to version 2.x, while Xapian’s latest version is only 1.012. Open-source projects abroad generally have strict version number control; a project isn’t usually considered stable and mature until it reaches 1.x.
What Platforms Can Xapian Run On?
Xapian is written in C++, but provides bindings for Perl, Python, PHP, Java, Tcl, C#, and Ruby, among many others. Xapian can be seen as a model of STL programming. Here, you’ll find familiar concepts like reference-counted smart pointers, containers, and iterators, with naming conventions even similar to the STL. This is sure to resonate with C++ and STL enthusiasts (and frankly, very few C++ programmers completely avoid the STL). Because Xapian relies on the STL and the C runtime library, it is highly portable. According to the official word, it can run on Linux, Mac OS X, FreeBSD, NetBSD, OpenBSD, Solaris, HP-UX, Tru64, IRIX, and even other Unix platforms, and it also runs very well on Microsoft Windows. Of course, it doesn’t achieve Java’s “write once, run anywhere” promise; generally, you need to recompile it when porting to another platform. For details on how to compile Xapian on a 32-bit Windows system, please refer to my earlier article, “Compiling Xapian on Windows Using nmake“.
Xapian Features
According to the official description, Xapian is a highly adaptable toolkit that allows developers to easily add advanced indexing and search capabilities to their applications. It supports the probabilistic retrieval model while also accommodating Boolean query operators.
In terms of features, Xapian is somewhat similar to Lucene. Both have concepts like Term, Value (called SortField in Lucene), Posting, Position, and Document. However, Xapian lacks the concept of a Field, which directly makes Xapian slightly more cumbersome to use than Lucene. This isn’t a problem at all, though; with a few tricks, you can easily implement a Field-like concept in Xapian yourself. Lucene also has an element called Payload, which is metadata or a payload attached to a Term. For example, the sentences “Go home and eat dinner” and “Hurry home to eat dinner” both contain the term “eat dinner,” but how do you convey the tone during retrieval? While you could add a term to solve this, the index information for a term is stored separately from its storage information, which leads to relatively poor I/O performance. Payload was created to address this, as payload information is stored directly in the index. Since my research into Xapian isn’t very deep yet, I still need to investigate whether a similar concept to Payload exists within it.
Xapian and Search
The purpose of search is to present result data to the end user. The biggest difference between a search engine and a standard database query lies in the query itself. Xapian provides multiple query mechanisms.
- Probabilistic search ranking – More important terms receive a higher weight than less important ones, so documents associated with high-weight terms appear higher in the result list.
- Relevance feedback – By providing one or more documents, Xapian can suggest the most relevant terms to expand a query, and display the most relevant documents.
- Phrase and proximity searching — Users can search for an exact phrase or a specified group of words.
- Full range of Boolean search operators, for example ("stock NOT market", etc).
- Support for stemming search keywords, for example, when searching for “football,” documents containing "footballs" or "footballer" are also considered matches. This helps find relevant results that might otherwise be missed. Stemming algorithms are currently available for Danish, Dutch, English, Finnish, French, German, Hungarian, Italian, Norwegian, Portuguese, Romanian, Russian, Spanish, Swedish, and Turkish.
- Support for wildcard queries, such as “xap*”.
- Support for synonym queries. For instance, C++ can be automatically converted to CPlusPlus, and C# to CSharp.
- Xapian supports spelling correction, for example, “xapian” can be corrected to “xapain,” provided the terms have been indexed. This feature is somewhat similar to Google’s “Did you mean: xxx” function.
Xapian’s Storage System
The current version of Xapian uses Flint as its default storage system. Flint stores data in blocks, with a default size of 8K per block, theoretically allowing a single file to reach a maximum size of 2048GB. Of course, this is impossible on older file systems like FAT/FAT32. Anyone familiar with Windows memory management knows that on a 32-bit Windows system, each process has a total virtual address space of only 4GB, and the user-mode portion is under 2GB (though Windows 2003 can extend user-mode space to around 3GB). Therefore, an application cannot read the entire database file into memory at once. The common approach is to use memory-mapped files, reserving the address space first and only committing physical memory when it is actually used. The memory page granularity is 4K, meaning each page in memory is 4K, whereas on IA64 systems, the page granularity is 8K. Besides pages, memory also uses allocation granularity blocks, which are 64K on both x86 and IA64 systems. Xapian likely stores data this way to achieve data alignment across various platforms. Data alignment is critically important for CPU addressing during computation, and both 8 and 64 are multiples of 4. Therefore, one might boldly conjecture that Xapian’s choice of 8K as its default block size for storage strikes the optimal balance between performance and compatibility.
Xapian uses unsigned 32-bit ints as Document IDs, meaning each Xapian database can hold up to 4 billion documents. Both Xapian’s terms and documents are stored using B-trees. In fact, many database systems (referring here to relational databases) use B-trees or B+ trees for their indexes, offering the benefit of relatively convenient and fast add, delete, modify, and search operations. The downside is that space from deleted indexes cannot be reused, and indexes often need to be rebuilt frequently to maintain performance.
Xapian Performance
Search engine performance is a major concern for users, so how does Xapian perform? The official answer is, The short answer is "very well" – a previous version of the software powered BrightStation's Webtop search engine, which offered a search over around 500 million web pages (around 1.5 terabytes of database files). Searches took less than a second. Across 500 million web pages totaling 1.5TB of files, a search completed in under a second. Of course, this is heavily dependent on the platform and hardware running it. Once we build our own Xapian search engine application, we can test the specific speed for ourselves.
Excellent Example of Xapian
Xapian’s official website features an excellent usage example, a project called Omega, which can even be used out of the box as a CGI application. Omega comes with two index generation tools, Omindex and ScriptIndex, which can index HTML, PDF, image, and even video files on your hard drive and generate a database. By operating on these databases created by Omindex or ScriptIndex, Omega provides the functionality to search these files.
About the “Building Your Own Search Engine with Xapian” Series
While using Xapian, I typically consult the Docs, API Docs, and Wiki at http://www.xapian.org/docs/.