Exploring Solr Internals : The Lucene Inverted Index

This blog post is about the Lucene Inverted Index and how Apache Solr internally works.

When playing with Solr systems, understanding and properly configuring the underlying Lucene Index is fundamental to deeply controlling your search.

With a better knowledge of how the index looks like and how each component is used, you can build a more performant, lightweight and efficient solution.

The scope of this blog post is to explore the different components of the Inverted Index.

The Lucene Inverted Index

The Inverted Index is the basic data structure used by Lucene to provide Search in a corpus of documents.

It’s pretty much quite similar to the index at the end of a book.

From Wikipedia :

“In computer science, an inverted index (also referred to as postings file or inverted file) is an index data structure storing a mapping from content, such as words or numbers, to its locations in a database file, or in a document or a set of documents.”

In Memory/On Disk

The Inverted index is the core data structure that is used to provide Search.

Assuming we are using a FileSystem Lucene Directory, the index will be stored on the disk for durability.

Modern implementation of the FileSystem Directory will leverage the OS Memory Mapping feature to load into the memory (RAM) chunk of the index when necessary.

The index in the file system looks like a collection of immutable segments.

Each segment is a fully working Inverted Index, built from a set of documents.

The segment is a partition of the full index, it represents a part of it and it is fully searchable.

Each segment is composed of a number of binary files, each of them storing a particular data structure relevant to the index.

Hands on!

Assuming 3 documents, each of them with 2 fields, here’s how a full inverted Index will look:

This sounds scary at the beginning, let’s analyze the different components of the data structure.

Term Dictionary

The term dictionary is a sorted skip list containing all the unique terms for the specific field.

Two operations are permitted:

• next() -
• advance(ByteRef b) -

This automaton is used at query time to identify a starting point to look into the dictionary.

When we run a query (a TermQuery for example):

1. we give input to the In Memory Automaton, and an Offset is returned
2. we access the location associated with the Offset in the Term Dictionary
3. we advance to the ByteRef representation of the TermQuery
4. if the term is a match for the TermQuery we return the Posting List associated

Document Frequency

The term frequency indicates the number of Documents in the corpus containing the term  t in the field f.

Posting List

The posting list is the sorted skip list of DocIds that contains the related term.

Each element of this posting list is :

• Document Ordinal: Term Frequency: [array of Term Positions]: [array of Term Offset].

Live Documents

Live Documents is a lightweight data structure keeping the alive documents at the current status of the index.

Norms

Norms is a data structure providing length normalization and boost factor per Field per Document.

Schema Configuration

When configuring a field in Solr (or directly in Lucene) it is possible to specify a set of field attributes to control which data structures are going to be produced.