Title: Speed up LexicalDistance.measure used for "Did you mean" suggestions · Issue #314 · graphql-python/graphql-core · GitHub
Open Graph Title: Speed up LexicalDistance.measure used for "Did you mean" suggestions · Issue #314 · graphql-python/graphql-core
X Title: Speed up LexicalDistance.measure used for "Did you mean" suggestions · Issue #314 · graphql-python/graphql-core
Description: 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...
Open Graph Description: 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 cod...
X Description: 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 di...
Opengraph URL: https://github.com/graphql-python/graphql-core/issues/314
X: @github
Domain: github.com
{"@context":"https://schema.org","@type":"DiscussionForumPosting","headline":"Speed up LexicalDistance.measure used for \"Did you mean\" suggestions","articleBody":"## Problem\n\n`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.\n\nThe method does extra work for each option:\n\n- It builds the full distance table even when a shared prefix or suffix needs no edits.\n- It builds the table even when the option has more missing characters than the threshold allows.\n- It calls `min()` with three values in every cell, even when the two characters are equal.\n- It converts the option to a list of code points on every call.\n\n## Numbers\n\nPython 3.12 on Linux. The Before column is the current `main`, and the After column is the proposed change.\n\n| Situation | Before | After | Change |\n| --- | --- | --- | --- |\n| `tests/benchmarks/test_validate_invalid_gql.py` (median) | 22.49 ms | 11.42 ms | 49% faster |\n| `suggestion_list`, 12-char typo, 2000 random names | 27.04 ms | 2.69 ms | 90% faster |\n| `suggestion_list`, 4-char typo, 2000 random names | 2.28 ms | 0.61 ms | 73% faster |\n| `suggestion_list`, 30-char input, 2000 random names | 0.70 ms | 0.30 ms | 58% faster |\n| Exact or case-only matches, 2000 options | 0.170 ms | 0.179 ms | about the same (early return, code unchanged) |\n\n## Proposed fix\n\nSkip 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.\n\n## Environment\n\ngraphql-core `main` (1d505c1), CPython 3.12, Linux x86_64.\n","author":{"url":"https://github.com/dexhunter","@type":"Person","name":"dexhunter"},"datePublished":"2026-11-08T04:26:22Z","url":"https://github.com/graphql-python/graphql-core/issues/314"}
| react-profiling | 0 |
| react-import-map | react,react-dom,react-dom/client,react-dom/profiling,react-is,react/compiler-runtime,react/jsx-dev-runtime,react/jsx-runtime,scheduler@b8488ee2c322 |
| route-pattern | /_view_fragments/issues/show/:user_id/:repository/:id/issue_layout(.:format) |
| route-controller | voltron_issues_fragments |
| route-action | issue_layout |
| fetch-nonce | v2:e2c4ef07-f70f-b93a-cc70-a15bc7f351f8 |
| current-catalog-service-hash | 81bb79d38c15960b92d99bca9288a9108c7a47b18f2423d0f6438c5b7bcd2114 |
| request-id | A624:18E7F5:1071942:158AC0D:6B00067C |
| html-safe-nonce | a518f2a12a1a31c0c507f5398e1ce93a215163266a9c2e9eb1c2c382fe8cf0f0 |
| visitor-payload | eyJyZWZlcnJlciI6IiIsInJlcXVlc3RfaWQiOiJBNjI0OjE4RTdGNToxMDcxOTQyOjE1OEFDMEQ6NkIwMDA2N0MiLCJ2aXNpdG9yX2lkIjoiOTE5MTMyOTQ1MjMxODAwMDc2NCIsInJlZ2lvbl9lZGdlIjoiaWFkIiwicmVnaW9uX3JlbmRlciI6ImlhZCJ9 |
| visitor-hmac | e7ff6b016b86f253818ab81c6e1f27f0f7c934f27398a2ed7f89bca0d2fe73cc |
| hovercard-subject-tag | issue:6267565988 |
| github-keyboard-shortcuts | repository,issues,copilot |
| google-site-verification | Apib7-x98H0j5cPqHWwSMm6dNU4GmODRoqxLiDzdx9I |
| octolytics-url | https://collector.github.com/github/collect |
| analytics-location | / |
| fb:app_id | 1401488693436528 |
| apple-itunes-app | app-id=1477376905, app-argument=https://github.com/_view_fragments/issues/show/graphql-python/graphql-core/314/issue_layout |
| twitter:image | https://opengraph.githubassets.com/f2af4503e1dd57fa3857fe9f6396d695d73c31021ccab38721789d714207816a/graphql-python/graphql-core/issues/314 |
| twitter:card | summary_large_image |
| og:image | https://opengraph.githubassets.com/f2af4503e1dd57fa3857fe9f6396d695d73c31021ccab38721789d714207816a/graphql-python/graphql-core/issues/314 |
| og:image:alt | 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 cod... |
| og:image:width | 1200 |
| og:image:height | 600 |
| og:site_name | GitHub |
| og:type | object |
| og:author:username | dexhunter |
| hostname | github.com |
| expected-hostname | github.com |
| None | 0a0d8686a27478df474dd7415776a7a080cde8838b3cd92ea7601187572e5729 |
| turbo-cache-control | no-preview |
| go-import | github.com/graphql-python/graphql-core git https://github.com/graphql-python/graphql-core.git |
| octolytics-dimension-user_id | 15002022 |
| octolytics-dimension-user_login | graphql-python |
| octolytics-dimension-repository_id | 143207933 |
| octolytics-dimension-repository_nwo | graphql-python/graphql-core |
| octolytics-dimension-repository_public | true |
| octolytics-dimension-repository_is_fork | false |
| octolytics-dimension-repository_network_root_id | 143207933 |
| octolytics-dimension-repository_network_root_nwo | graphql-python/graphql-core |
| turbo-body-classes | logged-out env-production page-responsive |
| disable-turbo | false |
| browser-stats-url | https://api.github.com/_private/browser/stats |
| browser-errors-url | https://api.github.com/_private/browser/errors |
| release | 16a11879678aaf97e2a42c33ee70830aa084fa37 |
| ui-target | full |
| theme-color | #1e2327 |
| color-scheme | light dark |
| react-app-name | issues |
Links:
Viewport: width=device-width