5

I have this statistics histogram vector for my non-clustered index made on LastName column of a table named AspNetUsers.

enter image description here

If I run a query as SELECT * FROM dbo.AspNetUsers WHERE LastName = 'Baker' it returns 6 rows as estimated rows, cause Baker is the RANGE_HI_KEY of the one of the step so the EQ_ROWS value is my Estimated rows count. Similarly, If i run a query as SELECT * FROM dbo.AspNetUsers WHERE LastName = 'Bacilia', it returns 1 row as estimated rows, cause Bacilia fells in to 'Baker' step range, so the AVG_RAGE_ROWS value of that step is my estimated rows count.

Similarly, to my understanding if i do query as SELECT * FROM dbo.AspNetUsers WHERE LastName LIKE 'Ba%' it matches 2 steps (Baker and Batagoda), so it should return 27 + 51 (RANGE_ROWS) + 6 + 4 (EQ_ROWS) = 88. But it returns 99 rows as estimation.

How does this Cardinality Estimation is works with a LIKE Query? Does it use different formulae for estimating number of rows when doing a LIKE query?

1 Answer 1

4

Does it use different formulae for estimating number of rows when doing a LIKE query?

Yes.

I don't know much about the gory details but see the mention of "string summary statistics" here

the statistics object contains string summary statistics to improve the cardinality estimates for query predicates that use the LIKE operator; for example, WHERE ProductName LIKE '%Bike'. String summary statistics are stored separately from the histogram and are created on the first key column of the statistics object when it is of type char, varchar, nchar, nvarchar, varchar(max), nvarchar(max), text, or ntext..

I don't have your sample data but just gave it a whirl with the player_overviews_unindexed tennis player dataset.

The relevant part of the histogram for that was

 RANGE_HI_KEY    RANGE_ROWS     EQ_ROWS   DISTINCT_RANGE_ROWS   AVG_RANGE_ROWS
----------------------------------------------------------------------------------
       Aubone            40           4                    37         1.081081
        Baker            79          12                    60         1.316667
       Barker            71           6                    55         1.290909
       Barton            46           4                    25             1.84
        Bates            26           5                    20              1.3
       Becker            45           6                    35         1.285714

The statistics only show definitively that the range will contain at least 170 rows (12 + 71 + 6 + 46 + 4 + 26 + 5). And at most 294 when the end ranges are taken into account.

  • 79 last_name > 'Aubone' and last_name < 'Baker'
  • 12 last_name = 'Baker'
  • 71 last_name > 'Baker' and last_name < 'Barker'
  • 6 last_name = 'Barker'
  • 46 last_name > 'Barker' and last_name < 'Barton'
  • 4 last_name = 'Barton'
  • 26 last_name > 'Barton' and last_name < 'Bates'
  • 5 last_name = 'Bates'
  • 45 last_name > 'Bates' and last_name < 'Becker'

When I indexed the last_name column the last_name LIKE N'Ba%' predicate gets converted to an index seek on last_name >= N'Ba' AND last_name < N'BB' and residual predicate but the estimates were different.

  • The estimate for last_name >= N'Ba' AND last_name < N'BB' was 180.525 rows.
  • The estimate for last_name LIKE N'Ba%' was 235.935 rows
  • The estimate for LEFT(last_name, 2) = 'Ba' was 171.317 rows.
  • The actual number of rows returned was 241 rows.

For LEFT potentially it is just adding the AVG_RANGE_ROWS value of 1.316667 to that minimum of 170.

When doing the simple index range seek it looks like it just looks at the size of the range of the end histogram steps and the range of these that the query would select and does some interpolation based on that.

So there were 79 rows with last_name > 'Aubone' and last_name < 'Baker' in the histogram (RANGE_ROWS).

enter image description here

It estimates that 77.6735 of those 79 rows will be in the range < 'Ba' and only 1.3265 in the range >= 'Ba' - though in reality the numbers were 34 and 45 respectively.

There are lots of players with surnames (Babcock, Bahrami, Baer, Backe, Baghdatis, 7 * Baileys etc) that fall into that range but it has no way of knowing that from the histogram.

Presumably the string summary statistics does capture the distribution better here than is possible just from the histogram.

12
  • Is there a way we could see those seperate statistics stores outside the Histogram for LIKE queries in SQL server? Feb 5 at 12:28
  • 1
    Based purely on the histogram we know that there are definitely at least 170 rows matching Ba%. We also have a group of 79 rows at the start - which all we know about is that they are in the range > 'Aubone' and < 'Baker' so anywhere between 0 and 79 of these could match and we have a similar group of 45 at the end in the range last_name > 'Bates' and last_name < 'Becker' so anywhere between 0 and 45 of those could start with "Ba" Feb 5 at 19:13
  • 1
    The estimate for last_name >= N'Ba' AND last_name < N'BB' was 180.525 rows so SQL Server only estimates 10.525 rows out of the potential 124 in these ambiguous ranges will match - which is quite a big underestimate and worse than the string statistics managed. This was just looking into that. And for the initial chunk of 79 rows it looks like it assumes most of them will belong to the group before the range Ba starts Feb 5 at 19:18
  • 1
    My answer to that question is just it uses "string summary statistics" - that as far as I know aren't documented any further than the quote given from BOL or are available for us to look at. The only additional thing I have to add on that is I believe I read somewhere it uses Tries Feb 5 at 19:53
  • 1
    Yes string statistics are based on tries
    – Paul White
    Feb 6 at 2:12

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.