A little while ago, I delivered my master thesis and finished my Master of Technology in Computer Science degree at the Norwegian University of Science and Technology. The thesis has the title iAD: Query Optimization in MARS, and is about building a query optimizer for Fast's (now a subsidiary of Microsoft, they bought them) new Enterprise Search solution.

The report itself can be found here: MasterReport.pdf, and the abstract is included below:

This document is the report for the authors' joint effort in researching and designing a query optimizer for Fast's next-generation search platform, known as MARS. The work was done during our master thesis at the Department of Computer and Information Science at the Norwegian University of Science and Technology, spring 2009.

MARS does not currently employ any form of query optimizer, but does have a parser and a runtime system. The report therefore focuses on the core query optimizing aspects, like plan generation and optimizer design. First, we give an introduction to query optimizers and selected problems. Then, we describe previous and ongoing efforts regarding query optimizers, before shifting focus to our own design and results.

MARS supports DAG-structured query plans for more efficient execution, which means that the optimizer must do so too. This turned out to be a greater task than what it might seem like -- since we must use algorithms that greatly differ from the optimizers we were familiar with. The optimizer also needed to be extensible, including the ability to deal with future query operators, as well as supporting arbitrary cost models.

During the course of the master's thesis, we have laid out the design of an optimizer that satisfies these goals. The optimizer is able to recognize common subexpressions and construct DAGs from non-DAG inputs. Extensibility is solved by loose coupling between optimizer components. Rules are used to model operators, and the cost model is a separate, customizable component. We have also implemented a prototype that demonstrates that the design actually works.

The optimizer itself is designed as a separate component, not tied up to MARS. We have been able tin inject it into the MARS query pipeline and run queries end-to-end with optimization enabled, improving query evaluation time. For now, the project depends on MARS assemblies, but reusing it for another engine and algebra is entirely feasible.

I'm in my last semester here at the Norwegian University of Science and Technology, which means that I'm starting on my master thesis these days. Actually, I'm not starting now, I'm continuing on the "pre-project" I worked on together with my friend, Alex Brasetvik from August to December last year.

Our master thesis is about building a query optimizer for Fast's (now a subsidiary of Microsoft, they bought them) new Enterprise Search solution.

The report itself can be found here: MasterProjectReport.pdf, and the abstract is included below:

This document is the report for the authors’ joint effort in researching and designing a query optimizer for fast’s next-generation search platform, known as MARS. This work was done during the pre-project to the master thesis at the Department of Computer and Information Science at the Norwegian University of Science and Technology, autumn 2008.

MARS does not currently employ any form of query optimizer, but does have a parser and a runtime system. The report therefore focuses on the core query optimizing aspects, like plan generation and optimizer design. First, we give an introduction to query optimizers and selected problems. Then, we describe previous and ongoing efforts regarding query optimizers, before shifting focus to our own design and results.

MARS supports DAG-structured query plans, which means that the optimizer must do so too. This turned out to be a greater task than what it might seem like. The optimizer also needed to be extensible, including the ability to deal with query operators it does not know, as well as supporting arbitrary cost models.

During the course of the project, we have laid out the design of an optimizer we believe satisfies these goals. DAGs are currently not fully supported, but the design can be extended to do so. Extensibility is solved by loose coupling between optimizer components. Rules are used to model operators, and the cost model is a separate, customizable component. We have also implemented a prototype that demonstrates that the design actually works.

I recently wrote a paper at school about how flash memory impacts the database world. Those who are interested can read it here: How Flash Memory Changes the DBMS World - An Introduction

I month ago my team (Åsmund Eldhuset, Frank Robert Kvam and me) came second in the Nordic Collegiate Programming Contest at NTNU (13th in total) and thereby qualified us for the Northwestern European Programming Contest (NWERC) in Utrecht, The Netherlands.

NWERC is happening this weekend, and the contest itself is today. You should be able to follow the standings live at http://2007.nwerc.eu/live/scoreboard, and if the web cam works (it doesn't right now, it looks like), you should be able to see us as well here: http://2007.nwerc.eu/live/cam3.

 

A couple of months ago my team from Imagine Cup (Team NTNU) got an invitation to TechEd 2006 in Barcelona from the organizers of Imagine Cup and Microsoft EMEA.

We are going to present our solution and talk a little about our experience in India to the students attending TechEd. We're maybe also going to have a booth with some posters and stuff where we can show our solution. TechEd starts on Monday, so now it's time to get to Barcelona.

It's also going to be exciting to see all the new stuff they are going to show at TechEd. I've never attended a developer conference at this scale, so this is going to be interesting!

On Wednesday Gøran and I held the third lecture in the .NET course I mentioned in the last blog post. This time it was about Windows Workflow Foundation, which is a very cool product. I'm looking forward to testing it more. The lecture was recorded on video this time too, see links below (only in Norwegian this time too, unfortunately).

Part 1:
http://multimedie.adm.ntnu.no/mediasite/viewer/?peid=0c87d69b-90e1-4452-a264-3134b2c46970

Part 2:
http://multimedie.adm.ntnu.no/mediasite/viewer/?peid=2f71abd7-7d52-4e6d-a2ce-efd334d2c478

It has long irritated me that NTNU - The Norwegian University of Science and Technology - doesn't offer ANY courses on Microsoft Technology whatsoever, at least as far as I know. We're only learning Java and other stuff, and .NET and C# are lucky to be mentioned at the end of a sentence. The foremost university in the country should take a look at the figures for which technologies are really used by software companies today.

But, things are starting to change, but not exactly in the way I expected them to:

1. It is not my department, the Department of Computer and Information Science (IDI) that is responsible for the change, but the Department of Engineering Design and Materials! The first .NET course at NTNU is not hosted by the computer science people, but by the engineering design and materials people! Come on, IDI, take the hint! Look outside your own little Java sandbox.
2. Guess who is holding the lectures! It's Rune Zakariassen from Microsoft, me and a friend of mine, Gøran, from Microsoft Student Community NTNU. That's pretty cool!

The course is a preparation study for 5th year students starting on their diploma assignment, and consists of four seminars with lectures and hands-on labs. The first one was an introduction to .NET and C#. The second one, held this Wednesday was about Windows Communication Foundation (WCF), and the two next ones will be about Windows Workflow Foundation (WF) and real time communication. The idea behind the course is to give the students a superficial knowledge about these technologies so they can use them in their assignments.

The lectures were recorded on video. Here are the videos from the WCF lecture (in Norwegian, unfortunately):

Part 1: http://multimedie.adm.ntnu.no/mediasite/viewer/?peid=ac76f55b-9779-46d2-bc80-f789d3e1b469
Part 2: http://multimedie.adm.ntnu.no/mediasite/viewer/?peid=45f281b4-ae25-46d1-bfc9-d0d81ca6f140

I'm still alive, but I've been so busy the last couple of months that I haven't had the time to update the blog. So here comes a blog post a bit longer than usual.

A lot of things have happened since the last post from August 3rd:
- Team Norway got third place in the Software Design final in Imagine Cup
- My internship at Microsoft is over
- I'm back in Norway at school

So, let's take the first things first.

From the 4th to the 12th of August I had one week off from my internship at Microsoft to participate in the International finals of Imagine Cup 2006 in Agra and New Delhi, India, together with my team mates from Norway. I flew from Seattle to New York, had 20 minutes to get on the plane to New Delhi and then spent the next 14 hours on that plane. We actually flew right above Trondheim, the city where I study here in Norway. I took around 30 hours in total, and then add the 11,5 hours of time difference and staying up the first night in India to get our demo up and running, and you're there.

We didn't really expect to get as far as we got in India, since we knew there were going to be very many good teams and solutions. But we wanted to do our best, and at least we would get to see what India and the Imagine Cup finals are like

Our team consists of four students from NTNU; Jan-Kristian (who is a FTE at MS now), Jonas, Gøran and me. We participated in the Software Design category, in which you are to come up with an idea on this year's Imagine Cup theme and design a software solution around this.
The Software Design category consisted of three rounds. The first round was a 20 minute presentation where we presented our solution to the judges, and then 10 minutes with Q&A after wards. We held our presentation, and we thought it went pretty well, but we were still a bit surprised when we were selected to be among the 12 best teams that went to the second round. Now we were starting to think "maybe we're onto something here", and went for the second round presentation to do our best.

As always, things didn't come together before the last moment. We stayed up all night before the first round to get our demo up and running, and when we got to the second round, we had to improve it a bit. So we were coding to the last moment. After the second round, things got even better when it was announced that we were among the six best teams, along with Denmark, Italy, Japan, China and Brazil. We were to present our solution to all the other contestants at the biggest conference center in New Delhi! The presentation went well, and we managed to answer the questions the judges came up with pretty well. Finally we ended up third, winning $10 000 and a trip to England in January!

The trip was great; we got to see India and met a lot of other smart people with the same interests. The only showstopper was that I got sick a couple of days, probably because I ate some ice cream which I shouldn't have eaten. I missed a couple of things, the trip to Taj Mahal, among others.

Thanks to all the people who made Imagine Cup 2006 possible and to all the participants for a great time in India!

Us on stage in Delhi, presenting the MSN bot in our solution.

After the prize ceremony. We won $10 000! (Me on the far left)

Gøran has published a few photos from India on his Flickr site:
http://www.flickr.com/photos/22075141@N00/sets/72057594128196432/

When we got third place, we got a lot of publicity on many internet sites and in many newspapers. The number of results when you google my name has skyrocketed from about fifty to several hundred.

Here is a collection of links to news paper articles about Imagine Cup (mostly in Norwegian, unfortunately):
http://www.microsoft.com/norge/about/pr/news/pressemeldinger/imaginecup.mspx
http://www.demokraten.no/lokalnytt/article2230027.ece Demokraten: Fredrikstad-student i verdenstoppen
http://www.dagbladet.no/nyheter/2006/08/12/473687.html Dagbladet: Nerde-bronse
http://www.f-b.no/apps/pbcs.dll/article?AID=/20060813/NYHET/108130011 Fredrikstad Blad: Bronse til Hvaler-gutt i Imagine Cup
http://www.f-b.no/apps/pbcs.dll/article?AID=/20060809/NYHET/60809012 Fredrikstad Blad: Til topps i Imagine Cup?
http://www.f-b.no/apps/pbcs.dll/article?AID=/20060610/NYHET/106100011 Fredrikstad Blad: Til "data-VM" i India
http://www.amcham.no/news/news.asp?id=2165 Microsoft Announces Imagine Cup 2006 Winners - Norwegian Students Take 3rd
http://www.adressa.no/student/article702330.ece Adressavisen: NTNU-bronse i India
http://www.adressa.no/student/article701661.ece NTNU-studenter i verdensklasse
http://www.adressa.no/student/article699982.ece Adressavisen: NTNU-studenter i verdenstoppen
http://www.computerworld.no/index.cfm/fuseaction/artikkel/id/60990 Computerworld: Tredjeplass for NTNU-studenter
http://www.dagensit.no/min-it/article848038.ece Dagens IT: Forsvarer Norges ære
http://www.dagensit.no/bedrifts-it/article850515.ece Dagens IT: NTNU-studenter på verdenstoppen
http://www.digi.no/php/art.php?id=314315 Digi.no: NTNU-studenter på global medaljeplass
http://www.hegnar.no/IT-Kanalen/newsdet.asp?id=225807&cat=110 Hegnar.no: Nordmenn i global teknologikonkurranse
http://grunder.imaker.no/cgi-bin/grunder/imaker?id=1971  Grunder: Stor seier for NTNU-studentene
http://www.nettavisen.no/innenriks/article708217.ece Nettavisen: NTNU helt i tet
http://www.nordlys.no/nyheter/article2232445.ece Nordlys: Lakselv-studenter kan nå helt til tops
http://www.nordlys.no/nyheter/article2230046.ece Gjør suksess i India
http://www.finnmarkdagblad.no/nyheter/article2230903.ece Nordlys: Lakselvgutter i verdenstoppen

I'll talk more about my internship at Microsoft in a later blog post.

Yesterday seven students from high school were competing in the NIO finals. The competition got a little bit delayed because of technical problems with the online judging system, but anyway the competition was a success. You can view the results here.

Congratulations to all contestants and to Jørgen Vold Rennemo for the highest score in NIO's history!

The Norwegian Informatics Olympiad (NIO) finals are being held this weekend. 7 contestants from high school will be competing for a trip to the International Olympiad in Informatics (IOI), held in Mérida, Yucatán, Mexico this year.

The contestants will be solving four algorithmic tasks in five hours. I'm a co-organizer, and I'm looking forward to seeing the contestants and the results.