Comment by aboodman | Hacker News Reader

Comment by aboodman | Hacker News Reader

Parent Full thread

Imagine you're doing:

SELECT * FROM EMPLOYEE, DEPARTMENT WHERE EMPLOYEE.DEPARTMENTID = DEPARTMENT.ID

The naive thing would be to iterate employees and for each one read the corresponding department. However that would mean one disk seek per employee.

Disk seeks on the rotational disks relational dbs were developed for took hundreds of ms to complete. Even today's rotational disks have seeks that take dozens of ms. So doing one seek per join result doesn't work at all. You can add caching to disguise to some extent, but that costs memory.

Compare to B-Trees: You build an index on EMPLOYEE.DEPARTMENTID. That index is also a B-Tree. Because they are sorted, you can just walk both employee index and department table in parallel by id. You only need to do n/k seeks (where k is branching factor of the b-tree). You only need one record worth of caching per table (the one under the current cursor).

Bonus: because the indices are sorted, it's easy to pipeline each seek after the previous to further reduced the latency of the query.

Thanks, makes sense! I've once before seen comparing sorted values is faster, even when not all match.

If "building an index" means it's just the indices (not all rows of the table), doesn't that indirection mean an extra seek to get the full row? (I probably have a fundamental misunderstanding here)

You're right!

But you can sort the second column of the index too. So in our case, the index would be sorted by dept id, then employee id.

  deptid  empid
  1       1
  1       3
  1       7
  1       10
  ...
  2       4
  2       5
  2       9
  ...
  3       2
  3       6
  3       8

Now if we just do the basic thing and run through the index in order, we'll end up doing m sorted scans of the employee table, where m is the number of unique department ids. Not ideal, but if departments are large, still far better than seeking each employee individually.

But we can do better: If there are relatively few departments, the database can put a cursor at the beginning of each run of them:

  deptid  empid
  1       1    <- cursor
  1       3
  1       7
  1       10
  2       4    <- cursor
  2       5
  2       9
  3       2    <- cursor
  3       6
  3       8

Now the database can scan those cursors in parallel, merge sort them, and feed the result into scanning the employee id table. Now we again have a single sorted scan of the employee table, at the cost of m extra memory.

This isn't a general solution. If there are zillions of departments and each one has only a handful of employees, this doesn't work. And in modern databases low-cardinality indexes like our dept_emp_id index sometimes use more specialized data structures.

One of the beautiful/crazy things about working on databases is it's a product that promises an abstraction that can't actually be implemented perfectly in all cases. Databases uses all kinds of heuristics internally to decide different strategies to answer queries. And vendors are constantly refining, trying to get closer to an ideal they can never actually reach.

But this particular strategy is a common and important one and an example of why B-trees were so important to early relational systems.

Reply on news.ycombinator.com