mik_sql/pagination/
keyset.rs

1//! Keyset pagination condition generation.
2
3use crate::builder::{
4    CompoundFilter, Filter, FilterExpr, LogicalOp, Operator, SortDir, SortField, Value,
5};
6
7use super::cursor::Cursor;
8
9/// Keyset pagination condition.
10///
11/// Generates efficient `(col1, col2) > ($1, $2)` style WHERE clauses
12/// for keyset/seek pagination.
13#[derive(Debug, Clone, PartialEq)]
14#[non_exhaustive]
15pub struct KeysetCondition {
16    /// The sort fields and their directions.
17    pub sort_fields: Vec<SortField>,
18    /// The cursor values for each field.
19    pub cursor_values: Vec<Value>,
20    /// Direction: true for "after", false for "before".
21    pub forward: bool,
22}
23
24impl KeysetCondition {
25    /// Create a new keyset condition for paginating after a cursor.
26    #[must_use]
27    pub fn after(sorts: &[SortField], cursor: &Cursor) -> Option<Self> {
28        Self::new(sorts, cursor, true)
29    }
30
31    /// Create a new keyset condition for paginating before a cursor.
32    #[must_use]
33    pub fn before(sorts: &[SortField], cursor: &Cursor) -> Option<Self> {
34        Self::new(sorts, cursor, false)
35    }
36
37    fn new(sorts: &[SortField], cursor: &Cursor, forward: bool) -> Option<Self> {
38        if sorts.is_empty() {
39            return None;
40        }
41
42        // Match cursor fields to sort fields
43        let mut cursor_values = Vec::new();
44        for sort in sorts {
45            let value = cursor
46                .fields
47                .iter()
48                .find(|(name, _)| name == &sort.field)
49                .map(|(_, v)| v.clone())?;
50            cursor_values.push(value);
51        }
52
53        Some(Self {
54            sort_fields: sorts.to_vec(),
55            cursor_values,
56            forward,
57        })
58    }
59
60    /// Convert to a filter expression for the query builder.
61    ///
62    /// For a single field, generates: `field > $1` (or `<` for DESC)
63    ///
64    /// For multiple fields, generates proper compound OR conditions:
65    /// `(a, b) > (1, 2)` becomes: `(a > 1) OR (a = 1 AND b > 2)`
66    ///
67    /// For 3+ fields: `(a > 1) OR (a = 1 AND b > 2) OR (a = 1 AND b = 2 AND c > 3)`
68    ///
69    /// This follows the keyset pagination standard used by PostgreSQL, GraphQL Relay,
70    /// and major ORMs. See: <https://use-the-index-luke.com/no-offset>
71    #[must_use]
72    pub fn to_filter_expr(&self) -> FilterExpr {
73        if self.sort_fields.is_empty() || self.cursor_values.is_empty() {
74            // Return a tautology (always true) - will be optimized away
75            return FilterExpr::Simple(Filter {
76                field: "1".to_string(),
77                op: Operator::Eq,
78                value: Value::Int(1),
79            });
80        }
81
82        if self.sort_fields.len() == 1 {
83            // Simple case: single field comparison
84            let sort = &self.sort_fields[0];
85            let value = &self.cursor_values[0];
86            let op = self.get_operator(sort.dir);
87
88            return FilterExpr::Simple(Filter {
89                field: sort.field.clone(),
90                op,
91                value: value.clone(),
92            });
93        }
94
95        // Multi-field keyset: generate OR conditions
96        // (a, b, c) > (1, 2, 3) expands to:
97        //   (a > 1)
98        //   OR (a = 1 AND b > 2)
99        //   OR (a = 1 AND b = 2 AND c > 3)
100        let mut or_conditions: Vec<FilterExpr> = Vec::new();
101
102        for i in 0..self.sort_fields.len() {
103            // Build: equality on fields 0..i, then comparison on field i
104            let mut and_conditions: Vec<FilterExpr> = Vec::new();
105
106            // Add equality conditions for all preceding fields
107            for j in 0..i {
108                and_conditions.push(FilterExpr::Simple(Filter {
109                    field: self.sort_fields[j].field.clone(),
110                    op: Operator::Eq,
111                    value: self.cursor_values[j].clone(),
112                }));
113            }
114
115            // Add comparison condition for current field
116            let sort = &self.sort_fields[i];
117            let value = &self.cursor_values[i];
118            let op = self.get_operator(sort.dir);
119            and_conditions.push(FilterExpr::Simple(Filter {
120                field: sort.field.clone(),
121                op,
122                value: value.clone(),
123            }));
124
125            // Combine with AND
126            let condition = if and_conditions.len() == 1 {
127                and_conditions.into_iter().next().unwrap()
128            } else {
129                FilterExpr::Compound(CompoundFilter {
130                    op: LogicalOp::And,
131                    filters: and_conditions,
132                })
133            };
134
135            or_conditions.push(condition);
136        }
137
138        // Combine all with OR
139        if or_conditions.len() == 1 {
140            or_conditions.into_iter().next().unwrap()
141        } else {
142            FilterExpr::Compound(CompoundFilter {
143                op: LogicalOp::Or,
144                filters: or_conditions,
145            })
146        }
147    }
148
149    const fn get_operator(&self, dir: SortDir) -> Operator {
150        match (self.forward, dir) {
151            (true, SortDir::Asc) => Operator::Gt,
152            (true, SortDir::Desc) => Operator::Lt,
153            (false, SortDir::Asc) => Operator::Lt,
154            (false, SortDir::Desc) => Operator::Gt,
155        }
156    }
157}
158
159#[cfg(test)]
160#[allow(clippy::match_wildcard_for_single_variants)]
161mod tests {
162    use super::*;
163
164    #[test]
165    fn test_keyset_condition_asc() {
166        let sorts = vec![SortField::new("id", SortDir::Asc)];
167        let cursor = Cursor::new().int("id", 100);
168
169        let condition = KeysetCondition::after(&sorts, &cursor).unwrap();
170        let expr = condition.to_filter_expr();
171
172        match expr {
173            FilterExpr::Simple(f) => {
174                assert_eq!(f.field, "id");
175                assert_eq!(f.op, Operator::Gt);
176            },
177            _ => panic!("Expected simple filter"),
178        }
179    }
180
181    #[test]
182    fn test_keyset_condition_desc() {
183        let sorts = vec![SortField::new("created_at", SortDir::Desc)];
184        let cursor = Cursor::new().string("created_at", "2024-01-01");
185
186        let condition = KeysetCondition::after(&sorts, &cursor).unwrap();
187        let expr = condition.to_filter_expr();
188
189        match expr {
190            FilterExpr::Simple(f) => {
191                assert_eq!(f.op, Operator::Lt);
192            },
193            _ => panic!("Expected simple filter"),
194        }
195    }
196
197    #[test]
198    fn test_keyset_condition_before() {
199        let sorts = vec![SortField::new("id", SortDir::Asc)];
200        let cursor = Cursor::new().int("id", 100);
201
202        let condition = KeysetCondition::before(&sorts, &cursor).unwrap();
203        let expr = condition.to_filter_expr();
204
205        match expr {
206            FilterExpr::Simple(f) => {
207                assert_eq!(f.op, Operator::Lt);
208            },
209            _ => panic!("Expected simple filter"),
210        }
211    }
212
213    #[test]
214    fn test_keyset_condition_multi_field_asc_asc() {
215        // Test: (created_at, id) > ('2024-01-01', 100)
216        // Should generate: (created_at > '2024-01-01') OR (created_at = '2024-01-01' AND id > 100)
217        let sorts = vec![
218            SortField::new("created_at", SortDir::Asc),
219            SortField::new("id", SortDir::Asc),
220        ];
221        let cursor = Cursor::new()
222            .string("created_at", "2024-01-01")
223            .int("id", 100);
224
225        let condition = KeysetCondition::after(&sorts, &cursor).unwrap();
226        let expr = condition.to_filter_expr();
227
228        // Should be OR compound
229        match expr {
230            FilterExpr::Compound(compound) => {
231                assert_eq!(compound.op, LogicalOp::Or);
232                assert_eq!(compound.filters.len(), 2);
233
234                // First: created_at > '2024-01-01'
235                match &compound.filters[0] {
236                    FilterExpr::Simple(f) => {
237                        assert_eq!(f.field, "created_at");
238                        assert_eq!(f.op, Operator::Gt);
239                    },
240                    _ => panic!("Expected simple filter for first condition"),
241                }
242
243                // Second: (created_at = '2024-01-01' AND id > 100)
244                match &compound.filters[1] {
245                    FilterExpr::Compound(and_compound) => {
246                        assert_eq!(and_compound.op, LogicalOp::And);
247                        assert_eq!(and_compound.filters.len(), 2);
248                    },
249                    _ => panic!("Expected compound AND filter for second condition"),
250                }
251            },
252            _ => panic!("Expected compound OR filter for multi-field keyset"),
253        }
254    }
255
256    #[test]
257    fn test_keyset_condition_multi_field_desc_asc() {
258        // Test: ORDER BY created_at DESC, id ASC with cursor after
259        let sorts = vec![
260            SortField::new("created_at", SortDir::Desc),
261            SortField::new("id", SortDir::Asc),
262        ];
263        let cursor = Cursor::new()
264            .string("created_at", "2024-01-01")
265            .int("id", 100);
266
267        let condition = KeysetCondition::after(&sorts, &cursor).unwrap();
268        let expr = condition.to_filter_expr();
269
270        match expr {
271            FilterExpr::Compound(compound) => {
272                assert_eq!(compound.op, LogicalOp::Or);
273
274                // First condition: created_at < '2024-01-01' (DESC means <)
275                match &compound.filters[0] {
276                    FilterExpr::Simple(f) => {
277                        assert_eq!(f.field, "created_at");
278                        assert_eq!(f.op, Operator::Lt); // DESC + After = Lt
279                    },
280                    _ => panic!("Expected simple filter"),
281                }
282            },
283            _ => panic!("Expected compound filter"),
284        }
285    }
286
287    #[test]
288    fn test_keyset_condition_three_fields() {
289        // Test: (a, b, c) > (1, 2, 3) expands to:
290        //   (a > 1)
291        //   OR (a = 1 AND b > 2)
292        //   OR (a = 1 AND b = 2 AND c > 3)
293        let sorts = vec![
294            SortField::new("a", SortDir::Asc),
295            SortField::new("b", SortDir::Asc),
296            SortField::new("c", SortDir::Asc),
297        ];
298        let cursor = Cursor::new().int("a", 1).int("b", 2).int("c", 3);
299
300        let condition = KeysetCondition::after(&sorts, &cursor).unwrap();
301        let expr = condition.to_filter_expr();
302
303        match expr {
304            FilterExpr::Compound(compound) => {
305                assert_eq!(compound.op, LogicalOp::Or);
306                assert_eq!(compound.filters.len(), 3);
307
308                // First: a > 1 (simple)
309                match &compound.filters[0] {
310                    FilterExpr::Simple(f) => {
311                        assert_eq!(f.field, "a");
312                        assert_eq!(f.op, Operator::Gt);
313                    },
314                    _ => panic!("Expected simple filter"),
315                }
316
317                // Second: a = 1 AND b > 2
318                match &compound.filters[1] {
319                    FilterExpr::Compound(and_compound) => {
320                        assert_eq!(and_compound.filters.len(), 2);
321                    },
322                    _ => panic!("Expected compound filter"),
323                }
324
325                // Third: a = 1 AND b = 2 AND c > 3
326                match &compound.filters[2] {
327                    FilterExpr::Compound(and_compound) => {
328                        assert_eq!(and_compound.filters.len(), 3);
329                    },
330                    _ => panic!("Expected compound filter"),
331                }
332            },
333            _ => panic!("Expected compound filter"),
334        }
335    }
336
337    #[test]
338    fn test_keyset_with_missing_cursor_field() {
339        // Sort by field not in cursor should return None
340        let sorts = vec![SortField::new("missing_field", SortDir::Asc)];
341        let cursor = Cursor::new().int("id", 100);
342
343        let condition = KeysetCondition::after(&sorts, &cursor);
344        assert!(
345            condition.is_none(),
346            "Should return None when cursor missing required field"
347        );
348    }
349
350    #[test]
351    fn test_keyset_with_empty_sorts() {
352        let cursor = Cursor::new().int("id", 100);
353        let condition = KeysetCondition::after(&[], &cursor);
354        assert!(
355            condition.is_none(),
356            "Should return None for empty sort list"
357        );
358    }
359}
mik_sql/pagination/keyset.rs

mik_sql/pagination/
keyset.rs
