1

I'm using the nested set architecture to store URL hierarchies in the following InnoDB table on MySQL 5.7. From my research, I've learnt that using a SPATIAL index will significantly speed up any queries to retrieve a full path on tables that contain millions of rows. However, EXPLAIN is showing that sk_set shows up in possible_keys, but is then not used in the query plan. I've tried everything I can think of, and I could really use some expert guidance at this point. Any help is much appreciated.

My table definition:

--
-- Table structure for table `site_uri_layout`
--

CREATE TABLE `site_uri_layout` (
  `site_root_id` bigint(20) NOT NULL DEFAULT '0',
  `lft` bigint(20) NOT NULL DEFAULT '0' COMMENT 'Left hand side of nested set node',
  `rgt` bigint(20) NOT NULL DEFAULT '0' COMMENT 'Right hand side of nested set node',
  `set` linestring NOT NULL,
  `id` bigint(20) NOT NULL DEFAULT '0',
  `language_id` bigint(20) NOT NULL DEFAULT '0',
  `uri` varchar(255) COLLATE utf8mb4_unicode_ci NOT NULL DEFAULT ''
) ENGINE=InnoDB DEFAULT CHARSET=utf8mb4 COLLATE=utf8mb4_unicode_ci COMMENT='nested set' ROW_FORMAT=COMPACT;

--
-- Dumping data for table `site_uri_layout`
--

INSERT INTO `site_uri_layout` (`site_root_id`, `lft`, `rgt`, `set`, `id`, `language_id`, `uri`) VALUES
(2, 1, 32, '', 1, 0, ''),
(2, 2, 3, '', 5, 0, ''),
(2, 4, 17, '', 3, 0, ''),
(2, 5, 6, '', 8, 0, ''),
(2, 7, 14, '', 11, 0, ''),
(2, 8, 9, '', 14, 0, ''),
(2, 10, 11, '', 7, 0, ''),
(2, 12, 13, '', 15, 0, ''),
(2, 15, 16, '', 9, 0, ''),
(2, 18, 19, '', 6, 0, ''),
(2, 20, 21, '', 2, 0, ''),
(2, 22, 23, '', 16, 0, ''),
(2, 24, 31, '', 4, 0, ''),
(2, 25, 30, '', 10, 0, ''),
(2, 26, 27, '', 12, 0, ''),
(2, 28, 29, '', 13, 0, '');

--
-- Indexes for dumped tables
--

--
-- Indexes for table `site_uri_layout`
--
ALTER TABLE `site_uri_layout`
  ADD PRIMARY KEY (`site_root_id`,`lft`,`rgt`),
  ADD KEY `id` (`id`),
  ADD KEY `lft` (`lft`),
  ADD KEY `rgt` (`rgt`),
  ADD SPATIAL KEY `sk_set` (`set`);

My query:

SELECT
p.*
FROM
site_uri_layout AS n
LEFT JOIN site_uri_layout AS p ON (MBRWithin(Point(0, n.lft), p.set))
WHERE
n.id = 13
ORDER BY p.lft;

EXPLAIN shows:

1   SIMPLE  n       ref id  id  8   const   1   100.00  Using index; Using temporary; Using filesort
1   SIMPLE  p       ALL sk_set              16  100.00  Range checked for each record (index map: 0x10)

My test data set contains only 16 rows. I've edited out the raw geometric data. The 'pretty printed' nested set looks like this:

1
 5
 3
  8
  11
   14
   7
   15
  9
 6
 2
 16
 4
  10
   12
   13

I was expecting the optimizer to use sk_set as a key for this query, which was the whole point of setting up a SPATIAL index. What am I doing wrong?

  • +1 for a very thorough first question. p.s. welcome to the forum! :-) – Vérace Apr 16 at 17:14
  • Thank you, it's much appreciated. As an additional thought, what are the chances of the optimizer thinking that a full table scan might be faster for this small amount of rows, than to invoke the spatial key? – Ro Achterberg Apr 16 at 17:43
  • Define "small amound of rows" - certainly, less than ~ 5000 IMHO would mean that there's no point in doing an index scan - but that's just a guess. Why don't you do an EXPLAIN on your own data and see what it's doing? It's a bit difficult to know this kind of thing remotely. – Vérace Apr 16 at 17:48
  • So far I've only been testing with the above-mentioned 16 rows, but given your answer I will certainly look into scaling up my test set. Thank you for the insight. – Ro Achterberg Apr 16 at 17:51
  • At a University I was in, the library system (which they'd just upgraded) crashed. Apparently, they only tested on a few hundred records... Motto, always test with realistic data sets! I'd be prepared to bet lots of cash that a table with 16 records will always be immediately scanned without ref. to the index. Maybe you'll see quite different behaviour with 16,000? – Vérace Apr 16 at 17:54

Your Answer

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

Browse other questions tagged or ask your own question.