Home Writing 2025年2月6日 数据查询的原则性方法

本地优先 Web 应用的兴起，要求我们重新思考传统的客户端-服务器架构。用户期望接近原生应用的响应速度，即使在离线状态下也是如此。 这就要求高效的客户端数据处理，包括搜索。 本文介绍的技术，虽然是在本地优先的背景下讨论的，但也同样适用于服务器端系统。我们将探索一种类型驱动的方法，利用领域特定语言 (DSL)，来创建一个强大且可维护的搜索系统。

本文完整的、无依赖的代码可以在 GitHub 上找到。

领域特定语言 (DSL)

我们的方法围绕一个 DSL 展开，该 DSL 专门用于搜索 “issues”，这是项目管理和 bug 跟踪中常见的概念。 DSL 提供了一种专门的语言来表达搜索意图，具有几个关键优势。 考虑以下示例查询：

一个设计良好的 Domain-Specific Language (DSL) 的表达性和清晰性在许多成功的系统中都很明显。 例如，Lucene/Elasticsearch 使用查询字符串 DSL 进行全文搜索。 SQL 使用其 WHERE 子句作为 DSL 来过滤数据，而 GraphQL 定义了一种查询语言，用于从 API 获取数据。 读者可能会注意到所提出的 DSL 与 GitHub 在其 issue 搜索功能中使用的 DSL 相似。

使用 DSL 的好处是多方面的。 它通过限制可能的查询范围来提供可控的复杂性，并通过在词汇表中反映领域的概念来确保领域对齐。 反过来，这提高了可用性，允许用户使用熟悉的术语进行查询。 此外，形式语法简化了可维护性和可扩展性，使修改和扩展更容易管理。

定义领域

数据集的结构通常是从所建模的业务领域的约束推断出来的。 在这种情况下，我们选择了一个 issue 跟踪系统，因此我们将使用的基本值由 Issue 接口表示。

type IssueStatus = "open" | "closed";
type IssueType = "bug" | "feature" | "docs" | "enhancement";
interface Issue {
 id: string;
 title: string;
 status: IssueStatus;
 author: string;
 labels: string[];
 milestone: string | null;
 assignee: string | null;
 type: IssueType;
 updatedAt: number;
}

这只是一个例子。 同样的原则可以应用于许多其他领域：文档管理、客户关系管理、产品列表、应用程序日志等。

错误处理

在我们深入解析之前，我们需要一种强大的方法来处理潜在的错误。 Either 类型是函数式编程的基石，它提供了这种机制。 它用于表示一个值，该值可以是应用操作的 “成功” (Right case) 或 “失败” (Left case)。

type Either<L, R> = Left<L> | Right<R>;
class Left<L> {
 constructor(readonly value: L) {}
 isLeft(): this is Left<L> {
  return true;
 }
 isRight(): this is Right<never> {
  return false;
 }
}
class Right<R> {
 constructor(readonly value: R) {}
 isLeft(): this is Left<never> {
  return false;
 }
 isRight(): this is Right<R> {
  return true;
 }
}
const success = <T>(value: T) => new Right(value);
const failure = <E>(error: E) => new Left(error);

在整个程序中，我们将使用 Either 来传播结果。 如果解析步骤成功，它将返回一个 Right，其中包含已解析的值和剩余的输入。 如果失败，它将返回一个 Left，其中包含一个错误对象。 这种显式的错误处理对于构建可靠的系统至关重要。

精确解析

为了处理查询，我们使用 parser combinators。 它们是函数式编程中一种强大的技术，通常用于编译器设计，用于以模块化、可组合和声明式的方式构建解析器。

本质上，parser combinator 是一个高阶函数：它接受一个或多个解析器作为输入，并返回一个 新的 解析器。 每个解析器都尝试匹配输入字符串的一部分。 如果成功，它将返回一个 Right，其中包含已解析的值和剩余的输入字符串。 如果失败，它将返回一个 Left，并带有错误。

type ParserError = {
 code:
  | "INVALID_TOKEN"
  | "MISSING_VALUE"
  | "INVALID_STATUS"
  | "INVALID_TYPE"
  | "INVALID_TIME_FILTER";
 message: string;
 position: number;
 input: string;
};
type ParserResult<T> = Either<ParserError, [T, string]>;
type Parser<T> = (input: string) => ParserResult<T>;

此实现使用几个基本 combinators。

/** Matches a literal string. */
const lit = (match: string): Parser<string> => (input) => { ... };
/** Parses a sequence of alphanumeric characters. */
const word = (): Parser<string> => (input: string) => { ... };
/**
 * Tries multiple parsers in sequence, returning the result of the first one that succeeds.
 * This allows for choices in the grammar (e.g., `is:open` OR `is:closed`).
 */
const alt = <T>(...parsers: Parser<T>[]): Parser<T> => (input) => { ... };
/**
 * Applies multiple parsers sequentially, succeeding only if *all* of them succeed.
 * This is used to build up complex structures from simpler parts (e.g., `is:` followed by `open`).
 */
const seq = <T extends unknown[]>(...parsers: { [K in keyof T]: Parser<T[K]> }): Parser<T> => (input) => { ... };
/** Applies a parser zero or more times, collecting the results into an array. */
const many = <T>(parser: Parser<T>): Parser<T[]> => (input: string) => { ... };
/** Transforms the result of a successful parse using a provided function. Required to build the AST. */
const map = <T, U>(parser: Parser<T>, fn: (value: T) => U): Parser<U> => (input) => { ... };

我们从简单的解析器（如 lit 和 word）开始，并使用 seq、alt 和 many 等 combinators 将它们组合起来，以构建越来越复杂的解析器。 map combinator 对于将原始解析的字符串转换为更结构化的表示形式（我们的抽象语法树）非常重要。 从更简单的结构构建复杂结构的这种递归性质是函数式编程的标志。

组合非常棒。 将简单元素组合在一起所产生的意想不到的优雅令人惊叹。 在这种简单性中蕴藏着 parser combinators 的美。

结构化查询

解析器的职责不是直接执行查询，而是将输入字符串转换为抽象语法树 (AST)。 AST 是查询的结构化、分层表示，独立于其特定语法。 这种解耦至关重要，原因如下：

  1. 关注点分离： 解析（语法）与求值（语义）分离。
  2. 优化： 可以在执行之前分析和优化 AST。
  3. 灵活性： AST 可用于多种目的（例如，为不同的后端生成查询）。
type FilterNodeType =
 | "status"
 | "author"
 | "label"
 | "type"
 | "updated"
 | "and"
 | "or";
type LeafFilterNode = {
 readonly type: FilterNodeType;
 readonly value: string;
};
type FilterNode =
 | LeafFilterNode
 | {
   type: "and" | "or";
   value: FilterNode[];
  };

AST 由 FilterNode 对象组成。 叶节点 (LeafFilterNode) 表示单个过滤器（例如，status:open），而 and / or 节点表示布尔组合。

最终的 searchQueryParser 是通过组合 combinators 获得的。

const searchQueryParser: Parser<FilterNode> = map(
 many(alt(statusParser, authorParser, labelParser, typeParser, timeFilterParser, orParser)),
 (filters) => { ... }
);

各个过滤器解析器（如 statusParser）的定义如下。

const statusParser = map(
 seq(lit("is:"), alt(lit("open"), lit("closed"))),
 ([_, status]) => ({ type: "status", value: status } as const)
);

评估查询

有了 AST，我们可以将其转换为 谓词函数。

type IssuePredicate = (issue: Issue) => boolean;

我们为每种过滤器类型定义谓词构建函数，包括输入验证。

const isValidIssueStatus = (value: string): value is IssueStatus => {
 return ["open", "closed"].includes(value);
};
const matchStatus = (status: string): IssuePredicate => {
 if (isValidIssueStatus(status)) {
  return (issue) => issue.status === status;
 }
 console.error(`Invalid status: ${status}`);
 return matchNone();
};
// ... similar functions each filter type

createPredicate 函数递归地遍历 AST，创建和组合谓词。

const createPredicate = (node: FilterNode): IssuePredicate => {
 switch (node.type) {
  case "status":
   return isValidIssueStatus(node.value)
    ? matchStatus(node.value)
    : matchNone();
  // ... other cases
  case "and":
   return and(...(node.value as FilterNode[]).map(createPredicate));
  // ...
 }
};
const and =
 (...preds: IssuePredicate[]): IssuePredicate =>
 (issue) =>
  preds.every((p) => p(issue));

这种递归结构优雅地处理了将应用于数据集的复杂布尔逻辑。

查询执行

我们定义一个 executeQuery 函数来协调整个过程。

const executeQuery = (query: string, issues: Issue[]): Issue[] => {
 const parsedQuery = searchQueryParser(query);
 if (parsedQuery.isLeft()) {
  console.error(`Parse Error: ${parsedQuery.value.message}`);
  return []; // Return empty array on parse failure
 }
 const ast = parsedQuery.value[0];
 const predicate = createPredicate(ast);
 return issues.filter(predicate);
};

该函数的主体优雅地处理了解析错误，返回一个空的结果集并记录错误。 在生产系统中，此错误可以记录下来，并通过各种机制浮出水面，具体取决于上下文。

前进的道路

有人可能会说，其他解决方案可能更适合大型数据集。 例如，IndexedDB 或 SQLite 可用于数据存储和查询。 然而，这并不能否定本文介绍的技术的价值。 数据库解决方案可以用作存储层，而本文描述的方法可以用于从系统的输入构建查询。

考虑到这一点，我们应该检查此系统的性能并探索潜在的改进。 使用链接代码中提供的 helper utilities，进行了初步的性能评估。 以下结果是在测试机器上使用模拟的 100 万条 issue 的数据集获得的。

Search Results for: "is:open"
----------------------------------------
Matching issues: 499344
Search time: 20.77ms
Search Results for: "is:closed"
----------------------------------------
Matching issues: 500656
Search time: 20.06ms
Search Results for: "is:open label:bug"
----------------------------------------
Matching issues: 210988
Search time: 76.44ms
Search Results for: "author:alice type:feature"
----------------------------------------
Matching issues: 63052
Search time: 67.80ms
Search Results for: "label:documentation type:docs"
----------------------------------------
Matching issues: 105336
Search time: 52.06ms
Search Results for: "is:open (author:charlie author:alice) label:enhancement"
----------------------------------------
Matching issues: 105326
Search time: 81.30ms

这些结果表明，该系统可以处理相当数量的记录并以可接受的性能执行查询。 但是，重要的是要认识到当前的实现依赖于线性扫描。

因此，对于处理内在或外加约束的实际应用程序，索引对于保持可接受的性能至关重要。 对于文本字段（例如 title），一种常见的选择是倒排索引，它将单词映射到包含它们的 issue 的 ID。 对于其他字段，更简单的基于映射的索引可能就足够了。

除了索引之外，还可以应用其他几种优化：

这些优化可以为扩展系统以处理大量数据和复杂查询提供前进的道路，并且它们的实现留给读者作为练习。

结论

本文详细介绍了一种查询数据的原则性方法：一个基于类型安全、函数式编程和清晰的关注点分离的综合系统。 我们利用 TypeScript、parser combinators 和 AST 创建了一个搜索 DSL，它不仅功能强大，而且健壮、可维护和可扩展。

值得一提的是，Either 类型是 monad 的一个例子，monad 是函数式编程中的一个基本概念。 Monad 提供了一种构建涉及排序操作和处理潜在故障或副作用的计算的方法。 虽然深入研究 monad 理论超出了本文的范围，但认识到这种联系可以为更深入地理解函数式编程原则打开大门，甚至可以降低进入的门槛。

本文介绍的技术为构建高级搜索功能奠定了坚实的基础，适用于本地优先的 Web 应用程序和大型服务器端系统。 通过采用本方法中概述的原则，开发人员可以设计出既强大又用户友好的搜索体验。

参考和进一步阅读

© 2025 | Claudiu Iv