1,135 karma · joined December 20, 2012
@petervgeoghegan on Twitter.
I suggest testing the same workload with your existing hash indexes replaced with equivalent B-Trees.
[1] https://github.com/postgres/postgres/blob/master/src/backend...
No, it isn't. PostgreSQL 18 added support for index skip scan:
https://youtu.be/RTXeA5svapg?si=_6q3mj1sJL8oLEWC&t=1366
It's actually possible to use a multicolumn index with a query that only has operators on its lower-order columns in earlier versions. But that requires a full index scan, which is usually very inefficient.
That only happens when it is possible to give back space to the OS filesystem using relation truncation in the first place -- which isn't all that common (it's generally only seen when there are bulk range deletions that leave lots of contiguous empty space at the end of a table/heap structure). But you said that this is an append-only workload.
This behavior can be disabled by setting the vacuum_truncate table storage parameter to "off". This is useful with workloads where relation truncation is disruptive (truncation needs to acquire a very heavyweight table lock).
> Is there no way to automatically clean up indexes then?
What I meant was that indexes do not support relation truncation. It follows that the amount of space used for an index (from the point of view of the OS) cannot ever go down, barring a REINDEX or a VACUUM FULL.
This does not mean that we cannot reuse space for previously freed/deleted pages (as long as we're reusing that space for the same index). Nor does it mean that "clean up" isn't possible in any general sense.
It's possible to recycle pages within indexes that have some churn (e.g., with workloads that use bulk range deletions). But it's not possible for indexes to shrink on their own, in a way that can be observed by monitoring the output of psql's "\di+" command. For that you'd need to REINDEX or run VACUUM FULL.
I've done extensive work on improving the Postgres B-Tree code, over quite a number of releases. I'm not aware of any problems with high-insert workloads in particular. I have personally fixed a number of subtle issues that could lead to lower space utilization with such workloads [1][2] in the past, though.
if there's a remaining problem in this area, then I'd very much like to know about it.
[1] https://www.youtube.com/watch?v=p5RaATILoiE [2] https://speakerdeck.com/peterg/nbtree-arch-pgcon
This is the most important individual point that the blog post makes in my view. Lots of Postgres users are left with the wrong general idea about how things in this area work (e.g., the locking implications of autovacuum), just because they missed this one subtlety.
I'm not sure what can be done about that. It seems like Postgres could do a better job of highlighting when an interaction between two disparate transactions/sessions causes disruption.
I don't think that it's possible to test optimizer quality in isolation -- not really, not if it's to be in any way practical. Many (most?) individual improvements to the optimizer are hopelessly intertwined with executor enhancements. This is usually fairly obvious, because the same commit changes both the optimizer and the executor together. Sometimes it's much less obvious, though, because its more a case of the optimizer and executor coevolving.
It's probably still the case that a lot of the improvements seen here are pure executor enhancements, but I can't say that I'm very confident about that. (As the main person behind those B-Tree IO savings you might expect me to have more confidence than that, but I find it horribly difficult to tease these issues apart while keeping the discussion high level/relevant.)
What compiler might that be?
It's true that MSVC doesn't have an equivalent of -fno-strict-aliasing, but that's because it just doesn't apply optimizations that assume strict aliasing in the first place. Admittedly the picture around signed overflow is more complicated, but it's essentially the same story.
> Using these C dialects is a perfectly sensible thing to do, as long as you understand that this is what you are doing.
I suppose that they technically are C dialects, but it seem more than a bit absurd to put it like that -- at least to me. By that standard the Linux kernel isn't written in C. And Firefox isn't written in C++. Postgres also wouldn't count as according-to-hoyle C under your definition. Even though Postgres compiles when -fwrapv and -fno-strict-aliasing are removed, and still passes all tests.
The implication of what you're saying seems to be that all of these open source projects each independently decided to "go there own way". I find it far more natural to explain the situation as one of GCC diverging when it decided to make -fstrict-aliasing the default around 15 years ago.
It's difficult to get into Postgres development, but that has little to do with C expertise. The hard part is having the right domain expertise. Building up general familiarity with the system just takes a long time.
That's not the kind of thing that the standard takes a position on, for a variety of reasons. In general, it says very little about concurrency control/isolation. And what little is does say is all very abstract.
For whatever reason, a lot of people believe that MERGE promises something over and above what using multiple INSERT, UPDATE, and DELETE statements will promise. But that simply isn't true. The standard doesn't say anything that even vaguely suggests otherwise. Same is true of both the SQL Server MERGE docs, and the Oracle MERGE docs.
This is incorrect. To quote the Postgres MERGE docs:
"When MERGE is run concurrently with other commands that modify the target table, the usual transaction isolation rules apply; see Section 13.2 for an explanation on the behavior at each isolation level. You may also wish to consider using INSERT ... ON CONFLICT as an alternative statement which offers the ability to run an UPDATE if a concurrent INSERT occurs. There are a variety of differences and restrictions between the two statement types and they are not interchangeable."
MERGE can give duplicate violation errors when concurrent inserts take place (at the default READ COMMITTED isolation level). MERGE is no more capable of avoiding these sorts of race conditions than totally naively application code. In short, upserting is precisely what you're not supposed to use MERGE for -- ON CONFLICT is expressly designed for that use case.
I really don't know what you're arguing against. I never questioned the general usefulness of an abstract machine. I merely pointed out that a large amount of important C code exists that is in tension with the idea that of an all important abstract machine. This is an empirical fact. Is it not?
You are free to interpret this body of C code as "not true ISO C", I suppose. Kind of like how the C standard is free to remove integer overflow checks in the presence of undefined behavior.
"C has been characterized (both admiringly and invidiously) as a portable assembly language" - Dennis Ritchie
The idea of C as a portable assembler is not without its problems, to be sure -- it is an oxymoron at worst, and a squishy idea at best. But the tendency of compiler people to refuse to take the idea seriously, even for a second, just seems odd. The Linux kernel's memory-barriers.txt famously starts out by saying:
"Some doubts may be resolved by referring to the formal memory consistency model and related documentation at tools/memory-model/. Nevertheless, even this memory model should be viewed as the collective opinion of its maintainers rather than as an infallible oracle."
Isn't that consistent with the general idea of a portable assembler?
> I agree that undefined behavior is a silly concept but that's the fault of the standard, not of compilers.
The people that work on compilers have significant overlap with the people that work on the standard. They certainly seem to share the same culture.
Even if we could say for sure that x86 has been disproportionately affected by speculative execution bugs (which already seems dubious), that could easily be due to a kind of selection bias. Presumably security researchers as a group more or less focus on the most popular and relevant ISAs/microarchitectures.
I think that you're vastly overestimating the importance C as an abstract specification and as a community of programmers with a coherent set of shared goals. You're also too focussed on performance. There is a practical sense in which C will tend to perform better for certain tasks, but it doesn't necessarily have all that much to do with the language itself. It's the whole ecosystem. And yes, path dependence matters. It isn't intrinsically true that it has to be this way, a little like how it isn't intrinsically true that we have to use QWERTY keyboards instead of Dvorak keyboards.
It's not that there aren't lots of serious problems with C -- there certainly are. It's that those problems are systemic problems; they're more the result of a huge number of people making a huge number of pragmatic decisions, day after day, year after year -- and the sequence matters. Many of these people are not computer programmers. Many are from hardware vendors that have people that sit on standards bodies for everything from NVMe to RISC-V. These are all people that more or less all look at the world as it actually is today, and build on that incrementally. They build accretions on top of accretions.
There are many glaring contradictions in C. Depending on who you ask, it's either a portable assembler, or a programming language that targets something called the C abstract machine. And neither party seems to want to even address the glaring inconsistency! This is a cabal that seems to have a real problem with staying on message, don't you think?
I make only very modest claims here. I'm not saying that this is good or inevitable; only that it is the best explanation I am aware of. I'm definitely not saying that we can't do better. Only that I believe that the current state of affairs works as well as it does (i.e. barely adequately) because in the end it's very difficult to get an enormous number of people separated by time and space to agree on anything at all. C more or less remains the defacto standard when operating at the hardware/software interface not in spite of its glaring contradictions. It's because of them.
It's all but impossible for me to prove any of this, because I'm describing diffuse, emergent behavior -- what I'm arguing is that things tend to take the path of least resistance, in an environment where companies come and go, and short term business considerations hold sway. I might be willing to put more effort into convincing you of this if I really was the C zealot that you imagine me to be, but I'm not.
Okay!
I don't think that that's true. I find the explanation given by "Some Were Meant for C" [1] far more plausible.
But leaving that aside: what does that have to do with anything that I said? And might I be permitted to make a point about GCC that is wholly unrelated to Rust, without getting a generic lecture about memory safety?
> I was expecting it would be easy to find benchmarks trying the same C or C++ code with GCC, Clang and MSVC and giving performance numbers, but I didn't find that. Maybe it exists and I can be directed to it ?
I don't doubt that there are silly compiler microbenchmarks somewhere. And I know for sure that strict aliasing could in principle make a huge difference. For example, an autovectorization optimization could take place once the compiler had leeway to applying an assumption about two pointers not aliasing, but not otherwise.
However, in practice it doesn't seem to make all that much difference for most kinds of C programs, for all kinds of reasons that are very difficult to pin down. The big exceptions generally involve numerical code, which is why Fortran has always tended to be faster than C for numerical applications. At least it definitely was for most of the history of both languages. (Yes, C was openly understood to be slower than Fortran in cases that were important for Fortran 40+ years ago. I refer you to [1] once more.)
[1] https://www.cs.kent.ac.uk/people/staff/srk21//research/paper...
That's probably true, but compiler people do themselves no favors by pretending that these things come from some higher echelon, that they couldn't possibly presume to question. It just doesn't pass the smell test.
The fact that -wfrapv and -Wno-strict-aliasing are not the defaults in GCC is a choice made by GCC. A bad choice, in my opinion. MSVC made different choices, and lots of people still use it, so there is an existence proof that you can just not do these things on a mainstream compiler. (In fact, MSVC doesn't even offer type-based aliasing as an option that can be enabled, last I checked.)
I know what you mean, but I don't think that that quite captures it. It's more like this: planners are built on a set of assumptions that are often pretty far from robust, but nevertheless work adequately well in almost all cases. Including many cases where the assumptions haven't been met!
The best example is the standard assumption that multiple conditions/columns are independent of each other -- all optimizers make this assumption (some can be coxed into recognizing specific exceptions). This is obviously not true much of the time, even with a well normalized schema. Because: why would it be?
All kinds of correlations naturally appear in real data. It's just that it mostly doesn't cause huge problems most of the time, for messy reasons that can't quite be pinned down. You have to get unlucky; the correlations usually have to be very high, and the planner makes completely the wrong inference for the actual query that you ran (not some hypothetical other query). The planner only has to have approximately the right idea to discover the cheapest plan. And the planner doesn't have to discover the cheapest plan in many cases -- there may be quite a few adequate plans (it's really hard to generalize, but that's often true).
Overall, the fact that cost-based optimizers work as well as they do seems quite surprising to me.
I agree. I wonder how feasible it is to separate the two, though. Not because it seems as if there is some unavoidable trade-off to be made (if that was it then somebody would have found a relatively crisp definition of said trade-off). I suspect that it's best understood as an emergent phenomenon.
Consider the LINUX KERNEL MEMORY BARRIERS readme [1], which states very clearly: "Nevertheless, even this memory model should be viewed as the collective opinion of its maintainers rather than as an infallible oracle". And yet some people persist with the belief that such an Oracle must really be possible. Oracles are abstract concepts.
C doesn't persist despite its contradictions. It persists because of them.
I'm not claiming that this is good or bad. Just that it's the simplest explanation that I can think of.
[1] https://www.kernel.org/doc/Documentation/memory-barriers.txt
Are you really, though? I would argue that it's a matter of perspective and/or semantics.
The Linux kernel is built with -fwrapv and with -fno-strict-aliasing, and uses idioms that depend on it directly. We can surmise from that that the kernel must be:
1. Exhibiting undefined behavior (according to a literal interpretation of the standard)
OR:
2. Not written in C.
Either way, it's quite reasonable to wonder just how much practical applicability your statement really has in any given situation -- since you didn't have any caveats. It's not as if the kernel is some esoteric, obscure case; it's arguably the single most important C codebase in the world. Plus there are plenty of other big C codebases that take the same approach besides Linux.
Lots of compiler people seem to take the same hard line on the issue -- "the C abstract machine" and whatnot. It always surprises me, because it seems to presuppose that the only thing that matters is what the ISO standard says. The actual experience of people working on large C codebases doesn't seem to even get acknowledged. Nor does the fact that the committee and the people that work on compilers have significant overlap.
I'm not claiming that "low-level C hackers are right and the compiler people are wrong". I'm merely pointing out that there is a vast cultural chasm that just doesn't seem to be acknowledged.
I never said anything about workloads. All I said was that your statements about B+Trees having dwindling usage are clearly false.
If you make a claim that is self-evidently bogus, then you shouldn't expect anything else that you may have said at the same time to be taken seriously.
The fact that MyRocks doesn't use B+Trees seems like half the story. Less than half, even. The really important difference between MyRocks and InnoDB is that MyRocks uses log-structured storage (one LSM tree for everything), while InnoDB uses a traditional write-ahead log with checkpoints, and with logical UNDO. There are multiple dimensions to optimize here, not just a single dimension. Focusing only on time/speed is much too reductive. In fact, Facebook themselves have said that they didn't set out to improve performance as such by adopting MyRocks. The actual goal was price/performance, particularly better write amplification and space amplification.
You said that B-Trees "use in indexing has dwindled with time". This is demonstrably false.
> Back then I used them ubiquitously but I honestly don't remember the last time I've seen one in a new design.
Even if that was true (which it definitely isn't), why would anybody judge the commercial or scientific relevance of B-Trees by looking at what new systems do? There are very few new systems that are intended to be competitive as general purpose systems, which is where most of the market is.
You still haven't actually named a single example of a "modern database kernel" that exemplifies what you're talking about.
This is pure nonsense. B+Trees are used extensively and by default by 5 out of 5 of the top database systems, according to db-engines.com.
I am an expert on the subject matter, and I don't think that the overall approach is questionable. The approach that the author took seems fine to me.
The definition of certain basic concepts like 'consistency' is even confusing to experts at times. This is made all the more confusing by introducing concepts from the distributed systems world, where consistency is often understood to mean something else.
Here's an example of that that I'm familiar with, where an expert admits to confusion about the basic definition of consistency in the sense that it appears in ACID:
https://queue.acm.org/detail.cfm?id=3469647
This is a person that is a longtime peer of the people that invented the concepts!
Not trying to rigorously define these things makes a great deal of sense in the context of a high level overview. Getting the general idea across is far more important.
I expect it to get worse before it gets better. I imagine that people in this situation are typically overwhelmed by the shame.
I would also venture to guess that specimens like Michael Saylor don't feel any shame whatsoever, despite making statements about Bitcoin intended to convince ordinary retail investors to go all in at the height of the bubble: