List:General Discussion« Previous MessageNext Message »
From:Hank Date:October 6 2005 8:53pm
Subject:Re: How to avoid redundancy between PK and indices ?
View as plain text  
I understand what you're saying.

The problem is that if mysql attempted to do a query like you suggest:

>Select Count(*) From myTable Where a=1 And b=1 And c=1 And d=1 And e=1 And f=1;

It can only use one index for the query, and hopefully, the optimizer
will pick one of the six indexes with the fewest keys to scan.  But
even if it could virtualize the PK that way, it could still cause a
scan of millions of records while limiting the table scan to one of
the six non-unique keys.  In other words, it would/could take alot of
time to see if a record is unique upon inserting new records - not
something you'd be happy with performance wise, I'm sure.  Therefore,
a true, concatenated key that enforces uniqueness and can operate
immediately upon inserts is really necessary, regardless of what other
indexes are on the columns.

The type of query you're suggesting can be done with bitmapped indexes
(Oracle has them), where the indexes values are stored as bitmaps, and
you can combine them so Oracle uses multiple indexes in one query to
quickly pair down the records to scan.  Bitmapped indexes work very
well with the cardinality of keys is less than 10,000 (number of
unique key values).  In a nutshell, think of a field for sex/gender
and a table of 1 million records. A bitmapped index of that field
would only be 125,000 bytes long (1 million bits) (one bit=one
record), and to find all the "M" records, just map the "on" bits to
the record number in the datatable. For fields with larger possible
values (say, state of residence - 50 values), each location would be
represented by 6 bits. Pretty simple concept, but great performance
gains can be had over regular btree indexes.  I think this is what
you're getting at.

When I asked the MySQL AB folks at the first conference in Orlando a
couple of years ago about adding bitmapped index support in MySQL,
they didn't really know what I was talking about. The developer I
spoke to thought I was suggesting creating indexes on bitmapped
images. No, not exactly.   I hope they know what it is now, though,
and have (or already have) considered adding support for it in MySQL.

-Hank

On 10/5/05, C.R. Vegelin <vegelin@stripped> wrote:
> Hi Hank,
> You are quite right.
> I need separate non-unique indices on a, b, c, d, e and f to avoid table
> scans.
> And when each combi must be unique I need a Primary Key (a,b,c,d,e,f).
> And only Key a (a) seems to be redundant with the primary key ...
> Suppose there would be a PK (a,b,c,d,e,f) defined, without a "separate" PK
> index.
> And let's assume some rows like:
> > columns:    a   b   c   d   e   f
> > row1 has:  1  1   1   1   1   1
> > row2 has:  1  1   1   1   1   2
> > row3 has:  1  1   1   1   1   3
> > etc.
> Then checking on unique PK could be done by MySQL internally with:
> > Select Count(*) From myTable Where a=1 And b=1 And c=1 And d=1 And e=1 And
> > f=1;
> to avoid a duplicate primary key for row1, by using / joining the separate
> "index tables".
> With this Select query, MySQL could / should make use of the 6 existing
> separate indices.
> Uniqueness can be fully guaranteed with these 6 non-unique indices in this
> case.
> In other words, a separate PK index is fully redundant in this case, right ?
> In addition, it would save space without the longer concatenate key of
> a+b+c+d+e+f.
> Thanks, Cor
>
> ----- Original Message -----
> From: "Hank" <heskin@stripped>
> To: "C.R. Vegelin" <vegelin@stripped>
> Cc: <mysql@stripped>
> Sent: Wednesday, October 05, 2005 5:57 PM
> Subject: Re: How to avoid redundancy between PK and indices ?
>
>
> It depends.. if this is your create table statement:
>
> CREATE TABLE foo (
>  a smallint NOT NULL,
>  b smallint NOT NULL,
>  c smallint NOT NULL,
>  d smallint NOT NULL,
>  e smallint NOT NULL,
>  f smallint NOT NULL,
>  PRIMARY KEY  (a,b,c,d,e,f)
> );
>
> Then only one unique index is being created on the concatenate key of
> a+b+c+d+e+f.  Queries on any fields other than A will cause a full
> table scan.
>
> On the other hand, if your create table is:
>
> CREATE TABLE foo (
>  a smallint NOT NULL,
>  b smallint NOT NULL,
>  c smallint NOT NULL,
>  d smallint NOT NULL,
>  e smallint NOT NULL,
>  f smallint NOT NULL,
>  PRIMARY KEY  (a,b,c,d,e,f),
>  KEY a (a),
>  KEY b (b),
>  KEY c (c),
>  KEY d (d),
>  KEY e (e),
>  KEY f (f)
> );
>
> This will create the primary key, plus six additional indexes, each of
> which is queryable. But in this case, the "KEY a (a)" non-unique index
> is redundent with the primary key, so to do what you want - a unique
> index on a+b+c+d+e+f PLUS the ability to independtly search the  b c d
> e and f fields, here is the create table you'll need to use:
>
> CREATE TABLE foo (
>  a smallint NOT NULL,
>  b smallint NOT NULL,
>  c smallint NOT NULL,
>  d smallint NOT NULL,
>  e smallint NOT NULL,
>  f smallint NOT NULL,
>  PRIMARY KEY  (a,b,c,d,e,f),
>  KEY b (b),
>  KEY c (c),
>  KEY d (d),
>  KEY e (e),
>  KEY f (f)
> );
>
>
> --
>
> -Hank
>
> --
> MySQL General Mailing List
> For list archives: http://lists.mysql.com/mysql
> To unsubscribe:    http://lists.mysql.com/mysql?unsub=1
>
>
>
>
> --
> MySQL General Mailing List
> For list archives: http://lists.mysql.com/mysql
> To unsubscribe:    http://lists.mysql.com/mysql?unsub=1
>
>


--

-Hank
Thread
How to avoid redundancy between PK and indices ?C.R. Vegelin4 Oct
  • Re: How to avoid redundancy between PK and indices ?Alec.Cawley4 Oct
    • Re: How to avoid redundancy between PK and indices ?C.R. Vegelin4 Oct
      • Re: How to avoid redundancy between PK and indices ?Alec.Cawley4 Oct
  • Re: How to avoid redundancy between PK and indices ?Hank5 Oct
  • Re: How to avoid redundancy between PK and indices ?C.R. Vegelin6 Oct
    • Re: How to avoid redundancy between PK and indices ?Hank6 Oct