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
From 53291919f536f6e7b04ca87f408e5b95e730ddb0 Mon Sep 17 00:00:00 2001 From: Maxime Schoemans <maxime.schoem...@ulb.ac.be> Date: Mon, 20 Mar 2023 11:48:05 -0400 Subject: [PATCH] Apply division before adding remainder --- src/backend/utils/adt/multirangetypes_selfuncs.c | 5 ++++- src/backend/utils/adt/rangetypes_selfuncs.c | 5 ++++- 2 files changed, 8 insertions(+), 2 deletions(-) diff --git a/src/backend/utils/adt/multirangetypes_selfuncs.c b/src/backend/utils/adt/multirangetypes_selfuncs.c index 7ba4aa8b04..ad14b789f4 100644 --- a/src/backend/utils/adt/multirangetypes_selfuncs.c +++ b/src/backend/utils/adt/multirangetypes_selfuncs.c @@ -1412,11 +1412,14 @@ calc_hist_join_selectivity(TypeCacheEntry *typcache, prev_sel2 = cur_sel2; } + /* P(X < Y) = 0.5 * Sum(...) */ + selectivity /= 2; + /* Include remainder of hist2 if any */ if (j < nhist2) selectivity += 1 - prev_sel2; - return selectivity / 2; + return selectivity; } /* diff --git a/src/backend/utils/adt/rangetypes_selfuncs.c b/src/backend/utils/adt/rangetypes_selfuncs.c index 007e14bcf6..129ef9648f 100644 --- a/src/backend/utils/adt/rangetypes_selfuncs.c +++ b/src/backend/utils/adt/rangetypes_selfuncs.c @@ -1342,11 +1342,14 @@ calc_hist_join_selectivity(TypeCacheEntry *typcache, prev_sel2 = cur_sel2; } + /* P(X < Y) = 0.5 * Sum(...) */ + selectivity /= 2 + /* Include remainder of hist2 if any */ if (j < nhist2) selectivity += 1 - prev_sel2; - return selectivity / 2; + return selectivity; } /* -- 2.17.1
