apparently you lot are a tumultuous and hairy lot, or the dealings with you are, or something ;-) as evidenced by my local .NET User Group comments :p

What, we're all crotchety and grumpy?

@SimonRigharts You mean like a DBA or something?

Morning all

Hi

Afternoon

Yo

You know, I'm a bit of a SDLC man, and there's a damn good reason for that. Today the business just reaffrmed why.

?

Is that OK or am I totally wrong?

You're right, B+ trees are not optimal for low-cardinality columns

afternoon chaps

'lo Mark

So predictable, so preventable.

Hi

@Gonsalu: But having an index on (status, id) where status is the low cardinality column is more probable to be good in a join (using id). Right?

more probable than what?

@ypercube Don't know about Oracle, but SQL Server has a star query optimisation where it builds a bitmap structure from the indexes in memory on the fly and resolves high-selectivity star queries by calculating the intersection.

Never understood why they didn't implement bitmap imdexes (maybe a patent held by Oracle?) but they keep insisting that this isn't much slower than bitmap index resolution.

Off the top of my head I don't know if Oracle has anything equivalent in its star transformation plans or whether it just relies on bitmap indexes.

SQL Server also has another cool feature besides the bitmap creation, that they call bitmap filtering

which only reads the data from the facts which satisfy the join

pushing the filtering to the scans

I think Oracle relies on bitmap indexes for that

I think DB2 does something similar - I seem to remember reading that DB2 didn't have a bitmap index per se but did something similar. Just googling for this.

@Gonsalu: Than a query from a single table (where the selectivity is not going to be good)

no, it won't be better than a table scan, because you have to scan the whole index anyway

No, it has another structure called an 'encoded vector index'

Normally if the selectivity is more than a few percent of the total row count it's usually cheaper to do a table scan and get the benefit of the sequential I/O.

@Gonsalu: But isn't the whole index smaller than the whole table? (that's my point). No idea if MySQL optimizer takes that into consideration.

Another DB2 link on indexes

en.wikibooks.org/wiki/…

@COTW: The question was about MySQL (that's why I mentioned B-trees). No other indexes available in InnoDB.

@ypercube OK. Not sure where Oracle came into it.

But, a single column index on a low cardinality column is usually redundant on any DBMS platform as for that level of selectivity a table scan or filter operation on something previously selected is usually cheaper.

@ypercube, yes, but you'd have to do a record lookup for each record that matches

which might or might not be faster

it depends

if it's a clustered index, you don't have a lookup, but you have to do a full clustered index scan, so you don't win anything there

Bitmap indexes on low cardinality columns are cheap because the compress massively with run length encoding and if you're combining several columns with a bitmap join and the join does filter the row count down to small enough that seeks are cost effective then the bitmap processing is much cheaper than table scanning.

if it's a secondary index, you have to scan the whole index, which is faster than a full table scan, but dependending on the number of records returned, might still be slower, due to the record lookup

MySQL doesn't have any star transformation plans, does it? I remember someone saying it can only do nested loop joins.

my google-fu fails to find star optimizations for MySQL

There are several improvements in recent MariaDB 5.3 release: kb.askmonty.org/en/what-is-mariadb-53

But I can't find any "star" in that page.

cool page

they explain all the optimizations

Hash joins - that's a big improvement.

index pushdowns is similar to the bitmap filtering, except with btrees

kb.askmonty.org/en/about-csv

heh

This is nice, too: Subquery optimizations map

Well, I have not done any testing. But in general, having multiple ways to do a query is one step. Choosing the best way (or a quite good one) is step 2 (and not easy with a many tables - star schema query). No idea, what they have done in that aspect.

Vote to ... discussion.