List:Internals« Previous MessageNext Message »
From:Michael Widenius Date:April 29 2003 12:46am
Subject:Re: feature proposal: auto increment prefix
View as plain text  
Hi!

Catching up with some very old emails...

>>>>> "Tim" == Tim Bunce <Tim.Bunce@stripped> writes:

Tim> This thread reminds me of a separate but related issue.
Tim> It can often be useful to have a way to generate globally unique
Tim> values that are guaranteed to not clash with any other value anywhere
Tim> at anytime (even when merging data from systems that were previously
Tim> not connected).

<cut>

Here is a description of a function that we plan to add to 4.1:

-------------

Implement a function OID() that should return a 64 bit unique number for each invocation.

To make this independent of the server, it should construct the number as follows:

server_id << 45 +
(unix_timestamp_for_mysqld_start & (1 << 32-1)) << 24 +
count++

(Here count is a 64 bit number)

The function has the following restrictions:

- We assume that server id < 512 (or at least the lowest 9 bits are unique)
- The high bit for timestamps are not relevant (shouldn't be safe)
- We don't execute more than 15 million OID() during one second
  (To be exact, during X seconds of server uptime, we are not executing
   more then X * 15 milllion OID() queries)
- That the timestamp is different if the server restarts

­-----------

One major benefit of the above is that it 'only' takes up 64 bits


Tim> p.s. Another plus point for GUIDs is that the binary storage can be
Tim> arranged to not be sequential and thereby avoid frequent re-balancing
Tim> of b-tree indices on inserts. (Though that could also be avoided for
Tim> indices on other types like integer auto_increment and date fields
Tim> if MySQL supported the ability to index a value in reverse:
Tim>
> http://download-east.oracle.com/otndoc/oracle9i/901_doc/server.901/a90125/statements_510.htm
Tim> )

I thought about the above but I don't really know if the argument is
releveant:

- When updating the leftmost node in a b-tree, MySQL doesn't do any
  index balancing but splits the page before the last key.
  The new leftmost key page will thus only contain 2 keys and the
  other key page will be almost full.

The nice thing with this algorism is that if you write sequential
numbers to the b-tree, you will get better:

- Most keys are written to the end of the key block, which is a fast
  operation as you don't have to move much data.
- Better key leaf utilisation as most key pages will be full
- More hits in the key cache as you will many times access the same
  key pages.
- Much fewer updated blocks in the key cache to be flushed out later

Regards,
Monty



Thread
feature proposal: auto increment prefixdvorakv16 Sep
  • Re: feature proposal: auto increment prefixArjen Lentz17 Sep
    • Re: feature proposal: auto increment prefixTim Bunce17 Sep
      • Re: feature proposal: auto increment prefixMichael Widenius29 Apr
        • Re: feature proposal: auto increment prefixTim Bunce29 Apr
          • Re[2]: feature proposal: auto increment prefixMiroslav Nachev29 Apr