5 ms·

Why exactly would it be so bad to just put a suitable index on the table containing strings? The time complexity of the resulting search would be the same, so I

Why exactly would it be so bad to just put a suitable index on the table containing strings? The time complexity of the resulting search would be the same, so I assume there will be some constant factor slowdowns. Is it that indices over string fields are stored inefficiently on disk? (If so, can that not be fixed in the db engine directly?) Or is this fine today but wasn't fine 15 years ago?

thehappypm 5y ago
At the worst you could concatenate the strings and have a single primary key.. or hash the string concatenation.
jerjerjer 5y ago
Yeah, while this is not optimal (ip should be converted into integer, time should be ts), the table would be small (as old entries could be safely deleted). The only real issue is the lack of indices. Also is helo field even needed?
- mjevans 5y ago
  Yes. A proper mail implementation won't randomize it, so it should be consistent. Depending on the design of the validation stages it might only need a case-normalized lookup to the string index table and that id as part of the final multi-column unique index, and in that last case only to convey to the database the expectations to optimize around (and require the data adhere to).
- ttfkam 5y ago
  IP should NOT be an integer. IPv6 does not fit in a database integer. MySQL has functions to convert to bytes. Even better, use a database with a proper inet datatype. That way you get correctness, space efficiency, and ability to intelligently index.
  - _3u10 5y ago
    In 2002 it definitely should have been an integer. In 2021 I’d recommend just turning off the IPv6 allocation or deleting it from DNS like this site does.
    - miyuru 5y ago
      > In 2021 I’d recommend just turning off the IPv6 allocation or deleting it from DNS like this site does. This is the funniest IPv6 excuse I've heard on HN. https://ipv6excuses.com/ https://ipv6excuses.com/
      - _3u10 5y ago
        Thanks! I was really surprised to find it myself. I used HN in some sample code for analyzing how SSL tickets are reused and was surprised to see an IPv4 address come back.
junon 5y ago
Indexing existed 15 years ago. The article never mentions why indexing didn't solve this problem. Super weird take on the author's part...
- quickthrower2 5y ago
  Surely more than 15 years! 50 maybe?
- ericbarrett 5y ago
  Early InnoDB* had pretty strict limits on varchar indexes and was not the most efficient. I don't remember the details but it's entirely possible the single-table format Rachel described ran head on into those limitations. Also remember indexes take space, and if you index all your text columns you'll balloon your DB size; and this was 2002, when that mattered a lot more even for text. Indexes also add write and compute burden for inserts/updates as now the DB engine has to compute and insert new index entries in addition to the row itself. Finally, normalizing your data while using the file-per-table setting (also not the default back then) can additionally provide better write & mixed throughout due to the writes being spread across multiple file descriptors and not fighting over as many shared locks. (The locking semantics for InnoDB have also improved massively in the last 19 years.) * Assuming the author used InnoDB and not MyISAM. The latter is a garbage engine that doesn't even provide basic crash/reboot durability, and was the default for years; using MyISAM was considered the #1 newbie MySQL mistake back then, and it happened all the time.
  - cogman10 5y ago
    > Also remember indexes take space Indexes take space, except for the clustered index. An important distinction. If the point of this table is always selecting based on IP, m_from, m_to, then clustering on those columns in that order would make sense. Of course, if it's expected that a lot of other query patterns will exist then it might make sense to only cluster on one of those columns and build indexes on the others.
  - noduerme 5y ago
    To me it seems that spreading it over four tables would lead to a lot more potential read locks while the big combined table is waiting for a join on each of the others, and some process is trying to insert on the others and link them to the main. This is assuming they were using foreign keys and the main table 4-column index was unique.
HelloNurse 5y ago
Normalization is important for deduplication, not only to index and compare a few short numbers instead of a few long string: those host names and email addresses are long and often repeated.
- remram 5y ago
  That's not what normalization is. You're thinking of deduplication or compression. This table is normalized as per usual database terminology.
  - ghayes 5y ago
    But if it’s guaranteed to be 1:1, why? The two implementations (normalized and denormalized) in that case should be completely isomorphic, quirks of the DB engine aside.
    - remram 5y ago
      Why what? I don't understand what you are asking.
mst 5y ago
It was fine on -some- databases 20 years ago. mysql of that era, less often.
dan-robertson 5y ago
I think the article describes the solution that was used and not necessarily the best solution. If they made the “obvious” mistake in the first case they mightn’t arrive at the best solution in the second. Adding the single index and using the four tables have the same worst case complexity for reads, O(log n), with different constants and massively beat scanning at O(n). It may be that the second solution wasn’t the best, or that it was better for write performance or memory usage—this was 2002 after all. It may also be the case that the cardinal it’s of some columns was low in such a way that the four table solution was better, but maybe getting the columns in the right order for a multi column index could do that too. Either way, I don’t think it really matters that much and doesn’t affect the point of the article.
AdrianB1 5y ago
Let's say the article is a critique to some system by someone that is not much better at databases. As many people also pointed out, a bad solution was replaced with a bad solution that works better for someone.
FlyingAvatar 5y ago
I had the same initial reaction in reading the post. My assumption was that indexing would have sufficiently sped up the query speed problem. However, normalizing the fields that contain repetitive data into separate tables could create significant space savings since the full text for each column would not need to stored for each row. Instead of 20-30 bytes per email address, a 4 byte (assuming 32-bit era) OID is stored in its place. It's pretty easy to imagine how quickly the savings would add up, and that it would be very helpful in the era before SSDs or even 1TB HDDs existed.

thehappypm 5y ago

At the worst you could concatenate the strings and have a single primary key.. or hash the string concatenation.

jerjerjer 5y ago

Yeah, while this is not optimal (ip should be converted into integer, time should be ts), the table would be small (as old entries could be safely deleted). The only real issue is the lack of indices. Also is helo field even needed?

mjevans 5y ago
Yes. A proper mail implementation won't randomize it, so it should be consistent. Depending on the design of the validation stages it might only need a case-normalized lookup to the string index table and that id as part of the final multi-column unique index, and in that last case only to convey to the database the expectations to optimize around (and require the data adhere to).
ttfkam 5y ago
IP should NOT be an integer. IPv6 does not fit in a database integer. MySQL has functions to convert to bytes. Even better, use a database with a proper inet datatype. That way you get correctness, space efficiency, and ability to intelligently index.
- _3u10 5y ago
  In 2002 it definitely should have been an integer. In 2021 I’d recommend just turning off the IPv6 allocation or deleting it from DNS like this site does.
  - miyuru 5y ago
    > In 2021 I’d recommend just turning off the IPv6 allocation or deleting it from DNS like this site does. This is the funniest IPv6 excuse I've heard on HN. https://ipv6excuses.com/ https://ipv6excuses.com/
    - _3u10 5y ago
      Thanks! I was really surprised to find it myself. I used HN in some sample code for analyzing how SSL tickets are reused and was surprised to see an IPv4 address come back.

junon 5y ago

Indexing existed 15 years ago. The article never mentions why indexing didn't solve this problem. Super weird take on the author's part...

quickthrower2 5y ago
Surely more than 15 years! 50 maybe?
ericbarrett 5y ago
Early InnoDB* had pretty strict limits on varchar indexes and was not the most efficient. I don't remember the details but it's entirely possible the single-table format Rachel described ran head on into those limitations. Also remember indexes take space, and if you index all your text columns you'll balloon your DB size; and this was 2002, when that mattered a lot more even for text. Indexes also add write and compute burden for inserts/updates as now the DB engine has to compute and insert new index entries in addition to the row itself. Finally, normalizing your data while using the file-per-table setting (also not the default back then) can additionally provide better write & mixed throughout due to the writes being spread across multiple file descriptors and not fighting over as many shared locks. (The locking semantics for InnoDB have also improved massively in the last 19 years.) * Assuming the author used InnoDB and not MyISAM. The latter is a garbage engine that doesn't even provide basic crash/reboot durability, and was the default for years; using MyISAM was considered the #1 newbie MySQL mistake back then, and it happened all the time.
- cogman10 5y ago
  > Also remember indexes take space Indexes take space, except for the clustered index. An important distinction. If the point of this table is always selecting based on IP, m_from, m_to, then clustering on those columns in that order would make sense. Of course, if it's expected that a lot of other query patterns will exist then it might make sense to only cluster on one of those columns and build indexes on the others.
- noduerme 5y ago
  To me it seems that spreading it over four tables would lead to a lot more potential read locks while the big combined table is waiting for a join on each of the others, and some process is trying to insert on the others and link them to the main. This is assuming they were using foreign keys and the main table 4-column index was unique.

HelloNurse 5y ago

Normalization is important for deduplication, not only to index and compare a few short numbers instead of a few long string: those host names and email addresses are long and often repeated.

remram 5y ago
That's not what normalization is. You're thinking of deduplication or compression. This table is normalized as per usual database terminology.
- ghayes 5y ago
  But if it’s guaranteed to be 1:1, why? The two implementations (normalized and denormalized) in that case should be completely isomorphic, quirks of the DB engine aside.
  - remram 5y ago
    Why what? I don't understand what you are asking.

mst 5y ago

It was fine on -some- databases 20 years ago. mysql of that era, less often.

dan-robertson 5y ago

I think the article describes the solution that was used and not necessarily the best solution. If they made the “obvious” mistake in the first case they mightn’t arrive at the best solution in the second. Adding the single index and using the four tables have the same worst case complexity for reads, O(log n), with different constants and massively beat scanning at O(n). It may be that the second solution wasn’t the best, or that it was better for write performance or memory usage—this was 2002 after all. It may also be the case that the cardinal it’s of some columns was low in such a way that the four table solution was better, but maybe getting the columns in the right order for a multi column index could do that too. Either way, I don’t think it really matters that much and doesn’t affect the point of the article.

AdrianB1 5y ago

Let's say the article is a critique to some system by someone that is not much better at databases. As many people also pointed out, a bad solution was replaced with a bad solution that works better for someone.

FlyingAvatar 5y ago

I had the same initial reaction in reading the post. My assumption was that indexing would have sufficiently sped up the query speed problem. However, normalizing the fields that contain repetitive data into separate tables could create significant space savings since the full text for each column would not need to stored for each row. Instead of 20-30 bytes per email address, a 4 byte (assuming 32-bit era) OID is stored in its place. It's pretty easy to imagine how quickly the savings would add up, and that it would be very helpful in the era before SSDs or even 1TB HDDs existed.