4 ms·

One interesting observation of 'modern' sorting algorithms that ship with programming languages is that they're mostly an amalgamation of various classical sort

One interesting observation of 'modern' sorting algorithms that ship with programming languages is that they're mostly an amalgamation of various classical sorting algorithms with tests and heuristics to dynamically switch between them depending on the case. Cases like: few elements, elements already sorted with some out of order elements appended, elements sorted in reverse, detecting worst case behavior of quicksort and changing to heap sort instead, exploiting exit conditions of prior recursion steps to skip checks, etc etc. These kinds of meticulous opportunistic optimizations give us a chance to get theoretically ideal performance in both the worst and best case scenarios, and I hope we can apply this same methodology for many more algorithms in the future. Databases query optimizers sorta do this, but they typically make such decisions ahead of time so are prone to getting stuck with a bad plan. (Obviously this is highly dependent on your engine of choice.)

klysm 4y ago
I thought a lot of optimizers used tabled cardinalities to estimate the cost of various join algorithms.
- zasdffaa 4y ago
  Pretty well all modern commercial DBs do use summary (or sampled?) statistics of the cardinalities. The alternative is rule-based rewriters which were heuristically-driven only, and AFAIK they justifiably went out of use decades ago.
- juancn 4y ago
  They do, but joins still cause unpredictable data scan jumps. Even if perfectly optimized. Think of an analytic query over a star schema, maybe the query needs 10 or 20 joins to align all the data for each of the fact tables, and scans most of the data (some aggregate report over the last year of data), but these joins don't reduce the cardinality much. If you look at the data access pattern, it's scattered all over the place for each joined row. You end up needing to read in a lot of data, possibly many times to complete the query.
CHY872 4y ago
Increasingly databases can get do-overs on bad plans. A micro-level example might be dataflow splitting particularly expensive tasks so as to better parallelize them: https://cloud.google.com/blog/products/gcp/no-shard-left-behind-dynamic-work-rebalancing-in-google-cloud-dataflow https://cloud.google.com/blog/products/gcp/no-shard-left-beh... Spark will re-run the query planner after doing the map stage of a map-reduce operation so as to leverage the information collected: https://databricks.com/blog/2020/05/29/adaptive-query-execution-speeding-up-spark-sql-at-runtime.html https://databricks.com/blog/2020/05/29/adaptive-query-execut... Both examples represent changing parameters about a lower level plan than simply join operators, but the industry is certainly moving in this direction.
- sitkack 4y ago
  Most systems that make expensive scans should be updating or creating a count-min-sketch histogram of the data to allow schedulers and query planners to do a better job. https://en.wikipedia.org/wiki/Count%E2%80%93min_sketch https://en.wikipedia.org/wiki/Count%E2%80%93min_sketch https://duckduckgo.com/?t=ffab&q=count-min+sketch+site%3Avldb.org&ia=web https://duckduckgo.com/?t=ffab&q=count-min+sketch+site%3Avld... https://www.semanticscholar.org/search?q=count-min%20sketch%20database&sort=relevance https://www.semanticscholar.org/search?q=count-min%20sketch%...

klysm 4y ago

I thought a lot of optimizers used tabled cardinalities to estimate the cost of various join algorithms.

zasdffaa 4y ago
Pretty well all modern commercial DBs do use summary (or sampled?) statistics of the cardinalities. The alternative is rule-based rewriters which were heuristically-driven only, and AFAIK they justifiably went out of use decades ago.
juancn 4y ago
They do, but joins still cause unpredictable data scan jumps. Even if perfectly optimized. Think of an analytic query over a star schema, maybe the query needs 10 or 20 joins to align all the data for each of the fact tables, and scans most of the data (some aggregate report over the last year of data), but these joins don't reduce the cardinality much. If you look at the data access pattern, it's scattered all over the place for each joined row. You end up needing to read in a lot of data, possibly many times to complete the query.

CHY872 4y ago

Increasingly databases can get do-overs on bad plans. A micro-level example might be dataflow splitting particularly expensive tasks so as to better parallelize them: https://cloud.google.com/blog/products/gcp/no-shard-left-behind-dynamic-work-rebalancing-in-google-cloud-dataflow https://cloud.google.com/blog/products/gcp/no-shard-left-beh... Spark will re-run the query planner after doing the map stage of a map-reduce operation so as to leverage the information collected: https://databricks.com/blog/2020/05/29/adaptive-query-execution-speeding-up-spark-sql-at-runtime.html https://databricks.com/blog/2020/05/29/adaptive-query-execut... Both examples represent changing parameters about a lower level plan than simply join operators, but the industry is certainly moving in this direction.

sitkack 4y ago
Most systems that make expensive scans should be updating or creating a count-min-sketch histogram of the data to allow schedulers and query planners to do a better job. https://en.wikipedia.org/wiki/Count%E2%80%93min_sketch https://en.wikipedia.org/wiki/Count%E2%80%93min_sketch https://duckduckgo.com/?t=ffab&q=count-min+sketch+site%3Avldb.org&ia=web https://duckduckgo.com/?t=ffab&q=count-min+sketch+site%3Avld... https://www.semanticscholar.org/search?q=count-min%20sketch%20database&sort=relevance https://www.semanticscholar.org/search?q=count-min%20sketch%...