CMU Database Systems - 06 Hash Tables (Fall 2018)

[@Qladstone]

Databases do evoke everything I love about Computer Science. Love it!

[@pritamkarmokar3674]

At 12:41, didn't he mean "different keys hashed to the same offset " for collision ?

[@MrEternalFool]

Can I access the projects from outside CMU? There won't be any point in doing the course without doing the projects...

[@evanxg852000]

I actually have sent two emails about this but Never got a reply. At least I would expect to get a "Not possible" as an answer rather than no reply. Maybe my emails ended up in junk folder... But so far I am following while forcing myself in reading SQLite source.

[@mopang3116]

Maybe this is useful for you:github.com/Jiawei0227/CMU-Database/tree/441d48673353bf070747cf888a137e331063fcef

[@DenisG631]

Great lecture. But when it comes to Robin-Hood isn't it all about cheap writes vs fast access even under high load factor trade-off? Writes are expensive and even though reads are more or less as fast as in Linear Probing, we can operate (my assumption, no claim here) under higher load factors with still very good read speed, isn't it?

[@easternsunking255]

great talks ,thanks

[@clarkd1955]

On modern computers, cache friendly code runs faster than almost any other optimization technique. In fact this is so true that if you only use cache friendly code, you don’t need any other optimization. Linked lists are the cause of more cache misses than any other technique so linked lists should be avoided everywhere. I see no point in teaching techniques that are known to be sub-optimal and this video on hashing is an example. I find it very sad to see academics teaching minds that don’t know the truth, techniques that guarantee they will be second rate programmers. The only world that should ever be taught is the “real world” and if academics don’t understand that world, they shouldn’t be allowed to teach.

[@thesnowmancometh]

How much of a bummer at you at parties? I love that you think the working set of a database fits in cache memory. Dunning-Kruger effect incarnate.

[@andypavlo]

This is an intro class on disk-oriented DBMSs. I am trying to teach the basics of hash tables implementations to undergraduates. I think you missed the part where I say the linear probe hash table is usually the fastest. FWIW, I cover cache-friendly hash tables in the Advanced DB class: kzbin.info/www/bejne/mmHRn5V_d5mKf5I

[@DenisG631]

How come learning other approaches, which are "sub-optimal" bad? Before you learn about an approach that is successful you compare it with other approaches and compare them and then make a conclusion what made the fast solution that fast. And are you not fascinated by the ideas outside of linear probing? The moment I've heard about Robin-Hood and Cuckoo hashing it blew my mind. And when it comes to hashing with chaining, you can always replace linked list with a vector

[@clarkd1955]

I might have been a bit harsh but in my defense, it is difficult to describe complex ideas in just a few words. These courses seem to be about designing and working on large complex databases where every cycle counts. Every cycle doesn’t count in most end user software but this course isn’t for them. I do believe this teacher knows how to program (I don’t think that in general about most CS professors) and I just wanted to remind him that only cache efficient techniques should be used in databases. I wrote my first database code (not the application part) in the early 1980’s. I currently am developing a database/language combo so I know what kind of data structures actually work and which ones don’t. I do like watching this series of lectures although I obviously don’t agree with all the details. That just means that I passionately care about databases just like this teacher.