Predicate Comparison and Merging Utilities for Predicate Push-Down #668
Mergedsamwillis(GitHub profile, opens in a new tab)merged 28 commits into
query-driven-sync fromrefs/pull/668/headmerged by samwillis(GitHub profile, opens in a new tab) kevin-dp(GitHub profile, opens in a new tab) requested changes
@@ -0,0 +1,5 @@1+---2+"@tanstack/db": patch3+---4+5+Add predicate comparison and merging utilities (isWhereSubset, intersectWherePredicates, unionWherePredicates, and related functions) to support predicate push-down in collection sync operations, enabling efficient tracking of loaded data ranges and preventing redundant server requests. Includes performance optimizations for large primitive IN predicates (100-1250x speedup via Set-based lookups) and full support for Date objects in equality, range, and IN clause comparisons.@@ -0,0 +41,21 @@41+42+ return isWhereSubsetInternal(subset!, superset!)43+}44+45+function isWhereSubsetInternal(46+ subset: BasicExpression<boolean>,47+ superset: BasicExpression<boolean>48+): boolean {49+ // If expressions are structurally equal, subset relationship holds50+ if (areExpressionsEqual(subset, superset)) {51+ return true52+ }53+54+ // Handle subset being an AND: (A AND B) implies both A and B55+ if (subset.type === `func` && subset.name === `and`) {56+ // Special case: if superset is also AND, check if all conjuncts in superset are implied by subset57+ if (superset.type === `func` && superset.name === `and`) {58+ // For (A AND B) ⊆ (C AND D), we need every conjunct in superset to be implied by subset59+ // For each conjunct in superset, at least one conjunct in subset must be a subset of it60+ // OR the entire subset implies it61+ return superset.args.every((superArg) => {Resolvedby kevin-dp(GitHub profile, opens in a new tab)@@ -0,0 +105,21 @@105+ const supersetFunc = superset as Func106+107+ // Check if both are comparisons on the same field108+ const subsetField = extractComparisonField(subsetFunc)109+ const supersetField = extractComparisonField(supersetFunc)110+111+ if (112+ subsetField &&113+ supersetField &&114+ areRefsEqual(subsetField.ref, supersetField.ref)115+ ) {116+ return isComparisonSubset(117+ subsetFunc,118+ subsetField.value,119+ supersetFunc,120+ supersetField.value121+ )122+ }123+124+ // Handle eq vs in125+ if (subsetFunc.name === `eq` && supersetFunc.name === `in`) {@@ -0,0 +250,21 @@250+ args: simplified,251+ } as BasicExpression<boolean>252+}253+254+/**255+ * Combine multiple where predicates with OR logic (union).256+ * Returns a predicate that is satisfied when any input predicate is satisfied.257+ * Simplifies when possible (e.g., age > 10 OR age > 20 → age > 10).258+ *259+ * @example260+ * // Take least restrictive261+ * unionWherePredicates([gt(ref('age'), val(10)), gt(ref('age'), val(20))]) // age > 10262+ *263+ * @example264+ * // Combine equals into IN265+ * unionWherePredicates([eq(ref('age'), val(5)), eq(ref('age'), val(10))]) // age IN [5, 10]266+ *267+ * @param predicates - Array of where predicates to union268+ * @returns Combined predicate representing the union269+ */270+export function unionWherePredicates(@@ -0,0 +378,21 @@378+}379+380+/**381+ * Check if one limit is a subset of another.382+ * Returns true if the subset limit requirements are satisfied by the superset limit.383+ *384+ * @example385+ * isLimitSubset(10, 20) // true (requesting 10 items when 20 are available)386+ * isLimitSubset(20, 10) // false (requesting 20 items when only 10 are available)387+ * isLimitSubset(10, undefined) // true (requesting 10 items when unlimited are available)388+ *389+ * @param subset - The limit requirement to check390+ * @param superset - The limit that might satisfy the requirement391+ * @returns true if subset is satisfied by superset392+ */393+export function isLimitSubset(394+ subset: number | undefined,395+ superset: number | undefined396+): boolean {397+ // No limit requirement is always satisfied398+ if (subset === undefined) {@@ -0,0 +458,21 @@458+ .filter((w): w is BasicExpression<boolean> => w !== undefined)459+460+ const mergedWhere =461+ whereClauses.length > 0 ? intersectWherePredicates(whereClauses) : undefined462+463+ // Use first non-empty orderBy (they should be compatible if predicates are related)464+ const mergedOrderBy = predicates.find(465+ (p) => p.orderBy && p.orderBy.length > 0466+ )?.orderBy467+468+ // Use minimum limit (most restrictive - intersection must satisfy all constraints)469+ // If any predicate is unlimited, the intersection is limited by the others470+ const limits = predicates471+ .map((p) => p.limit)472+ .filter((l): l is number => l !== undefined)473+ const mergedLimit =474+ limits.length === 0475+ ? undefined // All unlimited = result unlimited476+ : Math.min(...limits) // Take most restrictive477+478+ return {@@ -0,0 +471,21 @@471+ .map((p) => p.limit)472+ .filter((l): l is number => l !== undefined)473+ const mergedLimit =474+ limits.length === 0475+ ? undefined // All unlimited = result unlimited476+ : Math.min(...limits) // Take most restrictive477+478+ return {479+ where: mergedWhere,480+ orderBy: mergedOrderBy,481+ limit: mergedLimit,482+ }483+}484+485+/**486+ * Merge multiple predicates by unioning their where clauses.487+ *488+ * @param predicates - Array of predicates to merge489+ * @returns Combined predicate490+ */491+export function unionPredicates(- packages/db/src/query/subset-dedupe.ts line 16@@ -0,0 +1,15 @@1+import {2+ isPredicateSubset,3+ isWhereSubset,4+ unionWherePredicates,5+} from "./predicate-utils.js"6+import type { BasicExpression } from "./ir.js"7+import type { LoadSubsetOptions } from "../types.js"8+9+/**10+ * Deduplicated wrapper for a loadSubset function.11+ * Tracks what data has been loaded and avoids redundant calls by applying12+ * subset logic to predicates.13+ *14+ * @example15+ * const dedupe = new DeduplicatedLoadSubset(myLoadSubset)
kevin-dp(GitHub profile, opens in a new tab) approved these changes
samwillis(GitHub profile, opens in a new tab) closed this
Sign in to join this conversation.
🦋 Changeset detected#
Latest commit: 6ee696c7712a713e87568adc5cc49707afb16658
The changes in this PR will be included in the next version bump.
This PR includes changesets to release 12 packages
Not sure what this means? Click here to learn what changesets are.
Click here if you're a maintainer who wants to add another changeset to this PR