LGTM! Thanks for fixing this!

Thanks for fixing this!

Reviewed 1 of 3 files at r1, 3 of 3 files at r2, all commit messages.
Reviewable status: complete! 0 of 0 LGTMs obtained (waiting on @jordanlewis and @mgartner)

pkg/sql/opt/memo/statistics_builder.go line 871 at r1 (raw file):

Probably worth adding a stats-specific test for this. Can you add some tests in opt/memo/testdata/stats/scan similar to the tests you added in logic /execbuilder tests?

We can probably fix this issue by adding a check before line 865 or saving the previous value of s.RowCount.

pkg/sql/opt/memo/statistics_builder.go line 884 at r2 (raw file):

							continue
						case types.BytesFamily:
							break LOOP

nit: I'd like to avoid using these GOTO style statements here if possible. I feel like this would be a good candidate for a helper function.

The execbuilder test I added doesn't have stable results - if I dump the histogram after running ANALYZE, the results differ from run to run. I know the statistics collection uses random sampling, but I guess I figured in logic tests we'd fix the seed. Is the proper way to fix this to inject artificial histograms rather than running ANALYZE? And if so, should all of the test cases that need the histograms really just belong in the stats testdata?

Also, in adding the stats test you suggested, I'm noticing that the stats tests have nice histograms with just a few buckets. How do you generate those nice test histograms? Is there a way to ask the stats system to use a lower bucket count?

Reviewable status: complete! 0 of 0 LGTMs obtained (waiting on @mgartner)

pkg/sql/opt/memo/statistics_builder.go line 871 at r1 (raw file):

That's true, we should also avoid editing the row count if we're looking at the wrong kind of histogram. I've fixed that.

But isn't there still the problem in the opposite case, where we're trying to use a histogram for an ordinary, non-inverted scan on a text column, and we see a set of inverted statistics? I think we'd want a guard in the opposite direction, in applyIndexConstraint, that makes sure that we aren't using an inverted histogram for a forward scan.

What I don't understand is why this theoretical problem doesn't manifest as a type error, like the original bug did.

The execbuilder test I added doesn't have stable results - if I dump the histogram after running ANALYZE, the results differ from run to run. I know the statistics collection uses random sampling, but I guess I figured in logic tests we'd fix the seed. Is the proper way to fix this to inject artificial histograms rather than running ANALYZE? And if so, should all of the test cases that need the histograms really just belong in the stats testdata?

You could use INJECT STATISTICS, but I think it's also fine to get rid of these execbuilder tests altogether.

Also, in adding the stats test you suggested, I'm noticing that the stats tests have nice histograms with just a few buckets. How do you generate those nice test histograms? Is there a way to ask the stats system to use a lower bucket count?

We don't currently have a way to control the number of histogram buckets collected by CREATE STATISTICS/ANALYZE (it's hardcoded as 200 for index columns, and 2 for other columns). Those histograms in the stats tests were just manually constructed.

Reviewable status: complete! 0 of 0 LGTMs obtained (waiting on @mgartner)

pkg/sql/opt/memo/statistics_builder.go line 871 at r1 (raw file):

That's true, we should also avoid editing the row count if we're looking at the wrong kind of histogram. I've fixed that.

Doesn't look like you've pushed the fix.

But isn't there still the problem in the opposite case, where we're trying to use a histogram for an ordinary, non-inverted scan on a text column, and we see a set of inverted statistics? I think we'd want a guard in the opposite direction, in applyIndexConstraint, that makes sure that we aren't using an inverted histogram for a forward scan.

I think you're right.

What I don't understand is why this theoretical problem doesn't manifest as a type error, like the original bug did.

I'm not sure -- it would be good to add some tests that exercise this.

This is ready for another look, I redid it like we discussed on Slack. Now, the code carefully segments inverted histograms from forward histograms in the statistics map, so there's no chance for code to accidentally get the wrong type of histogram when building plans.

Reviewable status: complete! 0 of 0 LGTMs obtained (waiting on @mgartner and @rytaft)

pkg/sql/opt/memo/statistics_builder.go line 871 at r1 (raw file):

Removed this code.

pkg/sql/opt/memo/testdata/stats/inverted-geo line 774 at r3 (raw file):

      │    │    └── stats: [rows=1, distinct(2)=1, null(2)=0, avgsize(2)=4]
      │    │        histogram(2)=  0                                                                                            4.9994e-05                                                                                            0.99988                                                           7.4991e-05
      │    │                     <--- '0107000020E6100000010000000103000020E610000001000000040000008C7D4198BD2B574080A6FD3A111E4D40F0DF86928AA12BC03A59212197A35140CEA3CEE206B863C0FC7649EB60BA53408C7D4198BD2B574080A6FD3A111E4D40' --------- '0102000020E61000000300000005D8E086BB6365C03F9E5737DD1A53C0C04ECDED673B55C06711C00C7C0240C0B8EABD96072856404A9D2C529FC74EC0'

I think the reason for this change is that the test is buggy.

The injected statistics here should have histo_col_type=BYTES, not GEOGRAPHY, unless they were collected on the ordinary column. But I think we don't collect forward statistics on GEOGRAPHY columns. So I think this test is just wrong, thoughts? The fix would be to change the injected stats to be bytes type.

thanks for working through these details!

I thought we had discussed iterating through older statistics to find both forward and inverted histograms? Feel free to open an issue and/or save that work for another PR. I think it's probably worth doing at some point, though (even before we fix #50655), since we can limit the extra computation to only cases where it's useful. For example, we can limit it to cases where we have a string column that also has an inverted index. We will (almost) always collect a forward histogram (it will just be smaller if there is no forward index), so we should try to find both the forward and inverted histograms for these columns.

Reviewed 3 of 5 files at r3, 1 of 1 files at r4, all commit messages.
Reviewable status: complete! 1 of 0 LGTMs obtained (waiting on @jordanlewis, @mgartner, and @rytaft)

pkg/sql/opt/memo/statistics_builder.go line 666 at r4 (raw file):

			if needHistogram {
				invertedColOrds = invertedIndexCols[stat.ColumnOrdinal(0)]
				invertedStatistic = len(invertedColOrds) > 0 && !histogramIsNonBytes(stat.Histogram())

nit: can we remove the double-negative and change this to histogramIsBytes?

pkg/sql/opt/memo/statistics_builder.go line 687 at r4 (raw file):

				// to calling stats.ColStats.Add() on any inverted column statistics
				// created above.
				colStat, _ = stats.ColStats.Lookup(cols)

I don't think you need to do this anymore

pkg/sql/opt/memo/testdata/stats/inverted-geo line 774 at r3 (raw file):

Your change looks good

I am probably missing something, but I thought that we were actually already doing that (and just ignoring all but the most recent one because of the way colStatsMap works:

		for i := 0; i < tab.StatisticCount(); i++ {
			stat := tab.Statistic(i)

As I understood, this loop finds every statistic in the table, including historical statistics.

Reviewable status: complete! 1 of 0 LGTMs obtained (waiting on @jordanlewis, @mgartner, and @rytaft)

That's correct -- we are ignoring all but the most recent one for each set of columns. So in order to make sure that we get both types of histograms, I think we can make a relatively small change (I added a comment below).

Reviewable status: complete! 1 of 0 LGTMs obtained (waiting on @jordanlewis, @mgartner, and @rytaft)

pkg/sql/opt/memo/statistics_builder.go line 669 at r4 (raw file):

			}

			if colStat, ok := stats.ColStats.Add(cols); ok {

I think we can ensure we get both types of histograms by changing this slightly as follows:

if colStat, ok := stats.ColStats.Add(cols); ok {
  // Keep what's already here
} else if colStat.Histogram == nil && needHistogram && !invertedStatistic {
  col := cols.SingleColumn()
  colStat.Histogram = &props.Histogram{}
  colStat.Histogram.Init(sb.evalCtx, col, stat.Histogram())
}

This takes advantage of the fact that stats.ColStats.Add(cols) returns the existing statistic if ok is false.

Reviewable status: complete! 1 of 0 LGTMs obtained (waiting on @jordanlewis, @mgartner, and @rytaft)

pkg/sql/opt/memo/statistics_builder.go line 669 at r4 (raw file):

Sorry for being dense, but I still don't understand what situation this branch defends against that the code doesn't already handle. The code as written does handle finding both the forward and inverted statistic for a given column set regardless of where either is in the list of historical statistics, since the new branch on line 700 gets executed regardless of whether we already have a forward statistic for the column set.

The only situation I can think of where this would change behavior is something like this list of statistics for a column t:

1. a forward statistic with no histogram at time x
2. an inverted statistic with a histogram at time x
3. a forward statistic with a histogram at time x-1

Is this the situation you're thinking of too or am I still missing something?

Reviewable status: complete! 0 of 0 LGTMs obtained (and 1 stale) (waiting on @mgartner and @rytaft)

pkg/sql/opt/memo/statistics_builder.go line 666 at r4 (raw file):

I'm not sure - would we ever get into a situation in which the histogram contains all null buckets? If so, we wouldn't be able to guarantee that the histogram was all bytes, just that it had no non-bytes buckets. That's why I named it this way.

pkg/sql/opt/memo/statistics_builder.go line 687 at r4 (raw file):

Done.

Reviewed 1 of 1 files at r5, all commit messages.
Reviewable status: complete! 0 of 0 LGTMs obtained (and 1 stale) (waiting on @jordanlewis, @mgartner, and @rytaft)

pkg/sql/opt/memo/statistics_builder.go line 666 at r4 (raw file):

I think that could happen if every row in the table is NULL. Maybe the better question is whether we would want to default to creating an inverted or a forward histogram in this case. I'm not sure it really matters in most cases, since I think we should be smart enough to just use the NULL counts and row counts directly to get the correct selectivity even without a histogram. The case where it might matter is if you implement my proposed change below to go back and add a forward histogram when one is found. In particular, if the most recent stats show a table with all NULLs, but historical stats have some non-nulls, we could end up using stale stats.

Alternatively, we could update the TableStatistic interface to include a HistogramType function that returns the type directly (then we wouldn't need to guess and you can get rid of the histogramIsNonBytes function). This info should be available with a bit of plumbing. If you think that's a better route, I'm happy to open a separate PR with that change.

Regardless, it would be good to add a test for this case.

pkg/sql/opt/memo/statistics_builder.go line 669 at r4 (raw file):

I'm thinking of this:

1. an inverted statistic on column c with a histogram at time x
2. a forward statistic on column c with a histogram at time x
3. ... more stats ...

For the first statistic, we will add a forward stat for column c with no histogram, and an inverted stat with a histogram. Once we get to the second statistic, as the code is currently written, we will see that a forward stat has already been added and it will be a no-op. My proposed change would ensure that we still save the histogram for this case.

As an alternative, you could just not add the forward stat if invertedStatistic is true. That might also work.

Reviewable status: complete! 0 of 0 LGTMs obtained (and 1 stale) (waiting on @mgartner and @rytaft)

pkg/sql/opt/memo/statistics_builder.go line 666 at r4 (raw file):

Great point, I took a look and your suggestion was very simple to implement (no plumbing was necessary, the actual data was available on both the test catalog and production stat struct as-is) so I just went ahead and did it.

In the case where the data is all null, no histogram is created at all, so I think we're fine.

      {
          "avg_size": 0,
          "columns": [
              "a"
          ],
          "created_at": "2022-07-28 04:05:28.848149",
          "distinct_count": 1,
          "histo_col_type": "",
          "null_count": 3,
          "row_count": 3
      }

pkg/sql/opt/memo/statistics_builder.go line 669 at r4 (raw file):

Ahh, I see, thanks for spelling it out, you're totally right of course.

We can't not add the forward stat if invertedStatistic is true, because in the case of ordinary inverted index types like JSON, we don't ever collect forward stats on that type - so we'd be missing out on the non-histogram stats.

I think your example snippet is also going to do something slightly weird - it has the potential of creating a statistic that consists of counts from an inverted histogram at time t, and a histogram from a forward histogram at a time t-1 when the counts were different.

The updated code now takes the entirety of the most recent forward statistic that has a histogram... I think that is the optimal thing.

And confirmed this change updated a test case in the trigram stats test file for the better! It now can use a forward histogram for a forward scan even though an inverted histogram on the same column was present.

Reviewable status: complete! 0 of 0 LGTMs obtained (and 1 stale) (waiting on @mgartner and @rytaft)

pkg/sql/opt/memo/statistics_builder.go line 669 at r4 (raw file):
Wait, is this still going to present a problem in a different case? You mention something similar above:

In particular, if the most recent stats show a table with all NULLs, but historical stats have some non-nulls, we could end up using stale stats.

time t-1: statistic with forward histogram for column c
time t: user truncates table
time t+1: statistic with no histogram because the table is empty

In this case, I think the code I just pushed (and your suggested snippet?) would fall into a similar hazard. The newest statistic is missing a histogram because the table is empty, so we replace it with an older statistic that has a histogram, that's now stale and out of date.

We could avoid this hazard with an extra bit per ColumnStatistic that is set to true if the information was derived from an inverted histogram, I guess...

Reviewable status: complete! 0 of 0 LGTMs obtained (and 1 stale) (waiting on @mgartner and @rytaft)

pkg/sql/opt/memo/statistics_builder.go line 669 at r4 (raw file):

I added a commit on top that does this, but it bloats the memo by a bit. PTAL. Bummed that this keeps increasing in complexity.

Reviewed 4 of 5 files at r6, 1 of 1 files at r7, all commit messages.
Reviewable status: complete! 0 of 0 LGTMs obtained (and 1 stale) (waiting on @jordanlewis, @mgartner, and @rytaft)

pkg/sql/opt/memo/statistics_builder.go line 666 at r4 (raw file):

Nice!

pkg/sql/opt/memo/statistics_builder.go line 669 at r4 (raw file):

Is there a way to avoid storing the extra bit in the ColStatsMap since we don't need this info outside of this function? One idea is to just check if we already have an inverted stat for this column. e.g., make a function like this:

func alreadyHasInvertedStat(invColOrds int[], stats *props.Statistics) {
  if len(invColOrds) > 0 {
    invCol := tabID.ColumnID(invColOrds[0])
    invCols := opt.MakeColSet(invCol)
    _, ok := stats.ColStats.Lookup(invCols)
    return ok
  }
  return false
}

Reviewable status: complete! 0 of 0 LGTMs obtained (and 1 stale) (waiting on @mgartner and @rytaft)

pkg/sql/opt/memo/statistics_builder.go line 669 at r4 (raw file):

I moved the state into a map that we're already keeping around in the statsbuilder loop and added more tests that ensure we don't use old histograms even if new statistics have no histograms at all for both the inverted and forward case.

thanks for all your work on this!

Reviewed 1 of 5 files at r3, 14 of 14 files at r9, all commit messages.
Reviewable status: complete! 1 of 0 LGTMs obtained (waiting on @jordanlewis and @mgartner)

pkg/sql/opt/memo/statistics_builder.go line 686 at r9 (raw file):

				//    If these conditions hold, it means that the previous histogram
				//    we found for the current colset was derived from an inverted
				//    histogram, and therefore doesn't have a histogram at all, and the

nit: and therefore doesn't -> and therefore the existing forward statistic doesn't

pkg/sql/opt/memo/statistics_builder.go line 715 at r9 (raw file):

			// Add inverted histograms if necessary.
			if needHistogram && invertedStatistic {
				// Record the fact that we just added an inverted statistic to this

nit: just added -> are adding

Thanks for the patient reviews!

bors r+

Reviewable status: complete! 1 of 0 LGTMs obtained (waiting on @mgartner and @rytaft)