Efficiently Querying Comma-Separated Keywords with AND Conditions in SQLite

Understanding Challenges with Keyword Matching in Denormalized String Columns

The core challenge revolves around querying records where a column contains comma-separated keywords, with the requirement to enforce logical AND conditions across multiple keywords. This scenario arises frequently in applications that store tags, categories, or attributes as a single string (e.g., 'computer-sci,programming,c'). While SQLite provides string manipulation functions like LIKE and INSTR, these methods often lead to unreliable results due to substring mismatches, improper delimiter handling, or inefficient execution plans. Additionally, the absence of a normalized schema (e.g., using junction tables) exacerbates performance and correctness issues as datasets grow.

The problem is compounded by edge cases such as single-keyword entries (e.g., 'c') or overlapping keyword substrings (e.g., 'c' vs. 'crab'). A naive approach using LIKE '%c%' would incorrectly match both 'c' and 'crab', while failing to enforce strict AND logic across multiple required keywords. The discussion highlights three primary strategies: (1) string-based pattern matching with delimiter safeguards, (2) recursive CTEs for keyword tokenization, and (3) schema normalization via junction tables. Each approach has trade-offs in accuracy, maintainability, and scalability.

Root Causes of Keyword Query Inefficiency and Incorrect Results

1. Substring Collisions in Delimiter-Free Patterns

The LIKE operator and INSTR function without proper delimiter handling cause unintended matches. For example, searching for 'c' in 'crab' using LIKE '%c%' returns a false positive. Similarly, INSTR(Keywords, 'c') > 0 fails to distinguish standalone keywords from substrings. This occurs because the absence of delimiter checks (e.g., commas) allows partial matches to satisfy conditions.

2. Inadequate Handling of Edge Cases in Comma-Separated Strings

When keywords are stored as comma-separated strings, edge cases such as single-keyword entries ('c'), leading/trailing commas, or inconsistent spacing break basic pattern-matching logic. For instance, a query designed to match 'c' using INSTR(',c,', ',c,') works for standalone keywords but fails if the stored string lacks enclosing commas or contains irregular spacing (e.g., 'c ,d').

3. Lack of Schema Normalization for Many-to-Many Relationships

Storing multiple keywords in a single column violates First Normal Form (1NF), leading to inefficient query execution. Without a junction table linking records to individual keywords, SQLite must repeatedly parse and tokenize the comma-separated string for each query. This results in O(n*m) complexity for n records and m keywords, degrading performance as data scales.

4. Recursive CTE Misapplication for AND Logic

Recursive Common Table Expressions (CTEs) can split comma-separated strings into individual tokens, but aggregating these tokens to enforce AND conditions requires additional logic. A naive recursive CTE may generate a list of tokens without associating them with their parent record, making it impossible to verify that all required keywords exist for a given row.

Step-by-Step Solutions for Reliable Keyword Queries

Solution 1: Delimiter-Aware String Matching with INSTR or LIKE

This approach wraps keywords and search terms in commas to enforce exact matches, avoiding substring collisions. For example, to find rows containing both 'computer-sci' and 'c':

SELECT id, keywords FROM entries
WHERE 
  instr(',' || keywords || ',', ',computer-sci,') > 0
  AND instr(',' || keywords || ',', ',c,') > 0;

Key Steps:

1. Normalize Stored Keywords: Ensure all entries are comma-separated without spaces (e.g., 'computer-sci,systems').
2. Wrap Keywords and Terms in Commas: This turns 'c' into ',c,', preventing matches with 'crab' or 'c-sharp'.
3. Combine Conditions with AND: Each required keyword becomes a separate INSTR or LIKE condition.

Limitations:

• Requires consistent keyword formatting (no spaces, trailing commas).
• Performance degrades with many AND conditions due to repeated full-string scans.

Solution 2: Recursive CTE for Tokenization and Aggregation

A recursive CTE can split keywords into tokens and then validate that all required tokens exist for a record. This method is more flexible but requires intermediate SQL skills.

WITH RECURSIVE split_tokens(id, token, remaining) AS (
  SELECT 
    id, 
    substr(keywords || ',', 0, instr(keywords || ',', ',')),
    substr(keywords || ',', instr(keywords || ',', ',') + 1)
  FROM entries
  UNION ALL
  SELECT
    id,
    substr(remaining, 0, instr(remaining, ',')),
    substr(remaining, instr(remaining, ',') + 1)
  FROM split_tokens
  WHERE remaining != ''
)
SELECT id
FROM split_tokens
WHERE token IN ('computer-sci', 'c')
GROUP BY id
HAVING COUNT(DISTINCT token) = 2;

Key Steps:

1. Tokenize Keywords: The CTE splits each comma-separated string into individual tokens.
2. Filter Tokens: Retain only tokens matching the required keywords ('computer-sci', 'c').
3. Aggregate by Record: Use GROUP BY id and HAVING COUNT(DISTINCT token) to enforce AND logic.

Limitations:

• Recursive CTEs can be slow for large datasets.
• Requires SQLite 3.8.3+ for CTE support.

Solution 3: Schema Normalization with Junction Tables

This is the most scalable and maintainable approach. It involves creating two new tables: one for unique keywords and another linking keywords to records.

Step 1: Create Normalized Tables

CREATE TABLE keywords (
  keyword_id INTEGER PRIMARY KEY,
  keyword TEXT UNIQUE
);

CREATE TABLE entry_keywords (
  entry_id INTEGER,
  keyword_id INTEGER,
  FOREIGN KEY(entry_id) REFERENCES entries(id),
  FOREIGN KEY(keyword_id) REFERENCES keywords(keyword_id)
);

Step 2: Migrate Existing Data
Use a recursive CTE or application logic to split existing comma-separated keywords and populate the normalized tables.

-- Using recursive CTE for migration
WITH RECURSIVE split(keyword, remaining, entry_id) AS (
  SELECT 
    substr(keywords || ',', 0, instr(keywords || ',', ',')),
    substr(keywords || ',', instr(keywords || ',', ',') + 1),
    id
  FROM entries
  UNION ALL
  SELECT
    substr(remaining, 0, instr(remaining, ',')),
    substr(remaining, instr(remaining, ',') + 1),
    entry_id
  FROM split
  WHERE remaining != ''
)
INSERT INTO keywords (keyword)
SELECT DISTINCT keyword FROM split WHERE keyword != '';

INSERT INTO entry_keywords (entry_id, keyword_id)
SELECT split.entry_id, keywords.keyword_id
FROM split
JOIN keywords ON split.keyword = keywords.keyword
WHERE split.keyword != '';

Step 3: Query Using JOINs
To find entries with both 'computer-sci' and 'c':

SELECT e.id, e.keywords
FROM entries e
JOIN entry_keywords ek1 ON e.id = ek1.entry_id
JOIN keywords k1 ON ek1.keyword_id = k1.keyword_id AND k1.keyword = 'computer-sci'
JOIN entry_keywords ek2 ON e.id = ek2.entry_id
JOIN keywords k2 ON ek2.keyword_id = k2.keyword_id AND k2.keyword = 'c';

Optimizations:

• Add indexes on keywords.keyword and entry_keywords.entry_id.
• Use INTERSECT for cleaner AND logic:

  SELECT entry_id FROM entry_keywords
  JOIN keywords USING (keyword_id)
  WHERE keyword = 'computer-sci'
  INTERSECT
  SELECT entry_id FROM entry_keywords
  JOIN keywords USING (keyword_id)
  WHERE keyword = 'c';
  

Advantages:

• Eliminates substring collisions.
• Enables efficient indexing and JOIN operations.
• Supports additional features like keyword counts or weighted tags.

Comparative Analysis and Decision Guide

Recommendations:

• Small Datasets: Use delimiter-aware string matching for simplicity.
• Moderate Datasets: Recursive CTEs offer a balance between correctness and complexity.
• Large-Scale Applications: Normalize the schema for optimal performance and flexibility.

By methodically addressing delimiter handling, leveraging SQLite’s recursive capabilities, and advocating for schema normalization, developers can achieve reliable and efficient keyword queries tailored to their application’s scale and requirements.