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

Why Polars rewrote its Arrow string data type

pola.rs

Post reply on HN
Print view View original

21–30 of 70 posts

Re: Why Polars rewrote its Arrow string data type

#21

Post by lor_louis »

o11c wrote: post #15
lor_louis wrote: post #4

Earlier quoted context omitted.

It looks a lot like cedarDB's "german strings". https://cedardb.com/blog/german_strings/ > You could probably write a C++ implementation based on the article. Note that it's not all that useful if you don't plan on searching for text based on their prefix. From my understanding, this is mostly a better way to store SStables in RAM/partially on disk if you mmap.

Hm, both the main article and your link are wasteful for strings of length 13-15, which are still pretty common. As a rule for SSO, if you're already take up the bytes unconditionally, it's going to be worth complexifying your "size" calculation to squeeze a little more into the no-alloc case. That said, note that there are a lot of strings around 20 bytes (stringified 64-bit integers or floats), so pushing to 24-1 i…

Yeah I tend to work with strings data around the 15 to 30 ish char count so I'm also sceptical of german strings when it comes to raw memory usage. What really interests me, is that in theory, an SSTable built from German Strings that point into a larger text buffer further down could result in less pagefaults during a binary search? Maybe?

Re: Why Polars rewrote its Arrow string data type

#22

Post by o11c »

lor_louis wrote: post #21
o11c wrote: post #15

Earlier quoted context omitted.

Hm, both the main article and your link are wasteful for strings of length 13-15, which are still pretty common. As a rule for SSO, if you're already take up the bytes unconditionally, it's going to be worth complexifying your "size" calculation to squeeze a little more into the no-alloc case. That said, note that there are a lot of strings around 20 bytes (stringified 64-bit integers or floats), so pushing to 24-1 i…

Yeah I tend to work with strings data around the 15 to 30 ish char count so I'm also sceptical of german strings when it comes to raw memory usage. What really interests me, is that in theory, an SSTable built from German Strings that point into a larger text buffer further down could result in less pagefaults during a binary search? Maybe?

I mean, if you're doing binary searches, the first thing to do is to switch to Eytzinger searches (at least for the prefixes; it's unclear if Eytzing-sorting large strings matters) which are much more cache friendly. (incidentally, Eytzinger was Austrian, not German - same language though!)

Second, I'd probably switch to struct-of-array instead of array-of-struct, since the search part only needs the (head of the) key. Possibly some trie-like logic would also help (that is, avoid duplicating the common prefix, instead point to an array of continuations rather than a single one), but beware of costly indirections.

Third, I would make sure the user is able to specify the SSO limit, since different domains will have different requirements.

Fourth ... if you're column-oriented (or for simple data in the first place), consider implicit union of different `Set` (or whatever) implementations. For example, store all short strings in one array, and all long strings in a different array.

Re: Why Polars rewrote its Arrow string data type

#23

Post by throwaway48540 »

tialaramex wrote: post #16
charliermarsh wrote: post #14

Earlier quoted context omitted.

Was this section removed? I'm not seeing it in the linked post.

It seems to be a quote from https://cedardb.com/blog/german_strings/ which is about this German Strings type (implemented in Polars) But yeah, it's pretty ignorant to assume Rust can't do this since the best available examples (as with many things) are in Rust. CompactString is really nice. On a typical modern (64-bit) computer CompactString takes 24 bytes and holds up to 24 bytes of UTF-8 text inline, while also hav…

I remember some C++ colleagues raving on about the standard library having anything and everything they might ever need. Makes sense in a world without sane package managers and package registries, but that mindset just doesn't carry over.

Re: Why Polars rewrote its Arrow string data type

#25

Post by lor_louis »

o11c wrote: post #22
lor_louis wrote: post #21

Earlier quoted context omitted.

Yeah I tend to work with strings data around the 15 to 30 ish char count so I'm also sceptical of german strings when it comes to raw memory usage. What really interests me, is that in theory, an SSTable built from German Strings that point into a larger text buffer further down could result in less pagefaults during a binary search? Maybe?

I mean, if you're doing binary searches, the first thing to do is to switch to Eytzinger searches (at least for the prefixes; it's unclear if Eytzing-sorting large strings matters) which are much more cache friendly. (incidentally, Eytzinger was Austrian, not German - same language though!) Second, I'd probably switch to struct-of-array instead of array-of-struct, since the search part only needs the (head of the) ke…

I did not know about Eytzing-sorting, I'll look into it after my vacation, thanks! And yeah our current system is column oriented, and I already tried most of your recommendations (including tries) but the biggest limitation we face is that different kinds of queries will be better served by different kinds of data structures but you can only store a few of them on disk before the cost to index becomes too big.

Re: Why Polars rewrote its Arrow string data type

#26

Post by lmeyerov »

I wonder if something like arrow's custom extension types mechanism would streamline building novel data representations without full forks? It may highlight gaps in the extension mechanism

For similar reasons, we've been curious about new compression modes on indexes

Re: Why Polars rewrote its Arrow string data type

#27

Post by jtrueb »

Rygian wrote: post #8

> “short string optimization”: A short enough string can be stored “in place” [...] An optimization that’s impossible in Rust, by the way ;). Author is not aware of https://docs.rs/compact_str/latest/compact_str/ or https://github.com/bodil/smartstring

This is false. The polars api has used smart string for a long time.

https://github.com/pola-rs/polars/blob/32a2325b55f9bce81d019...

Re: Why Polars rewrote its Arrow string data type

#28

Post by o11c »

lor_louis wrote: post #25
o11c wrote: post #22

Earlier quoted context omitted.

I mean, if you're doing binary searches, the first thing to do is to switch to Eytzinger searches (at least for the prefixes; it's unclear if Eytzing-sorting large strings matters) which are much more cache friendly. (incidentally, Eytzinger was Austrian, not German - same language though!) Second, I'd probably switch to struct-of-array instead of array-of-struct, since the search part only needs the (head of the) ke…

I did not know about Eytzing-sorting, I'll look into it after my vacation, thanks! And yeah our current system is column oriented, and I already tried most of your recommendations (including tries) but the biggest limitation we face is that different kinds of queries will be better served by different kinds of data structures but you can only store a few of them on disk before the cost to index becomes too big.

Whoops, I dropped the "er" the second time. I've also seen it labeled "cache-friendly binary sort", and sometimes the Breadth-First-Search aspect is played up (but that's unsearchable).

Logical-order (in-order DFS) iteration is obvious and trivial (though a lot of tasks are fine with physical-order (BFS) iteration. Beware that some tasks that nominally don't care about input order perform much better on already-sorted input though).

Conversion between logical index and physical index (if you need it - chances are you don't) can still be done efficiently, but requires some (fun!) thought especially for the non-power-of-2 tail.

Explicit prefetching is trivial to arrange for k-great grandchildren if needed (though the width of course grows exponentially). Using an n-ary rather than binary tree is possible but I'm not sure of the cache effects in practice. Switching to linear search just at the last level may be worth it? All of this means more complex logic though.

Re: Why Polars rewrote its Arrow string data type

#29

Post by adrianN »

throwaway48540 wrote: post #23
tialaramex wrote: post #16

Earlier quoted context omitted.

It seems to be a quote from https://cedardb.com/blog/german_strings/ which is about this German Strings type (implemented in Polars) But yeah, it's pretty ignorant to assume Rust can't do this since the best available examples (as with many things) are in Rust. CompactString is really nice. On a typical modern (64-bit) computer CompactString takes 24 bytes and holds up to 24 bytes of UTF-8 text inline, while also hav…

I remember some C++ colleagues raving on about the standard library having anything and everything they might ever need. Makes sense in a world without sane package managers and package registries, but that mindset just doesn't carry over.

That development is quite recent. The stdlib used to be very barebones. It still is compared to for example the Python one.

Re: Why Polars rewrote its Arrow string data type

#30

Post by kristianp »

Don't you lose the in-memory interop with other libraries by doing this? I'm thinking that duckdb will no longer be able to read polars data that has been loaded into memory, as it can currently do, due to duckdb supporting Arrow. Isn't the benefit of arrow that it's supported by many languages and libraries as a standard?

Will there be an option to use the "compatible" string format?

Post reply on HN