Advanced URL Filtering, Sorting & Pagination

Collection endpoints (GET /v1/resources) represent the highest-traffic and most computationally volatile surfaces of any RESTful API. When an API is first developed with a few dozen test records, returning entire collections in a single JSON payload appears harmless. However, as enterprise databases scale to millions of rows, unbounded collection endpoints cause catastrophic performance degradation: out-of-memory crashes on application nodes, network interface saturation, severe database buffer pool cache eviction, and table-level contention.

To construct resilient, high-throughput collection APIs, architects must implement defensive data access patterns. This requires designing unambiguous URL query grammars for filtering and multi-field sorting, understanding the mathematical computational complexity of pagination paradigms (Offset vs Keyset vs Opaque Cursor), and mitigating the severe database penalties associated with aggregate counts and concurrent data drift.

Collection Endpoint Architecture & Defensive Defaults#

A defensive API assumes that clients may inadvertently or maliciously attempt to request millions of records simultaneously. Therefore, an enterprise collection endpoint must never return unconstrained datasets.

+-----------------------------------------------------------------------------------+
| Defensive Collection Request Lifecycle                                            |
|                                                                                   |
|  [ Client Request: GET /v1/orders?limit=1000000 ]                                 |
|                         |                                                         |
|                         v                                                         |
|  +-----------------------------------------------------------------------------+  |
|  | API Gateway / Controller Parameter Normalization                            |  |
|  | - Enforce DEFAULT_LIMIT = 25                                                |  |
|  | - Enforce MAX_LIMIT = 100 (clamp requested 1,000,000 to 100)               |  |
|  | - Validate filter parameters against strict allow-list schema               |  |
|  +-------------------------------------+---------------------------------------+  |
|                                        | Validated & Clamped Query Parameters     |
|                                        v                                          |
|  +-----------------------------------------------------------------------------+  |
|  | SQL / Data Layer Query Execution (Cursor Seek)                              |  |
|  | - SELECT * FROM orders WHERE (created_at, id) < (cursor_date, cursor_id)    |  |
|  |   ORDER BY created_at DESC, id DESC LIMIT 101                               |  |
|  | - Fetch LIMIT + 1 to detect has_next_page without SELECT COUNT(*)           |  |
|  +-------------------------------------+---------------------------------------+  |
|                                        | Database Tuples Retained in Buffer Cache |
|                                        v                                          |
|  +-----------------------------------------------------------------------------+  |
|  | Response Serialization & Hypermedia Synthesis                               |  |
|  | - Slice payload to 100 items                                                |  |
|  | - Generate opaque next_cursor base64 token                                  |  |
|  | - Output HAL / JSON:API collection with 'next' and 'self' links             |  |
|  +-----------------------------------------------------------------------------+  |
+-----------------------------------------------------------------------------------+

Essential Defensive Rules:#

1. Mandatory Pagination: Every collection endpoint must be paginated by default. If a client omits pagination parameters, the server enforces a conservative default (e.g., limit=25).
2. Ceiling Limit Clamping: The server enforces a hard ceiling limit (MAX_LIMIT = 100). If a client requests limit=10000, the server either rejects the request with HTTP 400 Bad Request or silently clamps the limit to 100.
3. Sparse Fieldsets (Field Selection): Clients should be capable of requesting only the specific attributes required by their user interface:

GET /v1/users?fields=id,email,displayName

This eliminates JSON serialization CPU overhead on the API server and reduces network bandwidth across cellular and IoT networks.

URL Filtering Grammars & Specifications#

Designing an intuitive and unambiguous query grammar for filtering collections is critical for developer experience and database performance. In the industry, three primary filtering patterns have gained widespread adoption:

1. Left-Hand-Side (LHS) Bracket Syntax#

LHS bracket notation places the comparison operator inside square brackets within the query parameter key:

• GET /v1/transactions?amount[gte]=100&amount[lte]=5000
• GET /v1/users?status[in]=active,pending&created_at[gte]=2026-01-01
• Advantages: Clean URL encoding, naturally parses into nested object structures in modern web frameworks (e.g., Express qs parser converts amount[gte]=100 directly into { amount: { gte: 100 } }).
• Disadvantages: Can require custom URL decoding logic in less flexible backend frameworks.

2. Right-Hand-Side (RHS) Colon / Dot Syntax#

RHS notation places the comparison operator on the right-hand side of the equals sign:

• GET /v1/transactions?amount=gte:100&created_at=lte:2026-01-01
• GET /v1/users?status=in:(active,pending)
• Advantages: Extremely simple parameter keys; cleanly avoids square bracket percent-encoding issues on legacy proxies.

3. Filter Expressions & Domain-Specific Grammars#

For complex multi-criteria queries requiring boolean logic (AND, OR, NOT) and grouping parentheses, enterprise platforms (Google Cloud APIs, Microsoft Graph, OData, SCIM) utilize structured filter expressions:

• Google AIP-160 / SCIM:

GET /v1/users?filter="department eq 'Engineering' and (title eq 'Architect' or level gte 4)"

• Architecture: Requires building a formal Lexer and Abstract Syntax Tree (AST) parser on the API server to validate expressions and securely compile them into parameterized SQL queries without exposing the database to SQL injection.

Multi-Field Sorting & Index Alignment#

Sorting dictates the order of resource presentation. A robust sorting API must allow consumers to specify multiple sort attributes and their respective directions.

Syntax Conventions#

The most prevalent standard uses comma-delimited attribute names, where a leading hyphen (-) denotes descending order:

• GET /v1/orders?sort=-created_at,priority

Translates to: Order by created_at DESC, then by priority ASC.

• Alternative Explicit Notation:

GET /v1/orders?sort=created_at:desc,priority:asc

Database Index Alignment and Performance#

A collection sort is only as fast as the database index supporting it. If a client issues:

SELECT * FROM orders WHERE status = 'pending' ORDER BY created_at DESC LIMIT 50;

Without a composite index on (status, created_at DESC), the relational database must:

1. Scan all rows matching status = 'pending' (potentially millions of records).
2. Load all matching rows into memory or spill to temporary disk storage.
3. Execute a CPU-intensive Sort operation (e.g., QuickSort or External Merge Sort).
4. Return the first 50 rows.

This is known as a Filesort in MySQL or a Sort node in PostgreSQL. In high-throughput production environments, un-indexed sorts immediately saturate database CPU. Every permissible sort attribute combination must be validated against a strict allow-list and backed by corresponding B-tree indexes.

Exhaustive Analysis of Pagination Paradigms#

Pagination is the mechanism of dividing a massive collection into discrete, manageable subsets. The three primary pagination architectures possess drastically different performance and behavioral characteristics.

+-----------------------------------------------------------------------------------+
| Computational Complexity of Pagination Paradigms                                  |
|                                                                                   |
|  1. Offset / Limit Pagination:                                                    |
|     SELECT * FROM items ORDER BY id LIMIT 50 OFFSET 1000000;                      |
|     - Engine scans 1,000,000 index tuples, reads 1,000,000 heap pages,            |
|       discards 1,000,000 records, returns 50 rows.                                |
|     - Time Complexity: O(N) where N = offset depth. Latency degrades linearly!   |
|                                                                                   |
|  2. Keyset Pagination (Direct Value Seek):                                        |
|     SELECT * FROM items WHERE id > 10542 ORDER BY id ASC LIMIT 50;                |
|     - Engine performs direct B-tree root-to-leaf binary search for id = 10542.    |
|     - Reads exactly 50 contiguous leaf pages.                                     |
|     - Time Complexity: O(log M) where M = total table rows. Constant latency!     |
|                                                                                   |
|  3. Opaque Cursor-Based Pagination:                                               |
|     SELECT * FROM items WHERE (created_at, id) < (1, 2)                         |
|     ORDER BY created_at DESC, id DESC LIMIT 50;                                   |
|     - Cursor encodes composite (created_at, id) token.                            |
|     - Supports non-unique attributes via unique tie-breaker.                      |
|     - Time Complexity: O(log M). Immune to data drift and page shifts.            |
+-----------------------------------------------------------------------------------+

1. Offset / Limit Pagination#

Mechanics and API Contract#

The client supplies an integer offset (number of records to skip) and a limit (number of records to return):

GET /v1/products?offset=100&limit=20

The O(N) Database Degradation Problem#

Relational database storage engines (such as InnoDB in MySQL or PostgreSQL heap tables) do not store rows in a dense array with direct arithmetic pointer access. To fulfill an OFFSET 1000000 LIMIT 50 query:

1. The storage engine traverses the B-tree index to find the starting point.
2. It sequentially reads 1,000,000 index entries.
3. For each entry, it accesses the heap page in memory (or reads from disk) to verify visibility under Multi-Version Concurrency Control (MVCC).
4. It discards all 1,000,000 rows.
5. It collects the next 50 rows and transmits them to the client.

As the offset increases, query execution time degrades linearly (O(N)). While fetching page 1 (OFFSET 0) executes in 0.8 milliseconds, fetching page 20,000 (OFFSET 1000000) can take 12 seconds, locking database worker threads and stalling the connection pool.

The Phantom Row (Data Drift) Anomaly#

Offset pagination assumes that the underlying dataset remains completely static while the user navigates. In modern transactional systems, this assumption is false.

• The Duplicate Item Bug:

1. Client fetches Page 1 (limit=10, offset=0), receiving items #1 through #10.

2. While the user is viewing Page 1, another user inserts a new record at the top of the collection (new item #1).

3. The previous item #10 is pushed down into position #11.

4. Client requests Page 2 (limit=10, offset=10).

5. The server skips the first 10 items and returns items starting at position #11.

6. The client receives the old item #10 a second time! The user sees an annoying duplicate record.

• The Skipped Item Bug:

Conversely, if item #3 is deleted while the user is on Page 1, all subsequent records shift upward by one position. When the user requests Page 2 (offset=10), the old item #11 (now at position #10) is skipped entirely and never seen by the user.

2. Keyset (Seek) Pagination#

Keyset pagination solves the O(N) degradation problem by replacing the arbitrary row offset with a filter condition based on the last seen record's primary or unique key:

GET /v1/products?since_id=10542&limit=20

SQL Translation:

SELECT * FROM products
WHERE id > 10542
ORDER BY id ASC
LIMIT 20;

Engineering Advantages:#

• True O(log N) Performance: The database uses the B-tree index to locate key 10542 in O(log N) time, and then scans forward exactly 20 leaf pointers. Performance remains constant whether reading the first page or the billionth page.
• Immunity to Data Drift: Inserting or deleting records prior to 10542 has zero effect on the seek pointer.

Limitations:#

• Requires Monotonic Sequential Ordering: Works cleanly only when sorting on a unique, strictly monotonic key (such as an auto-increment integer ID or ULID).
• No Random Page Access: Clients cannot jump directly to "Page 42"; they can only navigate sequentially forward (next) or backward (previous).

3. Opaque Cursor-Based Pagination#

In enterprise APIs, collections are rarely sorted purely by primary key; users frequently sort by non-unique fields such as created_at, status, or price.

Opaque cursor pagination generalizes keyset pagination to arbitrary sort orders by utilizing composite tie-breakers and encoding the pagination token as an opaque string (e.g., base64-encoded JSON or encrypted binary).

Opaque Cursor String:
"eyJpZCI6MTA5NDIsImMiOiIyMDI2LTEwLTMwVDE0OjAwOjAwWiJ9"
                         |
                         v (Base64 Decode)
{ "id": 10942, "c": "2026-10-30T14:00:00Z" }

SQL Composite Inequality Logic#

If sorting by created_at DESC, multiple records may share the exact same millisecond timestamp. To guarantee deterministic pagination without skipping or duplicating records, the unique id must be appended as a tie-breaker column.

The SQL seek query must evaluate a composite tuple inequality:

SELECT * FROM orders
WHERE (created_at < cursor_created_at)
   OR (created_at = cursor_created_at AND id < cursor_id)
ORDER BY created_at DESC, id DESC
LIMIT 21;

Modern database engines (PostgreSQL, MySQL 8+, SQLite 3.38+) optimize row-value syntax natively:

SELECT * FROM orders
WHERE (created_at, id) < (cursor_created_at, cursor_id)
ORDER BY created_at DESC, id DESC
LIMIT 21;

When backed by a composite index on (created_at DESC, id DESC), this query executes in pure O(log N) time with zero filesort overhead.

Architectural Comparison Matrix#

The Hidden Cost of `total_count` and `total_pages`#

Frontend designers frequently request response envelopes containing:

{
  "totalCount": 4820194,
  "totalPages": 96404,
  "currentPage": 1,
  "data": [ ... ]
}

In relational databases utilizing Multi-Version Concurrency Control (MVCC) like PostgreSQL, executing SELECT COUNT(*) FROM orders WHERE tenant_id = 42 is extraordinarily expensive.

Because MVCC engines must verify the transaction visibility of every individual tuple on the heap, COUNT(*) cannot simply read an in-memory counter. It must scan the entire table or index, reading millions of disk pages. Under high QPS, calculating total_count on every paginated request degrades database throughput by up to 90%.

Production Mitigation Strategies:#

1. The "Fetch Limit + 1" Pattern:

Instead of requesting 20 items, the server queries the database for LIMIT 21.

* If the database returns 21 rows, the server knows with certainty that a subsequent page exists (has_next_page = true).

* The server trims the 21st row from the response array and provides a next_cursor link.

* If the database returns ≤ 20 rows, has_next_page = false and no next link is returned.

Cost: Exactly 1 extra row transferred from database to application. Cost of `COUNT()`: Completely eliminated!

1. Asynchronous Estimated Counts:

For administrative dashboards requiring approximate metrics, query PostgreSQL internal statistics:

SELECT reltuples::bigint FROM pg_class WHERE relname = 'orders';

This returns an instant O(1) approximation without reading data pages.

Production Cursor Pagination Engine Implementation#

Below is a complete, production-grade TypeScript implementation of a composite cursor-based pagination engine supporting bi-directional navigation, secure HMAC token signing, and SQL query generation.

// cursor-engine.ts
import crypto from 'node:crypto';

export interface CursorPayload {
  sortValue: string | number;
  id: string | number;
  direction: 'next' | 'prev';
}

export interface PaginationResult<T> {
  data: T[];
  pageInfo: {
    hasNextPage: boolean;
    hasPrevPage: boolean;
    startCursor: string | null;
    endCursor: string | null;
  };
}

export class CursorPaginationEngine {
  private secretKey: string;

  constructor(secretKey: string) {
    this.secretKey = secretKey;
  }

  // Encodes and signs an opaque cursor token to prevent client tampering
  public encodeCursor(payload: CursorPayload): string {
    const jsonString = JSON.stringify(payload);
    const base64Data = Buffer.from(jsonString, 'utf-8').toString('base64url');
    
    // Compute HMAC-SHA256 signature
    const signature = crypto
      .createHmac('sha256', this.secretKey)
      .update(base64Data)
      .digest('base64url');

    return `{base64Data}.{signature}`;
  }

  // Decodes and verifies the cryptographic signature of an opaque cursor
  public decodeCursor(cursorToken: string): CursorPayload {
    const parts = cursorToken.split('.');
    if (parts.length !== 2) {
      throw new Error('Invalid cursor token structure');
    }

    const [base64Data, providedSignature] = parts;

    // Verify HMAC signature
    const expectedSignature = crypto
      .createHmac('sha256', this.secretKey)
      .update(base64Data)
      .digest('base64url');

    const signatureValid = crypto.timingSafeEqual(
      Buffer.from(providedSignature),
      Buffer.from(expectedSignature)
    );

    if (!signatureValid) {
      throw new Error('Cursor tampering detected: invalid signature');
    }

    const jsonString = Buffer.from(base64Data, 'base64url').toString('utf-8');
    return JSON.parse(jsonString) as CursorPayload;
  }

  // Processes raw database rows into an API pagination result
  public buildPaginationResponse<T extends { id: string | number; [key: string]: any }>(
    rawRows: T[],
    requestedLimit: number,
    sortField: string,
    isPreviousPage: boolean = false
  ): PaginationResult<T> {
    const hasMore = rawRows.length > requestedLimit;
    const items = hasMore ? rawRows.slice(0, requestedLimit) : [...rawRows];

    // If navigating backward, reverse items to restore chronological order
    if (isPreviousPage) {
      items.reverse();
    }

    const startItem = items[0] || null;
    const endItem = items[items.length - 1] || null;

    return {
      data: items,
      pageInfo: {
        hasNextPage: isPreviousPage ? true : hasMore,
        hasPrevPage: isPreviousPage ? hasMore : false,
        startCursor: startItem
          ? this.encodeCursor({
              sortValue: startItem[sortField],
              id: startItem.id,
              direction: 'prev'
            })
          : null,
        endCursor: endItem
          ? this.encodeCursor({
              sortValue: endItem[sortField],
              id: endItem.id,
              direction: 'next'
            })
          : null
      }
    };
  }
}

Checkpoint Practice Problems#

Test your architectural depth and mathematical analysis of URL filtering, sorting, and pagination through these real-world engineering scenarios.

Problem 1: B-Tree Index Scan Complexity & Database I/O Derivation#

An enterprise auditing table contains M = 20,000,000 immutable audit log entries. Each entry consumes an average of 256 bytes on disk. A database page occupies 8 KB (8,192 bytes) and holds 32 tuples. A B-tree index on (created_at, id) possesses an index tuple size of 32 bytes, packing 256 index records per 8 KB index leaf page. The B-tree index has a height of h = 4.

An API consumer executes two different pagination requests to fetch 50 records:

• Query 1 (Offset):

SELECT * FROM audit_logs ORDER BY created_at ASC, id ASC LIMIT 50 OFFSET 500000;

• Query 2 (Cursor Seek):

SELECT * FROM audit_logs WHERE (created_at, id) > (cursor_time, cursor_id) ORDER BY created_at ASC, id ASC LIMIT 50;

Calculate:

1. The total number of index pages and data heap pages that must be accessed in the buffer cache to fulfill Query 1.
2. The total number of index pages and data heap pages accessed to fulfill Query 2.
3. Compute the ratio of memory page visits between Query 1 and Query 2, and explain why Query 1 risks evicting hot working sets from the database buffer cache.

Solution:

Step 1: Calculate Page Visits for Query 1 (Offset):

To fulfill OFFSET 500000 LIMIT 50:

• The database traverses the B-tree from root to the first leaf (h = 4 pages).
• It must read through 500,050 sequential index tuples.

Number of index leaf pages scanned:

Index Leaf Pages = 500,050 / 256 ≈ 1,953.3 → 1,954 pages.

• In an index-only scan without MVCC heap access, only index pages would be read. However, because visibility checks must occur for every tuple in PostgreSQL, or because unindexed columns (SELECT *) must be fetched from the heap, the engine must retrieve the actual data rows.
• Assuming random disk layout across the table heap for 500,000 skipped rows:

Worst-case heap page accesses = 500,000 pages (if completely un-clustered).

Best-case clustered heap page accesses:

Heap Pages = 500,050 / 32 ≈ 15,627 pages.

Total Page Reads (Query 1, Best-Case Clustered) = 4 (tree traverse) + 1,954 (index scan) + 15,627 (heap reads) = 17,585 buffer page visits.

Step 2: Calculate Page Visits for Query 2 (Cursor Seek):

To fulfill the cursor seek query:

• The database uses the binary search key (cursor_time, cursor_id) to navigate from root to the exact leaf page (h = 4 page reads).
• It reads exactly 50 contiguous index entries from the leaf level.

50 entries fit entirely on 1 or 2 index leaf pages.

• It accesses the heap for only the 50 returned rows.

Number of heap pages accessed for 50 rows = ⌈ 50 / 32 ⌉ = 2 heap pages.

Total Page Reads (Query 2) = 4 (tree traverse) + 2 (index leaf) + 2 (heap reads) = 8 buffer page visits.

Step 3: Comparative Ratio and Cache Eviction Analysis:

Ratio = Pages(Query 1) / Pages(Query 2) = 17,585 / 8 ≈ 2,198.1×.

Query 1 forces the database to cycle through 17,585 buffer cache pages (approximately 140.7 MB of RAM) simply to discard 99.99% of the data and return 50 rows. If multiple clients execute offset pagination concurrently, the database's LRU (Least Recently Used) buffer cache is rapidly saturated with dead scan pages, evicting frequently accessed index pages belonging to other critical tables and driving global system latency up across all services. Query 2 executes in 8 page reads (64 KB) with zero cache pollution.

Problem 2: Phantom Row Drift Probability Under High-Frequency Ingestion#

A financial cryptocurrency exchange ledger records incoming limit orders. Orders arrive according to a Poisson process with an arrival rate of λ = 40 orders per second.

A monitoring dashboard polls the API using Offset/Limit pagination with limit = 100. The operator opens Page 1 (offset = 0), reviews the data for T = 3.5 seconds, and then clicks "Next" to load Page 2 (offset = 100).

Orders are sorted by created_at DESC (newest orders at the top of the collection).

Calculate:

1. The expected number of newly arrived orders (μ) inserted at the top of the ledger during the 3.5-second viewing interval.
2. The exact number of duplicate rows the operator will see repeated at the top of Page 2.
3. The probability that the operator experiences zero duplicate records on Page 2 under offset pagination.
4. Explain how transitioning to an opaque cursor completely eliminates this phenomenon.

Solution:

Step 1: Expected newly arrived orders:

For a Poisson process with rate λ = 40 orders/sec and duration T = 3.5 seconds:

μ = λ × T = 40 × 3.5 = 140 new ordersStep 2: Number of duplicate rows on Page 2:

• When Page 1 was fetched at t = 0, the client received records indexed 0 through 99.
• Over the next 3.5 seconds, 140 new orders arrive and are inserted at the beginning of the table (created_at is newest).
• Every pre-existing order is shifted down by exactly 140 positions.

* The record originally at index 0 is now at index 140.

* The record originally at index 99 is now at index 239.

• At t = 3.5 s, the client requests Page 2 with offset = 100, limit = 100.
• The server skips the first 100 items (which now consist of 100 of the 140 newly arrived items).
• The server returns items at positions 100 through 199.
• These positions contain:

* 40 remaining newly arrived items (items 100–139).

* 60 items from the original Page 1 (items originally at indices 0 through 59, now at 140–199).

Consequently, the operator observes 60 duplicate records on Page 2 that were already viewed on Page 1!

Step 3: Probability of zero duplicates:

Zero duplicates occur if and only if zero new orders arrive during the 3.5-second window (k = 0):

P(X = 0) = (e^{-μ} · μ^0) / (0!) = e^{-140} ≈ 1.58 × 10^{-61}The probability is virtually zero (P ≈ 0). In high-velocity transaction systems, offset pagination guarantees a corrupted, duplicate-ridden user experience.

Step 4: Cursor Resolution:

Under cursor pagination, Page 1 returns an opaque cursor pointing to the last item on Page 1:

cursor = encode({ created_at: order_99.created_at, id: order_99.id }).

When requesting Page 2, the client issues:

GET /v1/orders?cursor=...&limit=100.

The database query executes:

WHERE (created_at, id) < (order_99.created_at, order_99.id).

Regardless of whether 140 or 1,000,000 new orders were inserted at the top of the table with newer timestamps, they are all strictly greater than order_99.created_at and are ignored by the inequality filter. The query begins scanning exactly at order_100. Duplicate rows: 0.

Problem 3: Production Cursor-Based Pagination Engine in TypeScript & SQL#

Implement an Express.js middleware and repository function that executes keyset pagination over a table sorted by (priority DESC, created_at ASC, id ASC). The solution must handle composite null-safe comparisons and produce RFC-compliant HAL hypermedia links.

Solution:

// task-repository.ts
import { Pool } from 'pg';
import { CursorPaginationEngine } from './cursor-engine';

export interface TaskRecord {
  id: string;
  title: string;
  priority: number; // 1 = Low, 5 = Critical
  created_at: Date;
}

export class TaskRepository {
  private db: Pool;
  private cursorEngine: CursorPaginationEngine;

  constructor(db: Pool, cursorSecret: string) {
    this.db = db;
    this.cursorEngine = new CursorPaginationEngine(cursorSecret);
  }

  public async getPaginatedTasks(
    cursorToken?: string,
    limit: number = 25
  ) {
    const clampedLimit = Math.min(Math.max(1, limit), 100);
    const fetchSize = clampedLimit + 1; // Fetch limit + 1 to detect hasNextPage

    let sql = `
      SELECT id, title, priority, created_at 
      FROM tasks
    `;
    const params: any[] = [];

    if (cursorToken) {
      const cursor = this.cursorEngine.decodeCursor(cursorToken);
      const [priority, createdAt, id] = cursor.sortValue as [number, string, string];

      // Composite tuple inequality for: ORDER BY priority DESC, created_at ASC, id ASC
      sql += `
        WHERE (priority < 1)
           OR (priority = 1 AND created_at > 2)
           OR (priority = 1 AND created_at = 2 AND id > 3)
      `;
      params.push(priority, createdAt, id);
    }

    const limitParamIdx = params.length + 1;
    sql += `
      ORDER BY priority DESC, created_at ASC, id ASC 
      LIMIT {limitParamIdx}
    `;
    params.push(fetchSize);

    const result = await this.db.query<TaskRecord>(sql, params);
    const rows = result.rows;

    const hasNextPage = rows.length > clampedLimit;
    const items = hasNextPage ? rows.slice(0, clampedLimit) : rows;

    const lastItem = items[items.length - 1];
    let nextCursor: string | null = null;

    if (hasNextPage && lastItem) {
      nextCursor = this.cursorEngine.encodeCursor({
        sortValue: [lastItem.priority, lastItem.created_at.toISOString(), lastItem.id],
        id: lastItem.id,
        direction: 'next'
      });
    }

    return {
      items,
      nextCursor,
      hasNextPage
    };
  }
}

Problem 4: Query Grammar Lexer & Abstract Syntax Tree (AST) Parser#

Construct a recursive descent lexer and parser in TypeScript that tokenizes an incoming filter parameter adhering to the syntax:

status eq "active" and (priority gte 3 or category eq "billing")

and produces a structured AST verifying that attribute names belong to a strict database allow-list ['status', 'priority', 'category'], preventing SQL injection vulnerabilities.

Solution:

// filter-parser.ts

type TokenType = 'IDENTIFIER' | 'STRING' | 'NUMBER' | 'OPERATOR' | 'AND' | 'OR' | 'LPAREN' | 'RPAREN';

interface Token {
  type: TokenType;
  value: string;
}

export interface FilterNode {
  type: 'BINARY_EXPR' | 'COMPARISON';
  operator: 'and' | 'or' | 'eq' | 'ne' | 'gt' | 'gte' | 'lt' | 'lte';
  field?: string;
  value?: string | number;
  left?: FilterNode;
  right?: FilterNode;
}

export class FilterCompiler {
  private static ALLOWED_FIELDS = new Set(['status', 'priority', 'category']);
  private static COMPARISON_OPS = new Set(['eq', 'ne', 'gt', 'gte', 'lt', 'lte']);

  // 1. Lexical Analysis (Tokenizer)
  public static tokenize(input: string): Token[] {
    const tokens: Token[] = [];
    let i = 0;

    while (i < input.length) {
      const char = input[i];

      if (/[ \t\r\n]/.test(char)) {
        i++;
        continue;
      }

      if (char === '(') {
        tokens.push({ type: 'LPAREN', value: '(' });
        i++;
        continue;
      }

      if (char === ')') {
        tokens.push({ type: 'RPAREN', value: ')' });
        i++;
        continue;
      }

      if (char === '"' || char === "'") {
        const quote = char;
        let strVal = '';
        i++;
        while (i < input.length && input[i] !== quote) {
          strVal += input[i];
          i++;
        }
        i++; // Skip closing quote
        tokens.push({ type: 'STRING', value: strVal });
        continue;
      }

      if (/[0-9]/.test(char)) {
        let numStr = '';
        while (i < input.length && /[0-9.]/.test(input[i])) {
          numStr += input[i];
          i++;
        }
        tokens.push({ type: 'NUMBER', value: numStr });
        continue;
      }

      if (/[a-zA-Z_]/.test(char)) {
        let word = '';
        while (i < input.length && /[a-zA-Z0-9_]/.test(input[i])) {
          word += input[i];
          i++;
        }
        const lower = word.toLowerCase();
        if (lower === 'and') tokens.push({ type: 'AND', value: 'and' });
        else if (lower === 'or') tokens.push({ type: 'OR', value: 'or' });
        else if (this.COMPARISON_OPS.has(lower)) tokens.push({ type: 'OPERATOR', value: lower });
        else tokens.push({ type: 'IDENTIFIER', value: word });
        continue;
      }

      throw new Error(`Unexpected character in filter string: {char}`);
    }

    return tokens;
  }

  // 2. Syntactic Analysis (Parser)
  public static parse(tokens: Token[]): FilterNode {
    let cursor = 0;

    function peek(): Token | undefined {
      return tokens[cursor];
    }

    function consume(expectedType?: TokenType): Token {
      const t = tokens[cursor];
      if (!t || (expectedType && t.type !== expectedType)) {
        throw new Error(`Syntax Error: Expected {expectedType || 'token'}, got {t?.type}`);
      }
      cursor++;
      return t;
    }

    function parsePrimary(): FilterNode {
      const t = peek();
      if (!t) throw new Error('Unexpected end of input');

      if (t.type === 'LPAREN') {
        consume('LPAREN');
        const expr = parseExpression();
        consume('RPAREN');
        return expr;
      }

      if (t.type === 'IDENTIFIER') {
        const fieldToken = consume('IDENTIFIER');
        const fieldName = fieldToken.value;

        if (!FilterCompiler.ALLOWED_FIELDS.has(fieldName)) {
          throw new Error(`Security Violation: Field '{fieldName}' is not in the allowed query schema`);
        }

        const opToken = consume('OPERATOR');
        const valToken = consume();

        let parsedVal: string | number = valToken.value;
        if (valToken.type === 'NUMBER') {
          parsedVal = Number(valToken.value);
        }

        return {
          type: 'COMPARISON',
          field: fieldName,
          operator: opToken.value as any,
          value: parsedVal
        };
      }

      throw new Error(`Unexpected token: {t.value}`);
    }

    function parseExpression(): FilterNode {
      let left = parsePrimary();

      while (peek() && (peek()!.type === 'AND' || peek()!.type === 'OR')) {
        const opToken = consume();
        const right = parsePrimary();
        left = {
          type: 'BINARY_EXPR',
          operator: opToken.value as 'and' | 'or',
          left,
          right
        };
      }

      return left;
    }

    return parseExpression();
  }
}

Through this recursive descent compiler, arbitrary consumer filter strings are tokenized, rigorously validated against database allow-lists, and converted into deterministic ASTs, completely neutralizing SQL injection risks while granting consumers rich boolean query capabilities.