Last week I have a discussion with a colleague who is working on improving the analyze-speed of AO|AOCS table in Greenplum (at least 10x speed up). We search the Internet and do not find the performance analysis of Algorithm S and Knuth’s TAOCP left this (mean and var) as exercises. This blog is the solution to Knuth’s exercises.

Recently I happen to see someone posts that the most beautiful data structure in his mind is Dancing Links. The name bursts my interest to understand one more idea from Dr. Knuth. (again let me paste the margin comment of Concrete Mathematics here):

Actually Gauss is often called the greatest mathematician of all time. So it’s nice to be able to understand at least one of his discoveries.

Follow the curiosity and keep youth. I am writing this blog to re-state the algorithm to confirm my understanding.

我2017年7月加入Pivotal，伴随着被收购，2020年4月成为了VMware的员工。Greenplum近期招聘了非常多优秀的年轻人，充满希望。在看到了今年中国区编程比赛的报名通知的时候，我立刻把信息转发给某个manager，建议组织一些年轻人去打，最好拿个奖回来，多少扬扬名。然后Greenplum团队组了两个绝对年轻的队伍，全部是入职一年以内（或者出头一点点）。比赛昨天结束，两个队伍一个第一，一个第二，成绩很优异。

我没有参加，但是下午的时候，我看了一眼题目，第一反应肯定是NP问题，第二反应，这种东西，就应该用声明式编程语言求搞定。然后我花了一点点时间，写了一个Python程序，把题目编译成SMT程序，然后丢给Z3求解器去搞定。没有做什么优化，可以跑出8组解，感觉如果继续加入一些人类经验去优化，应该可以搞定大部分(有点装得不负责任)。

The PR (Implement two-stage sampling for AO/AOC analyze #11190) of Greenplum catches my attention. The PR, like many other commits of Greenplum, is perfectly documented and at the top of the commit message it introduces two algorithms of sampling:

• Algorithm S from Knuth
• Algorithm Z from Vitter

Then I become interested in these algorithms, search some resource in the Internet and understand quite a bit of the topic so here comes this blog.

See the PDF version of tutorial. It can also be downloaded here.