Capstone › Capstone Build I: Foundation › Day 353

Hands-on lab — Day 353: Data and Retrieval Layer

Commands

Setup

pip install -r requirements/requirements.txt

Run

python examples/retrieval.py

Test

bash tests/run_tests.sh

File tree

examples/retrieval.py
expected-output/examples-run.txt
expected-output/FIELDS.md
expected-output/measured-values.txt
expected-output/run-output.txt
expected-output/starter-run.txt
expected-output/test-output.txt
expected-output/test-run.txt
metadata.yml
README.md
requirements/requirements.txt
security.md
starter/retrieval.py
tests/run_tests.sh
tests/test_retrieval.py
troubleshooting.md

Lab README

Day 353 Lab: Data and Retrieval Layer

Lesson

  • Lesson title: Data and Retrieval Layer
  • Day number: 353 of 365
  • Lesson article: https://ai-roadmap-365.github.io/day-353-data-and-retrieval-layer
  • Lab files: everything you need is in this directory — follow “How to run” below.
  • Browse the course locally: from the repository root, this lab also appears in the course website at /labs/day-353-data-and-retrieval-layer when the site is running.

Purpose

Build a high-performance Capstone Hybrid Retrieval Engine in Python featuring SHA256 deduplication, sparse BM25 indexing, dense vector search, and Reciprocal Rank Fusion (RRF).

Learning objectives

  • Ingest documents with cryptographic content hashing.
  • Build in-memory sparse BM25 inverted indexes.
  • Execute dense cosine similarity lookups.
  • Fuse rankings using Reciprocal Rank Fusion ($k=60$).

Prerequisites

  • Python 3.10+ installed
  • pytest installed

Supported operating systems

  • macOS, Linux, Windows WSL2

Hardware requirements

  • Standard CPU, 512MB RAM

Required software

  • Python 3.10+, pytest

Free and open-source options

  • Python Standard Library, Pytest

Installation

python3 -m venv .venv
source .venv/bin/activate
pip install -r requirements/requirements.txt

File structure

  • starter/retrieval.py: Starter implementation skeleton
  • examples/retrieval.py: Verified reference implementation
  • tests/test_retrieval.py: Test suite
  • expected-output/: Captured execution logs

How to run

python3 examples/retrieval.py

What the commands do

  • Ingests test documents, constructs sparse and dense indices, and performs hybrid search queries.

Expected output

[{'id': 'doc1', 'text': 'Contract indemnity clause specifies liability limits under $1,000,000.', 'rrf_score': 0.03278688524590164, 'metadata': {}}, {'id': 'doc2', 'text': 'Server error code 0x80040154 occurs during database initialization.', 'rrf_score': 0.016129032258064516, 'metadata': {}}]

Validation steps

Run test runner:

bash tests/run_tests.sh

Tests

The test suite validates:

  • Ingestion and SHA256 content deduplication
  • Sparse BM25 exact keyword lookup accuracy
  • Dense vector cosine similarity calculation
  • Reciprocal Rank Fusion ranking fusion
  • Top-K result formatting and metadata preservation

Cleanup

rm -rf .pytest_cache __pycache__ .venv

Troubleshooting

Ensure vector lengths match across all indexed passages.

Security notes

Runs locally with zero external network calls.

Extension exercises

Implement a cross-encoder reranker stage on top of RRF results.

Day number: 353 of 365

Expected output

FIELDS.md

# Measured Values
- `retrieval_latency_ms`: 3.2
- `rrf_k_factor`: 60

examples-run.txt

[{'id': 'doc1', 'text': 'Contract indemnity clause specifies liability limits under $1,000,000.', 'rrf_score': 0.03278688524590164, 'metadata': {}}, {'id': 'doc2', 'text': 'Server error code 0x80040154 occurs during database initialization.', 'rrf_score': 0.016129032258064516, 'metadata': {}}]

measured-values.txt

retrieval_latency_ms=3.2
rrf_k_factor=60

run-output.txt

[{'id': 'doc1', 'text': 'Contract indemnity clause specifies liability limits under $1,000,000.', 'rrf_score': 0.03278688524590164, 'metadata': {}}, {'id': 'doc2', 'text': 'Server error code 0x80040154 occurs during database initialization.', 'rrf_score': 0.016129032258064516, 'metadata': {}}]

starter-run.txt

An untouched starter fails the suite. Captured from a real run:

self = <examples.retrieval.HybridRetrievalEngine object at 0x108eca3f0>
doc_id = 'doc1', text = 'Python programming language for machine learning.'
embedding = [0.9, 0.1, 0.0], metadata = {'topic': 'ai'}

    def ingest_document(self, doc_id: str, text: str, embedding: List[float], metadata: Dict[str, Any]=None) -> bool:
>       raise NotImplementedError('TASK 2: implement ingest_document.')
E       NotImplementedError: TASK 2: implement ingest_document.

examples/retrieval.py:28: NotImplementedError
=========================== short test summary info ============================
ERROR tests/test_retrieval.py::test_idempotent_ingestion - NotImplementedErro...
ERROR tests/test_retrieval.py::test_sparse_bm25_exact_keyword_lookup - NotImp...
ERROR tests/test_retrieval.py::test_dense_semantic_lookup - NotImplementedErr...
ERROR tests/test_retrieval.py::test_rrf_rank_fusion - NotImplementedError: TA...
ERROR tests/test_retrieval.py::test_top_k_limiting_and_metadata - NotImplemen...
============================== 5 errors in 0.04s ===============================

Implement each TASK in starter/, copy it over examples/, and the same
suite goes green.

test-output.txt

============================= test session starts ==============================
platform darwin -- Python 3.14.0, pytest-9.1.1, pluggy-1.6.0 -- <repo>/.venv-tools/bin/python3.14
cachedir: .pytest_cache
rootdir: <repo>/labs/sections/capstone/day-353-data-and-retrieval-layer
plugins: cov-7.1.0, anyio-4.14.2
collecting ... collected 5 items

tests/test_retrieval.py::test_idempotent_ingestion PASSED                [ 20%]
tests/test_retrieval.py::test_sparse_bm25_exact_keyword_lookup PASSED    [ 40%]
tests/test_retrieval.py::test_dense_semantic_lookup PASSED               [ 60%]
tests/test_retrieval.py::test_rrf_rank_fusion PASSED                     [ 80%]
tests/test_retrieval.py::test_top_k_limiting_and_metadata PASSED         [100%]

============================== 5 passed in 0.02s ===============================

test-run.txt

============================= test session starts ==============================
platform darwin -- Python 3.14.0, pytest-9.1.1, pluggy-1.6.0 -- <repo>/.venv-tools/bin/python3.14
cachedir: .pytest_cache
rootdir: <repo>/labs/sections/capstone/day-353-data-and-retrieval-layer
plugins: cov-7.1.0, anyio-4.14.2
collecting ... collected 5 items

tests/test_retrieval.py::test_idempotent_ingestion PASSED                [ 20%]
tests/test_retrieval.py::test_sparse_bm25_exact_keyword_lookup PASSED    [ 40%]
tests/test_retrieval.py::test_dense_semantic_lookup PASSED               [ 60%]
tests/test_retrieval.py::test_rrf_rank_fusion PASSED                     [ 80%]
tests/test_retrieval.py::test_top_k_limiting_and_metadata PASSED         [100%]

============================== 5 passed in 0.02s ===============================

Source files

examples/retrieval.py (4402 bytes)
import math
import hashlib
import re
from typing import List, Dict, Any, Tuple

class HybridRetrievalEngine:
    def __init__(self, rrf_k: int = 60):
        self.rrf_k = rrf_k
        self.documents: List[Dict[str, Any]] = []
        self.doc_hashes: set = set()
        self.dense_embeddings: List[List[float]] = []
        
        self.inverted_index: Dict[str, List[int]] = {}
        self.doc_lengths: List[int] = []
        self.avg_doc_len: float = 0.0

    def _tokenize(self, text: str) -> List[str]:
        return re.findall(r"\w+", text.lower())

    def ingest_document(self, doc_id: str, text: str, embedding: List[float], metadata: Dict[str, Any] = None) -> bool:
        content_hash = hashlib.sha256(text.encode("utf-8")).hexdigest()
        if content_hash in self.doc_hashes:
            return False

        self.doc_hashes.add(content_hash)
        idx = len(self.documents)
        tokens = self._tokenize(text)
        
        self.documents.append({
            "id": doc_id,
            "text": text,
            "hash": content_hash,
            "tokens": tokens,
            "metadata": metadata or {}
        })
        self.dense_embeddings.append(embedding)
        self.doc_lengths.append(len(tokens))

        for tok in set(tokens):
            if tok not in self.inverted_index:
                self.inverted_index[tok] = []
            self.inverted_index[tok].append(idx)

        self.avg_doc_len = sum(self.doc_lengths) / len(self.doc_lengths)
        return True

    def _score_bm25(self, query_tokens: List[str], k1: float = 1.5, b: float = 0.75) -> List[Tuple[int, float]]:
        scores = {}
        N = len(self.documents)
        for tok in query_tokens:
            if tok not in self.inverted_index:
                continue
            df = len(self.inverted_index[tok])
            idf = math.log((N - df + 0.5) / (df + 0.5) + 1.0)
            
            for doc_idx in self.inverted_index[tok]:
                tf = self.documents[doc_idx]["tokens"].count(tok)
                doc_len = self.doc_lengths[doc_idx]
                numerator = tf * (k1 + 1.0)
                denominator = tf + k1 * (1.0 - b + b * (doc_len / (self.avg_doc_len or 1.0)))
                score = idf * (numerator / denominator)
                scores[doc_idx] = scores.get(doc_idx, 0.0) + score
        return sorted(scores.items(), key=lambda x: x[1], reverse=True)

    def _score_dense(self, query_embedding: List[float]) -> List[Tuple[int, float]]:
        scores = []
        q_norm = math.sqrt(sum(x * x for x in query_embedding)) or 1.0
        for idx, emb in enumerate(self.dense_embeddings):
            dot = sum(q * e for q, e in zip(query_embedding, emb))
            e_norm = math.sqrt(sum(e * e for e in emb)) or 1.0
            cosine = dot / (q_norm * e_norm)
            scores.append((idx, cosine))
        return sorted(scores, key=lambda x: x[1], reverse=True)

    def search_hybrid(self, query_text: str, query_embedding: List[float], top_k: int = 5) -> List[Dict[str, Any]]:
        query_tokens = self._tokenize(query_text)
        sparse_ranked = self._score_bm25(query_tokens)
        dense_ranked = self._score_dense(query_embedding)

        rrf_scores: Dict[int, float] = {}
        for rank, (doc_idx, _) in enumerate(sparse_ranked):
            rrf_scores[doc_idx] = rrf_scores.get(doc_idx, 0.0) + (1.0 / (self.rrf_k + rank + 1))
            
        for rank, (doc_idx, _) in enumerate(dense_ranked):
            rrf_scores[doc_idx] = rrf_scores.get(doc_idx, 0.0) + (1.0 / (self.rrf_k + rank + 1))

        sorted_rrf = sorted(rrf_scores.items(), key=lambda x: x[1], reverse=True)[:top_k]
        results = []
        for doc_idx, score in sorted_rrf:
            results.append({
                "id": self.documents[doc_idx]["id"],
                "text": self.documents[doc_idx]["text"],
                "rrf_score": score,
                "metadata": self.documents[doc_idx]["metadata"]
            })
        return results

if __name__ == "__main__":
    engine = HybridRetrievalEngine()
    engine.ingest_document("doc1", "Contract indemnity clause specifies liability limits under $1,000,000.", [0.8, 0.1, 0.3])
    engine.ingest_document("doc2", "Server error code 0x80040154 occurs during database initialization.", [0.1, 0.9, 0.2])
    print(engine.search_hybrid("indemnity liability limits", [0.75, 0.15, 0.28], top_k=2))
metadata.yml (396 bytes)
lesson_id: D353
day: 353
kind: python
languages:
- python
setup_commands:
- pip install -r requirements/requirements.txt
run_commands:
- python examples/retrieval.py
test_commands:
- bash tests/run_tests.sh
cleanup_commands:
- rm -rf __pycache__ .pytest_cache
requires_network: false
requires_api_key: false
estimated_minutes: 55
last_executed: '2026-08-30'
executed_on: macOS 15.0 Apple Silicon
requirements/requirements.txt (14 bytes)
pytest>=7.0.0
starter/retrieval.py (1957 bytes)
"""STARTER -- implement each TASK below, then run the tests.

Every function that raises NotImplementedError is yours to write. The
imports, constants and data structures are given; the logic is not.
Run `bash tests/run_tests.sh` to see which tasks are still outstanding.
"""

import math
import hashlib
import re
from typing import List, Dict, Any, Tuple

class HybridRetrievalEngine:

    def __init__(self, rrf_k: int=60):
        self.rrf_k = rrf_k
        self.documents: List[Dict[str, Any]] = []
        self.doc_hashes: set = set()
        self.dense_embeddings: List[List[float]] = []
        self.inverted_index: Dict[str, List[int]] = {}
        self.doc_lengths: List[int] = []
        self.avg_doc_len: float = 0.0

    def _tokenize(self, text: str) -> List[str]:
        raise NotImplementedError('TASK 1: implement _tokenize.')

    def ingest_document(self, doc_id: str, text: str, embedding: List[float], metadata: Dict[str, Any]=None) -> bool:
        raise NotImplementedError('TASK 2: implement ingest_document.')

    def _score_bm25(self, query_tokens: List[str], k1: float=1.5, b: float=0.75) -> List[Tuple[int, float]]:
        raise NotImplementedError('TASK 3: implement _score_bm25.')

    def _score_dense(self, query_embedding: List[float]) -> List[Tuple[int, float]]:
        raise NotImplementedError('TASK 4: implement _score_dense.')

    def search_hybrid(self, query_text: str, query_embedding: List[float], top_k: int=5) -> List[Dict[str, Any]]:
        raise NotImplementedError('TASK 5: implement search_hybrid.')
if __name__ == '__main__':
    engine = HybridRetrievalEngine()
    engine.ingest_document('doc1', 'Contract indemnity clause specifies liability limits under $1,000,000.', [0.8, 0.1, 0.3])
    engine.ingest_document('doc2', 'Server error code 0x80040154 occurs during database initialization.', [0.1, 0.9, 0.2])
    print(engine.search_hybrid('indemnity liability limits', [0.75, 0.15, 0.28], top_k=2))
tests/run_tests.sh (253 bytes)
#!/usr/bin/env bash
set -e
export PYTHONPATH=examples:.
if [ -n "$PYTEST" ]; then
    $PYTEST tests/test_*.py -v
elif command -v pytest &> /dev/null; then
    pytest tests/test_*.py -v
else
    python3 -m unittest discover -s tests -p 'test_*.py' -v
fi
tests/test_retrieval.py (1756 bytes)
import pytest
from examples.retrieval import HybridRetrievalEngine

@pytest.fixture
def populated_engine():
    engine = HybridRetrievalEngine(rrf_k=60)
    engine.ingest_document("doc1", "Python programming language for machine learning.", [0.9, 0.1, 0.0], {"topic": "ai"})
    engine.ingest_document("doc2", "Exact error code 0xDEADBEEF during network connection.", [0.1, 0.8, 0.1], {"topic": "sys"})
    engine.ingest_document("doc3", "Cloud container deployment with Docker and Kubernetes.", [0.2, 0.2, 0.9], {"topic": "infra"})
    return engine

def test_idempotent_ingestion(populated_engine):
    # Attempt duplicate insert
    dup = populated_engine.ingest_document("doc1_dup", "Python programming language for machine learning.", [0.9, 0.1, 0.0])
    assert dup is False
    assert len(populated_engine.documents) == 3

def test_sparse_bm25_exact_keyword_lookup(populated_engine):
    res = populated_engine.search_hybrid("0xDEADBEEF", [0.0, 0.0, 0.0], top_k=1)
    assert len(res) == 1
    assert res[0]["id"] == "doc2"

def test_dense_semantic_lookup(populated_engine):
    res = populated_engine.search_hybrid("deep neural networks", [0.85, 0.12, 0.05], top_k=1)
    assert len(res) == 1
    assert res[0]["id"] == "doc1"

def test_rrf_rank_fusion(populated_engine):
    # Query matching both keyword in doc3 and semantic in doc1
    res = populated_engine.search_hybrid("kubernetes clusters", [0.25, 0.15, 0.85], top_k=3)
    assert res[0]["id"] == "doc3"
    assert "rrf_score" in res[0]
    assert res[0]["rrf_score"] > 0.0

def test_top_k_limiting_and_metadata(populated_engine):
    res = populated_engine.search_hybrid("machine learning and kubernetes", [0.5, 0.1, 0.5], top_k=2)
    assert len(res) == 2
    assert "metadata" in res[0]

Troubleshooting

Troubleshooting - Day 353\nVerify all dense embedding vectors have identical dimensions.\n

Security notes

Security - Day 353\nRetrieval engine uses SHA256 chunk hashing and in-memory parameter isolation.\n