{"id":572,"date":"2011-01-03T14:24:00","date_gmt":"2011-01-03T14:24:00","guid":{"rendered":"\/blogs\/bobb\/post\/The-nearest-neighbor-optimization-in-SQL-Server-Denali.aspx"},"modified":"2013-01-03T23:59:34","modified_gmt":"2013-01-04T07:59:34","slug":"the-nearest-neighbor-optimization-in-sql-server-denali","status":"publish","type":"post","link":"https:\/\/www.sqlskills.com\/blogs\/bobb\/the-nearest-neighbor-optimization-in-sql-server-denali\/","title":{"rendered":"The nearest neighbor optimization in SQL Server Denali"},"content":{"rendered":"<p>\nThe nearest neighbor query is one of the most common queries against spatial data. How many people haven&#39;t gone to a mapping app, typed in their current location and asked for the 10 nearest [your favorite thing goes here]? The obvious way to phrase the spatial query for this, given an STDistance method on the SqlGeometry data type, would be:\n<\/p>\n<p>\nDECLARE @me = &#39;POINT (-121.626 47.8315)&#39;<br \/>\nSELECT TOP(10) Location, Description, Location.STDistance(@me) AS distance<br \/>\nFROM [spatial_table] <br \/>\nORDER BY distance\n<\/p>\n<p>\nUnfortunately (for your performance, it does return the correct answer) in SQL Server 2008\/R2, this query doesn&#39;t use the spatial index. And attempting to hint the spatial index results in the &quot;could not produce a plan with your hints&quot; error. Oh.\n<\/p>\n<p>\nIn SQL Server Denali, this just&nbsp;works. You <strong>do<\/strong> have to include a predicate that refers to STDistance, like:\n<\/p>\n<p>\n&#8230;FROM [spatial_table] <br \/>\nWHERE Location.STDistance(@me) &lt; 1000 &#8212; &#39;where-distance&#39; query<br \/>\nORDER BY distance\n<\/p>\n<p>\nbut the predicate can also be something as unintrusive (ie you don&#39;t have to commit to a max distance) as:\n<\/p>\n<p>\n&#8230;FROM [spatial_table] <br \/>\nWHERE Location.STDistance(@me) IS NOT NULL &#8212; &#39;where is not null&#39; query<br \/>\nORDER BY distance\n<\/p>\n<p>\nThis uses the spatial index without hinting. And its way faster than the 2008 version of the same query. Excellent. But&#8230;when the &quot;nearest neighbor&quot; question came up once too often in SQL Server 2008, Isaac Kunen came up with an <a href=\"http:\/\/blogs.msdn.com\/b\/isaac\/archive\/2008\/10\/23\/nearest-neighbors.aspx\" class=\"broken_link\">alternate algorithm<\/a> that uses a numbers table.&nbsp; And its quite fast, although you do have to hint the spatial index (or, let&#39;s say, I&#39;ve never got it to use the index without hinting). So how does this algorithm do against the new, automatic spatial index use plan?\n<\/p>\n<p>\nIn the simple example where I tried this out, here&#39;s the plan cost:<br \/>\nIsaac&#39;s algorithm and hint:&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; 0.517<br \/>\nDenali with WHERE and distance:&nbsp; 4.06683<br \/>\nDenali with WHERE..IS NOT NULL: 14.7\n<\/p>\n<p>\nBut the differences in query plans that involve spatial don&#39;t always seem to the &quot;revelent&quot; (the QO does sometimes underestimate the big difference using&nbsp;the spatial index will make). All the queries are subsecond, compared to 10 seconds or so when not using the index. So, any other comparison? How about I\/O or worker time?\n<\/p>\n<p>\nIssac&#39;s algorithm and hint: &nbsp; 1x worker time\/reads\/clrtime<br \/>\nDenali with wHERE and distance: 10x worker time\/reads\/clrtime<br \/>\nDenali with WHERE..IS NOT NULL:&nbsp; 3x worker time\/reads\/clrtime\n<\/p>\n<p>\nThis is interesting due to the fact that the plan cost was much less for the where-distance query vs. where-isnotnull query, but the resource cost is exactly the opposite. And more interesting is the fact that Isaac&#39;s numbers table-based algorithm wins both ways.\n<\/p>\n<p>\nCaveats: The obvious big caveat is that this is only a <strong>single<\/strong> test case,&nbsp;albeit a fairly common one (both &quot;@me&quot; and the points-of-interest are points). YMMV. Second, none of the queries I used, run in SSMS, allow for a proper cardinality estimate at plan creation time (aka parameter sniffing). But attempting to use sp_executesql or a sproc so that it could be estimated, causes the Denali &quot;where-distance&quot; query to loop endlessly. Bug reported; it is afterall, CTP1. And sp_executesql with the &quot;where-isnotnull&quot; case, doesn&#39;t do much better, still worse than&nbsp;&quot;numbers table&quot;.&nbsp;Third: Isaac&#39;s original algorithm&nbsp;is fragile&nbsp;in some edge cases (blank spatial table\/no qualifying points, IIRC), Ed and I handled these cases in the slightly&nbsp;revised version in the chapter in <a href=\"http:\/\/www.microsoft.com\/learning\/en\/us\/Book.aspx?ID=12805&amp;locale=en-us\">Inside SQL Server 2008 Programming<\/a>.\n<\/p>\n<p>\nSo, it appears that, even though the query is far less straightforward to write and the spatial index needs to be hinted, the numbers table method wins, so far. However,&nbsp;I&#39;d still say that&nbsp;the nearest neighbor optimization is useful to have in the product. But it <strong>is<\/strong> still Denali CTP1. And it goes without saying, if you have a test that disproves this, send it right along, I&#39;m always happy to see it.\n<\/p>\n<p>\n@bobbeauch<\/p>\n","protected":false},"excerpt":{"rendered":"<p>The nearest neighbor query is one of the most common queries against spatial data. How many people haven&#39;t gone to a mapping app, typed in their current location and asked for the 10 nearest [your favorite thing goes here]? The obvious way to phrase the spatial query for this, given an STDistance method on the [&hellip;]<\/p>\n","protected":false},"author":7,"featured_media":0,"comment_status":"open","ping_status":"closed","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[31,36],"tags":[],"class_list":["post-572","post","type-post","status-publish","format-standard","hentry","category-sql-server-2012","category-sql-server-spatial"],"yoast_head":"<!-- This site is optimized with the Yoast SEO plugin v21.9.1 - https:\/\/yoast.com\/wordpress\/plugins\/seo\/ -->\n<title>The nearest neighbor optimization in SQL Server Denali - Bob Beauchemin<\/title>\n<meta name=\"robots\" content=\"index, follow, max-snippet:-1, max-image-preview:large, max-video-preview:-1\" \/>\n<link rel=\"canonical\" href=\"https:\/\/www.sqlskills.com\/blogs\/bobb\/the-nearest-neighbor-optimization-in-sql-server-denali\/\" \/>\n<meta property=\"og:locale\" content=\"en_US\" \/>\n<meta property=\"og:type\" content=\"article\" \/>\n<meta property=\"og:title\" content=\"The nearest neighbor optimization in SQL Server Denali - Bob Beauchemin\" \/>\n<meta property=\"og:description\" content=\"The nearest neighbor query is one of the most common queries against spatial data. How many people haven&#039;t gone to a mapping app, typed in their current location and asked for the 10 nearest [your favorite thing goes here]? The obvious way to phrase the spatial query for this, given an STDistance method on the [&hellip;]\" \/>\n<meta property=\"og:url\" content=\"https:\/\/www.sqlskills.com\/blogs\/bobb\/the-nearest-neighbor-optimization-in-sql-server-denali\/\" \/>\n<meta property=\"og:site_name\" content=\"Bob Beauchemin\" \/>\n<meta property=\"article:published_time\" content=\"2011-01-03T14:24:00+00:00\" \/>\n<meta property=\"article:modified_time\" content=\"2013-01-04T07:59:34+00:00\" \/>\n<meta name=\"author\" content=\"Bob Beauchemin\" \/>\n<meta name=\"twitter:label1\" content=\"Written by\" \/>\n\t<meta name=\"twitter:data1\" content=\"Bob Beauchemin\" \/>\n\t<meta name=\"twitter:label2\" content=\"Est. reading time\" \/>\n\t<meta name=\"twitter:data2\" content=\"3 minutes\" \/>\n<script type=\"application\/ld+json\" class=\"yoast-schema-graph\">{\"@context\":\"https:\/\/schema.org\",\"@graph\":[{\"@type\":\"WebPage\",\"@id\":\"https:\/\/www.sqlskills.com\/blogs\/bobb\/the-nearest-neighbor-optimization-in-sql-server-denali\/\",\"url\":\"https:\/\/www.sqlskills.com\/blogs\/bobb\/the-nearest-neighbor-optimization-in-sql-server-denali\/\",\"name\":\"The nearest neighbor optimization in SQL Server Denali - Bob Beauchemin\",\"isPartOf\":{\"@id\":\"https:\/\/www.sqlskills.com\/blogs\/bobb\/#website\"},\"datePublished\":\"2011-01-03T14:24:00+00:00\",\"dateModified\":\"2013-01-04T07:59:34+00:00\",\"author\":{\"@id\":\"https:\/\/www.sqlskills.com\/blogs\/bobb\/#\/schema\/person\/62bfa986c5b5d28fcffd8b4fc409c73e\"},\"breadcrumb\":{\"@id\":\"https:\/\/www.sqlskills.com\/blogs\/bobb\/the-nearest-neighbor-optimization-in-sql-server-denali\/#breadcrumb\"},\"inLanguage\":\"en-US\",\"potentialAction\":[{\"@type\":\"ReadAction\",\"target\":[\"https:\/\/www.sqlskills.com\/blogs\/bobb\/the-nearest-neighbor-optimization-in-sql-server-denali\/\"]}]},{\"@type\":\"BreadcrumbList\",\"@id\":\"https:\/\/www.sqlskills.com\/blogs\/bobb\/the-nearest-neighbor-optimization-in-sql-server-denali\/#breadcrumb\",\"itemListElement\":[{\"@type\":\"ListItem\",\"position\":1,\"name\":\"Home\",\"item\":\"https:\/\/www.sqlskills.com\/blogs\/bobb\/\"},{\"@type\":\"ListItem\",\"position\":2,\"name\":\"SQL Server 2012\",\"item\":\"https:\/\/www.sqlskills.com\/blogs\/bobb\/category\/sql-server-2012\/\"},{\"@type\":\"ListItem\",\"position\":3,\"name\":\"The nearest neighbor optimization in SQL Server Denali\"}]},{\"@type\":\"WebSite\",\"@id\":\"https:\/\/www.sqlskills.com\/blogs\/bobb\/#website\",\"url\":\"https:\/\/www.sqlskills.com\/blogs\/bobb\/\",\"name\":\"Bob Beauchemin\",\"description\":\"SQL Server Blog\",\"potentialAction\":[{\"@type\":\"SearchAction\",\"target\":{\"@type\":\"EntryPoint\",\"urlTemplate\":\"https:\/\/www.sqlskills.com\/blogs\/bobb\/?s={search_term_string}\"},\"query-input\":\"required name=search_term_string\"}],\"inLanguage\":\"en-US\"},{\"@type\":\"Person\",\"@id\":\"https:\/\/www.sqlskills.com\/blogs\/bobb\/#\/schema\/person\/62bfa986c5b5d28fcffd8b4fc409c73e\",\"name\":\"Bob Beauchemin\",\"image\":{\"@type\":\"ImageObject\",\"inLanguage\":\"en-US\",\"@id\":\"https:\/\/www.sqlskills.com\/blogs\/bobb\/#\/schema\/person\/image\/\",\"url\":\"https:\/\/secure.gravatar.com\/avatar\/6f80e6cc667410857fa6a21931dc528b8092f4d112bf7a8ff7c267674d44ee37?s=96&d=mm&r=g\",\"contentUrl\":\"https:\/\/secure.gravatar.com\/avatar\/6f80e6cc667410857fa6a21931dc528b8092f4d112bf7a8ff7c267674d44ee37?s=96&d=mm&r=g\",\"caption\":\"Bob Beauchemin\"},\"sameAs\":[\"http:\/www.sqlskills.com\/blogs\/bobb\/\"],\"url\":\"https:\/\/www.sqlskills.com\/blogs\/bobb\/author\/bobb\/\"}]}<\/script>\n<!-- \/ Yoast SEO plugin. -->","yoast_head_json":{"title":"The nearest neighbor optimization in SQL Server Denali - Bob Beauchemin","robots":{"index":"index","follow":"follow","max-snippet":"max-snippet:-1","max-image-preview":"max-image-preview:large","max-video-preview":"max-video-preview:-1"},"canonical":"https:\/\/www.sqlskills.com\/blogs\/bobb\/the-nearest-neighbor-optimization-in-sql-server-denali\/","og_locale":"en_US","og_type":"article","og_title":"The nearest neighbor optimization in SQL Server Denali - Bob Beauchemin","og_description":"The nearest neighbor query is one of the most common queries against spatial data. How many people haven&#39;t gone to a mapping app, typed in their current location and asked for the 10 nearest [your favorite thing goes here]? The obvious way to phrase the spatial query for this, given an STDistance method on the [&hellip;]","og_url":"https:\/\/www.sqlskills.com\/blogs\/bobb\/the-nearest-neighbor-optimization-in-sql-server-denali\/","og_site_name":"Bob Beauchemin","article_published_time":"2011-01-03T14:24:00+00:00","article_modified_time":"2013-01-04T07:59:34+00:00","author":"Bob Beauchemin","twitter_misc":{"Written by":"Bob Beauchemin","Est. reading time":"3 minutes"},"schema":{"@context":"https:\/\/schema.org","@graph":[{"@type":"WebPage","@id":"https:\/\/www.sqlskills.com\/blogs\/bobb\/the-nearest-neighbor-optimization-in-sql-server-denali\/","url":"https:\/\/www.sqlskills.com\/blogs\/bobb\/the-nearest-neighbor-optimization-in-sql-server-denali\/","name":"The nearest neighbor optimization in SQL Server Denali - Bob Beauchemin","isPartOf":{"@id":"https:\/\/www.sqlskills.com\/blogs\/bobb\/#website"},"datePublished":"2011-01-03T14:24:00+00:00","dateModified":"2013-01-04T07:59:34+00:00","author":{"@id":"https:\/\/www.sqlskills.com\/blogs\/bobb\/#\/schema\/person\/62bfa986c5b5d28fcffd8b4fc409c73e"},"breadcrumb":{"@id":"https:\/\/www.sqlskills.com\/blogs\/bobb\/the-nearest-neighbor-optimization-in-sql-server-denali\/#breadcrumb"},"inLanguage":"en-US","potentialAction":[{"@type":"ReadAction","target":["https:\/\/www.sqlskills.com\/blogs\/bobb\/the-nearest-neighbor-optimization-in-sql-server-denali\/"]}]},{"@type":"BreadcrumbList","@id":"https:\/\/www.sqlskills.com\/blogs\/bobb\/the-nearest-neighbor-optimization-in-sql-server-denali\/#breadcrumb","itemListElement":[{"@type":"ListItem","position":1,"name":"Home","item":"https:\/\/www.sqlskills.com\/blogs\/bobb\/"},{"@type":"ListItem","position":2,"name":"SQL Server 2012","item":"https:\/\/www.sqlskills.com\/blogs\/bobb\/category\/sql-server-2012\/"},{"@type":"ListItem","position":3,"name":"The nearest neighbor optimization in SQL Server Denali"}]},{"@type":"WebSite","@id":"https:\/\/www.sqlskills.com\/blogs\/bobb\/#website","url":"https:\/\/www.sqlskills.com\/blogs\/bobb\/","name":"Bob Beauchemin","description":"SQL Server Blog","potentialAction":[{"@type":"SearchAction","target":{"@type":"EntryPoint","urlTemplate":"https:\/\/www.sqlskills.com\/blogs\/bobb\/?s={search_term_string}"},"query-input":"required name=search_term_string"}],"inLanguage":"en-US"},{"@type":"Person","@id":"https:\/\/www.sqlskills.com\/blogs\/bobb\/#\/schema\/person\/62bfa986c5b5d28fcffd8b4fc409c73e","name":"Bob Beauchemin","image":{"@type":"ImageObject","inLanguage":"en-US","@id":"https:\/\/www.sqlskills.com\/blogs\/bobb\/#\/schema\/person\/image\/","url":"https:\/\/secure.gravatar.com\/avatar\/6f80e6cc667410857fa6a21931dc528b8092f4d112bf7a8ff7c267674d44ee37?s=96&d=mm&r=g","contentUrl":"https:\/\/secure.gravatar.com\/avatar\/6f80e6cc667410857fa6a21931dc528b8092f4d112bf7a8ff7c267674d44ee37?s=96&d=mm&r=g","caption":"Bob Beauchemin"},"sameAs":["http:\/www.sqlskills.com\/blogs\/bobb\/"],"url":"https:\/\/www.sqlskills.com\/blogs\/bobb\/author\/bobb\/"}]}},"_links":{"self":[{"href":"https:\/\/www.sqlskills.com\/blogs\/bobb\/wp-json\/wp\/v2\/posts\/572","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/www.sqlskills.com\/blogs\/bobb\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.sqlskills.com\/blogs\/bobb\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.sqlskills.com\/blogs\/bobb\/wp-json\/wp\/v2\/users\/7"}],"replies":[{"embeddable":true,"href":"https:\/\/www.sqlskills.com\/blogs\/bobb\/wp-json\/wp\/v2\/comments?post=572"}],"version-history":[{"count":0,"href":"https:\/\/www.sqlskills.com\/blogs\/bobb\/wp-json\/wp\/v2\/posts\/572\/revisions"}],"wp:attachment":[{"href":"https:\/\/www.sqlskills.com\/blogs\/bobb\/wp-json\/wp\/v2\/media?parent=572"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.sqlskills.com\/blogs\/bobb\/wp-json\/wp\/v2\/categories?post=572"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.sqlskills.com\/blogs\/bobb\/wp-json\/wp\/v2\/tags?post=572"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}