RMarcus

You can also interpret each value in Perlin noise as a vector in a flow field to make some interesting and smooth animations reminiscent of older MacOS desktop wallpapers: https://rmarcus.info/blog/2018/03/04/perlin-noise.html

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.

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.

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

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.

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.

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)

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

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.

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.

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

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.

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.

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

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.

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

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

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)

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

https://rmarcus.info

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

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!

This would be considered absolutely batshit at all three of the R1 research universities I've been around, which spans a significant range of prestige.

I think it goes to show how much variance there are in PhD programs. I frequently advise undergrads to find the right lab (i.e., a lab that doesn't have such a competitive environment) instead of picking a school based on some other criteria like prestige, but this is far easier in hindsight. I got super lucky -- a small lab with a good advisor.

Maybe (in addition to a strong union) we need a "Yelp for labs" where advisors can be penalized (or recognized) for their behavior. If it were publicly available and student testimonial could be somehow verified and anonymous (potentially impossible), I bet administrators would put at least some pressure on problematic PIs...

Doh! Guess I should've checked. I didn't make it to Rio last year... Figured I was gonna miss a bunch of good stuff.

I've only read part of it, but it seems great so far! I always appreciate the clarity and practicality y'all at the JGL take.

I'm amazed that the implementation was under 1500 LOC! Was that the research prototype or the shipped preview?

Congratulations on the VLDB paper! Hopefully I'll come say "hi" in LA :)

I worked at Los Alamos for several years, and wore a TLD (dosimeter, radiation detection device). The only two times mine was ever "triggered" was when I left it on at the dentist (x-ray) and at the airport (x-ray).

It's interesting to see that these explanations are suggested even when employees say it isn't the case -- when I was "brought in" for my "why did you get this many mrems" talk, I explained about the dentist and the airport, and still got sent home (for a week!) with three doctor's visits and additional screenings. Many anecdotes != data, but when I asked a lot of my friends who worked there, or still work there, they were equally surprised.

None of us knew Chad Walde. It's well-known that different groups at the lab take safety more or less seriously. Which is obviously a huge problem when your dealing with source material.

I do wish the article had a little less of a "nuclear taboo" doom & gloom to it... there's less background radiation in Los Alamos than there is in Los Angeles. And substantially less than areas surrounding coal plants. In my experience, the "fear of the glow" causes people to view nuclear power with extreme suspicion... even when coal & oil plants actively pump far more deadly stuff into the air, far closer to major population centers.

The lab needs to get their shit together, and I believe they've done a lot over the past 10 years... hopefully it keeps moving in the right direction...

It's worth noting that the computer science community (at least in systems and machine learning) have already made some strides in this direction. Systems conferences like VLDB and CIDR post the proceedings online for free (and most ICDE and SIGMOD articles are available through the author's website). In machine learning, almost every conference paper is also available via arXiv.

When a paper is seemingly not available online, I've always gotten a free copy via an email to the author... And then there's sci-hub. It's not the way it should be (i.e. you shouldn't have to hunt around for publicly-funded research), but at least it's something.

It seems to have just come back up... at least my VM is responding.

The move does seem rather troubling, considering the history of Microsoft. Linux seems like it's a little too big for "extinguish," and th GPLv2 should provide some defense against nefarious "extend"ing...

But then again, I wonder how many now-defunct open standards and projects thought the same thing.

Very cool! I wrote something similar, but it only renders lines. https://rmarcus.info/blog/2017/10/23/humanlines.html

I have no idea :). I don't think this approach is state of the art, but I think the advantages are that RFs are lightweight when compared to ANNs.