Tags: databases, query-optimization, columnar-storage, cardinality-estimation, dictionary-encoding, Parquet
Cardinality estimation — predicting how many distinct values a column contains — is the first step in cost-based query optimization. Accurate NDV (number of distinct values) estimates determine join ordering, index selection, and memory allocation. Traditional approaches require scanning data or maintaining statistical sketches (HyperLogLog, Count-Min). Both cost time or space.
Columnar file formats like Apache Parquet already encode NDV information in their metadata — they just don't expose it as such (arXiv:2603.24606). Dictionary-encoded columns store a mapping from values to integer codes. The dictionary size and the column's compressed size jointly constrain the NDV. Inverting the dictionary-encoding equation — solving for the number of distinct values given the storage size — yields an NDV estimate that requires no data access, no extra storage, and no scan.
A second estimator handles sorted or partitioned data, where dictionary encoding is less informative. Each row group stores column min/max statistics. The number of distinct (min, max) pairs across row groups, combined with a coupon collector model, estimates how many distinct values the full column contains. The two estimators are complementary: the first works when values are well-spread; the second works when values are clustered.
The through-claim: columnar file formats are not just storage mechanisms — they are implicit statistical summaries. The metadata written for compression and I/O optimization already encodes distributional information that query optimizers need. Extracting this information requires no additional data structures; it requires reading the metadata that already exists differently.
Tags: databases, JSON-Schema, type-inclusion, formal-methods, normalization, witness-generation
JSON Schema defines what shapes of JSON data are valid. Schema inclusion — does every instance satisfying schema A also satisfy schema B? — is the key question for schema evolution, API compatibility, and data migration. Two approaches exist: rule-based algorithms that enumerate structural inclusion patterns (fast but incomplete — they miss valid inclusions that don't match any rule) and witness-generation algorithms that search for counterexamples (complete but slow — they explore the space of possible JSON documents).
Refutational normalization (arXiv:2603.25306) reconciles the two. The idea: normalize schemas into a canonical form that eliminates the structural complexity that makes rule-based approaches incomplete, then apply witness generation to the normalized form. The normalization expands schema constructs (allOf, oneOf, if-then-else, $ref) into a flattened representation where inclusion checking reduces to a tractable comparison. The witness generator on the normalized form is both faster and more complete than either approach alone.
The practical impact: inclusion checks on real-world JSON schemas that were previously infeasible — timing out after minutes — complete in seconds. Schema evolution tools can now automatically verify that a new schema version accepts all instances that the old version accepted.
The through-claim: the difficulty of JSON Schema inclusion is not intrinsic to the problem but to the syntactic surface of the schema language. JSON Schema's expressive constructs (combinators, conditionals, references) create the illusion of exponential complexity. Normalization strips the syntax back to the semantics, and the semantics is tractable. The schema language is harder than the schema problem.
Tags: databases, SQL, natural-language-to-SQL, LLM, template-matching, query-complexity
Large language models translate natural language to SQL by treating it as a sequence generation problem — the model generates SQL token by token, exploiting its training on millions of query-code pairs. The approach is powerful, expensive, and occasionally wrong in ways that are hard to audit. The implicit assumption: SQL queries are too complex and diverse for simpler approaches.
An empirical analysis of 376 databases (arXiv:2603.25568) challenges this assumption. SQL queries, as translations of natural language questions, are finite in practical complexity. No clear relationship exists between database size (number of tables) and query complexity. SQL templates follow a power-law distribution: 70% of tested queries are covered by just 13% of all template types. Most queries follow formulaic patterns — SELECT with WHERE, GROUP BY, JOIN, ORDER BY — in predictable combinations.
The implication: template-based approaches that match natural language patterns to SQL templates could be safer (deterministic, auditable), cheaper (no LLM inference cost), and more reliable (no hallucinated column names) for the majority of database access tasks. LLMs remain necessary for the long tail — the 30% of queries that require novel compositions — but the bulk of database interaction lives in the template-covered head.
The through-claim: the complexity of natural-language-to-SQL is concentrated in a small fraction of queries that the majority of practical use cases never encounter. LLMs solve the general problem but are overkill for the typical problem. The power-law distribution of query templates means that a template library covering 13% of patterns handles 70% of queries — and templates are deterministic, auditable, and free.
Tags: physics-education, fluid-dynamics, teapot-effect, wettability, capillary-forces, 3D-printing
The teapot effect — liquid clinging to the container's lip and running down the outside rather than separating cleanly — is a kitchen-table phenomenon with research-level physics. The interplay of fluid inertia, surface wettability, and capillary forces determines whether the liquid detaches at the lip or follows the contour of the spout.
A low-cost experiment using 3D-printed cups, a simple flow regulator, and basic surface treatments (arXiv:2603.25653) makes this accessible to introductory physics students. Students measure how far liquid runs down the outer wall — the run length — as a function of flow velocity and surface wettability. Hydrophobic coatings reduce the run length; slower flow rates increase it. The transition between clean separation and wall-following is sharp, not gradual — a qualitative change in behavior at a critical flow velocity.
The pedagogical value is in the connection between the mundane observation and the underlying physics. The teapot effect arises from the competition between inertia (which wants to carry the liquid straight past the lip) and capillary forces (which want to keep the liquid in contact with the solid surface). The critical velocity is the inertial-capillary transition — the point where the kinetic energy of the flow matches the energy cost of creating a new liquid-air interface at the lip.
The through-claim: the teapot effect is a low-cost gateway to fluid mechanics' deepest theme — the competition between inertia and surface forces. The experiment captures the same inertial-capillary physics that governs droplet formation, jet breakup, and spray dynamics, but in a setting where the measurement is “how far does the drip run?” and the apparatus costs dollars, not thousands.
Tags: computational-geometry, shortest-paths, unit-disk-graphs, geodesic-distance, polygon-algorithms, Voronoi-diagrams
Unit-disk graphs connect points that are within distance one of each other. In the Euclidean setting, shortest paths in unit-disk graphs can be computed efficiently. But when the points live inside a polygon and distance is measured geodesically — the shortest path that stays inside the polygon — the problem changes fundamentally. Geodesic distance is not a simple metric computation; it requires navigating around polygon obstacles.
The first subquadratic-time algorithms for shortest paths in geodesic unit-disk graphs (arXiv:2603.24872) achieve O(m + n log² n log² m) time for weighted simple polygons. The techniques are novel: a deletion-only geodesic range emptiness data structure, an additively weighted geodesic Voronoi diagram construction, and a dynamic structure extending Bentley's logarithmic method to support both insertion and delete-min operations.
The algorithmic challenge is that geodesic distance breaks the spatial structure that Euclidean algorithms exploit. In Euclidean unit-disk graphs, the disk-intersection property means nearby points share edges, and spatial data structures (quad-trees, grids) efficiently enumerate neighbors. In geodesic unit-disk graphs, two points close in Euclidean distance may be far in geodesic distance (separated by a polygon wall), and two points far apart may be close (connected through a narrow corridor).
The through-claim: the jump from Euclidean to geodesic distance in unit-disk graphs is not a mild generalization — it requires fundamentally different algorithmic techniques. The spatial locality that makes Euclidean problems tractable is destroyed by the polygon's geometry. The new algorithms succeed not by adapting Euclidean methods but by inventing geodesic-specific data structures that exploit the polygon's combinatorial structure rather than its metric properties.
## Essay #6758: The Skyline Sum Tags: computational-geometry, Pareto-sets, Minkowski-sums, min-plus-convolution, approximation-algorithms, fine-grained-complexity The Pareto sum of two 2D point sets is the skyline of their Minkowski sum — the set of non-dominated points in the sum. Exact computation faces conditional lower bounds: strongly subquadratic algorithms are unlikely, tied to the same hardness assumptions that constrain min-plus convolution and APSP. The approximation approach (arXiv:2603.25449) defines additively approximate Pareto sets and proves this problem is fine-grained equivalent to Bounded Monotone Min-Plus Convolution. The equivalence is bidirectional: any algorithm for one implies an algorithm for the other with matching complexity. This yields a strongly subquadratic Õ(n^{1.5})-time approximation algorithm — faster than the quadratic exact methods and provably near-optimal under standard fine-grained complexity assumptions. The practical engineering matters as much as the theory. The simplified implementation of the Chi-Duan-Xie-Zhang algorithm outperforms competing quadratic-time approaches on larger instances, providing a direct speed improvement for Pareto optimization in multi-objective settings. The through-claim: Pareto sum computation is a disguised min-plus convolution problem. The geometric language (skylines, dominance) and the algebraic language (min-plus, tropical arithmetic) describe the same computational difficulty. The fine-grained equivalence means progress on either front — geometric or algebraic — translates immediately to the other. The approximation breaks the quadratic barrier that the exact equivalence class imposes. ---