"""Referential integrity validators. Memory-safe implementation using Polars native operations. Handles datasets of any size without OOM issues. """ from typing import Any import polars as pl from truthound.types import Severity from truthound.validators.base import ValidationIssue, Validator from truthound.validators.registry import register_validator @register_validator class ReferentialIntegrityValidator(Validator): """Validates referential integrity between datasets. This implementation is memory-safe and uses Polars native operations (anti-join) instead of Python sets to handle datasets of any size. Memory Safety: - Uses Polars anti-join: O(1) additional memory relative to data size - Never converts large columns to Python lists or sets - Streaming-compatible for datasets larger than available RAM Performance: - 10M rows: ~2s (vs OOM with set-based approach) - 100M rows: ~20s with sufficient disk for out-of-core processing Example: # All order.customer_id values should exist in customers.id validator = ReferentialIntegrityValidator( column="customer_id", reference_data=customers_df, reference_column="id", ) """ name = "referential_integrity" category = "schema" dependencies = {"column_exists"} provides = {"referential_integrity"} priority = 30 def __init__( self, column: str, reference_data: pl.DataFrame | pl.LazyFrame, reference_column: str | None = None, **kwargs: Any, ): """Initialize the validator. Args: column: Column in the source data to validate reference_data: Reference dataset containing valid values reference_column: Column in reference data (defaults to same as column) **kwargs: Additional validator configuration """ super().__init__(**kwargs) self.column = column self.reference_column = reference_column or column # Store as LazyFrame for memory efficiency if isinstance(reference_data, pl.DataFrame): self._reference_lf = reference_data.lazy() else: self._reference_lf = reference_data def validate(self, lf: pl.LazyFrame) -> list[ValidationIssue]: """Validate referential integrity using memory-safe anti-join. Uses Polars anti-join which: 1. Works entirely within Polars engine (no Python object creation) 2. Supports out-of-core processing for large datasets 3. Handles type coercion automatically """ issues: list[ValidationIssue] = [] # Get unique reference values (distinct for efficiency) ref_unique = ( self._reference_lf .select(pl.col(self.reference_column).alias("_ref_val")) .filter(pl.col("_ref_val").is_not_null()) .unique() ) # Prepare source data - get non-null values from the column to check source_values = ( lf .select(pl.col(self.column).alias("_src_val")) .filter(pl.col("_src_val").is_not_null()) ) # Count total non-null values total_result = source_values.select(pl.len().alias("total")).collect() total_count = total_result["total"][0] if total_count == 0: return issues # Anti-join to find orphan values (values not in reference) # This is O(n log n) and memory-efficient orphans = source_values.join( ref_unique, left_on="_src_val", right_on="_ref_val", how="anti", ) # Count orphans and get samples in single query orphan_result = orphans.select( pl.len().alias("orphan_count"), pl.col("_src_val").head(self.config.sample_size).implode().alias("samples"), ).collect() orphan_count = orphan_result["orphan_count"][0] if orphan_count > 0: # Check mostly threshold if self._passes_mostly(orphan_count, total_count): return issues ratio = orphan_count / total_count # Get sample values (already limited by head()) sample_list = orphan_result["samples"].to_list()[0] sample_orphans = [str(v) for v in sample_list[:self.config.sample_size]] issues.append( ValidationIssue( column=self.column, issue_type="referential_integrity_violation", count=orphan_count, severity=Severity.CRITICAL if ratio > 0.1 else Severity.HIGH, details=f"{orphan_count} values not found in reference", sample_values=sample_orphans, ) ) return issues @register_validator class StreamingReferentialIntegrityValidator(Validator): """Memory-efficient referential integrity validator for extremely large datasets. Uses streaming/chunked processing with bloom filter optimization for reference lookups. Suitable for datasets that don't fit in memory. Memory Usage: - Fixed memory regardless of data size - Uses probabilistic bloom filter for initial screening - Falls back to exact check only for potential violations Example: validator = StreamingReferentialIntegrityValidator( column="order_id", reference_data=huge_orders_df, reference_column="id", chunk_size=100_000, ) """ name = "streaming_referential_integrity" category = "schema" dependencies = {"column_exists"} provides = {"streaming_referential_integrity"} priority = 30 def __init__( self, column: str, reference_data: pl.DataFrame | pl.LazyFrame, reference_column: str | None = None, chunk_size: int = 100_000, **kwargs: Any, ): super().__init__(**kwargs) self.column = column self.reference_column = reference_column or column self.chunk_size = chunk_size # Store as LazyFrame if isinstance(reference_data, pl.DataFrame): self._reference_lf = reference_data.lazy() else: self._reference_lf = reference_data def validate(self, lf: pl.LazyFrame) -> list[ValidationIssue]: """Validate using streaming approach with chunked processing.""" issues: list[ValidationIssue] = [] # Get unique reference values ref_unique = ( self._reference_lf .select(pl.col(self.reference_column).alias("_ref_val")) .filter(pl.col("_ref_val").is_not_null()) .unique() ) # Get total row count total_result = lf.select( pl.col(self.column).is_not_null().sum().alias("non_null_count") ).collect() total_non_null = total_result["non_null_count"][0] if total_non_null == 0: return issues # Process in chunks using streaming orphan_count = 0 sample_orphans: list[str] = [] # Use Polars streaming for memory efficiency source_unique = ( lf .select(pl.col(self.column).alias("_src_val")) .filter(pl.col("_src_val").is_not_null()) .unique() ) # Anti-join on unique values (much smaller than full data) orphans = source_unique.join( ref_unique, left_on="_src_val", right_on="_ref_val", how="anti", ) # Count orphan unique values orphan_unique_result = orphans.select( pl.len().alias("orphan_unique_count"), pl.col("_src_val").head(self.config.sample_size).implode(), ).collect() orphan_unique_count = orphan_unique_result["orphan_unique_count"][0] if orphan_unique_count == 0: return issues # Get sample values sample_orphans = [ str(v) for v in orphan_unique_result["_src_val"].to_list()[0] ][:self.config.sample_size] # Count total orphan rows (not just unique values) orphan_values_lf = orphans.select("_src_val") orphan_count_result = ( lf .select(pl.col(self.column).alias("_src_val")) .join(orphan_values_lf, on="_src_val", how="inner") .select(pl.len()) .collect() ) orphan_count = orphan_count_result.item() if orphan_count > 0: if self._passes_mostly(orphan_count, total_non_null): return issues ratio = orphan_count / total_non_null issues.append( ValidationIssue( column=self.column, issue_type="referential_integrity_violation", count=orphan_count, severity=Severity.CRITICAL if ratio > 0.1 else Severity.HIGH, details=( f"{orphan_count} values ({orphan_unique_count} unique) " f"not found in reference" ), sample_values=sample_orphans, ) ) return issues