RMarcus · HackerTrans

il y a 3 moisdiscuss

I've got emacs keybinds in my muscle memory and Zed works well for me, although there's no kill ring and the macro system is nothing like emacs. The former will be added at some point (there's an open PR), but I do not expect the latter will ever be comparable.

RMarcus

il y a 2 ansdiscuss

This is awesome, thanks for creating this. I've had to write some absolutely wonky scripts to dump a PostgreSQL database into Parquet, or read a Parquet file into PostgreSQL. Normally some terrible combination of psycopg and pyarrow, which worked, but it was ad-hoc and slightly different every time.

A lot of other commenters are talking about `pg_duckdb` which maybe also could've solved my problem, but this looks quite simple and clean.

I hope for some kind of near-term future where there's some standardish analytics-friendly data archival format. I think Parquet is the closest thing we have now.

RMarcus

il y a 2 ansdiscuss

Looks like he got a master's degree from UIUC and did some research on FFT implementations. Seems to have been successful. What makes you say he was 'considered a "bad student"'?

(This is a genuine question. I've never met Alex in person, but if an applicant to my lab spent their free time diving into SIMD implementations and breaking records for computing mathematical constants, I'd rush to hire them. Not that either of those two things is a requirement, of course.)

RMarcus

il y a 2 ansdiscuss

Depends!

If you double the number of keys and you double the number of bins (load factor stays constant), then the problem becomes much worse very quickly.

If you double the number of keys and you double the size of each bin (load factor stays constant), then the problem diminishes as you suggest. BUT, larger bins are more sensitive to changes in load factor.

The sibling comment ( https://news.ycombinator.com/item?id=40415826 ) does a good job of summarizing how post-2018 systems handle this issue.

RMarcus

il y a 2 ansdiscuss

This is my post from 2018 (I didn't submit it to HN), and it could definitely use a "here's what practical systems do" update! I'll put it on the TODO list...

Your point about systems dealing with a relatively small number of large objects vs. small objects also makes sense: this is essentially the "cost" of an overflow (4kb spills once in a blue moon? Oh well, handle that as a special case. 4TB spills once in a blue moon? The system might crash). This is more obvious, as you also point out, in load balancing.

One aspect I found very counter-intuitive: before this investigation, I would've guessed that having a large number of large bins makes overflow increasingly unlikely. This is only partially true: more bins is obviously good, but larger bins are actually more sensitive to changes in load factor!

Overall, I think you are right that this is not really a concern in modern systems today. Compared to Dynamo, I still think Vimeo's solution (linked at the bottom of the post) is both intuitive and low-complexity. But regardless, more of an interesting mathematical diversion than a practical systems concern these days.

RMarcus

il y a 2 ansdiscuss

I'm curious to hear a bit more of your opinion. For example, I'm surprised that syscall latency is something near the top of your list. I think the usual wisdom in the DB community is that the cost models are mostly fine, but the cardinality estimation is really bad.

In terms of the deferred / alternative planning, do you think adaptive query execution is a reasonable way to achieve this? It certainly allows for information early in the query execution to impact later plans. My worry with these approaches is that if you get the first couple of joins wrong (which is not uncommon), unless you have something like Yannakakis/SIPs, you still can't recover.

I am obviously biased on the whole "ML for query optimization" thing. One thing I would note is that every "ML for planning" approach I've seen does, under the hood, use ML for cost discovery/estimation. These approaches are just trying to balance the data they collect (exploration) with the quality of the plans they produce (exploitation). Interestingly, if you use ML in a way that is completely removed from planning, you actually get worse query plans despite more accurate estimates: https://people.csail.mit.edu/tatbul/publications/flowloss_vl... (again, I've got a horse in this race, so my opinion should come with a side of salt :D)

RMarcus

il y a 2 ansdiscuss

PostgreSQL has coarse-grain query hints (like `enable_hashjoin`), and the excellent `pg_hint_plan` extension allows you to specify a complete or partial execution plan: https://github.com/ossc-db/pg_hint_plan

RMarcus

il y a 2 ansdiscuss

It is certainly possible that the plans are similar, and that improvements to the execution engine are being measured. The join order benchmark was designed to test optimizer quality. It is worth noting that in addition to trying to measure the number of pages read from disk, the PG optimizer also tries to reduce the number of tuples examined by the CPU, the number of predicate evaluations, etc. All these numbers are rolled up into a "cost," which is the function that the optimizer minimizes.

It is also true that measuring cold cache and warm cache performance can produce different results, and this experiment is certainly in the warm cache scenario. But, the cold cache scenario suffers from the problem you mention as well: an improvement to PG's B-tree that saves a few IOs will dominate any kind of CPU-based improvement (at least at the data size of the join order benchmark).

FWIW, the plan for the query with the P90 latency changes from a plan that uses loop and merge join in PG8.4 to a plan that uses hash join in PG16 (where it is no longer the P90 query), which is at least some evidence of optimizer improvements.

RMarcus

il y a 2 ansdiscuss

I totally agree -- I picked the latest version for each major version using the semver interpretation of the version numbers, which is not how PostgreSQL has traditionally done major version numbers (i.e., PG 8.2 and 8.1 are different major versions, but I interpreted the version numbers as if they were minor versions).

The main reason I did this was to reduce the number of versions I had to test, but I agree a more complete analysis would test each (true) major version.

RMarcus

il y a 2 ansdiscuss

I'm the author of the blog post.

"Tail latency has improved by YMMV for everything else" => yes, I think that's a valid (but conservative) read. Of course, in many (most?) applications, tail latency is very important. Tail latency also tends to be the thing that optimizer engineers target (i.e., reduce the runtime of the longest running query).

RMarcus

il y a 2 ansdiscuss

This is the main motivation behind learned "steering" query optimizers: even if a DBA finds the right hint for a query, it is difficult to track that hint through data changes, future DB versions, and even query changes (e.g., if you add another condition to the WHERE clause, should you keep the hints or drop them?). Turns out, with a little bit of systems work, ML models can do a reasonably good job of selecting a good hint for a particular query plan.

RMarcus

il y a 2 ansdiscuss

Just wanted to say thank you! This extension was critical to a bunch of my research (and now my lab's research as well). Being able to control fine-grained elements of each plan while letting the PG planner "do the rest" has saved me personally probably 100s of hours of work.

RMarcus

il y a 3 ansdiscuss

Ah, I missed that this requires WAL mode -- indeed, if WAL is used, one transaction should always be able to make progress.

RMarcus

il y a 3 ansdiscuss

My reading is that no deadlocks should be possible since there is only one lock (pages are "locked" optimistically, meaning that the tx is aborted if the page has changed). "Live locks" are possible, where two repeatedly-reissued transactions cause each other to abort forever.

RMarcus

il y a 4 ansdiscuss

Thanks for the first-hand information! I was also curious about this.

> This is not a course everyone enrolls in.

This is the ticket -- at both the University of Arizona and MIT, I've seen a group of folks graduate with a CS degree after taking OS, compilers, databases, and abstract algebra. Another another group of folks graduated after taking HCI, software engineering, design, and psychology courses. The two groups had some baseline skills (all knew the basic data structures and algorithms), but otherwise appeared quite distinct.

I don't know how to phrase this formally, but I think some statement like the following is true: within-university variance is higher than between-university variance.

(When I was younger, I had strong opinions on which one of these groups were "real" computer scientists. This was a very unfortunate way of thinking that prevented me from talking to folks who I later realized were some of the smartest around. I wish someone had corrected me sooner -- solving a problem with inputs/outputs well-defined enough to apply "rigorous" techniques doesn't make those problems inherently valuable or "harder" than others. God gave all the easy problems to the physicists.)

RMarcus

il y a 5 ansdiscuss

We recently published a comparison of learned indexes (including RadixSpline and the PGM index posted yesterday)in VLDB: https://vldb.org/pvldb/vol14/p1-marcus.pdf

RMarcus

il y a 5 ansdiscuss

We produced a detailed comparison of such "fitting" and "learning" techniques, available here: https://vldb.org/pvldb/vol14/p1-marcus.pdf

(Thomas Neumann, one of authors of the blog post, is a co-author of the linked paper)

RMarcus

il y a 5 ansdiscuss

Check out work by Jialin Ding and Vikram Nathan, they both work on multi-dimensional learned index structures.

https://arxiv.org/pdf/2006.13282.pdf

RMarcus

il y a 6 ansdiscuss

https://rmarcus.info

I mostly post interactive or semi-narrative explanations of technical topics I find interesting. 1-3 posts per year.

RMarcus

il y a 7 ansdiscuss

My experience is entirely different -- writing HPC code for supercomputers at Los Alamos National Lab (on and off for 5 years) made me a true Rust believer.

One of the things I spent the most time on with Fortran / C++ codes was debugging wrong-result bugs. About 90% of the time, the wrong result came from some edge-case where an array was wrongly freed too early, an array was accessed out of scope, or a race condition caused an array member to be updated in a non-deterministic manner. Each of these bugs required hours of debugging and was a huge time sink. Once I started working with Rust, I never encountered any of these bugs. After about a year of fighting the borrow-checker, I feel my overall efficiency has greatly improved.

Now, when I go back and write or read C++ code, patterns that the Rust compiler would yell about jump out at me (multiple unprotected mutable references, cloning unique pointers), and I find these are generally a source of the bug I'm hunting. Like sibling comments point out, a lot (but not all) of the things Rust stops you from doing are just bad practice anyway.

Of course, for GPGPU stuff I have to write CUDA or OpenCL, but those are generally small, compact kernels that are easy to reason about end to end.

I'm not suggesting that you are doing this, but for me, I initially resisted Rust for a long time. Rust seemed extremely complex, and whenever I'd try to use it I would run into a wall. The loud Rust community talking about how great Rust was and how easy it was to use once you "got it" made me feel stupid. Instead of being humble, I became arrogant, and I'd say things like "Rust is too restrictive for the high performance applications I care about" or "I write code that Rust would find unsafe but is actually super well-tuned for this architecture." For me, these were mental excuses I made because I was unable to accept that I was having such a hard time with Rust, and I considered myself a "high performance computing software engineer!"

It took me way longer than most to "get" Rust -- over a year of repeatedly forcing myself to learn and stumble through compiler errors before things started to click. A year after that, and I'm still frequently surprised by certain aspects of the language ("really? I need a & in that match statement?" and "oh god, what does this lifetime and trait bound mean..." are two of the most common). But the parts of Rust that have clicked for me (the borrow checker and associated lifetime mechanics) make Rust very enjoyable to write.

Again, I'm not suggesting that you are falling into the same trap I did, I just wanted to post this to encourage anyone else in the "banging their head against the Rust compiler" stage to power through!