search

elastic / elasticsearch-definitive-guide

The Definitive Guide to Elasticsearch
https://www.elastic.co/guide/en/elasticsearch/guide/current/index.html
Other
3.55k stars 2.83k forks source link

"Deep Paging in Distributed Systems" complexity issue #588

Open cihati opened 8 years ago

cihati commented 8 years ago

You can see that, in a distributed system, the cost of sorting results grows *exponentially* the deeper we page.

It doesn't grow exponentially -- the growth function is still polynomial (what exactly depends on the number of shards and the sorting algorithm)

polyfractal commented 8 years ago

Ah, I think this was just a manner of expression, rather than an actual algorithmic complexity time. :)

But yeah, we should be more precise with language. Will fix when I get a chance :)