DumboDB: Announcing Collations Support

DoltHub is the version-control database company. We are in the alpha phase of building DumboDB, which is our take on MongoDB + Git. We’re not going to mention version control at all today, though. Database content today: collations, specifically.

Organization of data is obviously the purpose of every database, and all optimal code paths land at one critical point: sorting. Sorting is the foundation of indexing, searching, and organizing data. In order to sort data, we need to know how to compare two values. This is where collations come in. Collations are a set of rules that determine how textual values - what some would call a string of bytes - are compared and sorted.

We’ve added collation support to DumboDB in our latest release! With this feature, you can now specify how strings should be compared and sorted in your DumboDB collections. This leads to not just more correct behavior, but also enables features like case-insensitive unique indexes and locale-specific sorting. Let’s dig in!

Collation Basics#

String comparison is a surprisingly complex topic. Different languages have distinct rules for how letters are ordered, and even a single character can sort differently depending on the region.

Take the character ‘ä’ (a-umlaut):

• In German (de-DE), ‘ä’ is treated as a variant of ‘a’, so Äpfel (apples) sorts right next to Apfel (apple).
• In Swedish (sv-SE), ‘ä’ is an entirely separate letter positioned at the end of the alphabet, so Äpfel sorts after Zebra.

Without a specified locale, a collation engine has no way of knowing whether ‘ä’ belongs at the start or end of your list.

You might assume collation only matters for accented or non-English text. It doesn’t. Binary comparison — sorting by raw byte value — gets plain ASCII English wrong too, because the ASCII table puts every uppercase letter (A–Z, bytes 65–90) before every lowercase letter (a–z, bytes 97–122). So a computer sorting by bytes isn’t sorting alphabetically at all; it’s sorting by case first, letter second.

Take five ordinary words:

input:        apple, Banana, cherry, Apple, banana

binary sort:  Apple, Banana, apple, banana, cherry    // "Banana" is second?!
alphabetical: apple, Apple, banana, Banana, cherry

Binary order shoves every capitalized word to the front, so Banana lands ahead of apple — a result no English speaker would accept. Nothing exotic is going on here: no accents, no other languages, just capital letters. That’s why “just compare the bytes” fails even for the simplest English, and why real ordering needs a collation.

International Components for Unicode (ICU)#

Collations are complicated human behavior codified as binary data and logic tables. It’s a great example of where having standards is important. I don’t need to be an expert in every language in the world to sort text, thanks to the International Components for Unicode (ICU). ICU is a set of libraries that provide robust and full-featured Unicode support, including collations. ICU is widely used in many programming languages and platforms, including Java, C++, and Python. Most importantly for us, MongoDB uses it too.

What makes this particularly interesting is that ICU changes over time as new Unicode characters are defined. As stated above, databases rely very heavily on sorting. If you have an index whose keys are sorted in a certain way, and then the collation rules change, you can end up with an index that is no longer sorted correctly. That effectively breaks the index, and makes the database unusable. MongoDB has never upgraded its ICU version for this reason. We’ll talk a little more about this below.

Collations in MongoDB#

By default, when you create any collection or index in MongoDB, it uses binary comparison of UTF-8 byte strings. If you set the default on a collection, then indexes created on that collection will inherit the collation. The collation of a collection or index is immutable.

⚠️ Note! As stated above, binary comparison doesn’t produce sensible results for any language, so it is always a good idea to use a collation when creating a collection if you are going to need to sort on text data. Default behavior is most likely not what you want, and it can lead to subtle bugs in your application.

Here is an example of creating a collection with a collation:

db.createCollection("products", {
    collation: {
      locale: "en",           // English rules
      strength: 2,            // case-insensitive ("Widget" == "widget")
      numericOrdering: true   // "item10" sorts after "item2", not before
    }
  })

collation is an object with nine options that control how strings are compared. The following table summarizes the options available in MongoDB (and therefore DumboDB):

Option	Values (default)	What it controls
locale	an ICU locale ID like "en", "de", "sv", "fr_CA" — 109 accepted; "simple" or omitted = binary	Which language’s rules apply. This is the switch that turns on language-aware comparison; everything else refines it.
strength	1–5 (3)	How many “levels” of difference matter: 1 = base letters, 2 = +accents, 3 = +case (default), 4 = +punctuation, 5 = exact code points.
caseLevel	true / false (false)	Adds a dedicated case-comparison level, so case can matter even at strength 1–2 (accent-insensitive but case-sensitive).
caseFirst	"off" / "upper" / "lower" ("off")	When case is the tie-breaker, whether uppercase or lowercase sorts first. "off" uses the locale’s own default.
numericOrdering	true / false (false)	Compares embedded digit runs as numbers, so "file10" sorts after "file2".
alternate	"non-ignorable" / "shifted" ("non-ignorable")	Whether spaces and punctuation are significant, or ignored at the primary level (so "black bird", "black-bird", "blackbird" compare equal).
maxVariable	"punct" / "space" ("punct")	With alternate:"shifted", which characters count as ignorable — up through punctuation, or whitespace only.
normalization	true / false (false)	Applies full Unicode normalization first, so text that encodes the same character different ways compares correctly.
backwards	true / false (false)	Compares accent differences from the end of the string backward — the classic French accent-ordering rule.

As stated above, the collation for a collection or index is immutable. It is impossible to update the collation of an existing collection or index. If you need to change the collation, you must create a new collection or index with the desired collation, and then copy the data over. The reason for this is that the collation affects how the data is stored on disk, and changing it would require rewriting the entire collection or index. This is a fundamental limitation of how collations work in MongoDB (and therefore DumboDB). This actually helps us avoid a lot of complexity in a branch and merge workflow, so we are happy to keep this limitation in DumboDB.

Locales#

The locale option is a shorthand for a set of collation rules. Generally, you will set just the locale, and then add other options to refine the behavior. There isn’t a MongoDB-native way to see the settings for a given locale, but you can create a collation and then look at its properties, like this:

mydb> db.createCollection("probe", { collation: { locale: "da" } })
{ ok: 1 }
mydb>  db.getCollectionInfos({ name: "probe" })[0].options.collation
{
  locale: 'da',
  caseLevel: false,
  caseFirst: 'off',
  strength: 3,
  numericOrdering: false,
  alternate: 'non-ignorable',
  maxVariable: 'punct',
  normalization: false,
  backwards: false,
  version: '57.1'            // Mongo's ICU version. DumboDB uses "78.3"
}

DumboDB currently accepts 109 locales, which matches the set of locales supported by MongoDB. There are more than 200 locales supported by ICU, so if you need one we don’t support, let us know.

DumboDB Specifics#

DumboDB tries its best to be compatible with MongoDB, but there is a small instance of deviation here. DumboDB uses a newer version of ICU than MongoDB. MongoDB uses version 57.1 of ICU, which was released in 2016. As stated above, changing the version of ICU brings risks; sorting is foundational to how the database stores data. DumboDB uses version 78.3 of ICU, which is the most recent version. DumboDB may actually stay on that version forever. The changes in ICU are pretty obscure at this point. New languages and characters aren’t coming into existence with the exception of emojis. The sorting rules for existing languages are pretty stable. We don’t expect to have to upgrade ICU in the future, but if we do, it will be a conscious decision.

As an implementation detail, we’ve captured the C code we care about in amber to ensure it’s stable. It even has its own code repository.

Other than the ICU version difference, DumboDB’s collation support is compatible with MongoDB. You can use the same collation options and locales, and expect the same behavior.

Useful Examples#

Let’s consider a couple of ways to use collations in the real world.

Language-Specific Sorting#

This is the most obvious use case for collations. There are many applications that are language-specific, and you just want strings to make sense in that context. For example, if you are building a Swedish phone book, you want the names to be sorted the way a Swedish speaker would look them up. Here is an example:

mydb> db.createCollection("telefonkatalog",     
   { 
    collation: { locale: "sv" }                 // Swedish locale. 
   });
{ ok: 1 }
mydb> db.telefonkatalog.insertMany([            // Luckily, "phone book" contains no accented characters!
  { name: "Öberg",      phone: "08-11 22 33" },
  { name: "Andersson",  phone: "08-44 55 66" },
  { name: "Åberg",      phone: "08-77 88 99" },
  { name: "Zetterberg", phone: "08-12 34 56" },
  { name: "Berg",       phone: "08-65 43 21" },
  { name: "Ängström",   phone: "08-90 09 90" },
  { name: "Svensson",   phone: "08-55 66 77" }
])
mydb> db.telefonkatalog.find({}, { _id: 0 }).sort({ name: 1 })
[
  { name: 'Andersson', phone: '08-44 55 66' },
  { name: 'Berg', phone: '08-65 43 21' },
  { name: 'Svensson', phone: '08-55 66 77' },
  { name: 'Zetterberg', phone: '08-12 34 56' },
  { name: 'Åberg', phone: '08-77 88 99' },       // å ä ö come AFTER z, Swedish norm.
  { name: 'Ängström', phone: '08-90 09 90' },    // NOT binary order, which would put Ä before Å
  { name: 'Öberg', phone: '08-11 22 33' }
]

The default find-then-sort uses the collection’s collation, which is Swedish. As a comparison, here is what the results would look like if you used a binary (“simple”) collation instead, which is the default:

mydb> db.telefonkatalog.find({}, { _id: 0, name: 1 })
                       .sort({ name: 1 }).collation({ locale: "simple" })
[
  { name: 'Andersson' },
  { name: 'Berg' },
  { name: 'Svensson' },
  { name: 'Zetterberg' },
  { name: 'Ängström' },           // binary order, so Ä comes before Å
  { name: 'Åberg' },
  { name: 'Öberg' }
]

Finally, to show what this looks like when you sort in English, which treats Å and Ä as A, and Ö as O:

mydb> db.telefonkatalog.find({}, { _id: 0 }).sort({ name: 1 }).collation({ locale: "en" })
[
  { name: 'Åberg', phone: '08-77 88 99' },
  { name: 'Andersson', phone: '08-44 55 66' },
  { name: 'Ängström', phone: '08-90 09 90' },
  { name: 'Berg', phone: '08-65 43 21' },
  { name: 'Öberg', phone: '08-11 22 33' },
  { name: 'Svensson', phone: '08-55 66 77' },
  { name: 'Zetterberg', phone: '08-12 34 56' }
]

Case-Insensitive Unique Index#

Suppose you have a collection of users, and you want to ensure that emails are unique. Emails, like host names, are case-insensitive. So you want to create a unique index on the email field, but you want it to be case-insensitive. Furthermore, you would never want to create a user with an email that conflicted with an existing email, even if the case was different. You enforce this by doing two things: using a validator to ensure that the user document has an email, and creating a unique index on the email field with a case-insensitive collation. Here is an example:

mydb> db.createCollection("users", {
  validator: {
    $jsonSchema: {
      bsonType: "object",
      required: ["email"],
      properties: {
        email: {
          bsonType: "string",
          description: "email is required and must be a string"
        }
      }
    }
  }
})
mydb> db.users.createIndex(
  { email: 1 },
  {
    unique: true,
    collation: { locale: "en", strength: 2 } }   // strength 2 = ignore case
)

Now let’s insert a user document, and ensure that we can’t insert another user with the same email, even if the case is different:

mydb> db.users.insertOne({ email: "Alice@example.com" })
{
  acknowledged: true,
  insertedId: ObjectId('6a8ca52c071063f49fbc3d8c')
}
mydb> db.users.insertOne({ email: "alice@example.com" })
MongoServerError: E11000 duplicate key error collection: mydb.users index: email_1 dup key: { email: "alice@example.com" }

The email is unique, even though the case is different. Yay! Now, let’s do a case-insensitive search for the user:

// You must specify the collation in your query!
db.users.find({ email: "alice@example.com" }).collation({ locale: "en", strength: 2 })
[
  {
    _id: ObjectId('6a8ca52c071063f49fbc3d8c'),
    email: 'Alice@example.com'
  }
]

You can see in the find query, we specify the same collation. This is important, because MongoDB’s query planner doesn’t fuzzy match on these sorts of things. If you don’t specify the collation, it will do a binary search and not find the user. One way to avoid this would be to set the collation on the collection itself. Then creating an index on the email field would automatically use the collection’s collation, and you wouldn’t have to specify it in the find query. However, this would also make all other queries on strings case-insensitive, which may not be desirable. So it’s a trade-off.

If you really need to know what the query planner is going to do, you can use the explain function to see the query plan. Here is an example:

mydb> db.users.find({ email: "alice@example.com" })
        .collation({ locale: "en", strength: 2 })
        .explain().queryPlanner.winningPlan
{
  "stage": "FETCH",
  "inputStage": {
    "stage": "IXSCAN",
    "indexName": "email_1",                // The index we created above
    "keyPattern": { "email": 1 }
  }
}

What’s Next?#

We’re continuing to add features to DumboDB. Push and Pull support is in the works, and we’ll land that at the same time we enable branch permissions. We’re working on these features because our users have asked for them in our Discord. If you have a feature request, or want to see what we’re working on, join us there!