Status

Current state: [One of "Under Discussion", "Accepted", "Rejected"]

Discussion thread: 

JIRA or Github Issue: 

Released: <Doris Version>

Google Doc: <If the design in question is unclear or needs to be discussed and reviewed, a Google Doc can be used first to facilitate comments from others.>

Motivation

For text data, such as log, commodity description, OLAP users need to search in the text. For example search error logs that contains 'ERROR', 'Exception' keywords.

Currently, users use LIKE SQL function for text pattern matching in Doris and most OLAP databases. But LIKE is not slow since all rows need to be checked against the search pattern.

Related Research


In information retrieve area, fulltext search is a mature solution to find the content that match a given query. It's widely used by web search engine.

Elasticsearch support distributed fulltext search capability based on the open source search library lucene.

Some database, eg. MySQL, PostgreSQL, also add inverted index to support fulltext search.

In fact, the BITMAP index in Doris is a simple inverted index. But it lack text tokenization, efficient dictionary, search query syntax to support mature fulltext search.

Detailed Design


Functionality

  1. add a new index type INVERTED index
  2. support create INVERTED index with parser and fast fulltext search on text column with type char/varchar/string.
  3. support create INVERTED index without parser and fast equal, range operators on text column with type char/varchar/string.
  4. support create INVERTED index without parser and fast equal, range operators on numeric column with type int*/float*/date/datetime.

User interface


CREATE TABLE httplogs (
  ts datetime,
  clientip varchar(20),
  request string,
  status smallint,
  size int,
  INDEX idx_size (size) USING INVERTED,
  INDEX idx_status (status) USING INVERTED,
  INDEX idx_clientip (clientip) USING INVERTED PROPERTIES("parser"="none")
)
DUPLICATE KEY(ts)
DISTRIBUTED BY RANDOM BUCKETS 10
PROPERTIES ("replication_allocation" = "tag.location.default: 1"); -- replication 1 for localhost test


mysql> show index from httplogs;
+---------------------------------+------------+--------------+--------------+-------------+-----------+-------------+----------+--------+------+------------+---------+
| Table                           | Non_unique | Key_name     | Seq_in_index | Column_name | Collation | Cardinality | Sub_part | Packed | Null | Index_type | Comment |
+---------------------------------+------------+--------------+--------------+-------------+-----------+-------------+----------+--------+------+------------+---------+
| default_cluster:testdb.httplogs |            | idx_size     |              | size        |           |             |          |        |      | INVERTED   |         |
| default_cluster:testdb.httplogs |            | idx_status   |              | status      |           |             |          |        |      | INVERTED   |         |
| default_cluster:testdb.httplogs |            | idx_clientip |              | clientip    |           |             |          |        |      | INVERTED   |         |
+---------------------------------+------------+--------------+--------------+-------------+-----------+-------------+----------+--------+------+------------+---------+
3 rows in set (0.01 sec)
mysql> CREATE INDEX idx_request ON httplogs(request) USING INVERTED PROPERTIES("parser"="english");
Query OK, 0 rows affected (0.03 sec)


mysql> show index from httplogs;
+---------------------------------+------------+--------------+--------------+-------------+-----------+-------------+----------+--------+------+------------+---------+
| Table                           | Non_unique | Key_name     | Seq_in_index | Column_name | Collation | Cardinality | Sub_part | Packed | Null | Index_type | Comment |
+---------------------------------+------------+--------------+--------------+-------------+-----------+-------------+----------+--------+------+------------+---------+
| default_cluster:testdb.httplogs |            | idx_size     |              | size        |           |             |          |        |      | INVERTED   |         |
| default_cluster:testdb.httplogs |            | idx_status   |              | status      |           |             |          |        |      | INVERTED   |         |
| default_cluster:testdb.httplogs |            | idx_clientip |              | clientip    |           |             |          |        |      | INVERTED   |         |
| default_cluster:testdb.httplogs |            | idx_request  |              | request     |           |             |          |        |      | INVERTED   |         |
+---------------------------------+------------+--------------+--------------+-------------+-----------+-------------+----------+--------+------+------------+---------+
4 rows in set (0.00 sec)

// Other type of indexes:
CREATE INDEX idx_ngrambf ON tblname(username) USING NGRAM_BF PROPERTIES("size"="3", "other" = "256")  COMMENT "xxx";

CREATE INDEX idx ON tblname(username) USING BITMAP;

CREATE INDEX idx ON tblname(username) USING BLOOM_FILTER PROPERTIES("xxx"="asdasd");



-- search for request contains word 'login'
SELECT * FROM httplogs WHERE request MATCH 'login';

-- search for request contains word 'login' or 'error'
SELECT * FROM httplogs WHERE request MATCH 'login error';

-- search for request contains word 'login' and 'error'
SELECT * FROM httplogs WHERE request MATCH_ALL 'login';


SELECT * FROM httplogs WHERE status = 404;


SELECT COUNT() FROM httplogs WHERE size > 1024;


Scheduling


Step1: INVERTED index SQL spec and code interface

  Step1.1: SQL syntax and metadata

  Step1.2: index write interface and related call in write path

  Step1.3: index query interface and related call in query path

Step2: INVERTED index implementation for string type

Step3: INVERTED index implementation for numeric type

Step4: INVERTED index implementation for array type