DynamoDS/Dynamo — pull request #2198 by pboyer (2014-08-20 20:07:39+00:00)
Title: Improve node library search speed

### Problem

Search is too slow! Ian reported seeing >100 ms round trip times. Ew!

### Philosophy of fix

My hope was that search speed could be improved while maintaining similarly good results. I also wasn't looking to spend a week on the project, just an hour or so to see if it could be fixed.

Ian pointed out that the bottleneck for search speed was `SearchModel.Search`, which delegates to `SearchDictionary.Search`. My numbers (see below) corroborated this.

I discovered the following line in `SearchDictionary.Search`:

```
if (pair.Key.ToLower().Contains(query.ToLower()) || MatchWithQuerystring(pair.Key, query)){
```

Which essentially filters the search results, before finding their match "closeness", and sorting them.

It turns out that `MatchWithQueryString` constructs a regex in order to account for whitespace and otherwise incorrectly formatted queries. While this solves an important problem of finding approximate matches, it is slower than molasses in january and is performed on any search tag that does not contain the query. :(

I changed `SearchDictionary.Search` so that it will only perform this more expensive matching if a critically low number of matches is returned by the default search strategy. This is configurable, but currently set to 0.

### Results

As a result, search runs about 1-2 orders of magnitude faster while still returning approximately as good results for most calls. In the below numbers, I typed in "point" sequentially and recorded the numbers. The update of the UI is very consistently ~12 ms.

Original results (does tolerant search every call)
```
Search complete in 00:00:00.0349741 // P
Search complete in 00:00:00.0730395 // O
Search complete in 00:00:00.0806041 // I
Search complete in 00:00:00.0800181 // N
Search complete in 00:00:00.0804722 // T
```
Results after optimization
```
Search complete in 00:00:00.0008895 // P
Search complete in 00:00:00.0005377 // O
Search complete in 00:00:00.0004870 // I
Search complete in 00:00:00.0004864 // N
Search complete in 00:00:00.0004958 // T
Search complete in 00:00:00.0794679 // (space) - at this point more tolerant search kicks in
Search complete in 00:00:00.0969312 // B
Search complete in 00:00:00.1781982 // Y
```
### Reviewers

@Benglin, @ikeough, @ke-yu