Modern databases abstract away a lot of database complexity for things like indices. It's true that these days you'd just add an index on the text column and go with it. Depending on your index type and data, the end result might be that the database turns the table into third normal form by creating separate lookup tables for strings, but hides it from the user. It could also create a smarter index that's less wasteful, but the end result is not so dissimilar. Manually doing these kinds of optimisations these days is usually a waste of effort or can even cause performance issues (e.g. that post on the front page yesterday about someone forgetting to add an index because mysql added them automatically).
All that doesn't mean it was probably a terrible design back when it was written. We're talking database tech of two decades ago, when XP had just come out and was considered a memory hog because it required 128MB of RAM to work well.
[0]: http://download.nust.na/pub6/mysql/doc/refman/4.1/en/create-...
The issue is that her analysis of what the issue was with her original table is completely wrong, and it's very weird given that the tone her "present" self is that it's so much more experienced and wise than her "inexperienced, naive" self.
My point is that she should give her inexperience self a break, all that was missing from her original implementation were some indexes.
Being able to look up each id via a single-string unique index would've almost certainly worked much better in those days.
More importantly, given the degree of uniqueness likely to be present in many of those columns (like the email addresses), she could have gotten away with not indexing on every column.
Your second is quite possibly true, but would have required experimentation to be sure of, and at some point "doing the thing that might be overkill but will definitely work" becomes a more effective use of developer time, especially when you have a groaning production system with live users involved.
I'd say there's very little performance gain in normalizing (it usually goes the other way anyway: normalize for good design, avoiding storing multiple copies of individual columns; de-normalize for performance).
I'm a little surprised by the tone of the article - sure, there were universities that taught computer science without a database course - but it's not like there weren't practical books on dB design in the 90s and onward?
I guess it's meant as a critique of the mentioned, but not linked other article "being discussed in the usual places".
A lot of this stuff was invented in the 70s, and was quite sophisticated by 2000. It just wasn't free, rather quite expensive. MySQL was pretty braindead at the time, and my recollection is that even postgres was not that hot either. We've very lucky they've come so far.
So you could've had a indexed column of "fingerprint", like
[email protected][email protected]
And indexed this, with only single WHERE in the query.
I don't understand at all how multiple tables thing would help compared to indices, and the whole post seemed kind of crazy to me for that reason. In fact if I had to guess multiple tables would've performed worse.
That is if I'm understanding the problem correctly at all.
"If you want to efficiently fuzzy-search through a combination of firstname + lastname + (etc), it's faster to make a generated column which concatenates them and index the generated column and do a text search on that."
(Doesn't have to be fuzzy-searching, but just a search in general, as there's a single column to scan per row rather than multiple)But also yeah I think just a compound UNIQUE constraint on the original columns would have worked
I'm pretty sure that the degree of normalization given in the end goes also well beyond 3rd-Normal-Form.
I think that is 5th Normal Form/6th Normal Form or so, almost as extreme as you can get:
https://en.wikipedia.org/wiki/Database_normalization#Satisfy...
The way I remember 3rd Normal Form is "Every table can stand alone as it's own coherent entity/has no cross-cutting concerns".
So if you have a "product" record, then your table might have "product.name", "product.price", "product.description", etc.
The end schema shown could be described as a "Star Schema" too, I believe (see image on right):
https://en.wikipedia.org/wiki/Star_schema#Example
This Rachel person is also much smarter than I am, and you can make just about anything work, so we're all bikeshedding anyways!
> I think that is 5th Normal Form/6th Normal Form or so, almost as extreme as you can get
The original schema is also in 5NF, unless there are constraints we aren't privy too.
5NF means you can't decompose a table into smaller tables without loss of information, unless each smaller table has a unique key in common with the original table (in formal terms, no non-trivial join dependencies except for those implied by the candidate key(s)).
The original table appears to meet this constraint: you could break it down into, e.g., four tables, one mapping the quad id to the IP address, one mapping it to the HELO string, etc. However, each of these would share a unique constraint with the original table, the quad id; hence the original table is in 5NF.
As for 6NF, I don't think the revised schema meets that: 6NF means you can't losslessly decompose the table at all. In the revised schema, the four tables mapping IP id to IP address etc. are in 6NF, but the table mapping quad id to a unique combination of IP id, HELO id, etc. is not: it could be decomposed into four tables similarly to how the original table could be.
(Interestingly, if the original table dropped the quad ID column and just relied on a composite primary key of IP address, HELO string, FROM address and TO address, it would be in 6NF.)
Let's say you know the lastname (Smith) but only the first letter of the firstname (A) - in the proposed scenario only the first letter of the firstname helps you narrow down the search to records starting with the letter (WHERE combined LIKE "A%SMITH"), you will have to check all the rows where firstname starts with "A" even if their lastname is not Smith. If there are two separate indexed columns the WHERE clause will look like this:
WHERE firstname like "A%" AND lastname = "Smith"
so the search can be restricted to smaller number of rows.
Of course having 2 indexes will have its costs like increased storage and slower writes.
Overall the blog post conveys a useful message but the table example is a bit confusing, it doesn't look like there are any functional dependencies in the original table so pointing to normalization as the solution sounds a bit odd.
Given that the query from the post is always about concrete values (as opposed to ranges) it sounds like the right way to index the table is to use hash index (which might not have been available back in 2002 in MySql).
https://www.postgresql.org/docs/current/textsearch-tables.ht...
Specifically, the part starting at the below paragraph, the explanation for which continues to the bottom of the page:
"Another approach is to create a separate tsvector column to hold the output of to_tsvector. To keep this column automatically up to date with its source data, use a stored generated column. This example is a concatenation of title and body, using coalesce to ensure that one field will still be indexed when the other is NULL:"
I have been told by PG wizards this same generated, concatenated single-column approach with an index on each individual column, plus the concatenated column, is the most effective way for things like ILIKE search as well.But I couldn't explain to you why
I don't know what kind of internal representation is used to store tsvector column type in PG, but I think GIN index lookups should be very simple to parallelize and combine (I believe a GIN index would basically be a map [word -> set_of_row_ids_that_contain_the_word] so you could perform them on all indexed columns at the same time and then compute intersection of the results?). But maybe two lookups in the same index could be somehow more efficient than two lookups in different indexes, I don't know.
I'm still sceptical about the LIKE/ILIKE scenario though. "WHERE firstname LIKE 'A%' and lastname LIKE 'Smith' " can easily discard all the Joneses and whatnot before even looking at the firstname column, whereas "WHERE combined_firstname_and_lastname LIKE 'A%SMITH' " will only be able to reject "Andrew Jones" after reading the entire string.
It will make sure that incorrect data is detected at the time of storage rather than at some indeterminate time in the future and it will likely be more efficient than arbitrary strings.
And in case of IP addresses, when you are using Postgres, it comes with an inet type that covers both ipv4 and ipv6, so you will be save from requirement changes
In the end you have to normalize anyways. Some databases have specific types. If not you have to pick a scheme and then ideally verify.
[email protected] [email protected] [email protected] [email protected]
Btw, storing just the domains, or inverting the email strings, would have speed up the comparison
But this was also back in the early '00s, when "data store" meant "relational DB", and anything that wasn't a RDBMS was probably either a research project or a toy that most people wouldn't be comfortable using in production.
Indeed; her problem looks to have been pre-memcached.
Multiple tables could be a big win if long email addresses are causing you a data size problem, but for this use case, I think a hash of the email would suffice.
These days, sure, the original schema plus indices would work fine on pretty much anything I can think of. Olde mysqls were a bit special though.
Some offices avoid many of the challenging patterns but not the vast majority. A lot of it is natural result of the newness of the industry and the high stakes of investment. Many of the work and organizational model assumptions mean that offering flexibility to employees complicates the already challenging management role. Given the power of those roles, this means workers largely must fit into the mold rather than designing a working relationship that meets all needs. As the needs change predictably over time a mounting pressure develops.
I'm only 17 years in but it has gotten harder and harder to find someone willing to leave me to simply code in peace and quiet and dig my brain into deep and interesting problems.
But I think she's if anything been in the industry longer than I have and the versions of mysql I first ran in production were a different story.
Anything you are doing conditional logic or joins on in SQL usually needs some sort of index.
However...
Consider the rows `a b c d e` and `f b h i j`. How many times will `b` be stored in the two formulations? 2 and 1, right? The data volume has a cost.
Consider the number of cycles to compare a string versus an integer. A string is, of course, a sequence of numbers. Given the alphabet has a small set of symbols you will necessarily have a character repeated as soon as you store more values than there are characters. Therefore the database would have to perform at least a second comparison. I imagine you're correctly objecting that in this case the string comparison happens either way but consider how this combines with the first point. Is the unique table on which the string comparisons are made smaller? Do you expect that the table with combinations of values will be larger than the table storing comparable values? Through this, does the combinations table using integer comparisons represent a larger proportion of the comparison workload? Clearly she found that to be the case. I would expect it to be the case as well.
No it didn't. Someone else put an index on the main table and that worked.
I think you're remarking about the relationship between normalized tables and indexes. That relationship does exist in some databases.
Please say more if I'm missing your point.
Therefore as long as the size data type (C language's "sizeof") used for an ID is inferior to the average size of the column contents then using an ID will very probably lead to a performance gain.
On some DB states and usage patterns (where commonly used data+index cannot fit in RAM: the caches (DB+OS) hit ratios are < to .99) this gain will be somewhat proportional (beware of diminishing returns) to the value of the ratio (total data+index size BEFORE using IDs)/(total data+index size AFTER using IDs).
Creating queries then becomes more difficult (one has to use 'JOIN'), however there are ways alleviate this: using views, "natural join"...
Some modern DB engines let you put data into an index, in order to spare an access to the data when the index is used (Postgresql: see the "INCLUDE" parameter of the "CREATE INDEX"). As far as I understand using a proper ID (<=> on average smaller than the data it represents) will also lead to a gain(?)
SELECT INET_NTOA(ip) FROM ips WHERE...
...in MySQL at least. (Which might be why MySQL has this function built in?)I guess if you ever need to match on a specific prefix storing the numeric IP might be an issue?
If you want to search for range, you can do:
SELECT INET_NTOA(ip) FROM ips WHERE ip > INET_NTOA(:startOfRange) AND ip < INET_NTOA(:endOfRange)This is what the post is about.
And btw, if they hadn't normalized those tables, it'd instead have been pointed out to them that their "post is bizzare..."
In most cases I'd expect just adding an index to the original table to be more efficient, but it depends on the type of the original column and if some data could be de-duplicated by the normalization.
On anything you're likely to be deploying today, just throwing a compound index at it is likely quite sufficient though.
(Some subtleties on projected values and such, but the point stands.)
There may well be some subtlety to the indexing capabilities of MySQL I’m unaware of though - could easily imagine myself making rookie mistakes like assuming that it has same indexing capabilities. So, to the post’s point - if I were working on a MySQL db I would probably benefit from an old hand’s advice to warn me away from dangerous assumptions.
On the other hand I also remember an extremely experienced MS SQL Server DBA giving me some terrible advice because what he had learned as a best practice on SQL Server 7 turned out to be a great way to not get any of the benefits of a new feature in SQL Server 2005.
Basically, we’re all beginners half the time.
It's a strange role where, in order to do your job well, you kind of have to hyper-specialize in the specific version of the tech that your MegaCorp employer uses, which is usually a bit older, because upgrading databases can be extremely costly and difficult.
Which is nonsense. The problem with the original DB design is that the appropriate columns weren't indexed. I don't know enough about the problem space to really know if a more normalized DB structure would be warranted, but from her description I would say it wasn't.