Is there a better way to create an alphabetic pagination index in PHP/MySQL?

Question

One of my standard behaviors for pagination within my CMSs is to show an alphabetic quickbar when sorting by an alpha column. For example, if the results are being sorted by Last Name, under the pagination I output a series of links, A to Z, to take you directly to the page for a particular first character.

Example:

Currently I'm doing this by getting all the results for that column, sorted alphabetically, and then looping through them all in PHP and recording what page the record appears on. This works fine when you're only dealing with a few hundred results, but I'm now working on a project that could potentially have several hundred thousand rows and it simply isn't a viable option.

Is there a more efficient method to produce this kind of index? Note that it also needs to handle more than just A-Z, since rows may begin with numbers or punctuation.

Edit for clarification: I'm not looking for a simple list of all the first characters, that's easy. I need to calculate what page of the total results the field starting with that character would be on. So say we're looking for someone named Walter, and I have 1000 rows, I need to know where in that 1-1000 range the W's start at.

Answer 1

I presume it's a varchar field, so have you considered the following:

SELECT DISTINCT SUBSTRING(lastname FROM 1 FOR 1) FROM mytable;

This will get you a distinct list of the first letters of the last name.

You can also use UPPER() to ensure you just get upper case characters. LEFT() will also achieve something similar, so you should experiment to see which performs quickest on your dataset.

Edit: If you also want counts:

SELECT DISTINCT SUBSTRING(lastname FROM 1 FOR 1) AS firstletter, COUNT(*) AS counter FROM mytable GROUP BY firstletter;

No need to do a second query for each letter.

Answer 2

$sql = "SELECT left(name, 1) AS firstchar FROM mytable ORDER BY name";

$result = mysql_query($sql) or die(mysql_error());

$letters = array();
$row = 0;
while($row = mysql_fetch_assoc($result)) {
    $row++;
    if (!isset($letters[$row['firstchar']])) {
        $letters[$row['firstchar']] = $row;
    }
}

This would give you an array keyed by the first letters, and the row number they first appeared on for the value:

a => 1,
b => 50,
c => 51,

etc...

There's probably some way of doing it purely in SQL, but MySQL itself doesn't have any 'row number' support built in, so it'd be a highly ugly query.