3

In MySQL / MariaDB I have this table with fixed-length rows (no VARCHAR, TEXT, etc)

CREATE TABLE trigram (
    id BIGINT(20) NOT NULL,
    trigram CHAR(3) NOT NULL COLLATE 'utf8mb4_general_ci',
    PRIMARY KEY (trigram, id) USING BTREE,
    INDEX id (id) USING BTREE
)
COLLATE='utf8mb4_general_ci' ENGINE=InnoDB ROW_FORMAT=COMPACT;

The table has tens of megarows, and gets production queries of this form

SELECT id FROM trigram 
 WHERE trigram IN ('dba', 'ba.', 'a.s', '.st', 'sta', 'tac', 'ack')
 GROUP BY ID HAVING COUNT(*) = 7

as well as INSERTs and DELETE FROM trigram WHERE id = 12345 maintenance queries. The indexes are appropriate for the table's query patterns.

This table is a poor-man's trigram index. (This poor man can't upgrade to postgreSQL and use their built in trigram indexes, sigh.) The sample query looks for ids that have 'dba.stack' strings in them. It's waaaay faster than content_column LIKE '%dba.stack%' once the trigram table is built.

Edit: What do I mean by "better"? Faster, more reliable, less buffer pool flushing in production, less maintenance burden on non-DBA users.

Question: Should I define this fixed-length-row table with ROW_FORMAT=COMPACT? Or is DYNAMIC called for? I've noticed it takes quite a bit less disk space with COMPACT.

Question: Any other suggestions or performance things to worry about?

My users (WordPress.org software users) are mostly on MariaDB 10.3+, but some are on MySQL 8, and a few are on MySQL 5.7-. I don't need to support Antelope or MyISAM legacy stuff.

Another edit:

My IN() query does a range scan on a test data set with 180K rows in the table. The JOIN to the UNION table suggested in an answer does a nested loop. The range scan takes less time. True on MariaDB 10.11, MySQL 8, and MySQL 5.7. For what it's worth. Looks like the skip-scan optimization works pretty well.

5
  • "Better" according to what criteria?
    – mustaccio
    Mar 25 at 15:15
  • Good question, please see my edit.
    – O. Jones
    Mar 25 at 15:20
  • Would ngram work for you?
    – Rick James
    Mar 27 at 18:56
  • It might. It's worth trying. I would still need a separate search table, because the fulltext searchable text for this application lies in some, but not all, values in three, count 'em, three of those notorious key/value tables in WordPress.
    – O. Jones
    Mar 27 at 19:40
  • Oh, darnit. ngram isn't in MariaDB. Most of my / our target users use MariaDB.
    – O. Jones
    Mar 27 at 20:40

5 Answers 5

4

For the table you show, I don't think COMPACT or DYNAMIC row format makes any significant difference.

In modern MySQL, DYNAMIC row format is the default. It is pretty much the same as COMPACT, except it improves storage of long TEXT and BLOB columns and allows longer index prefix lengths. None of these differences are relevant to the table you show.

You said the former row format results in a smaller table, but this might just be coincidence, since you probably achieved a defragmentation as you altered the table from one row format to the other.

If you OPTIMIZE TABLE on the table with the DYNAMIC row format, I expect you'll see it defragment and become smaller too.

There is nothing in InnoDB that gives an advantage for fixed-length rows. Rows are always located by using pointers within a page.

MyISAM has some advantage for fixed-length rows, because rows can be located by multiplying by the row length. But this is never done in InnoDB.

1
  • Right you are, Bill. Dropping and recreating the table (telling InnoDB to optimize it) makes the two row-formats consume almost the same amount of SSD / HDD space. Thanks.
    – O. Jones
    Mar 27 at 18:28
3

Another option would be to use multiple joins, to avoid grouping and counting and leveraging the fact that after the first few joins there are less and less rows satisfying the conditions:

SELECT t1.id FROM trigram t1
JOIN trigram t2 ON (t1.id=t2.id)
JOIN trigram t3 ON (t1.id=t3.id)
JOIN trigram t4 ON (t1.id=t4.id)
JOIN trigram t5 ON (t1.id=t5.id)
JOIN trigram t6 ON (t1.id=t6.id)
JOIN trigram t7 ON (t1.id=t7.id)
WHERE t1.trigram = 'dba' and t2.trigram ='ba.' 
  and t3.trigram = 'a.s' and t4.trigram ='.st' 
  and t5.trigram = 'sta' and t6.trigram ='tac' 
  and t7.trigram = 'ack'
3

FIXED vs DYNAMIC made a tiny difference in MyISAM. For InnoDB, there is essentially no such thing.

COMPACT vs DYNAMIC says what happens when a "big" column exists in a row. CHAR(3) does not qualify as "big".

"trigram" sounds like a fixed length datatype, so CHAR(3) is appropriate, but saves only the 1-byte "length" (relative to VARCHAR(3).

The utf8mb4 charset, on the other hand, forces even CHAR to be variable length since each character can be up to 4 bytes wide. If you only need English letters, use Ascii.

The following would cut the table size in half -- if you don't really need id:

CREATE TABLE trigram (
    trigram CHAR(3) NOT NULL COLLATE 'ascii_general_ci',
    PRIMARY KEY (trigram)
) ENGINE=InnoDB;

If you actually have more columns in the table, say so!

In picking a collation and charset:

_bin is faster than _general_ci is faster than the others
_ci is needed for case folding (or do you fold the incoming data?)
ascii and latin% are only one byte and faster than others

Antelope is old; Baraccuda is preferred. But because WP cannot seem to upgrade their customers, you must handle either.

"Skip-scan" is likely to be the best optimization; it seems to have been added in MySQL 8.0.13; I don't know if it is in MariaDB.

1
  • I need the id for sure. And the characters are utf8mb4 for sure, and I need to use a case-insensitive collation as I don't have client-side code capable of all the case-insensitivity code folding. And I've been around this block enough times to know I should tell you all the entire table definition. So I did. Thanks!
    – O. Jones
    Mar 25 at 21:19
2

Count is notoriuos for being slow.

But one of the performace problem can be addressed.by eliminating the IN clause, which would need to make a full table scan, ehivh xou would see if you make an EXPLAIN your query

SELECT 
    id
FROM
    trigram
        JOIN
    (SELECT 'dba' AS trigram UNION ALL SELECT 'ba.' UNION ALL SELECT 'a.s' UNION ALL SELECT '.st' UNION ALL SELECT 'sta' UNION ALL SELECT 'tac' UNION ALL SELECT 'ack') tr12 ON trigram.trigram = tr1.trigram
GROUP BY ID
HAVING COUNT(*) = 7
CREATE TABLE trigram (
    id BIGINT(20) NOT NULL,
    trigram CHAR(3) NOT NULL COLLATE 'utf8mb4_general_ci',
    PRIMARY KEY (trigram, id) USING BTREE,
    INDEX id (id) USING BTREE
)
COLLATE='utf8mb4_general_ci' ENGINE=InnoDB ROW_FORMAT=COMPACT;
EXPLAIN SELECT id FROM trigram 
 WHERE trigram IN ('dba', 'ba.', 'a.s', '.st', 'sta', 'tac', 'ack')
 GROUP BY ID HAVING COUNT(*) = 7

id select_type table partitions type possible_keys key key_len ref rows filtered Extra
1 SIMPLE trigram null index PRIMARY,id id 8 null 1 100.00 Using where; Using index
EXPLAIN
    SELECT 
        id
    FROM
        trigram
            JOIN
        (SELECT 'dba' AS trigram UNION ALL SELECT 'ba.' UNION ALL SELECT 'a.s' UNION ALL SELECT '.st' UNION ALL SELECT 'sta' UNION ALL SELECT 'tac' UNION ALL SELECT 'ack') tr1 ON trigram.trigram = tr1.trigram
    GROUP BY ID
    HAVING COUNT(*) = 7
id select_type table partitions type possible_keys key key_len ref rows filtered Extra
1 PRIMARY trigram null index PRIMARY,id id 8 null 1 100.00 Using index; Using temporary
1 PRIMARY <derived2> null ALL null null null null 7 14.29 Using where; Using join buffer (hash join)
2 DERIVED null null null null null null null null null No tables used
3 UNION null null null null null null null null null No tables used
4 UNION null null null null null null null null null No tables used
5 UNION null null null null null null null null null No tables used
6 UNION null null null null null null null null null No tables used
7 UNION null null null null null null null null null No tables used
8 UNION null null null null null null null null null No tables used

fiddle

3
  • 1
    My query plans don't show a full table scan, for what it's worth.
    – O. Jones
    Mar 25 at 16:08
  • see if the pan differ, and run the query
    – nbk
    Mar 25 at 16:09
  • My quey plans show range scans. And `COUNT(*) is indeed slow on tables, or materialized view, with a great many rowx. It's fine for result sets consisting of tens of rows.
    – O. Jones
    Mar 27 at 18:32
1

MySQL 5.7+ supports ngram indexing for full-text search. The chances are that this will be faster than your higher level implementation of the same feature. Set ngram_token_size=3 and you have trigram search.

The incantation you need is:

CREATE FULLTEXT INDEX ... WITH PARSER ngram;

Then use the standard FTS MATCH/AGAINST syntax to query it.

3
  • Yes, this is a good text-searrch feature, and you are right that it would be faster. But, the requirement I'm meeting requires the search to match things like a few characters of a SKU or purchase order number, or an Australian postcode, or whatever. So word-by-word FULLTEXT is not a suitable algorithm. Neither would the Relevanssi algorithm which searches for sttring matches in reverrse as well as forward. I really need col LIKE '%searchterm%' to be fast. Sadly. The stuff I'm doing is a PITA. Wish I could switch to PostgreSQL.
    – O. Jones
    Mar 27 at 18:39
  • 1
    @O.Jones The ngram parser for FTS literally does that, it works very similarly the PostgreSQL's trigram gin index. It isn't like the default FTS parser that does word stemming. Mar 27 at 23:07
  • Thanks for that information! Uhfortunately most of my target users use MariaDb, which doesn't support ngram.
    – O. Jones
    Mar 28 at 14:17

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.