Inputs were not long enough to properly see either of the true wins in terms of reduced token counts for terser formats or their benefits in terms of avoiding stuffing the context window thereby potentially reducing accuracy. The test really needs to be conducted across multiple dimensions!
I write C# and rust fulltime. Native discriminated unions (and their integration throughout the ecosystem) are often the deciding factor when choosing rust over C#.
Very hard to imagine teams cross shopping C# and Rust and DU's being the deciding factor. The tool chains, workflows, and use cases are just so different, IMO. What heuristics were your team using to decide between the two?
I do like/respect C# but come on now. I know they're fixing it but the rest of the language was designed the same way and thus still has this vestigial layer of OOP-hubris
It's up to each team to decide how they want to write their code. TypeScript is the same with JS having a "vestigial" `class` (you can argue that "it's not the same", but nevertheless, it is possible to write OOP style code in JS/TS and in fact, is the norm in many packages like Nest.js).
The language is a tool; teams decide how to use the tool.
For me, it will be if they ever get checked errors of some sort. I don’t want to use a language with unchecked exceptions flying about everywhere. This isn't saying I want checked exceptions either, but I think if they get proper unions and then have some sort of error union type it would go a long way.
Are their ghostty builds statically linked by default or does zig follow in the footsteps of the C/C++ world and dynamically link everything? If statically linking (like rust) then a huge part of the incremental build times for apps with external dependencies is the lack of incremental linking in any of the major linkers. Wild linker is working on becoming the answer to this: https://github.com/davidlattimore/wild
ghostty statically links all its zig dependencies. The only dynamic libraries I can see are the usual suspects (libc, X11, Wayland, OpenGL, GTK, glib, libadwaita, etc).
A well-written JOIN against a well-designed database (regardless if we're talking postgres, SQLite, MySQL/MariaDB, or MS SQL) should not be slow. If it's slow, you're using it wrong.
Not a great article; I clicked expecting something super technical about SQLite internals and found a mix of rdbms basics and some misconceptions. The limitations in the blog post aren't really specific to SQLite (for the most part), they're just how indexes (indices) and database engines work across the board. And some of the things phrased as "SQLite [can't] do this" is stuff that wouldn't make sense to do in the first place.
If you understand what (multi-column) indexes are at the lowest level (i.e. what data structure they represent, how they are used by the database, what the code reading them would look like) then all of this makes immediate and natural sense. Indexes aren't magic. They're just a shortcut to help the the db engine find your data more effectively.
This doesn't require super complex understanding of data structures, btw. The same limitations and advice would apply if you were trying to, for example, search a stack of resumes sorted by one or more attributes. If you have them sorted by position, years of experience, and applicant's last name; you wouldn't be able to quickly grab all resumes for the HR Manager position that have a last name starting with J - after all, you sorted them by years of experience first! It's physically not possible! You can only use the first part of that index, the position, to jump to HR Manager resumes; then you would need to manually go through them one-by-one to grab only the ones starting with J for each years-of-experience subgroup (if any).
> I also can't think of a reason this is the case given the underlying data structures.
Ditto.
I suspect like me you are already familiar the underlying data structures. I'm now wondering why they wouldn't do use the B*Tree to search for thing_color. It's downright odd.
Granted in your example, assuming there are only a few colours, it would not be a big win. That's because all the colours for one date would likely fit in one B*Tree Node, which would be a leaf. When you search for a key in a single B*Tree node, you are forced to sequentially scan the sorted list of keys in the node because of the compression they use. Maybe SQLite thinks your example is the typical one that happens in most data sets, and so the extra effort of skipping through the tree isn't worth it.
But in Scour that wasn't true, and it seems to me in indexes with lots of columns it would often not be true.
It's a flattened tree, and you've used the index to reach a point where you have multiple child nodes that meet the precondition thing_date < 17. Some, but not all, of these have thing_color = blue, but the important part is that they're non-consecutive (the index can only give you one point-of-entry, so the data has to be consecutive or you need to do some amount of scan).
I asked an llm to give me an ascii representation so it'll be easier to see what I mean; consider the case where you want thing_date < 17 and thing_color = blue, the results that match are marked with an asterisk, but note that there's no way to get to them (ALL of them) directly:
Root (internal)
+---------------------+
| keys: 14 17 |
+----+--------+--------+
| | |
v v v
+----------------+ +----------------+ +----------------+
| Leaf P0 | | Leaf P1 | | Leaf P2 |
| (dates 10-13) | | (dates 14-16) | | (dates 17-20) |
|----------------| |----------------| |----------------|
| 10 | red |101 | | 14 | blue |141| | 17 | green |171|
| 11 | blue |111 |*| 14 | red |142| | 18 | blue |181|
| 12 | green |121 | | 15 | yellow|151| | 19 | red |191|
| 13 | red |131 | | 16 | blue |161|*| 20 | green |201|
+----------------+ +----------------+ +----------------+
Go back to my resume's example: you have the resumes sorted by application timestamp (chronologically) and position (alphabetically). You want to find all resumes received last Tuesday where position was "Senior Architect". You literally can't skip to the point where the next n consecutive results will be the results you seek, because you can't temporarily re-order them and within the subset of resumes where date > monday and date < wednesday, there may be multiple for "Senior Architect" but they didn't arrive one-after-the-other so they're interspersed with results you don't want. The correct to do here would be (if this is always the shape of the query you expect to get) to sort the resumes by (position, timestamp) instead, at which point you absolutely CAN jump to the position that guarantees the next results are (all the results) of the query ("Senior Architect", last Tuesday).
One important thing to keep in mind is that a SCAN is not the end of the world. You know your data and you know when it's ok (you expect most of the results to match and a few to be filtered out, in which case you're really not saving much time anyway) and when it's not (the scan will cover a huge range that contains only a few, widely interspersed results and you have no way of terminating early).
EDIT: In response to your exact question however, note that with a covering index you might not end up with a SCAN (i.e. you don't hit the table) even though it uses only the partial index (thing_date) and not (thing_date, thing_color)! It's still possible for it to avoid hitting the backing table and might return the results directly from the index - something it wouldn't have been able to do if the index was only (thing_date).
The key thing is "an index is a flattened tree", and for all us devs who haven't thought about trees in many years or younger folks who might not yet know, that means it's conceptually a bunch of nested maps/objects/dictionaries where the keys at each "level" are the columns in that same "level" of the index. To use a little bit of python, here's a list of the raw maps in your ascii art DB:
Notice that since this index is built from nested maps, if we want to use this index to find things, we HAVE to first do it by checking the keys in the "outermost" map, the 'date' column. It's a compound index but its order matters. This 'order matters' property is true in our map-based index and it's also true in our SQLite based index. It's also true that because this 'date < 17' is a range criteria, it has to check individual keys in the outermost map, which constitutes a SCAN of the index (smaller than a scan of the DB, but a scan nonetheless). To then find everything matching 'color = blue', it has to individually check all the color values in the result of the prior date SCAN in order to get down to only those with a 'color = blue'. As you can see, this index of date -> color isn't super helpful for the query 'WHERE color = blue AND date < 17' query. A query this index would be good for is a query like 'WHERE color = red AND date = 14'. That would not require any scans; if we were writing application code such a query with this index would be like calling `index[14][red]` which as we all know is super fast.
A better index for this, which is a different index, comes from swapping the order of the columns when forming the index. Instead of (date, color), this better index would be (color, date). That index looks like this:
Now with this new index to fulfill the exact same query of 'WHERE color = blue AND date < 17', we can do a `index[blue]` and then do a single SCAN of that intermediary to find only those `date < 17`. This still means our query does a SCAN, but it's scanning a smaller set of values (only 4 instead of at least 8 with the previous index) and we only do one scan instead of two scans.
Indexes in general are not flattened trees; they are just trees. Using a Python map as a mental model is fraught with peril since those are implemented as hash tables, which don't have ordering (which most database indexes need to support). So it's the wrong model.
For multidimensional indexes, you don't need to do anything fancy about nesting; you just need to have keys that have more than one component. To a first order, string concatenation is a good enough model. So in your case, here's what the index looks like:
Yes, this is true. I chose a nested-maps example because while it is inaccurate for actual DB applications, it's very helpful for explaining the limits of index ordering and the limits that range queries have when interacting with indexes. It's helpful to use maps as a first explanation because they're one of the most used datastructures that nearly all languages have built in (yes, I know, C, I'm talking about the other 9 of top 10 languages), and many work-a-day developers and dabblers will use nearly _only_ lists and maps (and objects/classes/structs) in their language of choice. I could've used Python's OrderedDict but I figured if I was going to stray away from "the most straightforward possible case using the datastructures everyone is already using daily", I'd have been better off jumping straight to a custom tree, like you've done.
> You can only use the first part of that index, the position, to jump to HR Manager resumes; then you would need to manually go through them one-by-one to grab only the ones starting with J for each years-of-experience subgroup (if any).
You're phrasing that like this situation — relying on an index formed by (key 1 that you know, key 2 that you don't know, key 3 that you want to depend on) — necessarily implies a sequential walk of everything within the HR manager subgroup.
But it doesn't; within each key-1 partition of the index, you can binary-search to find the boundaries of the key-2 partitions; and within those, you can binary-search to find the all (or, more commonly, the first) last_name[0] = "J" entry/entries. It's actually not overly slow (i.e. is often still a win over a naive index-partial seq scan) if the cardinality ratio of of key-2 : key-3 isn't too extreme (i.e. if you're saving useful amounts of time by eliminating enough key-3 entries from consideration per key-2 partition.)
(We use this approach quite a bit at $WORK — MySQL and Postgres people like to call this a https://wiki.postgresql.org/wiki/Loose_indexscan. [See the "Making use of a non-leading column of an index" section.])
Looking at the documentation, MySQL definitely has this feature now.
I don't think it understands when to use it.
I have a table where the primary key (A,B) is two integers. The first one is a single byte and only has a dozen distinct values. Any query I do based on just B ends up doing a table scan and being extremely slow. But if I add "WHERE A IN (1,2,3,4,5,6,7,8,9,10,11) AND" suddenly it's super fast.
So I'm stuck with a redundant index on just B if I don't want to add that cruft all over.
Anyway, yes, optimization is often possible in this kind of situation but don't trust your database engine to figure it out.
Well, yes, I omitted anything that may or may not happen to explain the general principle. Cardinality-based optimizations can and do take place, but they depend on the db being aware of the shape of your data (you need to analyze the tables often) and depend on internal factors and heuristics that are subject to change between releases, can't be assumed across different databases, and may or may not actually speed up the query (pathological cases certainly exist, even in the real world).
I agree, all of these rules aren't the right way to teach about how to reason about this. All of the perf properties described should fall out of the understanding that both tables and indices in SQLite are B-trees. B-trees have the following properties:
- can look up a key or key prefix in O(log N) time ("seek a cursor" in DB parlance, or maybe "find/find prefix and return an iterator" for regular programmers)
- can iterate to next row in amortized O(1) time ("advance a cursor" in DB parlance, or maybe "advance an iterator" for regular programmers). Note that unordered data structures like hash maps don't have this property. So the mental model has to start with thinking that tables/indices are ordered data structures or you're already lost.
A table is a b+tree where the key is the rowid and the value is the row (well, except for WITHOUT ROWID tables).
An index is a b-tree where the key is the indexed column(s) and the value is a rowid.
And SQLite generally only does simple nested loop joins. No hash joins etc. Just the most obvious joining that you could do if you yourself wrote database-like logic using ordered data structures with the same perf properties e.g. std::map.
From this it ought to be pretty obvious why column order in an index matters, etc.
Yeah, but who ever writes "x=0.9" as a constraint on a partial index? Really? Don't you know you aren't suppose to compare floating point quantities for equality?
If P is the expression on the partial index and Q is the WHERE clause of the query, then the partial index is only usable if Q implies P for all possible assignments of variables. A theorem prover is needed to establish this. Every RDBMS has one. The one inside SQLite is not terribly bright, true enough. It leans toward usually little memory and few CPU cycles. It does not do a good job if P contains "x=0.9". On the other hand, SQLite's theorem prover is decent if P contains "x IS NOT NULL", because in actual practice, probably about 90% of partial index WHERE clauses are some variation on "x IS NOT NULL".
The partial index expression does not always have to be exactly the same as what is in the WHERE clause of the query. SQLite will always find the match if P is a subset of Q; if Q can be rewritten as "R AND P". But if P is "x IS NOT NULL" and Q does anything that restricts x from being NULL, for example if Q contains "x>0", then SQLite's theorem prover will find that match too, even if "IS NOT NULL" never appears in Q.
Will the theorem prover in SQLite get better someday? Perhaps. It has gotten better over the years. The question becomes, how much more code space and query-planning CPU cycles are you willing to spend to get a slightly better query planner? This trade-off is different for a client/server database engine. With SQLite being embedded, the trade-off tends to fall more on the side of "keep it simple". If you have followed SQLite over many years, you might have noticed it is shifting toward more complex decision making as memory becomes cheaper and CPUs get faster. It's a tricky balancing act to find the sweet spot.
The top-level routine is here: <https://sqlite.org/src/info/aae36a5fbd17?ln=6767-6818>. Small (32-bit) integer literals are compared numerically, here: <https://sqlite.org/src/info/aae36a5fbd17?ln=6526>. They don't have to exactly match. So if you say "x=0x123" in the WHERE clause of the partial index and "x=291" in the WHERE clause of the query, and that will still work. However, 64-bit integer literals and floating-point literals are compared using strcmp(), here: <https://sqlite.org/src/info/aae36a5fbd17?ln=6570>, so they do need to match exactly, at least in the current implementation. Maybe that is something I should work on...
I wouldn’t say it’s so intuitive. We need more of these articles coming in — I learned nice things from this text, specially about the exact match over partial indexes, and to always QUERY EXPLAIN instead of assuming you’re right (my case haha).
What’s obvious for you might not be for someone else.
* I was impressed that WASD controls worked with my keyboard set to Dvorak :)
* Unfortunately have to second the comments about nausea; the oddly paced camera (it feels like it is panning through molasses then suddenly accelerates to switch views) is probably responsible, I'm guessing the "overshoot view then correct" "feature" is also a factor. Additionally seconding the comments about allowing the camera to follow the mouse (if feasible somehow while not losing cross-form-factor support) would go a long way to help here as well.
* The font that shows you where you are is cute in an orientalist sense, but imho it is very difficult to read (even knowing what it says from context clues and previous hints)
* Not a criticism but it is odd to have jumping when there is no mechanism that uses it in-game
* 99.99% a me problem: I had a hard time with spatial awareness and a difficulty building a mental map of the world and my best guess is that it's because I personally found the default field of view to be too "zoomed in".
> 99.99% a me problem: I had a hard time with spatial awareness and a difficulty building a mental map of the world and my best guess is that it's because I personally found the default field of view to be too "zoomed in".
Agreed on the spatial awareness issue. I think games like Mario Galaxy are a bit better in that regard because you see more of the world at a time. In this game you can sometimes not see what's 5m in front of you.
I think the article could use more on the cache invalidation and write-through (?) behavior. Are updates to the same file batched or written back to S3 immediately? Do you do anything with write conflicts, which one wins?
The article hints that cache invalidation is driven by the layers higher up the stack, relying on domain knowledge.
For example, the application may decide that all files are read-only, until expired a few days later.
Not clear about write-cache. My guess is that you will want some sort of redundancy when caching writes, so this goes beyond a library and becomes a service. Unless the domain level can absolve you of this concern by having redundancy elsewhere in the system (eg feed data from a durable store and replay if you lost some s3 writes).
I don't like relying on (release-only) llvm optimizations for a number of reasons, but primarily a) they break between releases, more often than you'd think, b) they're part of the reason why debug builds of rust software are so much slower (at runtime) than release builds, c) they're much harder to verify (and very opaque).
For non-performance-sensitive code, sure, go ahead and rely on the rust compiler to compile away the allocation of a whole new vector of a different type to convert from T to AtomicT, but where the performance matters, for my money I would go with the transmute 100% of the time (assuming the underlying type was decorated with #[transparent], though it would be nice if we could statically assert that). It'll perform better in debug mode, it's obvious what you are doing, it's guaranteed not to break in a minor rustc update, and it'll work with &mut [T] instead of an owned Vec<T> (which is a big one).
The particular optimisation for non-copying Vec -> IntoIter -> Vec transform is actually hard coded in the standard library as a special case of collecting an Iterator into a Vec. It doesn't rely on the backend for this.
Though this optimisation is treated as an implementation detail [1].
You misunderstood the purpose of that trick. The vector is not going to be accessed again, the idea is to move it to another thread so it can be dropped in parallel (never accessed).
reply