Thread

1. Implement missing join selectivity estimation for range types

   Mahmoud Sakr <mahmoud.sakr@ulb.be> — 2022-06-30T14:31:30Z

   Hi,
   Given a query:
   SELECT * FROM t1, t2 WHERE t1.r << t2.r
   where t1.r, t2.r are of range type,
   currently PostgreSQL will estimate a constant selectivity for the << predicate,
   which is equal to 0.005, not utilizing the statistics that the optimizer
   collects for range attributes.
   
   We have worked out a theory for inequality join selectivity estimation
   (http://arxiv.org/abs/2206.07396), and implemented it for range
   types it in this patch.
   
   The algorithm in this patch re-uses the currently collected statistics for
   range types, which is the bounds histogram. It works fairly accurate for the
   operations <<, >>, &&, &<, &>, <=, >= with estimation error of about 0.5%.
   The patch also implements selectivity estimation for the
   operations @>, <@ (contains and is contained in), but their accuracy is not
   stable, since the bounds histograms assume independence between the range
   bounds. A point to discuss is whether or not to keep these last two operations.
   The patch also includes the selectivity estimation for multirange types,
   treating a multirange as a single range which is its bounding box.
   
   The same algorithm in this patch is applicable to inequality joins of scalar
   types. We, however, don't implement it for scalars, since more work is needed
   to make use of the other statistics available for scalars, such as the MCV.
   This is left as a future work.
   
   --
   Mahmoud SAKR - Univeristé Libre de Bruxelles
   This work is done by Diogo Repas, Zhicheng Luo, Maxime Schoemans, and myself
   

2. Re: Implement missing join selectivity estimation for range types

   Tomas Vondra <tomas.vondra@enterprisedb.com> — 2023-01-18T17:25:15Z

   Hello Mahmoud,
   
   Thanks for the patch and sorry for not taking a look earlier.
   
   On 6/30/22 16:31, Mahmoud Sakr wrote:
   > Hi,
   > Given a query:
   > SELECT * FROM t1, t2 WHERE t1.r << t2.r
   > where t1.r, t2.r are of range type,
   > currently PostgreSQL will estimate a constant selectivity for the << predicate,
   > which is equal to 0.005, not utilizing the statistics that the optimizer
   > collects for range attributes.
   > 
   > We have worked out a theory for inequality join selectivity estimation
   > (http://arxiv.org/abs/2206.07396), and implemented it for range
   > types it in this patch.
   > 
   
   Interesting. Are there any particular differences compared to how we
   estimate for example range clauses on regular columns?
   
   > The algorithm in this patch re-uses the currently collected statistics for
   > range types, which is the bounds histogram. It works fairly accurate for the
   > operations <<, >>, &&, &<, &>, <=, >= with estimation error of about 0.5%.
   
   Right. I think 0.5% is roughly expected for the default statistics
   target, which creates 100 histogram bins, each representing ~1% of the
   values. Which on average means ~0.5% error.
   
   > The patch also implements selectivity estimation for the
   > operations @>, <@ (contains and is contained in), but their accuracy is not
   > stable, since the bounds histograms assume independence between the range
   > bounds. A point to discuss is whether or not to keep these last two operations.
   
   That's a good question. I think the independence assumption is rather
   foolish in this case, so I wonder if we could "stabilize" this by making
   some different - less optimistic - assumption. Essentially, we have an
   estimates for lower/upper boundaries:
   
     P1 = P(lower(var1) <= lower(var2))
     P2 = P(upper(var2) <= upper(var1))
   
   and independence means we take (P1*P2). But maybe we should be very
   pessimistic and use e.g. Min(P1,P2)? Or maybe something in between?
   
   Another option is to use the length histogram, right? I mean, we know
   what the average length is, and it should be possible to use that to
   calculate how "far" ranges in a histogram can overlap.
   
   > The patch also includes the selectivity estimation for multirange types,
   > treating a multirange as a single range which is its bounding box.
   > 
   
   OK. But ideally we'd cross-check elements of the two multiranges, no?
   
   > The same algorithm in this patch is applicable to inequality joins of scalar
   > types. We, however, don't implement it for scalars, since more work is needed
   > to make use of the other statistics available for scalars, such as the MCV.
   > This is left as a future work.
   > 
   
   So if the column(s) contain a couple very common (multi)ranges that make
   it into an MCV, we'll ignore those? That's a bit unfortunate, because
   those MCV elements are potentially the main contributors to selectivity.
   
   
   regards
   
   -- 
   Tomas Vondra
   EnterpriseDB: http://www.enterprisedb.com
   The Enterprise PostgreSQL Company
   
   
   
   

3. Re: Implement missing join selectivity estimation for range types

   Tomas Vondra <tomas.vondra@enterprisedb.com> — 2023-01-18T18:07:23Z

   Also, calc_hist_selectivity_contains in multirangetypes_selfuncs.c needs
   a proper comment, not just "this is a copy from rangetypes".
   
   However, it seems the two functions are exactly the same. Would the
   functions diverge in the future? If not, maybe there should be just a
   single shared function?
   
   regards
   
   -- 
   Tomas Vondra
   EnterpriseDB: http://www.enterprisedb.com
   The Enterprise PostgreSQL Company
   
   
   
   

4. Re: Implement missing join selectivity estimation for range types

   Mahmoud Sakr <mahmoud.sakr@ulb.be> — 2023-01-18T19:23:20Z

   Hi Tomas,
   Thanks for picking up the patch and for the interesting discussions that
   you bring !
   
   > Interesting. Are there any particular differences compared to how we
   > estimate for example range clauses on regular columns?
   The theory is the same for scalar types. Yet, the statistics that are currently
   collected for scalar types include other synopsis than the histogram, such
   as MCV, which should be incorporated in the estimation. The theory for using
   the additional statistics is ready in the paper, but we didn't yet implement it.
   We thought of sharing the ready part, till the time allows us to implement the
   rest, or other developers continue it.
   
   > Right. I think 0.5% is roughly expected for the default statistics
   > target, which creates 100 histogram bins, each representing ~1% of the
   > values. Which on average means ~0.5% error.
   Since this patch deals with join selectivity, we are then crossing 100*100 bins.
   The ~0.5% error estimation comes from our experiments, rather than a
   mathematical analysis.
   
   > independence means we take (P1*P2). But maybe we should be very
   > pessimistic and use e.g. Min(P1,P2)? Or maybe something in between?
   >
   > Another option is to use the length histogram, right? I mean, we know
   > what the average length is, and it should be possible to use that to
   > calculate how "far" ranges in a histogram can overlap.
   The independence assumption exists if we use the lower and upper
   histograms. It equally exists if we use the lower and length histograms.
   In both cases, the link between the two histograms is lost during their
   construction.
   You discussion brings an interesting trade-off of optimistic v.s. pessimistic
   estimations. A typical way to deal with such a trade-off is to average the
   two, for example is model validation in machine learning, Do you think we
   should implement something like
   average( (P1*P2), Min(P1,P2) )?
   
   > OK. But ideally we'd cross-check elements of the two multiranges, no?
   
   > So if the column(s) contain a couple very common (multi)ranges that make
   > it into an MCV, we'll ignore those? That's a bit unfortunate, because
   > those MCV elements are potentially the main contributors to selectivity.
   Both ideas would require collecting more detailed statistics, for
   example similar
   to arrays. In this patch, we restricted ourselves to the existing statistics.
   
   
   > Also, calc_hist_selectivity_contains in multirangetypes_selfuncs.c needs
   > a proper comment, not just "this is a copy from rangetypes".
   Right, the comment should elaborate more that the collected statistics are
   currently that same as rangetypes but may potentially deviate.
   
   > However, it seems the two functions are exactly the same. Would the
   > functions diverge in the future? If not, maybe there should be just a
   > single shared function?
   Indeed, it is possible that the two functions will deviate if that statistics
   of multirange types will be refined.
   
   --
   Best regards
   Mahmoud SAKR
   
   On Wed, Jan 18, 2023 at 7:07 PM Tomas Vondra
   <tomas.vondra@enterprisedb.com> wrote:
   >
   > Also, calc_hist_selectivity_contains in multirangetypes_selfuncs.c needs
   > a proper comment, not just "this is a copy from rangetypes".
   >
   > However, it seems the two functions are exactly the same. Would the
   > functions diverge in the future? If not, maybe there should be just a
   > single shared function?
   >
   > regards
   >
   > --
   > Tomas Vondra
   > EnterpriseDB: http://www.enterprisedb.com
   > The Enterprise PostgreSQL Company
   
   
   
   

5. Re: Implement missing join selectivity estimation for range types

   Tomas Vondra <tomas.vondra@enterprisedb.com> — 2023-01-20T14:25:11Z

   On 1/18/23 20:23, Mahmoud Sakr wrote:
   > Hi Tomas,
   > Thanks for picking up the patch and for the interesting discussions that
   > you bring !
   > 
   >> Interesting. Are there any particular differences compared to how we
   >> estimate for example range clauses on regular columns?
   >
   > The theory is the same for scalar types. Yet, the statistics that are currently
   > collected for scalar types include other synopsis than the histogram, such
   > as MCV, which should be incorporated in the estimation. The theory for using
   > the additional statistics is ready in the paper, but we didn't yet implement it.
   > We thought of sharing the ready part, till the time allows us to implement the
   > rest, or other developers continue it.
   > 
   
   I see. We don't have MCV stats for range types, so the algorithms don't
   include that. But we have that for scalars, so the code would need to be
   modified to consider that too.
   
   However, I wonder how much could that improve the estimates for range
   queries on scalar types. I mean, we already get pretty good estimates
   for those, so I guess we wouldn't get much.
   
   >> Right. I think 0.5% is roughly expected for the default statistics
   >> target, which creates 100 histogram bins, each representing ~1% of the
   >> values. Which on average means ~0.5% error.
   > Since this patch deals with join selectivity, we are then crossing 100*100 bins.
   > The ~0.5% error estimation comes from our experiments, rather than a
   > mathematical analysis.
   > 
   
   Ah, understood. Even for joins there's probably a fairly close
   relationship between the bin size and estimation error, but it's
   certainly more complex.
   
   BTW the experiments are those described in section 6 of the paper,
   correct? I wonder how uniform (or skewed) the data was - in terms of
   range length, etc. Or how it works for other operators, not just for
   "<<" as in the paper.
   
   >> independence means we take (P1*P2). But maybe we should be very
   >> pessimistic and use e.g. Min(P1,P2)? Or maybe something in between?
   >>
   >> Another option is to use the length histogram, right? I mean, we know
   >> what the average length is, and it should be possible to use that to
   >> calculate how "far" ranges in a histogram can overlap.
   > The independence assumption exists if we use the lower and upper
   > histograms. It equally exists if we use the lower and length histograms.
   > In both cases, the link between the two histograms is lost during their
   > construction.
   > You discussion brings an interesting trade-off of optimistic v.s. pessimistic
   > estimations. A typical way to deal with such a trade-off is to average the
   > two, for example is model validation in machine learning, Do you think we
   > should implement something like
   > average( (P1*P2), Min(P1,P2) )?
   > 
   
   I don't know.
   
   AFAICS the independence assumption is used not only because it's very
   cheap/simple to implement, but also because it actually is a reasonable
   assumption for a fair number of data sets (particularly in OLTP).
   
   You're right it's an optimistic estimate, but for many data sets  it's
   actually quite reasonable.
   
   I'm not sure that applies to range boundaries - the upper/lower bounds
   seem pretty strongly correlated. So maybe using a more pessimistic
   formula would be appropriate.
   
   I was thinking the length histogram might allow an alternative,
   approach, because it says what fraction of ranges has what length. So
   for a "fixed" lower boundary, we may check each of those fractions. Of
   course, this assumes consistent range length distribution (so if ranges
   at one end are much longer, that won't work).
   
   >> OK. But ideally we'd cross-check elements of the two multiranges, no?
   > 
   >> So if the column(s) contain a couple very common (multi)ranges that make
   >> it into an MCV, we'll ignore those? That's a bit unfortunate, because
   >> those MCV elements are potentially the main contributors to selectivity.
   > Both ideas would require collecting more detailed statistics, for
   > example similar
   > to arrays. In this patch, we restricted ourselves to the existing statistics.
   > 
   
   Ah, I didn't realize we don't actually build MCV for range types. In
   that case the current behavior makes perfect sense.
   
   > 
   >> Also, calc_hist_selectivity_contains in multirangetypes_selfuncs.c needs
   >> a proper comment, not just "this is a copy from rangetypes".
   > Right, the comment should elaborate more that the collected statistics are
   > currently that same as rangetypes but may potentially deviate.
   > 
   >> However, it seems the two functions are exactly the same. Would the
   >> functions diverge in the future? If not, maybe there should be just a
   >> single shared function?
   > Indeed, it is possible that the two functions will deviate if that statistics
   > of multirange types will be refined.
   > 
   
   Right, but are there any such plans? Also, what's the likelihood we'll
   add new statistics to only one of the places (e.g. for multiranges but
   not plain ranges)?
   
   I'd keep a single function until we actually need two. That's also
   easier for maintenance - with two it's easy to fix a bug in one place
   and forget about the other, etc.
   
   
   regards
   
   -- 
   Tomas Vondra
   EnterpriseDB: http://www.enterprisedb.com
   The Enterprise PostgreSQL Company
   
   
   
   

6. Re: Implement missing join selectivity estimation for range types

   Tomas Vondra <tomas.vondra@enterprisedb.com> — 2023-01-21T21:12:27Z

   Hi Mahmoud,
   
   I finally had time to properly read the paper today - the general
   approach mostly matches how I imagined the estimation would work for
   inequalities, but it's definitely nice to see the algorithm properly
   formalized and analyzed.
   
   What seems a bit strange to me is that the patch only deals with range
   types, leaving the scalar cases unchanged. I understand why (not having
   a MCV simplifies it a lot), but I'd bet joins on range types are waaaay
   less common than inequality joins on scalar types. I don't even remember
   seeing inequality join on a range column, TBH.
   
   That doesn't mean the patch is wrong, of course. But I'd expect users to
   be surprised we handle range types better than "old" scalar types (which
   range types build on, in some sense).
   
   Did you have any plans to work on improving estimates for the scalar
   case too? Or did you do the patch needed for the paper, and have no
   plans to continue working on this?
   
   I'm also wondering about not having MCV for ranges. I was a bit
   surprised we don't build MCV in compute_range_stats(), and perhaps we
   should start building those - if there are common ranges, this might
   significantly improve some of the estimates (just like for scalar
   columns). Which would mean the estimates for range types are just as
   complex as for scalars. Of course, we don't do that now.
   
   
   regards
   
   -- 
   Tomas Vondra
   EnterpriseDB: http://www.enterprisedb.com
   The Enterprise PostgreSQL Company
   
   
   
   

7. Re: Implement missing join selectivity estimation for range types

   Mahmoud Sakr <mahmoud.sakr@ulb.be> — 2023-01-25T19:11:33Z

   Hi Tomas,
   
   > I finally had time to properly read the paper today - the general
   > approach mostly matches how I imagined the estimation would work for
   > inequalities, but it's definitely nice to see the algorithm properly
   > formalized and analyzed.
   
   Awesome, thanks for this interest!
   
   > What seems a bit strange to me is that the patch only deals with range
   > types, leaving the scalar cases unchanged. I understand why (not having
   > a MCV simplifies it a lot), but I'd bet joins on range types are waaaay
   > less common than inequality joins on scalar types. I don't even remember
   > seeing inequality join on a range column, TBH.
   >
   > That doesn't mean the patch is wrong, of course. But I'd expect users to
   > be surprised we handle range types better than "old" scalar types (which
   > range types build on, in some sense).
   >
   > Did you have any plans to work on improving estimates for the scalar
   > case too? Or did you do the patch needed for the paper, and have no
   > plans to continue working on this?
   
   I fully agree. Scalars are way more important.
   I join you in the call for Diogo and Zhicheng to continue this implementation,
   specially after the interest you show towards this patch. The current patch
   was a course project (taught by me and Maxime), which was specific to range
   types. But indeed the solution generalizes well to scalars. Hopefully after the
   current exam session (Feb), there will be time to continue the implementation.
   Nevertheless, it makes sense to do two separate patches: this one, and
   the scalars. The code of the two patches is located in different files, and
   the estimation algorithms have slight differences.
   
   > I'm also wondering about not having MCV for ranges. I was a bit
   > surprised we don't build MCV in compute_range_stats(), and perhaps we
   > should start building those - if there are common ranges, this might
   > significantly improve some of the estimates (just like for scalar
   > columns). Which would mean the estimates for range types are just as
   > complex as for scalars. Of course, we don't do that now.
   
   Good question. Our intuition is that MCV will not be useful for ranges.
   Maxime has done an experiment and confirmed this intuition. Here is his
   experiment and explanation:
   Create a table with 126000 int4ranges.
   All ranges have their middle between 0 and 1000 and a length between 90
   and 110.
   The ranges are created in the following way:
   - 10 different ranges, each duplicated 1000 times
   - 20 different ranges, each duplicated 500 times
   - 40 different ranges, each duplicated 100 times
   - 200 different ranges, each duplicated 10 times
   - 100000 different ranges, not duplicated
   Two such tables (t1 and t2) were created in the same way but with different
   data. Then he ran the following query:
   
   EXPLAIN ANALYZE SELECT count(*)
   FROM t, t2 WHERE t && t2
   
   The results (using our patch) where the following:
   Plan rows: 2991415662
   Actual rows: 2981335423
   
   So the estimation accuracy is still fairly good for such data with a lot
   of repeated values, even without having MCV statistics.
   The only error that can happen in our algorithms comes from the last bin in
   which we assume uniform distribution of values. Duplicate values
   (end bound, not ranges) might make this assumption be wrong, which would
   create inaccurate estimations. However, this is still only incorrect
   for the last
   bin and all the others are correct.
   MCV's are mainly useful for equality, which is not an operation we cover, and
   probably not an important predicate for ranges. What do you think?
   
   Best regards,
   Mahmoud
   
   
   
   

8. Re: Implement missing join selectivity estimation for range types

   SCHOEMANS Maxime <maxime.schoemans@ulb.be> — 2023-03-20T15:34:47Z

   Hi Tomas,
   
   As a quick update, the paper related to this work has finally been published in Mathematics (https://www.mdpi.com/2227-7390/11/6/1383).
   During revision we also added a figure showing a comparison of our algorithm vs the existing algorithms in Oracle, SQL Server, MySQL and PostgreSQL, which can be found in the experiments section of the paper.
   As can be seen, our algorithm outperforms even Oracle and SQL Server.
   
   During this revision we also found a small bug, so we are working on a revision of the patch, which fixes this.
   
   
   Also, calc_hist_selectivity_contains in multirangetypes_selfuncs.c needs
   a proper comment, not just "this is a copy from rangetypes".
   
   
   Right, the comment should elaborate more that the collected statistics are
   currently that same as rangetypes but may potentially deviate.
   
   
   
   However, it seems the two functions are exactly the same. Would the
   functions diverge in the future? If not, maybe there should be just a
   single shared function?
   
   
   Indeed, it is possible that the two functions will deviate if that statistics
   of multirange types will be refined.
   
   
   
   Right, but are there any such plans? Also, what's the likelihood we'll
   add new statistics to only one of the places (e.g. for multiranges but
   not plain ranges)?
   
   I'd keep a single function until we actually need two. That's also
   easier for maintenance - with two it's easy to fix a bug in one place
   and forget about the other, etc.
   
   Regarding our previous discussion about the duplication of calc_hist_join_selectivity in rangetypes_selfuncs.c and multirangetypes_selfuncs.c, we can also remove this duplication in the revision if needed.
   Note that currently, there are no external functions shared between rangetypes_selfuncs.c and multirangetypes_selfuncs.c.
   Any function that was used in both files was duplicated as a static function.
   The functions calc_hist_selectivity_scalar, calc_length_hist_frac, calc_hist_selectivity_contained and calc_hist_selectivity_contains are examples of this, where the function is identical but has been declared static in both files.
   That said, we can remove the duplication of calc_hist_join_selectivity if it still needed.
   We would, however, require some guidance as to where to put the external definition of this function, as there does not appear to be a rangetypes_selfuncs.h header.
   Should it simply go into utils/selfuncs.h or should we create a new header file?
   
   Best regards,
   Maxime Schoemans
   

9. Re: Implement missing join selectivity estimation for range types

   SCHOEMANS Maxime <maxime.schoemans@ulb.be> — 2023-06-19T09:49:22Z

   Hi,
   
   In the selectivity algorithm, the division was applied after adding the remaining histogram buckets of histogram2 that don't overlap with histogram1.
   This could lead to reducing selectivity by half, e.g., in the case that histogram2 is completely right of histogram1.
   The correct calculation is to divide by two before adding the remainder.
   This patch-fix does the needed.
   
   Best regards,
   Maxime Schoemans
   
   On 20/03/2023 16:34, maxime wrote:
   Hi Tomas,
   
   As a quick update, the paper related to this work has finally been published in Mathematics (https://www.mdpi.com/2227-7390/11/6/1383).
   During revision we also added a figure showing a comparison of our algorithm vs the existing algorithms in Oracle, SQL Server, MySQL and PostgreSQL, which can be found in the experiments section of the paper.
   As can be seen, our algorithm outperforms even Oracle and SQL Server.
   
   During this revision we also found a small bug, so we are working on a revision of the patch, which fixes this.
   
   
   Also, calc_hist_selectivity_contains in multirangetypes_selfuncs.c needs
   a proper comment, not just "this is a copy from rangetypes".
   
   
   Right, the comment should elaborate more that the collected statistics are
   currently that same as rangetypes but may potentially deviate.
   
   
   
   However, it seems the two functions are exactly the same. Would the
   functions diverge in the future? If not, maybe there should be just a
   single shared function?
   
   
   Indeed, it is possible that the two functions will deviate if that statistics
   of multirange types will be refined.
   
   
   
   Right, but are there any such plans? Also, what's the likelihood we'll
   add new statistics to only one of the places (e.g. for multiranges but
   not plain ranges)?
   
   I'd keep a single function until we actually need two. That's also
   easier for maintenance - with two it's easy to fix a bug in one place
   and forget about the other, etc.
   
   Regarding our previous discussion about the duplication of calc_hist_join_selectivity in rangetypes_selfuncs.c and multirangetypes_selfuncs.c, we can also remove this duplication in the revision if needed.
   Note that currently, there are no external functions shared between rangetypes_selfuncs.c and multirangetypes_selfuncs.c.
   Any function that was used in both files was duplicated as a static function.
   The functions calc_hist_selectivity_scalar, calc_length_hist_frac, calc_hist_selectivity_contained and calc_hist_selectivity_contains are examples of this, where the function is identical but has been declared static in both files.
   That said, we can remove the duplication of calc_hist_join_selectivity if it still needed.
   We would, however, require some guidance as to where to put the external definition of this function, as there does not appear to be a rangetypes_selfuncs.h header.
   Should it simply go into utils/selfuncs.h or should we create a new header file?
   
   Best regards,
   Maxime Schoemans
   
   

10. Re: Implement missing join selectivity estimation for range types

    SCHOEMANS Maxime <maxime.schoemans@ulb.be> — 2023-06-19T16:26:09Z

    This is a quick correction as the last patch contained a missing semicolon.
    
    Regards,
    Maxime Schoemans

11. Re: Implement missing join selectivity estimation for range types

    Damir Belyalov <dam.bel07@gmail.com> — 2023-07-07T08:08:48Z

    Hello!
    
    Thank you for the patch, very interesting article.
    The patch doesn't apply to the current postgres version. Could you please
    update it?
    
    Regards,
    Damir Belyalov,
    Postgres Professional
    

12. Re: Implement missing join selectivity estimation for range types

    SCHOEMANS Maxime <maxime.schoemans@ulb.be> — 2023-07-07T15:40:43Z

    Hi,
    
    Thank you for picking up this patch.
    
     > The patch doesn't apply to the current postgres version. Could you 
    please update it?
    Indeed, the code was initially written on pg15.
    You can find attached a new version of the patch that can be applied on 
    the current master branch of postgres.
    
    Please let us know if there is anything else we can do.
    
    Best regards,
    Maxime Schoemans

13. Re: Implement missing join selectivity estimation for range types

    Tom Lane <tgl@sss.pgh.pa.us> — 2023-11-14T19:46:21Z

    Schoemans Maxime <maxime.schoemans@ulb.be> writes:
    > You can find attached a new version of the patch that can be applied on 
    > the current master branch of postgres.
    
    I took a brief look through this very interesting work.  I concur
    with Tomas that it feels a little odd that range join selectivity
    would become smarter than scalar inequality join selectivity, and
    that we really ought to prioritize applying these methods to that
    case.  Still, that's a poor reason to not take the patch.
    
    I also agree with the upthread criticism that having two identical
    functions in different source files will be a maintenance nightmare.
    Don't do it.  When and if there's a reason for the behavior to
    diverge between the range and multirange cases, it'd likely be
    better to handle that by passing in a flag to say what to do.
    
    But my real unhappiness with the patch as-submitted is the test cases,
    which require rowcount estimates to be reproduced exactly.  We know
    very well that ANALYZE estimates are not perfectly stable and tend to
    vary across platforms.  As a quick check I tried the patch within a
    32-bit VM, and it passed, which surprised me a bit ... but it would
    surprise me a lot if we got these same numbers on every machine in
    the buildfarm.  We need a more forgiving test method.  Usually the
    approach is to set up a test case where the improved accuracy of
    the estimate changes the planner's choice of plan compared to what
    you got before, since that will normally not be too prone to change
    from variations of a percent or two in the estimates.  Another idea
    could be something like
    
    	SELECT (estimate/actual BETWEEN 0.9 AND 1.1) AS ok FROM ...
    
    which just gives a true/false output instead of an exact number.
    
    			regards, tom lane
    
    
    
    

14. Re: Implement missing join selectivity estimation for range types

    SCHOEMANS Maxime <maxime.schoemans@ulb.be> — 2023-11-20T20:17:22Z

    On 14/11/2023 20:46, Tom Lane wrote:
    > I took a brief look through this very interesting work.  I concur
    > with Tomas that it feels a little odd that range join selectivity
    > would become smarter than scalar inequality join selectivity, and
    > that we really ought to prioritize applying these methods to that
    > case.  Still, that's a poor reason to not take the patch.
    
    Indeed, we started with ranges as this was the simpler case (no MCV) and 
    was the topic of a course project.
    The idea is to later write a second patch that applies these ideas to 
    scalar inequality while also handling MCV's correctly.
    
    > I also agree with the upthread criticism that having two identical
    > functions in different source files will be a maintenance nightmare.
    > Don't do it.  When and if there's a reason for the behavior to
    > diverge between the range and multirange cases, it'd likely be
    > better to handle that by passing in a flag to say what to do.
    
    The duplication is indeed not ideal. However, there are already 8 other 
    duplicate functions between the two files.
    I would thus suggest to leave the duplication in this patch and create a 
    second one that removes all duplication from the two files, instead of 
    just removing the duplication for our new function.
    What are your thoughts on this? If we do this, should the function 
    definitions go in rangetypes.h or should we create a new 
    rangetypes_selfuncs.h header?
    
    > But my real unhappiness with the patch as-submitted is the test cases,
    > which require rowcount estimates to be reproduced exactly.
    
    > We need a more forgiving test method. Usually the
    > approach is to set up a test case where the improved accuracy of
    > the estimate changes the planner's choice of plan compared to what
    > you got before, since that will normally not be too prone to change
    > from variations of a percent or two in the estimates.
    
    I have changed the test method to produce query plans for a 3-way range 
    join.
    The plans for the different operators differ due to the computed 
    selectivity estimation, which was not the case before this patch.
    
    Regards,
    Maxime Schoemans

15. Re: Implement missing join selectivity estimation for range types

    Alena Rybakina <lena.ribackina@yandex.ru> — 2023-11-30T14:50:36Z

    Hi!
    
    Thank you for your work on the subject, I think it's a really useful 
    feature and it allows optimizer to estimate more correctly clauses with 
    such type of operator.
    
    I rewieved your patch and noticed that some comments are repeated into 
    multirangejoinsel functions, I suggest combining them.
    
    The proposed changes are in the attached patch.
    
    
    If this topic is about calculating selectivity, have you thought about 
    adding cardinality calculation test for queries with this type of operator?
    
    For example, you could form queries similar to those that you use in 
    src/test/regress/sql/multirangetypes.sql and 
    src/test/regress/sql/rangetypes.sql.
    
    I added a few in the attached patch.
    
    -- 
    Regards,
    Alena Rybakina
    

16. Re: Implement missing join selectivity estimation for range types

    vignesh C <vignesh21@gmail.com> — 2024-01-05T10:37:17Z

    On Tue, 21 Nov 2023 at 01:47, Schoemans Maxime <maxime.schoemans@ulb.be> wrote:
    >
    > On 14/11/2023 20:46, Tom Lane wrote:
    > > I took a brief look through this very interesting work.  I concur
    > > with Tomas that it feels a little odd that range join selectivity
    > > would become smarter than scalar inequality join selectivity, and
    > > that we really ought to prioritize applying these methods to that
    > > case.  Still, that's a poor reason to not take the patch.
    >
    > Indeed, we started with ranges as this was the simpler case (no MCV) and
    > was the topic of a course project.
    > The idea is to later write a second patch that applies these ideas to
    > scalar inequality while also handling MCV's correctly.
    >
    > > I also agree with the upthread criticism that having two identical
    > > functions in different source files will be a maintenance nightmare.
    > > Don't do it.  When and if there's a reason for the behavior to
    > > diverge between the range and multirange cases, it'd likely be
    > > better to handle that by passing in a flag to say what to do.
    >
    > The duplication is indeed not ideal. However, there are already 8 other
    > duplicate functions between the two files.
    > I would thus suggest to leave the duplication in this patch and create a
    > second one that removes all duplication from the two files, instead of
    > just removing the duplication for our new function.
    > What are your thoughts on this? If we do this, should the function
    > definitions go in rangetypes.h or should we create a new
    > rangetypes_selfuncs.h header?
    >
    > > But my real unhappiness with the patch as-submitted is the test cases,
    > > which require rowcount estimates to be reproduced exactly.
    >
    > > We need a more forgiving test method. Usually the
    > > approach is to set up a test case where the improved accuracy of
    > > the estimate changes the planner's choice of plan compared to what
    > > you got before, since that will normally not be too prone to change
    > > from variations of a percent or two in the estimates.
    >
    > I have changed the test method to produce query plans for a 3-way range
    > join.
    > The plans for the different operators differ due to the computed
    > selectivity estimation, which was not the case before this patch.
    
    One of the tests was aborted at [1], kindly post an updated patch for the same:
    [04:55:42.797] src/tools/ci/cores_backtrace.sh linux /tmp/cores
    [04:56:03.640] dumping /tmp/cores/postgres-6-24094.core for
    /tmp/cirrus-ci-build/tmp_install/usr/local/pgsql/bin/postgres
    
    [04:57:24.199] Core was generated by `postgres: old_node: postgres
    regression [local] EXPLAIN '.
    [04:57:24.199] Program terminated with signal SIGABRT, Aborted.
    [04:57:24.199] #0 __GI_raise (sig=sig@entry=6) at
    ../sysdeps/unix/sysv/linux/raise.c:50
    [04:57:24.199] Download failed: Invalid argument. Continuing without
    source file ./signal/../sysdeps/unix/sysv/linux/raise.c.
    [04:57:26.803]
    [04:57:26.803] Thread 1 (Thread 0x7f121d9ec380 (LWP 24094)):
    [04:57:26.803] #0 __GI_raise (sig=sig@entry=6) at
    ../sysdeps/unix/sysv/linux/raise.c:50
    [04:57:26.803] set = {__val = {4194304, 0, 4636737291354636288,
    4636737291354636288, 0, 0, 64, 64, 128, 128, 192, 192, 256, 256, 0,
    0}}
    [04:57:26.803] pid = <optimized out>
    [04:57:26.803] tid = <optimized out>
    [04:57:26.803] ret = <optimized out>
    [04:57:26.803] #1 0x00007f122003d537 in __GI_abort () at abort.c:79
    ...
    ...
    [04:57:38.774] #6 0x00007f357ad95788 in __asan::__asan_report_load1
    (addr=addr@entry=107477261711120) at
    ../../../../src/libsanitizer/asan/asan_rtl.cpp:117
    [04:57:38.774] bp = 140731433585840
    [04:57:38.774] pc = <optimized out>
    [04:57:38.774] local_stack = 139867680821632
    [04:57:38.774] sp = 140731433585832
    [04:57:38.774] #7 0x000055d5b155c37c in range_cmp_bound_values
    (typcache=typcache@entry=0x629000030b60, b1=b1@entry=0x61c000017708,
    b2=b2@entry=0x61c0000188b8) at rangetypes.c:2090
    [04:57:38.774] No locals.
    [04:57:38.774] #8 0x000055d5b1567bb2 in calc_hist_join_selectivity
    (typcache=typcache@entry=0x629000030b60,
    hist1=hist1@entry=0x61c0000188b8, nhist1=nhist1@entry=101,
    hist2=hist2@entry=0x61c0000170b8, nhist2=nhist2@entry=101) at
    rangetypes_selfuncs.c:1298
    [04:57:38.774] i = 0
    [04:57:38.774] j = 101
    [04:57:38.774] selectivity = <optimized out>
    [04:57:38.774] cur_sel1 = <optimized out>
    [04:57:38.774] cur_sel2 = <optimized out>
    [04:57:38.774] prev_sel1 = <optimized out>
    [04:57:38.774] prev_sel2 = <optimized out>
    [04:57:38.774] cur_sync = {val = <optimized out>, infinite =
    <optimized out>, inclusive = <optimized out>, lower = <optimized out>}
    [04:57:38.774] #9 0x000055d5b1569190 in rangejoinsel
    (fcinfo=<optimized out>) at rangetypes_selfuncs.c:1495
    
    [1] - https://cirrus-ci.com/task/5507789477380096
    
    Regards,
    Vignesh
    
    
    
    

17. Re: Implement missing join selectivity estimation for range types

    SCHOEMANS Maxime <maxime.schoemans@ulb.be> — 2024-01-05T17:39:50Z

    On 05/01/2024 11:37, vignesh C wrote:
     > One of the tests was aborted at [1], kindly post an updated patch for 
    the same:
    
    Thank you for notifying us.
    I believe I fixed the issue but it is hard to be certain as the issue 
    did not arise when running the regression tests locally.
    
    Regards,
    Maxime

18. Re: Implement missing join selectivity estimation for range types

    vignesh C <vignesh21@gmail.com> — 2024-01-17T10:48:15Z

    On Fri, 5 Jan 2024 at 23:09, Schoemans Maxime <maxime.schoemans@ulb.be> wrote:
    >
    > On 05/01/2024 11:37, vignesh C wrote:
    >  > One of the tests was aborted at [1], kindly post an updated patch for
    > the same:
    >
    > Thank you for notifying us.
    > I believe I fixed the issue but it is hard to be certain as the issue
    > did not arise when running the regression tests locally.
    
    I'm noticing this issue is not yet resolved, the CFBot is still
    failing at [1] with:
    #7 0x000055cddc25cd93 in range_cmp_bound_values
    (typcache=typcache@entry=0x629000030b60, b1=b1@entry=0x61c000016f08,
    b2=b2@entry=0x61c0000180b8) at rangetypes.c:2090
    [19:55:02.591] No locals.
    [19:55:02.591] #8 0x000055cddc2685c1 in calc_hist_join_selectivity
    (typcache=typcache@entry=0x629000030b60,
    hist1=hist1@entry=0x61c0000180b8, nhist1=nhist1@entry=101,
    hist2=hist2@entry=0x61c0000168b8, nhist2=nhist2@entry=101) at
    rangetypes_selfuncs.c:1295
    [19:55:02.591] i = 0
    [19:55:02.591] j = 101
    [19:55:02.591] selectivity = 0
    [19:55:02.591] prev_sel1 = -1
    [19:55:02.591] prev_sel2 = 0
    [19:55:02.591] #9 0x000055cddc269aaa in rangejoinsel
    (fcinfo=<optimized out>) at rangetypes_selfuncs.c:1479
    [19:55:02.591] root = <optimized out>
    [19:55:02.591] operator = <optimized out>
    [19:55:02.591] args = <optimized out>
    [19:55:02.591] sjinfo = <optimized out>
    [19:55:02.591] vardata1 = {var = <optimized out>, rel = <optimized
    out>, statsTuple = <optimized out>, freefunc = <optimized out>,
    vartype = <optimized out>, atttype = <optimized out>, atttypmod =
    <optimized out>, isunique = <optimized out>, acl_ok = <optimized out>}
    [19:55:02.591] vardata2 = {var = <optimized out>, rel = <optimized
    out>, statsTuple = <optimized out>, freefunc = <optimized out>,
    vartype = <optimized out>, atttype = <optimized out>, atttypmod =
    <optimized out>, isunique = <optimized out>, acl_ok = <optimized out>}
    [19:55:02.591] hist1 = {staop = <optimized out>, stacoll = <optimized
    out>, valuetype = <optimized out>, values = <optimized out>, nvalues =
    <optimized out>, numbers = <optimized out>, nnumbers = <optimized
    out>, values_arr = <optimized out>, numbers_arr = <optimized out>}
    [19:55:02.591] hist2 = {staop = <optimized out>, stacoll = <optimized
    out>, valuetype = <optimized out>, values = <optimized out>, nvalues =
    <optimized out>, numbers = <optimized out>, nnumbers = <optimized
    out>, values_arr = <optimized out>, numbers_arr = <optimized out>}
    [19:55:02.591] sslot = {staop = <optimized out>, stacoll = <optimized
    out>, valuetype = <optimized out>, values = <optimized out>, nvalues =
    <optimized out>, numbers = <optimized out>, nnumbers = <optimized
    out>, values_arr = <optimized out>, numbers_arr = <optimized out>}
    [19:55:02.591] reversed = <optimized out>
    [19:55:02.591] selec = 0.001709375000000013
    [19:55:02.591] typcache = 0x629000030b60
    [19:55:02.591] stats1 = <optimized out>
    [19:55:02.591] stats2 = <optimized out>
    [19:55:02.591] empty_frac1 = 0
    [19:55:02.591] empty_frac2 = 0
    [19:55:02.591] null_frac1 = 0
    [19:55:02.591] null_frac2 = 0
    [19:55:02.591] nhist1 = 101
    [19:55:02.591] nhist2 = 101
    [19:55:02.591] hist1_lower = 0x61c0000168b8
    [19:55:02.591] hist1_upper = 0x61c0000170b8
    [19:55:02.591] hist2_lower = 0x61c0000178b8
    [19:55:02.591] hist2_upper = 0x61c0000180b8
    [19:55:02.591] empty = <optimized out>
    [19:55:02.591] i = <optimized out>
    [19:55:02.591] __func__ = "rangejoinsel"
    [19:55:02.591] #10 0x000055cddc3b761f in FunctionCall5Coll
    (flinfo=flinfo@entry=0x7ffc1628d710, collation=collation@entry=0,
    arg1=arg1@entry=107545982648856, arg2=arg2@entry=3888,
    arg3=arg3@entry=107820862916056, arg4=arg4@entry=0, arg5=<optimized
    out>) at fmgr.c:1242
    [19:55:02.591] fcinfodata = {fcinfo = {flinfo = <optimized out>,
    context = <optimized out>, resultinfo = <optimized out>, fncollation =
    <optimized out>, isnull = <optimized out>, nargs = <optimized out>,
    args = 0x0}, fcinfo_data = {<optimized out> <repeats 112 times>}}
    [19:55:02.591] fcinfo = 0x7ffc1628d5e0
    [19:55:02.591] result = <optimized out>
    [19:55:02.591] __func__ = "FunctionCall5Coll"
    [19:55:02.591] #11 0x000055cddc3b92ee in OidFunctionCall5Coll
    (functionId=8355, collation=collation@entry=0,
    arg1=arg1@entry=107545982648856, arg2=arg2@entry=3888,
    arg3=arg3@entry=107820862916056, arg4=arg4@entry=0, arg5=<optimized
    out>) at fmgr.c:1460
    [19:55:02.591] flinfo = {fn_addr = <optimized out>, fn_oid =
    <optimized out>, fn_nargs = <optimized out>, fn_strict = <optimized
    out>, fn_retset = <optimized out>, fn_stats = <optimized out>,
    fn_extra = <optimized out>, fn_mcxt = <optimized out>, fn_expr =
    <optimized out>}
    [19:55:02.591] #12 0x000055cddbe834ae in join_selectivity
    (root=root@entry=0x61d00017c218, operatorid=operatorid@entry=3888,
    args=0x6210003bc5d8, inputcollid=0,
    jointype=jointype@entry=JOIN_INNER,
    sjinfo=sjinfo@entry=0x7ffc1628db30) at
    ../../../../src/include/postgres.h:324
    [19:55:02.591] oprjoin = <optimized out>
    [19:55:02.591] result = <optimized out>
    [19:55:02.591] __func__ = "join_selectivity"
    [19:55:02.591] #13 0x000055cddbd8c18c in clause_selectivity_ext
    (root=root@entry=0x61d00017c218, clause=0x6210003bc678,
    varRelid=varRelid@entry=0, jointype=jointype@entry=JOIN_INNER,
    sjinfo=sjinfo@entry=0x7ffc1628db30,
    use_extended_stats=use_extended_stats@entry=true) at clausesel.c:841
    
    I have changed the status to "Waiting on Author", feel free to post an
    updated version, check CFBot and update the Commitfest entry
    accordingly.
    
    [1] - https://cirrus-ci.com/task/5698117824151552
    
    Regards,
    Vignesh
    
    
    
    

19. Re: Implement missing join selectivity estimation for range types

    jian he <jian.universality@gmail.com> — 2024-01-22T08:10:37Z

    I cannot figure out why it aborts.
    
    as Tom mentioned in upthread about the test cases.
    similar to src/test/regress/sql/stats_ext.sql check_estimated_rows function.
    we can test it by something:
    
    create or replace function check_estimated_rows(text) returns table (ok bool)
    language plpgsql as
    $$
    declare
        ln text;
        tmp text[];
        first_row bool := true;
    begin
        for ln in
            execute format('explain analyze %s', $1)
        loop
            if first_row then
                first_row := false;
                tmp := regexp_match(ln, 'rows=(\d*) .* rows=(\d*)');
                return query select 0.2 < tmp[1]::float8 / tmp[2]::float8
    and tmp[1]::float8 / tmp[2]::float8 < 5;
            end if;
        end loop;
    end;
    $$;
    
    select * from check_estimated_rows($$select * from test_range_join_1,
    test_range_join_2 where ir1 && ir2$$);
    select * from check_estimated_rows($$select * from test_range_join_1,
    test_range_join_2 where ir1 << ir2$$);
    select * from check_estimated_rows($$select * from test_range_join_1,
    test_range_join_2 where ir1 >> ir2$$);
    
    Do you need 3 tables to do the test? because we need to actually run
    the query then compare the estimated row
    and actually returned rows.
    If you really execute the query with 3 table joins, it will take a lot of time.
    So two tables join with where quql should be fine?
    
    /* Fast-forwards i and j to start of iteration */
    + for (i = 0; range_cmp_bound_values(typcache, &hist1[i], &hist2[0]) < 0; i++);
    + for (j = 0; range_cmp_bound_values(typcache, &hist2[j], &hist1[0]) < 0; j++);
    +
    + /* Do the estimation on overlapping regions */
    + while (i < nhist1 && j < nhist2)
    + {
    + double cur_sel1,
    + cur_sel2;
    + RangeBound cur_sync;
    +
    + if (range_cmp_bound_values(typcache, &hist1[i], &hist2[j]) < 0)
    + cur_sync = hist1[i++];
    + else if (range_cmp_bound_values(typcache, &hist1[i], &hist2[j]) > 0)
    + cur_sync = hist2[j++];
    + else
    + {
    + /* If equal, skip one */
    + cur_sync = hist1[i];
    +
    
    this part range_cmp_bound_values "if else if" part computed twice, you
    can just do
    `
    int cmp;
    cmp = range_cmp_bound_values(typcache, &hist1[i], &hist2[j]);
    if cmp <0  then
    else if cmp > 0 then
    else then
    `
    
    also. I think you can put the following into  main while loop.
    + for (i = 0; range_cmp_bound_values(typcache, &hist1[i], &hist2[0]) < 0; i++);
    + for (j = 0; range_cmp_bound_values(typcache, &hist2[j], &hist1[0]) < 0; j++);
    
    split range and multirange into 2 patches might be a good idea.
    seems: same function (calc_hist_join_selectivity) with same function
    signature in src/backend/utils/adt/multirangetypes_selfuncs.c
    and src/backend/utils/adt/rangetypes_selfuncs.c,
    previously mail complaints not resolved.
    
    
    
    

20. Re: Implement missing join selectivity estimation for range types

    Haibo Yan <tristan.yim@gmail.com> — 2026-04-06T23:32:02Z

    On Mon, Apr 6, 2026 at 3:12 PM jian he <jian.universality@gmail.com> wrote:
    
    > I cannot figure out why it aborts.
    >
    > as Tom mentioned in upthread about the test cases.
    > similar to src/test/regress/sql/stats_ext.sql check_estimated_rows
    > function.
    > we can test it by something:
    >
    > create or replace function check_estimated_rows(text) returns table (ok
    > bool)
    > language plpgsql as
    > $$
    > declare
    >     ln text;
    >     tmp text[];
    >     first_row bool := true;
    > begin
    >     for ln in
    >         execute format('explain analyze %s', $1)
    >     loop
    >         if first_row then
    >             first_row := false;
    >             tmp := regexp_match(ln, 'rows=(\d*) .* rows=(\d*)');
    >             return query select 0.2 < tmp[1]::float8 / tmp[2]::float8
    > and tmp[1]::float8 / tmp[2]::float8 < 5;
    >         end if;
    >     end loop;
    > end;
    > $$;
    >
    > select * from check_estimated_rows($$select * from test_range_join_1,
    > test_range_join_2 where ir1 && ir2$$);
    > select * from check_estimated_rows($$select * from test_range_join_1,
    > test_range_join_2 where ir1 << ir2$$);
    > select * from check_estimated_rows($$select * from test_range_join_1,
    > test_range_join_2 where ir1 >> ir2$$);
    >
    > Do you need 3 tables to do the test? because we need to actually run
    > the query then compare the estimated row
    > and actually returned rows.
    > If you really execute the query with 3 table joins, it will take a lot of
    > time.
    > So two tables join with where quql should be fine?
    >
    > /* Fast-forwards i and j to start of iteration */
    > + for (i = 0; range_cmp_bound_values(typcache, &hist1[i], &hist2[0]) < 0;
    > i++);
    > + for (j = 0; range_cmp_bound_values(typcache, &hist2[j], &hist1[0]) < 0;
    > j++);
    > +
    > + /* Do the estimation on overlapping regions */
    > + while (i < nhist1 && j < nhist2)
    > + {
    > + double cur_sel1,
    > + cur_sel2;
    > + RangeBound cur_sync;
    > +
    > + if (range_cmp_bound_values(typcache, &hist1[i], &hist2[j]) < 0)
    > + cur_sync = hist1[i++];
    > + else if (range_cmp_bound_values(typcache, &hist1[i], &hist2[j]) > 0)
    > + cur_sync = hist2[j++];
    > + else
    > + {
    > + /* If equal, skip one */
    > + cur_sync = hist1[i];
    > +
    >
    > this part range_cmp_bound_values "if else if" part computed twice, you
    > can just do
    > `
    > int cmp;
    > cmp = range_cmp_bound_values(typcache, &hist1[i], &hist2[j]);
    > if cmp <0  then
    > else if cmp > 0 then
    > else then
    > `
    >
    > also. I think you can put the following into  main while loop.
    > + for (i = 0; range_cmp_bound_values(typcache, &hist1[i], &hist2[0]) < 0;
    > i++);
    > + for (j = 0; range_cmp_bound_values(typcache, &hist2[j], &hist1[0]) < 0;
    > j++);
    >
    > split range and multirange into 2 patches might be a good idea.
    > seems: same function (calc_hist_join_selectivity) with same function
    > signature in src/backend/utils/adt/multirangetypes_selfuncs.c
    > and src/backend/utils/adt/rangetypes_selfuncs.c,
    > previously mail complaints not resolved.
    >
    >
    >
    > Hi,all
    I'd like to revive the discussion on improving selectivity estimation for
    range/range joins.
    Attached is the v5 patch which teaches rangejoinsel to use range bound
    histograms for estimating the <<, >>, and && operators. Currently, the
    planner often falls back to a hardcoded default (like 0.005), which can
    lead to poor join ordering in complex queries.
    In this version, I have intentionally excluded &< and &>.
    a &< b essentially maps to upper(a) <= upper(b).
    a &> b essentially maps to lower(a) >= lower(b).
    Since these operators include equality (<= / >=) rather than strict
    inequality (< / >), their estimation is slightly more nuanced. I believe
    focusing on the strict inequality and overlap operators first allows us to
    deliver a clean, converged, and significantly beneficial improvement. We
    can discuss the best approach for the remaining operators once this
    foundation is in place.
    Test Results
    My local tests show that the planner now correctly identifies cases with
    zero or full selectivity, which were previously misestimated.
    ----------------------------------------------------------------------
    CREATE TABLE t1 (id int, r int4range);
    CREATE TABLE t2 (id int, r int4range);
    INSERT INTO t1 SELECT g, int4range(g * 2 - 1, g * 2) FROM
    generate_series(1, 1000) g;
    INSERT INTO t2 SELECT g, int4range(10000 + g * 200, 10000 + g * 200 + 100)
    FROM generate_series(1, 1000) g;
    ANALYZE t1, t2;
    ----------------------------------------------------------------------
    
    Real Selectivity:
    ----------------------------------------------------------------------
    SELECT
        avg((t1.r << t2.r)::int) AS p_ll, -- Expected: 1.0
        avg((t1.r >> t2.r)::int) AS p_rr, -- Expected: 0.0
        avg((t1.r && t2.r)::int) AS p_ov  -- Expected: 0.0
    FROM t1, t2;
    -- Result: p_ll = 1.0, p_rr = 0.0, p_ov = 0.0
    ----------------------------------------------------------------------
    
    Planner Improvements:
    With the patch, the EXPLAIN output reflects these probabilities accurately:
    For << (High Selectivity):
    The planner correctly estimates rows=1000000 (1000 * 1000 * 1.0).
    ----------------------------------------------------------------------
    Nested Loop (cost=29.50..15080.75 rows=1000000 width=61)
      Join Filter: (t1.r << t2.r)
    ----------------------------------------------------------------------
    For && and >> (Near-Zero Selectivity):
    The planner now correctly predicts rows=1 instead of using the default
    multiplier.
    ----------------------------------------------------------------------
    Nested Loop (cost=0.00..15036.50 rows=1 width=36)
      Join Filter: (t1.r && t2.r)
    This improved estimation allows the optimizer to make much better decisions
    regarding join order and nesting when range columns are involved.
    I look forward to your feedback.
    Regards,
    Haibo
    

21. Re: Implement missing join selectivity estimation for range types

    SCHOEMANS Maxime <maxime.schoemans@ulb.be> — 2026-04-14T14:03:07Z

    Hi Haibo,
    
    Thank you for picking this up again. I agree with the changes you made
    in v5, in particular scoping the patch to the three strict operators and
    reworking the tests to check plan structure rather than exact row counts.
    
    Attached is v6 as a 3-patch series building on your v5.
    
    Patch 1 is your range join selectivity patch with one small change: the
    range_cmp_bounds result in the merge walk is stored in a local cmp
    variable to avoid calling it twice per iteration, as jian he suggested.
    
    Patch 2 adds the same estimation for multirange types, covering all type
    combinations (multirange x multirange, multirange x range, range x
    multirange). Since both range and multirange types use the same bound
    histogram format and the same RangeBound representation, the core
    algorithm is identical.
    
    Patch 3 removes the duplication between rangetypes_selfuncs.c and
    multirangetypes_selfuncs.c that Tom raised as a concern. It makes the
    10 shared helper functions non-static, exports them via selfuncs.h,
    and deletes the copies from the multirange file. This covers all the
    pre-existing duplication between the two files, not just the functions
    added in this patch set.
    
    Regards,
    Maxime
    

22. Re: Implement missing join selectivity estimation for range types

    Haibo Yan <tristan.yim@gmail.com> — 2026-04-15T00:53:31Z

    On Tue, Apr 14, 2026 at 7:03 AM SCHOEMANS Maxime <maxime.schoemans@ulb.be>
    wrote:
    
    > Hi Haibo,
    >
    > Thank you for picking this up again. I agree with the changes you made
    > in v5, in particular scoping the patch to the three strict operators and
    > reworking the tests to check plan structure rather than exact row counts.
    >
    > Attached is v6 as a 3-patch series building on your v5.
    >
    > Patch 1 is your range join selectivity patch with one small change: the
    > range_cmp_bounds result in the merge walk is stored in a local cmp
    > variable to avoid calling it twice per iteration, as jian he suggested.
    >
    
    Hi Maxime,
    Thank you for working on this and for building on top of v5.
    
    I think patch 1 looks good to me. I do not see major issues there. One
    small note: the localized bool join_is_reversed; in my version was
    intentional. I left it that way because get_join_variables() wants a
    storage location, and I preferred to keep that use local and explicit
    rather than trying to reshape things around it.
    
    >
    > Patch 2 adds the same estimation for multirange types, covering all type
    > combinations (multirange x multirange, multirange x range, range x
    > multirange). Since both range and multirange types use the same bound
    > histogram format and the same RangeBound representation, the core
    > algorithm is identical.
    >
    For patch 2, I am less convinced, especially for &&.
    
    My concern is not so much whether the code runs, but whether the semantic
    argument is strong enough for the mixed range/multirange cases. The patch
    assumes that because range and multirange use the same bounds histogram
    format and the same RangeBound representation, the same estimator can be
    applied directly. I think that argument is much easier to make for << and >>
    than for &&.
    
    For single ranges, && works nicely with the usual decomposition because if
    two single ranges do not overlap, then one must be entirely to the left or
    entirely to the right of the other. But for multiranges there is a third
    possibility: neither side is entirely left nor entirely right, and yet they
    still do not overlap because of an internal gap.
    For example:
    
    A = {[1,2), [100,101)}
    
    B = [50,60)
    
    Here:
    
    A << B is false
    A >> B is false
    A && B is also false
    
    So for multiranges, “not left and not right” does not imply overlap in the
    same way it does for single ranges. That makes me worry that reusing the
    same estimator logic for &&, especially in mixed range/multirange cases,
    may overestimate overlap because the overall lower/upper bounds do not
    capture the internal holes.
    
    So I think patch 2 still needs a stronger justification there, and probably
    more targeted tests around sparse multiranges / hole cases, especially for
    &&.
    
    >
    > Patch 3 removes the duplication between rangetypes_selfuncs.c and
    > multirangetypes_selfuncs.c that Tom raised as a concern. It makes the
    > 10 shared helper functions non-static, exports them via selfuncs.h,
    > and deletes the copies from the multirange file. This covers all the
    > pre-existing duplication between the two files, not just the functions
    > added in this patch set.
    >
    > Regards,
    > Maxime
    >
    For patch 3, I agree with the motivation: the duplication between
    rangetypes_selfuncs.c and multirangetypes_selfuncs.c is not ideal. But I am
    not convinced that exporting those helpers via selfuncs.h is the right
    boundary.
    
    My preference would be something tighter:
    
    
       -
    
       keep the shared helper implementations in one place
       -
    
       add a backend-private internal header just for the range-family selfuncs
       code
       -
    
       include that internal header from rangetypes_selfuncs.c and
       multirangetypes_selfuncs.c
       -
    
       avoid widening visibility by turning a group of file-local helpers into
       broader extern declarations in selfuncs.h
    
    In other words, I agree that the duplication should be removed, but I think
    a backend-private internal header should be enough for that goal. I do not
    think we need to expand visibility more than necessary by moving these
    helpers out of the file-private space into a broader interface.
    
    Thanks again for working on this.
    
    Regards,
    
    Haibo
    

23. Re: Implement missing join selectivity estimation for range types

    SCHOEMANS Maxime <maxime.schoemans@ulb.be> — 2026-04-15T15:13:34Z

    Hi Haibo,
    
    Thank you for the review.
    
    > One small note: the localized bool join_is_reversed; in my version was
    > intentional. I left it that way because get_join_variables() wants a
    > storage location, and I preferred to keep that use local and explicit
    > rather than trying to reshape things around it.
    
    Fair point. I moved it out of the bare block because it looked unusual,
    but I can change it back if you prefer.
    
    > For patch 2, I am less convinced, especially for &&.
    > [...]
    > for multiranges there is a third possibility: neither side is entirely
    > left nor entirely right, and yet they still do not overlap because of
    > an internal gap.
    
    This is a valid concern, but it is an existing limitation of multirange
    statistics, not something we are introducing. The existing restriction
    selectivity code in multirangetypes_selfuncs.c already uses the same
    NOT(<<) AND NOT(>>) decomposition for && on multiranges. And
    multirange_typanalyze explicitly says:
    
        /* Treat multiranges like a big range without gaps. */
    
    The statistics only store the outermost bounds, so the gap information
    is already lost before our estimator sees it. The multirange GiST
    opclass does the same (stores the bounding range). Our join estimator
    is just consistent with how multiranges are handled elsewhere.
    
    The alternative is falling back to the 0.005 default, which will almost
    certainly be worse. Would a comment explaining the limitation be enough?
    
    > For patch 3, I agree with the motivation [...] But I am not convinced
    > that exporting those helpers via selfuncs.h is the right boundary.
    > My preference would be something tighter: [...] a backend-private
    > internal header just for the range-family selfuncs code
    
    Good point about the visibility. I'll move the declarations to a
    separate backend-private header in the next version.
    
    Regards,
    Maxime
    

24. Re: Implement missing join selectivity estimation for range types

    Haibo Yan <tristan.yim@gmail.com> — 2026-04-16T04:12:35Z

    On Wed, Apr 15, 2026 at 8:13 AM SCHOEMANS Maxime <maxime.schoemans@ulb.be>
    wrote:
    
    > Hi Haibo,
    >
    > Thank you for the review.
    >
    > > One small note: the localized bool join_is_reversed; in my version was
    > > intentional. I left it that way because get_join_variables() wants a
    > > storage location, and I preferred to keep that use local and explicit
    > > rather than trying to reshape things around it.
    >
    > Fair point. I moved it out of the bare block because it looked unusual,
    > but I can change it back if you prefer.
    >
    > > For patch 2, I am less convinced, especially for &&.
    > > [...]
    > > for multiranges there is a third possibility: neither side is entirely
    > > left nor entirely right, and yet they still do not overlap because of
    > > an internal gap.
    >
    > This is a valid concern, but it is an existing limitation of multirange
    > statistics, not something we are introducing. The existing restriction
    > selectivity code in multirangetypes_selfuncs.c already uses the same
    > NOT(<<) AND NOT(>>) decomposition for && on multiranges. And
    > multirange_typanalyze explicitly says:
    >
    >     /* Treat multiranges like a big range without gaps. */
    >
    > The statistics only store the outermost bounds, so the gap information
    > is already lost before our estimator sees it. The multirange GiST
    > opclass does the same (stores the bounding range). Our join estimator
    > is just consistent with how multiranges are handled elsewhere.
    >
    > The alternative is falling back to the 0.005 default, which will almost
    > certainly be worse. Would a comment explaining the limitation be enough?
    >
    Thanks, that is a fair point.
    
    I agree that this is not something patch 2 is uniquely introducing. If the
    
    existing multirange statistics and restriction selectivity already treat a
    
    multirange essentially as its outer bounds, then it makes sense that the
    
    join estimator can only work within that same approximation.
    
    So I am less worried about this as a correctness objection than I was at
    
    first. My main concern is really about making that limitation explicit,
    
    especially for &&, where internal gaps can matter a lot for the real
    
    overlap semantics.
    
    I think it would help if patch 2 said this a bit more directly, both in
    
    the code comments and in the patch description. Something along the lines
    
    of:
    
    
       - this reuses the same outer-bounds approximation already used by
       existing
    
    multirange statistics / restriction selectivity
    
    
       - internal gaps are not represented in the available stats
       - so && for sparse multiranges may still be overestimated in some cases
       - but this is still expected to be better than falling back to a fixed
       default selectivity
    
    > For patch 3, I agree with the motivation [...] But I am not convinced
    > > that exporting those helpers via selfuncs.h is the right boundary.
    > > My preference would be something tighter: [...] a backend-private
    > > internal header just for the range-family selfuncs code
    >
    > Good point about the visibility. I'll move the declarations to a
    > separate backend-private header in the next version.
    >
    > Regards,
    > Maxime
    >
    
    If you are willing to add that clarification, I think that would address
    
    most of my concern here.
    
    Regards,
    Haibo
    

25. Re: Implement missing join selectivity estimation for range types

    SCHOEMANS Maxime <maxime.schoemans@ulb.be> — 2026-04-16T15:12:56Z

    Hi Haibo,
    
    Attached is v7 with the changes we discussed.
    
    Patch 2 now has an inline comment on the && case explaining the
    outer-bounds approximation and its consistency with existing restriction
    selectivity. The commit message mentions it as well.
    
    Patch 3 uses a separate backend-private header (rangetypes_selfuncs.h)
    instead of selfuncs.h.
    
    Regards,
    Maxime
    

26. Re: Implement missing join selectivity estimation for range types

    Haibo Yan <tristan.yim@gmail.com> — 2026-04-18T04:02:36Z

    On Thu, Apr 16, 2026 at 8:13 AM SCHOEMANS Maxime <maxime.schoemans@ulb.be>
    wrote:
    
    > Hi Haibo,
    >
    > Attached is v7 with the changes we discussed.
    >
    > Patch 2 now has an inline comment on the && case explaining the
    > outer-bounds approximation and its consistency with existing restriction
    > selectivity. The commit message mentions it as well.
    >
    > Patch 3 uses a separate backend-private header (rangetypes_selfuncs.h)
    > instead of selfuncs.h.
    >
    > Regards,
    > Maxime
    >
    
    Hi Maxime,
    
    Thanks for the updated series. Overall I do not have major objections to
    the direction here.
    
    A few small nits on patch 2:
    
       1. In the commit message, I wonder if “the core algorithm is identical”
       is a bit stronger than necessary. Since the main point is that we are
       reusing the same approximation based on outer bounds, something like “the
       same outer-bounds-based estimator can be reused” might be a bit more
       precise.
       2. In a few comments, the wording still says just “range”, but in patch
       2 we are really dealing with range/multirange combinations. I think it
       would be a bit clearer to make that explicit where appropriate, and reserve
       “range” for the underlying range-type/bound-comparison level.
       3. I think it would be good to add the reverse mixed-direction test as
       well, since patch 2 covers multirange × range in addition to range ×
       multirange. Something like:
    
    --------------------------------------------------------
    explain (costs off)
    select count(*)
    from test_mr_join_mr a, test_mr_join_r b
    where a.mr << b.r;
    
    explain (costs off)
    select count(*)
    from test_mr_join_mr a, test_mr_join_r b
    where a.mr >> b.r;
    
    explain (costs off)
    select count(*)
    from test_mr_join_mr a, test_mr_join_r b
    where a.mr && b.r;
    --------------------------------------------------------
    
    I think that would make the mixed-case coverage feel more complete.
    
    Regards,
    Haibo
    

27. Re: Implement missing join selectivity estimation for range types

    SCHOEMANS Maxime <maxime.schoemans@ulb.be> — 2026-04-21T13:54:33Z

    Hi Haibo,
    
    Thanks for the continued feedback. Attached is v8 addressing your nits
    on patch 2:
    
    - Reworded the commit message to say "the same outer-bounds-based
      estimator can be reused" instead of implying the code is just
      duplicated.
    - Made comments in multirangejoinsel type-neutral where they
      unnecessarily said "range" (e.g. "bound histograms" instead of
      "range histograms", "empty values" instead of "empty ranges").
    - Added the reverse mixed-direction tests (multirange x range).
    
    Regards,
    Maxime
    

28. Re: Implement missing join selectivity estimation for range types

    Haibo Yan <tristan.yim@gmail.com> — 2026-04-23T02:25:55Z

    On Tue, Apr 21, 2026 at 6:54 AM SCHOEMANS Maxime <maxime.schoemans@ulb.be>
    wrote:
    
    > Hi Haibo,
    >
    > Thanks for the continued feedback. Attached is v8 addressing your nits
    > on patch 2:
    >
    > - Reworded the commit message to say "the same outer-bounds-based
    >   estimator can be reused" instead of implying the code is just
    >   duplicated.
    > - Made comments in multirangejoinsel type-neutral where they
    >   unnecessarily said "range" (e.g. "bound histograms" instead of
    >   "range histograms", "empty values" instead of "empty ranges").
    > - Added the reverse mixed-direction tests (multirange x range).
    >
    > Regards,
    > Maxime
    >
    
    Hi Maxime,
    
    Thanks for addressing those points — this looks good to me now.
    
    If you don’t mind, I’ve created a CommitFest entry for this:
    https://commitfest.postgresql.org/patch/6668/
    
    I’ve listed both of us as authors.
    
    I’m not a committer yet, so we’ll need someone else to review and
    (hopefully) pick this up for commit.
    
    Thanks again for the work on this.
    
    Best regards,
    Haibo
    

29. Re: Implement missing join selectivity estimation for range types

    SCHOEMANS Maxime <maxime.schoemans@ulb.be> — 2026-04-23T12:32:13Z

    Hi Haibo,
    
    Thanks for creating the CommitFest entry. Could you add Diogo Repas,
    Zhicheng Luo, and Mahmoud Sakr as authors as well? They wrote the
    original patch and the underlying algorithm. The earlier CF entry is
    at https://commitfest.postgresql.org/patch/3821/ for reference.
    
    Regards,
    Maxime
    

30. Re: Implement missing join selectivity estimation for range types

    Haibo Yan <tristan.yim@gmail.com> — 2026-04-24T18:44:34Z

    On Thu, Apr 23, 2026 at 5:32 AM SCHOEMANS Maxime <maxime.schoemans@ulb.be>
    wrote:
    
    > Hi Haibo,
    >
    > Thanks for creating the CommitFest entry. Could you add Diogo Repas,
    > Zhicheng Luo, and Mahmoud Sakr as authors as well? They wrote the
    > original patch and the underlying algorithm. The earlier CF entry is
    > at https://commitfest.postgresql.org/patch/3821/ for reference.
    >
    > Of course — I’ve added Diogo Repas, Zhicheng Luo, and Mahmoud Sakr as
    authors as we
    
    > Regards,
    > Maxime
    >
    Thanks for the reference.
    
    Best regards,
    Haibo