Alright, a little more information. I just did a different test with backlinks. On most of my tiddlers, I have a tab that lists all of the backlinks to that tiddler. When I click on that, I see a similar delay. Looking at the performance instrumentation, I see the following:
mainRefresh: 3381.10ms
"filter: [all[current]backlinks[]!search:description[Newspapers]limit[1]]"
takes 3316.5ms
However, this long time only happens the very first time I click this particular backlinks tab for any tiddler. Any other tiddler after that, I can open that tab in a fairly fast time. Although, I need to experiment a bit further, I think this is the same thing that is happening with Relink. It's the first time a backlinks filter is run that takes forever. Any time after that, it seems reasonably fast (unless the TW is reloaded then it starts all over again).
So my question is now becoming what is it about the first time the filter for backlinks is run that takes so long? Is it the size of my TW or something else?