Speed up LexicalDistance.measure used for "Did you mean" suggestions

未關閉
  • 哪裡不對？
#314 0 則留言 0 個 reaction 已指派 0 人 在 GitHub 檢視

維護者通常 1 天內回覆

還沒有人認領這個 Issue。

評估

難度
3/5
預估耗時
1-2 天
新手友好度
75/100
Issue 類型
重構
描述清晰度
描述清楚
活躍度
活躍
技術堆疊
python
領域
backend-api-design, performance

研究方向

Start by locating LexicalDistance.measure() and its callers in suggestion_list(); the issue names tests/benchmarks/test_validate_invalid_gql.py as a performance benchmark. Read the current distance calculation and run that benchmark to establish a baseline. Implement the proposed prefix/suffix trimming, threshold early return, and row-buffer changes, then compare benchmark results and check that suggestion behavior remains correct.

由索引模型根據 Issue 內容生成。

描述

Problem

suggestion_list() calls LexicalDistance.measure() once for each option. When a query has a typo, validation uses this to build "Did you mean ...?" hints. On large schemas, this distance code takes most of the validation time.

The method does extra work for each option:

  • It builds the full distance table even when a shared prefix or suffix needs no edits.
  • It builds the table even when the option has more missing characters than the threshold allows.
  • It calls min() with three values in every cell, even when the two characters are equal.
  • It converts the option to a list of code points on every call.

Numbers

Python 3.12 on Linux. The Before column is the current main, and the After column is the proposed change.

Situation Before After Change
tests/benchmarks/test_validate_invalid_gql.py (median) 22.49 ms 11.42 ms 49% faster
suggestion_list, 12-char typo, 2000 random names 27.04 ms 2.69 ms 90% faster
suggestion_list, 4-char typo, 2000 random names 2.28 ms 0.61 ms 73% faster
suggestion_list, 30-char input, 2000 random names 0.70 ms 0.30 ms 58% faster
Exact or case-only matches, 2000 options 0.170 ms 0.179 ms about the same (early return, code unchanged)

Proposed fix

Skip the common prefix and suffix, and return early when too many characters are missing. In the table, copy the diagonal cell for equal characters, and rotate the row buffers.

Environment

graphql-core main (1d505c1), CPython 3.12, Linux x86_64.

主要語言
Python
星號
534
分支
159
平均合併
1 天 18 小時
30 天內合併 PR
9

環境準備

  • 沒有 Dockerfile 或 Docker Compose 檔案
  • 有 Pull Request 範本
  • 沒有貢獻指南

從這裡開始

  1. 先讀完整個 Issue，再讀專案的貢獻指南。
  2. 在 Issue 下留言說明你要接手 —— 這能避免兩個人做同樣的事。
  3. Fork 儲存庫，在一個分支上完成修改。
  4. 送出 Pull Request，並在描述裡引用這個 Issue 編號。

graphql-python/graphql-core 的其他 Issue

查看 graphql-python/graphql-core 的全部 Issue

相似的 Issue

更多 Python Issue

把新 issue 寄到你的電子郵件信箱

精選適合新手參與的 GitHub issue 摘要。