Simple Windowing and Ranking on Postgres – Or a Behind-The-Scenes look at GitHeroes

19 Jan 2012 – Singapore

I’d written this down a while ago about an app that I thought would be cool – l33tornot.com. The concept is basically centered around voting for hackers you thought were l33t – the idea was to be completely harmless and meant out of curiosity as to whom people would vote for.

But there were complications – who was eligible? How would you handle duplicates ? How would you avoid election fraud – authenticating with Twitter, Facebook or something else? Also how do you handle the case where a larger-than-life character overshadows your personal hero based in tiny Singapore?

These problems put a dampener on my efforts but I was determined not to let this idea pass – and so on New Years’ Eve (after much thought for the previous two days), I decided to re-incarnate the idea as GitHeroes.

Premise

The premise was simple:

• Login using GitHub
• Nominate your personal hero (you could nominate as many as you want)
• Publicize your nomination so you could get fellow hackers to vote for them
• Put up a leaderboard so you could see how your hero was doing

This re-incarnation of the app did away with problems of deciding “canonical” objects for hackers being nominated, election fraud and seemed a much more elegant app.

Behind The Scenes

The app was built using Rails 3.1, CoffeeScript, Twitter Bootstrap, PostgreSQL and is hosted on Heroku. It uses Omniauth for GitHub OAuth integration (Omniauth by the way is a fantastic library) and with a little help from Quora, I even found the GitHub font so that I could design a good-enough logo.

Ranking using PostgreSQL

The most interesting bit for me about GitHeroes is the way the ranking/leaderboard stuff is done. I contemplated using Redis to do ranking, but I am quite wary of introducing dependencies to a Rails stack unless it’s absolutely necessary.

Turns out, it is unnecessary because Postgres (8.4 and above) provides with you window functions which let you run calculations across a set of rows in a table. You can choose to group similar rows together, but they also work across the entire table.

Sidenote: Postgres 8.4 is not available on the shared database plans available on Heroku so you will need to provision your own or upgrade to the paid plans.

How voting is designed is quite simple, here is the class:

As you may notice, there is a counter-cache for the hero being voted for and the votes_received is incremented on Hero every time a vote is cast.

The votes_received column is then used as the column to rank while choosing heroes for the leaderboard.

This is the function used in the Hero class to get the top 20 heroes ranked by votes across all locations:

…and this is the function used to get the top 20 hereoes by votes in a given location:

Note: You will need to add a descending order index on votes_received, since by default btree indexes on Postgres use the ascending order:

CREATE INDEX desc_votes_recvd_idx on heros(votes_received DESC NULLS LAST);

As you can see from the query plan below, the query is quite efficient and works like a charm: (although I probably should run benchmarks against a larger table)

Conclusion

GitHeroes was a fun little project that took two days to build and got to the front page of Hacker News. But it also gave me a chance to explore some neat Postgres features which will be useful for the other app that we are building – Denso.