ethbak commented on issue #16552: URL: https://github.com/apache/lucene/issues/16552#issuecomment-5414678913
It seems @msokolov predicted this issue while the initial PR was still in review, but the fix never made it into the merged code. https://github.com/apache/lucene/pull/15003#issuecomment-3250002372 > there is the possibility of creeping graph rot where we continually erode the graph through repeated merges, and each time the deletion % gets reset to 0 so we think everything looks fine? … examine some metric that persists across merges, like graph connectivity. We could (for example) check for nodes whose outdegree drops below 50% of maxconn, and in those cases, use searches to "patch up" the graph? The `outdegree < 50% of maxConn` idea was benchmarked in https://github.com/apache/lucene/pull/15003#issuecomment-3499486112, but was discarded in favor of the relative, 15% single merge loss, implementation due to performance (naive implementation which simply repaired all nodes with outdegree < 50% M erased nearly all performance gains, taking **73.1%** of merge time with NO RE-USE). Since the case with small delete percentage over many iterations was not benchmarked, the cost of using the relative approach over the absolute was not fully understood. Performance was so poor in the previous absolute maxConn benchmark run because some nodes are sparse by design, and even in a healthy graph built from scratch, they have fewer than .5 * maxConn connections. @benwtrent pointed this out https://github.com/apache/lucene/pull/15003#issuecomment-3497692104: > I bet the issue with higher maxconn is that the layer is sparsely connected already, meaning very few deletes throw you under the 50% threshold … make that 50% relative to the connections the graph had BEFORE the deletes? BUT, we can avoid this issue somewhat by only applying the cap-relative clause **when the node actually lost at least one neighbor in the current merge**. A sparse-but-stable node that lost nothing is never touched. This would improve merge performance (won't repeatedly fire re-diversification on nodes that are sparse by design, unless they actually lost a connection) and has some nice properties: - It doesn't change behavior on very sparse nodes at all. With the current 0.85 factor, a single lost neighbor already exceeds 15% once a node is down to ~6 or fewer connections (`1 > 0.15 * 6`), so those nodes were already being repaired on any loss, and the loss-gate preserves that. - Instead, it extends protection to the higher-degree nodes that currently slip through when they lose a little each merge, stay above the 15%-relative bar every time, and erode unchecked. I'm currently working on an implementation for this locally and am mid-benchmarking but the results so far look very promising, it looks like we may be able to restore the recall while maintaining a bigger improvement in merge time performance (~25% of rebuild time, vs. 73.1% that was initially benchmarked, ~3x speedup). -- This is an automated message from the Apache Git Service. To respond to the message, please log on to GitHub and use the URL above to go to the specific comment. To unsubscribe, e-mail: [email protected] For queries about this service, please contact Infrastructure at: [email protected] --------------------------------------------------------------------- To unsubscribe, e-mail: [email protected] For additional commands, e-mail: [email protected]
