The split asked first
A phrase index answers does this pattern occur? in two stages. The first stage is two binary searches: for every position at which the pattern can be cut, the prefix is looked up among the text’s reversed phrase prefixes and the suffix among its suffixes, and each search returns a range. The second stage is a grid. A rectangle over a permutation set it out: every phrase boundary of the text is a point, placed by its rank in the two sorted orders, and a cut of the pattern occurs in the text exactly when the rectangle its two ranges make holds a point. On the index measured here, a repetitive text at five per cent divergence, the grid holds 3,612 points in a wavelet tree of twelve levels, stored level by level with the rank directories the structure paid for before the first query priced and coded as the level where compression stops paying left it. A count that names every point showed that answering exactly about its rectangles costs the full floor of a bit for every bit, so every query below is asked of the whole tree.
A test that is the top of the search tried to make the second stage cheaper by stopping the tree’s descent halfway, and found the descent had little left to save. An existence query stops at the first split that says yes, and for a pattern that occurs the first split asked is nearly always occupied. What it did leave was a number that depends on nothing but order. Asked from the shortest prefix to the longest, a pattern that occurs costs 12.9 nodes of the full grid; asked from the longest to the shortest, 9.4. Both orders are fixed before the query has seen anything.
Its closing section noticed that they need not be. Every split’s rectangle is known before the grid is consulted: the columns are the prefix’s range and the rows the suffix’s, both already computed by the searches. A query could read those two ranges for every split and ask first the one most likely to answer. The proposal was a score: the number of points the rectangle would hold if the grid’s points were scattered at random, its width times its height over the 3,612 points. It predicted that ordering the splits by that score would settle a pattern that occurs in under eight nodes, because it would ask first the split most likely to be occupied among those cheap to descend.
Seven orders from two ranges
The measurement keeps everything the earlier essay used: the same grid, the same 300 patterns of eight and sixteen characters taken from the text, the same 300 made by replacing one character so that the text does not contain them. A pattern of length has cuts, and a cut is a split only if both its prefix and its suffix have a non-empty range; the patterns that occur have 6.9 splits each. Every split is asked of the full grid once, at all twelve levels, and the nodes its descent visits are recorded with its answer. An order then costs a query the nodes of the splits it asks up to and including the first yes.
Seven orders are compared, all but one computed from the two ranges alone. Two are the earlier essay’s: the shortest prefix first, and the longest first. The proposal’s is the most points expected, for a rectangle columns wide and rows tall over points. Two take one side each: the widest first and the tallest first. One prices both questions the proposal mixed: the chance a rectangle is occupied if the points were thrown at random, , divided by the nodes a descent would need to find a node inside a rectangle rows tall, about . The last reads the answers: it asks the occupied splits first, the cheapest of them first. No query could compute it, and that is its use. It is the least any order of these splits can cost, since a query that knows which split to ask asks only that one.
A pattern that does not occur asks every split it has whatever the order, so the order cannot change its cost: 3.12 nodes in every order here, as it was before. Everything below is about the patterns that occur.
The proposal costs more than a fixed order
Ordered by the points each rectangle is expected to hold, a query settles a pattern that occurs in 10.7 nodes, not under eight, and more than asking the longest prefix first, 9.4. The proposal improves on the order the earlier essays started from, by two nodes, and loses to the other fixed order, by more than one. The best order computable from the ranges is the tallest rectangle first, at 9.31 nodes, a tenth of a node under longest-first. The pricing that divides likelihood by depth sits between them at 9.94.
The bottom bar is the reason the prediction could never hold. An order that knows which split is occupied and asks the cheapest such split alone costs 8.24 nodes. No score of any kind can beat that, because no score can do better than asking a single split, the right one. The prediction of under eight was a prediction about what the order could save. Read against the oracle, the most it could save over longest-first was 1.16 nodes, and the proposal moved the other way.
Under eight is reachable only on the shorter patterns. On eight characters the oracle costs 7.71 nodes and on sixteen 8.77, so an order would have had to be perfect on short patterns and better than perfect on long ones.
The likeliest split is not the cheapest
The points-expected order does what it was designed to do — it asks an occupied split first for 94% of patterns — and costs 10.7 nodes, while tallest-first is right first only 85% of the time and costs 9.3. The plate is close to a line that runs the wrong way. The three orders that most often ask an occupied split first are the three dearest, and the two that are wrong first one time in seven are the two cheapest computable orders.
This is the plate that says what the prediction misread. It treated a query’s cost as the number of splits asked, so that asking the likeliest split first would minimise the splits and with them the nodes. The splits asked barely vary: from 1.07 for the widest order to 1.26 for longest-first, a quarter of a split between the extremes. The nodes each split costs vary by half again. A score that is right about likelihood and silent about cost picks the split that will answer, and does not notice that the answer is expensive.
There is a second reason the likeliest split is so often a dear one, and it is the shape of the rectangles. A split whose prefix is one character has a prefix range of hundreds of columns, so its rectangle is wide and very likely occupied. The same split’s suffix is the rest of the pattern, which narrows its range to a few rows. The rectangles most likely to hold a point are wide and short, and wide-and-short is what the next plate prices.
A yes is priced by its rows
A yes is cheap when its rectangle is tall: an occupied split spanning 256 or more rows is settled in 6.2 nodes and one spanning a single row in 13.0, while its width barely matters and runs the other way, 10.1 nodes at one column and 12.2 at 256 or more. The two halves of the plate have the same splits in them, binned two ways, and only one of the two ranges sets the price.
The reason is in how the wavelet tree says yes. Its levels split the range of heights in half, then in half again, so a node at depth covers consecutive rows. The descent answers yes at the first node whose rows lie wholly inside the rectangle and that holds a point of the column range. A rectangle 256 rows tall contains whole nodes from the fourth level down, and on an occupied split one of them almost always holds a point, so the descent stops near the top. A rectangle one row tall contains no node above the twelfth level, so the descent must go to the bottom of the tree to say yes, and at every level it follows the branch toward that row. Height decides the depth of the first node that can possibly answer, and that depth is most of the cost.
Width works against a yes rather than for it. A wide column range keeps more nodes non-empty on the way down, so the descent abandons fewer of the nodes that straddle the rectangle’s edges and visits more of them. A narrow range empties those side branches quickly. That is the effect a test that is the top of the search named when it explained why longest-first is cheap: a long prefix has a narrow column range. The plate says the narrowness is the smaller of the two reasons. A long prefix leaves a short suffix, and a short suffix has a wide suffix range, which is a tall rectangle. Longest-first was cheap mostly because it was tallest-first under another name.
That is why the proposal lost. The number of points expected, width times height, rewards width as much as height. A wide, short rectangle and a narrow, tall one with the same area score the same, and the wide one is likelier to be occupied because points in a narrow range of columns are few. The score therefore favours the very rectangles that are dearest to settle.
The yes it stops at is the bill
Almost all of a query’s cost is the yes it stops at: asked longest prefix first, 8.4 of its 9.4 nodes are the occupied split, and the points-expected order saves half a node of empty splits only to pay 1.8 more for a dearer yes. The pale ends of the bars are the empty splits each order asks before it finds a point, and they never reach a node. The dark bars are the yes, and they range over four nodes.
So the real choice an order makes is not whether to ask an empty split first; it is which of a pattern’s occupied splits to stop at. A pattern of sixteen characters that occurs has many occupied splits, since every cut of a string the text contains is a cut of a string the text contains. All of them would say yes. They differ only in the price of saying it, and an order that is right first 94% of the time is choosing among yeses without asking what each costs.
The oracle’s bar shows how much of the price is fixed. Its 8.24 nodes are the cheapest yes each pattern has. Tallest-first stops at a yes that costs 8.40 on average, within a sixth of a node of the cheapest, and the rest of its gap is the 0.91 nodes of empty splits it asks first. The chance-over-price order was the attempt to price both, and it lands between: its estimate of depth from the rows is right, but its estimate of the chance of a point from random scattering pushes it back toward the wide splits, because on a repetitive text the points are not scattered at random. The occupied splits are occupied because the text contains the pattern, not because the rectangle is large, and the random model gives a narrow, tall rectangle a chance of a point it has not earned and does not need.
Longer patterns, the same gap
Longer patterns cost more in every order, and the gap an order can close is no wider for them: on sixteen characters tallest-first costs 9.9 nodes against the oracle’s 8.8, on eight 8.7 against 7.7. On eight characters, longest-first and tallest-first are within three hundredths of a node of each other, and on sixteen tallest-first is two tenths cheaper. The difference between the two fixed orders lives almost entirely in the long patterns.
The reason is visible in the patterns’ splits. A pattern of eight characters has at most seven cuts, and its last cut leaves a one-character suffix, whose range covers every phrase starting with that character, so the longest prefix is the tallest rectangle almost every time. A pattern of sixteen characters has fifteen cuts, and among its longer suffixes the ranges no longer shrink in step with the suffix’s length: a suffix of three characters and one of five can plausibly have nearly the same range on a repetitive text, because the text repeats whole passages; the ranges were not tabulated by length. There, the tallest rectangle is sometimes not the last split, and an order that reads the rows finds it.
The oracle’s cost grows with length too, by a node. A longer pattern’s cheapest yes is still dearer, because even the tallest of its rectangles is shorter than an eight-character pattern’s tallest; its suffix ranges are narrower at every length. No order pays for that. It is the price of asking a longer question.
Most patterns leave nothing to choose
For 78% of patterns that occur, tallest-first already pays exactly the oracle’s nodes, and most of its gap of 1.1 nodes a query comes from the few where it asks an empty split first. Longest-first matches the oracle on the same share, and the points-expected order on 46%. The plate spreads each order’s average over the patterns, and the averages hide two different kinds of query.
Most patterns are settled at the best price by any sensible order, because their tallest rectangle is both occupied and the cheapest. Those patterns leave an order nothing to decide. A fifth of the patterns are where all the cost difference lies: the tallest rectangle is empty, because a long prefix of the pattern does not end at a phrase boundary in the text where the pattern occurs, and the query pays for an empty descent before moving on. On those patterns, tallest-first pays from one node to more than ten over the oracle, and nothing computed from the ranges tells it which ones they are.
This is the shape the join order is a guess found for a different problem, and the one the candidates a filter cannot avoid found in the phrase index’s own first stage. A query optimiser choosing the order of three joins does well on most queries with any reasonable estimate, and the bill is set by a few queries on which the estimate is badly wrong. There the remedy was a better estimate of the intermediate sizes. Here the estimate that would help is whether the tallest rectangle is occupied, and that is the question the grid exists to answer. An order can only use what the two searches return, and they return ranges, not occupancy.
What the ranges can tell a query
The proposal’s mistake was to optimise the wrong quantity, and the measurement is cleanest read that way. A query’s cost is the sum, over the splits asked, of each split’s descent. The proposal minimised the number of terms; the cost is set by the size of the last one. The two coincide only when every descent costs the same, and on a wavelet tree they never do, because the depth at which a yes can occur is fixed by the rectangle’s height.
A score built on that would put height first, and it does: tallest-first is the best computable order measured, and it is within a sixth of a node of the oracle on the yes it stops at. What separates it from the oracle is not a better reading of the ranges, but the empty splits it cannot foresee. The ranges say how much of the grid a rectangle covers; they do not say whether the pattern’s occurrences end at phrase boundaries on that cut. That depends on where the parse put its boundaries, and the parse is not in the ranges.
The two sorted orders carry a little more than the widths used here. The range of a suffix nested inside a longer suffix’s range says how many of the text’s occurrences of the shorter suffix extend to the longer one, and that is a measure of whether the pattern lies within one phrase or across several. None of the scores here used it, and it is not obvious it would help, because a phrase boundary falls inside an occurrence at a position the parse chose, not one the suffix ranges predict.
The finding has a plainer reading for anyone writing such a query. Ask the longest prefix first, or the tallest rectangle, which is nearly the same thing; never ask the widest first; and expect at most a node of improvement from anything cleverer, since 8.24 nodes is what a query that guessed perfectly would pay. On this grid, the order of the splits was worth at most an eighth of the query, and the fixed order the earlier essays happened to try second already had most of it.
What the comparison assumes
One grid, one index. Every number is from the grid of a phrase index over one repetitive text at five per cent divergence: 3,612 points over twelve levels. A grid with more points has more levels, which widens the spread between a tall rectangle’s yes and a short one’s and should make the rows matter more. A text with less repetition has narrower ranges at every length and fewer occupied splits per pattern, which leaves an order less to choose among.
Nodes as the cost. A node is a pair of rank queries on one level’s bit vector, and every node is counted the same. On a machine whose levels lie in different places in memory, the top levels of a wavelet tree are read by every query and stay in cache, and a node near the bottom costs more than one near the top. That would favour tall rectangles further, since their descent stops high.
Patterns drawn from the text. The patterns that occur are substrings at random positions. Real queries are often for frequent strings, which have wide ranges in both orders; for those every rectangle is tall, and the orders would differ even less.
Still open: a grid descended from the other side
The plates locate the remaining cost in the rectangles that are wide and short. They are the likeliest to hold a point and the dearest to settle, because a wavelet tree built over the rows can only say yes at the depth where its nodes fit inside the rectangle’s rows, and a short rectangle forces the descent to the bottom. A second wavelet tree over the inverse permutation, with the columns as its values, would turn every such rectangle into a tall one: a split could be asked of whichever tree its longer side favours, and a yes in a wide, short rectangle would come near the top of the second tree.
The measurement that follows builds that second tree over the same 3,612 points, asks every split of the tree in which its rectangle is taller relative to the tree’s depth, and orders the splits by the cheaper of the two estimated depths. It counts nodes against tallest-first on the single tree and against the oracle of each. The prediction is that a pattern that occurs costs about seven nodes, under the single tree’s oracle of 8.24, since the cheapest yes of most patterns sits in a wide rectangle the second tree reaches in five or six nodes. It could fail on the side the plates already showed: width works against a descent over rows because it keeps side branches alive, and a tall rectangle in the second tree is a wide one in the first, which may keep as many branches alive there. The question is whether doubling the grid’s bits, 47,668 more, buys a query a cheaper yes, or whether every split of these patterns is expensive on one tree or the other in the same way.
Named alongside this one
Essays reaching for the same objects. Nobody chose these; they are what the concept index makes visible.
- A block, a class and an offset grid · permutation · wavelet tree
- The operations a candidate count leaves out grid · permutation · wavelet tree
- The runs a permutation does not leave grid · permutation · wavelet tree
- A band as wide as the answer cost model · evaluation order
- Permuting is the harder problem here cost model · permutation
- The same table, filled two ways cost model · evaluation order
The objects this essay names
Each one links to every other essay that touches it.
Cost modelEarly exitEvaluation orderGridPermutationWavelet tree