Implementation:Duckdb Duckdb PCG Random

Knowledge Sources	Duckdb_Duckdb PCG Random
Domains	Random_Number_Generation, Third_Party
Last Updated	2026-02-07 12:00 GMT

Overview

PCG (Permuted Congruential Generator) is a family of random number generators by Melissa O'Neill that provides statistically excellent, fast, and space-efficient pseudorandom number generation with multiple stream variants, used by DuckDB for internal randomization needs.

Description

The PCG library is a header-only C++ implementation consisting of three files:

• pcg_random.hpp -- The main file defining the PCG engine templates and all standard typedefs. It implements several members of the PCG family corresponding to different output functions (XSH RR, XSH RS, XSL RR, RXS M XS, XSL RR RR) with four stream techniques (MCG, one-stream LCG, settable-stream LCG, unique-stream LCG). The library provides convenience typedefs such as:
  • pcg32 -- 32-bit output, 64-bit state, XSH RR output function, settable stream
  • pcg64 -- 64-bit output, 128-bit state, XSL RR output function, settable stream
  • pcg32_fast -- 32-bit output using MCG (no stream), faster but less flexible
  • Extended generators (pcg32_k2, pcg32_k64, pcg64_k32, etc.) with larger state for k-dimensional equidistribution

• pcg_extras.hpp -- Support code including 128-bit integer support for platforms lacking native __uint128_t, bit-twiddling operations, I/O helpers for 128-bit and 8-bit integers, SeedSeq handling, and bounded random number generation.

• pcg_uint128.hpp -- A portable 128-bit unsigned integer class for 32-bit platforms or compilers without native 128-bit integer support.

All PCG generators are fully compatible with C++11's <random> interface, supporting seed(), operator(), min(), max(), discard(), and stream I/O.

Usage

DuckDB uses PCG for random number generation in sampling operators (e.g., TABLESAMPLE, USING SAMPLE), hash-based algorithms that require randomization, and reservoir sampling. PCG is preferred over the standard library's Mersenne Twister because it is faster, uses less state (8--16 bytes vs. 2.5 KB), and has better statistical properties.

Code Reference

Source Location

• Repository: Duckdb_Duckdb
• Files:
  • third_party/pcg/pcg_random.hpp
  • third_party/pcg/pcg_extras.hpp
  • third_party/pcg/pcg_uint128.hpp

Signature

// Common convenience typedefs (from pcg_random.hpp):

// Standard generators
typedef pcg_engines::setseq_xsh_rr_64_32    pcg32;       // 32-bit output, settable stream
typedef pcg_engines::setseq_xsl_rr_128_64   pcg64;       // 64-bit output, settable stream

// Fast (MCG) generators
typedef pcg_engines::mcg_xsh_rs_64_32       pcg32_fast;  // 32-bit output, no stream
typedef pcg_engines::mcg_xsl_rr_128_64      pcg64_fast;  // 64-bit output, no stream

// One-stream generators
typedef pcg_engines::oneseq_xsh_rr_64_32    pcg32_oneseq;
typedef pcg_engines::oneseq_xsl_rr_128_64   pcg64_oneseq;

// Extended generators (k-dimensional equidistribution)
typedef pcg_engines::ext_setseq_xsh_rr_64_32<1,16,true>   pcg32_k2;
typedef pcg_engines::ext_setseq_xsh_rr_64_32<6,16,true>   pcg32_k64;
typedef pcg_engines::ext_setseq_xsl_rr_128_64<5,16,true>  pcg64_k32;

// All generators conform to the C++11 RandomNumberEngine concept:
//   result_type operator()();
//   void seed(state_type seed_val);
//   void seed(state_type seed_val, state_type stream_val);
//   static constexpr result_type min();
//   static constexpr result_type max();
//   void discard(state_type count);

Import

#include "pcg/pcg_random.hpp"

I/O Contract

Inputs

Name	Type	Required	Description
seed_val	state_type (uint64_t for pcg32)	No	Initial seed value; generator has a default seed if not provided
stream_val	state_type	No	Stream selector for settable-stream variants; different streams produce independent sequences

Outputs

Name	Type	Description
return (operator())	result_type (uint32_t for pcg32, uint64_t for pcg64)	Next pseudorandom number in the sequence
min()	result_type	Minimum possible output value (0)
max()	result_type	Maximum possible output value (2^bits - 1)

Usage Examples

#include "pcg/pcg_random.hpp"

// Create a 32-bit PCG generator with a specific seed and stream
pcg32 rng(42u, 54u);

// Generate random numbers
uint32_t val = rng();

// Generate a bounded random number in [0, bound)
uint32_t bounded = rng() % 100;

// Seed with new values
rng.seed(12345u, 67890u);

// Use with standard library distributions
#include <random>
std::uniform_int_distribution<int> dist(1, 6);
int die_roll = dist(rng);

// 64-bit generator
pcg64 rng64(42u, 54u);
uint64_t val64 = rng64();

Related Pages

• Principle:Duckdb_Duckdb_Random_Number_Generation