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

Das Problem mit German Strings

polarsignals.com

Post reply on HN
Print view View original

11–20 of 25 posts

Re: Das Problem mit German Strings

#11

Post by kazinator »

> Because it is difficult to assume what the best encoding will be for any given workload, database systems should dynamically choose encodings based on storage and workload characteristics.

It would be better just to take the storage requirement on the chin and not add a gratuitous variation in encoding which will bite you on the ass somehow (or someone else).

As much as possible, pick one way of doing one thing. Your stuff already has thousands of things to do. Each time you do something in two or more ways, you add combinations between that and surrounding things being done in two or more ways.

Re: Das Problem mit German Strings

#12

Post by andai »

mathieuh wrote: post #7
thayne wrote: post #6

So... why are they called Getman strings?

https://datafusion.apache.org/blog/2024/09/13/string-view-ge... > The concept of inlined strings with prefixes (called “German Strings” by Andy Pavlo, in homage to TUM, where the Umbra paper that describes them originated) has been used in many recent database systems (Velox, Polars, DuckDB, CedarDB, etc.) and was introduced to Arrow as a new StringViewArray[^3] type. Arrow’s original StringArray is very memory effic…

Here is the paper in question:

Umbra: A Disk-Based System with In-Memory Performance

https://db.in.tum.de/~freitag/papers/p29-neumann-cidr20.pdf

Section 3.1 covers string handling.

This article (also linked from tfa) explains German strings in more detail.

https://cedardb.com/blog/german_strings

Re: Das Problem mit German Strings

#14

Post by yorwba »

aleph_minus_one wrote: post #8
mathieuh wrote: post #7

Earlier quoted context omitted.

https://datafusion.apache.org/blog/2024/09/13/string-view-ge... > The concept of inlined strings with prefixes (called “German Strings” by Andy Pavlo, in homage to TUM, where the Umbra paper that describes them originated) has been used in many recent database systems (Velox, Polars, DuckDB, CedarDB, etc.) and was introduced to Arrow as a new StringViewArray[^3] type. Arrow’s original StringArray is very memory effic…

> I spent quite some time thinking it had something to do with German’s sometimes-SOV word order. If you refer to subclauses in the German language: here the rule is rather "the finite verb is at the end of the subclause".

It also applies to infitives and participles and the verb in nominalized noun-verb compounds. So the rule is closer to "the verb is at the end of its grammatical unit, except for the finite verb in a main clause, which appears in second position." https://en.wikipedia.org/wiki/V2_word_order

Re: Das Problem mit German Strings

#15

Post by kaladin-jasnah »

aleph_minus_one wrote: post #8
mathieuh wrote: post #7

Earlier quoted context omitted.

https://datafusion.apache.org/blog/2024/09/13/string-view-ge... > The concept of inlined strings with prefixes (called “German Strings” by Andy Pavlo, in homage to TUM, where the Umbra paper that describes them originated) has been used in many recent database systems (Velox, Polars, DuckDB, CedarDB, etc.) and was introduced to Arrow as a new StringViewArray[^3] type. Arrow’s original StringArray is very memory effic…

> I spent quite some time thinking it had something to do with German’s sometimes-SOV word order. If you refer to subclauses in the German language: here the rule is rather "the finite verb is at the end of the subclause".

I think this is also called V2 word order.

Re: Das Problem mit German Strings

#17

Post by aleph_minus_one »

kaladin-jasnah wrote: post #15
aleph_minus_one wrote: post #8

Earlier quoted context omitted.

> I spent quite some time thinking it had something to do with German’s sometimes-SOV word order. If you refer to subclauses in the German language: here the rule is rather "the finite verb is at the end of the subclause".

I think this is also called V2 word order.

V2 word order (finite verb comes second) is what is used in main clauses.

Re: Das Problem mit German Strings

#18

Post by JdeBP »

> Because each element requires at least a 16 byte representation, both tiny and repeated short strings use more memory than they otherwise would.

In a wider view, that depends. If one is using a general-purpose heap for string storage and a 64-bit instruction set architecture, the heap is often aligning and padding out allocations to such multiples already.

Re: Das Problem mit German Strings

#19

Post by chombier »

andai wrote: post #12
mathieuh wrote: post #7

Earlier quoted context omitted.

https://datafusion.apache.org/blog/2024/09/13/string-view-ge... > The concept of inlined strings with prefixes (called “German Strings” by Andy Pavlo, in homage to TUM, where the Umbra paper that describes them originated) has been used in many recent database systems (Velox, Polars, DuckDB, CedarDB, etc.) and was introduced to Arrow as a new StringViewArray[^3] type. Arrow’s original StringArray is very memory effic…

Here is the paper in question: Umbra: A Disk-Based System with In-Memory Performance https://db.in.tum.de/~freitag/papers/p29-neumann-cidr20.pdf Section 3.1 covers string handling. This article (also linked from tfa) explains German strings in more detail. https://cedardb.com/blog/german_strings

my tl;dr: after reading the article:

- two 64-bits words representation

- fixed, 32 bits length

- short strings (- long strings store a 4 byte prefix in-place + pointer to the rest

- two bits are used as flags in the pointer to further optimize some use-cases

Re: Das Problem mit German Strings

#20

Post by kccqzy »

kazinator wrote: post #11

> Because it is difficult to assume what the best encoding will be for any given workload, database systems should dynamically choose encodings based on storage and workload characteristics. It would be better just to take the storage requirement on the chin and not add a gratuitous variation in encoding which will bite you on the ass somehow (or someone else). As much as possible, pick one way of doing one thing. Yo…

The combinatorial explosion problem is nicely solved by defining good interfaces. C++ gives you iterators and algorithms that work on iterators. Clojure has sequence interfaces and functions that work on all sequence types.
Post reply on HN