SQL Query Optimization, AST Compilers & Relational Database Internals: From Tokens to B+ Tree Index Scans

for (const r of R) {
  for (const s of S) {
    if (r.key === s.key) {
      emit(r, s);
    }
  }
}

-- ANTI-PATTERN: Non-SARGable (Forces Full Table Scan of 10,000,000 rows)
SELECT id, username 
FROM users 
WHERE DATE(created_at) = '2026-01-01';

-- SARGABLE REWRITE: Executes via O(log N) B+ Tree Index Range Scan (< 1 millisecond)
SELECT id, username 
FROM users 
WHERE created_at >= '2026-01-01 00:00:00' 
  AND created_at < '2026-01-02 00:00:00';

SELECT * FROM customers WHERE phone_number = 123456789;

/**
 * INNOXTOOLS HIGH-PERFORMANCE SQL COMPILER & FORMATTER
 * 100% Client-Side Lexical Tokenizer & AST Indentation Engine.
 */

export enum TokenType {
  KEYWORD,
  IDENTIFIER,
  OPERATOR,
  LITERAL_STRING,
  LITERAL_NUMBER,
  PUNCTUATION,
  WHITESPACE,
  NEWLINE
}

export interface SQLToken {
  type: TokenType;
  value: string;
}

export class SQLFormatterEngine {
  private static readonly KEYWORDS = new Set([
    'SELECT', 'FROM', 'WHERE', 'JOIN', 'INNER', 'LEFT', 'RIGHT', 'FULL',
    'OUTER', 'ON', 'GROUP', 'BY', 'HAVING', 'ORDER', 'ASC', 'DESC',
    'LIMIT', 'OFFSET', 'UNION', 'ALL', 'INSERT', 'INTO', 'VALUES',
    'UPDATE', 'SET', 'DELETE', 'CREATE', 'TABLE', 'ALTER', 'DROP',
    'INDEX', 'AND', 'OR', 'NOT', 'IN', 'IS', 'NULL', 'LIKE', 'BETWEEN',
    'CASE', 'WHEN', 'THEN', 'ELSE', 'END', 'AS', 'DISTINCT'
  ]);

  /**
   * Lexical Tokenizer: Transforms raw SQL string into typed tokens.
   */
  public static tokenize(sql: string): SQLToken[] {
    const tokens: SQLToken[] = [];
    let i = 0;
    const len = sql.length;

    while (i < len) {
      const char = sql[i];

      // Handle Whitespace & Newlines
      if (/\s/.test(char)) {
        if (char === '\n' || char === '\r') {
          tokens.push({ type: TokenType.NEWLINE, value: '\n' });
        }
        i++;
        continue;
      }

      // Handle String Literals ('text')
      if (char === "'") {
        let str = "'";
        i++;
        while (i < len && sql[i] !== "'") {
          if (sql[i] === "\\" && i + 1 < len) {
            str += sql[i++];
          }
          str += sql[i++];
        }
        str += "'";
        i++;
        tokens.push({ type: TokenType.LITERAL_STRING, value: str });
        continue;
      }

      // Handle Numbers
      if (/[0-9]/.test(char)) {
        let num = '';
        while (i < len && /[0-9.]/.test(sql[i])) {
          num += sql[i++];
        }
        tokens.push({ type: TokenType.LITERAL_NUMBER, value: num });
        continue;
      }

      // Handle Punctuation & Operators
      if (/[,();]/.test(char)) {
        tokens.push({ type: TokenType.PUNCTUATION, value: char });
        i++;
        continue;
      }
      if (/[=<>!+\-*\/]/.test(char)) {
        let op = char;
        i++;
        if (i < len && /[=><]/.test(sql[i])) {
          op += sql[i++];
        }
        tokens.push({ type: TokenType.OPERATOR, value: op });
        continue;
      }

      // Handle Identifiers & Keywords
      if (/[a-zA-Z_]/.test(char)) {
        let word = '';
        while (i < len && /[a-zA-Z0-9_.]/.test(sql[i])) {
          word += sql[i++];
        }
        const upper = word.toUpperCase();
        if (this.KEYWORDS.has(upper)) {
          tokens.push({ type: TokenType.KEYWORD, value: upper });
        } else {
          tokens.push({ type: TokenType.IDENTIFIER, value: word });
        }
        continue;
      }

      i++;
    }

    return tokens;
  }

  /**
   * AST-Aware Formatter: Applies enterprise indentation rules.
   */
  public static format(sql: string, indentSize = 2): string {
    const tokens = this.tokenize(sql);
    let output = '';
    let indentLevel = 0;
    const indent = ' '.repeat(indentSize);

    const MAJOR_CLAUSES = new Set(['SELECT', 'FROM', 'WHERE', 'GROUP BY', 'HAVING', 'ORDER BY', 'LIMIT']);

    for (let i = 0; i < tokens.length; i++) {
      const token = tokens[i];

      if (token.type === TokenType.KEYWORD && MAJOR_CLAUSES.has(token.value)) {
        output += (output.length > 0 ? '\n' : '') + token.value + '\n' + indent;
        continue;
      }

      if (token.type === TokenType.PUNCTUATION && token.value === ',') {
        output += ',\n' + indent;
        continue;
      }

      output += token.value + ' ';
    }

    return output.trim();
  }
}

Seq Scan on users  (cost=0.00..1845.00 rows=100000 width=72) (actual time=0.015..18.241 rows=100000 loops=1)
  Buffers: shared hit=845 read=1000
Planning Time: 0.124 ms
Execution Time: 22.450 ms

SELECT * FROM orders; -- 1 query returns 100 rows
SELECT * FROM order_items WHERE order_id = 1; -- 100 separate queries