3 ms·

Amazing, servicing thousands of users for $150 a month. I'd clearly start writing my own indexing engine instead of using Posgresql, or maybe switching to digi

by fleitz 13y ago

Amazing, servicing thousands of users for $150 a month. I'd clearly start writing my own indexing engine instead of using Posgresql, or maybe switching to digital ocean/hetzner.

pjscott 13y ago
You don't know the size of their dataset, or the number of queries per second they need to support, or the latency requirements they have to meet. They do, and found that the obvious solution -- prefix queries on B-trees -- was too slow in practice. That their actual measurements trump your sarcasm, and you would know this if you'd read beyond the first paragraph before contemptuously dismissing the whole thing.
- fleitz 13y ago
  You don't know that I didn't read the whole article, and since I did I know their dataset is < 8GB because they are running EC2 medium instances and they said they have a budget of $150 which means they have a max of 2 servers. Also because I read the code I know it doesn't write to disk which means the dataset has to fit in RAM unless they are relying on the pager to swap memory for them. Since an 8 GB dataset is a fucking joke I made fun of their post in a sarcastic way. Also databases that lock are a fucking joke too, maybe I'll just repeat webscale a few times and that will make it performant. Should be titled "Startup throws out Mongo DB, gets decent performance"
  - argusdusty 13y ago
    EC2 medium instances come with 480GB space. Our database currently takes roughly 60GB. Ferret isn't running on this entire database, though - it's for auto-complete searches over our artist names, roughly 4MB. EDIT: Since I can't seem to reply to fleitz' below comment, I'll post a response here: 1. Boyer-Moore takes linear time. Ferret takes logarithmic time. Also, it's intended for searching over a single string, so using it on a dictionary would require some sort of hack like a termination character, taking slightly more memory and time. 2. A trie was one of the original iterations of Ferret. The reason it lost out was memory usage, requiring quadratic memory from every word (because this is a suffix search, not just a prefix search).
    - fleitz 13y ago
      4MB? Wouldn't boyer-moore, or a trie be very efficient for this?
      - deleted 13y ago
        [deleted]
      - deleted 13y ago
        [deleted]
      - thedufer 13y ago
        boyer-moore doesn't make sense if you're searching the same data set over and over again - it doesn't do any pre-processing on the data, which is why it can't be better than linear time.
        deleted 13y ago
        [deleted]
    - thedufer 13y ago
      I don't understand why the trie would take quadratic memory. I would expect it to be high-constant linear. Can you explain?
      - argusdusty 13y ago
        Because a trie works great for prefix searches, but we want substring searches, so we'd have to modify the trie to be more like a suffix tree, in it's simplest form inserting each possible suffix into the trie and doing a prefix search over that. For each word, adding up the length of each suffix gives quadratic memory.
        thedufer 13y ago
        That's linear. It's quadratic on each word, but that doesn't matter (this is why I mentioned high-constant). It's linear on the size of the data set, which is the important part. I'd be happy to code it up if you'd like. Even a binary tree on all suffixes (which would be somewhat simpler to write) would have the linear memory/logarithmic search time that you're looking for. Edit: I can't reply to you yet, so here goes: Calling it O(n.m^2) is, at best, an abuse of big-O notation. Since m is a constant (1), that is large-constant O(n). Which is what I've been saying. Yes, it increases the size of the data set. That would be the "large-constant" part. (1) If this is not the case, I would love to hear why.
deleted 13y ago
[deleted]

by fleitz 13y ago

Amazing, servicing thousands of users for $150 a month. I'd clearly start writing my own indexing engine instead of using Posgresql, or maybe switching to digital ocean/hetzner.

pjscott 13y ago

You don't know the size of their dataset, or the number of queries per second they need to support, or the latency requirements they have to meet. They do, and found that the obvious solution -- prefix queries on B-trees -- was too slow in practice. That their actual measurements trump your sarcasm, and you would know this if you'd read beyond the first paragraph before contemptuously dismissing the whole thing.

fleitz 13y ago
You don't know that I didn't read the whole article, and since I did I know their dataset is < 8GB because they are running EC2 medium instances and they said they have a budget of $150 which means they have a max of 2 servers. Also because I read the code I know it doesn't write to disk which means the dataset has to fit in RAM unless they are relying on the pager to swap memory for them. Since an 8 GB dataset is a fucking joke I made fun of their post in a sarcastic way. Also databases that lock are a fucking joke too, maybe I'll just repeat webscale a few times and that will make it performant. Should be titled "Startup throws out Mongo DB, gets decent performance"
- argusdusty 13y ago
  EC2 medium instances come with 480GB space. Our database currently takes roughly 60GB. Ferret isn't running on this entire database, though - it's for auto-complete searches over our artist names, roughly 4MB. EDIT: Since I can't seem to reply to fleitz' below comment, I'll post a response here: 1. Boyer-Moore takes linear time. Ferret takes logarithmic time. Also, it's intended for searching over a single string, so using it on a dictionary would require some sort of hack like a termination character, taking slightly more memory and time. 2. A trie was one of the original iterations of Ferret. The reason it lost out was memory usage, requiring quadratic memory from every word (because this is a suffix search, not just a prefix search).
  - fleitz 13y ago
    4MB? Wouldn't boyer-moore, or a trie be very efficient for this?
    - deleted 13y ago
      [deleted]
    - deleted 13y ago
      [deleted]
    - thedufer 13y ago
      boyer-moore doesn't make sense if you're searching the same data set over and over again - it doesn't do any pre-processing on the data, which is why it can't be better than linear time.
      - deleted 13y ago
        [deleted]
  - thedufer 13y ago
    I don't understand why the trie would take quadratic memory. I would expect it to be high-constant linear. Can you explain?
    - argusdusty 13y ago
      Because a trie works great for prefix searches, but we want substring searches, so we'd have to modify the trie to be more like a suffix tree, in it's simplest form inserting each possible suffix into the trie and doing a prefix search over that. For each word, adding up the length of each suffix gives quadratic memory.
      - thedufer 13y ago
        That's linear. It's quadratic on each word, but that doesn't matter (this is why I mentioned high-constant). It's linear on the size of the data set, which is the important part. I'd be happy to code it up if you'd like. Even a binary tree on all suffixes (which would be somewhat simpler to write) would have the linear memory/logarithmic search time that you're looking for. Edit: I can't reply to you yet, so here goes: Calling it O(n.m^2) is, at best, an abuse of big-O notation. Since m is a constant (1), that is large-constant O(n). Which is what I've been saying. Yes, it increases the size of the data set. That would be the "large-constant" part. (1) If this is not the case, I would love to hear why.

deleted 13y ago

[deleted]