Structures

A scan evicted by its neighbours

A document listing that scans its rows of the document array kept almost all of its price resident in a held cache of 256 lines on a collection of 145,000 characters, and no chain of range-minimum queries undercut it on any listing. On a collection that outgrows the cache, a chain was predicted to win first on the listings whose own rows outnumber what the cache holds — about 18,700 at seven bits a document — and only for the commonest words. Grown from 125,000 to a million characters of 82 essays, the scan's held price rises fiftyfold, from 0.4 misses a listing to 20.5; below a million no rule beats scanning everything, and at a million the tree's chain wins 174 of 2,000 listings, the smallest with 675 occurrences, nine lines of rows. A rule that walks the chain from 6,775 occurrences costs 12.4 misses a listing, 39% under the scan. What the scan loses is not its own rows overflowing the cache but the commonest words' scans flushing everyone else's.

A document index answers which documents contain this word? without reporting every occurrence. The occurrences of a pattern sit in a contiguous range of rows of the suffix array, and a document array beside it says which document each row came from. The simplest answer reads that range of the document array and marks each document it sees. The output-sensitive answer, due to Muthukrishnan, walks a chain instead: a second array records, for each row, the previous row holding the same document, and a range-minimum query over it finds the first occurrence of each document in the range, one query per document reported. On a word with many occurrences in few documents, the chain does far less work; the shape a range question is about set out the range minimum it rests on, and two bits a value, and what undoes them the succinct form of it measured here.

The lines a constant-time query lands in began counting the range minimum’s cost in cache lines rather than operations, and two lines a superblock priced both answers cold, every line of memory a listing touches counted once. A cache the listings share ran two thousand listings back to back through a cache of a few hundred lines that is never emptied, the way a running index would, and found the scan nearly free. On a collection of 144,617 characters, the frequently asked words’ rows of the document array fit in a couple of hundred lines and stay there; the chains’ structures were spread over four thousand. No chain undercut the scan on a single listing.

Its closing section said this is a fact about small indexes. A document array is n⌈log⁡2d⌉n \lceil \log_2 d \rceil bits, and on a large collection a common word’s rows run to more lines than any cache holds. It predicted that the scan’s held price would grow with the common words’ occurrences, and that a chain would first undercut the scan on a listing when that listing’s rows outnumber the cache. The named risk was the chains’ own side: their resident directories grow with the collection too, and might grow faster than the scan’s hot rows.

A collection that outgrows the cache

The proposal suggested generating a larger collection from the corpus vocabulary. A real one was available instead: a frozen collection of 82 essays, a million characters in all, frozen with its figures and tables removed. Cutting each essay to the same fraction gives the same 82 documents at 125,000, 250,000, 500,000 and 1,000,040 characters, so the document array stays at seven bits a row, 73 rows a 64-byte line, at every size. A cache of 256 lines holds 18,725 rows of it.

The workload is the earlier essay’s. A listing is a word of three or more letters drawn by occurrence, a random position in the text and the word covering it, so words are asked for as often as the text uses them. A thousand listings run first and are charged to nobody, to warm the caches; then two thousand are measured. Four methods answer them, each through its own fully associative LRU cache held across the whole workload: the scan, and the chain walked with three range-minimum structures — the segment tree, the succinct structure laid out as separate arrays, and the same structure interleaved two lines a superblock. Every chain’s replay must list exactly the documents the index lists.

The scan’s price, fifty times over

Grown from 125k to a million characters, the scan's held price rises from 0.4 to 20.5 misses a listing, and a rule that scans below 6,775 occurrences and walks the tree's chain above them costs 12.4 — 39% under the scan, where on every smaller collection the best rule is the scan itselfMisses a listing with 256 lines held, after 1,000 listings to warm the caches, over 2,000 listings drawn by occurrence, for the scan, the three chains and the best rule that scans below an occurrence count and walks the tree's chain above it, at each size: 125,040 characters: scan 0.4, tree 11.9, separate 15.5, interleaved 12.6, rule 0.4; 250,041 characters: scan 1.0, tree 17.3, separate 28.5, interleaved 24.2, rule 1.0; 500,042 characters: scan 3.4, tree 26.1, separate 39.5, interleaved 34.2, rule 3.4; 1,000,081 characters: scan 20.5, tree 35.4, separate 58.9, interleaved 52.9, rule 12.4.0204060characters in the collection (82 essays)misses a listing, 256 lines held125k250k500ka millionchain, separate arrayschain, interleavedchain, treescancount rule, tree82 essays; 2,000 listings by occurrencemisses a listing
Fig. 1 Misses a listing with 256 lines held, over 2,000 listings drawn by occurrence, by collection size. 125,040 characters: scan 0.4, tree 11.9, separate arrays 15.5, interleaved 12.6. 250,041: 1.0, 17.3, 28.5, 24.2. 500,042: 3.4, 26.1, 39.5, 34.2. 1,000,081: 20.5, 35.4, 58.9, 52.9. The best rule that scans below an occurrence count and walks the tree’s chain above it: the scan’s own price at the three smaller sizes, 12.4 at a million.

Grown from 125,000 to a million characters, the scan’s held price rises from 0.4 to 20.5 misses a listing, and a rule that scans below 6,775 occurrences and walks the tree’s chain above them costs 12.4 — 39% under the scan, where on every smaller collection the best rule is the scan itself. The first half of the prediction holds with room to spare: the scan’s price grows with the collection, and faster than the collection. Doubling the text from 500,000 to a million characters multiplies it by six.

The chains grow too, but more slowly: the tree from 11.9 to 35.4, a factor of three over an eightfold growth. At every size below a million the scan is far cheaper than any chain on average. At a million, the scan alone is still cheaper on average than every chain alone, by fifteen misses against the tree; the gain comes only from letting each listing choose.

That last point is where the per-listing view matters. A rule that scans small listings and walks the chain for large ones pays the cheaper method’s price on most of each, and at a million characters the large listings are where the scan has become dear.

Wins that appear all at once

At 256 lines held, the tree's chain undercuts the scan on 0, 0, 3, 174 of 2,000 listings as the text grows through 125k, 250k, 500k, a million characters; the succinct chains follow, 115 and 123 at a millionListings, of 2,000 drawn by occurrence, on which a chain's held misses are fewer than the scan's, 256 lines held, by size: 125,040 characters: tree 0, separate 0, interleaved 0; 250,041 characters: tree 0, separate 0, interleaved 0; 500,042 characters: tree 3, separate 3, interleaved 3; 1,000,081 characters: tree 174, separate 115, interleaved 123.chain, treechain, separate arrayschain, interleaved125k000250k000500k333a million174115123of 2,000 listings, 256 lines heldlistings a chain wins
Fig. 2 Listings, of 2,000, on which a chain’s held misses are fewer than the scan’s, 256 lines held. 125,040 characters: none for any chain. 250,041: none. 500,042: three for each. 1,000,081: tree 174, separate arrays 115, interleaved 123.

At 256 lines held, the tree’s chain undercuts the scan on 0, 0, 3, 174 of 2,000 listings as the text grows through 125k, 250k, 500k, a million characters; the succinct chains follow, 115 and 123 at a million. Nothing, nothing, three, then a twelfth of the workload. The chains do not creep up on the scan as the text grows; they arrive.

The tree leads the succinct chains, as it did when the cache was held on the smaller collection, though the table that fits inside a block and where a crossing moved to had made the succinct structure cheaper in reads per query when nothing is held. Its resident part is its top levels, which every query touches; the succinct structure’s directories are smaller but most of its reads land at content-determined places. In a held cache the structure whose shared part is largest per query keeps the most of its price, and the tree wins more listings for that reason.

The order of the three chains matters less than the shape. Something about the scan changes between half a million and a million characters, and the next plate shows it is not what the prediction expected.

Wins far below the cache’s rows

At a million characters the tree's chain wins only on listings of common words — every one of its 174 wins has 675 or more occurrences — and the smallest of them is 28 times under the 18,725 rows that 256 lines of the document array hold, where the prediction put the crossingEach of the 2,000 listings at 1,000,081 characters (repeated words drawn once): the word's occurrences, against the scan's held misses less the tree chain's, 256 lines held; above nought the chain is cheaper. The chain wins 174 listings, the fewest occurrences among them 675; 256 lines hold 18,725 entries of the document array.0100200occurrences of the word listedscan's misses less the tree's1101001,00010,000rows 256 lines holdtree cheaperscan cheapera million characters, 256 lines heldper listing
Fig. 3 Each listing at 1,000,081 characters, each repeated word drawn once: its occurrences against the scan’s held misses less the tree chain’s, 256 lines held. Above nought the chain is cheaper. The chain wins 174 listings; the fewest occurrences among them is 675. The vertical line is the 18,725 rows that 256 lines of the document array hold.

At a million characters the tree’s chain wins only on listings of common words — every one of its 174 wins has 675 or more occurrences — and the smallest of them is 28 times under the 18,725 rows that 256 lines of the document array hold, where the prediction put the crossing. No listing in the workload comes near the cache’s rows: the commonest word occurs 15,542 times. If chains could only win once a listing’s own rows overflowed the cache, they would not win at all at this size.

A listing of 675 occurrences reads about nine lines of the document array. On the smaller collections those nine lines, once read, stayed in the cache until the word came round again. At a million characters they do not, and the reason is the other listings. The commonest words now have thousands of rows: a listing for the commonest reads 213 lines, most of the cache, and words like it are asked for constantly, because the workload draws by occurrence. Every such scan sweeps through the cache and evicts what the rarer words had left there.

So the scan’s price at a million characters is not its own rows overflowing; it is the neighbours’ rows. The chain wins on a word of 675 occurrences not because its rows are too many but because they will have been flushed by the time it is asked again, while the chain’s walk touches a handful of nodes near the top of the tree that every walk keeps warm.

The cache, not the collection

The scan's advantage is the cache's size, not the collection's: at a million characters it pays 30.2 misses a listing with 64 lines held, 20.5 with 256 and 2.0 with 1,024, while the tree's chain pays 43.1, 35.4 and 23.8Misses a listing at 1,000,081 characters, 2,000 listings by occurrence, by lines held: 64 lines: scan 30.2, tree 43.1, separate arrays 73.5; 256 lines: scan 20.5, tree 35.4, separate arrays 58.9; 1024 lines: scan 2.0, tree 23.8, separate arrays 30.6.scanchain, treechain, separate arrays64 lines30.243.173.5256 lines20.535.458.91024 lines2.023.830.6a million charactersmisses a listing
Fig. 4 Misses a listing at 1,000,081 characters, by lines held. 64 lines: scan 30.2, tree 43.1, separate arrays 73.5. 256 lines: scan 20.5, tree 35.4, separate arrays 58.9. 1,024 lines: scan 2.0, tree 23.8, separate arrays 30.6.

The scan’s advantage is the cache’s size, not the collection’s: at a million characters it pays 30.2 misses a listing with 64 lines held, 20.5 with 256 and 2.0 with 1,024, while the tree’s chain pays 43.1, 35.4 and 23.8. Four times the cache takes the scan back to where it was on the small collection. The chains gain much less from the same lines, because their working sets are spread over tens of thousands of lines and a cache four times larger holds a small part of them.

This is the cliff a cache below the reachable set found for a lazy automaton, and that a cache the listings share found for the scan at about 130 lines on the small collection. At a million characters the scan’s cliff has moved to somewhere between 256 and 1,024 lines, because the commonest words’ rows are what has to stay resident and they now fill hundreds of lines. Below the cliff the scan pays for every flush; above it, almost nothing.

That makes the result a statement about a ratio. What decides whether a chain is worth its apparatus is how the document array’s hot part compares with the cache, and growing the collection eightfold at a fixed cache is the same move, as far as the scan is concerned, as shrinking the cache at a fixed collection.

Every footprint outgrows the cache

Every footprint outgrows the cache together: at a million characters the scan's document array and bitmap fill 13,674 lines and the tree's chain 95,594, against 256 held — the chains' directories grew as the proposal feared, and the tree still wins its listingsLines each method's structures occupy, by size: 125,040 characters: scan 1,711, chain, tree 10,415, chain, separate arrays 9,110, chain, interleaved 9,541; 250,041 characters: scan 3,420, chain, tree 21,852, chain, separate arrays 18,441, chain, interleaved 18,553; 500,042 characters: scan 6,838, chain, tree 45,750, chain, separate arrays 37,718, chain, interleaved 42,665; 1,000,081 characters: scan 13,674, chain, tree 95,594, chain, separate arrays 76,413, chain, interleaved 82,711. The cache holds 256 lines.characters in the collectionlines, log scale125k250k500ka million1001,00010,000100,000256 lines heldchain, treechain, interleavedchain, separate arraysscanlines a structure occupieslog scale
Fig. 5 Lines each method’s structures occupy, log scale, by size. Scan, the document array and its bitmap: 1,711, 3,420, 6,838, 13,674. Tree: 10,415, 21,852, 45,750, 95,594. Separate arrays: 9,110, 18,441, 37,718, 76,413. Interleaved: 9,541, 18,553, 42,665, 82,711. The cache holds 256.

Every footprint outgrows the cache together: at a million characters the scan’s document array and bitmap fill 13,674 lines and the tree’s chain 95,594, against 256 held — the chains’ directories grew as the proposal feared, and the tree still wins its listings. The risk was that the chains’ resident parts would grow faster than the scan’s hot rows. Their whole footprints do grow faster, a factor of nine against eight for the scan’s, and they are six to seven times the scan’s at every size.

What the risk missed is that a held cache does not care about footprints. It cares about what a workload touches repeatedly. The tree’s walk touches a few nodes near its root on every query, and those stay resident however large the tree grows below them, because the root is only seventeen to twenty levels from any leaf. The scan’s repeated touches are the hot rows of the document array, and those grow with the collection’s commonest words.

So the footprints, ten and a hundred thousand lines, say almost nothing about the held prices. The plate is the reason to distrust a structure’s size as a proxy for its cache behaviour, which is the same warning a list and a block of memory gave about layouts.

Where to switch

Below a million characters the best rule is to scan every listing; at a million it walks the tree's chain from 6,775 occurrences up — the workload's ninetieth percentile, well under the 18,725 rows the cache holdsFor each size: the occurrence count at which the best count rule for the tree's chain switches from scanning to walking (none: scanning everything is best), the workload's median, ninetieth percentile and largest occurrence count, and the document array's entries in 256 lines. 125,040 characters: switch none, median 36, 90th 841, largest 1,749, rows held 18,725; 250,041 characters: switch none, median 59, 90th 1,659, largest 3,692, rows held 18,725; 500,042 characters: switch none, median 123, 90th 3,395, largest 7,575, rows held 18,725; 1,000,081 characters: switch 6,775, median 246, 90th 6,775, largest 15,542, rows held 18,725.switch pointmedian · 90th · largestrows held125k250k500ka million101001,00010,000occurrences, log scale256 lines heldoccurrences
Fig. 6 For each size: the occurrence count at which the best rule switches from scanning to walking the tree’s chain (none below a million characters), against the workload’s median, ninetieth percentile and largest occurrence count, and the document array’s entries in 256 lines. 125,040 characters: median 36, 90th 841, largest 1,749. 250,041: 59, 1,659, 3,692. 500,042: 123, 3,395, 7,575. 1,000,081: switch at 6,775; median 246, 90th 6,775, largest 15,542. Rows held: 18,725.

Below a million characters the best rule is to scan every listing; at a million it walks the tree’s chain from 6,775 occurrences up — the workload’s ninetieth percentile, well under the 18,725 rows the cache holds. The switch is not at the smallest listing the chain wins, 675, because most listings between 675 and 6,775 occurrences are still cheaper to scan. The chain wins a scattering of them and loses most; the rule chooses a count above which it wins on balance.

The rule needs nothing a running index does not already have. The suffix-array search that finds a pattern’s rows returns their count, before either method reads anything, so choosing by count is free. The threshold is fitted on this workload and is therefore the best such rule rather than a rule tested out of sample, but its position at the workload’s ninetieth percentile suggests what to fit: send the tenth of listings with the most rows to the chain, and the scan’s cache stops being flushed by them.

That last effect is not in the plate’s price, and it matters. Each method was run through its own cache, so the rule’s price is assembled from the scan’s misses in a cache that the large scans did flush. A running index following the rule would never run those large scans, and its scan cache would be flushed far less, so the rule’s real price should be lower than 12.4. That was not measured.

Churn, not overflow

The proposal pictured the scan failing listing by listing: a word whose rows outnumber the cache cannot be held, and its listing costs its rows. The measurement shows the scan failing as a population. No listing outgrows the cache, but a tenth of them are large enough to sweep most of it, and they come often enough that every other listing’s rows are evicted between its own visits. The price of the scan becomes a property of the workload’s heavy tail rather than of the listing in hand.

That changes what the chain is for. In the earlier essays the chain was the method for large outputs: when a word occurs in many places in few documents, the chain does work proportional to the documents and not the occurrences. At a million characters it is that, and it is also a way to keep the heavy listings out of a cache that the light listings need. A rule that sends the heavy tail to the chain protects the scan, and the benefit falls on listings the rule never touches.

It is a familiar shape in caching generally: a few large sequential reads evict a working set that many small reads depend on, and the cure is to route the large reads around the cache. Database buffer managers do it with scan-resistant replacement. Here the routing is free because the size of the read is known before it happens.

What an index would do with this

A running index does not get to fit its threshold on the workload it is about to see, but the plates say what to estimate. The switch sat at the ninetieth percentile of the occurrence counts, and the reason it sat there is a statement about the cache: the scans worth diverting are the ones large enough to sweep a good part of the cache and frequent enough to do it between a smaller word’s visits. Both quantities are cheap to track. The row count of every listing is known before the listing runs, and a running quantile of those counts over the last few thousand listings is a few dozen numbers. An index could send the listings above its running ninetieth percentile to the chain and revisit the percentile as the indexed text grows.

The cache side of the estimate is the harder one. The scan’s cliff moved from about 130 lines at 145,000 characters to somewhere between 256 and 1,024 at a million, and an index does not know where its own cliff is without measuring misses, which most systems expose only coarsely. The simpler policy is the one the cache plate implies: if the cache can be made four times larger, the chain is not needed at this size at all, since the scan with 1,024 lines held pays two misses a listing against the tree’s twenty-four. Routing large listings to the chain is the remedy for a cache that cannot grow, and a growing collection is precisely the case in which it cannot keep up.

What the replay leaves out

Separate caches. Each method runs through its own cache, so no method’s traffic disturbs another’s. A real index following a mixed rule shares one cache between the scans and the walks, and the rule’s price would have to be measured in that cache.

Fully associative LRU. A real cache of a few hundred lines is set-associative, and a large scan through it evicts by set rather than by age. The flushing measured here would be patchier, and the scan’s price at a million characters probably lower.

One collection, one draw. The documents are 82 long essays and the words are drawn by occurrence. A collection of many short documents, or a workload drawn by distinct word, would change the heavy tail that does the flushing.

Rows found for free. Finding a pattern’s rows in the suffix array is charged to nobody, as before. On a million characters that search touches lines too, and they compete for the same cache.

Still open: one cache, shared by the rule

The rule’s price is assembled from two caches that never met. The scan’s cache in the measurement was flushed by the very scans the rule would have sent to the chain, so the rule as priced pays for a flushing it would have prevented, and the chain’s cache never saw the light listings the rule would have scanned.

The measurement that follows runs the rule itself through one held cache of 256 lines: listings above a threshold walk the tree’s chain, the rest scan, and every line either touches competes for the same space. It sweeps the threshold from the workload’s median to beyond its largest listing, at a million characters and at half that. The prediction is that at a million characters the shared rule costs under ten misses a listing at a threshold near the ninetieth percentile, below the 12.4 assembled here, because the scans it keeps no longer suffer the large scans’ sweeps. It could fail on the chain’s side: its walks touch nodes spread across ninety thousand lines, and in a shared cache those nodes may evict the light listings’ rows as thoroughly as the large scans did. The question is whether a rule can protect a cache by routing traffic around it, or whether any method that reads enough lines flushes whatever it shares the cache with.

Named alongside this one

Essays reaching for the same objects. Nobody chose these; they are what the concept index makes visible.

The objects this essay names

Each one links to every other essay that touches it.

CacheCache lineDocument listingOutput-sensitiveRange minimumWorking set