In case anyone wonders why they are called German strings: the article mentions the "research predecessor" of Cedar, Umbra. Umbra is a project of TU (technical university) Munich, Germany.

If I understood what I was reading about German Strings, I think UTF-8 could add complications to these things.

The added question mark in the HN submission makes little sense.

Title should mention (2024). Some of the info was already outdated back then [1]

https://news.ycombinator.com/item?id=41176051

I really enjoyed this article. The storing in-place of a prefix is a neat idea for faster matching/sorting.

I wonder if they also have the concept of a reverse string which stores the (reversed) suffix instead and stores the short strings backward.

Niche, but would be fast for heavy ends-with filters.

> To solve these problems, Umbra, the research predecessor of CedarDB, invented what Andy Pavlo now affectionately (we assume ;)) calls “German-style strings”.

This is how Borland Turbo Pascal stored strings as far back as the first version in mid-80s.

Length followed by the string.

  { length, string value}

  {length, prefix, class, pointer }

    {length, pointer}

    {length, capacity, pointer}

This is actually really similar to how SQL Server has long encoded it's varchar(max) format as I understand it. Short text is stored on the row page, but longer text is bumped to a different page.

Interesting to see a deepdive about string formats. I hadn't thought very deeply about it before.

I do agree with the string imutable argument. Mutable and imutable strings have different usecases and design tradeoffs. They perhaps shouldn't be the same type at all.

The transient string is particularly brilliant. Ive worked with some low level networking code in c, and being able to create a string containing the "payload" by pointing directly to an offset in the raw circular packet buffer is very clean. (the alternative is juggling offsets, or doing excessive memcpy)

So beyond the database usecase it's a clever string format.

It would be nice to have an ISO or equivalent specification on it though.

"Optimized" string types are everywhere and I bet that multiple people have already created string types almost identical to German strings. But the memory savings are small and they are not more efficient than ordinary strings. For string comparison you compare the pointers, which is cheaper than comparing two pairs of registers. If the pointers mismatch you compare the (cached) hashes and only if they match do you need to compare characters. For the prefix query, starts_with(content, 'http'), just store a string of the four-character prefix. With immutable strings the overhead is just one pointer.

Something is very wrong with the site's design. The header's font size is 9.8px, the body is 13px.

> We would like to have a string that is very cheap to construct and points to a region of memory that is currently valid, but may become invalid later without the string having control over it.

> This is where transient strings come in. They point to data that is currently valid, but may become invalid later, e.g., when we swap out the page on which the payload is stored to disk after we’ve released the lock on the page.

> Creating them has virtually no overhead: They simply point to an externally managed memory location. No memory allocation or data copying is required during construction! When you access a transient string, the string itself won’t know whether the data it points to is still valid, so you as a programmer need to ensure that every transient string you use is actually still valid. So if you need to access it later, you need to copy it to memory that you control.

Hm. What if I don't bother with that and I just read from the transient string? It's probably still good.

> In C, strings are just a sequence of bytes with the vague promise that a \0 byte will terminate the string at some point.

> This is a very simple model conceptually, but very cumbersome in practice:

> What if your string is not terminated? If you’re not careful, you can read beyond the intended end of the string, a huge security problem!

This sounds like a problem that transient strings were designed to exemplify. How do they improve on the C model?

-----

I was interested that the short strings use a full 32-bit length field. That's a lot of potential length for a string of at most 12 characters.

If we shaved that down to the four bits necessary to represent a number from 0-12, we'd save 28 bits, which is 3.5 characters. Adding three characters to the content would bring the potential length of a short string up to 15, requiring 0 additional length bits. And we'd have four bits left over.

I assume we aren't worried about this because strings of length 13-15 are already rare and it adds a huge amount of complexity to parsing the string, but it was fun to think about.

Joel had a very nice quote - the whole history of C/C++ is them trying to deal with strings. In a way it is both worrying and encouraging that 50 years in there is still development in the area.