Problem Description

Recently, I had the exciting challenge to redesign the database representation of a potentially very large list of elements, each with an arbitrary number of possibly different attributes. Previously, the list was internally stored in an embedded SQL database. In order to deal with the fixed schema requirements of SQL, the following schema was conceptualized:

This approach is perfectly fine for a few thousand elements. However, when performance becomes critical because you would like to support very large databases, this approach reaches its limitations. This is not surprising because the relational database needs to perform JOIN operations for almost all use cases. Simply displaying an element with all its properties requires a JOIN of all three tables.

Nevertheless, it is a very common approach with relational databases. I cannot think of many ways to improve this schema without introducing other pitfalls. I would be very interested to hear about improved schema suggestions in the comments below.

However, there is definitely one way to improve this situation:
Getting rid of the relational database completely.

Having a list of elements that can each have an arbitrary number of properties which might differ from each other is a perfect use case for a document-oriented NoSQL database. The only challenge remaining was to find an embeddable open-source project, as those were strict requirements.

Nitrite Overview

When I started to look for NoSQL alternatives to tackle the described problem, I immediately thought of MongoDB. I have used it already in some small projects and feel quite comfortable with it. Unfortunately, there is no embedded version of MongoDB, except for testing and for mobile app development.

So my search went on. At first, I stumbled upon some very interesting key-value store projects:

• Chronicle Map: https://github.com/OpenHFT/Chronicle-Map
• MapDB: https://github.com/jankotek/mapdb/

I am happy to have these on my radar now, they are certainly very interesting and might find some use in future projects. However, for the above described use case, a key-value store is not a good fit. Instead, a document-oriented approach similar to MongoDB would be ideal. With this requirement, I actually had trouble finding open source projects. In the end, I had two relatively unknown alternatives:

• Jsondb: https://github.com/Jsondb/jsondb-core
• Nitrite Database: https://github.com/dizitart/nitrite-database

The decision in favor of Nitrite was quite obvious, it has beautiful and extensive documentation and boasts a “Very fast and lightweight MongoDB like API”.

Implementation

Implementing our use case in a document-oriented NoSQL database is actually very straightforward. We simply create a NitriteCollection and add all our elements as Document to this collection. Each document will contain exactly the attributes that the respective element actually has set. This requires much less effort than with fixed-schema databases.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17

Nitrite db = Nitrite.builder()
    .filePath("databaseFile.db").openOrCreate("user", "password");

NitriteCollection collection = db.getCollection("elementCollection");

int i = 0;
for (Element element : elements)
{
  Document document = Document.createDocument("tableId", i);
  for (Map.Entry<String, String> entry : map.entrySet()))
  {
    document.put(entry.getKey(), entry.getValue());
  }
  collection.insert(document);
  i++
}
collection.createIndex("tableId", IndexOptions.indexOptions(IndexType.Unique, true));

The tableId attribute is specific to my use case. It allows to index my elements for later use with a JTable.

Using Nitrite as JTable Backend

I did not (yet) create a proper, reproducible evaluation setup. However, it is quite easy to get a feeling for how fast Nitrite compares to embedded SQL solutions (Derby, H2, …). Simply create a a basic Java Swing GUI containing a JTable with the following TableModel:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50

public class NitriteTableModel extends AbstractTableModel
{
  private NitriteCollection nitriteCollection;
  private List<String> attributeNames;
  private final List<Document> filteredDocuments = new ArrayList<Document>();


  public NitriteTableModel(NitriteCollection nitriteCollection,
      List<String> attributeNames)
  {
    super();
    this.nitriteCollection = nitriteCollection;
    this.attributeNames = attributeNames;
  }

  @Override
  public int getColumnCount()
  {
    return attributeNames.size();
  }

  @Override
  public int getRowCount()
  {
    return filteredDocuments.size();
  }

  @Override
  public Object getValueAt(int rowIndex, int columnIndex)
  {
    int tableId = (int) filteredDocuments.get(rowIndex).get("tableId");

    Document document = nitriteCollection.find(Filters.eq("tableId", tableId))
        .firstOrDefault();

    return document.get(attributeNames.get(columnIndex));
  }

  public void setFilteredIndices(Cursor find)
  {
    filteredDocuments.clear();
    Document projection = Document.createDocument("tableId", null);
    RecordIterable<Document> documents = find.project(projection);

    for (Document document : documents)
    {
      filteredDocuments.add(document);
    }
  }
}

This allows to easily filter collections and display the results.

Sorting:

nitriteTableModel.setFilteredIndices(nitriteCollection.find(Filters.eq(attributeNameField.getText(), attributeValueField.getText())));
nitriteTableModel.fireTableDataChanged();

Filtering:

nitriteTableModel.setFilteredIndices(nitriteCollection.find(FindOptions
                .sort(attributeNameField.getText(), SortOrder.Ascending)));
nitriteTableModel.fireTableDataChanged();

attributeNameField and attributeValueField are basic JTextField GUI elements that allow to specify which column should be used for filtering or sorting as well as which value the filtered elements have to match. Nitrite provides all the obvious filtering (eq, gt, gte, lt, lte, in, …) and sorting (ascending, descending) options out of the box.

Conclusion

I have used Nitrite as JTable backend with several million elements. The table performs amazingly smooth. Filtering and sorting on indexed attributes is almost instant as compared to several seconds or even minutes with the SQL-based approach described in the beginning.

If you happen to know of a more extensive performance evaluation of Nitrite, ideally comparing it against embedded SQL-based systems, please post it in the comments or contact me directly. If there is none, I might do one myself in a future blog post.