The index that replaces the text

The split asked first

An existence query on a phrase index asks its grid, split by split, whether a rectangle holds a point, and stops at the first that does. Both ranges of every split are known before the grid is asked, so the query can choose its own order, and asking first the rectangle expected to hold the most points was predicted to settle a pattern that occurs in under eight nodes. It costs 10.7, worse than simply asking the longest prefix first, 9.4, although it asks an occupied split first 94% of the time against 85%. What a query pays is the yes it stops at, and a yes is cheap when its rectangle is tall: 6.2 nodes at 256 rows or more, 13.0 at one row, while width barely matters. Ordered tallest first, the query costs 9.3, and even an order that knows the answers cannot get under 8.2.

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 mm has m−1m - 1 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, wh/zwh/z for a rectangle ww columns wide and hh rows tall over zz 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, 1−e−wh/z1 - e^{-wh/z}, divided by the nodes a descent would need to find a node inside a rectangle hh rows tall, about 2+2log⁡2(z/h)2 + 2\log_2(z/h). 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 split's rectangle is expected to hold, an existence query settles a pattern that occurs in 10.7 nodes — not under eight, and worse than simply asking the longest prefix first, 9.4; asking the tallest rectangle first costs 9.3, and no order at all, even one that knows the answers, gets under 8.2Mean nodes of the full wavelet grid visited by an exact existence query on 300 patterns that occur, stopping at the first occupied split, with the splits asked in each order: shortest prefix first 12.87 nodes over 1.10 splits; widest first 12.68 nodes over 1.07 splits; most points expected 10.68 nodes over 1.08 splits; chance over price 9.94 nodes over 1.12 splits; longest prefix first 9.40 nodes over 1.26 splits; tallest first 9.31 nodes over 1.22 splits; oracle 8.24 nodes over 1.00 splits. The proposal predicted under eight for the points expected; a pattern that does not occur costs 3.12 nodes in every order.eight, predictedshortest prefix first12.87 nodeswidest first12.68 nodesmost points expected10.68 nodeschance over price9.94 nodeslongest prefix first9.40 nodestallest first9.31 nodesoracle8.24 nodes300 patterns that occur; full grid, twelve levelsnodes visited a query
Fig. 1 Mean nodes of the full grid a query visits for 300 patterns that occur, by the order the splits are asked. Shortest prefix first 12.87; widest first 12.68; most points expected 10.68; chance over price 9.94; longest prefix first 9.40; tallest first 9.31; the oracle, which asks the cheapest occupied split and nothing else, 8.24. The dashed line is the predicted eight.

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

Asking the likeliest split first does not make a query cheap: the points-expected order 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.3For each order, over 300 patterns that occur: the share of queries whose first split asked holds a point, against the mean nodes visited. shortest prefix first: 94% first split occupied, 12.87 nodes; widest first: 95% first split occupied, 12.68 nodes; most points expected: 94% first split occupied, 10.68 nodes; chance over price: 90% first split occupied, 9.94 nodes; longest prefix first: 85% first split occupied, 9.40 nodes; tallest first: 85% first split occupied, 9.31 nodes; oracle: 100% first split occupied, 8.24 nodes. The shortest prefix first and the widest first are right first most often and cost the most.78910111213140.8000.8500.9000.9501share of queries whose first split asked is occupiednodes visited a queryshortest prefix firstwidest firstmost points expectedchance over pricelongest prefix firsttallest firstoracle300 patterns that occurthe likeliest split is not the cheapest
Fig. 2 For each order, the share of the 300 queries whose first split asked holds a point, against the mean nodes the query visits. Shortest prefix first: 94% and 12.87 nodes. Widest first: 95% and 12.68. Most points expected: 94% and 10.68. Chance over price: 90% and 9.94. Longest prefix first: 85% and 9.40. Tallest first: 85% and 9.31. The oracle: 100% and 8.24.

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 for one column and 12.2 for 256 or moreEvery occupied split of the 300 patterns that occur (1787 of them), asked of the full grid: mean nodes visited before the descent finds a node whose whole range of rows lies inside the rectangle, binned by the rectangle's rows (left) and by its columns (right). Rows: 1: 13.00 nodes over 128 splits; 2–3: 12.45 nodes over 116 splits; 4–15: 11.67 nodes over 812 splits; 16–63: 10.55 nodes over 502 splits; 64–255: 7.78 nodes over 181 splits; 256+: 6.17 nodes over 48 splits. Columns: 1: 10.10 over 104; 2–3: 11.07 over 29; 4–15: 10.36 over 718; 16–63: 11.22 over 623; 64–255: 12.03 over 185; 256+: 12.16 over 128. An empty split costs 5.20 nodes on average.by the rectangle's rowsby its columns113.010.12–312.411.14–1511.710.416–6310.511.264–2557.812.0256+6.212.21787 occupied splits; nodes to the first yesrows and columns, binned
Fig. 3 Every occupied split of the 300 patterns that occur, 1,787 of them, asked of the full grid: mean nodes before the descent finds a node lying wholly inside the rectangle, binned by the rectangle’s height in rows (left) and its width in columns (right). By rows: one row 13.0 nodes; 2–3 rows 12.4; 4–15 rows 11.7; 16–63 rows 10.5; 64–255 rows 7.8; 256 rows or more 6.2. By columns: one column 10.1; 2–3 columns 11.1; 4–15 columns 10.4; 16–63 columns 11.2; 64–255 columns 12.0; 256 or more 12.2. An empty split costs 5.2.

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 kk covers z/2kz/2^k 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 yesMean nodes a query that occurs, split into the nodes of the occupied split it stops at and the nodes of the empty splits asked before it, by order: shortest prefix first: yes 12.11, empty before it 0.76; widest first: yes 12.10, empty before it 0.58; most points expected: yes 10.20, empty before it 0.48; chance over price: yes 9.30, empty before it 0.65; longest prefix first: yes 8.42, empty before it 0.98; tallest first: yes 8.40, empty before it 0.91; oracle: yes 8.24, empty before it 0.00.the yes it stops atempty splits before itshortest prefix first12.1 + 0.8widest first12.1 + 0.6most points expected10.2 + 0.5chance over price9.3 + 0.6longest prefix first8.4 + 1.0tallest first8.4 + 0.9oracle8.2 + 0.0300 patterns that occurnodes a query
Fig. 4 Mean nodes a query, split into the nodes of the occupied split it stops at and those of the empty splits it asked first. Shortest prefix first: 12.1 + 0.8. Widest first: 12.1 + 0.6. Most points expected: 10.2 + 0.5. Chance over price: 9.3 + 0.6. Longest prefix first: 8.4 + 1.0. Tallest first: 8.4 + 0.9. The oracle: 8.2 + 0.

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 the 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.7Mean nodes a query, 150 patterns of eight characters and 150 of sixteen, all of which occur: shortest prefix first: 12.43 on eight, 13.31 on sixteen; most points expected: 10.13 on eight, 11.23 on sixteen; longest prefix first: 8.69 on eight, 10.11 on sixteen; tallest first: 8.72 on eight, 9.89 on sixteen; oracle: 7.71 on eight, 8.77 on sixteen.eight characterssixteen charactersshortest prefix first12.4313.31most points expected10.1311.23longest prefix first8.6910.11tallest first8.729.89oracle7.718.77150 patterns of each length, all occurnodes a query
Fig. 5 Mean nodes a query on 150 patterns of eight characters and 150 of sixteen, all of which occur. Shortest prefix first: 12.43 and 13.31. Most points expected: 10.13 and 11.23. Longest prefix first: 8.69 and 10.11. Tallest first: 8.72 and 9.89. Oracle: 7.71 and 8.77.

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

Most patterns leave an order nothing to choose: tallest-first already costs exactly the oracle's nodes on 78% of patterns that occur, and most of its gap of 1.1 nodes a query comes from the few where it asks an empty split firstFor each of 300 patterns that occur, the nodes an order costs above the oracle's (occupied splits first, cheapest first), binned: tallest first: 0 above 78%, 1–2 above 9%, 3–5 above 6%, 6–10 above 5%, 11+ above 2%; longest prefix first: 0 above 78%, 1–2 above 10%, 3–5 above 5%, 6–10 above 4%, 11+ above 3%; most points expected: 0 above 46%, 1–2 above 16%, 3–5 above 20%, 6–10 above 17%, 11+ above 1%. 12 patterns have only one split, where every order is the oracle.01–23–56–1011+nodes above the oracle, share of patternstallest firstlongest prefix firstmost points expected300 patterns that occurper pattern, against the oracle
Fig. 6 For each of the 300 patterns that occur, the nodes an order costs above the oracle’s, binned. Tallest first: none above for 78% of patterns, 1–2 for 9%, 3–5 for 6%, 6–10 for 5%, 11 or more for 2%. Longest prefix first: 78%, 10%, 5%, 4% and 3%. Most points expected: 46%, 16%, 20%, 17% and 1%. Twelve patterns have a single split.

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.

The objects this essay names

Each one links to every other essay that touches it.

Cost modelEarly exitEvaluation orderGridPermutationWavelet tree