Skip to main content
replaced http://stackoverflow.com/ with https://stackoverflow.com/
Source Link

Suppose one has a column of words on which one builds a BTREE index:

CREATE TABLE myTable (
  words VARCHAR(25),
  INDEX USING BTREE (words)
);

LOAD DATA LOCAL INFILE '/usr/share/dict/words' INTO TABLE myTable (words);

And now one wants to find the records which share the longest common prefix with some search query, e.g. 'foobar'. I thoughtI thought to do the following:

SELECT DISTINCT words
FROM   myTable
WHERE  words LIKE CASE
  WHEN NOT EXISTS (SELECT * FROM myTable WHERE words LIKE 'f%') THEN '%'
  WHEN NOT EXISTS (SELECT * FROM myTable WHERE words LIKE 'fo%') THEN 'f%'
  WHEN NOT EXISTS (SELECT * FROM myTable WHERE words LIKE 'foo%') THEN 'fo%'
  WHEN NOT EXISTS (SELECT * FROM myTable WHERE words LIKE 'foob%') THEN 'foo%'
  WHEN NOT EXISTS (SELECT * FROM myTable WHERE words LIKE 'fooba%') THEN 'foob%'
  WHEN NOT EXISTS (SELECT * FROM myTable WHERE words LIKE 'foobar%') THEN 'fooba%'
  ELSE 'foobar%'
END

Which is fine: it's very readable and performant; and it can easily be generated in application code.

However, this search should be even simpler to resolve: just walk through the index tree according to the search term until a branch does not exist, then return all the results that branch from the current node.

Granted that walking a path through the index only once instead of multiple times is probably a needless micro-optimisation, but it feels as though it should be possible: is it?

Suppose one has a column of words on which one builds a BTREE index:

CREATE TABLE myTable (
  words VARCHAR(25),
  INDEX USING BTREE (words)
);

LOAD DATA LOCAL INFILE '/usr/share/dict/words' INTO TABLE myTable (words);

And now one wants to find the records which share the longest common prefix with some search query, e.g. 'foobar'. I thought to do the following:

SELECT DISTINCT words
FROM   myTable
WHERE  words LIKE CASE
  WHEN NOT EXISTS (SELECT * FROM myTable WHERE words LIKE 'f%') THEN '%'
  WHEN NOT EXISTS (SELECT * FROM myTable WHERE words LIKE 'fo%') THEN 'f%'
  WHEN NOT EXISTS (SELECT * FROM myTable WHERE words LIKE 'foo%') THEN 'fo%'
  WHEN NOT EXISTS (SELECT * FROM myTable WHERE words LIKE 'foob%') THEN 'foo%'
  WHEN NOT EXISTS (SELECT * FROM myTable WHERE words LIKE 'fooba%') THEN 'foob%'
  WHEN NOT EXISTS (SELECT * FROM myTable WHERE words LIKE 'foobar%') THEN 'fooba%'
  ELSE 'foobar%'
END

Which is fine: it's very readable and performant; and it can easily be generated in application code.

However, this search should be even simpler to resolve: just walk through the index tree according to the search term until a branch does not exist, then return all the results that branch from the current node.

Granted that walking a path through the index only once instead of multiple times is probably a needless micro-optimisation, but it feels as though it should be possible: is it?

Suppose one has a column of words on which one builds a BTREE index:

CREATE TABLE myTable (
  words VARCHAR(25),
  INDEX USING BTREE (words)
);

LOAD DATA LOCAL INFILE '/usr/share/dict/words' INTO TABLE myTable (words);

And now one wants to find the records which share the longest common prefix with some search query, e.g. 'foobar'. I thought to do the following:

SELECT DISTINCT words
FROM   myTable
WHERE  words LIKE CASE
  WHEN NOT EXISTS (SELECT * FROM myTable WHERE words LIKE 'f%') THEN '%'
  WHEN NOT EXISTS (SELECT * FROM myTable WHERE words LIKE 'fo%') THEN 'f%'
  WHEN NOT EXISTS (SELECT * FROM myTable WHERE words LIKE 'foo%') THEN 'fo%'
  WHEN NOT EXISTS (SELECT * FROM myTable WHERE words LIKE 'foob%') THEN 'foo%'
  WHEN NOT EXISTS (SELECT * FROM myTable WHERE words LIKE 'fooba%') THEN 'foob%'
  WHEN NOT EXISTS (SELECT * FROM myTable WHERE words LIKE 'foobar%') THEN 'fooba%'
  ELSE 'foobar%'
END

Which is fine: it's very readable and performant; and it can easily be generated in application code.

However, this search should be even simpler to resolve: just walk through the index tree according to the search term until a branch does not exist, then return all the results that branch from the current node.

Granted that walking a path through the index only once instead of multiple times is probably a needless micro-optimisation, but it feels as though it should be possible: is it?

Tweeted twitter.com/#!/StackDBAs/status/276446427201277953
Source Link
eggyal
  • 331
  • 2
  • 8

Walking a BTREE index as far as possible in MySQL

Suppose one has a column of words on which one builds a BTREE index:

CREATE TABLE myTable (
  words VARCHAR(25),
  INDEX USING BTREE (words)
);

LOAD DATA LOCAL INFILE '/usr/share/dict/words' INTO TABLE myTable (words);

And now one wants to find the records which share the longest common prefix with some search query, e.g. 'foobar'. I thought to do the following:

SELECT DISTINCT words
FROM   myTable
WHERE  words LIKE CASE
  WHEN NOT EXISTS (SELECT * FROM myTable WHERE words LIKE 'f%') THEN '%'
  WHEN NOT EXISTS (SELECT * FROM myTable WHERE words LIKE 'fo%') THEN 'f%'
  WHEN NOT EXISTS (SELECT * FROM myTable WHERE words LIKE 'foo%') THEN 'fo%'
  WHEN NOT EXISTS (SELECT * FROM myTable WHERE words LIKE 'foob%') THEN 'foo%'
  WHEN NOT EXISTS (SELECT * FROM myTable WHERE words LIKE 'fooba%') THEN 'foob%'
  WHEN NOT EXISTS (SELECT * FROM myTable WHERE words LIKE 'foobar%') THEN 'fooba%'
  ELSE 'foobar%'
END

Which is fine: it's very readable and performant; and it can easily be generated in application code.

However, this search should be even simpler to resolve: just walk through the index tree according to the search term until a branch does not exist, then return all the results that branch from the current node.

Granted that walking a path through the index only once instead of multiple times is probably a needless micro-optimisation, but it feels as though it should be possible: is it?