— миллионом строчек, начинающихся с foo.

INSERT INTO t(weight, description) VALUES ( generate_series(1, 1000000), 'foo' || md5(random()::text)); 

SELECT count(*) FROM t;
1000000

SELECT description FROM t LIMIT 10;
"foo89448d015071204ffcb90de6c4f0dd8b"
"foo810b2f42e05159604513413cfe7f4cd5"
"foo174e9210c3c7dd5fc5b3f8f9133ea812"
"foob837d4d2334aa8dfd4696a6becf2cccc"
"foo47f29c44426ea4b5e2d6e158d4190e76"
"foo9506414aaa59fd25cd90f954a5dbcfb6"
"foo8bb07854c1e65a7947bb65b0dffa4a1d"
"foo5b3a2367c08c95bdca35b4162debda4f"
"foodca671f581369cd9a349398d374ea804"
"foo4940ce3d9950052e38a78a50b55660a0"

EXPLAIN ANALYZE SELECT description,weight FROM t WHERE description LIKE 'foo%' ORDER BY weight DESC LIMIT 10;

"Limit  (cost=0.00..0.38 rows=10 width=40) (actual time=0.063..0.072 rows=10 loops=1)"
"  ->  Index Scan Backward using t_weight_index on t  (cost=0.00..37829.36 rows=999900 width=40) (actual time=0.062..0.068 rows=10 loops=1)"
"        Filter: (description ~~ 'foo%'::text)"
"Total runtime: 0.095 ms"

— миллионом рандомных строчек. Они нужны для того, чтобы слишком умный postgresql не додумался использовать индекс по weight вместо индекса по description.

INSERT INTO t(weight, description) VALUES ( generate_series(1, 1000000), md5(random()::text)); 

SELECT count(*) FROM t;
1000000

EXPLAIN ANALYZE SELECT description,weight FROM t WHERE description LIKE 'foo%' ORDER BY weight DESC LIMIT 10;

"Limit  (cost=10.81..10.84 rows=10 width=37) (actual time=8.663..8.666 rows=10 loops=1)"
"  ->  Sort  (cost=10.81..11.06 rows=100 width=37) (actual time=8.661..8.662 rows=10 loops=1)"
"        Sort Key: weight"
"        Sort Method: top-N heapsort  Memory: 25kB"
"        ->  Index Scan using t_description_index on t  (cost=0.00..8.65 rows=100 width=37) (actual time=0.042..7.379 rows=4066 loops=1)"
"              Index Cond: ((description ~>=~ 'foo'::text) AND (description ~<~ 'fop'::text))"
"              Filter: (description ~~ 'foo%'::text)"
"Total runtime: 8.741 ms"

Вот пример с данными:

insert into t(weight, description) values ( generate_series(1, 111000), md5(random()::text)); 
insert into t(weight, description) values ( generate_series(1, 400000), 'foofoo');

SELECT count(*) FROM t ;
511000

SELECT count(*) FROM t WHERE description LIKE 'foo%';
400000

 EXPLAIN ANALYZE SELECT description,weight FROM t WHERE description LIKE 'foo%' ORDER BY weight DESC LIMIT 10;

Limit  (cost=0.00..0.82 rows=10 width=16) (actual time=0.037..0.051 rows=10 loops=1)
   ->  Index Scan Backward using t_weight_index on t  (cost=0.00..32967.34 rows=400533 width=16) (actual time=0.035..0.048 rows=10 loops=1)
         Filter: (description ~~ 'foo%'::text)
         Rows Removed by Filter: 3
 Total runtime: 0.095 ms
(5 rows)

Остается открытым вопрос насчет производительности SELECT’а по GIN индексу с применением сортировки, если заданному префиксу соответствует большое количество фраз.

Для этого и существуют индексы, что бы ускорить поиск. Если брать GIN (а он в три раза быстрее GiST), то скорость будет достаточно высокой при милионах записей в таблице. Тут главное, что бы индекс в память помещался :) Ну а на сортировочное поле weight как уже писалось добавить отдельный индекс — для более быстрой сортировки по нему. Тогда нас не пугает, что при выборки много получилось — сортировка будет по индексу.

Как можно заметить, индекс по weight ( t_weight_index ) в данном случае не используется.

У меня в примере используется оба индекса. На всякий случай цитирую Тома Лейна, если вас ввело в заблуждение Bitmap Heap Scan:

Bitmap Index Scan / Bitmap Heap Scan / Recheck Cond

A plain Index Scan fetches one tuple-pointer at a time from the index, and immediately visits that tuple in the table. A bitmap scan fetches all the tuple-pointers from the index in one go, sorts them using an in-memory “bitmap” data structure, and then visits the table tuples in physical tuple-location order.

www.postgresql.org/[email protected]

weight — я не знаю как определяется вес, но если это коофициент ранжирования, то можно рассмотреть готовый функционал в БД:

SELECT title, ts_rank_cd(text_tsv, query) AS rank
FROM t, to_tsquery('п:*') query
WHERE query @@ text_tsv
ORDER BY rank DESC
LIMIT 10;

ts_rank_cd бужет измерять насколько ревалентный данные в text_tsv для запроса.

www.postgresql.org/...PARSING-QUERIES

И что бы долго не искать пример:

=> SELECT to_tsvector('iphone') @@ to_tsquery('iph:*');
 ?column? 
----------
 t
(1 row)

Думаю имелось ввиду, что и с помощью микроскопа можно забивать гвозди и он будет решать поставленную на него задачу — забивать гвозди. Но микроскоп не лучший вариант для решения подобной задачи. Если используется DevOps на проекте (тот же Chef или Puppet), то расширяемость и гибкость архитектуры «облака» как вопрос в таком случае не стоит — он может быть решен достаточно быстро при грамотном проекторовании.

Тем более при

потребляя при этом не более 200 Мб памяти

тут любой из предложенных инструментов справится, что уже упоминались (PostgreSQL, Solr, Lucene, ElasticSearch).

А зачем гадать. Сделаем расчет. Берем PostgreSQL и создадим таблицу с индексами:

CREATE TABLE t
(
  id serial NOT NULL,
  description text,
  weight integer,
  CONSTRAINT t_pkey PRIMARY KEY (id)
)
WITH (
  OIDS=FALSE
);

CREATE INDEX t_weight_index ON t USING btree(weight); // индекс по weight
CREATE INDEX t_description_index ON t (description text_pattern_ops); // индекс по LIKE патерну
CREATE INDEX t_description_lower_tag ON t USING btree(lower(description) text_pattern_ops); // индекс по LIKE патерну для lower case (так проще делать LIKE с игнором кейса)

И производим анализ запроса:

EXPLAIN SELECT description FROM t WHERE description LIKE 'foo%' ORDER BY weight DESC LIMIT 10;

"Limit  (cost=13.86..13.87 rows=6 width=36)"
"  ->  Sort  (cost=13.86..13.87 rows=6 width=36)"
"        Sort Key: weight"
"        ->  Bitmap Heap Scan on t  (cost=4.31..13.78 rows=6 width=36)"
"              Filter: (description ~~ 'foo%'::text)"
"              ->  Bitmap Index Scan on t_description_index  (cost=0.00..4.31 rows=6 width=0)"
"                    Index Cond: ((description ~>=~ 'foo'::text) AND (description ~<~ 'fop'::text))"

Игнорируем кейс:

EXPLAIN SELECT description FROM t WHERE lower(description) LIKE 'foo%' ORDER BY weight DESC LIMIT 10;

"Limit  (cost=13.88..13.89 rows=6 width=36)"
"  ->  Sort  (cost=13.88..13.89 rows=6 width=36)"
"        Sort Key: weight"
"        ->  Bitmap Heap Scan on t  (cost=4.32..13.80 rows=6 width=36)"
"              Filter: (lower(description) ~~ 'foo%'::text)"
"              ->  Bitmap Index Scan on t_description_lower_tag  (cost=0.00..4.32 rows=6 width=0)"
"                    Index Cond: ((lower(description) ~>=~ 'foo'::text) AND (lower(description) ~<~ 'fop'::text))"

Итак, мы получаем поиск по двум индексам (нет никакого Sequences Scan), тоесть сканирование идет не по строкам. А значит скорость поиска по индексам будет Log(N), где N — количество записей.

Такое решение подойдет?

А в чем будет фишка от подобных аналогов?

www.dbschemaeditor.com/OnlineDB.aspx
ondras.zarovi.cz/sql/demo
diagrams.seaquail.net
data-modeler.com/...count/Home.aspx
creately.com/...atabase-Diagram

Но в любом случае — удачи!