3 ms·

There are some DBs where the order of fields doesn't matter in the compound index if you're just searching by one field (but of course is less efficient). I thi

by winrid 4y ago

There are some DBs where the order of fields doesn't matter in the compound index if you're just searching by one field (but of course is less efficient). I think Oracle supports this.

magicalhippo 4y ago
Good point, I reworded it to be more general. Can't recall seeing our DB being that clever.
thom 4y ago
Postgres is capable of doing this with some index types, but generally more slowly than a B-tree index being asked about its leftmost columns: https://www.postgresql.org/docs/current/indexes-multicolumn.html https://www.postgresql.org/docs/current/indexes-multicolumn.... Also worth noting that for very complex workloads that need to support arbitrary subsets of equality matches over columns, a Bloom filter might work best: https://www.postgresql.org/docs/current/bloom.html https://www.postgresql.org/docs/current/bloom.html
mattashii 4y ago
This dependz on the index type, but PostgreSQL also supports queries based on arbitrary attributes of multi-attribute indexes: both GIN and BRIN can be used for queries on any of the indexed expressions. Maybe eventually PG will also get index skip scans for btrees, which could allow for arbitrary columns searches in the btree; but we're not there yet by a large margin.
chrsig 4y ago
> (but of course is less efficient) This means the order does matter
- winrid 4y ago
  Yes...? Sorry my comment is not semantically accurate enough for you.
Sirupsen 4y ago
MySQL can do skip-scans https://dev.mysql.com/doc/refman/8.0/en/range-optimization.html#range-access-skip-scan https://dev.mysql.com/doc/refman/8.0/en/range-optimization.h...
- winrid 4y ago
  Nice, I did not know MySQL supported this. Someday I'll work with MySQL again, good to know.
dspillett 4y ago
All can search an index by just one field if it is the first field covered by the index, few can use an index if your predicate concerns the second and not the first. IIRC Oracle does support this and calls it a skip-scan. If the first column in the index is not very selective this can be very efficient, though if the first column is good in terms of selectivity then a skip-scan will be very inefficient and the DB might as well just scan the whole index. Given that a good choice of index usually has a fairly selective column as its first, and that unless storage space is very cramped you are likely better off just defining an extra index without the column that you want to not touch in some queries, this means that a skip-scan isn't helpful as often as one might think which is one of the reasons DB engine maintainers give for not spending time implementing and maintaining the feature. There are some use cases where having the option to skip-scan is definitely a significant bonus, but they are rare enough that I understand why most engine maintainers have not implemented them.
- winrid 4y ago
  Yes, I'm talking about skip-scan. I know pretty much all DBs can use compound index predicates for querying :) I can think of several cases where it would have been nice to have, sometimes "good enough" for a particular read pattern is better than additional write overhead etc.
  - dspillett 4y ago
    One arguement against implementing nice to have features in a SQL or similar engine is that it adds complexity to the query planner: to try make it bright enough to know when to use it without using it when it is significantly detrimental, without ballooning there time needed to make a good enough¹ choice, without making a less good choice often enough that the overall efficiency of the choices the planner makes is lowered. Of course an obvious counter is to implement it as an optional feature only used when explicitly requested by a query hint, with the counter counter being "is it worth the implementation effort given how rarely it will get used in that case?". Oracle's developers were seated by the benefits, other database developers have not been. There are ways to "emulate" the behaviour using CTEs to gain the expected benefit in at least some cases, but I've not experimented with this myself so can't speak for how well it works in practise, or if the extra legwork makes queries too convoluted to be easily maintained (or understood easily at all be future maintainers). ---- [1] noting that query planners do not strive to produce the best query plan, that is a Turing complete problem in many cases, instead trying to make a good enough choice in a reasonable amount of time

by winrid 4y ago

There are some DBs where the order of fields doesn't matter in the compound index if you're just searching by one field (but of course is less efficient). I think Oracle supports this.

magicalhippo 4y ago

Good point, I reworded it to be more general. Can't recall seeing our DB being that clever.

thom 4y ago

Postgres is capable of doing this with some index types, but generally more slowly than a B-tree index being asked about its leftmost columns: https://www.postgresql.org/docs/current/indexes-multicolumn.html https://www.postgresql.org/docs/current/indexes-multicolumn.... Also worth noting that for very complex workloads that need to support arbitrary subsets of equality matches over columns, a Bloom filter might work best: https://www.postgresql.org/docs/current/bloom.html https://www.postgresql.org/docs/current/bloom.html

mattashii 4y ago

This dependz on the index type, but PostgreSQL also supports queries based on arbitrary attributes of multi-attribute indexes: both GIN and BRIN can be used for queries on any of the indexed expressions. Maybe eventually PG will also get index skip scans for btrees, which could allow for arbitrary columns searches in the btree; but we're not there yet by a large margin.

chrsig 4y ago

> (but of course is less efficient) This means the order does matter

winrid 4y ago
Yes...? Sorry my comment is not semantically accurate enough for you.

Sirupsen 4y ago

MySQL can do skip-scans https://dev.mysql.com/doc/refman/8.0/en/range-optimization.html#range-access-skip-scan https://dev.mysql.com/doc/refman/8.0/en/range-optimization.h...

winrid 4y ago
Nice, I did not know MySQL supported this. Someday I'll work with MySQL again, good to know.

dspillett 4y ago

All can search an index by just one field if it is the first field covered by the index, few can use an index if your predicate concerns the second and not the first. IIRC Oracle does support this and calls it a skip-scan. If the first column in the index is not very selective this can be very efficient, though if the first column is good in terms of selectivity then a skip-scan will be very inefficient and the DB might as well just scan the whole index. Given that a good choice of index usually has a fairly selective column as its first, and that unless storage space is very cramped you are likely better off just defining an extra index without the column that you want to not touch in some queries, this means that a skip-scan isn't helpful as often as one might think which is one of the reasons DB engine maintainers give for not spending time implementing and maintaining the feature. There are some use cases where having the option to skip-scan is definitely a significant bonus, but they are rare enough that I understand why most engine maintainers have not implemented them.

winrid 4y ago
Yes, I'm talking about skip-scan. I know pretty much all DBs can use compound index predicates for querying :) I can think of several cases where it would have been nice to have, sometimes "good enough" for a particular read pattern is better than additional write overhead etc.
- dspillett 4y ago
  One arguement against implementing nice to have features in a SQL or similar engine is that it adds complexity to the query planner: to try make it bright enough to know when to use it without using it when it is significantly detrimental, without ballooning there time needed to make a good enough¹ choice, without making a less good choice often enough that the overall efficiency of the choices the planner makes is lowered. Of course an obvious counter is to implement it as an optional feature only used when explicitly requested by a query hint, with the counter counter being "is it worth the implementation effort given how rarely it will get used in that case?". Oracle's developers were seated by the benefits, other database developers have not been. There are ways to "emulate" the behaviour using CTEs to gain the expected benefit in at least some cases, but I've not experimented with this myself so can't speak for how well it works in practise, or if the extra legwork makes queries too convoluted to be easily maintained (or understood easily at all be future maintainers). ---- [1] noting that query planners do not strive to produce the best query plan, that is a Turing complete problem in many cases, instead trying to make a good enough choice in a reasonable amount of time