0

So, according to this article, low-cardinality indexes may negatively impact performance: http://www.ibm.com/developerworks/data/library/techarticle/dm-1309cardinal/

Let's say you have 15-20 yes/no flags you want to be able to search on in any combination, with a kicker of having the final column of the index be your SORT BY column of high-cardinality values. Let's say we have 5 or so different columns we want to be able to sort on. We want our queries to always use an index without having to do any extra table scans or use temporary tables or do any extra sorting.

To create all of these indexes, it would require a permutation of all of these combinations - you're gonna have a lot of indexes to update. And it's possible it's going to be very inefficient if I understand the above article correctly.

Is it possible to consolidate all of your flags into one column using some kind of bitmasking technique? I'm vaguely familiar with the concept but pretty clueless when it comes to the execution.

P.S. If it makes a difference, I'm using MySQL.

2
  • Using bit datatype would involve little more work, but I think it is a good solution for your case: dev.mysql.com/doc/refman/5.7/en/bit-type.html – Jehad Keriaki Sep 19 '16 at 16:07
  • That seems interesting. Is there a way to use that to create an index to select on any combination of flag conditions? – Dan Sep 23 '16 at 10:58
1

Bottom line: Can't be optimized.

But, you can speed things up some by minimizing the size of the rows. Such will be especially beneficial if the table is too big to be cached.

Here's one approach.

Put the flags in a single MEDIUMINT UNSIGNED column. That will give you up to 24 yes/no values in a mere 3 bytes. DATE is 3 bytes. Your id is perhaps 4 bytes. Put those three things into an index -- total of 10 bytes (plus a lot of overhead).

I suggest this ordering: INDEX(date, flags, id). Then have code like:

SELECT id FROM tbl
    WHERE date >= ... AND date < ...
      AND (flags & $mask) = $value;

The steps will be

  1. Range scan using the first column of the index (date) to limit the number of index 'rows' to search.
  2. Perform the boolean operation to filter out rows based on the flags
  3. Get the id so you can go off to the table to get whatever other info you need.

Something like:

SELECT b.*
    FROM (
        SELECT ... -- as above
         ) AS filter
    JOIN tbl AS b  USING(id)
    ORDER BY ...

The ORDER BY on the end won't be able to use any index, but it will benefit from having all the filtering already done, so only the desired number of rows will be involved.

4
  • Okay, the masking bit of this answer is very helpful (although I don't know how to set $mask but I can probably google that). If we throw out the date range condition (remember I've already converted that into a set of flags), will the DB engine be able to utilize an index on (flags & $mask) = $value? – Dan Sep 24 '16 at 12:36
  • No, still a full scan (of either the index or the table). – Rick James Sep 25 '16 at 5:33
  • In MySQL, the nth bit is (1 << n). "OR" them together using |. Most languages have "shift" and "bitwise or" operators. – Rick James Sep 25 '16 at 5:34
  • Flags for dates seems really bad -- if the flag for "today" has to be cleared tonight and the flag for "yesterday" has to be set at that time. Or, maybe your flags have some other semantics? – Rick James Sep 25 '16 at 5:36
0

First, the article is for a specific vendor (DB2) so some of the reasoning may not be applicable to other DBMS:s. Nevertheless, having 20 indexes with cardinality <= 2 is probably a very bad idea regardless of which DBMS that is used.

Second, a lot of yes/no flags in a table may indicate a problem with the design (may indicate). I've seen tables with columns like is_male / is_female instead of gender.

I would advise against bit-masking the flags into say an integer. How should you index that? Say that you want to find all rows where bit 12 is 1, how should the query look, and how do you create an index that supports it?

Can you group the columns somehow? Say c1, c5, c9 and c11 is always used together in predicates. A good candidate for an index would then be:

CREATE INDEX ... ON ... (c1, c5, c9, c11)

etc.

7
  • Let's assume the table design is sound. One of the reasons for the flags is to consolidate time ranges, i.e. udpated_today, updated_past_week, updated_past_month, updated_past_year. To my knowledge, in MySQL, a compound index can't utilize a range column followed by a sort column, i.e. WHERE last_updated >= UNIX_TIMESTAMP() - 60*60*24*30 ORDER BY popularity DESC. Let's also ignore grouping columns for now. I'm curious about solving this specific problem. – Dan Sep 19 '16 at 14:04
  • I don't understand your description of the table, can you add a create table statement and some sample data to your question? – Lennart Sep 19 '16 at 18:17
  • The column updated_today, is that updated every day for all rows in the table that haven’t been updated that day? – Lennart Sep 21 '16 at 13:46
  • The reason behind the flag columns isn't really relevant to the solution but updated_today, for example, is set to 1 if the thing has been updated in the last day, 0 if not. – Dan Sep 23 '16 at 10:56
  • But that flag will be out of date tomorrow! The massive update to turn it off will be a killer. – Rick James Sep 24 '16 at 5:32

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.