3 ms·

I love everything about this article. This is the kind of database black arts that I really enjoy.

cogman10 3y ago
Black arts? Databases, pretty much all of them, are relatively simple creatures. If you can understand how a Tree structure and pointers work, you basically have most of the fundamental knowledge underlying the "black art" concepts of databases. The primary key/clustered index is how the data is physically stored and sorted, in a btree. Additional secondary indexes are generally quiet literally just secondary tables clustered on the secondary index key with primary key pointers. The job of the optimizer is to take when you have "Select foo from bar where baz=2" and ask questions like "Is there an index on baz. Does that index contain foo?" and then executing based on that. If there is an index on baz, it traverses the baz index looking for 2. If that index covers foo, then the query is done and it just pulls foo from the baz index. If it doesn't, then it queries the foo table with each of the primary keys in the baz index. If no index exists, then the db has to do a linear search through the table looking for "baz=2". When databases are slow, it's because you are forcing them to do O(n). When they are fast, it's because you use an index to turn that into a O(log n) search. (or in some cases, O(1).) The black black arts of databases is when you start getting into things like CTEs and windowed functions and their interactions with the indexes/optimizers. That's when it can be almost trivial to introduce O(n^2) performance if you aren't careful. NoSQL databases generally speaking, are implemented similar to how SQL databases are (just trees) but with less features and less guarantees.
- sgarland 3y ago
  > The primary key/clustered index is how the data is physically stored and sorted, in a btree. This is only true for RDBMS with a clustered index, like MySQL (assuming InnoDB) and MSSQL. Postgres stores tuples in a heap. The indices are generally B+trees, yes, but there is an extra level of indirection via the visibility map. There are a million gotchas, is the problem. You declared a partial index on foo as WHERE foo = true, but you’re querying for WHERE foo IS NOT false? I have bad news about the secret third state, WHERE foo IS NULL (not to mention the subtle differences between equality and IS). You made a UUIDv4 as the PK, thinking that since Postgres doesn’t cluster on it, it won’t suffer the same performance issues? Visibility map just wrecked your IOPS, enjoy the 7x hit to pages. You have an index and it’s not being used? Could be incorrect equality check (see first example), or inadequate auto-analyze on a write-heavy table leading to incorrect statistics, or any other number of things. RDBMS are much easier to understand if you know what a B+tree looks like, yes, and I highly recommend any backend dev take the time to do so. But there is so, so much more that can go wrong.
  - cogman10 3y ago
    > RDBMS are much easier to understand if you know what a B+tree looks like, yes, and I highly recommend any backend dev take the time to do so. But there is so, so much more that can go wrong. I agree, but that stuff that goes wrong isn't (in my experience) super common. At least, not until your tables reach fairly large (as in 10s of GBs of data) sizes. Which is why I'd suggest you still employ DBAs :). You wouldn't, for example, think about pulling out a filter index if you weren't dealing with fairly large tables where a full index might have an overly large negative impact. On the flip side, I've seen more than a few tables where a fundamental understanding of how the data is structured would have prevented a multitude of issues like bad or missing indexes. (My favorite that is depressingly common `Create Index blah ON foo(id, thingToIndex)`)
    - sgarland 3y ago
      > I agree, but that stuff that goes wrong isn't (in my experience) super common. At least, not until your tables reach fairly large (as in 10s of GBs of data) sizes. Which is why I'd suggest you still employ DBAs :). As a DBRE who oversees tables in the 100s of GB, some in TB range, these things happen entirely too often. But then, it’s my job. And yes, I whole-heartedly agree that past a certain scale, you need DB folks.
- gigatexal 3y ago
  The art comes from the querying engine and statistics and the time of day and if I’ve sacrificed a goat or not. Okay maybe not those last two but there’s still some nuance to this engine to engine.
- gigatexal 3y ago
  What indexes give you O(n)? IIRC btrees are o log n.
  - cogman10 3y ago
    No index gives you O(n) (technically O(n log n)). I'm talking about doing a table scan instead of a seek. Or did you mean O(1)? Some RDBMs have Hash indexes which given you (effectively) O(1) searches. For example: https://www.postgresql.org/docs/current/indexes-types.html#INDEXES-TYPES-HASH https://www.postgresql.org/docs/current/indexes-types.html#I...

Black arts? Databases, pretty much all of them, are relatively simple creatures. If you can understand how a Tree structure and pointers work, you basically have most of the fundamental knowledge underlying the "black art" concepts of databases. The primary key/clustered index is how the data is physically stored and sorted, in a btree. Additional secondary indexes are generally quiet literally just secondary tables clustered on the secondary index key with primary key pointers. The job of the optimizer is to take when you have "Select foo from bar where baz=2" and ask questions like "Is there an index on baz. Does that index contain foo?" and then executing based on that. If there is an index on baz, it traverses the baz index looking for 2. If that index covers foo, then the query is done and it just pulls foo from the baz index. If it doesn't, then it queries the foo table with each of the primary keys in the baz index. If no index exists, then the db has to do a linear search through the table looking for "baz=2". When databases are slow, it's because you are forcing them to do O(n). When they are fast, it's because you use an index to turn that into a O(log n) search. (or in some cases, O(1).) The black black arts of databases is when you start getting into things like CTEs and windowed functions and their interactions with the indexes/optimizers. That's when it can be almost trivial to introduce O(n^2) performance if you aren't careful. NoSQL databases generally speaking, are implemented similar to how SQL databases are (just trees) but with less features and less guarantees.

sgarland 3y ago
> The primary key/clustered index is how the data is physically stored and sorted, in a btree. This is only true for RDBMS with a clustered index, like MySQL (assuming InnoDB) and MSSQL. Postgres stores tuples in a heap. The indices are generally B+trees, yes, but there is an extra level of indirection via the visibility map. There are a million gotchas, is the problem. You declared a partial index on foo as WHERE foo = true, but you’re querying for WHERE foo IS NOT false? I have bad news about the secret third state, WHERE foo IS NULL (not to mention the subtle differences between equality and IS). You made a UUIDv4 as the PK, thinking that since Postgres doesn’t cluster on it, it won’t suffer the same performance issues? Visibility map just wrecked your IOPS, enjoy the 7x hit to pages. You have an index and it’s not being used? Could be incorrect equality check (see first example), or inadequate auto-analyze on a write-heavy table leading to incorrect statistics, or any other number of things. RDBMS are much easier to understand if you know what a B+tree looks like, yes, and I highly recommend any backend dev take the time to do so. But there is so, so much more that can go wrong.
- cogman10 3y ago
  > RDBMS are much easier to understand if you know what a B+tree looks like, yes, and I highly recommend any backend dev take the time to do so. But there is so, so much more that can go wrong. I agree, but that stuff that goes wrong isn't (in my experience) super common. At least, not until your tables reach fairly large (as in 10s of GBs of data) sizes. Which is why I'd suggest you still employ DBAs :). You wouldn't, for example, think about pulling out a filter index if you weren't dealing with fairly large tables where a full index might have an overly large negative impact. On the flip side, I've seen more than a few tables where a fundamental understanding of how the data is structured would have prevented a multitude of issues like bad or missing indexes. (My favorite that is depressingly common `Create Index blah ON foo(id, thingToIndex)`)
  - sgarland 3y ago
    > I agree, but that stuff that goes wrong isn't (in my experience) super common. At least, not until your tables reach fairly large (as in 10s of GBs of data) sizes. Which is why I'd suggest you still employ DBAs :). As a DBRE who oversees tables in the 100s of GB, some in TB range, these things happen entirely too often. But then, it’s my job. And yes, I whole-heartedly agree that past a certain scale, you need DB folks.
gigatexal 3y ago
The art comes from the querying engine and statistics and the time of day and if I’ve sacrificed a goat or not. Okay maybe not those last two but there’s still some nuance to this engine to engine.
gigatexal 3y ago
What indexes give you O(n)? IIRC btrees are o log n.
- cogman10 3y ago
  No index gives you O(n) (technically O(n log n)). I'm talking about doing a table scan instead of a seek. Or did you mean O(1)? Some RDBMs have Hash indexes which given you (effectively) O(1) searches. For example: https://www.postgresql.org/docs/current/indexes-types.html#INDEXES-TYPES-HASH https://www.postgresql.org/docs/current/indexes-types.html#I...