SQL Server string statistics

Co-written with Claude, who ran much of the testing and research.

String statistics

Statistics are what cardinality estimation works from. They have three parts: the header, the density vector and a histogram. I described them in the chapter Les statistiques et la cardinalité of my book Optimiser SQL Server (in French), and in the video Introduction aux statistiques dans SQL Server (in French).

The histogram of a statistics object splits the values of the first column into at most 200 steps. It answers Nom = 'Dupont' or Nom >= 'Ma' AND Nom < 'Mb' well, and Email LIKE '%.org' badly: the end of a string says nothing about its place in sort order. For these predicates, SQL Server 2005 added a second object, stored with the statistics, which the documentation calls string summary statistics.

DBCC SHOW_STATISTICS is the historical command to read a statistics object. It returns three result sets: the header, the density vector and the histogram; the options WITH STAT_HEADER, DENSITY_VECTOR and HISTOGRAM limit the output to one of them. Since SQL Server 2012 SP1, SELECT permission on the table and on all the columns of the statistics is enough; before that, you had to own the table or be a member of sysadmin, db_owner or db_ddladmin. Two dynamic management functions partly replace it, and lend themselves better to queries over a whole database: sys.dm_db_stats_properties (SQL Server 2008 R2 SP2 and 2012 SP1) for the header, and sys.dm_db_stats_histogram (SQL Server 2016 SP1 CU2) for the histogram. Neither returns the density vector, the String Index property or the content of the string summary: for string statistics, DBCC SHOW_STATISTICS remains the only documented command.

The DBCC SHOW_STATISTICS documentation page is practically the only place where Microsoft documents string statistics today. It says that they are stored separately from the histogram, that they are used for LIKE predicates, and that they are created on the first key column of the statistics when it is char, varchar, nchar, nvarchar, varchar(max), nvarchar(max), text or ntext. A sentence added at the end of August 2026 (according to the page history on GitHub) excluded columns with a UTF-8 collation; since October 7, it only excludes char and varchar columns in those collations. No documented command shows the content of the summary.

The rest comes from two white papers, Statistics Used by the Query Optimizer in Microsoft SQL Server 2005 and its 2008 version. They mention a “patented technology” that summarizes the frequency distribution of substrings for pattern forms such as 'abc%', '%abc', '%abc%', 'a_c', 'a[bc]d', state that an explicit ESCAPE defeats these statistics, and that a string longer than 80 characters is reduced to its first 40 and last 40 characters.

The patent is US 6,829,602, “System and method for using a compressed trie to estimate like predicates”, filed by Microsoft in 2002. No Microsoft source in the SQL Server documentation cites it, but when you look at the summary stored in a statistics object, you find exactly the structure the patent describes. Moreover, the engine names the selectivity calculator that uses this summary CSelCalcTrieBased (output of trace flag 2363, see “Reading the calculator”). As in the patent, the summary is a compressed trie of whole strings, with a count per node. The patent builds the trie from a representative set of strings, and scales the estimate up to the whole table: if a quarter of the rows were inserted, the estimate is multiplied by four. Likewise, SQL Server only stores part of the table’s strings in this trie. To estimate a LIKE, the optimizer counts the strings of this sample that match the pattern, and multiplies the proportion by the number of rows in the table: on the Contact.ProspectUS table of PachaDataFormation, the sample database I use in my training courses and articles, 241 of the 2,825 strings in the sample end with .org, and the estimate is 1,000,000 × 241 / 2,825, or 85,310 rows. The section “Reading the summary” shows how to check it.

A trie (the word comes from retrieval) is a tree in which each path, from the root to a node, spells a string. The strings Martin, Martinez and Marty share a node Mart, which has two children, in and y; in has a child of its own, ez. A node counts how many strings of the sample end on it: 1 for Martin, 1 for Martinez, 1 for Marty, 0 for Mart. In a plain trie, each node holds a single character: Mart would take four nodes in a row, M, a, r and t, each with a single child. A compressed trie (also called a radix tree, or PATRICIA tree) merges these runs of single-child nodes into one node holding the whole sequence of characters: Mart then fits in one node instead of four. That is the shape of the SQL Server summary, where the pieces of all nodes are stored end to end in a single sequence of characters, and each node gives the position and length of its own piece in that sequence. Strings that share their beginning, such as family names or codes with a common prefix, take little space this way.

flowchart TD
    R(("root")) --> M["Mart<br/>0 strings"]
    M --> I["in<br/>1 string: Martin"]
    M --> Y["y<br/>1 string: Marty"]
    I --> E["ez<br/>1 string: Martinez"]

Everything below was measured on SQL Server 2025 CU7 (17.0.4065.4), compatibility level 170, unless the legacy estimator is mentioned.

Finding the string statistics

The examples use the Contact.ProspectUS table of PachaDataFormation: a million prospects, Nom (last name) and Email as varchar, collation French_CI_AS. The table has auto-created statistics on these two columns (_WA_Sys_...). The database load script recomputed them with UPDATE STATISTICS ... WITH FULLSCAN: they read the million rows (rows_sampled equals rows in sys.dm_db_stats_properties), not the sample an automatic creation would have taken. On a million rows, the default sampling reads enough rows to fill the string summary: FULLSCAN does not change its size, but it changes the strings kept, hence the estimates. Here I call DBCC SHOW_STATISTICS with the column name in place of the statistics name, which is supported and convenient:

USE [PachaDataFormation];
GO
-- The String Index column is YES or NO
DBCC SHOW_STATISTICS ('Contact.ProspectUS', Email) WITH STAT_HEADER;
DBCC SHOW_STATISTICS ('Contact.ProspectUS', Nom) WITH STAT_HEADER;

No system view shows this information: neither sys.stats nor sys.dm_db_stats_properties, nor sys.dm_db_stats_histogram. To review all the statistics of a database, you have to run DBCC SHOW_STATISTICS ... WITH STAT_HEADER one statistics object at a time, for instance in a cursor with INSERT ... EXEC.

By column type and collation, with statistics on the same 100,000 values, computed with FULLSCAN:

The UTF-8 exclusion therefore only affects char and varchar, as the documentation says: an nvarchar declared with the same collation keeps its summary. For it, the _UTF8 suffix changes nothing anyway: nchar and nvarchar stay in UTF-16 whatever the collation (Collation and Unicode support), and only the comparison rules of the rest of the name apply (Latin1_General_100_CI_AS_SC). The suffix only changes the encoding of char and varchar, which become UTF-8. The same holds for an auto-created statistics object (_WA_Sys_...), with the default sampling.

The predicates that benefit

The cardinality estimator hands each predicate to a selectivity calculator, a specialized internal component. The ones that matter here are CSelCalcColumnInInterval for an interval read from the histogram, CSelCalcHistogramComparison for a comparison, CSelCalcTrieBased for the string summary and CSelCalcFixedFilter for a fixed guess. An undocumented trace flag shows this information, as the section “Reading the calculator” explains. If the string summary was used, the calculator is CSelCalcTrieBased.

On Contact.ProspectUS, plan estimates, actual counts and the calculator used:

USE [PachaDataFormation];
GO
-- Three ways to write the same prefix filter
SELECT Nom FROM Contact.ProspectUS WHERE Nom LIKE 'Mc%';
SELECT Nom FROM Contact.ProspectUS WHERE Nom >= 'Mc' AND Nom < 'Md';
SELECT Nom FROM Contact.ProspectUS WHERE LEFT(Nom, 2) = 'Mc';

-- A suffix
SELECT Nom FROM Contact.ProspectUS WHERE Email LIKE '%.org';
SELECT Nom FROM Contact.ProspectUS WHERE RIGHT(Email, 4) = '.org';
SELECT Nom FROM Contact.ProspectUS WHERE CHARINDEX('.org', Email) > 0;

Surprisingly, the prefix search (Nom LIKE 'Mc%') goes through the string summary rather than the histogram, and gets a better result: for the equivalent interval, the histogram has to spread the rows of the steps where the bounds fall, whereas the summary counted the strings of its sample. LEFT is estimated as an interval, by another computation on the histogram. On another test table, the gap becomes huge. It has a million rows, and the 1,000 values starting with QA1 are the highest of the column: they all fall into the last step of the histogram. The interval s >= 'QA1' AND s < 'QA2' is estimated there at 2 rows. LIKE 'QA1%', which goes through the summary, is estimated at 710 or 1,065 rows, depending on the statistics rebuild (see “The sample”).

For RIGHT, the output of trace flag 2363 shows two computations: a fixed guess of 10%, then an equality estimate drawn from the density of the Email column, which is nearly unique, and gives one row for 85,060 actual rows. CHARINDEX gets a fixed guess of 30%: no statistics describe its result, and the optimizer applies 30% to any >, >=, < or <= comparison it cannot estimate, such as LEN(Email) > 10 or Email > @v with a local variable. Email <> @v gets 90%; Email = @v is estimated from the density. On a function of the column, = goes through 10% then through the density, like RIGHT (LEN(Email) = 10: one row), and <> is estimated like a < or a > (LEN(Email) <> 10: 510,000).

On the test set, with three-character strings placed at the start, middle or end of the string, the patterns 'abc%', '%abc', '%abc%', 'a_c%', '%a[bc]_%' and NOT LIKE all go through the summary. It follows the collation: '%Vill%' and '%vïll%' give the same estimate on a French_CI_AI column; with _CS_AS or _BIN2, '%zqw' and '%ZQW' are estimated separately, each fairly close to reality.

A pattern with several wildcards is estimated as a whole, with no independence assumption between its pieces. On 100,000 rows, with AAA and BBB each present in half of the strings: when they never appear in the same string, '%AAA%BBB%' is estimated at 3.6 rows for 0; when they always appear together, at 49,982 for 50,000.

The legacy estimator (USE HINT ('FORCE_LEGACY_CARDINALITY_ESTIMATION')) reads the same summary: same estimates, to the decimal, for all the measured LIKE predicates on literals that it estimates through the summary. Its estimates without the summary do differ (see below).

Reading the calculator

The calculator names come from trace flag 2363, which is undocumented. Together with trace flag 3604, it writes the details of the current estimator’s selectivity computation to the messages tab:

USE [PachaDataFormation];
GO
SELECT Nom
FROM Contact.ProspectUS
WHERE Email LIKE '%.org'
OPTION (RECOMPILE, QUERYTRACEON 3604, QUERYTRACEON 2363);

Plan for computation:
  CSelCalcTrieBased
      Column: QCOL: [PachaDataFormation].[Contact].[ProspectUS].Email
Selectivity: 0.0853097

The limits of the summary

The string summary cannot be used in the following cases:

• The column is used in an expression or passed to a function;
• The pattern is in a local variable, alone or concatenated with wildcards, unless OPTION (RECOMPILE) is used;
• The pattern is nvarchar while the column is varchar, whether it is an N'...' literal or a parameter;
• The LIKE has an ESCAPE clause, even a useless one;
• The column is char or varchar with a UTF-8 collation: its statistics have no summary;
• The column is not the first column of any statistics object;
• The pattern contains no wildcard: it is then an equality, estimated from the histogram.

The following table shows the estimate of various predicates on a test table of a million random hexadecimal strings, where 1,000 strings start with QA1, 10,000 contain QB2 and 100,000 end with QC3. All the forms look for the 10,000 strings that contain QB2, and all were measured with the same statistics.

In practice:

• To search for a wildcard character, escape it with brackets rather than with ESCAPE: '%K[_]9%' is estimated through the summary (CSelCalcTrieBased), '%K\_9%' ESCAPE '\' gets the 9% guess; even a useless ESCAPE, '%QB2%' ESCAPE '\', goes from 9,936 to 90,000. The 2005 white paper already said that an ESCAPE makes SQL Server guess the selectivity, and this is still true on SQL Server 2025, with a literal pattern.
• A function around the column (LOWER, UPPER, RTRIM) loses the summary. On a case-insensitive collation, LOWER adds nothing to the result and costs the estimate: 90,000 for '%qb2%', and 3 rows for LOWER(s) LIKE 'qa1%', estimated from the histogram, against 1,065 for s LIKE 'QA1%' (1,000 actual). On Contact.ProspectUS, LOWER(Email) LIKE '%.org' also gets the guess of 90,000.
• A local variable is not sniffed at compile time: the 9% guess applies, unless OPTION (RECOMPILE) is used. A parameter is sniffed, for its first value only: a procedure compiled for '%QA1%' (estimated at 1,065) kept that plan for '%QC3%', which returns 100,000 rows.
• An nvarchar pattern compared with a varchar column also loses the summary: on Contact.ProspectUS, Email LIKE N'%.org' gets the 9% guess (CSelCalcFixedFilter (0.09)), as does an @m nvarchar(20) parameter passed through sp_executesql, whereas a varchar(20) parameter gets the summary estimate. An nvarchar prefix goes through the histogram, and fares badly: Email LIKE N'ab%' is estimated at 430 rows, against 2,478 for 'ab%', for 2,669 actual rows. SqlClient infers NVarChar from a .NET String when the parameter type is not specified (Configuring parameters), and the JDBC driver sends strings as Unicode as long as sendStringParametersAsUnicode is true, its default (connection properties). So, as has long been advised, declare the parameter with the column’s type.
• Switching a varchar column to a UTF-8 collation removes the summary from its statistics. LIKE patterns that start with a wildcard are estimated at 9%, prefixes go through the histogram ('QA1%': 2 rows estimated for 1,000). On a UTF-8 copy of the test set, '%QC3' went from 100,852 (for 100,000) to 90,000, and '%QB2%' from 9,233 (for 10,000, on another build of the statistics) to 90,000.
• A multi-column statistics object only has a summary for its first column, as with its histogram.

These estimates without the summary differ by estimator. The current estimator applies 9% to any LIKE with a leading wildcard that it cannot estimate (CSelCalcFixedFilter (0.09)), whatever the length of the pattern; a prefix without the summary, or with ESCAPE, is estimated from the histogram ('QA1%' ESCAPE '\': 2 rows for 1,000). The legacy estimator depends on the length: on this million-row set, without the summary, '%Q%' gives 612,216, '%QB%' 306,108, '%QB2%' 204,072, an eleven-character pattern 55,656: a proportion divided by the number of characters, for a literal pattern enclosed in %. A suffix '%QC3' gets half of it, 102,036. The proportion depends on the column: 61.2% here, from 41% to 74% on other sets, of strings of 10 to 60 characters. The values of the CE 70 column of the table are therefore specific to this set, while the 90,000 of the current estimator show up everywhere. Internal wildcards give other values, not measured here.

Reading the summary

The summary is stored in the statistics blob, along with the histogram. DBCC SHOW_STATISTICS ... WITH STATS_STREAM returns the whole blob, preceded by a 64-byte header, and it can be captured in T-SQL with INSERT ... EXEC into a varbinary(max) column. The small table example below does just that.

The format is undocumented. I used Claude to work it out, and it did so by building tables of a few rows whose every byte it knew, changing only one thing from one table to the next, then comparing the blobs. The summary follows the histogram, after a fixed marker. Its header gives the number of NULLs met by the sampling, the number of sampled values, NULLs included, the number of distinct values in the sample, where NULL counts as one, 40 twice, the truncation lengths, eight zero bytes, and the number of characters that follow. Then come the characters of the sample, end to end, then the nodes of the trie.

The easiest way is to see it on a small table. This one has eight names, Martin twice; under eleven rows, the sample keeps them all:

USE [PachaDataFormation];
GO
CREATE TABLE dbo.DemoTrie (Nom varchar(50) COLLATE French_CI_AS);
INSERT dbo.DemoTrie (Nom)
VALUES ('Martin'), ('Martinez'), ('Marty'), ('Martin'),
       ('Dupont'), ('Durand'), ('Dubois'), ('Dupuis');
CREATE STATISTICS st_Nom ON dbo.DemoTrie (Nom) WITH FULLSCAN;
GO
-- The statistics blob, in hexadecimal
DECLARE @stream TABLE (stats_stream varbinary(max), [rows] bigint, data_pages bigint);
INSERT @stream EXEC ('DBCC SHOW_STATISTICS (''dbo.DemoTrie'', st_Nom) WITH STATS_STREAM');
SELECT CONVERT(varchar(max), stats_stream, 2) AS blob FROM @stream;
GO
DROP TABLE dbo.DemoTrie;

The summary header announces 0 NULLs, 8 sampled values, 7 distinct, then 26 characters, which are the pieces of all the nodes end to end: DuboispontuisrandMartinezy. Eleven five-byte nodes follow, in preorder:

The first byte holds the flags: 0x80 when the node has a sibling after it, 0x40 when the next node is its first child. Its four low bits store the count when it does not exceed 15: 2 for Martin, 1 for the other strings, 0 for nodes where no string ends, such as Du or Mart. A larger count adds one byte after the node, flagged by 0x10, or four, flagged by 0x20 (249 is the largest one-byte count I have seen, 295 the smallest four-byte one). The second byte gives the length of the piece, the next three its position in the character sequence. The string of a node is the sequence of its ancestors’ pieces, then its own: you read Du, then p, then ont, and get Dupont.

flowchart TD
    R(("root")) --> DU["Du · 0"]
    R --> MART["Mart · 0"]
    DU --> BOIS["bois · 1: Dubois"]
    DU --> P["p · 0"]
    DU --> RAND["rand · 1: Durand"]
    P --> ONT["ont · 1: Dupont"]
    P --> UIS["uis · 1: Dupuis"]
    MART --> IN["in · 2: Martin"]
    MART --> Y["y · 1: Marty"]
    IN --> EZ["ez · 1: Martinez"]

The summary stores no substrings: these are whole strings, as varchar in the column’s code page, as nvarchar in UTF-16. With a case-insensitive collation, MiXeD, mixed and Mixed make a single entry, with a count of 3.

So there is only one trie per statistics object, and it stays small: about 2,800 strings at most, of 80 characters at most, some 224 KB before the sharing of common beginnings, and it is around 200 KB (194 KB for varchar, 212 KB for nvarchar in my tests) that SQL Server halves the sample (see “The sample”). Nor is the trie used as a search engine. For LIKE '%.org', the estimate equals exactly the number of strings of the sample that match the pattern, as if the optimizer rebuilt them one by one to apply the LIKE to them; I have not seen how it walks the tree to get there, only the result. A trie only speeds up searching by the start of a string anyway, which is of no use for a pattern starting with %. It serves to store the sample compactly and to count duplicates; a few thousand comparisons at compile time cost little.

The script string-summary.sql decodes the summary of a statistics object, lists the sampled strings and computes the estimate the summary gives for a pattern, provided the predicate uses it (pattern of the column’s type, no function around the column). Run as is, on the statistics of Contact.ProspectUS.Email, it finds 2,825 sampled values, 29 of them NULL, and 241 strings matching '%.org': 1,000,000 × 241 / 2,825 = 85,309.7, the plan estimate.

The sample

A 10,000-row table of values 0000001 to 0010000 gives a summary of 510 strings, 19 or 20 values apart in sort order. The same values inserted in reverse order, or in random order, give the same 510 strings: the sample is taken at a fixed step in the sorted stream of the build, whatever the physical order of the rows. A value present in 30% of the rows takes 153 of the 510 places, which is 30%.

Its size is 5% of the rows read by the statistics plus 10, without exceeding the number of rows (a four-row table keeps them all): 510 strings for 10,000 rows, 1,010 for 20,000, 2,510 for 50,000. With sampling, it is 5% of the sampled rows: on a table of 40,000 wide rows, SAMPLE 2 PERCENT reads 984 rows, and the summary keeps 59 strings, against 2,018 with FULLSCAN. It then levels off around 2,820: the cap is reached around 56,000 rows, and it holds up to 3,000,000, the largest table measured (2,814 to 2,830 depending on the data and on parallelism). The cap is also a space limit, not only a number of strings: when the sample does not fit in the summary, SQL Server keeps one string out of two. On 200,000 distinct and dissimilar strings, with MAXDOP = 1, the sample keeps 2,824 strings of 65 characters, and drops at once to 1,412 strings of 66 characters; the stored statistics then weighed 211 KB. What counts is the space taken in the trie, not the length: 200-character strings that share their beginning keep all 2,824. With nvarchar, the starting cap is lower, 2,409 strings, and it drops to 1,205 between 43 and 44 characters (86 and 88 bytes), for a summary of about 212 KB against 194 KB for varchar at the same point. This starting cap only depends on the character width: 2,824 for char, varchar and varchar(max), 2,409 for nchar, nvarchar and nvarchar(max), whatever the declared length of the column, its collation (BIN2, SQL collation, Japanese or UTF-8) or the length of the strings below the threshold. The rule that sets it remains to be found. The sample of the e-mail addresses of the demo database holds 2,410 strings as nvarchar, against 2,825 as varchar.

The estimate of a LIKE with a wildcard can then be computed exactly: the number of rows in the table, multiplied by the number of strings of the sample that match the pattern, divided by the size of the sample. When no string matches, the count is 0.1. On ten patterns ('%x%', 'x%', '%x', _, [bc], two internal %), the computation done on the decoded sample gave the plan estimate to the decimal. An equality without wildcard goes through the histogram.

Estimates therefore move in steps of one sampled string, 354 rows on the million prospects (1,000,000 / 2,825), with a floor of 35.4:

USE [PachaDataFormation];
GO
-- Estimate against actual count, for names of different frequencies
SELECT Nom FROM Contact.ProspectUS WHERE Nom LIKE '%Aguila';
SELECT Nom FROM Contact.ProspectUS WHERE Nom LIKE '%Baldwin';
SELECT Nom FROM Contact.ProspectUS WHERE Nom LIKE '%Wilson';

The same floor shows on tables of different sizes:

The ratio is ten times the sample size: 5,100 for 510 strings, 15,100 for 1,510, 28,140 for 2,814. On the three-million-row table, a substring present 1, 10 or 100 times is estimated at 106.5, like an absent substring; at 999 occurrences, it is estimated at 1,065, one string of the sample; at 10,000, at 11,719, eleven strings of a sample of 2,816, built another time. For 200-character strings that are all different, the sample drops to about 1,410 strings as varchar (1,200 as nvarchar), and the floor to about the number of rows divided by 14,000.

Such a small sample still estimates frequent patterns well, because its precision depends on the number of strings that match the pattern, not on the fraction of the table it represents. That is the principle of polling: a thousand people interviewed give the same margin of error for a small town as for a large country. For a proportion p measured on n strings, the typical relative error is about √((1 − p) / (n × p)). With '%.org', 241 strings of the sample match the pattern, and the expected error is about 6%: the estimate of 85,310 for 85,060 actual rows is therefore partly luck, a 10% gap would have been just as normal.

The fixed step in sort order also favors prefixes. The rows matching 'Mc%' form a contiguous block in that order, and a step of 354 rows always lands in it 49 or 50 times: the error does not exceed one sampled string, or 354 rows, and you get 17,699 estimated rows for 17,620. A suffix or a substring, scattered across the sort order, has no such advantage, and the sample behaves for them roughly like a random draw.

For a rare pattern, the precision is that of a sample of a few dozen strings. A substring present in 1% of a million rows, so 28 strings expected in the sample, appeared 27, 32, 28 then 27 times over four successive UPDATE STATISTICS ... WITH FULLSCAN, with no change to the data: estimates of 9,585, 11,356, 9,947 and 9,581 for 10,000. In parallel, the sample size also varied, from 2,815 to 2,818 strings. With MAXDOP = 1, the rebuilds all give the same sample, of 2,824 strings, which here held the substring 22 times: 7,790 estimated rows. On three rebuilds of another table, the same effect had given 5,329, 10,653 and 6,392 for 10,000.

The SQL Server 2005 documentation (Index Statistics) warned that the summary is not kept when it exceeds what the engine can maintain, with the example of 85,000 unique and dissimilar varchar(80) values, with FULLSCAN. The example no longer reproduces: with 85,000 unique 80-character values, String Index is YES, and the sample is reduced to 1,413 strings.

Beyond 80 characters

The white paper rule still holds. A table of 100,000 strings of 200 characters, with a three-character substring placed at position 5, 60, 100 or 190, a quarter of the rows each:

Positions 60 and 100 fall outside the first 40 and the last 40 characters: the sample does not contain them, and they get the floor. With strings of 79 to 82 characters and a substring straddling the 40th and 41st characters, the estimate is right at 79 and 80 characters (25,710 and 25,994), and drops to 1,634 then 1,136 at 81 and 82, for Latin1 varchar as for nvarchar; these two values come from chance occurrences elsewhere in my hexadecimal strings, and a substring found nowhere else drops to the floor.

The summary stores the first 40 and the last 40 characters joined together, so a pattern can match across the junction. On 100,000 strings of 200 characters with a Q at position 40 and a W at position 161, '%QW%', which appears in no row, is estimated at 100,000; '%Qm%' and '%mW%', present in every row, are estimated at 3.5.

For varchar, the threshold is counted in bytes. On a varchar column in Japanese_CI_AS whose first ten characters take two bytes each, a substring at characters 39 to 41 stays visible in a 76-character string (86 bytes), and disappears in a 79-character string (89 bytes): 3.6 rows estimated for 25,000. The same value as nvarchar is still estimated at 24,230: there, the threshold is 80 characters.

On varchar(max) columns of 100 to 20,000 characters, a prefix and a suffix are well estimated, with the imprecision of a sample of about 1,400 strings; everything in between is invisible. For a comments or descriptions column, a LIKE '%word%' whose occurrences are only in the middle of the texts can therefore get the estimate of an absent pattern, as in these tests. To search for words in long text, full-text search (CONTAINS) is the intended tool; it finds words and word prefixes, and misses a fragment taken from the middle of a word.

Key points

• A LIKE that compares the column, without a function around it, to a literal is often better estimated than you would think, '%abc%' included. Write it that way rather than with LEFT, RIGHT, CHARINDEX or LOWER.
• Escape a wildcard with brackets, not with ESCAPE.
• A pattern in a local variable gets a fixed guess; OPTION (RECOMPILE) brings back the summary estimate, and a parameter of the column’s type gets it for its compiled value.
• A varchar with a UTF-8 collation has no string summary; an nvarchar with the same collation has one.
• Pass the pattern in the column’s type: an nvarchar literal or parameter against a varchar column loses the summary (9% for a pattern that starts with a wildcard, the histogram for a prefix).
• The summary is a sample of 5% of the rows read plus 10, capped around 2,800 strings from about 56,000 rows on (2,400 for nvarchar, half as many for long, dissimilar strings). A pattern present in fewer than about one row in 2,800 can be estimated as absent, and a rare pattern is estimated with the imprecision of a small sample.
• Of a long string, the summary only keeps the first 40 and the last 40 characters (bytes for varchar), joined together.

Possible improvements

Now that the format can be read, one may wonder how it could evolve. The following ideas are a reader’s opinion, without any measurement of the cost of each change: Microsoft has constraints that cannot be seen from here, such as compile time, blob size or format compatibility between versions.

Four cases lose the summary or mislead it, while the fix seems within reach. On a 100,000-row table where 2,000 rows end with .org, the varchar pattern is estimated at 1,954 rows, and each of the first three cases at 9,000:

• an nvarchar pattern against a varchar column, N'...' literal or parameter, loses the summary, and a pattern that starts with a wildcard gets the 9% guess. Converting it to the column’s type, when the conversion loses nothing, would be enough. .NET drivers send strings as nvarchar by default, which makes this case common;
• ESCAPE also loses the summary, although the estimate already consists in applying a LIKE to the strings of the sample;
• LOWER(column) changes nothing in the result on a case-insensitive collation, and could be ignored for the estimate;
• the 40 + 40 character truncation joins the beginning and the end of the string. On 100-character strings where a Q ends the first 40 and a W starts the last 40, '%QW%', which matches no row, is estimated at 100,000. A junction marker, which the pattern could not cross, would avoid these false matches. The opposite effect, a substring taken from the dropped part and estimated at the floor, is the price of the truncation itself.

Other ideas touch the core of the mechanism, and their value depends on the data:

• the trie already counts duplicates, but only in the sample. For a column of a few distinct values over a million rows, the values and their exact row counts would fit in a few bytes, and the estimate would become exact;
• all patterns absent from the sample get the same floor, a tenth of a string, although an absent two-character pattern is far more likely than an absent twelve-character one. The literature on substring estimation, such as pruned suffix trees (Krishnan, Vitter and Iyer, 1996) or the work of Chaudhuri, Ganti and Gravano (2004) on underestimation, proposes breaking the absent pattern into pieces that are present;
• the sample size does not follow the table size: on a hundred million rows, if the cap holds, the arithmetic gives a floor of 3,500 rows. A sample that grew a little with the table, within the space limit, would reduce this jump;
• with parallelism, two successive UPDATE STATISTICS ... WITH FULLSCAN, with no change to the data, give different samples, hence different estimates. Sampling at the same step, whatever the split between threads, would make plans reproducible.

The current trade-off is still defensible: a sample of 2,800 strings in a compressed trie fits in about 200 KB, applies quickly at compile time, estimates frequent patterns well, and its errors on rare patterns seldom change the plan.