Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Why German Strings Are Everywhere?

cedardb.com

Post reply on HN
Print view View original

11–20 of 58 posts

Re: Why German Strings Are Everywhere?

#11

Post by StopDisinfo910 »

jmclnx wrote: post #3

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

Not really, no.

The main difference is that you don't know how many code points you have in the prefix as they use variable encoding so it can be up to four but as little as one. I imagine the choice of four bytes for the prefix was actually done specifically for this reason. That's the maximum length of a UTF-8 code point.

The length is not the number of characters anymore but just the size of the string.

Apart from that, it should work exactly the same.

Re: Why German Strings Are Everywhere?

#12

Post by xnorswap »

WaitWaitWha wrote: post #10

> 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.

That's not what it's doing though.

Pascal strings are: { length, pointer }

In these strings:

For short strings it's storing:

  { length, string value}
for longer strings, it's storing

  {length, prefix, class, pointer }

Re: Why German Strings Are Everywhere?

#14

Post by f1shy »

WaitWaitWha wrote: post #10

> 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.

I think is about the kind of union they use, to store it differently depending on the string length, not the fact of length+data. Anyway is/was also nothing remotely new (the idea) as many lisp and scheme implementations have done so for strings and numbers basically for ages.

Re: Why German Strings Are Everywhere?

#15

Post by afandian »

WaitWaitWha wrote: post #10

> 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.

Storing the prefix and the tagged union of pointer and inline data structure is big difference to Pascal strings though.

Re: Why German Strings Are Everywhere?

#16

Post by mau »

WaitWaitWha wrote: post #10

> 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.

German-style strings is a way to store array of strings for columnar dbs. The idea is to have an array of metadata. Metadata has a fixed size (16 bytes) The metadata includes the string length and either a pair of pointer + string prefix or the full string for short strings. For some operations the string prefix is enough in many cases avoiding the indirection.

This is different from Pascal strings.

Re: Why German Strings Are Everywhere?

#18

Post by maweki »

f1shy wrote: post #5
ahartmetz wrote: post #2

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.

I knew the C++ strings were optimized so. I do not like calling them "German". First time I see them called so (I know it, you can search yourself, as SSO -short string opt.), and looks as some kind of nationalist pride thing to me. Is certainly not a unique or new idea, many scheme/lisps implementations do that for strings AND numbers. Downvotes coming from other connationals :) love you! I know… never say anything…

What do you like to call Hungarian notation?

Re: Why German Strings Are Everywhere?

#19

Post by masklinn »

f1shy wrote: post #5
ahartmetz wrote: post #2

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.

I knew the C++ strings were optimized so. I do not like calling them "German". First time I see them called so (I know it, you can search yourself, as SSO -short string opt.), and looks as some kind of nationalist pride thing to me. Is certainly not a unique or new idea, many scheme/lisps implementations do that for strings AND numbers. Downvotes coming from other connationals :) love you! I know… never say anything…

C++ strings are not "optimized so". C++ strings (generally) do SSO (up to 23 bytes depending on implementation), these also do SSO but only 8 bytes (to a total of 12), the first 4 bytes are always stored inline for fast lookup even when the rest of the string is on the heap (in which case they're duplicated), and the strings are limited to 4GB (32 bits length). IIRC they also have a bunch of other limitations (e.g. they're not really extensible, by design).

Which is why they're "everywhere"... in databases, especially columnar storage.

Re: Why German Strings Are Everywhere?

#20

Post by aDyslecticCrow »

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.

Post reply on HN