Trait TextSource 

pub trait TextSource:
    Debug
    + Send
    + Sync {
    // Required methods
    fn len(&self) -> usize;
    fn bytes_at(&self, index: usize) -> Result<Option<&[u8]>>;
    fn footprint(&self) -> usize;

    // Provided methods
    fn is_empty(&self) -> bool { ... }
    fn bytes_len_at(&self, index: usize) -> Result<Option<usize>> { ... }
    fn bytes_lens_at(&self, indices: &[u32], into: &mut Vec<i64>) -> Result<()> { ... }
    fn chars_lens_at(&self, indices: &[u32], into: &mut Vec<i64>) -> Result<()> { ... }
    fn sweep(
        &self,
        first: usize,
        limit: usize,
        body: &mut dyn FnMut(usize, &[u8]) -> Result<()>,
    ) -> Result<usize> { ... }
    fn visit_at(
        &self,
        indices: &[u32],
        body: &mut dyn FnMut(usize, &[u8]) -> Result<()>,
    ) -> Result<()> { ... }
    fn might_contain(&self, first: usize, literal: &[u8]) -> Result<bool> { ... }
    fn visit(
        &self,
        indices: &[usize],
        body: &mut dyn FnMut(usize, &[u8]) -> Result<()>,
    ) -> Result<()> { ... }
    fn ranks(&self) -> Option<usize> { ... }
    fn compare_rank(&self, rank: usize, wanted: &[u8]) -> Result<Ordering> { ... }
    fn below(&self, ranks: usize, wanted: &[u8]) -> Result<(usize, bool)> { ... }
    fn code_at_rank(&self, rank: usize) -> Result<u32> { ... }
    fn code_ranks(&self) -> Option<&[u32]> { ... }
    fn equal(&self, other: &dyn TextSource) -> bool { ... }
}

Random access to immutable text kept by a storage reader.

Required Methods

fn len(&self) -> usize

Number of values available.

fn bytes_at(&self, index: usize) -> Result<Option<&[u8]>>

Bytes at one position, or no value when the position is outside the source.

fn footprint(&self) -> usize

Resident bytes retained by this source.

Provided Methods

fn is_empty(&self) -> bool

Whether this source has no values.

fn bytes_len_at(&self, index: usize) -> Result<Option<usize>>

Byte length at one position without requiring the payload when the source has an index.

fn bytes_lens_at(&self, indices: &[u32], into: &mut Vec<i64>) -> Result<()>

The byte length at each of indices, appended to into in the same order, and zero for a position the source does not have.

The same answers as bytes_len_at a position at a time, which is what the default does. A source overrides it when it can answer a run of positions for less than the run of calls: a length asked once per row goes through a dispatch here, a dispatch in the vector and a Result at each, and on a column whose lengths are one load each that was most of what STRLEN cost. Appended rather than written into place, so that the caller has no zeroed buffer to make first only for every slot of it to be written over.

fn chars_lens_at(&self, indices: &[u32], into: &mut Vec<i64>) -> Result<()>

The length in characters at each of indices, appended to into in the same order, and zero for a position the source does not have.

What length asks for, where bytes_lens_at is what strlen asks for. Counting characters means looking at the bytes, and the default does that through bytes_at, which is right for a source that keeps its values anyway. A source that decodes a block to answer bytes_at keeps that block for as long as it lives, so a scan of length over a whole column ends up holding the whole column decoded. Such a source overrides this and keeps the counts instead of the bytes.

fn sweep( &self, first: usize, limit: usize, body: &mut dyn FnMut(usize, &[u8]) -> Result<()>, ) -> Result<usize>

Hands body the values from first up to at most limit, and answers where it stopped.

The point of it is what it does not do, which is keep what it read. bytes_at hands back a borrow, so a source that decodes a block to answer it has to hold that block for as long as the source lives, and a reader that walks the whole source therefore ends up holding the whole thing decoded. On the ClickBench URL dictionary that is 4.2 GB resident to answer one LIKE, and none of it is read twice.

A caller that means to walk a stretch of values once calls this instead and gets the bytes on loan for the length of the call. The source decides how much it hands over at a time, which for a blocked payload is the rest of the block it had to decode anyway, and answers with one past the last value it visited so the caller can come back for the next stretch. The answer is always above first where first is a value this source has, so a loop on it finishes.

The default hands over one value through bytes_at and is correct for every source. It is also pointless for a source that keeps everything anyway, which is every source built in memory, and that is the right default for exactly that reason.

fn visit_at( &self, indices: &[u32], body: &mut dyn FnMut(usize, &[u8]) -> Result<()>, ) -> Result<()>

Hands body the value at each of indices, in whatever order suits the source, with the position in indices it belongs to.

The whole vector twin of bytes_at, for a kernel that reads every row of a vector once and writes something per row, which is what lower, upper and substring do. Read a row at a time, a source that decodes a block to answer bytes_at has to keep every block a row lands in for as long as the source lives, because the borrow it hands back says so. Handed a whole vector of positions at once it can put them in block order, decode each block once for the call and decide for itself whether that block is worth keeping.

A position the source does not have gets the empty value, which is what a row at a time read turns its missing value into. The default reads through bytes_at in the order given, which is right for every source that keeps its values anyway.

fn might_contain(&self, first: usize, literal: &[u8]) -> Result<bool>

Whether the payload block holding first might contain literal in any value.

A false answer is a proof that every value in the block misses. A source without a stored substring signature answers true, which keeps the ordinary exact comparison authoritative.

fn visit( &self, indices: &[usize], body: &mut dyn FnMut(usize, &[u8]) -> Result<()>, ) -> Result<()>

Hands over the values at indices, which rise, without keeping what reading them decoded.

The scattered twin of sweep. A caller that wants a few hundred values spread over the whole source once, which is what turning a frequency synopsis’s codes into values is, would otherwise leave every block it touched decoded and held for the rest of the source’s life. On ClickBench SearchPhrase that is a hundred and twenty five blocks, the larger part of what a query answered out of the synopsis was holding.

body is told the position in indices and the bytes. The default reads through bytes_at, which is right for every source that keeps everything anyway.

fn ranks(&self) -> Option<usize>

How many ranks this source’s sorted value order has, when it has one.

A rank is a position in the values sorted by their bytes, so rank zero is the smallest value and rank ranks() - 1 is the largest. A storage format that keeps a dictionary for a whole column can afford to sort the distinct values once when it writes the file, and what that buys is a binary search where a reader that only knows the values are distinct has to ask every one of them whether it matches.

None means the source does not know its order, which is the honest answer for anything built in memory and for a file written before its format stored one. Nothing is allowed to depend on this for correctness, only for speed.

A source that answers with Some promises the ranks cover every value it has, and that compare_rank is consistent with an ordering in which the values are strictly increasing. Strictly, which is to say the values are distinct, because what reads this searches it, and a search of a run of equal values finds one of them rather than all of them. A source that holds the same value twice must answer None here even though it could sort itself perfectly well.

fn compare_rank(&self, rank: usize, wanted: &[u8]) -> Result<Ordering>

How the value at rank compares against wanted.

This is a method rather than a slice of positions the caller indexes because the answer is the only thing a search wants, and a source that knows that can answer most probes without reading a value at all. A file that stores the first few bytes of each value in rank order settles every probe from those bytes except the ones where two values start the same way, and the payload stays untouched. A caller handed positions instead would have to read a value per probe, which for a dictionary of half a million entries spread over thirty megabytes is a fresh block of the file every time.

Only called for a rank below ranks, so the default is the error a source that has no order should never be asked to produce.

fn below(&self, ranks: usize, wanted: &[u8]) -> Result<(usize, bool)>

How many values sort before wanted, and whether one of them is wanted.

The whole search rather than a probe of it, so that a source which can answer the same question twice without repeating the work is allowed to. The default runs the search through compare_rank and remembers nothing, which is right for a source whose probes are cheap.

The reason it is on the trait at all is the top N. ORDER BY <varchar> LIMIT 10 asks once a chunk whether anything left can beat the worst candidate, and the worst candidate stops changing long before the chunks run out, so nearly every one of those searches is the one before it asked again. A probe of a file backed dictionary is not cheap: it settles on the stored head where it can and reads a value where it cannot, and reading a value means decoding the payload block it sits in. On ClickBench 25 that search was 29 percent of the query’s instructions and the block decoding under it another 40.

Only called when ranks is Some, and ranks is what it answered.

fn code_at_rank(&self, rank: usize) -> Result<u32>

The position of the value at rank, which is what a search returns once it has found one.

Called about once per search rather than once per probe, so unlike compare_rank it is free to be the expensive one.

fn code_ranks(&self) -> Option<&[u32]>

The rank of every value, in position order, when the source can hand the whole map over.

This is code_at_rank turned round, and it is a separate method because the two are wanted by opposite kinds of reader. A search wants one code out of a rank and probes a handful of times, so it reads the order a block at a time and leaves the rest alone. A min or a max over a grouped column wants a rank out of a code once per row, and a walk of the order per row costs far more than reading the order once and turning it round. What that buys is a comparison of two integers where the alternative is a fetch of two strings out of a payload the size of the column.

The slice is indexed by position and is as long as len, so a caller holding a dictionary code indexes it directly.

None from a source with no order, and from one with an order it would rather not invert. Nothing depends on this for correctness, only for speed.

fn equal(&self, other: &dyn TextSource) -> bool

Whether another source presents the same values.

Trait Implementations

impl PartialEq for dyn TextSource

fn eq(&self, other: &Self) -> bool

Equality operator ==.

fn ne(&self, other: &Rhs) -> bool

Inequality operator !=.

Dyn Compatibility

This trait is dyn compatible.

In older versions of Rust, dyn compatibility was called "object safety".

Implementors