web search done right
// Stract is an open source web search engine.
// Copyright (C) 2024 Stract ApS
//
// This program is free software: you can redistribute it and/or modify
// it under the terms of the GNU Affero General Public License as
// published by the Free Software Foundation, either version 3 of the
// License, or (at your option) any later version.
//
// This program is distributed in the hope that it will be useful,
// but WITHOUT ANY WARRANTY; without even the implied warranty of
// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
// GNU Affero General Public License for more details.
//
// You should have received a copy of the GNU Affero General Public License
// along with this program. If not, see <https://www.gnu.org/licenses/>.
use tantivy::query::{BooleanQuery, Occur, ShortCircuitQuery};
use super::{
collector::{top_docs, HostDeduplicator, TopDocsCollector},
document_scorer::DefaultDocumentScorer,
raw::LinksQuery,
AndFilter, Filter, FilterEnum, Query,
};
use crate::{
ampc::dht::ShardId,
webgraph::{
doc_address::DocAddress,
edge::Edge,
schema::{Field, FromHostId, FromId, RelFlags, SortScore, ToHostId, ToId},
searcher::Searcher,
EdgeLimit, Node, NodeID, SmallEdge, SmallEdgeWithLabel,
},
Result,
};
pub fn fetch_small_edges<F: Field>(
searcher: &Searcher,
mut doc_ids: Vec<DocAddress>,
node_id_field: F,
) -> Result<Vec<(NodeID, crate::webpage::RelFlags, u64)>> {
doc_ids.sort_unstable_by_key(|doc| doc.segment_ord);
let mut prev_segment_id = None;
let mut field_column = None;
let mut score_column = None;
let mut rel_flags_column = None;
let mut edges = Vec::with_capacity(doc_ids.len());
for doc in doc_ids {
if Some(doc.segment_ord) != prev_segment_id {
prev_segment_id = Some(doc.segment_ord);
let segment_column_fields = searcher.warmed_column_fields().segment(
&searcher
.tantivy_searcher()
.segment_reader(doc.segment_ord)
.segment_id(),
);
field_column = Some(segment_column_fields.u128(node_id_field).unwrap());
rel_flags_column = Some(segment_column_fields.u64(RelFlags).unwrap());
score_column = Some(segment_column_fields.u64(SortScore).unwrap());
}
let Some(id) = field_column.as_ref().unwrap().first(doc.doc_id) else {
continue;
};
let Some(rel_flags) = rel_flags_column.as_ref().unwrap().first(doc.doc_id) else {
continue;
};
let Some(sort_score) = score_column.as_ref().unwrap().first(doc.doc_id) else {
continue;
};
edges.push((
NodeID::from(id),
crate::webpage::RelFlags::from(rel_flags),
sort_score,
));
}
Ok(edges)
}
pub fn fetch_edges(searcher: &Searcher, mut doc_ids: Vec<DocAddress>) -> Result<Vec<Edge>> {
doc_ids.sort_unstable_by_key(|doc| doc.segment_ord);
let mut edges = Vec::with_capacity(doc_ids.len());
for doc in doc_ids {
edges.push(searcher.tantivy_searcher().doc(doc.into())?);
}
Ok(edges)
}
#[derive(Debug, Clone, bincode::Encode, bincode::Decode)]
pub struct BacklinksQuery {
node: NodeID,
limit: EdgeLimit,
filters: Vec<FilterEnum>,
}
impl BacklinksQuery {
pub fn new(node: NodeID) -> Self {
Self {
node,
limit: EdgeLimit::Unlimited,
filters: Vec::new(),
}
}
pub fn with_limit(self, limit: EdgeLimit) -> Self {
Self {
node: self.node,
limit,
filters: self.filters,
}
}
pub fn filter<F: Filter>(mut self, filter: F) -> Self {
self.filters.push(filter.into());
self
}
fn filter_as_and(&self) -> Option<AndFilter> {
if self.filters.is_empty() {
None
} else {
let mut filter = AndFilter::new();
for f in self.filters.clone() {
filter = filter.and(f);
}
Some(filter)
}
}
}
impl Query for BacklinksQuery {
type Collector = TopDocsCollector;
type TantivyQuery = Box<dyn tantivy::query::Query>;
type IntermediateOutput = Vec<(u64, SmallEdge)>;
type Output = Vec<SmallEdge>;
fn tantivy_query(&self, searcher: &Searcher) -> Self::TantivyQuery {
let mut raw = Box::new(
LinksQuery::new(self.node, ToId, searcher.warmed_column_fields().clone())
.with_deduplication_field(FromId),
) as Box<dyn tantivy::query::Query>;
if let Some(filter) = self.filter_as_and().and_then(|f| f.inverted_index_filter()) {
let filter = filter.query(searcher);
let mut queries = vec![(Occur::Must, raw)];
queries.extend(filter);
raw = Box::new(BooleanQuery::new(queries));
}
match self.limit {
EdgeLimit::Unlimited => raw,
EdgeLimit::Limit(limit) => Box::new(ShortCircuitQuery::new(
raw,
(limit + top_docs::DEDUPLICATION_BUFFER) as u64,
)),
EdgeLimit::LimitAndOffset { limit, offset } => Box::new(ShortCircuitQuery::new(
raw,
(limit + offset + top_docs::DEDUPLICATION_BUFFER) as u64,
)),
}
}
fn collector(&self, searcher: &Searcher) -> Self::Collector {
let mut collector = TopDocsCollector::from(self.limit)
.with_shard_id(searcher.shard())
.disable_offset()
.with_column_fields(searcher.warmed_column_fields().clone());
if let Some(filter) = self.filter_as_and().and_then(|f| f.column_field_filter()) {
collector = collector.with_filter(filter);
}
collector
}
fn coordinator_collector(&self) -> Self::Collector {
TopDocsCollector::from(self.limit).enable_offset()
}
fn retrieve(
&self,
searcher: &Searcher,
fruit: <Self::Collector as super::collector::Collector>::Fruit,
) -> Result<Self::IntermediateOutput> {
let docs: Vec<_> = fruit.into_iter().map(|(_, doc)| doc).collect();
let nodes = fetch_small_edges(searcher, docs, FromId)?;
Ok(nodes
.into_iter()
.map(|(node, rel_flags, sort_score)| {
(
sort_score,
SmallEdge {
from: node,
to: self.node,
rel_flags,
},
)
})
.collect())
}
fn filter_fruit_shards(
&self,
shard_id: ShardId,
fruit: <Self::Collector as super::Collector>::Fruit,
) -> <Self::Collector as super::Collector>::Fruit {
fruit
.into_iter()
.filter(|(_, doc)| doc.shard_id == shard_id)
.collect()
}
fn merge_results(results: Vec<Self::IntermediateOutput>) -> Self::Output {
let mut edges: Vec<_> = results.into_iter().flatten().collect();
edges.sort_by(|(a, _), (b, _)| a.cmp(b));
edges.into_iter().map(|(_, e)| e).collect()
}
}
#[derive(Debug, Clone, bincode::Encode, bincode::Decode)]
pub struct HostBacklinksQuery {
node: NodeID,
limit: EdgeLimit,
filters: Vec<FilterEnum>,
}
impl HostBacklinksQuery {
pub fn new(node: NodeID) -> Self {
Self {
node,
limit: EdgeLimit::Unlimited,
filters: Vec::new(),
}
}
pub fn with_limit(mut self, limit: EdgeLimit) -> Self {
self.limit = limit;
self
}
pub fn filter<F: Filter>(mut self, filter: F) -> Self {
self.filters.push(filter.into());
self
}
fn filter_as_and(&self) -> Option<AndFilter> {
if self.filters.is_empty() {
None
} else {
let mut filter = AndFilter::new();
for f in self.filters.clone() {
filter = filter.and(f);
}
Some(filter)
}
}
}
impl Query for HostBacklinksQuery {
type Collector = TopDocsCollector<DefaultDocumentScorer, HostDeduplicator>;
type TantivyQuery = Box<dyn tantivy::query::Query>;
type IntermediateOutput = Vec<(u64, SmallEdge)>;
type Output = Vec<SmallEdge>;
fn tantivy_query(&self, searcher: &Searcher) -> Self::TantivyQuery {
let mut raw = Box::new(
LinksQuery::new(self.node, ToHostId, searcher.warmed_column_fields().clone())
.with_deduplication_field(FromHostId),
) as Box<dyn tantivy::query::Query>;
if let Some(filter) = self.filter_as_and().and_then(|f| f.inverted_index_filter()) {
let filter = filter.query(searcher);
let mut queries = vec![(Occur::Must, raw)];
queries.extend(filter);
raw = Box::new(BooleanQuery::new(queries));
}
match self.limit {
EdgeLimit::Unlimited => raw,
EdgeLimit::Limit(limit) => Box::new(ShortCircuitQuery::new(
raw,
(limit + top_docs::DEDUPLICATION_BUFFER) as u64,
)),
EdgeLimit::LimitAndOffset { limit, offset } => Box::new(ShortCircuitQuery::new(
raw,
(limit + offset + top_docs::DEDUPLICATION_BUFFER) as u64,
)),
}
}
fn collector(&self, searcher: &Searcher) -> Self::Collector {
let mut collector = TopDocsCollector::from(self.limit)
.with_shard_id(searcher.shard())
.disable_offset()
.with_deduplicator(HostDeduplicator)
.with_column_fields(searcher.warmed_column_fields().clone())
.with_host_field(FromHostId);
if let Some(filter) = self.filter_as_and().and_then(|f| f.column_field_filter()) {
collector = collector.with_filter(filter);
}
collector
}
fn coordinator_collector(&self) -> Self::Collector {
TopDocsCollector::from(self.limit)
.enable_offset()
.with_deduplicator(HostDeduplicator)
}
fn retrieve(
&self,
searcher: &Searcher,
fruit: <Self::Collector as super::collector::Collector>::Fruit,
) -> Result<Self::IntermediateOutput> {
let docs: Vec<_> = fruit.into_iter().map(|(_, doc)| doc.address).collect();
let nodes = fetch_small_edges(searcher, docs, FromHostId)?;
Ok(nodes
.into_iter()
.map(|(node, rel_flags, score)| {
(
score,
SmallEdge {
from: node,
to: self.node,
rel_flags,
},
)
})
.collect())
}
fn filter_fruit_shards(
&self,
shard_id: ShardId,
fruit: <Self::Collector as super::Collector>::Fruit,
) -> <Self::Collector as super::Collector>::Fruit {
fruit
.into_iter()
.filter(|(_, doc)| doc.address.shard_id == shard_id)
.collect()
}
fn merge_results(results: Vec<Self::IntermediateOutput>) -> Self::Output {
let mut edges: Vec<_> = results.into_iter().flatten().collect();
edges.sort_by(|(a, _), (b, _)| a.cmp(b));
edges.into_iter().map(|(_, e)| e).collect()
}
}
#[derive(Debug, Clone, bincode::Encode, bincode::Decode)]
pub struct FullBacklinksQuery {
node: Node,
limit: EdgeLimit,
filters: Vec<FilterEnum>,
skip_self_links: bool,
deduplicate: bool,
}
impl FullBacklinksQuery {
pub fn new(node: Node) -> Self {
Self {
node,
limit: EdgeLimit::Unlimited,
filters: Vec::new(),
skip_self_links: true,
deduplicate: true,
}
}
pub fn with_limit(self, limit: EdgeLimit) -> Self {
Self { limit, ..self }
}
pub fn skip_self_links(mut self, skip_self_links: bool) -> Self {
self.skip_self_links = skip_self_links;
self
}
pub fn deduplicate(mut self, deduplicate: bool) -> Self {
self.deduplicate = deduplicate;
self
}
pub fn filter<F: Filter>(mut self, filter: F) -> Self {
self.filters.push(filter.into());
self
}
fn filter_as_and(&self) -> Option<AndFilter> {
if self.filters.is_empty() {
None
} else {
let mut filter = AndFilter::new();
for f in self.filters.clone() {
filter = filter.and(f);
}
Some(filter)
}
}
}
impl Query for FullBacklinksQuery {
type Collector = TopDocsCollector;
type TantivyQuery = Box<dyn tantivy::query::Query>;
type IntermediateOutput = Vec<Edge>;
type Output = Vec<Edge>;
fn tantivy_query(&self, searcher: &Searcher) -> Self::TantivyQuery {
let mut q = LinksQuery::new(
self.node.id(),
ToId,
searcher.warmed_column_fields().clone(),
)
.skip_self_links(self.skip_self_links);
if self.deduplicate {
q = q.with_deduplication_field(FromId);
}
let mut raw = Box::new(q) as Box<dyn tantivy::query::Query>;
if let Some(filter) = self.filter_as_and().and_then(|f| f.inverted_index_filter()) {
let filter = filter.query(searcher);
let mut queries = vec![(Occur::Must, raw)];
queries.extend(filter);
raw = Box::new(BooleanQuery::new(queries));
}
match self.limit {
EdgeLimit::Unlimited => raw,
EdgeLimit::Limit(limit) => Box::new(ShortCircuitQuery::new(
raw,
(limit + top_docs::DEDUPLICATION_BUFFER) as u64,
)),
EdgeLimit::LimitAndOffset { limit, offset } => Box::new(ShortCircuitQuery::new(
raw,
(limit + offset + top_docs::DEDUPLICATION_BUFFER) as u64,
)),
}
}
fn collector(&self, searcher: &Searcher) -> Self::Collector {
let mut collector = TopDocsCollector::from(self.limit)
.with_shard_id(searcher.shard())
.disable_offset()
.with_column_fields(searcher.warmed_column_fields().clone());
if let Some(filter) = self.filter_as_and().and_then(|f| f.column_field_filter()) {
collector = collector.with_filter(filter);
}
collector
}
fn coordinator_collector(&self) -> Self::Collector {
TopDocsCollector::from(self.limit).enable_offset()
}
fn retrieve(
&self,
searcher: &Searcher,
fruit: <Self::Collector as super::collector::Collector>::Fruit,
) -> Result<Self::IntermediateOutput> {
let docs: Vec<_> = fruit.into_iter().map(|(_, doc)| doc).collect();
let edges = fetch_edges(searcher, docs)?;
Ok(edges)
}
fn filter_fruit_shards(
&self,
shard_id: ShardId,
fruit: <Self::Collector as super::Collector>::Fruit,
) -> <Self::Collector as super::Collector>::Fruit {
fruit
.into_iter()
.filter(|(_, doc)| doc.shard_id == shard_id)
.collect()
}
fn merge_results(results: Vec<Self::IntermediateOutput>) -> Self::Output {
let mut edges: Vec<_> = results.into_iter().flatten().collect();
edges.sort_by(|a, b| b.sort_score.cmp(&a.sort_score));
edges
}
}
#[derive(Debug, Clone, bincode::Encode, bincode::Decode)]
pub struct FullHostBacklinksQuery {
node: Node,
limit: EdgeLimit,
filters: Vec<FilterEnum>,
nodes_as_host: bool,
skip_self_links: bool,
deduplicate: bool,
}
impl FullHostBacklinksQuery {
pub fn new(node: Node) -> Self {
Self {
node,
limit: EdgeLimit::Unlimited,
filters: Vec::new(),
nodes_as_host: true,
skip_self_links: true,
deduplicate: true,
}
}
pub fn with_limit(self, limit: EdgeLimit) -> Self {
Self { limit, ..self }
}
pub fn nodes_as_host(mut self, nodes_as_host: bool) -> Self {
self.nodes_as_host = nodes_as_host;
self
}
pub fn skip_self_links(mut self, skip_self_links: bool) -> Self {
self.skip_self_links = skip_self_links;
self
}
pub fn deduplicate(mut self, deduplicate: bool) -> Self {
self.deduplicate = deduplicate;
self
}
pub fn filter<F: Filter>(mut self, filter: F) -> Self {
self.filters.push(filter.into());
self
}
fn filter_as_and(&self) -> Option<AndFilter> {
if self.filters.is_empty() {
None
} else {
let mut filter = AndFilter::new();
for f in self.filters.clone() {
filter = filter.and(f);
}
Some(filter)
}
}
}
impl Query for FullHostBacklinksQuery {
type Collector = TopDocsCollector<DefaultDocumentScorer, HostDeduplicator>;
type TantivyQuery = Box<dyn tantivy::query::Query>;
type IntermediateOutput = Vec<Edge>;
type Output = Vec<Edge>;
fn tantivy_query(&self, searcher: &Searcher) -> Self::TantivyQuery {
let mut query = LinksQuery::new(
self.node.clone().into_host().id(),
ToHostId,
searcher.warmed_column_fields().clone(),
)
.skip_self_links(self.skip_self_links);
if self.deduplicate {
query = query.with_deduplication_field(FromHostId);
}
let mut raw = Box::new(query) as Box<dyn tantivy::query::Query>;
if let Some(filter) = self.filter_as_and().and_then(|f| f.inverted_index_filter()) {
let filter = filter.query(searcher);
let mut queries = vec![(Occur::Must, raw)];
queries.extend(filter);
raw = Box::new(BooleanQuery::new(queries));
}
match self.limit {
EdgeLimit::Unlimited => raw,
EdgeLimit::Limit(limit) => Box::new(ShortCircuitQuery::new(
raw,
(limit + top_docs::DEDUPLICATION_BUFFER) as u64,
)),
EdgeLimit::LimitAndOffset { limit, offset } => Box::new(ShortCircuitQuery::new(
raw,
(limit + offset + top_docs::DEDUPLICATION_BUFFER) as u64,
)),
}
}
fn collector(&self, searcher: &Searcher) -> Self::Collector {
let mut collector = TopDocsCollector::from(self.limit)
.with_shard_id(searcher.shard())
.disable_offset()
.with_deduplicator(HostDeduplicator)
.with_column_fields(searcher.warmed_column_fields().clone())
.with_host_field(FromHostId);
if let Some(filter) = self.filter_as_and().and_then(|f| f.column_field_filter()) {
collector = collector.with_filter(filter);
}
collector
}
fn coordinator_collector(&self) -> Self::Collector {
TopDocsCollector::from(self.limit)
.enable_offset()
.with_deduplicator(HostDeduplicator)
}
fn retrieve(
&self,
searcher: &Searcher,
fruit: <Self::Collector as super::collector::Collector>::Fruit,
) -> Result<Self::IntermediateOutput> {
let docs: Vec<_> = fruit.into_iter().map(|(_, doc)| doc.address).collect();
let edges = fetch_edges(searcher, docs)?;
if !self.nodes_as_host {
return Ok(edges);
}
Ok(edges
.into_iter()
.map(|e| Edge {
from: e.from.into_host(),
to: e.to.into_host(),
..e
})
.collect())
}
fn filter_fruit_shards(
&self,
shard_id: ShardId,
fruit: <Self::Collector as super::Collector>::Fruit,
) -> <Self::Collector as super::Collector>::Fruit {
fruit
.into_iter()
.filter(|(_, doc)| doc.address.shard_id == shard_id)
.collect()
}
fn merge_results(results: Vec<Self::IntermediateOutput>) -> Self::Output {
let mut edges: Vec<_> = results.into_iter().flatten().collect();
edges.sort_by(|a, b| b.sort_score.cmp(&a.sort_score));
edges
}
}
#[derive(Debug, Clone, bincode::Encode, bincode::Decode)]
pub struct BacklinksWithLabelsQuery {
node: NodeID,
limit: EdgeLimit,
filters: Vec<FilterEnum>,
}
impl BacklinksWithLabelsQuery {
pub fn new(node: NodeID) -> Self {
Self {
node,
limit: EdgeLimit::Unlimited,
filters: Vec::new(),
}
}
pub fn with_limit(self, limit: EdgeLimit) -> Self {
Self {
node: self.node,
limit,
filters: self.filters,
}
}
pub fn filter<F: Filter>(mut self, filter: F) -> Self {
self.filters.push(filter.into());
self
}
fn filter_as_and(&self) -> Option<AndFilter> {
if self.filters.is_empty() {
None
} else {
let mut filter = AndFilter::new();
for f in self.filters.clone() {
filter = filter.and(f);
}
Some(filter)
}
}
}
impl Query for BacklinksWithLabelsQuery {
type Collector = TopDocsCollector;
type TantivyQuery = Box<dyn tantivy::query::Query>;
type IntermediateOutput = Vec<(u64, SmallEdgeWithLabel)>;
type Output = Vec<SmallEdgeWithLabel>;
fn tantivy_query(&self, searcher: &Searcher) -> Self::TantivyQuery {
let mut raw = Box::new(
LinksQuery::new(self.node, ToId, searcher.warmed_column_fields().clone())
.with_deduplication_field(FromId),
) as Box<dyn tantivy::query::Query>;
if let Some(filter) = self.filter_as_and().and_then(|f| f.inverted_index_filter()) {
let filter = filter.query(searcher);
let mut queries = vec![(Occur::Must, raw)];
queries.extend(filter);
raw = Box::new(BooleanQuery::new(queries));
}
raw
}
fn collector(&self, searcher: &Searcher) -> Self::Collector {
let mut collector = TopDocsCollector::from(self.limit)
.with_shard_id(searcher.shard())
.disable_offset()
.with_column_fields(searcher.warmed_column_fields().clone());
if let Some(filter) = self.filter_as_and().and_then(|f| f.column_field_filter()) {
collector = collector.with_filter(filter);
}
collector
}
fn coordinator_collector(&self) -> Self::Collector {
TopDocsCollector::from(self.limit).enable_offset()
}
fn retrieve(
&self,
searcher: &Searcher,
fruit: <Self::Collector as super::Collector>::Fruit,
) -> Result<Self::IntermediateOutput> {
let docs: Vec<_> = fruit.into_iter().map(|(_, doc)| doc).collect();
let edges = fetch_edges(searcher, docs)?;
Ok(edges
.into_iter()
.map(|e| {
(
e.sort_score,
SmallEdgeWithLabel {
from: e.from.id(),
to: e.to.id(),
rel_flags: e.rel_flags,
label: e.label,
},
)
})
.collect())
}
fn filter_fruit_shards(
&self,
shard_id: ShardId,
fruit: <Self::Collector as super::Collector>::Fruit,
) -> <Self::Collector as super::Collector>::Fruit {
fruit
.into_iter()
.filter(|(_, doc)| doc.shard_id == shard_id)
.collect()
}
fn merge_results(results: Vec<Self::IntermediateOutput>) -> Self::Output {
let mut edges: Vec<_> = results.into_iter().flatten().collect();
edges.sort_by(|(a, _), (b, _)| a.cmp(b));
edges.into_iter().map(|(_, e)| e).collect()
}
}