Cases where full scans are better than indexes • Hacker News Board

Re: Cases where full scans are better than indexes

#71

Post by wswope » Thu, May 25, 2023, 4:49 PM UTC

jefftk wrote: post #53

cactusplant7374 wrote: post #15

Earlier quoted context omitted.

Indexes are such an easy thing to add. I don't get it. Seems like under optimization when you consider the tradeoffs.

Consider the example from the post of searching your shell history. If I don't need indexes I can just have it all in one flat file and use grep. Switching to a tool that supports indexing adds a lot of potential complexity and ways things could go wrong. Or consider the example of a developer querying frontend logs: queries are many orders of magnitude less common than writes, and (at the scale I used to work at) an…

I take the point of your examples as written in the post, but I think both of those are a bad comparison to the Reddit Premium subscriber table being discussed, because:

- We’re already using a database, so there’s very minimal added complexity

- This is an extremely hot table getting read millions of times a day

- The scale of the data isn’t well-bounded

- Usage patterns of the table are liable to change over time

Re: Cases where full scans are better than indexes

#72

Post by Mailtemi » Thu, May 25, 2023, 4:50 PM UTC

magicalhippo wrote: post #49

captainmuon wrote: post #25

The inverse is also true, often you have linear or even quadratic lookup times when something like an index can give you the result "immediately". I wish languages other than SQL had a concept of adding an index. Imagine a variant of Python's list or C++'s vector where you can add indicies on arbitrary fields of the contents, like a more flexible dict. Something like (pseudocode) books = List and then you could up by…

For C++ there's Boost's multi_index[1]. [1]: https://www.boost.org/doc/libs/1_82_0/libs/multi_index/doc/i...

I used multi_index a lot in the past. However, since I also frequently use sqlite, I have decided to exclusively use SQLite for multi_index in memory. If there is a problem, temporarily using sqlite as a file makes it a lot easier to track the issue. When multi_index patterns become too complex, it's natural to wrap them in a unit test specifically designed for sqlite (multi_index).

Re: Cases where full scans are better than indexes

#73

Post by mastax » Thu, May 25, 2023, 4:51 PM UTC

> I recently came across someone maintaining a 0.5GB full text index to support searching their shell history, 100k commands. I use grep on a flat file, and testing now it takes 200ms for a query across my 180k history entries.

I just started using a tool that stores my bash history and replaces C-R that I found on HN, it's written in Rust and uses SQLite of course. But it'll randomly cause commands to pause for a few seconds before executing (I think the hook to write the command to history gets blocked). Probably some simple bug, but I could just have my command history in a flat file and use rg or fzf in a 5 line shell function and have no lag.

Re: Cases where full scans are better than indexes

#74

Post by doodlesdev » Thu, May 25, 2023, 4:58 PM UTC

jefftk wrote: post #60

zokier wrote: post #4

> I use grep on a flat file, and testing now it takes 200ms for a query across my 180k history entries 200ms is order of magnitude more than I'd prefer for interactive use

I was going to say that it was "instant", because that's how it feels when using it, but got 200ms from running "time" on grepping it to include a number in the post.

Have you tried out using ripgrep [0] or fzf [1]? 200ms is quite a lot for history search, I'd expect search to be 20ms or less. In fact, it should be instantaneous as it should all fit in memory really. I've been using fzf and the searches are all faster than my monitor can display frames (so less than 16ms), although I only have 10k entries on my history as I clear it up once in a while.

[0]: https://github.com/BurntSushi/ripgrep

[1]: https://github.com/junegunn/fzf

Re: Cases where full scans are better than indexes

#75

Post by wswope » Thu, May 25, 2023, 5:01 PM UTC

titaniczero wrote: post #51

EGreg wrote: post #38

Earlier quoted context omitted.

Wait a second, the whole thing is you don't mind O(N) overhead in searching on every request, but you mind O(log N) overhead for updates and inserts?

Well, my guess is that updates and inserts are much more frequent than searches in their use case. You're assuming a balanced frequency for these operations and it hardly ever happens.

This is a read-heavy workload per the OP: https://news.ycombinator.com/item?id=36071799

Re: Cases where full scans are better than indexes

#76

Post by scarmig » Thu, May 25, 2023, 5:01 PM UTC

mastax wrote: post #73

> I recently came across someone maintaining a 0.5GB full text index to support searching their shell history, 100k commands. I use grep on a flat file, and testing now it takes 200ms for a query across my 180k history entries. I just started using a tool that stores my bash history and replaces C-R that I found on HN, it's written in Rust and uses SQLite of course. But it'll randomly cause commands to pause for a fe…

Can you share the tool? I've been thinking of making something similar for fun backed by a suffix array, interested in what else is out there.

Re: Cases where full scans are better than indexes

#77

Post by XCSme » Thu, May 25, 2023, 5:02 PM UTC

Why not just add the index? It future-proofs the performance and, as mentioned in the article, for small datasets, performance is not an issue anyway, so adding an index won't affect the small-dataset performance.

Re: Cases where full scans are better than indexes

#78

Post by cdcarter » Thu, May 25, 2023, 5:04 PM UTC

PaulHoule wrote: post #27

One of the problems of the RDF and SPARQL world is that the standard index structure considers the 6 possible permutations of ?subject ?predicate ?object. You can answer many queries with good efficiency with those indexes but building them gets brutal when you are handling billions of triples. I went to a talk at Dreamforce years ago where the CTO explained their database architecture and it is interesting that the…

> it is interesting that the core table in Saleforce is literally a collection of triples

This is... not entirely true. Most of the data for each "Object" in salesforce are stored in a series of columns on a single table. These are called "flex columns" in the official whitepaper describing the architecture. [0]

However, _foreign key relationships_ are indeed stored in a table that acts like a collection of triples. This is used in place of native foreign keys, and is indeed deeply integrated with the optimizer.

[0]: https://www.developerforce.com/media/ForcedotcomBookLibrary/...

Re: Cases where full scans are better than indexes

#79

Post by wswope » Thu, May 25, 2023, 5:04 PM UTC

scarmig wrote: post #76

mastax wrote: post #73

> I recently came across someone maintaining a 0.5GB full text index to support searching their shell history, 100k commands. I use grep on a flat file, and testing now it takes 200ms for a query across my 180k history entries. I just started using a tool that stores my bash history and replaces C-R that I found on HN, it's written in Rust and uses SQLite of course. But it'll randomly cause commands to pause for a fe…

Can you share the tool? I've been thinking of making something similar for fun backed by a suffix array, interested in what else is out there.

https://github.com/ellie/atuin

Re: Cases where full scans are better than indexes

#80

Post by vivegi » Thu, May 25, 2023, 5:07 PM UTC

Once upon a time (25+ years ago) I used to maintain an Oracle database that had around 50M records in its main table and 2M records in a related table. There were a dozen or so dimension (lookup) tables.

Each day, we would receive on the order of 100K records that had to be normalized and loaded into database. I am simplifying this a lot, but that was the gist of the process.

Our first design was a PL/SQL program that looped through the 100K records that would be loaded into a staging table from a flat file, performing the normalization and inserts into the destination tables. Given the size of our large tables, indices and the overhead of the inserts, we never could finish the batch process in the night that was reserved for the records intake.

We finally rewrote the entire thing using SQL, parallel table scans, staging tables and disabling and rebuilding the indexes and got the entire end-to-end intake process to finish in 45 minutes.

Set theory is your friend and SQL is great for that.