4 ms·

GitHub's search is pretty interesting: every time I refresh the search page it shows a different number of results: 18,401,830; 17,751,631; 15,995,799. Which i

GitHub's search is pretty interesting: every time I refresh the search page it shows a different number of results: 18,401,830; 17,751,631; 15,995,799. Which is anyways quite a lot of results, but then this search finds ThisShouldNeverHappenException, the string "this should never happen" and stuff like // *This* gets run before every test. if (b > d) { fail("XX *should never happen*"); } With quotations it's only about 500,000.

ddebernardy 11y ago
Usually, you'd never actually _count_ the expected results for such stuff. Instead, you'd return the estimate number of records (think SQL EXPLAIN). I'd gather the number seems very dynamic because of the constant stream of commits.
BenoitP 11y ago
HyperLogLog[1] will do that. You can find it in Redis, Lucene; and I suspect it is also hidden behind BigQuery's count(distinct X)s. [1] https://en.wikipedia.org/wiki/HyperLogLog https://en.wikipedia.org/wiki/HyperLogLog
- sammoth 11y ago
  What part of the algorithm would cause the number to change significantly every time you run the query?
  - BenoitP 11y ago
    All shards compute their own, and send the result in a non deterministic order. My explanation is that the merge part of HLL depends on the order. Line 95 of this method [1] from this implementation [2] shows a max(mask(x), mask(y)), which is not associative but is a close proxy to max()(which is associative). [1] https://github.com/addthis/stream-lib/blob/af045cb4199959c07fb4422e605573e180491191/src/main/java/com/clearspring/analytics/stream/cardinality/RegisterSet.java#L87 https://github.com/addthis/stream-lib/blob/af045cb4199959c07... [2] https://github.com/addthis/stream-lib/blob/master/src/main/java/com/clearspring/analytics/stream/cardinality/HyperLogLog.java https://github.com/addthis/stream-lib/blob/master/src/main/j...
datihein 11y ago
Trying a quoted "should never happen" yields a bit over 3,000,000 results. Trying a quoted "never happen" yields over 5,000,000 results.

ddebernardy 11y ago

Usually, you'd never actually _count_ the expected results for such stuff. Instead, you'd return the estimate number of records (think SQL EXPLAIN). I'd gather the number seems very dynamic because of the constant stream of commits.

BenoitP 11y ago

HyperLogLog[1] will do that. You can find it in Redis, Lucene; and I suspect it is also hidden behind BigQuery's count(distinct X)s. [1] https://en.wikipedia.org/wiki/HyperLogLog https://en.wikipedia.org/wiki/HyperLogLog

sammoth 11y ago
What part of the algorithm would cause the number to change significantly every time you run the query?
- BenoitP 11y ago
  All shards compute their own, and send the result in a non deterministic order. My explanation is that the merge part of HLL depends on the order. Line 95 of this method [1] from this implementation [2] shows a max(mask(x), mask(y)), which is not associative but is a close proxy to max()(which is associative). [1] https://github.com/addthis/stream-lib/blob/af045cb4199959c07fb4422e605573e180491191/src/main/java/com/clearspring/analytics/stream/cardinality/RegisterSet.java#L87 https://github.com/addthis/stream-lib/blob/af045cb4199959c07... [2] https://github.com/addthis/stream-lib/blob/master/src/main/java/com/clearspring/analytics/stream/cardinality/HyperLogLog.java https://github.com/addthis/stream-lib/blob/master/src/main/j...

datihein 11y ago

Trying a quoted "should never happen" yields a bit over 3,000,000 results. Trying a quoted "never happen" yields over 5,000,000 results.