improve nested pagination. Should be O(n) instead O(n log n)
use connector::QueryArguments;
use prisma_models::{ManyRecords, RecordProjection};
-use std::collections::HashMap;
pub struct NestedPagination {
skip: Option<i64>,
@@ -21,7 +20,6 @@ impl NestedPagination {
if !self.must_apply_pagination() {
return;
}
- let mut count_by_parent_id: HashMap<Option<RecordProjection>, i64> = HashMap::new();
// replacement for SQL order by
// TODO: this must also handle secondary order bys
many_records.records.sort_by_key(|r| {
@@ -38,18 +36,25 @@ impl NestedPagination {
many_records.records.reverse();
}
+ // The records are sorted by their parent id. Hence we just need to remember the count for the last parent id to apply pagination.
+ let mut current_count: i64 = 0;
+ let mut last_parent_id: Option<RecordProjection> = None;
+
many_records.records.retain(|record| {
- let current_count = count_by_parent_id.get(&record.parent_id).unwrap_or(&0);
- let new_count = current_count + 1;
- count_by_parent_id.insert(record.parent_id.clone(), new_count);
+ if last_parent_id == record.parent_id {
+ current_count = current_count + 1;
+ } else {
+ last_parent_id = record.parent_id.clone();
+ current_count = 1; // this is the first record we see for this parent id
+ };
let is_beyond_skip_range = match self.skip {
None => true,
- Some(skip) => new_count > skip,
+ Some(skip) => current_count > skip,
};
let is_within_take_range = match self.take {
None => true,
- Some(take) => new_count <= take + self.skip.unwrap_or(0),
+ Some(take) => current_count <= take + self.skip.unwrap_or(0),
};
is_beyond_skip_range && is_within_take_range
