3 ms·

I do wonder if one could eventually just turn off nestloops in such a case (e.g. inner side contains a seqscan), like the JOB paper recommended. Yes, it will ha

I do wonder if one could eventually just turn off nestloops in such a case (e.g. inner side contains a seqscan), like the JOB paper recommended. Yes, it will have marginally higher estimated cost, but the upside is _much_ safer query plans when the statistics are off.

davidrowley 3y ago
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.
- Sesse__ 3y ago
  Yeah, nestloop with a cheap inner path (e.g. a lookup into a unique index) should be just fine, so I don't think nestloops as a whole should be banned. (Also, I believe Postgres is pretty much the only place I've seen the concept of a parameterized path described; it's not talked much about in academia, although it is probably really hard to make an index-aware System R planner without it.) I wondered whether it would be possible just to add a fixed fuzz to every row estimate, say five rows. It would essentially mean you can never get this issue of a small undercount causing a plan disaster. Overestimating slightly is basically never a big issue as far as I know. (I should perhaps have considered this when I was actually making a query planner in a previous life, but there were more than enough other things to worry about :-) )
  - davidrowley 3y ago
    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+YPPUssfTV1GB=Z8nMVa+9Uq4RZJ8sULeQ@mail.gmail.com https://www.postgresql.org/message-id/CAApHDvo2sMPF9m=i+YPPU...
    - Sesse__ 3y ago
      Yes, a lot of this seems interesting to go into. I really hope that at some point, someone would find the resources to just try a lot of dumb stuff and see what works in practice. I mean, what we have right now (multiply selectivities together as if they were independent) is also pretty dumb, and there's no good reason why it should be preferred over everything else. Another avenue is of course trying to avoid the issue to begin with, e.g. through the recent “translation grids” of Müller and Moerkotte for better join selectivities. But I doubt anyone is going to be finding a silver bullet for this anytime soon, so reducing plan risk somehow seems very worthwhile.
      - davidrowley 3y ago
        > 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.
        Sesse__ 3y ago
        Yeah, I don't have all the answers, my point is that it would be worthwhile to try similarly dumb stuff and see if it works just as well and could be more robust in some places :-) Multi-selectivities are good, but IIRC they can't be specified across tables and thus across joins, right? Out of curiosity; how do you reconcile multiple selectivities? If you have a multi-column histogram on (a,b) and one on (b,c) and one on (c), and you need to figure out the selectivity of WHERE a=? AND b=? AND c=? from those three? I looked into this at some point, and academia presented me with a nightmare of second-order cone programming and stuff. :-) (I never implemented any of it before leaving the database world.)
emmettmoore 3y ago
What is the JOB paper? A quick google search didn’t find it, but I’d be interesting to see the recommendations
- Sesse__ 3y ago
  https://www.vldb.org/pvldb/vol9/p204-leis.pdf https://www.vldb.org/pvldb/vol9/p204-leis.pdf

davidrowley 3y ago

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.

Sesse__ 3y ago
Yeah, nestloop with a cheap inner path (e.g. a lookup into a unique index) should be just fine, so I don't think nestloops as a whole should be banned. (Also, I believe Postgres is pretty much the only place I've seen the concept of a parameterized path described; it's not talked much about in academia, although it is probably really hard to make an index-aware System R planner without it.) I wondered whether it would be possible just to add a fixed fuzz to every row estimate, say five rows. It would essentially mean you can never get this issue of a small undercount causing a plan disaster. Overestimating slightly is basically never a big issue as far as I know. (I should perhaps have considered this when I was actually making a query planner in a previous life, but there were more than enough other things to worry about :-) )
- davidrowley 3y ago
  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+YPPUssfTV1GB=Z8nMVa+9Uq4RZJ8sULeQ@mail.gmail.com https://www.postgresql.org/message-id/CAApHDvo2sMPF9m=i+YPPU...
  - Sesse__ 3y ago
    Yes, a lot of this seems interesting to go into. I really hope that at some point, someone would find the resources to just try a lot of dumb stuff and see what works in practice. I mean, what we have right now (multiply selectivities together as if they were independent) is also pretty dumb, and there's no good reason why it should be preferred over everything else. Another avenue is of course trying to avoid the issue to begin with, e.g. through the recent “translation grids” of Müller and Moerkotte for better join selectivities. But I doubt anyone is going to be finding a silver bullet for this anytime soon, so reducing plan risk somehow seems very worthwhile.
    - davidrowley 3y ago
      > 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.
      - Sesse__ 3y ago
        Yeah, I don't have all the answers, my point is that it would be worthwhile to try similarly dumb stuff and see if it works just as well and could be more robust in some places :-) Multi-selectivities are good, but IIRC they can't be specified across tables and thus across joins, right? Out of curiosity; how do you reconcile multiple selectivities? If you have a multi-column histogram on (a,b) and one on (b,c) and one on (c), and you need to figure out the selectivity of WHERE a=? AND b=? AND c=? from those three? I looked into this at some point, and academia presented me with a nightmare of second-order cone programming and stuff. :-) (I never implemented any of it before leaving the database world.)

emmettmoore 3y ago

What is the JOB paper? A quick google search didn’t find it, but I’d be interesting to see the recommendations

Sesse__ 3y ago
https://www.vldb.org/pvldb/vol9/p204-leis.pdf https://www.vldb.org/pvldb/vol9/p204-leis.pdf