5 ms·

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

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)

aboodman 6y ago
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.

aboodman 6y ago

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.