DEV Community: yang yaru

Understanding the Rerank Stage in Industrial RAG Pipelines

yang yaru — Fri, 13 Mar 2026 09:03:30 +0000

Retrieval-Augmented Generation (RAG) systems and modern search engines rely on multiple stages to retrieve the most relevant information for a user query. One critical component in these pipelines is Rerank, a stage designed to improve the precision of retrieved results.

In industrial systems, retrieval methods such as vector search or keyword search prioritize speed and recall, which means they often return many candidates that are only partially relevant. The reranking stage solves this problem by reordering these candidates using a stronger but more computationally expensive model.

This article explains how reranking typically works in production systems.

1. Query Processing

The pipeline begins when a user submits a query. Before retrieval starts, the system may perform several preprocessing steps to better understand the user's intent.

Common steps include:

Query normalization – removing noise, punctuation, or unnecessary tokens
Query rewriting – expanding or clarifying the query to improve recall
Intent detection – identifying the user’s goal or domain

Example query:

"How to deploy Dify with Docker?"

These preprocessing steps help the retrieval system generate better candidate results.

2. Multi-Recall (Candidate Generation)

Next, the system retrieves a large set of candidate documents using fast retrieval strategies. This stage focuses on maximizing recall, meaning it tries to retrieve as many potentially relevant documents as possible.

Common retrieval approaches include:

Vector Search (embedding similarity)
Keyword Search such as BM25
Metadata filtering
Hybrid retrieval, which combines multiple methods

Example:

Vector Search → Top 50 documents
Keyword Search → Top 30 documents

After merging, the system may have around 80 candidate documents.

3. Candidate Merge and Deduplication

Because results come from multiple retrieval channels, they must be merged into a single candidate set.

Typical operations include:

Removing duplicate documents
Normalizing scores from different retrieval methods
Combining results into a unified list

After merging and deduplication, the candidate set may shrink to around 60 documents.

4. Pre-Filtering (Optional)

To reduce computational cost before reranking, many production systems apply lightweight filtering.

Examples include:

Removing extremely short or low-quality documents
Filtering by similarity thresholds
Applying metadata constraints

After filtering, the system may keep around 40 candidates for reranking.

5. Reranking Stage (Core Step)

The rerank stage evaluates how well each candidate document matches the query and assigns a new relevance score.

Unlike embedding similarity—which compares vectors independently—rerank models typically use cross-encoders. These models process the query and document together, allowing them to capture deeper semantic relationships.

Example scoring:

Query:
"How to deploy Dify with Docker?"

Candidate scores:

Document A → 0.92
Document B → 0.88
Document C → 0.40
Document D → 0.31

The candidates are then reordered according to these scores.

6. Top-K Selection

After reranking, the system selects the Top-K documents with the highest relevance scores.

Typically:

Top 5–10 documents are selected.

These documents may be:

Sent to a Large Language Model (LLM) as context in a RAG system
Returned directly to the user in a search interface

7. Post-Processing (Optional)

Some production systems apply additional processing after reranking.

Examples include:

Diversity control to avoid returning highly similar documents
Chunk merging to combine adjacent text segments
Context window optimization to fit within LLM token limits

These steps help improve the final response quality.

Typical Industrial Architecture

User Query
    ↓
Query Rewrite / Intent Detection
    ↓
Multi-Recall
(Vector + Keyword + Metadata)
    ↓
Candidate Merge
    ↓
Pre-Filter
    ↓
Rerank (Cross-Encoder Model)
    ↓
Top-K Selection
    ↓
LLM Generation / Final Results

Why Reranking Is Necessary

Fast retrieval techniques such as vector search or BM25 are optimized for speed, not deep semantic understanding. As a result, their ranking quality is limited.

Reranking addresses this limitation by applying a more sophisticated model to a smaller set of candidates.

Method	Speed	Accuracy
Vector Search	Fast	Medium
BM25 Keyword Search	Fast	Medium
Rerank Model	Slower	High

Because reranking is computationally expensive, industrial systems follow a common architecture:

Fast Recall + Slow Precision

First, retrieve many candidates quickly. Then use a stronger model to produce a more accurate ranking.

Conclusion

Reranking plays a crucial role in modern search and RAG pipelines. By re-evaluating retrieved candidates with more powerful models, it significantly improves the relevance of final results while keeping system latency manageable.

Understanding this stage is essential for anyone building production-grade AI applications, especially systems that combine retrieval with large language models.

Query Rewrite in RAG Systems: Why It Matters and How It Works

yang yaru — Mon, 09 Mar 2026 08:20:48 +0000

In Retrieval-Augmented Generation (RAG) systems, many developers focus heavily on embeddings and vector databases. However, in real-world production systems, one of the most critical components is often overlooked:

Query Rewrite.

Query rewriting significantly improves retrieval quality and can dramatically impact the overall performance of a RAG pipeline.

This article explains:

What Query Rewrite is
Why it is necessary
How it is implemented in production systems
Common engineering patterns for query optimization

1. What Is Query Rewrite?

Query Rewrite refers to the process of transforming a user's original query into one or more optimized queries that are better suited for retrieval.

Users typically ask questions in natural language, but retrieval systems perform best when queries are:

clear
explicit
keyword-rich
structured

Therefore, a rewriting step is often introduced before retrieval.

Basic pipeline:

User Query
     ↓
Query Rewrite
     ↓
Optimized Retrieval Query
     ↓
Vector / Keyword Search

The rewritten queries help the retrieval system locate more relevant documents.

2. Why Query Rewrite Is Necessary

User queries often suffer from several issues that reduce retrieval quality.

2.1 Missing Context

Users frequently omit important context.

Example:

User query:
What is it?

The system may need to expand it to something like:

What is the architecture of LangGraph?

Without context, retrieval becomes ineffective.

2.2 Conversational Language

Users naturally ask questions in informal language.

Example:

How does AI connect to databases?

A retrieval-friendly query might be:

How to connect an LLM to a database

2.3 Very Short Queries

Example:

LangGraph

A better query for retrieval could be:

LangGraph framework architecture and use cases

2.4 Poor Retrieval Keywords

Example:

Why do AI models make things up?

A rewritten query might be:

LLM hallucination causes

This makes it easier to match relevant documents.

3. Query Rewrite in the RAG Pipeline

A typical RAG system pipeline looks like this:

User Query
     ↓
Query Rewrite
     ↓
Intent Analysis
     ↓
Multi Retrieval
(vector / keyword / metadata)
     ↓
Hybrid Merge
     ↓
Top-K
     ↓
Score Threshold
     ↓
Rerank
     ↓
LLM

Query rewriting is the first step in optimizing retrieval quality.

4. A Practical Query Rewrite Prompt

In many production systems, a small language model is used to generate optimized queries.

Example prompt:

You are a search query optimizer.

Rewrite the user's question to improve retrieval quality.

Rules:
1. Preserve the original meaning.
2. Remove conversational language.
3. Add missing keywords if necessary.
4. Generate 3 different search queries.

User Question:
{query}

Return JSON format:
{
 "intent": "...",
 "queries": ["...", "...", "..."]
}

This prompt produces structured retrieval queries.

5. Example

User input:

What is the difference between LangGraph and AutoGPT?

Rewritten output:

{
 "intent": "compare two AI agent frameworks",
 "queries": [
   "LangGraph vs AutoGPT architecture comparison",
   "differences between LangGraph and AutoGPT agent framework",
   "LangGraph workflow design vs AutoGPT autonomous agent"
 ]
}

Each generated query can then be sent to the retrieval system independently.

6. Common Query Rewrite Patterns

Production systems typically implement query rewriting in several ways.

6.1 Multi-Query Retrieval

The system generates multiple queries from a single user question.

Example:

Query 1 → vector search
Query 2 → vector search
Query 3 → vector search

The results are then merged and ranked.

Frameworks such as LangChain implement this strategy with components like MultiQueryRetriever.

Advantages:

Higher recall
Better document coverage

Disadvantages:

Increased retrieval cost

6.2 Query Decomposition

Complex questions are split into smaller sub-questions.

Example:

User query:

Why is LangGraph more stable than AutoGPT?

Decomposed queries:

LangGraph architecture
AutoGPT architecture
AutoGPT stability issues

Each query retrieves documents independently.

This method is particularly effective for complex reasoning tasks.

6.3 Query Routing

Some systems determine the intent of the query and route it to different retrieval mechanisms.

Example:

Query
 ↓
Intent Detection
 ↓
Router

Example routing table:

Intent	Retrieval Method
Technical explanation	Vector search
API documentation	Keyword search
Database query	SQL

7. The Full Query Optimization Pipeline

In advanced RAG systems, query processing often includes multiple steps:

User Query
   ↓
Query Rewrite
   ↓
Intent Detection
   ↓
Query Expansion
   ↓
Multi Retrieval
(vector + keyword)
   ↓
Hybrid Merge
   ↓
Top-K
   ↓
Rerank
   ↓
LLM

In practice, most RAG optimizations focus on three core areas:

Query Quality
Retrieval Strategy
Reranking

8. A Less Known Optimization Trick

Some systems do not stop at generating multiple queries.

Instead, they perform an additional step:

Rewrite
↓
Generate 5 queries
↓
Select the best 3 queries
↓
Run retrieval

This approach is sometimes called self-query optimization.

It improves retrieval quality while controlling cost.

9. Why Query Rewrite Matters More for Large Knowledge Bases

When a knowledge base is small:

~1000 documents

A simple query may still retrieve relevant information.

But in large systems:

~1,000,000 documents

Query quality becomes critical.

Poor queries lead to:

Low recall
↓
Missing documents
↓
Incorrect or incomplete LLM responses

10. Frameworks Supporting Query Rewrite

Several RAG frameworks provide built-in query transformation tools:

LangChain
LlamaIndex
Haystack

These frameworks include features such as:

Query transformation
Multi-query retrieval
Sub-question decomposition
Query routing

All of these techniques fall under the broader concept of query optimization.

Conclusion

While embeddings and vector databases are essential components of RAG systems, query quality often determines retrieval performance.

A well-designed Query Rewrite layer can:

improve recall
increase retrieval relevance
reduce hallucinations
enhance overall system reliability

In many production RAG pipelines, optimizing the query itself is one of the most effective ways to improve results.

Retrieval Strategy Design: Vector, Keyword, and Hybrid Search

yang yaru — Sat, 28 Feb 2026 06:08:56 +0000

This article explains how to design a modern retrieval strategy for AI systems, especially Retrieval-Augmented Generation (RAG). The focus is not only on definitions, but on engineering trade-offs, system architecture, and practical defaults.

The target audience is backend engineers who can already use embeddings, but want to design reliable and controllable search systems.

1. Where Retrieval Strategy Fits in the System

A typical modern retrieval pipeline looks like this:

User Query
  ↓
Query Rewrite / Intent Analysis
  ↓
Multi-Channel Retrieval
  (Vector / Keyword / Metadata)
  ↓
Hybrid Merge
  ↓
Top-K Limiting
  ↓
Score Threshold Filtering
  ↓
(Optional) Reranking
  ↓
LLM Generation

Concepts like vector search, hybrid search, Top-K, and threshold filtering are not isolated features. They work together inside the recall and filtering stages of this pipeline.

2. Vector Search: The Semantic Recall Layer

2.1 What Vector Search Solves

Vector search addresses the problem of semantic mismatch:

The user and the document use different words
The meaning is similar, but lexical overlap is low

Example:

Query: How to reduce dopamine addiction
Document: Attention control and dopamine regulation

Keyword search fails here, but embeddings succeed.

2.2 Core Parameters Engineers Must Understand

Similarity Metric

The most common similarity metrics are:

Cosine Similarity (industry default)
Dot Product
L2 Distance

Most embedding models are trained assuming cosine similarity, so databases typically follow that convention.

Index Type (Performance-Critical)

Index Type	Use Case
Flat	Small datasets, maximum accuracy
HNSW	General-purpose, production default
IVF	Very large-scale datasets

For most knowledge-base and RAG systems, HNSW is the best trade-off.

2.3 The Fundamental Weakness of Vector Search

Vector search is strong at recall, but weak at precision:

It retrieves related content
It may retrieve irrelevant but semantically nearby content

This is why vector search must be combined with:

Top-K limits
Score thresholds
Reranking

3. Keyword Search (BM25): The Precision Layer

Keyword search is not obsolete. Its role is deterministic precision.

It excels at:

Code and stack traces
API names
Error messages
Proper nouns
Numbers and IDs

In many technical queries, keyword search outperforms embeddings.

Another key benefit is controllability: keyword matching acts as a deterministic filter that reduces hallucinations.

4. Hybrid Search: The Industry Standard

Hybrid search combines the strengths of both approaches:

Vector search for semantic recall
Keyword search for lexical precision

This is no longer optional in production systems.

4.1 Parallel Hybrid (Most Common)

Vector Search Top-K = 20
Keyword Search Top-K = 20
↓
Merge Results
↓
Rerank

Advantages:

Simple to implement
Stable behavior
Widely used in production

4.2 Score Fusion Hybrid

A weighted scoring approach:

Final Score = α × Vector Score + β × BM25 Score

This method is suitable for search-engine-like systems that require strong global ranking.

5. Top-K: A Recall Boundary, Not a Quality Guarantee

A common misconception is:

Higher Top-K means better results

In reality:

Top-K defines the maximum recall scope
Large Top-K increases noise
Token usage and latency increase rapidly

Practical Defaults

Scenario	Recommended Top-K
FAQ	3–5
Technical Docs	5–10
Code Search	10–20

For most RAG systems:

Vector Top-K: 8–10
Keyword Top-K: 8–10

6. Score Threshold Filtering: The Missing Safeguard

Top-K always returns results — even when nothing is relevant.

Threshold filtering solves this:

Only keep results where score > threshold

Without thresholds, systems produce classic failures:

Query: Apple phone
Result: Apple fruit

Threshold Guidelines (Cosine Similarity)

Similarity	Interpretation
> 0.85	Strongly relevant
0.75–0.85	Acceptable
< 0.70	Noise

Many production systems use:

threshold ≈ 0.78

7. A Practical, Production-Ready Retrieval Strategy

A robust default pipeline:

1. Optional Query Rewrite
2. Vector Search (Top-K = 10)
3. Keyword Search (Top-K = 10)
4. Merge Results
5. Filter: score > 0.78
6. Rerank Top 5
7. Send Top 3 to LLM

This structure balances recall, precision, cost, and stability.

8. What Engineers Should Actually Focus On

8.1 Recall vs Precision Trade-off

Vector Search → Recall
Keyword Search → Precision
Reranker → Final Quality

Understanding this triangle is more important than tuning any single parameter.

8.2 Chunk Design Matters More Than Algorithms

Poor chunking breaks all retrieval strategies:

Chunks too long → embedding dilution
Chunks too short → context fragmentation

Good retrieval starts with good chunk boundaries.

8.3 Top-K Is Not the Final Output Size

Typical production flow:

Retrieve 20
Filter to 12
Rerank to 5
LLM consumes 3

Conclusion

Modern retrieval systems are not built on vector search alone.

Hybrid retrieval + threshold filtering + reranking is the real foundation of stable, production-grade RAG systems.

If you design retrieval with a system mindset instead of a single-algorithm mindset, quality improves dramatically.

Designing a Scalable Knowledge Base for Large Language Models

yang yaru — Wed, 11 Feb 2026 06:47:41 +0000

A Practical Engineering Guide to Cleaning, Semantic Chunking, Metadata, and Batch Embeddings

Large Language Model (LLM) knowledge bases are often misunderstood as simply “vectorizing documents.” In reality, a production-grade knowledge system is a retrieval infrastructure that must be traceable, incremental, and measurable.

This article walks through a practical engineering pipeline covering:

Data cleaning and normalization
Semantic chunking strategies
Metadata schema design
Batch embedding architecture
Retrieval and evaluation considerations

The focus is not theory, but implementation decisions that work in real systems.

1. System Architecture Overview

Before implementation, define the boundaries of your pipeline. A robust LLM knowledge base usually consists of the following stages:

Ingest → Normalize → Chunk → Enrich → Embed → Index → Retrieve → Monitor

Core Responsibilities

Ingest: PDFs, web pages, Markdown, databases, or internal docs
Normalize: Convert raw content into structured blocks
Chunk: Create retrieval-ready units
Enrich: Attach metadata and context
Embed: Generate vectors with version control
Index: Build hybrid search indexes
Serve: Retrieval + reranking + citation
Monitor: Evaluate retrieval quality continuously

A knowledge base is closer to a search engine than a simple storage system.

2. Data Cleaning and Normalization

The goal is not to “clean aggressively,” but to preserve structural signals.

Required Processing

Convert all content to UTF-8
Normalize whitespace and line breaks
Remove duplicated navigation/footer content
Detect headings (H1/H2/H3 or numeric sections)
Preserve structural blocks:
- Paragraphs
- Lists
- Tables
- Code blocks

Avoid flattening everything into plain text. Structure improves both retrieval accuracy and traceability.

Common Noise Sources

Web navigation bars and cookie banners
PDF headers and repeated page numbers
Hyphenated line breaks in scanned PDFs
Template content repeated across pages

Tables should ideally be converted into Markdown or key: value rows so that LLMs can interpret them correctly.

3. Semantic Chunking Strategy

Chunking is the most important factor affecting retrieval performance.

Chunking Goals

A good chunk should be:

Self-contained: understandable without large context
Traceable: linked back to its original location
Searchable: not too long or too fragmented

Recommended Hierarchical Approach

Structure-aware splitting (Preferred)

Split by document headings first
Merge paragraphs inside each section

Recursive splitting

Paragraph → Line → Sentence → Token boundary

Semantic boundary detection (Advanced)

Use topic shifts or embeddings to find natural breaks

Chunk Size and Overlap

Typical engineering defaults:

FAQ or policies: 200–450 tokens, overlap 30–80
Technical docs: 300–700 tokens, overlap 50–120
Long reports or research: 400–900 tokens, overlap 80–150

Overlap prevents losing context when answers span boundaries.

Parent–Child Chunk Design

A highly effective production pattern:

Child chunks: smaller pieces used for vector retrieval
Parent chunks: larger contextual sections passed to the LLM

Workflow:

Retrieve child chunks
Expand to parent chunks
Send parents to the model for generation

This significantly improves answer coherence.

4. Metadata Schema Design

Metadata is not optional. It enables filtering, access control, versioning, and debugging.

Minimum Viable Metadata

Each chunk should include:

doc_id
chunk_id
title
section_path
source_uri
page_start / page_end
created_at / updated_at
language
hash (content checksum)
tenant/project
acl (access control)

Enhanced Metadata (Recommended)

doc_version
effective_date
tags
entities (product names, systems, people)
content_type (faq, guide, spec, code)
parent_id
quality_flags

These fields enable advanced filtering and evaluation later.

Stable Chunk ID Strategy

Chunk IDs must remain stable across re-processing.

Example:

chunk_id = sha1(doc_id + doc_version + section_path + chunk_index + text_hash_prefix)

Only changed content should produce new IDs.

5. Batch Embedding Architecture

Embedding pipelines must be idempotent, incremental, and observable.

Suggested Data Model

documents

doc_id, version, uri, title, checksum

chunks

chunk_id, doc_id, text, metadata_json, hash

embeddings

chunk_id, model_name, dim, vector, text_hash

embedding_jobs

job_id, status, created_at

embedding_job_items

job_id, chunk_id, retry_count, error

Key Engineering Practices

Only embed chunks whose hash changed
Process in batches (32–256 chunks or token-limited)
Control concurrency to avoid rate limits
Implement exponential retry
Monitor throughput and failure rates

Supporting Multiple Models

Embedding records must include:

model_name
model_version
vector_dimension
normalized_flag

Allow multiple embeddings per chunk for gradual migration between models.

6. Retrieval Design: Hybrid Search and Reranking

Vector search alone is rarely sufficient.

Recommended Retrieval Pipeline

Hybrid retrieval:

Vector similarity
BM25 keyword search
1. Metadata filtering:
tenant/project
ACL
document type
1. Reranking:
Lightweight reranker or LLM scoring
1. Source citation:
Return source_uri + section_path + page

Hybrid search dramatically improves precision for exact terms and technical names.

7. Chunk Quality Monitoring

Many production issues are caused by poor chunks rather than model failures.

Common anti-patterns:

Chunks shorter than 50 tokens
Chunks longer than 1200 tokens
Repeated template content
Missing title context
Duplicate sections occupying top results

Add a simple rule engine that tags chunks with quality_flags.

8. End-to-End Processing Pipeline

A practical implementation roadmap:

Ingest documents and generate doc_id
Extract structured blocks
Remove noise and duplicates
Build parent chunks from sections
Generate child chunks with overlap
Attach metadata and hashes
Upsert into chunks table
Create embedding jobs for new/changed chunks
Batch embedding with workers
Build vector and keyword indexes
Run evaluation queries (golden dataset)

Final Thoughts

Designing an LLM knowledge base is less about models and more about information architecture.

The biggest improvements usually come from:

Better chunk structure
Strong metadata design
Incremental embedding pipelines
Hybrid retrieval strategies

If you treat your knowledge base like a search system rather than a document dump, both retrieval accuracy and generation quality improve significantly.

How to Choose the Right Model for Your AI Application(A Practical Engineering Guide)

yang yaru — Fri, 30 Jan 2026 07:10:13 +0000

Choosing an AI model is not about finding the strongest model.

It is about finding the most suitable model for your specific scenario.

Many developers waste money, suffer from slow responses, or over-engineer their systems simply because they start with the wrong assumption:

Bigger model = better product.

In reality:

There is no best model.

Only the best model for your use case.

This article provides a practical, engineering-oriented framework for selecting models in real AI applications.

1. The Four Core Dimensions of Model Selection

Every model choice is a trade-off between:

Capability (reasoning, language quality)
Latency (response speed)
Cost (per-token price)
Controllability (structured output reliability)

You cannot maximize all four simultaneously.

Good model selection means choosing the right balance.

2. First: Classify Your Application

Before choosing a model, identify which category your feature belongs to.

A. Generative Tasks

Article writing
Copywriting
Story generation

B. Q&A Tasks

Customer support
Knowledge base Q&A
FAQ bots

C. Structured Output Tasks

JSON generation
Tables
Fixed schemas

D. Strong Reasoning Tasks

Multi-step logical reasoning
Complex code analysis
Data reasoning

E. Embedding Tasks

Vectorization
Semantic search
Similarity matching

3. Capability Requirements by Category

Task Type	Needs Top-Tier Model?
Text generation	No
Customer service	No
Structured JSON	No
Strong reasoning	Yes
Code generation	Medium–High
Embedding	No (use embedding model)

Most applications do not need frontier models.

4. Industry-Proven Three-Tier Model Strategy

Mature systems rarely use a single model.

Instead:

Tier 1 — Cheap Model

Handles ~70% of traffic

Tier 2 — Mid-Level Model

Handles moderately complex requests

Tier 3 — Strong Model

Used only for hard cases

Architecture:

User Request
    |
Rule / Router
    |
Simple → Cheap Model
Medium → Mid Model
Complex → Strong Model

This drastically reduces cost while maintaining quality.

5. Embeddings Are a Separate Track

Never use chat models to create vectors.

Use a dedicated embedding model.

Pipeline:

Text → Embedding Model → Vector → Vector DB

Advantages:

Much cheaper
Better semantic consistency
Faster

6. Practical Model Selection Workflow

Step 1 — Define I/O Contract

Example:

Input: ...
Output: ...

Step 2 — Start with Mid-Level Model

Get the system working first.

Step 3 — Measure

Output quality
Latency
Cost per request

Step 4 — Upgrade Only If Needed

Only upgrade when:

Frequent hallucinations
Logical breakdown
Prompt already optimized

7. A Useful Rule of Thumb

If prompt engineering can fix it,

do NOT switch models.

Most failures are caused by:

Weak prompts
Missing constraints
Unclear output formats

Not weak models.

8. Temperature Guidelines

Scenario	Temperature
Article writing	0.7
Stable output	0.2
JSON generation	0.1
Creative writing	0.8

For article generation:

0.6 – 0.7

9. Three Common Beginner Mistakes

Mistake 1

Using the most expensive model by default

Mistake 2

No caching

Same prompt → regenerate → waste money

Mistake 3

No retry mechanism

Should have:

Fail → Retry once → Log

10. Backend-Oriented Architecture

Controller
|
Service
|
Prompt Builder
|
Model Router
 |       |
Cheap  Strong
|
AI Provider

11. When Should You Upgrade to Stronger Models?

Only when:

content frequently go off-topic
Logical structure collapses
Prompts already well designed

12. Final Takeaway

Start with mid-level models
Use embedding models for vectors
Let prompts and parameters do most of the work
Add model tiers later

Good architecture beats expensive models.

*If you found this useful, feel free to adapt it into your own system design or produce

How to Write a Developer-Level Prompt: A Practical Guide

yang yaru — Fri, 30 Jan 2026 06:46:38 +0000

Large Language Models (LLMs) do not work well with vague instructions.

If you want consistent, controllable, and production-grade behavior, you must move beyond simple “user prompts” and start designing Developer-level prompts.

This article explains:

What a Developer Prompt is
How it differs from other prompt types
A practical structure you can reuse
Real-world examples

1. Prompt Layers: System, Developer, and User

Modern LLM applications usually operate with three layers of instructions:

Layer	Purpose
System Prompt	Defines global behavior of the model
Developer Prompt	Defines product-level rules
User Prompt	Defines per-request task

Think of it like this:

System Prompt → Constitution
Developer Prompt → Job description
User Prompt → Daily task

Your focus as a builder is primarily the Developer Prompt.

2. What Is a Developer Prompt?

A Developer Prompt is a persistent instruction set that defines:

Who the model is
What its main responsibility is
What rules it must follow
What it is allowed and not allowed to do
How it must format output

It is not about what the user asks.

It is about how the system behaves.

A Developer Prompt turns a general AI into a specialized product component.

3. Why Developer Prompts Matter

Without a Developer Prompt:

The model improvises
Output style changes
Hallucinations increase
Formatting becomes inconsistent

With a Developer Prompt:

Behavior becomes stable
Boundaries are enforced
Outputs are predictable
Product quality improves

This is the difference between experimentation and engineering.

4. Standard Structure of a Developer Prompt

A strong Developer Prompt usually contains five sections:

Role
Goal
Knowledge Scope
Behavior Rules
Output Format

Generic Template


text
You are a {role}.

Your primary goal is to {goal}.

You must follow these rules:
1. ...
2. ...
3. ...

You can only use the following knowledge sources:
- ...

If information is missing, respond with:
"I don't know based on the provided information."

Output format:
- ...

Retrieval Technique Series-6.A Discourse on Design in High-Performance Retrieval Systems

yang yaru — Mon, 28 Jul 2025 03:59:07 +0000

In an era defined by data, the ability to retrieve information quickly and accurately is no longer a luxury—it's a fundamental requirement. From the search engines that power our curiosity to the e-commerce platforms that recommend our next purchase, high-performance retrieval systems are the invisible engines of our digital world. But what does it take to build a system that can sift through petabytes of data in milliseconds?

The answer lies in a set of core architectural philosophies. These are not just technical tricks but foundational principles that ensure scalability, speed, and stability. Let's explore four of the most critical design ideas that underpin modern, high-performance retrieval systems.

Principle 1: Decoupling the Index from the Data

At its core, a retrieval system works much like a library. To find a book, you don't scan every shelf; you first consult the card catalog—the index. This analogy highlights our first principle: the separation of the index from the actual data.

The Index: This is a lightweight, highly optimized data structure that maps search terms to the locations of the documents that contain them. Its primary job is to enable fast lookups.
The Data: This is the full, original content of the documents themselves (e.g., web pages, product descriptions, user profiles).
By decoupling these two, we gain immense benefits. The index, being much smaller than the raw data, can often be stored in faster media like SSDs or even loaded entirely into RAM. This allows the system to perform the initial "where is it?" query at lightning speed. Once the relevant document locations are identified, the system can then fetch the full data from slower, more cost-effective storage like HDDs or cloud object storage. This separation also allows for independent scaling—we can add more resources to our indexing service without altering our primary data storage, and vice-versa.

Principle 2: Minimizing Disk I/O

The single greatest bottleneck in most data-intensive systems is disk input/output (I/O). Accessing data from a spinning disk or even an SSD is orders of magnitude slower than accessing it from memory (RAM). Therefore, a relentless focus on minimizing disk I/O is paramount for performance.

Several techniques are employed to achieve this:

Aggressive Caching: Frequently accessed index blocks and popular documents are kept in memory caches. The system checks the cache first, avoiding a trip to the disk entirely if the data is present.
Data Compression: Compressing data reduces its size on disk, meaning fewer bytes need to be read for any given query. This trades a small amount of CPU time (for decompression) for a significant reduction in I/O latency.
Sequential Access Patterns: Random disk access is notoriously slow. Modern systems often use data structures like Log-Structured Merge-Trees (LSM-Trees) that convert random writes into sequential appends, which are much faster. Similarly, structuring data to be read sequentially can dramatically improve throughput.

Principle 3: Implementing Read-Write Separation

The workload of a retrieval system is typically asymmetrical. There are often far more read operations (users searching) than write operations (new data being indexed). The requirements for these two operations are also different: reads must be ultra-fast, while writes need to be durable and consistent.

This leads to the principle of Read-Write Separation, also known as Command Query Responsibility Segregation (CQRS). In this model:

The Write Path handles data ingestion, updates, and indexing. It can be optimized for throughput and data integrity.
The Read Path handles user queries. It operates on a separate, read-optimized copy of the data.
This separation allows us to scale each path independently. If search traffic spikes, we can simply spin up more read replicas without impacting the indexing process. This architecture also improves system resilience; a failure or slowdown in the write system won't bring down the search functionality for users.

Principle 4: Adopting a Layered or Tiered Architecture

It's not feasible to apply complex, computationally expensive logic to every single document in a massive dataset for every query. To solve this, high-performance systems adopt a multi-stage, layered processing approach, creating a "funnel" that progressively refines the results.

A typical search funnel might look like this:

Recall Layer (or Matching): This first layer quickly scans the index to retrieve a large set of potentially relevant candidates—perhaps thousands or tens of thousands of documents. The goal here is high recall (don't miss anything important) and speed. The scoring logic is simple and fast.
Ranking Layer (or Scoring): The candidate set from the first layer is passed to a second, more sophisticated layer. Here, more complex ranking models, often powered by machine learning, are used to score and order the documents more accurately. Since this is only applied to a smaller subset of documents, the computational cost is manageable.
Re-ranking Layer (or Blending): A final layer may take the top-ranked results and apply further business logic, personalization, or diversity rules to produce the final list presented to the user.
This tiered approach ensures that the most expensive computations are reserved for only the most promising candidates, striking a perfect balance between accuracy and performance.

Conclusion

Building a high-performance retrieval system is a masterclass in managing trade-offs. By embracing these four fundamental design philosophies—separating index and data, minimizing disk I/O, segregating reads and writes, and processing in layers—engineers can construct systems that are not only incredibly fast but also scalable, resilient, and efficient. These principles, working in concert, form the bedrock of the seamless information access we rely on every day.

Retrieval Technique Series-5.How Large-Scale Search Systems Accelerate Retrieval with Distributed Technology

yang yaru — Wed, 11 Jun 2025 06:14:37 +0000

In the era of big data, search systems must handle massive volumes of information and user queries efficiently. Traditional single-server architectures quickly become bottlenecks as data and traffic grow. To address this, large-scale search systems leverage distributed technology and index sharding to accelerate retrieval and ensure scalability. In this post, we’ll explore how these techniques work, their advantages, and the challenges they bring.

What are the advantages of distributed technology?

Distributed technology is the decomposition of large tasks into multiple subtasks, using multiple servers to jointly undertake tasks, which greatly improves the overall system's service capabilities compared to single machine systems.

What does a simple distributed structure look like?

A complete distributed system will have complex service management mechanisms, including service registration, service discovery, load balancing, traffic control, remote calling, and redundant backup. Here, let's first set aside the implementation details of distributed systems and return to their essence, which is to start with "letting multiple servers share the task" and see how a simple distributed retrieval system works. Firstly, we need a server that receives requests, but it does not perform specific query tasks. It is only responsible for task distribution, which we call a distribution server. Multiple index servers are the ones that actually perform the retrieval task, each of which stores a complete inverted index and is capable of completing the retrieval task. When the distribution server receives a request, it will send the current query request to a relatively idle index server for querying based on the load balancing mechanism. The specific retrieval work is independently completed by the indexing server and the results are returned.

                +----------------------+
                |   Dispatcher Server  |        The dispatcher server receives the request and forwards it to a specific index server, 
                +----------------------+          according to the load balancing mechanism.
                        |
             -------------------------------------------------------
             |                      |                              |
+---------------------+  +---------------------+   ...   +---------------------+
|  Full Index Data    |  |  Full Index Data    |         |  Full Index Data    |
|  Index Server 1     |  |  Index Server 2     |         |  Index Server n     |
+---------------------+  +---------------------+         +---------------------+

The index server processes the request and returns the search result.

What is Index Sharding?

Index sharding is the process of splitting a large search index into smaller, manageable pieces (shards) that can be distributed across multiple servers. Each shard contains a subset of the data, allowing the system to process queries in parallel and balance the load.

How Index Sharding Works

There are two main strategies for sharding:

1. Document-Based Sharding

Each shard contains a subset of documents.

+---------------------------------------------------------------+
|                        All Documents                          |
|  +-------------------+      ...      +-------------------+    |
|  | Document Set 1    |               | Document Set n    |    |
|  +-------------------+               +-------------------+    |
+---------------------------------------------------------------+
           |                                      |
           v                                      v
   Generate Index Shard 1                 Generate Index Shard n
           |                                      |
           v                                      v
+--------------------------------+   +--------------------------------+
| word 1 ->doc 1->doc 2...doc 19 |   |word 1 ->doc 23->doc 25...doc 41|
| word 2 ->doc 3->doc 4...doc 14 |   |word 2 ->doc 12->doc 16...doc 30|
|   ...                          |   |    ...                         |
| word n ->doc 1->doc 3...doc 15 |   |word n ->doc 21->doc 24...doc 35|
+--------------------------------+   +--------------------------------+

Note: The posting list in a single shard is incomplete.

When a query arrives:

                        +----------------------+
                        |  Dispatcher Server   |
                        +----------------------+
                                 |
        -------------------------------------------------
        |                       |                      |
+-------------------+  +-------------------+   ...   +-------------------+
|  Index Shard 1    |  |  Index Shard 2    |         |  Index Shard 3    |
|  Index Server 1   |  |  Index Server 2   |         |  Index Server n   |
+-------------------+  +-------------------+         +-------------------+

1. The dispatcher server receives the query request and sends the request to all index servers with different index shards.

2. Each index server searches its own loaded index shard and returns the search results to the dispatcher server.

3. The dispatcher server merges all returned results and returns the final result.

Advantages:

Accelerates search efficiency.
Evenly distributes queries and balances server load.
Makes it easier to update the index by adding or modifying documents.
Management Challenges:
Requires careful balancing of query loads across shards.

2. Keyword-Based Sharding

Each shard is responsible for a subset of keywords.

+-------------------+
|   All Documents   |
+-------------------+
          |
          v
   Generate Complete Inverted Index
          |
          v

 Incomplete |
 dictionary | Complete posting list in shard
 in shard   |                 
+--------------------------------------------+
| word 1  -----> doc 1 -> doc 2 ... doc 41   |
| word 2  -----> doc 3 -> doc 4 ... doc 30   |
|   ...                                      |
| word 20 -----> doc 1 -> doc 3 ... doc 35   |
+--------------------------------------------+
+--------------------------------------------+
| word 41 -----> doc 1 -> doc 5 ... doc 41   |
| word 42 -----> doc 2 -> doc 6 ... doc 30   |
|   ...                                      |
| word n  -----> doc 3 -> doc 4 ... doc 35   |
+--------------------------------------------+

When a query arrives:

Query: key1 + key2

                        +----------------------+
                        |  Dispatcher Server   |
                        +----------------------+
                          /               \
                         /                 \
        +---------------------+   +---------------------+   ...   +---------------------+
        |  Full Index Data    |   |  Full Index Data    |         |  Full Index Data    |
        |  Index Server 1     |   |  Index Server 2     |         |  Index Server n     |
        +---------------------+   +---------------------+         +---------------------+

 (Return posting list for key1)   (Return posting list for key2)

1. The dispatcher server receives the request and, based on the query, dispatches it to one or more index servers.
2. Index servers process the request and return the complete search results.
3. The dispatcher server merges the results and returns the final result.

Advantages:

Reduces duplicate computation.
Management Challenges:
If queries contain many keywords not evenly distributed, performance may drop.
High-frequency keywords can overload specific shards.

Conclusion

Index sharding and distributed technology are essential for building scalable, high-performance search systems. By splitting the index and distributing the workload, these systems can handle massive data volumes and high query rates efficiently. However, careful planning and management are required to avoid bottlenecks and ensure balanced performance.

Retrieval Technique Series-4.How Search Engines Generate Indexes for Trillions of Websites?

yang yaru — Fri, 06 Jun 2025 03:21:41 +0000

How to Generate Inverted Indexes Larger Than Memory Capacity

Review of In-Memory Inverted Index Generation

For small document collections that fit in memory, we generate hash-based inverted indexes as follows:

Assign unique, sequential IDs to each document
Scan each document sequentially, generating tuples
Store these tuples in an inverted table with the keyword as the key (position information can be omitted if unnecessary)
Repeat until all documents are processed

This creates an in-memory inverted index.

[Document Analysis Process]

+------------+                +---------------------------------------------+
| word 1     |                | Keywords | DocID  | Position | Posting List |
| word 2     |    Analyze     +----------+--------+----------+--------------+
| word 1     | ------------>  | Word 1   | Doc 2  | [1,3]    |              |
| doc 2      |                | Word 2   | Doc 2  | [2]      |              |
+------------+                +---------------------------------------------+
                                    |
                                    |
                                    v
If key exists in posting list, directly insert node:
word 1 -------> doc 1 -------> doc 2

If key doesn't exist in index, insert key and create posting list:
word 2 -------> doc 2

Handling Large-Scale Document Collections

For large-scale document collections, we need a different approach. Can we split them into smaller collections to build inverted indexes in memory? How do we combine these smaller indexes into a complete large-scale inverted index stored on disk?

Industrial-grade inverted indexes are more complex than what we've studied. For example, if a document contains "Geek Time" , not only might these four characters be added to the dictionary as keywords, but "Geek" , "Time" , and "Geek Time" might also be added. This results in a very large dictionary, potentially containing millions or tens of millions of terms.

Since words have different lengths and storage requirements, we assign a number to each word in the dictionary and store the corresponding string. In the posting list, we record not just document IDs but also position information, frequency, and other details. Each node in the posting list is a complex structure identified by document ID.

Dictionary                          Posting List
+--------------+      +-----------------------------------------------+
| word ID 1    | ---> | [doc 1, pos, tf,...] -> [doc 2, pos, tf,...]   -> ... -> [doc 19, pos, tf,...] |
| string       |      +-----------------------------------------------+
+--------------+
| word ID 2    |      +-----------------------------------------------+
| string       | ---> | [doc 19, pos, tf,...] -> [doc 21, pos, tf,...]  -> ... -> [doc 38, pos, tf,...] |
+--------------+      +-----------------------------------------------+
       :
       :
| word ID n    |      +-----------------------------------------------+
| string       | ---> | [doc 7, pos, tf,...] -> [doc 11, pos, tf,...]  -> ... -> [doc 43, pos, tf,...] |
+--------------+      +-----------------------------------------------+

Generating Industrial-Grade Inverted Indexes

Here's how we generate a large-scale inverted index:

Divide large document collections into multiple smaller sets
Generate in-memory inverted indexes for each small document set
Store these in-memory indexes on disk as temporary inverted files:
- Sort the document lists by keyword string size
- Write each keyword and its corresponding document list as a record to the temporary file
- Records in the temporary file are ordered, and we don't need to store keyword IDs (as they're only locally unique)

Index Table (In Memory)                                                                                  Temporary Files (Disk)

+----------------+                                                                                    +---------------------------+
| word ID 1      |                                                                                    | string 1 | posting list 1 |
| string         |---> doc 1 --> doc 2 --> ... --> doc 19                                             +---------------------------+
+----------------+                                                                                    | string 2 | posting list 2 |
                                                                                                      +---------------------------+
+----------------+                                                                                    | string 3 | posting list 3 |
| word ID 2      |                                                  Write to temporary files          +---------------------------+
| string         |---> doc 19 --> doc 20 --> ... --> doc 34         by key value order                |            ...            |
+----------------+                                                ----------------->                  +---------------------------+
                                                                                                      | string n | posting list n |
        ...                                                                                           +---------------------------+                                            
+----------------+                                             
| word ID n      |                                             
| string         |---> doc 1 --> doc 20 --> ... --> doc 53     
+----------------+

Process each batch of small document collections to generate corresponding temporary files
Merge multiple temporary files using multi-way merge:
- Extract the current record's keyword from each temporary file
- For identical keywords, read out and merge the corresponding posting lists
- If the posting list fits in memory, merge it there and write the result to the final inverted file
- If the posting list is too large, process it in segments
- Assign a globally unique ID to each keyword after merging

Temporary File 1               Temporary File 2           Temporary File 3
+-----------------------+  +-----------------------+  +-----------------------+
| string 1|posting list |  | string 1|posting list |  | string 3|posting list |
+-----------------------+  +-----------------------+  +-----------------------+
| string 2|posting list |  | string 3|posting list |  | string 4|posting list |
+-----------------------+  +-----------------------+  +-----------------------+
| string 3|posting list |  | string 4|posting list |  | string 5|posting list |
+-----------------------+  +-----------------------+  +-----------------------+
|          ...          |  |           ...         |  |           ...         |
+-----------------------+  +-----------------------+  +-----------------------+
| string n|posting list |  | string i|posting list |  | string j|posting list |
+-----------------------+  +-----------------------+  +-----------------------+
        |                         |                         |
        +-------------------------+-------------------------+
                                  |
                                  v
                     +-------------------------------------+
                     | word ID 1 | string 1 | posting list |
                     +-------------------------------------+
                     | word ID 2 | string 2 | posting list |
                     +-------------------------------------+
                     | word ID 3 | string 3 | posting list |
                     +-------------------------------------+
                     |                  ...                |
                     +-------------------------------------+
                     | word ID n | string n | posting list |
                     +-------------------------------------+
                            Complete Sorted File

This approach is similar to the Map-Reduce distributed computing paradigm, making it easy to implement on multiple machines to significantly improve efficiency.

Using Disk-Based Inverted Files for Retrieval

When using large-scale inverted files for retrieval, the core principle is to load as much data as possible into memory since memory retrieval is much faster than disk access.

An inverted index consists of two parts: the dictionary (key collection) and the document lists. In many applications, the dictionary is small enough to load into memory using a hash table.

Hash Table (In Memory)                 |        Inverted Index File (Disk)
                                       |
+----------------+                     |        +----------------------------+
| word ID 1      |                     |        | word ID 1 | posting list 1 |
| string         |---> pos ------------|------> +----------------------------+
+----------------+                     |        | word ID 2 | posting list 2 |
                                       |        +----------------------------+
+----------------+                     |        | word ID 3 | posting list 3 |
| word ID 2      |                     |        +----------------------------+
| string         |---> pos ------------|------> |              ...           |
+----------------+                     |        +----------------------------+
        :                              |        | word ID n | posting list n |
        :                              |        +----------------------------+
+----------------+                     |
| word ID n      |                     |
| string         |---> pos ------------|------->
+----------------+                     |
                                       |

When a query occurs:

Search the in-memory hash table to find the corresponding key
Read the posting list associated with that key from disk into memory for processing

If the dictionary is too large for memory, we can use a B+ tree to search it, treating it as an ordered sequence of keys.

The retrieval process can be summarized in two steps:

Use a B+ tree or similar technology to query the keyword in the dictionary
Read out the posting list for that keyword and process it in memory

B-tree/B+ tree (In Memory)      Dictionary File (Disk)           Inverted Index File (Disk)

       •                    +----------------------------+     +----------------------------+
      / \                   | word ID 1 | string 1 | pos |---->| word ID 1 | posting list 1 |
     •   •--------------->  +----------------------------+     +----------------------------+
    /                       | word ID 2 | string 2 | pos |---->| word ID 2 | posting list 2 |
   •                        +----------------------------+     +----------------------------+
  / \                       | word ID 3 | string 3 | pos |---->| word ID 3 | posting list 3 |
 •   •------------------->  +----------------------------+     +----------------------------+
                            |              ...           |     |             ...            |
                            +----------------------------+     +----------------------------+
                            | word ID n | string n | pos |---->| word ID n | posting list n |
                            +----------------------------+     +----------------------------+

Handling Very Large Posting Lists

For extremely popular keywords that might appear in hundreds of millions of pages, the posting lists may be too large to load into memory. In such cases:

Create B+ tree-like indexes for oversized posting lists
Load only useful data blocks into memory to reduce disk access
For shorter posting lists, load them directly into memory
Use caching techniques like LRU to keep frequently used posting lists in memory

Key Takeaways

We can generate trillion-level inverted indexes using multi-file merging and implement retrieval through dictionary and document list queries.
Two fundamental design principles:
- Load as much data as possible into memory (index compression is crucial here)
- Break large data collections into smaller sets (the core idea of distributed systems)

Retrieval Technique Series-3.Why Do Logging Systems Primarily Use LSM Trees Instead of B+ Trees?

yang yaru — Wed, 04 Jun 2025 03:24:07 +0000

In the world of NoSQL databases, the choice of data structure can significantly impact performance and efficiency. Logging systems, in particular, have found a reliable ally in Log-Structured Merge (LSM) trees, which offer distinct advantages over traditional B+ trees. This blog explores why LSM trees are favored in logging systems, focusing on their design philosophy and performance characteristics.

The Limitations of B+ Trees

Performance Bottlenecks

B+ trees are widely used in relational databases due to their efficient range queries and balanced structures. However, they encounter performance bottlenecks in write-heavy applications, such as logging systems. Each insert operation in a B+ tree may require multiple disk writes to maintain its structure, leading to increased latency.

┌───────────────────────────┐
│        B+ Tree Write      │
│  ┌──────┐   ┌──────┐      │
│  │Insert│   │Update│      │
│  └──────┘   └──────┘      │
│      │         │          │
│      ▼         ▼          │
│  Multiple Disk Writes     │
└───────────────────────────┘

Inherent Write Amplification

B+ trees suffer from write amplification, where a single logical write can result in multiple physical writes due to the need to maintain balance and order in the tree. This can cause significant overhead in high-throughput environments, making them less ideal for logging applications.

┌───────────────────────────┐
│      Write Amplification  │
│  ┌─────────────┐          │
│  │Logical Write│          │
│  └─────────────┘          │
│           │               │
│           ▼               │
│  Multiple Physical Writes │
└───────────────────────────┘

Advantages of LSM Trees

Write Optimization

LSM trees are designed specifically for write-heavy workloads. They accumulate writes in memory (in a structure called a MemTable) before merging them into disk-based structures in batches. This approach significantly reduces the number of disk writes, leading to better performance in logging systems.

┌───────────────────────────┐
│        LSM Tree Write     │
│  ┌──────┐                 │
│  │Insert│                 │
│  └──────┘                 │
│      │                    │
│  Accumulate in Memory     │
│      │                    │
│      ▼                    │
│   Batch Disk Write        │
└───────────────────────────┘

Efficient Data Merging

LSM trees periodically merge the data stored in the MemTable with data on disk, ensuring that the structure remains efficient and compact. This merging process is designed to minimize the impact on read performance, allowing for fast retrieval even as new data is continuously written.

┌────────────────────────────┐
│     Efficient Data Merge   │
│  ┌────────┐   ┌────────┐   │
│  │MemTable│   │ Disk   │   │
│  └────────┘   └────────┘   │
│        │                   │
│        ▼                   │
│     Merge Process          │
└────────────────────────────┘

LSM Tree Design Philosophy

Batch Writes and Reduced I/O

The core design philosophy of LSM trees revolves around reducing the frequency of I/O operations. By accumulating multiple writes in memory and performing batch writes, LSM trees ensure that the underlying storage system is not overwhelmed by frequent updates.

Handling High Write Frequencies

Logging systems often generate large volumes of data in a short period. LSM trees are well-suited to handle high write frequencies without compromising performance. This capability allows logging systems to scale efficiently.

┌────────────────────────────┐
│   Handling High Write      │
│           Frequencies      │
│  ┌────────┐   ┌────────┐   │
│  │Log Data│   │LSM Tree│   │
│  └────────┘   └────────┘   │
│        │                   │
│        ▼                   │
│    Efficient Processing    │
└────────────────────────────┘

Search Operations and Recent Data

Optimized Searching

LSM trees also optimize search operations. When searching for data, they check the MemTable first, providing quick access to the most recently written data. If not found, the search continues in the disk-based structures. This approach minimizes the time spent on searches, especially for recent data.

┌───────────────────────────┐
│       Optimized Search    │
│  ┌───────────────┐        │
│  │ Check MemTable│        │
│  └───────────────┘        │
│        │                  │
│        ▼                  │
│     Found?                │
│      │                    │
│      ├────────────┐       │
│      ▼            ▼       │
│   Yes          No         │
│  Return       Search Disk │
└───────────────────────────┘

Conclusion

LSM trees offer a compelling solution for logging systems that require efficient write performance and optimized search capabilities. Their ability to handle large volumes of write operations with reduced write amplification makes them a preferred choice over B+ trees in NoSQL implementations.

As logging systems continue to evolve and generate vast amounts of data, understanding the advantages of LSM trees will be crucial for designing robust, high-performance applications that can efficiently handle today's data challenges.

Retrieval Technique Series-2.How to Index Massive Disk Data Using B+ Trees

yang yaru — Wed, 21 May 2025 02:52:22 +0000

In today's data-driven world, the ability to efficiently store and retrieve massive amounts of information is crucial for any database system. When dealing with data that exceeds the capacity of main memory, specialized data structures become essential. Among these structures, the B+ tree stands out as one of the most powerful and widely implemented indexing mechanisms in modern database systems. This blog explores how B+ trees enable efficient retrieval of massive disk-based data.

Key Features of B+ Trees

Suitable for Range Queries

One of the most significant advantages of B+ trees is their exceptional performance for range queries. Unlike hash indexes that excel at point queries but struggle with ranges, B+ trees maintain data in sorted order, making them ideal for operations like:

SELECT * FROM customers WHERE age BETWEEN 25 AND 40;

The structure allows for efficient traversal through consecutive keys, as illustrated below:

┌─────────────────────────────────────────────────────┐
│                  Range Query Process                │
│                                                     │
│  1. Find the leaf containing the lower bound (25)   │
│  2. Scan sequentially through leaf nodes            │
│  3. Continue until reaching upper bound (40)        │
│                                                     │
└─────────────────────────────────────────────────────┘

Structure of B+ Trees

A key design of the B+ tree is to make the size of a node equal to the size of a block. The data stored within a node is not an element, but an ordered array that can hold m elements.

Internal Nodes

Internal nodes in a B+ tree serve as navigational aids, containing keys that guide the search process but don't store actual data records. Each internal node contains:

Sorted keys that define the ranges
Pointers to child nodes
A minimum fill factor (typically 50%) to ensure efficient space utilization

┌───────── Internal Node ────────┐
│                                │
│  ┌─────┐┌─────┐┌─────┐         │                   
│  │ K₁  ││ K₂  ││ K₃  │         │
│  └─────┘└─────┘└─────┘         │
│  │ P₁  ││ P₂  ││ P₃  │  ...    │
│  └─────┘└─────┘└─────┘         │
│     │                          │
│     ▼                          │
│  Pointer to                    │
│  child node                    │
│                                │
└────────────────────────────────┘

Leaf Nodes

Leaf nodes are where the actual data (or pointers to data) resides. When a B+ tree is used for database indexing, the leaf nodes typically store the key value (Key) and the location of the corresponding data record on disk (pointer). The key characteristics of leaf nodes include:

They contain the indexed keys and associated data records (or pointers to records)
All leaf nodes are at the same level, ensuring balanced tree height
Leaf nodes are linked together in a doubly-linked list, facilitating efficient range queries

                       ┌──────── Leaf Node ────────┐                      ┌──────── Leaf Node ────────┐     
                       │                           │                      │                           │      
                       │  ┌─────┐┌─────┐┌─────┐    │                      │  ┌─────┐┌─────┐┌─────┐    │     
                       │  │ K₁  ││ K₂  ││ K₃  │    │                      │  │ K₁  ││ K₂  ││ K₃  │    │     
                       │  └─────┘└─────┘└─────┘    │                      │  └─────┘└─────┘└─────┘    │    
  ... ◄──────────────► │  │ P₁  ││ P₂  ││ P₃  │... │  ◄───────────────►   │  │ P₁  ││ P₂  ││ P₃  │... │      
        Previous Leaf  │  └─────┘└─────┘└─────┘    │     Next Leaf        │  └─────┘└─────┘└─────┘    │                  
                       │     │                     │                      │     │                     │ 
                       │     ▼                     │                      │     ▼                     │   
                       │  pointers to data         │                      │  pointers to data         │       
                       └───────────────────────────┘                      └───────────────────────────┘

Search Process in B+ Trees

Starting from the Root Node

Every search operation in a B+ tree begins at the root node. The process follows these steps:

Compare the search key with the keys in the root node
Determine which child pointer to follow
Traverse down the tree until reaching a leaf node

┌────────────────────────────────────────┐
│               Root Node                │
│           ┌─────┐   ┌─────┐            │
│           │ 30  │   │ 70  │            │
│           └─────┘   └─────┘            │
│              │         │               │
└──────────────┼─────────┼───────────────┘
               ▼         ▼
┌─────────────────┐ ┌─────────────────┐ ┌─────────────────┐
│   < 30 Node     │ │  30-70 Node     │ │   > 70 Node     │
│ ┌────┐ ┌────┐   │ │ ┌────┐ ┌────┐   │ │ ┌────┐ ┌────┐   │
│ │ 10 │ │ 20 │   │ │ │ 40 │ │ 60 │   │ │ │ 80 │ │ 90 │   │
│ └────┘ └────┘   │ │ └────┘ └────┘   │ │ └────┘ └────┘   │
└─────────────────┘ └─────────────────┘ └─────────────────┘

Traversing Internal Nodes Layer by Layer

As the search progresses through the tree:

At each internal node, the algorithm compares the search key with the node's keys
It follows the appropriate pointer based on the comparison
This process continues until reaching a leaf node

Implementing Range Queries via Doubly-Linked Lists

The doubly-linked list connecting all leaf nodes is what makes B+ trees particularly efficient for range queries:

First, locate the leaf node containing the lower bound of the range
Scan sequentially through the linked list of leaf nodes
Continue until reaching the upper bound of the range

┌──────────┐   ┌──────────┐   ┌──────────┐   ┌──────────┐
│ Leaf 1   │◄─►│ Leaf 2   │◄─►│ Leaf 3   │◄─►│ Leaf 4   │
│ Keys:    │   │ Keys:    │   │ Keys:    │   │ Keys:    │
│ 10,15,20 │   │ 25,30,35 │   │ 40,45,50 │   │ 55,60,65 │
└──────────┘   └──────────┘   └──────────┘   └──────────┘
                    ▲               ▲
                    │               │
                    └───────────────┘
                    Range query from
                      30 to 45

Dynamic Adjustments in B+ Trees(A node has 4 elements)

Inserting Data

When inserting new data into a B+ tree:

Locate the appropriate leaf node
Insert the key in sorted order
If the node overflows (exceeds maximum capacity):
- Split the node into two
- Promote the middle key to the parent
- Adjust pointers accordingly

Before insertion of 45:
┌───────────────┐
│    Node A     │
│ 30, 40, 50, 60│
└───────────────┘

After insertion and split:
        ┌─────┐
        │ 45  │  ← Promoted to parent
        └─────┘
         /   \
        /     \
┌───────────┐ ┌───────────┐
│  Node A   │ │  Node B   │
│ 30, 40    │ │ 45, 50, 60│
└───────────┘ └───────────┘

Deleting Data

The deletion process involves:

Finding the key to be deleted
Removing it from the leaf node
If the node becomes underfilled:
- Borrow keys from siblings if possible
- Merge with siblings if necessary
- Adjust parent nodes accordingly

Before deletion of 40:
┌───────────┐ ┌───────────┐
│  Node A   │ │  Node B   │
│ 30, 40    │ │ 45, 50, 60│
└───────────┘ └───────────┘
      Parent key: 45

After deletion and potential merge:
┌─────────────────┐
│     Node AB     │
│ 30, 45, 50, 60  │
└─────────────────┘

Advantages of B+ Trees

Suitable for Large-Scale Data

B+ trees are specifically designed to handle data that doesn't fit in memory:

The tree structure minimizes disk I/O operations
The height of the tree grows logarithmically with the number of records
Even with millions or billions of records, a B+ tree typically has a height of 3-4 levels

┌────────────────────────────────────────────────┐
│        B+ Tree Performance Characteristics     │
├────────────────────────┬───────────────────────┤
│ Number of Records      │ Typical Tree Height   │
├────────────────────────┼───────────────────────┤
│ 1,000                  │ 2                     │
│ 1,000,000              │ 3                     │
│ 1,000,000,000          │ 4                     │
└────────────────────────┴───────────────────────┘

Index Data Stored on Disk

B+ trees are optimized for disk-based storage:

Node size is aligned with disk block size (typically 4KB to 16KB)
This alignment minimizes the number of disk I/O operations
Internal nodes are often cached in memory for faster access

┌───────────────────────────────────────────────────┐
│              Disk-Based B+ Tree                   │
│                                                   │
│  ┌─────────┐                                      │
│  │ Memory  │  Root and frequently accessed nodes  │
│  │ Cache   │  kept in memory                      │
│  └─────────┘                                      │
│        │                                          │
│        ▼                                          │
│  ┌─────────┐                                      │
│  │  Disk   │  Most nodes stored on disk,          │
│  │ Storage │  loaded as needed                    │
│  └─────────┘                                      │
│                                                   │
└───────────────────────────────────────────────────┘

Design Philosophy

Separation of Index and Data

A key design principle of B+ trees is the separation of indexing structure from the actual data:

Leaf nodes contain either the full data records or pointers to them
This separation allows for more efficient use of cache memory
It also enables different organizations of the data itself

┌───────────────────────────────────────────────────┐
│           Index and Data Separation               │
│                                                   │
│  ┌─────────────────┐                              │
│  │   B+ Tree Index │                              │
│  │   Structure     │                              │
│  └────────┬────────┘                              │
│           │                                       │
│           │ References                            │
│           ▼                                       │
│  ┌─────────────────┐                              │
│  │   Actual Data   │                              │
│  │   Records       │                              │
│  └─────────────────┘                              │
│                                                   │
└───────────────────────────────────────────────────┘

Practical Implementation

To better understand how B+ trees work in practice, let's consider simplified implementations in Java and Go:

Java Implementation

import java.util.ArrayList;
import java.util.List;
import java.util.AbstractMap.SimpleEntry;

public class BPlusTree<K extends Comparable<K>, V> {
    private Node<K, V> root;
    private final int maxKeys;

    public BPlusTree(int maxKeys) {
        this.root = new LeafNode<>(maxKeys);
        this.maxKeys = maxKeys;
    }

    public V search(K key) {
        return root.search(key);
    }

    public List<SimpleEntry<K, V>> rangeQuery(K startKey, K endKey) {
        List<SimpleEntry<K, V>> result = new ArrayList<>();

        // Find leaf node containing the start key
        LeafNode<K, V> node = findLeafNode(root, startKey);

        // Collect all keys in range by following leaf pointers
        while (node != null) {
            for (int i = 0; i < node.keys.size(); i++) {
                K key = node.keys.get(i);
                if (key.compareTo(startKey) >= 0 && key.compareTo(endKey) <= 0) {
                    result.add(new SimpleEntry<>(key, node.values.get(i)));
                }
                if (key.compareTo(endKey) > 0) {
                    return result;
                }
            }
            node = node.next;
        }

        return result;
    }

    private LeafNode<K, V> findLeafNode(Node<K, V> node, K key) {
        if (node instanceof LeafNode) {
            return (LeafNode<K, V>) node;
        }

        InternalNode<K, V> internalNode = (InternalNode<K, V>) node;
        int i = 0;
        while (i < internalNode.keys.size() && key.compareTo(internalNode.keys.get(i)) >= 0) {
            i++;
        }
        return findLeafNode(internalNode.children.get(i), key);
    }

    private abstract static class Node<K extends Comparable<K>, V> {
        List<K> keys;
        int maxKeys;

        Node(int maxKeys) {
            this.keys = new ArrayList<>();
            this.maxKeys = maxKeys;
        }

        abstract V search(K key);
    }

    private static class InternalNode<K extends Comparable<K>, V> extends Node<K, V> {
        List<Node<K, V>> children;

        InternalNode(int maxKeys) {
            super(maxKeys);
            this.children = new ArrayList<>();
        }

        @Override
        V search(K key) {
            int i = 0;
            while (i < keys.size() && key.compareTo(keys.get(i)) >= 0) {
                i++;
            }
            return children.get(i).search(key);
        }
    }

    private static class LeafNode<K extends Comparable<K>, V> extends Node<K, V> {
        List<V> values;
        LeafNode<K, V> next;
        LeafNode<K, V> prev;

        LeafNode(int maxKeys) {
            super(maxKeys);
            this.values = new ArrayList<>();
        }

        @Override
        V search(K key) {
            for (int i = 0; i < keys.size(); i++) {
                if (keys.get(i).equals(key)) {
                    return values.get(i);
                }
            }
            return null;
        }
    }
}

Go Implementation

package bplustree

import (
    "fmt"
)

type KeyValuePair struct {
    Key   interface{}
    Value interface{}
}

type BPlusTreeNode struct {
    IsLeaf   bool
    Keys     []interface{}
    Children []*BPlusTreeNode
    Next     *BPlusTreeNode
    Prev     *BPlusTreeNode
    Values   []interface{}
    MaxKeys  int
}

type BPlusTree struct {
    Root    *BPlusTreeNode
    MaxKeys int
}

func NewBPlusTree(maxKeys int) *BPlusTree {
    return &BPlusTree{
        Root: &BPlusTreeNode{
            IsLeaf:  true,
            Keys:    make([]interface{}, 0),
            Values:  make([]interface{}, 0),
            MaxKeys: maxKeys,
        },
        MaxKeys: maxKeys,
    }
}

func (t *BPlusTree) Search(key interface{}) interface{} {
    return t.search(t.Root, key)
}

func (t *BPlusTree) search(node *BPlusTreeNode, key interface{}) interface{} {
    if node.IsLeaf {
        for i, k := range node.Keys {
            if compare(k, key) == 0 {
                return node.Values[i]
            }
        }
        return nil
    }

    // If not leaf, find the appropriate child
    i := 0
    for i < len(node.Keys) && compare(key, node.Keys[i]) >= 0 {
        i++
    }
    return t.search(node.Children[i], key)
}

func (t *BPlusTree) RangeQuery(startKey, endKey interface{}) []KeyValuePair {
    // Find leaf node containing the start key
    node := t.Root
    for !node.IsLeaf {
        i := 0
        for i < len(node.Keys) && compare(startKey, node.Keys[i]) >= 0 {
            i++
        }
        node = node.Children[i]
    }

    // Collect all keys in range by following leaf pointers
    result := make([]KeyValuePair, 0)
    for node != nil {
        for i, key := range node.Keys {
            if compare(key, startKey) >= 0 && compare(key, endKey) <= 0 {
                result = append(result, KeyValuePair{Key: key, Value: node.Values[i]})
            }
            if compare(key, endKey) > 0 {
                return result
            }
        }
        node = node.Next
    }

    return result
}

// Helper function to compare keys
func compare(a, b interface{}) int {
    switch a := a.(type) {
    case int:
        return a - b.(int)
    case string:
        if a < b.(string) {
            return -1
        } else if a > b.(string) {
            return 1
        }
        return 0
    default:
        panic("Unsupported type for comparison")
    }
}

Conclusion

B+ trees have become the backbone of indexing in disk-based database systems for good reasons. Their balanced structure ensures consistent performance regardless of data size, while their leaf-level linked list enables efficient range queries. The design specifically addresses the challenges of disk-based storage by minimizing I/O operations and maximizing cache utilization.

When designing database systems that must handle large volumes of data, understanding B+ trees is essential. They represent one of the most elegant solutions to the problem of efficiently retrieving data from disk-based storage systems, balancing the trade-offs between memory usage, disk access patterns, and query performance.

Whether you're developing a database system in Java, Go, or any other language, the B+ tree is a fundamental concept that demonstrates how clever algorithm design can overcome the physical limitations of storage hardware. The implementations provided above, while simplified, illustrate the core concepts that make B+ trees so valuable in database systems.

Retrieval Technique Series-1.Linear Structure Retrieval

yang yaru — Mon, 14 Apr 2025 06:02:31 +0000

Understanding the Essence of Retrieval Through Arrays and Linked Lists

In today's information explosion era, retrieval technology has become an indispensable part of our daily lives and work.Whether searching for information through search engines or retrieving records from databases, the efficiency and accuracy of retrieving records directly impact our user experience.To deeply understand complex retrieval systems, we must start with the most fundamental data structures-arrays and linked lists, the two basic linear structures.

The Essence of Retrieval

Definition of Retrieval

Retrieval is essentially the process of finding specific elements within a series of data.This seemingly simple operation is actually one of the most fundamental and important operations in computer science.From simple array traversal to complex web indexing, all implements the core functionality of "retrieval".

┌─────────────────────────────────┐
│                                 │
│         RETRIEVAL PROCESS       │
│                                 │
│  ┌─────┐     ┌─────────┐        │
│  │Input│────▶│Searching│        │
│  └─────┘     │Algorithm│        │
│              └────┬────┘        │
│                   │             │
│                   ▼             │
│              ┌─────────┐        │
│              │ Output  │        │
│              └─────────┘        │
│                                 │
└─────────────────────────────────┘

Relationship Between Retrieval Efficiency and Data Storage Methods

The way data is stored directly determines retrieval efficiency.Different data structures have different storage characteristics and therefor different retrieval performance.In linear structure,arrays and linked lists are the two most basic storage methods with fundamentally different retrival characteristics.

Storage Characteristics of Arrays and Linked Lists

Arrary Characteristics

Arrays are data structures with contiguous storage, where elements are adjacent in memory.This storage method has the following characteristics:

Strong random access capability: can directly access elements at any position through indexing, with O(1) time complexity
High memory utilization: no additional pointer overhead
Cache-friendly: contiguous memory layout benefits CPU cache utilization
However, arrays are usually fixed in size, and dynamic size adjustment requires memory reallocation

┌───────────────────────────────────────┐
│               ARRAY                   │
├───┬───┬───┬───┬───┬───┬───┬───┬───┬───┤
│ 0 │ 1 │ 2 │ 3 │ 4 │ 5 │ 6 │ 7 │ 8 │ 9 │
└───┴───┴───┴───┴───┴───┴───┴───┴───┴───┘
  ▲                   ▲               ▲
  │                   │               │
Direct access      Direct access   Direct access
   O(1)               O(1)           O(1)

Linked List Characteristics

Linked lists are non-contiguous storage data structures that connect nodes through pointers. The characteristics of linked lists include:

Dynamic memory allocation: nodes can be added or removed dynamically as needed
Efficient insertion and deletion operations: no need to move other elements, just adjust pointers
However, linked lists do not support random access; accessing a specific position requires traversal from the head

┌────────┐     ┌────────┐     ┌────────┐     ┌────────┐
│  Data  │     │  Data  │     │  Data  │     │  Data  │
│ ┌────┐ │     │ ┌────┐ │     │ ┌────┐ │     │ ┌────┐ │
│ │ 10 │ │     │ │ 20 │ │     │ │ 30 │ │     │ │ 40 │ │
│ └────┘ │     │ └────┘ │     │ └────┘ │     │ └────┘ │
│  Next  │     │  Next  │     │  Next  │     │  Next  │
│ ┌────┐ │     │ ┌────┐ │     │ ┌────┐ │     │ ┌────┐ │
│ │ ──────────▶│ ──────────▶│ ──────────▶│  NULL │ │
│ └────┘ │     │ └────┘ │     │ └────┘ │     │ └────┘ │
└────────┘     └────────┘     └────────┘     └────────┘
    Head                                         Tail

Representatives of Linear Structures

Besides arrays and linked lists, linear structures also include stacks, queues, and other data structures that store data in a linear order, each with its own characteristics and applicable scenarios.

Improving Array Retrieval Efficiency

Binary Search Algorithm

For sorted arrays, binary search is an efficient retrieval algorithm. Its basic idea is:

Divide the search interval in half
Determine which half contains the target value
Continue searching in the corresponding half-interval
Repeat the above steps until the target value is found or determined not to exist

Binary search has a time complexity of O(log n), far superior to linear search's O(n).

┌───┬───┬───┬───┬───┬───┬───┬───┬───┬───┐
│ 1 │ 3 │ 5 │ 7 │ 9 │ 11│ 13│ 15│ 17│ 19│  Search for 11
└───┴───┴───┴───┴───┴───┴───┴───┴───┴───┘
                  ▲
                  │
               mid = 9
              9 < 11, go right

┌───┬───┬───┬───┬───┐
│ 11│ 13│ 15│ 17│ 19│  Search for 11
└───┴───┴───┴───┴───┘
  ▲
  │
mid = 11
11 = 11, found!

Implementation Steps

The implementation of binary search needs to pay attention to the following points:

The array must be sorted
Boundary conditions must be handled correctly
Prevent integer overflow
Handle cases with duplicate elements

Binary Search Efficiency

The efficiency of binary search is mainly reflected in:

Time complexity: O(log n)
Space complexity: O(1) (iterative implementation) or O(log n) (recursive implementation)
For large datasets, the efficiency improvement is particularly significant

Advantages and Disadvantages of Linked Lists

Linked List Retrieval Efficiency

The retrieval efficiency of linked lists is relatively low, mainly because:

They do not support random access; traversal must start from the head node
Time complexity is O(n)
Not cache-friendly, as nodes are scattered throughout memory

┌────────┐     ┌────────┐     ┌────────┐     ┌────────┐
│  Head  │     │        │     │        │     │  Tail  │
│  Node  │────▶│  Node  │────▶│  Node  │────▶│  Node  │
└────────┘     └────────┘     └────────┘     └────────┘
    ▲
    │
  Start here and traverse sequentially
  to find any element: O(n)

Dynamic Adjustment Capability of Linked Lists

Despite low retrieval efficiency, linked lists have significant advantages in dynamic adjustment:

Time complexity for insertion and deletion operations is O(1) (assuming the position is known)
No need to pre-allocate fixed-size memory
Efficiently handle dynamically changing datasets

Flexible Modification of Linked Lists

Flexible Adjustment of Non-Contiguous Storage Space

The non-contiguous storage characteristic of linked lists allows them to flexibly adapt to various memory constraints:

Can utilize fragmented memory space
Not limited by physical memory contiguity
Suitable for use in memory-constrained environments

Examples of Modified Linked Lists

To improve the retrieval efficiency of linked lists, various modifications can be made:

Skip List: Add multiple levels of indexes to achieve average O(log n) search time
Doubly Linked List: Support bidirectional traversal, improving retrieval efficiency in specific scenarios
Circular Linked List: Suitable for scenarios requiring circular access
Hash Linked List: Combining the advantages of hash tables and linked lists

Skip List Structure:
┌───┐                                  ┌───┐
│ H │──────────────────────────────────▶ T │  Level 3
└─┬─┘                                  └───┘
  │
┌─▼─┐          ┌───┐                   ┌───┐
│ H │──────────▶ 30│───────────────────▶ T │  Level 2
└─┬─┘          └───┘                   └───┘
  │
┌─▼─┐  ┌───┐   ┌───┐   ┌───┐          ┌───┐
│ H │──▶ 10│───▶ 30│───▶ 50│──────────▶ T │  Level 1
└─┬─┘  └───┘   └───┘   └───┘          └───┘
  │
┌─▼─┐  ┌───┐   ┌───┐   ┌───┐   ┌───┐  ┌───┐
│ H │──▶ 10│───▶ 20│───▶ 30│───▶ 50│──▶ T │  Level 0
└───┘  └───┘   └───┘   └───┘   └───┘  └───┘

Key Review

Retrieval Technology and Efficiency Analysis of Linear Structures

The retrieval efficiency of linear structures mainly depends on:

Data storage method (contiguous vs. non-contiguous)
Whether the data is sorted
Choice of retrieval algorithm
Data scale

Core Ideas of Retrieval

The core ideas of retrieval technology include:

Reducing the number of comparisons
Utilizing data characteristics (such as order)
Balancing space and time
Choosing appropriate data structures for specific application scenarios

By deeply understanding the two basic linear data structures—arrays and linked lists—we can better grasp the essence of retrieval technology and lay a solid foundation for learning more complex retrieval algorithms and data structures. In practical applications, we need to choose appropriate data structures and retrieval algorithms based on specific scenarios and requirements to achieve optimal performance and user experience.

Whether traditional information retrieval systems or modern search engines, all are built on these basic principles through continuous optimization and innovation to construct more efficient and accurate retrieval systems. Therefore, mastering the retrieval principles of linear structures is our first step in understanding and applying modern retrieval technology.