8 ms·
Speeding up sort performance in Postgres 15
- JacKTrocinskI 5y agoThey added the MERGE statement! ...and better defaults for the public schema. Really looking forward to Postgres 15.
- darksaints 5y agoOne of the things I have been consistently excited about was the new pluggable storage API, and I had followed a handful of projects that were working on plugins, like zedstore, zheap, and cstore. But now it seems like all of those efforts have stagnated. Any idea what happened?
- jfbaro 5y agoorioleDB is another one
- ccleve 5y agoThe difficulty is that the new table access method is very complex and hard to get right. I'm building something using a regular index access method now and it's hard enough. Once I get all that infrastructure working properly I may take another crack at a table access method. For some purposes you can get away with a foreign data wrapper. FDWs are a lot simpler.
- nhoughto 5y agoInteresting to see there is still some more to squeeze out of the old girl yet. Most seem like things that could have attempted before now but I guess weren’t the top pain points to fix, I wonder how many more 4-6% savings there are in there, good to see people going deep and keeping the improvements coming.
- mattashii 5y agoI'm currently working (on and off) on improving the performance of specific "kinds"/"shapes" of btree indexes by several %s (depending on shape it can be tens of percents). I hope and expect that it'll be ready for Pg16, but that of course assumes that the concept behind the implementation is acceptable. See https://www.postgresql.org/message-id/flat/CAEze2Wg52tsSWA9Fy7OCXx-K7pPLMNxA_fmQ6-%2B_pzR-AoODDA%40mail.gmail.com https://www.postgresql.org/message-id/flat/CAEze2Wg52tsSWA9F... for specifics
- mchusma 5y agoThanks so much for your contributions! The community for PG is so great.
- jeffbee 5y agoAnyone who is using a distro package of pg has the largest opportunity because they are all built wrong. A peak-optimized binary will get you much more than 4% speed up over generic packages.
- Bootvis 5y agoCan you please elaborate, what’s wrong and what do I need to do when building from source?
- adgjlsfhk1 5y agocompile with --march=native can often be significant.
- jeffbee 5y agoCompiling for your target is good, not using the PLT for mem* functions helps a ton, feedback-directed optimization and LTO and/or post-link optimization helps the most. For CPU-bound workloads of course.
- mayama 5y agoWill native march option work in case of cloud where you're not in control of cpu?
- jeffbee 5y agoI haven't used a cloud where you don't dictate the exact CPU you want. EC2, GCE, and Azure all provide specific guarantees. Even if you wanted a generic any-cloud binary you would probably compile with -march=skylake or, if truly paranoid, sandybridge. 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.
- brianwawok 5y ago
- hinkley 5y agoIn the long tail it’s more a matter of choosing a module or concern and squeezing a percent here and a percent there until it adds up to 5%, rather than looking for tall tent poles. Also counting calls for a fixed workload, and making sure this call stack really should call functionB nine times for three results or if that should be six or three. Function is still exactly the same cost but is now 1% of the overall cost instead of 3%.
- mkurz 5y agoGreat work!
- nitinreddy88 5y ago"The first test I ran while working on reducing the memory consumption of sort improved performance by 371%" This is impressive in terms of performance for SQL Server operations. Imagine the end performance benefits for analytical/warehouse model of queries.
- mattashii 5y ago> SQL Server operations 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.
- dspillett 5y ago> but this is a post about PostgreSQL, not Microsoft's SQL Server. 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.
- dewey 5y agoThere's a lot of interesting improvements in PG15, some of my favorites from https://www.postgresql.org/about/news/postgresql-15-beta-1-released-2453/ https://www.postgresql.org/about/news/postgresql-15-beta-1-r... are: >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.
- thejosh 5y agoI'm also super excited for the points you raised, looks like some great features being released, I really like that JSON is becoming a first class citizen. I'm also looking forward to the \copy improvements, especially around loading data into PG.
- baggiponte 5y agoThat’s fascinating! Totally orthogonal: how does PG store data? Do they use columnar specifications such as Arrow & Parquet?
- paulryanrogers 5y agoIt's row based with versions kept along side current data. Later to be vacuumed away. Unlike a redo log based approach.
- uhoh-itsmaciek 5y agoThere's a pretty good high-level overview of the implementation details in the official docs: https://www.postgresql.org/docs/current/storage.html https://www.postgresql.org/docs/current/storage.html
- 5y ago
- Jamie9912 5y agoGreat stuff. What's the best way to update a major version of Postgres when it comes out?
- speedgoose 5y agoIt's difficult to say without knowing your situation. Personally I would wait a few months at least to be sure that the biggest bugs are killed. Then if it's a new project or something not critical, I may upgrade without any precaution and hope for the best. For something more critical I would rely on the integration tests and manual testing in a pro-production environment for a few weeks. Before the final upgrade, I would finally do a few practice upgrade runs and be ready to rollback if needed.
- altendo 5y ago> Personally I would wait a few months at least to be sure that the biggest bugs are killed. This is my default behavior with any database product. Solid advice.
- mike-cardwell 5y agohttps://www.postgresql.org/docs/current/upgrading.html https://www.postgresql.org/docs/current/upgrading.html
- dewey 5y agoThis is just a data point but in my experience over the past few years Postgres updates are usually nothing to worry about. There's other systems where updates come with a lot more baggage attached (Like ElasticSearch) where you have to refactor schemas and stay up to date with the documentation way more than with PG.
- jon_richards 5y agoHomebrew on mac has a long-standing upgrade bug with Postgres extensions like postgis. It uninstalls the old postgis before copying the data over and then gets stuck in a hard to recover state. I always assume I’m going to lose all my data whenever I update major versions.
- maccard 5y ago> The change made here adds a set of new quicksort functions which suit some common datatypes. These quicksort functions have the comparison function compiled inline to remove the function call overhead. 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;h=697492434 https://git.postgresql.org/gitweb/?p=postgresql.git;a=commit...
- JacobiX 5y agoJust to clarify, this is what C++ templates do, they can create specializations for you, because templates are processed at compile-time. But its not how generics works for most languages (runtime, type erasure, etc).
- mort96 5y ago> 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. 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.
- maccard 5y agoI never said they used the inline keyword, you inferred that. If you look at the diff, they mark the fuctions as `pg_attribute_always_inline` which expands to __forceinline or __attribute__((always_inline)) inline depending on your compiler. These specifiers will remove any of the compilers heurestics [0]. > 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-cpp?view=msvc-170#inline-__inline-and-__forceinline https://docs.microsoft.com/en-us/cpp/cpp/inline-functions-cp...
- ollysb 5y agoIt seems a little surprising that GIN indexes have never been improved to allow for efficient sorting. Is this just not in enough demand to receive any attention or is there a technical aspect that makes it particularly difficult?
- mattashii 5y agoI'm not familiar with the full details, but GIN indeed has some issues that make it difficult to make presorting expensive: 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.
- gampleman 5y agoCould the specialisation of sort functions be further improved by using e.g. something like Radix sort for integers?
- kabes 5y agoA couple of months back there was a post from someone who made a presentation about a lot of things that are 'bad' in postgres (mostly performance-wise) and a github repo that tried to fix that (in first instance with patches and the idea was to later have it either upstreamed or as an addon). 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 https://github.com/orioledb/orioledb I'd love to hear what PG devs here think of his criticism and proposed solutions.
- canadiantim 5y agoYeah I’ve been following orioleDB as well. I think the guys behind it are also going to be offering a managed version of it too. I fully intend to use it in my next project.
- fuy 5y agoAgree with you - would love to hear some of the core PG devs to pay attention and discuss this work.
- ConnorLeet 5y agoI think that this repo was created by a core PG dev. https://github.com/orioledb/orioledb/commits?author=akorotkov https://github.com/orioledb/orioledb/commits?author=akorotko... https://github.com/akorotkov https://github.com/akorotkov
- fuy 5y agothat's the point - my understanding is that he created it as a result of reluctance of core pg team to make progress on these more low level and fundamental problems. I'd be interested to know what core pg people think of it - whether it's just too costly to implement these enhancements in pg, or they think these are just not desirable/correct per se.
- zeckalpha 5y agoOne graph has sorting a 10GB table and refers to it as a “Large sort”… is 10GB large any more?
- d_watt 5y agoNot for OLAP, but this seems to be about OLTP. If you're trying to sort 10GB of data for a traditional OLTP query, I would consider that "too large" and need of some data structure optimization. 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.
- hinkley 5y agoIt is a common complaint in discussions about sort algorithms that the case for sorting numbers is a degenerate case and 'real' cases involve at least pointer chasing, which can make the cost of compares to stop being constant time, or have a constant time that is greater than log(n) (or worse, n). 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.
- dagw 5y ago"Large" in this context is stated to mean significantly larger than work_mem, which defaults to 4MB out of the box. Interestingly performance (relative to PG14) seems to get worse as work_mem increases and the ratio of table size to work_mem decreases. If this holds it should mean that for a fixed work_mem PG15 performance (again relative to PG14) should improve as table size increases.
- pigcat 5y ago> performance (relative to PG14) seems to get worse as work_mem increases and the ratio of table size to work_mem decreases 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.
- avar 5y agoA related discussion about inlining these sort functions, templating etc.: https://www.postgresql.org/message-id/flat/CA%2BhUKGJ2-eaDqAum5bxhpMNhvuJmRDZxB_Tow0n-gse%2BHG0Yig%40mail.gmail.com https://www.postgresql.org/message-id/flat/CA%2BhUKGJ2-eaDqA...
- hinkley 5y agoI’m surprised they use quicksort. I would think in a database you’d value predictability over best case behavior. Also is it a stable quicksort?
- MR4D 5y agoIt is this type of analytics and discipline that I love about the PG team. 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)
- maccard 5y agoI work in video games and have done my fair share of perf work. Pretty much every game does this kind of work, and all the live service games have had a full team dedicated to ongoing performance work. 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.
- MR4D 5y agoYou make a good point, and I am aware of that. Frankly, the engineering that goes into any FPS (even the bad ones) is beyond amazing, especially when you add networking latencies to the complexity. 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.
- hinkley 5y agoIt's typical in non-gaming teams to have any instinct to optimize beaten out of you instead of guided. 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.
- aftbit 5y agoAh yes, good old: # set client\_min\_messages TO ’debug1’;
- winrid 5y agoAwesome! Will have to benchmark against the latest Mongo. 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.