pub struct Link { /* private fields */ }Expand description
A relationship’s child to parent map.
Implementations§
Source§impl Link
impl Link
Sourcepub fn build(parents_of: &[Rid], parents: u64) -> Result<Self>
pub fn build(parents_of: &[Rid], parents: u64) -> Result<Self>
Builds a link from one parent rid per child, with NO_PARENT for the unmatched.
The form is chosen here and not by the caller: monotone when every child has a parent and
the rids are non-decreasing, packed otherwise. That decision is a pass over the slice the
caller already produced, so it costs a comparison per child on top of a build that was
already linear.
§Errors
If a parent rid is not NO_PARENT and is not below parents, which means the link and
the key map it was built against disagree about how many rows the parent table has. That is
a bug rather than a data condition, and a link built past the end of its parent resolves to
a row that is not there, which is the one failure in this layer that is a wrong answer.
Sourcepub fn forward(&self, child: Rid) -> Option<Rid>
pub fn forward(&self, child: Rid) -> Option<Rid>
The parent of a child row, or None if it has none or the child is past the end.
Sourcepub fn forward_run(&self, first: Rid, out: &mut [Rid]) -> Result<()>
pub fn forward_run(&self, first: Rid, out: &mut [Rid]) -> Result<()>
The parents of a run of consecutive children, with NO_PARENT for the ones that have none.
This is Link::forward over a range, and what it adds is the monotone form. Answering one
child there is a select1, which is a search, and walking a run of them one search at a time
is paying for random access on a read that is sequential. So the run is found once and then
read off the bitmap in order: a one bit is a child of the current parent and a zero bit moves
on to the next parent, which is a load per sixty four bits and a count of zeros per word.
§Errors
If the run goes past the last child.
Sourcepub fn forward_each(&self, children: &[Rid], out: &mut Vec<Rid>)
pub fn forward_each(&self, children: &[Rid], out: &mut Vec<Rid>)
The parent of each child in a list, with NO_PARENT for a child that has none or is past
the end.
This is Link::forward over the rows a filter or a reduction left, and it is for the
monotone form again. A child there is a select1 and a rank0, about three hundred
instructions between them, and on q09 those were a tenth of the query for 319,404 children.
The children a scan hands up are ascending, so the next one is usually a few words further
along the bitmap than the last, and walking those words is a count of ones per word. A
child further away than Link::WALK children, or one before the last, is searched for
again, so the answer is the same in any order and only the cost depends on it.
Sourcepub fn backward(&self, parent: Rid) -> Option<Range<Rid>>
pub fn backward(&self, parent: Rid) -> Option<Range<Rid>>
The children of a parent row, as a half open range of child rids.
None for the packed form, which does not answer this direction, and for a parent past the
end. An empty range is a parent with no children and is not the same answer.
Sourcepub fn backward_from(
&self,
parent: Rid,
cursor: &mut Cursor,
) -> Option<Range<Rid>>
pub fn backward_from( &self, parent: Rid, cursor: &mut Cursor, ) -> Option<Range<Rid>>
Self::backward for a parent at or a little past the one cursor was left at, found by
reading on from there rather than by two selects.
For a caller asking about parents in rising order, which is a child read in its own order
asking about its siblings. A select is a search each time, and on TPC-H q21 two of them per
line of lineitem were a tenth of the query, where the next parent asked about is a word or
two of bits further on. A parent behind the cursor or far past it is two selects as before,
and leaves the cursor there.
Sourcepub fn part_bounds(&self, part: usize) -> Option<Bounds>
pub fn part_bounds(&self, part: usize) -> Option<Bounds>
The minimum and maximum parent rid over one part of the child table, for section 5.5.
None for a part past the end of the table; Some(None) for a part in which no child has a
parent, which is a part a reduction skips.
Sourcepub fn counts(bytes: &[u8]) -> Result<Counts>
pub fn counts(bytes: &[u8]) -> Result<Counts>
The counts at the front of a link’s payload, read without its body.
bytes is at least the first HEADER_BYTES of what Link::write produced, and may be
all of it. This is for a caller that only wants to know whether every child found a parent,
which a planner asks of every relationship before a query, and which is three numbers at the
front of a body that is megabytes long for the links of a large table.
§Errors
If there are fewer bytes than a header, or the header names a form or a layout this build
does not know, which is what Link::read refuses the header for too.
Sourcepub fn read(bytes: &[u8]) -> Result<Self>
pub fn read(bytes: &[u8]) -> Result<Self>
Reads a link from exactly the bytes Link::write produced.
§Errors
If the payload is shorter than its header, names a form or a layout this build does not know, or holds a body that is not the size its header implies. Every one of those is a section to drop rather than a query to fail, by section 3.1.
Sourcepub fn read_from(payload: Vec<u8>, at: usize) -> Result<Self>
pub fn read_from(payload: Vec<u8>, at: usize) -> Result<Self>
Link::read of the bytes of payload from at on, keeping payload for the packed
parents rather than copying them out of it. See Tail for why.
§Errors
As Link::read, or if at is past the end of payload.