davidrowley

The Oversized-Attribute Storage Technique. https://www.postgresql.org/docs/17/storage-toast.html

> Multi-selectivities are good, but IIRC they can't be specified across tables and thus across joins, right?

Yeah, no extended statistics for join quals yet.

> how do you reconcile multiple selectivities?

Looking at https://doxygen.postgresql.org/extended__stats_8c.html#a3f10... it seems the aim is to find the stats that cover the largest number of clauses tiebreaking on the statistics with the least number of keys. For your example both of those are the same, so it seems that which stats are applied is down to the order the stats appear in the stats list. That list is ordered by OID, which does not seem ideal as a dump and restore could result in the stats getting a different OID. Seems sorting that list by statistics name might be better. That's what we do for triggers, which seems like a good idea as it gives the user some ability to control the trigger fire order.

> I mean, what we have right now (multiply selectivities together as if they were independent) is also pretty dumb

Yeah, I think it was probably a mistake to always assume there's zero correlation between columns, but what value is better to use as a default? At least extended statistics allows the correlations of multiple columns to be gathered now. That probably means we'd be less likely to reconsider changing the default assumption of zero correlation when multiplying selectivities.

UNION is certainly one way to eliminate the OR condition.

In theory, a hash join is possible with a condition like `ON t1.a = t2.a OR t1.b = t2.b`, but Hash Join would need to build two hash tables and only probe the 2nd one if the first lookup found nothing. I don't know if there are any RDBMSs that allow multiple hash tables in a hash join.

> Also PG has no true clustered indexes all tables are heaps which is something most use all the time in MSSQL, usually your primary key is also set as the clustered index so that the table IS the index and any lookup on the key has no indirection.

This is true, but I believe if you have an index-organised table then subsequent indexes would have to reference the primary key. With PostgreSQL, indexes can effectively point to the record in the heap by using the block number and item pointer in the block. This should mean, in theory, index lookups are faster in PostgreSQL than non-clustered index lookups in SQL Server.

I was wondering, is there a concept of Bitmap Index Scans in SQL Server?

PostgreSQL is able to effectively "bitwise" AND and bitwise OR bitmap index scan results from multiple indexes to obtain the subset of tuple identifier (ctids) or blocks (in lossy mode) that should be scanned in the heap. Effectively, that allows indexes on a single column to be used when the query has a condition with an equality condition on multiple columns which are indexed individually. Does SQL Server allow this for heap tables? In theory, supporting both allows DBAs to choose, but I wonder how well each is optimised. It may lead to surprises if certain query plan shapes are no longer possible when someone switches to an IOT.

SELECT DISTINCT has seen quite a bit of work over the past few years. As of PG15, SELECT DISTINCT can use parallel query. I imagine that might help for big tables.

I assume the recursive CTEs comment is skip scanning using an index and looking for the first value higher than the previously seen value?

Certainly skip scans would be nice. There has been some work in this area, but not recently. As far as I recall some other infrastructure needed to go in first to make it easier for the query planner to understand when skip scanning would be useful.

Was there an indication of the number of functions compiled? There is work ongoing in this area, so feedback on this topic is very welcome on the PostgreSQL mailing lists.

Yeah, this is similar to some semi-baked ideas I was talking about in https://www.postgresql.org/message-id/CAApHDvo2sMPF9m=i+YPPU...

I think it should always be clear which open would scale better for additional rows over what the estimated row count is. We should always know this because we already cost for N rows, so it's possible to cost for N+1 rows and use the additional costs to calculate how the plan choice will scale when faced with more rows than expected.

Yes, I think so too. There is some element of this idea in the current version of PostgreSQL. However, it does not go as far as deferring the decision until execution. It's for choosing the cheapest version of a subplan once the plan has been generated for the next query level up. See fix_alternative_subplan() in setrefs.c. Likely it would be possible to expand that and have the finish plan contain the alternative and switch between them accordingly to which one is cheaper for the number of rows that previous executions have seen. Maybe tagging on some additional details about how many rows is the crossover point where one becomes cheaper than the other so that the executor can choose without having to think too hard about it would be a good idea.

> If the sort order isn't fully determined by a query, can the query plan influence the result order?

Yes. When running a query, PostgreSQL won't make any effort to provide a stable order of rows beyond what's specified in the ORDER BY.

I think the join search would remain at the same level of exhaustiveness for all levels of optimisation. I imagined we'd maybe want to disable optimisations that apply more rarely or are most expensive to discover when the planner "optimisation level" was set to lower settings. I suppose that would be things like LEFT JOIN removals and self-join removals. However, PostgreSQL does not have very many expensive optimisations that rarely help, so having an optimisation level might be more of a way of introducing more new optimisations that help fewer queries. Because we don't have a plan cache, there's been a focus on keeping the planner lean and having it not go to too much effort to optimise queries that are poorly written, for example.

I agree. The primary area where bad estimates bite us is estimating some path will return 1 row. When we join that Nested Loop looks like a great option. What could be faster to join to 1 row?! It just does not go well when 1 row turns into more than 1. We'd realise that the 1-row estimate we wrong by the time we got to row 2, so queuing 1 row would likely cover the majority of cases.

I think the first step to making improvements in this area is to have the planner err on the side of caution more often. Today it's quite happy to join using a Nested Loop when it thinks the outer side of the join contains a single row. We have various means in the planner on how certain we might be that the 1 row thing will hold true during execution. An equality condition on a column with a unique index, is, for example, a way we could be certain of getting <= 1 row. If for example, the selectivity estimate concludes 1 row will match for some WHERE clause containing several columns with independent statistics, then the certainty level goes down. It seems silly not to swap the join order and switch to a hash join for this. Best case, we have to build a hash table to store 1 row. Probing that won't be very expensive and could even be optimised further to skip hashing if we continually probe the same bucket for N probes. The cost of additional rows over the estimated 1 row scales much more linearly than the quadratic scaling we'd have gotten with Nested Loop. I imagine a setting which controls how much risk the planner is willing to take would allow users to maintain the status quo of the current costing model. I'd imagine not many would want that, however.

It's a bit complex to explain here, but I describe an idea I've been considering in https://www.postgresql.org/message-id/CAApHDvo2sMPF9m=i+YPPU...

You have to remember that because the query has an ORDER BY, it does not mean the rows come out in a deterministic order. There'd need to be at least an ORDER BY column that provably contains unique values. Of course, you could check for that, but then I don't think that's the end of the complexity. Things like SKIP LOCKED skip over rows which we can't immediately lock. If the first time we couldn't lock the lowest order row and output the 2nd, then aborted, replanned, then next time the 1st row wasn't locked, we'd then output the rows in the wrong order. It's probably possible to figure out all these cases and not do it when there's some hazard, but it sounds very tricky and bug-prone to me.

That could be useful if there was a way to just disable non-parameterized nested loop, however enable_nestloop=0 also disables parameterized nested loops. Parameterized nested loops are useful to avoid sorting or hashing some large relation when only a small subset of that relation is likely to have a join partner. This is even more true when you consider that since PG14, Memoize exists to act as a cache between Nested Loop and its inner subnode to cache previously looked-up values.

It's also important to consider that with enable_nestloop=0, when Nested Loop must be used (e.g for a CROSS JOIN) that the cost penalty that's added to reduce the chances of Nested Loop being used can dilute the costs so much that the query planner can then go on to make poor subsequent choices later in planning due to the costs for each method of implementing the subsequent operation being so relatively close to each other than the slightly cheaper one might not even be considered. See add_path() and STD_FUZZ_FACTOR. So, running enable_nestloop=0 in production is not without risk.

There's some information about why that does not happen in https://www.postgresql.org/message-id/20211104234742.ao2qzqf...

In particular:

> The immediate goal is to be able to generate JITed code/LLVM-IR that doesn't > contain any absolute pointer values. If the generated code doesn't change > regardless of any of the other contents of ExprEvalStep, we can still cache > the JIT optimization / code emission steps - which are the expensive bits.

A colleague is working on getting this patch into shape. So we might see some caching work get done after the relative pointer work is in.

I've considered things like this before but not had time to take it much beyond that. The idea was that the planner could run with all expensive optimisations disabled on first pass, then re-run if the estimated total cost of the plan was above some threshold with more expensive optimisations enabled. It does seem pretty silly to worry about producing a plan in a millisecond for say, an OLAP query that's going to take 6 hours to complete. On the other hand, we don't want to slow down the planner too much for a query that executes in 0.1 milliseconds.

There'd be a few hurdles to get over before we could get such a feature. The planner currently has a habit of making changes to the parsed query, so we'd either need to not do that, or make a copy of it before modifying it. The former would be best.

You'd still need analyze to gather table statistics to have the planner produce plans prior to getting any feedback from the executor. So, before getting feedback, the quality of the plans needn't be worse than they are today.

Perhaps, but it might be harsh to say it was the wrong decision when it was made as partitioned tables are far more optimised than when JIT was first worked on. It seems to me, most of the people that have issues with slow JIT times are having these issues with partitioned tables and JIT is slow due to having to compile large numbers of expressions. However, maybe this is the place for me to find out that's not always the case. The JIT costing is likely to get an overhaul soon, and if all goes to plan there JIT will be considered per plan node rather than per plan.

There certainly are valid reasons for this. For example, adding a join condition with an OR clause. The only join operator that supports non-equi joins is Nested Loop. If you went from a Hash or Merge join to that, then you'd likely notice some performance degradation. If you have a link to anywhere you've asked for help on this, then I'd be interested to see more details.

(blog author and Postgres committer here) I personally think this would be nice to have. However, I think the part about sending of tuples to the client is even more tricky than you've implied above. It's worse because a new plan does not even guarantee that the same tuples are returned. e.g. if you wrote: SELECT * FROM table LIMIT 10, there's no ORDER BY so which tuples are returned is non-deterministic. It may be easier to do something like queue up X tuples and just start sending those out when the queue is full. When the queue is full, we can say that it's too late to replan and we're locked into the current plan. People can set X to what they want to increase the time that the plan can change at the expense of using more memory and higher latency to get the first tuple.

> One part of this I found rather frustrating is the JIT in newer Postgres versions. The heuristics on when to use appear not robust at all to me.

(Author of the blog here and Postgres committer). I very much agree that the code to decide if JIT should be used or not needs work. For PG16, it only takes into account the estimated total cost of the plan and does not take into account how many expressions need to be compiled. It's quite fast to compile a few expressions, but if you're querying a partitioned table with hundreds of partitions and the plan contains all those partitions, then the JIT compiler has a lot of work to do. The number of expressions is not considered. A colleague and I do have some code to improve this. Unsure if it'll make PG17 at this stage.

Just to clarify. I'm the author of the blog. I work for Microsoft in the Postgres open-source team. All the work mentioned in the blog is in PostgreSQL 16, which is open-source.

(Author of the blog and that feature here) This one did crop up on the pgsql-hackers mailing list. I very much agree that it's unlikely to apply very often, but the good thing was that detecting when it's possible is as simple as checking if a pointer is NULL. So, it's very simple to detect, most likely does not apply very often, but can provide significant performance increases when it can be applied.

Postgres does not currently reuse JIT-compiled code. JIT will run each execution of the query. This may change in the next few years, likely starting with tuple deforming, as that's fairly reusable, per table for any query.

It sounds like it would have to be an opt-in feature which could be applied per query, as otherwise wouldn't it be equally as annoying if the planner didn't adapt to the table data changing?

What may be better is if the executor provided feedback to the planner to tell it the new plan was worse than the old one. With that, you might be able to recover much more quickly and less likely to get a midnight phonecall. The tricky part would be when should the planner then retry the new plan again. Also, other factors that influence the plan's execution time such as locking would be a cause of noise for any sub-system that was monitoring this.

> The one I'd love to tell the planner is that a table holds transactions in time, and that it should not expect that today's data is empty because it was empty 10 hours ago. It's an extremely common pattern, it makes any statistics gathering based on percentage of data changed dubious pretty quickly, and harms a whole lot of real queries, because in data like this, people care the most about the recent data.

It's not a hint, but PostgreSQL does have something that can help with cases like that.

In some cases, to obtain selectivity estimates, the planner will probe a btree index to find the actual lower and/or upper bound. For this to apply, a btree index must exist and you have to be using indexes >, >=, < or <= operator. The planner will probe the index if the query is comparing the indexed column to a value that's known the planner if that value falls on the first or last histogram bucket. This can help when your statistics are slightly out of date and you're querying for some column which stores a monotonically increasing or decreasing value.

It's pretty hard to tell if a plan is good or bad from EXPLAIN without using the ANALYZE option. With EXPLAIN ANALYZE you can see where the time is being spent, so can you get an idea of which part of the plan you should focus on.

To know if it's a bad plan, it does take quite a bit of knowledge as you need to know what alternative plans could have been used instead. It takes quite a bit of time to learn that stuff. You need to know what PostgreSQL is capable of. Some computer science knowledge helps here as you'll know, for example, when a hash join is a good way to join a table vs a nested loop.

As for fixing plan you've identified as bad, that also takes quite a bit of experience. If you understand the EXPLAIN ANALYZE output well, that's a good start. Looking for places where the estimated rows differ from the actual can be key. Having an understanding of how Postgres performed the row estimations helps. That's not something that comes easily without looking at the source code, unfortunately. Understanding tools that you have to change the plan is useful. Perhaps that's CREATE STATISTICS, or adjusting the stats targets on existing single column stats. Or maybe creating a new index. Having a test environment that allows you to experiment is very useful too.

> you don't want your "optimizer stats" to be as big as the whole dataset itself. So optimizer has limited information, by design, and it has to come up with _something_ in a very short amount of time.

This is very true. PostgreSQL does not do any proactive plan caching, so it's important that the planner remains fast. It is possible to adjust the number of stats targets to control the size of the histograms and most common values list. Upping that can be useful for OLAP-type workloads.

> I imagine that in addition to table/column stats, is also uses structural info as its inputs, like existence of (enabled & valid) constraints for example.

Yes. Foreign key constraints are used to assist with join selectivity estimations. PG17 (when released) should be able to make more use of NOT NULL constraints to improve plans.