Speeding up sort performance in Postgres 15
citusdata.com
citusdata.com
>PostgreSQL 15 introduces the jsonlog format for logging. This allows PostgreSQL logs to be consumed by many programs that perform structured log aggregation and analysis.
>pg_basebackup, a utility used to take full backups of a PostgreSQL cluster, now supports server-side compression using Gzip, LZ4, or Zstandard compression.
>This includes the introduction of parallelization for SELECT DISTINCT statements and improvements in performance to window functions that use row_number(), rank(), and count().
>PostgreSQL 15 builds on its existing support for the SQL/JSON path language by including more standard SQL/JSON functions. These include SQL/JSON constructors, query / introspection functions, and the ability to convert JSON data into a table.
I'm also looking forward to the \copy improvements, especially around loading data into PG.
- We get a lot of mileage out of DISTINCT ON to get the most recent version of a row for some subset of columns. I think this a different use case than what you refer to.
- We typically use DISTINCT to get PKs for a table when starting from another table. Like, find all user IDs that commented on a given story by looking at the join table.
SELECT DISTINCT user_id FROM story_comment WHERE story_id = 4- SELECT id FROM users WHERE EXISTS (SELECT 1 FROM story_comment WHERE story_id = 4 AND story_comment.user_id = users.id)
Like in the case of a GIN indexed array intersection.
If it needs to write to the table, it has a free space map listing all of the available fixed size pages. Each page can hold some number of fixed size tuples.
I'm surprised they've gotten so far with this. It seems ripe for fragmentation issues. I'm surprised they don't at least have a b+tree implementation to provide clustering based on the primary key. They have a b+tree implementation for indices, but not for tuple storage. IIRC, there's a feature to allow fixed size data row to be stored directly in the index, to help alleviate the need to look in the heap table. Perhaps that's what's kept the heap as viable?
Variable length strings are kept in a separate file (TOAST tables), referenced by the tuple. This keeps records fixed size, and allows for circumventing disk reads for string data for queries that don't require them. I'm not quite sure how the allocation scheme or data structure works there. My (very speculative) guess is that they're stored as a linked list, and on write, the allocator tries to give contiguous pages.
fwiw, I don't use postgresql on a regular basis, I've just spent some good amount of time squinting at the file format and related code, soley due to my own curiosity. It's been a while, so it's very possible that I'm misrepresenting or misremembering something. Someone has already posted their documentation on the file format -- it's a good read if you're interested.
That's not entirely true: variable-width row values under a size threshold are stored inline (possibly compressed).
The beauty part about TOAST is that they're mostly just regular tables (any table that needs its data TOASTed gets its own TOAST table). You can look them up in the system catalogs and query them directly.
The schema for these is (chunk_id, chunk_seq, chunk_data). Chunk "pieces" are limited in size so they can be stored inline (obviously there's not much benefit to a TOAST table itself having a TOAST table), so any row values that need to be TOASTed may also be broken up into multiple pieces. Row values stored inline in the "owning" table reference a chunk_id where the TOASTed data is stored, and queries that need to return that data look up all the chunks for a chunk id, ordered by chunk_seq.
You're right that this scheme avoids reading TOASTed data when you're not actually using it (a good reason to avoid "SELECT *" if you've got big TOASTed data).
Both tables and indexes use the same b+-tree implementation based on Lehman and Yao (prev/next links on internal nodes).
> Each page can hold some number of fixed size tuples
Variable size.
> Variable length strings are kept in a separate file
Only if the row exceeds the page size, otherwise everything is stuffed into the data leaf node.
> I'm not quite sure how the allocation scheme or data structure works there
Values are broken up into DataSize/PageSize "virtual rows" and stitched back together, but everything is still in the same slotted page structure.
Tables in Postgres are not btree's they are unordered heaps. The row id in the b-tree index points to a page number + item index in the heap.
A true clustered index would simply expose the index itself as a table without secondary heap storage, reducing I/O and storage space. Row visibility seems to complicate this in PG as index only scans may require checking the heap for visibility.
I can't find anything of this effort anymore. Does someone know what I'm talking about and what the current status of that is?
EDIT: found it: https://github.com/orioledb/orioledb
I'd love to hear what PG devs here think of his criticism and proposed solutions.
https://github.com/orioledb/orioledb/commits?author=akorotko...
See https://www.postgresql.org/message-id/flat/CAEze2Wg52tsSWA9F... for specifics
Many distro packages are, by contrast, compiled for k8-generic. Freaking Opteron!
BTW "native" is not really recommendable. One really ought to target a particular platform.
Stuff like this frustrates me. This is what generics are for in most languages. Looking at the commit[0], this is a _perfect_ example of where a sprinkling of C++ features (a very basic template) would outperform the original C version. It's also super disappointing that in 2022 we're still manually marking 10- line functions used in one place and called from one site as inline.
[0] https://git.postgresql.org/gitweb/?p=postgresql.git;a=commit...
The `inline` keyword usually isn't necessary anymore to get the compiler to inline stuff, the compiler has some pretty good heuristics for determining whether to inline a function call or not. The `inline` keyword is an extra hint to the compiler, and affects linkage (i.e multiple object files defining the same `inline` function does not result in a linker error).
I don't understand what you're disappointed at, this all seems very reasonable.
> I don't understand what you're disappointed at, this all seems very reasonable.
I'm disappointed by the fact that we're still manually overriding compiler heuristics and manually writing faux copy-pasted generics for performance, when this is a solved problem in so many other languages.
EDIT: I would _love_ to see some benchmarks without the pg_attribute_always_inline to see whether forcibly inlining the code is even necessary. In my (extended) experience with optimising C++ code, leaning on __forceinline is unnecessary in the vast vast majority of cases and should be used very sparingly.
[0] https://docs.microsoft.com/en-us/cpp/cpp/inline-functions-cp...
Not everything you tried is going to be worth explaining, and I get that their whole plan here is "forcibly inline this" so in C, where the compiler won't necessarily get your memo, it seems reasonable to explicitly say so.
I experimented with this on various projects and found the same even under lower optimisation levels. I'm definitely in the camp of "profile profile profile", and the guideline that I use is "if it has internal linkage, the compiler will figure it out. If it has external linkage, then I'm profiling".
> they do document the intention of the programmer in instantiating all these specialisations...
Is the intent of the programmer to write them inline, or for them to be inlined for performance? marking something as __forceinline does the former, but implies the latter, when it's not necessarily true to say inline == faster in every case!
Not really. The heuristics are pretty much based on a rough idea of function size (e.g. if it believes the call overhead is larger than just inlining the function, it will generally always be done if optimization is on), and/or functions it can prove is used only once (e.g. because they are static). That's it. There's no good idea of e.g. “this looks like a tight loop, and if I inline, I can maybe special-case away this cruft here”. The programmer's hints are very much relevant even in 2022.
src/lib/sort_template.h is an example of a pseudo template function, but we also have at least one pseudo template container in src/lib/simplehash.h.
And if you want to see some "policy based design" (C++ community term) in PostgreSQL C code, check out src/backend/exec/nodeHashjoin.c. It uses forced inlining to "instantiate" two different versions of the hash join executor code, one with parallelism and one without, so that we don't have all the "am I in parallel mode?" branching/code size in the generated code.
> I hear ya! But I don't have the power to make PostgreSQL switch to C++. Years ago, std::sort() vs qsort() was almost a standard example of how C++ can be faster than C.
Indeed - re-reading my initial comment it sounds like that particular part of my comment was directed at you, but it's really directed at projects like Postgres. The std::sort vs qsort example is exacly what I mean!
That goes exactly opposite of this optimization, and is just entirely orthogonal.
> It's also super disappointing that in 2022 we're still manually marking 10- line functions used in one place and called from one site as inline.
You misunderstand the change.
In a nutshell the prior version was a polymorphic function pointer that varied by the sort type.
(*sort_ptr)(data);
Their change adds specialized cases.
if (dataType == PG_INT32) {
sort_int32(data);
} else if (dataType == PG_INT64) {
sort_int64(data);
} ... {
} else {
(*sort_ptr)(data);
}
Op is not trying to say “the code as is” but “written in c++ style”.
I don’t think they misunderstood anything (and their beef with seemingly unprofiled use of always inline attribute is probably correct too)
The code could have made the type-specific sort macros. They could have literally written the code blocks in the actual sort function.
Instead they decided to make it separate functions and mark it inline because that is their overt intention and they thought it was cleaner.
What is the problem? Honestly, aside from noisy, useless griping, what is possibly the problem with that?
Their implication seems to be that inline shouldn't be necessary. And the truth is that it almost certainly isn't necessary, and any optimizing compiler would inline regardless. But clarifying their intentions is precisely what developers should do: "We're moving it here for organizational/cleanliness purpose, but it is intentionally written this way to be inlined because that is the entire point of this optimization".
As to the "unprofiled" use, their specific optimization was because they know the time being wasted in function calls, and the optimization was to avoid that.
> (*sort_ptr)(data);
> No compiler can inline this, no matter how aggressively you turn up the optimizations.
LTO can inline these just fine, provided the object files contain the necessary info (i.e. the IR or assembly from static archives, which is how -flto works for clang and GCC). I even tested this using a copy[1] of OpenBSD's qsort implementation a few weeks ago, verifying that both the sort algorithm itself as well as the comparator were inlined, just as would happen with C++ template'd vector sorting.
[1] I had to use a copy of qsort because the compiled libc qsort lacks the accompanying info necessary for LTO. But in theory libc and shared libraries in general could ship critical routines with the necessary metadata required for LTO optimizations. (IOW, a cross between a dynamic and static library.) Fundamentally this is just a toolchain issue, not a language issue. AFAIU, Rust code works much the same way, and its comparator functions tend to be inlined because Rust effectively compiles using LTO (and heavily relies on these implicit optimizations), except that because all Rust code is compiled statically, the necessary IR is always available. The same would be true of Go, but the Go compiler doesn't optimize as heavily. FWIW, AFAIU the C++ standard doesn't guarantee a templated sort comparator would get inlined, either, even if you're using a lambda. But this is optimization is extremely likely when the sort algorithm itself is template-expanded and the comparator is simple--as almost all would be.
What does that mean? Also, how is it "exactly opposite" and "orthogonal"? Maybe let's get rid of the mixed metaphors and speak in concrete terms.
In your comment below ("why would you want the compiler to do that? you can write out all the monomorphizations yourself!") I'm not totally certain that you understand the point of generics. You can always write out each case yourself. Incidentally that also applies to your precious inlining. But it's a tool to make programmers more productive.
It takes a lot of dedication and patience to do, but I wish more software teams did this. Perhaps schools should put more emphasis on this type of analysis.
Maybe then Call of Duty would load in a reasonable time. (sorry, pet peeve of mine)
I could easily sit and throw shade that Twitter takes longer to show my timeline than most ps5 games do to boot up and load into game, but that doesn't help anyone.
Knuth's comments about premature optimization have been so misquoted at this point that we've gone way beyond people using it as permission not to think, they also use it as a mandate to stop other people from thinking as well.
Academics are particularly bad at falling back on aphorisms, so how one would change the curriculum to fix this would also involve changing the teachers, which as an automatic conversation killer.
In my case I was keeping my own council before anyone tried to beat it out of me, and I learned to just keep things to myself. On the plus side I know dozens of ways to refactor for legibility and 'accidentally' improve performance at the same time.
My favorite is "That nested loop is kind of hard to read, how about making a dictionary/hashmap instead?"
Of course, very often, doing that often improves readability so it might still be a good use if your time.
There was the memorable story shared around here a while ago of a player patching GTA V's live service online to eliminate multiple-minute load times [1]. I'm sure Rockstar had/has many people working on performance (the core game is a well-known good performer and now has been on three different console generations since launch) but just, not this.
(Though to totally miss such truly extensive load times on your main revenue-generating component, that one's a headscratcher. Feels like something you'd end up addressing just for your own internal sanity. Maybe everyone just had monster workstations and didn't notice.)
I should have chosen websites for my rant, but CoD has been on my mind this week due to the weird way you have to keep getting into a game every time and go through what seems like multiple home screens in a way that is either a bug, or just poorly thought out. Either way, it is a weird waste of time, and annoying when you're trying to play two back-to-back games.
It has a guarantee of only one item in the tree for each key. All table rows that share that key are stored under that one item, as one large value. This value can thus become really large (and is stored as a subtree in such cases).
To sort these tuples, you can either implement that as 'merge key/value pairs when keys are equal during the sort phase' or 'merge key/value pairs when keys are equal during the index load phase'.
The first requires handling of arbitrarily large KV pairs (potentially larger than the normal page size, which indexes generally don't handle well) and losing sort elements during the sort (due to merges of values, I'm not sure sort algorithms can work with that).
The second requires a significantly larger temporary space to store the temporary data (potentially several times the size of the original data).
Additionally, someone must first find this enough of an issue to try to fix this, and apparently nobody has yet thought it to be enough of an issue to take a stab at it.
This is my default behavior with any database product. Solid advice.
For some purposes you can get away with a foreign data wrapper. FDWs are a lot simpler.
...and better defaults for the public schema.
Really looking forward to Postgres 15.
Also is it a stable quicksort?
Also it's specifically about queries where the sorted data is too big for memory:
> The final change is aimed at larger scale sorts that exceed the size of work_mem significantly. The algorithm which merges individual tapes was changed to use a k-way merge. When the number of tapes is large, less I/O is required than the original polyphase merge algorithm.
Sometimes locality of reference may increase the total number of comparisons but decrease the average cost considerably. For practical applications like databases, it's the runtime that matters, not the theory.
Do you have any source for this? This is the first time I've ever heard this and it seems contrary to everything I've read.
This is impressive in terms of performance for SQL Server operations. Imagine the end performance benefits for analytical/warehouse model of queries.
I might me misunderstanding you, but this is a post about PostgreSQL, not Microsoft's SQL Server.
> performance benefits for analytical/warehouse model
That performance result was for a fully in-memory sort operation, which you are are less likely to see in data warehouses.
I assume that what was meant is what I'd say as “SQL engine” or “SQL query runner”. It is unfortunate that MS has a habit of using common words in its product names. PG is a SQL server (no capital) in the sense that it is a server that processes SQL statements for retrieving and manipulating data.
# set client\_min\_messages TO ’debug1’;The best solution however, if you can afford it, remains to have an index that stores the values pre-sorted. These changes are still cool, though.